数据结构课件第四章

《数据结构课件第四章》由会员分享，可在线阅读，更多相关《数据结构课件第四章（36页珍藏版）》请在装配图网上搜索。

1、第第4章章 串串4.1 串的定义串的定义4.2 抽象数据类型串的实现抽象数据类型串的实现4.2.1 定长顺序串定长顺序串4.2.2 堆串堆串4.2.3 块链串块链串4.3 串的应用举例：文本编辑串的应用举例：文本编辑返回主目录4.1 串的定义串的定义串串(String)是零个或多个字符组成的有限序列。是零个或多个字符组成的有限序列。一般记为：一般记为： S=a1a2an (n0)子串子串：串中任意个：串中任意个连续的字符连续的字符组成的子序列称为该串的子串。组成的子序列称为该串的子串。主串主串：包含子串的串相应地称为主串。：包含子串的串相应地称为主串。其中其中S为串名，用单引号括起来的为串值，

2、为串名，用单引号括起来的为串值， n为串的长度。为串的长度。通常将字符在串中的序号称为该字符在串中的位置。通常将字符在串中的序号称为该字符在串中的位置。空格串空格串：由一个或多个称为空格的特殊字符组成的串。：由一个或多个称为空格的特殊字符组成的串。空串空串： n=0时的串为空串时的串为空串返回主目录4.1 串的定义串的定义串串(String)是零个或多个字符组成的有限序列。是零个或多个字符组成的有限序列。一般记为：一般记为： S=a1a2an (n0)子串子串：串中任意个：串中任意个连续的字符连续的字符组成的子序列称为该串的子串。组成的子序列称为该串的子串。主串主串：包含子串的串相应地称为主串

3、。：包含子串的串相应地称为主串。其中其中S为串名，用单引号括起来的为串值，为串名，用单引号括起来的为串值， n为串的长度。为串的长度。通常将字符在串中的序号称为该字符在串中的位置。通常将字符在串中的序号称为该字符在串中的位置。空格串空格串：由一个或多个称为空格的特殊字符组成的串。：由一个或多个称为空格的特殊字符组成的串。空串空串： n=0时的串为空串时的串为空串返回主目录串的抽象数据类型定义：串的抽象数据类型定义：ADT String 数据对象数据对象:D=ai| ai CharacterSet,i=1,2,n; n0数据关系数据关系:R=| ai-1,ai D,i=2,n; n0基本操作：基

4、本操作： （1） StrAsign(S,chars)初始条件初始条件:chars是字符串常量是字符串常量 操作结果操作结果:生成一个值等于生成一个值等于chars的串的串S 返回主目录（2） StrInsert(S,pos,T)初始条件初始条件:串串S和和T存在存在,1posStrLength(S) +1 操作结果操作结果:在串在串S的第的第pos个字符之前插入串个字符之前插入串T （3） StrDelete(S,pos,len)初始条件初始条件: 串串S存在存在,1posStrLength(S) -len +1操作结果操作结果: 从串从串S中删除第中删除第pos个字符起长度为个字符起长度为l

5、en的子串的子串（4） StrCopy(S,T)初始条件初始条件: 串串S存在存在 操作结果操作结果:由串由串T复制得串复制得串S 返回主目录（5） StrEmpty(S)初始条件初始条件: 串串S存在存在 操作结果操作结果:若串若串S为空串为空串,则返回则返回TRUE,否则返回否则返回FALSE （6）StrCompare(S,T)初始条件初始条件: 串串S和和T存在存在操作结果操作结果:若若ST,则返回值则返回值0;若若S=T,则返回值则返回值=0;若若ST, 则返回值则返回值0 （7）StrLength(S)初始条件初始条件: 串串S存在存在 操作结果操作结果:返回串返回串S的长度的长度

6、,即串即串S中的元素个数中的元素个数 返回主目录（8）StrClear(S)初始条件初始条件: 串串S存在存在操作结果操作结果:将将S清为空串清为空串（9）StrCat(S,T)初始条件初始条件: 串串S和和T存在存在 操作结果操作结果:将串将串T的值连接在串的值连接在串S的后面的后面 （10）SubString(Sub,S,pos,len)初 始 条 件初 始 条 件 : 串串 S 存 在存 在 , 1 p o s S t r L e n g t h ( S ) 且且 1lenStrLength(S)-pos+1操作结果操作结果:用用Sub返回串返回串S的第的第pos个字符起长度为个字符起长

