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

《最新数据结构--第四章--课件课件ppt.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构--第四章--课件第四章串4.1串的抽象数据类型的定义4.2串的表示和实现SubString(&Sub,S,pos,len)Index(S,T,pos)Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)ClearString(&S)}ADTStringStrEmpty(S)初始条件：串S存在。操作结果：若S为空串，则返回true，否则返回false。表示空串，空串的长度为零。StrCompare(S,T)初始条件：串S和T存在。操作结果：若ST，则返回值0；若ST，则返回值0

2、；若ST，则返回值0。例如：StrCompare(data,state)<0StrCompare(cat,case)>0Concat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。例如：Concat(T,man,kind)求得T=mankindSubString(&Sub,S,pos,len)初始条件：操作结果：用Sub返回串S的第pos个字符起长度为len的子串。串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。例如：SubStr

3、ing(sub,commander,4,3)子串为“串”中的一个字符子序列求得sub=man;SubString(sub,commander,1,9)SubString(sub,commander,9,1)求得sub=r求得sub=commanderSubString(sub,commander,4,7)sub=?SubString(sub,beijing,7,2)=?sub=?SubString(student,5,0)=起始位置和子串长度之间存在约束关系长度为0的子串为“合法”串Index(S,T,pos)初始条件

4、：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。假设S=abcaabcaaabc,T=bcaIndex(S,T,1)=2;Index(S,T,3)=6;Index(S,T,8)=0;“子串在主串中的位置”意指子串中的第一个字符在主串中的位序。Replace(&S,T,V)初始条件：串S,T和V均已存在，且T是非空串。操作结果：用V替换主串S中出现的所有与（模式串）T相等的不重叠的子串。例如：假设S=abcaab

5、caaabca,T=bca若V=x,则经置换后得到S=axaxaax若V=bc,则经置换后得到S=abcabcaabcbcabcabcaStrInsert(&S,pos,T)初始条件：串S和T存在，1≤pos≤StrLength(S)＋1。操作结果：在串S的第pos个字符之前插入串T。例如：S=chater，T=rac，则执行StrInsert(S,4,T)之后得到S=characterStrDelete(&S,pos,len)初始条件：串S存在1≤pos≤StrLength(S)-len+1。操作结果：从串S中删除第pos

6、个字符起长度为len的子串。对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。gets(str)输入一个串；puts(str)输出一个串；strcat(str1,str2)串联接函数；strcpy(str1,str2)串复制函数；strcmp(str1,str2)串比较函数；strlen(str)求串长函数；例如：C语言函数库中提供下列串处理函数：串赋值StrAssign、串复制Strcopy、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等六种操作构

7、成串类型的最小操作子集。在上述抽象数据类型定义的13种操作中，即：这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串销毁DestroyString外）可在这个最小操作子集上实现。串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。4.2串

8、的表示和实现一、串的定长顺序存储表示二、串的堆分配存