数据结构-串.ppt

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

1、Chapter4String教学内容1、串的定义2、串的存储表示3、串的模式匹配算法串的值串的长度串的名4.1串的定义串（字符串）：是由0个或多个字符组成的有限序列。记为：s=“a1a2a3…ai…an”(n≥0)。字母、数字或其他字符必须有！作用：避免字符串与变量名或数的常量混淆。基本概念例：x=“123”x=123test=“test”作用：避免字符串与变量名或数的常量混淆。空串：不含任何字符的串，长度=0，用符号表示。空格串：仅由一个或多个空格组成的串。子串：由串中任意个连续的字符组成的子序列。主串：包含子串的串。位置：字符在序列中的序号。子串在

2、主串中的位置：子串的首字符在主串中的位置。例：S=“JINAN”S1=“”S2=“NA”S=“JINAN”—S的子串。S4=“JAN”——非S的子串（非串S中的连续字符所组成）。在S中的位置：2在S中的位置：0串相等的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。例：S=“JINAN”S1=“JINAN”SS1空串是任意串的子串，任意串是其自身的子串。串的逻辑结构：和线性表极为相似。串的基本操作：和线性表有很大差别。区别：串的数据对象约定是字符集。线性表的基本操作：以“单个元素”为操作对象；串的基本操作：以“串的整体”作为操作对象。例：在串中

3、查找某个子串；在串的某个位置上插入一个子串；删除一个子串等。串的抽象数据类型的定义ADTString{数据对象：D＝{ai

4、ai∈CharacterSet,i=1,2,...,n,n≥0}数据关系：R1＝{

5、ai-1,ai∈D,i=2,...,n}基本操作：StrAssign(&T,chars)初始条件：chars是字符串常量。操作结果：构造一个串值为chars的串。StrCopy(&T,S)初始条件：串S存在。操作结果：由串S复制得串T。DestroyString(&S)初始条件：串S存在。操作结果：串S被销毁。StrEmpty(S)初始

6、条件：串S存在。操作结果：若S为空串，则返回TRUE，否则返回FALSE。StrCompare(S,T)初始条件：串S和T存在。操作结果：若S>T，则返回值>0；若S=T，则返回值=0；若S0StrLength(S)初始条件：串S存在。操作结果：返回S的元素个数，称为串的长度。Concat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2连接而成的新串。SubStr

7、ing(&Sub,S,pos,len)初始条件：串S存在，0≤pos≤StrLength(S)-1且0≤len≤StrLength(S)–pos。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。Index(S,T,pos)初始条件：串S和T存在，T是非空串，0≤pos≤StrLength(S)-1。操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。Replace(&S,T,V)初始条件：串S、T和V存在，T是非空串。操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。}A

8、DTString假设S=“abcacabcaca”，T=“abca”，V=“ab”，则置换之后的S=“abcabca”，而不是“abbcaca”。例如：SubString(sub,commander,3,3)子串为“串”中的一个字符子序列求得sub=man;SubString(sub,commander,0,9)SubString(sub,commander,8,1)求得sub=r求得sub=commanderSubString(sub,commander,3,7)sub=?SubString(sub,beijing,6,2)

9、=?sub=?SubString(student,5,0)=起始位置和子串长度之间存在约束关系长度为0的子串为“合法”串假设S=abcaabcaaabc,T=bcaIndex(S,T,0)=1;Index(S,T,3)=5;Index(S,T,8)=0;“子串在主串中的位置”意指子串中的第一个字符在主串中的位序。因为串是特殊的线性表，故其存储结构与线性表的存储结构类似，只不过组成串的结点是单个字符。4.2.1定长顺序存储表示定长顺序存储表示，也称为静态存储分配的顺序串。即用一组地址连续的存储单元依次存放串中的字符序列。4.2串的存储表示#de

10、fineMAXLEN255classString{p