7、度为len的子串的子串 返回主目录（11）StrIndex(S,T,pos) 初始条件初始条件: 串串S和和T存在存在,T是非空串是非空串, 1posStrLength(S)操作结果操作结果:若串若串S中存在与串中存在与串T相同的子串相同的子串,则返回它在串则返回它在串S中第中第pos个字符之后第一次出现的位置个字符之后第一次出现的位置;否则返回否则返回0 （12）StrReplace(S,T,V)初始条件初始条件: 串串S,T和和V存在存在,且且T是非空串是非空串 操作结果操作结果:用用V替换串替换串S中出现的所有与中出现的所有与T相等的不重叠子串相等的不重叠子串 （13）StrDestro

8、y(S)初始条件初始条件: 串串S存在存在 操作结果操作结果:销毁串销毁串S 返回主目录4.2 抽象数据类型串的实现抽象数据类型串的实现4.2.1 定长顺序串定长顺序串定长顺序串是将串设计成一种结构类型定长顺序串是将串设计成一种结构类型,串的存储分串的存储分配是在编译时完成的。配是在编译时完成的。 串的定长顺序存储表示串的定长顺序存储表示#define MAXLEN 20typedef struct /*串结构定义串结构定义*/ char chMAXLEN; int len; SString; 返回主目录定长顺序串基本操作的实现算法定长顺序串基本操作的实现算法（1）串插入函数）串插入函数见见P

