数据结构课件-第四章.ppt

《数据结构课件-第四章.ppt》由会员分享，可在线阅读，更多相关《数据结构课件-第四章.ppt（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为串名，用单引号括起来的为串值，n为串的长度。,通常将字符在串中的序号称为该字符在串中的位置。,空格串：由一个或多个称为空格的特殊字符组成的串。,空串：n=0时的串为空串,返回主目录,4.1 串的定义,串(String)是零个或多个字符组成的

2、有限序列。一般记为：S=a1a2an(n0),子串：串中任意个连续的字符组成的子序列称为该串的子串。,主串：包含子串的串相应地称为主串。,其中S为串名，用单引号括起来的为串值，n为串的长度。,通常将字符在串中的序号称为该字符在串中的位置。,空格串：由一个或多个称为空格的特殊字符组成的串。,空串：n=0时的串为空串,返回主目录,串的抽象数据类型定义：,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是字符串常量 操作结果:生成

3、一个值等于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个字符起长度为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;若ST,则返回值0,（7）StrLength(S)初始条件:串S存在 操作结果:返回串S的长度,即串S中的元素个数,返回主目录,（8）StrClear(S)初始条件:串S存在操作结果:将S清为空串,（9）StrCat(S,T)初始条件:串S和T存在 操作结果:将串T的值连接在串S的后面,（10）SubString(Sub,S,pos,len)初始条件:串S存在,1posStrLength(S)且 1lenStrLength(S)-pos+1操作结果:用Sub返回串S的第pos个字符起长度为len的子串,返回主目录,（11）St

5、rIndex(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）StrDestroy(S)初始条件:串S存在 操作结果:销毁串S,返回主目录,4.2 抽象数据类型串的实现,4.2.1 定长顺序串,定长顺序串是将串设计成一种结构类型,串的存储分配是在编译时完成的。,串的定长顺序存储表示,#define MAXLEN

6、 20typedef struct/*串结构定义*/char chMAXLEN;int len;SString;,返回主目录,定长顺序串基本操作的实现算法,（1）串插入函数,见P83,返回主目录,（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)/*将

7、串t的值复制到串s中*/SString*s,t;int i;for(i=0;ichi=t.chi;s-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,返回主目录,（6）求串长函数,StrLength(s)/*返回串s的长度*/SStrin

8、g s;return(s.len);,返回主目录,（7）清空函数,StrClear(s)/*将串s置为空串*/SString*s;s-len=0;return(1);,返回主目录,（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;else if(s-lenlen;ichi=t.chi-s-len;s-len=MAXLEN;flag=0;else flag=0;/串s的长度等于MAXLEN,串t

9、不被连接return(flag);,（9）求子串函数,SubString(sub,s,pos,len)/*将串s中序号pos起len个字符复制到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)

10、;i=pos;j=0;while(i=t.len)return(i-j);else return(0);,返回主目录,4.2.2 堆串,这种存储方法以一组地址连续的存储单元存放串的字符序列，但它们的存储空间是在程序执行过程中动态分配的。系统将一个地址连续、容量很大的存储空间作为字符串的可用空间，每当建立一个新串时，系统就从这个空间中分配一个大小和字符串长度相同的空间存储新串的串值。,返回主目录,堆串的定义为:,typedef structint len；int start；HeapString；,其中len域指示串的长度,start域指示串的起始位置。借助此结构可以在串名和串值之间建立一个对应

11、关系，称为串名的存储映像。系统中所有串名的存储映像构成一个符号表。,返回主目录,堆串的存储映象示例,a=a program，b=string，c=process，free=23。,HeapMAXSIZE free=23,符号表,返回主目录,用C语言中的“堆”实现堆串,其定义为:,typedef struct char*ch；int len；HString；其中len域指示串的长度，ch域指示串的起始地址。,返回主目录,堆串的基本操作,(1)串赋值函数,StrAssign(s，tval)/*将字符常量tval的值赋给串s*/HString*s;char*tval;int len，i=0;if(s

12、-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|s-len=0)return(0);temp=(char*)malloc(s-len

13、+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);,返回主目录,(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);f

14、or(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 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*

15、/HString s;if(s.len=0)return(1);else return(0);,返回主目录,(6)串比较函数,StrCompare(s，t)/*若串s和t相等，则返回0，若st返回1，若st返回-1*/HString s，t;int i;for(i=0;is.len,返回主目录,(7)求串长函数,StrLength(s)/*返回串s的长度*/HString s;return(s.len);,返回主目录,(8)清空函数,StrClear(s)/*将串s置为空串*/HString*s;if(s-ch!=NULL)free(s-ch);s-ch=NULL;s-len=0;return

16、(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+)tempi=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

17、个字符复制到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(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;in

18、t i，j;if(s.len=0|t.len=0)return(0);i=pos;j=0;while(i=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等。,返回主目录,