《数据结构 第4章》由会员分享，可在线阅读，更多相关《数据结构 第4章（59页珍藏版）》请在金锄头文库上搜索。
1、第4章 串 4.1 串的定义4.2 抽象数据类型串的实现4.3 串的应用举例：文本编辑 4.1 串的定义 串(String)是零个或多个字符组成的有限序列。 一般记为： S=a1a2.an (n0)其中S是串的名字, 用单引号括起来的字符序列是串的值，ai(1in)可以是字母、数字或其它字符。n是串中字符的个数, 称为串的长度，n=0时的串称为空串 (Null String)。 串中任意个连续的字符组成的子序列称为该串的子串。 包含子串的串相应地称为主串。通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。 假如有串A=China Beij
2、ing, B=Beijing, C=China, 则它们的长度分别为13、7和5。B和C是A的子串, B在A中的位置是7, C在A中的位置是1。 当且仅当两个串的值相等时,称这两个串是相等的，即只有当两个串的长度相等, 并且每个对应位置的字符都相等时才相等。 串的抽象数据类型定义如下:ADT String 数据对象: D=ai| ai CharacterSet, i=1, 2, , n; n0数据关系: R=| ai-1, ai D, i=2, , n; n0基本操作:(1) StrAsign(S, chars)初始条件: chars是字符串常量。操作结果: 生成一个值等于chars的串S。
3、(2) StrInsert(S, pos, T)初始条件: 串S存在, 1posStrLength(S)+1。操作结果: 在串S的第pos个字符之前插入串T。(3) StrDelete(S, pos, len)初始条件: 串S存在, 1posStrLength(S)-len+1。操作结果: 从串S中删除第pos个字符起长度为len的子串。(4) StrCopy(S, T)初始条件: 串S存在。操作结果: 由串T复制得串S。 (5) StrEmpty(S)初始条件: 串S存在。操作结果: 若串S为空串, 则返回TRUE, 否则返回FALSE。(6) StrCompare(S, T)初始条件: 串
4、S和T存在。操作结果: 若ST, 则返回值0;如S=T, 则返回值=0;若SMAXLEN且pos+LCMAXLEN且pos+LCMAXLEN，则B的全部字符被舍弃（不需后移），并且C在插入时也有部分字符被舍弃。 与上述类似， 在进行串的连接时（假设原来串为A， 长度为LA, 待连接串为B， 长度为LB）， 也可能有三种情况： （1）连接后串长MAXLEN， 则直接将B加在A的后面。 （2）连接后串长MAXLEN且LAMAXLEN且LA=MAXLEN， 则B的全部字符被舍弃（不需连接）。 置换时的情况较为复杂，假设原串为A、长度为LA，被置换串为B、长度为LB, 置换串为C、 长度为LC，每次置
5、换位置为pos，则每次置换有三种可能： （1） LB=LC： 将C复制到A中pos起共LC个字符处。 （2） LBLC： 将A中B后的所有字符前移LB-LC个字符位置，然后将C复制到A中pos起共LC个字符。 （3） LBs-len+1) return(0); /* 插入位置不合法 */if (s-len + t.lenlen + t.len-1;i=t.len + pos-1;i-) s-chi=s-chi-t.len; for (i=0;ichi+pos-1=t.chi; s-len=s-len+t.len; else if (pos+t.lenMAXLEN, 但串t的字符序列可以全部插入
6、 */ for (i=MAXLEN-1;it.len+pos-1;i-) s-chi=s-chi-t.len; for (i=0;ichi+pos-1=t.chi; s-len=MAXLEN; else /* 串t的部分字符序列要舍弃 */ for (i=0;ichi+pos-1=t.chi; s-len=MAXLEN; return(1); 【算法4.1 串插入函数】 (2) 串删除函数。StrDelete(s, pos, len) /* 在串s中删除从序号pos起len个字符 */SString *s;int pos, len;int i;if (pos(s-len-len+1) retu
7、rn(0);for (i=pos+len-1;ilen;i+) s-chi-len=s-chi;s-len=s-len - len;return(1); 【算法4.2 串删除函数】 (3) 串复制函数。StrCopy(s, t) /* 将串t的值复制到串s中 */SString *s, t;int i;for (i=0;ichi=t.chi;s-len=t.len; 【算法4.3 串复制函数】 (4) 判空函数。StrEmpty(s) /* 若串s为空(即串长为0), 则返回1, 否则返回0 */SString s;if (s.len=0) return(1);else return(0);
8、【算法4.4 判空函数】 (5) 串比较函数。StrCompare(s, t) /* 若串s和t相等, 则返回0；若st，则返回0；若slen=0;return(1); 【算法4.7 清空函数】 (8) 连接函数。 StrCat(s, t) /* 将串t连接在串s的后面 */SString *s, t;int i, flag;if (s-len + t.lenlen; ilen + t.len; i+)s-chi=t.chi-s-len; s-len+=t.len;flag=1; for (i=0; ilen-1; i+)s-chi+ s-len =t.chi;else if (s-lenle
9、n;ichi=t.chi-s-len; s-len=MAXLEN;flag=0; else flag=0;/* 串s的长度等于MAXLEN, 串t不被连接 */return(flag); 【算法4.8 连接函数】 (9) 求子串函数。 SubString(sub, s, pos, len) /* 将串s中序号pos起len个字符复制到sub中 */SString *sub, s;int pos, len;int i;if (poss.len | lens.len-pos+1) sub-len=0;return(0);else for (i=0;ichi=s.chi+pos-1; sub-len
10、=len;return(1); 【算法4.9 求子串函数】 (10) 定位函数。 StrIndex(s, pos, t) /* 求串t在串s中的位置 */SString s, t;int pos;int i, j;if (t.len=0) return(0);i=pos-1;j=0;while (i=t.len) return(i-j);else return(0); 【算法4.10 定位函数】 4.2.2 堆串 假设以一维数组heap MAXSIZE 表示可供字符串进行动态分配的存储空间，并设 int free 指向heap 中未分配区域的开始地址(初始化时free=0) 。在程序执行过程中
11、，当生成一个新串时，就从free指示的位置起，为新串分配一个所需大小的存储空间，同时建立该串的描述。这种存储结构称为堆结构。 此时，堆串可定义如下： typedef structint len； int start； HeapString； 其中len域指示串的长度，start域指示串的起始位置。借助此结构可以在串名和串值之间建立一个对应关系，称为串名的存储映象。系统中所有串名的存储映象构成一个符号表。 图4.1是一个堆存储及符号表，其中a=a program， b=string ， c=process 图4.1 堆串的存储映象示例 aprogram stringprocessHeapMAXS
12、IZEFree=23符号名lenStart a90 b79 c716符号表在C语言中，已经有一个称为“堆”的自由存储空间，并可用malloc（）和free（）函数完成动态存储管理。因此，我们可以直接利用C语言中的“堆”实现堆串。此时，堆串可定义如下： typedef struct char * ch； int len； HString； (1) 串赋值函数。 StrAssign(s， tval) /* 将字符常量tval的值赋给串s */ HString *s; char *tval; int len， i=0; if (s-ch! =NULL) free(s-ch); while (tval
13、i! =0) i+; len=i; if (len) s-ch=(char *)malloc(len); if (s-ch=NULL) return(0); for (i=0;ichi=tvali; else s-ch=NULL; s-len=len; return(1); 【算法4.11 串赋值函数】 (2) 串插入函数。 StrInsert(s， pos， t) /* 在串s中序号为pos的字符之前插入串t */ HString *s， t; int pos; int i; char *temp; if (poss-len | s-len=0) return(0); temp=(char
14、*)malloc(s-len + t.len); if (temp=NULL) return(0); for (i=0;ichi; for (i=0;ilen;i+) tempi + t.len=s-chi; s-len+=t.len; free(s-ch);s-ch=temp; return(1); 【算法4.12 串插入函数】 (3) 串删除函数。StrDelete(s， pos， len) /* 在串s中删除从序号pos起的len个字符 */HString *s;int pos， len;int i;char *temp;if (pos(s-len - len) return(0);temp=(char *)malloc(s-len - len);if (temp=NULL) return(0);for (i=0;ichi;for (i=pos;ilen - len;i+) tempi=s-chi+len;s-len=s-len-len;free(s-ch);s-ch=temp;return(1);
