数据结构 第4 章 字符串

《数据结构 第4 章 字符串》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、字符串1、串的概念；2、串的存储结构；3、串的运算。教学内容x的值为整数123。x的值为字符串123。串的值串的长度串的名4.1串类型的定义串（也称字符串）：是由0个或多个字符组成的有限序列。通常记为：s=“a1a2a3…ai…an”(n≥0)。字母、数字或其他字符必须有！不属于串！作用：避免与变量名或数的常量混淆。例：x=“123”x=123test=“test”基本概念空串：不含任何字符的串，串长度=0，用符号表示。空格串：仅由一个或多个空格组成的串。子串：由串中任意个连续的字符组成的子序列。例：S=“JINAN”S1=“

2、”、S2=“NA”、S=“JINAN”主串：包含子串的串。位置：字符在序列中的序号。子串在主串中的位置是子串的首字符在主串中的位置。——子串。S4=“JAN”——非子串（非串S中的连续字符所组成）。在S中的位置：3在S中的位置：1串相等的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。例：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赋为T的值。StrCopy(&T,S)初始条件：串S存在。操作结果：由串S复制

6、得串T。DestroyString(&S)初始条件：串S存在。操作结果：串S被销毁。StrEmpty(S)初始条件：串S存在。操作结果：若S为空串，则返回TRUE，否则返回FALSE。StrCompare(S,T)初始条件：串S和T存在。操作结果：若S>T，则返回值>0；若S=T，则返回值=0；若S0StrLength(S)初始条件：串S存在。操作结果：返回S的元

7、素个数，称为串的长度。Concat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。SubString(&Sub,S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)–pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。Index(S,T,pos)初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第

8、一次出现的位置；否则函数值为0。Replace(&S,T,V)初始条件：串S、T和V存在，T是非空串。操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。假设S=“abcacabcaca”，T=“abca”V=“ab”，则置换之后的S=“abcabca”，而不是“abbca”。StrInsert(&S,pos,T)初始条件：串S和T存在，1≤pos≤StrLength(S)＋1。操作结果：在串S的第pos个字符之前插入串T。StrDelete(&S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)

9、-len+1。操作结果：从串S中删除第pos个字符起长度为len的子串。ClearString(&S)初始条件：串S存在。操作结果：将S清为空串。}ADTString在以上操作中，串赋值StrAssign、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等五种操作构成串类型的最小操作子集，即这些操作不可能利用其他串操作来实现。除串清除ClearString和串销毁DestroyString以外的其他串操作均可在最小操作子集上实现。例如，可利用判等、求串长和求子串等操作实现定位函

10、数Index(S,T,pos)：在主串S中取从第i（i的初值为pos）个字符起、长度和串T相等的子串同串T比较，若相等，则求得函数值为i，否则i值增1，直至串S中从第i个字符起直到串尾的子串长度小于串T的长度为止。intIndex(StringS,StringT