数据结构--第四章串学习教案.pptx

《数据结构--第四章串学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构--第四章串学习教案.pptx（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据结构数据结构(sh j ji u)-第四章串第四章串第一页，共46页。4.1 串的定义串的定义(dngy)串串(String)是零个或多个字符组成的有限是零个或多个字符组成的有限(yuxin)序列。序列。一般记为：一般记为： S=a1a2an (n0)子串：串中任意个连续子串：串中任意个连续(linx)的字符组成的子序列称为该串的子串。的字符组成的子序列称为该串的子串。主串主串：包含子串的串相应地称为主串。：包含子串的串相应地称为主串。其中其中S为串名，用单引号括起来的为串值，为串名，用单引号括起来的为串值， n为串的长度。为串的长度。通常将字符在串中的序号称为该字符在串中的位置。

2、通常将字符在串中的序号称为该字符在串中的位置。空格串空格串：由一个或多个称为空格的特殊字符组成的串。：由一个或多个称为空格的特殊字符组成的串。空串空串： n=0时的串为空串时的串为空串第1页/共46页第二页，共46页。串的抽象数据类型定义串的抽象数据类型定义(dngy)：ADT String 数据对象数据对象(duxing):D=ai| ai CharacterSet,i=1,2,n; n0数据关系数据关系:R=| ai-1,ai D,i=2,n; n0基本操作：基本操作： （1） StrAsign(S,chars)初始条件:chars是字符串常量 操作结果(ji gu):生成一个值等于cha

3、rs的串S 第2页/共46页第三页，共46页。（2） StrInsert(S,pos,T)初始条件初始条件:串串S和和T存在存在,1posStrLength(S) +1 操作结果操作结果(ji gu):在串在串S的第的第pos个字符之前插入个字符之前插入串串T （3） StrDelete(S,pos,len)初始条件初始条件: 串串S存在存在,1posStrLength(S) -len +1操作操作(cozu)结果结果: 从串从串S中删除第中删除第pos个字符起长度为个字符起长度为len的子串的子串（4） StrCopy(S,T)初始条件初始条件: 串串S存在存在 操作结果操作结果(ji gu

4、):由串由串T复制得串复制得串S 第3页/共46页第四页，共46页。（5） StrEmpty(S)初始条件初始条件: 串串S存在存在 操作结果操作结果(ji gu):若串若串S为空串为空串,则返回则返回TRUE,否则返回否则返回FALSE （6）StrCompare(S,T)初始条件初始条件: 串串S和和T存在存在(cnzi)操作结果操作结果:若若ST,则返回值则返回值0;若若S=T,则返回值则返回值=0;若若ST, 则返回值则返回值0 （7）StrLength(S)初始条件初始条件: 串串S存在存在 操作结果操作结果:返回返回(fnhu)串串S的长度的长度,即串即串S中的元素个中的元素个数数

5、 第4页/共46页第五页，共46页。（8）StrClear(S)初始条件初始条件: 串串S存在存在操作操作(cozu)结果结果:将将S清为空串清为空串（9）StrCat(S,T)初始条件初始条件: 串串S和和T存在存在 操作结果操作结果(ji gu):将串将串T的值连接在串的值连接在串S的后面的后面 （10）SubString(Sub,S,pos,len)初始条件初始条件: 串串S存在存在, 1posStrLength(S)且且 1lenStrLength(S)-pos+1操作操作(cozu)结果结果:用用Sub返回串返回串S的第的第pos个字符起个字符起长度为长度为len的子串的子串 第5页

6、/共46页第六页，共46页。（11）StrIndex(S,T,pos) 初始条件初始条件: 串串S和和T存在存在,T是非空串是非空串, 1posStrLength(S)操作结果操作结果(ji gu):若串若串S中存在与串中存在与串T相同的子串相同的子串,则返回它在串则返回它在串S中第中第pos个字符之后第一次出现的位置个字符之后第一次出现的位置;否则返回否则返回0 （12）StrReplace(S,T,V)初始条件初始条件: 串串S,T和和V存在存在,且且T是非空串是非空串 操作结果操作结果:用用V替换串替换串S中出现中出现(chxin)的所有与的所有与T相等的不重叠子串相等的不重叠子串 （1

7、3）StrDestroy(S)初始条件初始条件: 串串S存在存在(cnzi) 操作结果操作结果:销毁串销毁串S 第6页/共46页第七页，共46页。4.2 抽象数据类型串的实现抽象数据类型串的实现(shxin)4.2.1 定长顺序定长顺序(shnx)串串定长顺序串是将串设计成一种结构类型定长顺序串是将串设计成一种结构类型,串的存储分配是串的存储分配是在编译在编译(biny)时完成的。时完成的。 串的定长顺序存储表示串的定长顺序存储表示#define MAXLEN 20typedef struct /*串结构定义串结构定义*/ char chMAXLEN; int len; SString; 第7

