数据结构 第4章 串

《数据结构 第4章 串》由会员分享，可在线阅读，更多相关《数据结构 第4章 串（35页珍藏版）》请在装配图网上搜索。

1、23.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.21ADT String 数据对象数据对象：D=ai|aiCharacterSet,i=1,2,n,n0 数据关系数据关系：R1=|ai-1,aiD,i=2,3,n 基本操作：基本操作：ADT String23.2.2123.2.21基本操作：StrAssign(&T,chars)StrCopy(&T,S)StrEmpty(S)StrCompare(S,T)StrLength(S)ClearString(&S)Concat(&T,S1,S2)SubString

2、(&Sub,S,pos,len)Index(S,T,pos)Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)DestroyString(&S)23.2.2123.2.21uStrAssign(&T,chars)初时条件：初时条件：chars是字符串常量。是字符串常量。操作结果：把操作结果：把chars赋为赋为T的值。的值。uStrCopy(&T,S)初时条件：串初时条件：串S存在存在操作结果：由串操作结果：由串S复制得串复制得串T。uStrEmpty(S)初时条件：串初时条件：串S存在。存在。操作结果：若操作结果：若S为空串，则返回

3、为空串，则返回TRUE，否，否则返回则返回FALSE。23.2.2123.2.21uStrCompare(S,T)初时条件：串初时条件：串S和和T存在。存在。操作结果：若操作结果：若ST,则返回则返回0 若若S=T,则返回则返回=0 若若ST,则返回则返回0uStrLength(S)初时条件：串初时条件：串S存在存在操作结果：返回操作结果：返回S的元素个数，称为串的长的元素个数，称为串的长度。度。23.2.2123.2.21uClearString(&S)初时条件：串初时条件：串S存在。存在。操作结果：将操作结果：将S清为空串。清为空串。uConcat(&T,S1,S2)初时条件：串初时条件：

4、串S1和和S2存在。存在。操作结果：用操作结果：用T返回由返回由S1和和S2联接而成的联接而成的新串。新串。23.2.2123.2.21uSubString(&Sub,S,pos,len)初时条件：串初时条件：串S存在，存在，1posStrLength(S)且且 1lenStrLength(S)-pos1。操作结果：用操作结果：用Sub返回串返回串S的第的第pos个字符起个字符起 长度为长度为len的子串。的子串。uIndex(S,T,pos)初时条件：串初时条件：串S和和T存在，存在，T是非空串，是非空串，1posStrLength(S)操作结果：若主串操作结果：若主串S中存在与串中存在与串

5、T相同的子相同的子 串，则返回它在主串串，则返回它在主串S中的第中的第pos 个字符之后第一次出现的位置，个字符之后第一次出现的位置，否则返回否则返回0。23.2.2123.2.21uReplace(&S,T,V)初时条件：串初时条件：串S，T和和V存在，存在，T是非空串。是非空串。操作结果：用操作结果：用V替换主串替换主串S中出现的所有与中出现的所有与 T相等的不重叠子串。相等的不重叠子串。uStrInsert(&S,pos,T)初时条件：串初时条件：串S和和T存在，存在，1posStrLength(S)1。操作结果：操作结果：在串在串S的第的第pos个字符之前插入串个字符之前插入串T.23

6、.2.2123.2.21uStrDelete(&S,pos,len)初时条件：串初时条件：串S存在存在,1posStrLength(S)-len1。操作结果：从串操作结果：从串S中删除第中删除第pos个字符起长个字符起长 度为度为len的子串。的子串。uDestroyString(&S)初时条件：串初时条件：串S存在存在.操作结果：串操作结果：串S被销毁。被销毁。23.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.

7、2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.2123.2.21 串的链式存储结构和线性表的串的链式存串的链式存储结构和线性表的串的链式存储结构类似，采用单链表来存储串，结点的储结构类似，采用单链表来存储串，结点的构成是：构成是：udatadata域：存放字符，域：存放字符，datadata域可存放的字符域可

8、存放的字符个数称为结点的大小；个数称为结点的大小；unextnext域：存放指向下一结点的指针。域：存放指向下一结点的指针。若每个结点仅存放一个字符，则结点的指若每个结点仅存放一个字符，则结点的指针域就非常多，造成系统空间浪费，为节省针域就非常多，造成系统空间浪费，为节省存储空间，考虑串结构的特殊性，使每个结存储空间，考虑串结构的特殊性，使每个结点存放若干个字符，这种结构称为块链结构。点存放若干个字符，这种结构称为块链结构。23.2.2123.2.2123.2.2123.2.21 在这种存储结构下，结点的分配总是在这种存储结构下，结点的分配总是完整的结点为单位，因此，为使一个串完整的结点为单位，因此，为使一个串能存放在整数个结点中，在串的末尾填能存放在整数个结点中，在串的末尾填上不属于串值的特殊字符，以表示串的上不属于串值的特殊字符，以表示串的终结。终结。当一个块当一个块(结点结点)内存放多个字符时，内存放多个字符时，往往会使操作过程变得较为复杂，如在往往会使操作过程变得较为复杂，如在串中插入或删除字符操作时通常需要在串中插入或删除字符操作时通常需要在块间移动字符。块间移动字符。a b c e p c g#head串的块链式存储结构示意图串的块链式存储结构示意图