9、83返回主目录（2）串删除函数）串删除函数StrDelete(s,pos,len) /*在串在串s中删除从序号中删除从序号pos起起len个字符个字符*/SString *s; int pos,len;int i;if (pos(s-len-len) return(0);for (i=pos+len;ilen;i+) s-chi-len=s-chi;s-len=s-len - len;return(1);返回主目录（3）串复制函数）串复制函数StrCopy(s,t) /*将串将串t的值复制到串的值复制到串s中中*/SString *s,t;int i;for (i=0;ichi=t.chi;s

10、-len=t.len; 返回主目录（4）判空函数）判空函数StrEmpty(s) /*若串若串s为空为空(即串长为即串长为0),则返回则返回1,否则否则返回返回0*/SString s;if (s.len=0) return(1);else return(0); 返回主目录（5）串比较函数）串比较函数StrCompare(s,t) /*若串若串s和和t相等相等,则返回则返回0,若若st返回返回1,若若st返返回回-1。*/SString s,t;int i;for (i=0;is.len&ilen=0; return(1); 返回主目录（8）连接函数）连接函数StrCat(s,t) /*将串将

11、串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; else if (s-lenlen;ichi=t.chi-s-len;s-len=MAXLEN;flag=0; else flag=0;/ 串串s的长度等于的长度等于MAXLEN ,串串t不被连接不被连接return(flag); （9）求子串函数）求子串函数SubString(sub,s,pos,len) /*将串将串s中序号中序号pos起起len个

12、字符复制到个字符复制到sub中中*/SString *sub,s;int pos,len;int i;if (poss.len | lens.len-pos) sub-len=0;return(0);else for (i=0;ichi=s.chi+pos; sub-len=len;return(1); 返回主目录（10）定位函数）定位函数StrIndex(s,pos,t) /*求串求串t在串在串s中的位置中的位置*/SString s,t;int pos;int i,j;if (t.len=0) return(0); i=pos;j=0;while (is.len & j=t.len) re

13、turn(i-j);else return(0); 返回主目录4.2.2 堆串堆串这种存储方法以一组地址连续的存储单元存放这种存储方法以一组地址连续的存储单元存放串的字符序列，但它们的存储空间是在程序执串的字符序列，但它们的存储空间是在程序执行过程中动态分配的。系统将一个地址连续、行过程中动态分配的。系统将一个地址连续、容量很大的存储空间作为字符串的可用空间，容量很大的存储空间作为字符串的可用空间，每当建立一个新串时，系统就从这个空间中分每当建立一个新串时，系统就从这个空间中分配一个大小和字符串长度相同的空间存储新串配一个大小和字符串长度相同的空间存储新串的串值。的串值。 返回主目录堆串的定义

14、为堆串的定义为:typedef structint len； int start； HeapString； 其中其中len域指示串的长度域指示串的长度, start域指示串的起始位置。域指示串的起始位置。借助此结构可以在串名和串值之间建立一个对应关借助此结构可以在串名和串值之间建立一个对应关系，称为串名的存储映像。系统中所有串名的存储系，称为串名的存储映像。系统中所有串名的存储映像构成一个符号表。映像构成一个符号表。 返回主目录堆串的存储映象示例堆串的存储映象示例a=a program，b=string ，c=process，free=23。ap r o g r a m s tr in gp

15、r o c e s sHeapMAXSIZE free=23符号名符号名lenstarta90b79c716符号表符号表返回主目录用用C语言中的语言中的“堆堆”实现堆串实现堆串,其定义为其定义为:typedef struct char * ch； int len； HString；其中其中len域指示串的长度，域指示串的长度，ch域指示串的起始地址。域指示串的起始地址。返回主目录堆串的基本操作堆串的基本操作(1) 串赋值函数串赋值函数StrAssign(s，tval) /*将字符常量将字符常量tval的值赋给串的值赋给串s */HString *s; char *tval;int len，i=

16、0;if (s-ch!=NULL) free(s-ch);while (tvali!=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);返回主目录(2) 串插入函数串插入函数StrInsert(s，pos，t) /*在串在串s中序号为中序号为pos的字符之前插入串的字符之前插入串t */HString *s，t; int pos;int i;char *temp;if (poss-len

17、| s-len=0) return(0);temp=(char *)malloc(s-len + t.len);if (temp=NULL) return(0);for (i=0;ichi;for (i=0;it.len;i+) tempi+pos=t.chi;for (i=pos;ilen;i+) tempi + t.len=s-chi;s-len+=t.len; free(s-ch);s-ch=temp;return(1); 返回主目录(3) 串删除函数串删除函数StrDelete(s，pos，len) /*在串在串s中删除从序号中删除从序号pos起起len个字符个字符 */HString

18、 *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);返回主目录(4) 串复制函数串复制函数StrCopy(s，t) /*将串将串t的值复制到串的值复制到串s中中 */HString *s，t;int

19、 i;s-ch=(char *)malloc(t.len);if (s-ch=NULL) return(0);for (i=0;ichi=t.chi;s-len=t.len;return(1); 返回主目录(5) 判空函数判空函数StrEmpty(s) /*若串若串s为空为空(即串长为即串长为0)，则返回，则返回1，否则返回，否则返回0 */HString s;if (s.len=0) return(1);else return(0); 返回主目录(6) 串比较函数串比较函数StrCompare(s，t) /*若串若串s和和t相等，则返回相等，则返回0，若，若st返回返回1，若，若st返回返回

20、-1 */HString s，t;int i;for (i=0;is.len&ich!=NULL) free(s-ch); s-ch=NULL; s-len=0; return(1); 返回主目录(9) 连接函数连接函数StrCat(s，t) /*将串将串t联接在串联接在串s的后面的后面 */HString *s，t;int i;char *temp; temp=(char *)malloc(s-len + t.len);if (temp=NULL) return(0);for (i=0;ilen;i+) tempi=s-chi;for (i=s-len;ilen + t.len;i+) te

21、mpi=t.chi-s-len; s-len+=t.len; free(s-ch);s-ch=temp;return(1); 返回主目录(10) 求子串函数求子串函数SubString(sub，s，pos，len) /*将串将串s中序号中序号pos起起len个字符复制到个字符复制到sub中中 */HString *sub，s;int pos，len;int i;if (sub-ch!=NULL) free(sub-ch);if (poss.len | lens.len-pos) sub-ch=NULL;sub-len=0;return(0);else sub-ch=(char *)malloc

22、(len);if (sub-ch=NULL) return(0); for (i=0;ichi=s.chi+pos; sub-len=len; return(1); 返回主目录(11) 定位函数定位函数StrIndex(s，pos，t) /*求串求串t在串在串s中的位置中的位置 */HString s，t; int pos;int i，j;if (s.len=0 | t.len=0) return(0);i=pos;j=0;while (is.len & j=t.len) return(i-j);else return(0); 返回主目录4.2.3 块链串块链串#define BLOCK_SIZE typedef struct Blockchar chBLOCK_SIZE;struct Block *next; Block; typedef struct Block *head; Block *tail;int length; BLString; 返回主目录4.3 串的应用举例串的应用举例:文本编辑文本编辑文本编辑程序用于源程序的输入和修改，公文书信、文本编辑程序用于源程序的输入和修改，公文书信、报刊和书籍的编辑排版等。常用的文本编辑程序有报刊和书籍的编辑排版等。常用的文本编辑程序有Edit，WPS，Word等等 。返回主目录