8、页/共46页第八页，共46页。定长顺序串基本操作的实现定长顺序串基本操作的实现(shxin)算法算法（1）串插入）串插入(ch r)函数函数见见P86例如：例如：S = chater ，T = rac ， 则执行则执行 StrInsert(S, 4, T) 之后之后(zhhu)得到得到 S = character 第8页/共46页第九页，共46页。（2）串删除）串删除(shnch)函数函数StrDelete(s,pos,len) /*在串在串s中删除中删除(shnch)从序号从序号pos起起len个字符个字符*/SString *s; int pos,len;int i;if (pos(s-l

9、en-len) return(0);for (i=pos+len;ilen;i+) s-chi-len=s-chi;s-len=s-len - len;return(1);第9页/共46页第十页，共46页。（3）串复制）串复制(fzh)函数函数StrCopy(s,t) /*将串将串t的值复制到串的值复制到串s中中*/SString *s,t;int i;for (i=0;ichi=t.chi;s-len=t.len; 第10页/共46页第十一页，共46页。（4）判空函数）判空函数(hnsh)StrEmpty(s) /*若串若串s为空为空(即串长为即串长为0),则返回则返回(fnhu)1,否则返

10、回否则返回(fnhu)0*/SString s;if (s.len=0) return(1);else return(0); 第11页/共46页第十二页，共46页。（5）串比较）串比较(bjio)函数函数StrCompare(s,t) /*若串若串s和和t相等相等(xingdng),则返回则返回0,若若st返回返回1,若若st返回返回-1。*/SString s,t;int i;for (i=0;is.len&ilen=0; return(1); 第14页/共46页第十五页，共46页。（8）连接）连接(linji)函数函数StrCat(s,t) /*将串将串t联接在串联接在串s的后面的后面*/

11、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的长度等于的长度等于(dngy)MAXLEN ,串串t不被连接不被连接return(flag); 第15页/共46页第十六页，共46页。（9）求子串函数）求子串函数(hnsh)SubString(sub,s,pos,len) /*将串将串s中序号

12、中序号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); 第16页/共46页第十七页，共46页。（10）定位）定位(dngwi)函数函数StrIndex(s,pos,t) /*求串求串t在串在串s中的位置中的位置(wi zhi)*/SString s,t;int pos;int i,j;if (t.len=0) return(

13、0); i=pos;j=0;while (is.len & j=t.len) return(i-j);else return(0); 第17页/共46页第十八页，共46页。4.2.2 堆串堆串这种存储方法以一组地址连续的存储单元存放这种存储方法以一组地址连续的存储单元存放串的字符序列，但它们的存储空间是在程序执串的字符序列，但它们的存储空间是在程序执行过程中动态分配的。系统将一个地址连续、行过程中动态分配的。系统将一个地址连续、容量很大的存储空间作为字符串的可用空间，容量很大的存储空间作为字符串的可用空间，每当建立一个新串时，系统就从这个空间中分每当建立一个新串时，系统就从这个空间中分配一个大

14、小配一个大小(dxio)和字符串长度相同的空间存和字符串长度相同的空间存储新串的串值。储新串的串值。 第18页/共46页第十九页，共46页。堆串的定义堆串的定义(dngy)为为:typedef structint len； int start； HeapString； 其中其中len域指示串的长度域指示串的长度, start域指示串的起始位置域指示串的起始位置。借助此结构可以在串名和串值之间建立一个对应。借助此结构可以在串名和串值之间建立一个对应关系关系(gun x)，称为串名的存储映像。系统中所有，称为串名的存储映像。系统中所有串名的存储映像构成一个符号表。串名的存储映像构成一个符号表。 第

15、19页/共46页第二十页，共46页。堆串的存储映象堆串的存储映象(yn xin)示例示例a=a program，b=string ，c=process，free=23。ap r o g r a m s tr in gp r o c e s sHeapMAXSIZE free=23符号名符号名lenstarta90b79c716符号表符号表第20页/共46页第二十一页，共46页。用用C语言中的语言中的“堆堆”实现实现(shxin)堆串堆串,其定义为其定义为:typedef struct char * ch； int len； HString；其中其中len域指示串的长度，域指示串的长度，ch域指

16、示串的起始域指示串的起始(q sh)地址。地址。第21页/共46页第二十二页，共46页。堆串的基本操作堆串的基本操作(1) 串赋值函数串赋值函数(hnsh)StrAssign(s，tval) /*将字符将字符(z f)常量常量tval的值赋给串的值赋给串s */HString *s; char *tval;int len，i=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;

17、else s-ch=NULL; s-len=len;return(1);第22页/共46页第二十三页，共46页。(2) 串插入串插入(ch r)函数函数StrInsert(s，pos，t) /*在串在串s中序号为中序号为pos的字符之前的字符之前(zhqin)插入串插入串t */HString *s，t; int pos;int i;char *temp;if (poss-len | 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.l

18、en;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); 第23页/共46页第二十四页，共46页。(3) 串删除串删除(shnch)函数函数StrDelete(s，pos，len) /*在串在串s中删除中删除(shnch)从序号从序号pos起起len个字符个字符 */HString *s;int pos，len;int i; char *temp;if (pos(s-len - len) return(0);temp=(char *)m

19、alloc(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);第24页/共46页第二十五页，共46页。(4) 串复制串复制(fzh)函数函数StrCopy(s，t) /*将串将串t的值复制到串的值复制到串s中中 */HString *s，t;int i;s-ch=(char *)malloc(t.len);if (s-ch=NULL) return(0);for

20、(i=0;ichi=t.chi;s-len=t.len;return(1); 第25页/共46页第二十六页，共46页。(5) 判空函数判空函数(hnsh)StrEmpty(s) /*若串若串s为空为空(即串长为即串长为0)，则返回，则返回(fnhu)1，否则返回，否则返回(fnhu)0 */HString s;if (s.len=0) return(1);else return(0); 第26页/共46页第二十七页，共46页。(6) 串比较串比较(bjio)函数函数StrCompare(s，t) /*若串若串s和和t相等相等(xingdng)，则返回，则返回0，若，若st返回返回1，若，若st

21、返回返回-1 */HString s，t;int i;for (i=0;is.len&ich!=NULL) free(s-ch); s-ch=NULL; s-len=0; return(1); 第29页/共46页第三十页，共46页。(9) 连接连接(linji)函数函数StrCat(s，t) /*将串将串t联接联接(lin ji)在串在串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

22、;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); 第30页/共46页第三十一页，共46页。(10) 求子串函数求子串函数(hnsh)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-

23、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); 第31页/共46页第三十二页，共46页。(11) 定位定位(dngwi)函数函数StrIndex(s，pos，t) /*求串求串t在串在串s中的位置中的位置(wi zhi) */HString s，t; int pos;int i，j;if (s.len=0 | t.len=0) return(0);i=pos;j=0;wh

24、ile (is.len & j=t.len) return(i-j);else return(0); 第32页/共46页第三十三页，共46页。4.2.3 块链串块链串#define BLOCK_SIZE typedef struct Blockchar chBLOCK_SIZE;struct Block *next; Block; typedef struct Block *head; Block *tail;int length; BLString; 第33页/共46页第三十四页，共46页。4.3 串的应用串的应用(yngyng)举例举例:文本编辑文本编辑文本编辑程序用于源程序的输入和修改，

25、公文书信文本编辑程序用于源程序的输入和修改，公文书信、报刊和书籍、报刊和书籍(shj)的编辑排版等。常用的文本编的编辑排版等。常用的文本编辑程序有辑程序有Edit，WPS，Word等等 。第34页/共46页第三十五页，共46页。例如例如(lr)：S = chater，T = rac， 则执行则执行 StrInsert(S, 4, T) 之后得到之后得到 S = character第35页/共46页第三十六页，共46页。例如例如(lr)：S = chater，T = rac， 则执行则执行 StrInsert(S, 4, T) 之后得之后得到到 S = characte第36页/共46页第三十七

26、页，共46页。例如：例如：S = chater，T = rac， 则执行则执行 StrInsert(S, 4, T) 之后之后(zhhu)得到得到 S = chara 第37页/共46页第三十八页，共46页。例如：例如：S = chater，T = rac， 则执行则执行(zhxng) StrCat(S, T) 之后之后得到得到 S = chaterrac第38页/共46页第三十九页，共46页。例如：例如：S = chater，T = rac， 则执行则执行(zhxng) StrCat(S, T) 之后之后得到得到 S = chaterra第39页/共46页第四十页，共46页。例如例如(lr)

27、：S = chater，T = rac， 则执行则执行 StrCat(S, T) 之后得到之后得到 S = chater第40页/共46页第四十一页，共46页。例如例如(lr)：S = chater，T = rac 则执行则执行 StrReplace(S,4,T) 之后得到之后得到 S = charac第41页/共46页第四十二页，共46页。例如例如(lr)：S = chaterscha，T = rac 则执行则执行 StrReplace(S,4,T) 之后得到之后得到 S = characcha序号12345678109chaterscahrac置换后 第42页/共46页第四十三页，共46页。例如：例如：S = chatercha，T = racr 则执行则执行 StrReplace(S,4,T) 之后之后(zhhu)得到得到 S = characcha序号12345678109chatercha置换后 raac第43页/共46页第四十四页，共46页。第44页/共46页第四十五页，共46页。K个 ii +1i+k-149212830426251第45页/共46页第四十六页，共46页。