数据结构第4章串类型的定义
课前导学4.1 串类型的定义4.2 串的表示和实现【学习目标】1.理解串类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。2.理解串类型的各种存储表示方法。【重点和难点】了解串类型定义中各基本操作的定义以及串的实现方法，并学会利用这些基本操作来实现串的其它操作。【知识点】串的类型定义、串的存储表示【课前思考】从从数数据据结结构构的的观观点点来来说说，串串是是一一种种特特殊殊的线性表的线性表;但就数据类型而言，串不是线性表。但就数据类型而言，串不是线性表。区区别别1 1、它它的的数数据据元元素素都都是是字字符符，它它的的存存储储结构和线性表有很大不同结构和线性表有很大不同 ;区区别别2 2、串串的的基基本本操操作作通通常常以以 串串的的整整体体 作作为为操操作作对对象象，而而不不像像线线性性表表是是以以 数数据据元元素素 作作为操作对象。为操作对象。“串就是线性表串就是线性表”的结论是否正确？的结论是否正确？二者之间有何区别二者之间有何区别?4.1 串类型的定义 1.基本概念串（string）：由0个或多个字符组成的有限序列，也称字符串。记为：s=a1a2a3an (n0)式 中 s是 串 的 名，a1a2a3an是 串 的 值，ai（1in）可以是字母、数字或其它字符。串长度：串中字符的数目n。空串：不含任何字符的串，串长度=0空格串：仅由一个或多个空格组成的串子串：由串中任意个连续的字符组成的子序列主串：包含子串的串。串串相相等等的的条条件件：当两个串的长度相等且各个对应位置的字符都相等时才相等。注意：（1）串值必须用一对单引号括起来 （2）串值大小是按词典次序进行比较的 StrCompare(data,Stru)0显然，只有在两个串的长度相等且每个字符一一对等的情况下称两个串相等。2.串的抽象数据类型的定义串的抽象数据类型的定义ADT String 数据对象：D ai|aiCharacterSet,i=1,2,.,n,n0 数据关系：R1|ai-1,ai D,i=2,.,n 基本操作：StrAssign(&T,chars)初始条件：chars是字符串常量。操作结果：把chars赋为T的值。StrCopy(&T,S)初始条件：串S存在。操作结果：由串S复制得串T。DestroyString(&S)初始条件：串S存在。操作结果：串S被销毁。StrEmpty(S)初始条件：串S存在。操作结果：若S为空串，则返回TRUE，否则返回FALSE。StrCompare(S,T)初始条件：串S和T存在。操作结果：若ST，则返回值0；若S=T，则返回值=0；若ST，则返回值0。StrLength(S)初始条件：串S存在。操作结果：返回S的元素个数，称为串的长度。Concat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。SubString(&Sub,S,pos,len)初始条件：串S存在，1posStrLength(S)且 0lenStrLength(S)-pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。Index(S,T,pos)初始条件：串S和T存在，T是非空串，1posStrLength(S)。操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。Replace(&S,T,V)初始条件：串S,T和V存在，T是非空串。操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。StrInsert(&S,pos,T)初始条件：串S和T存在，1posStrLength(S)1。操作结果：在串S的第pos个字符之前插入串T。StrDelete(&S,pos,len)初始条件：串S存在，1posStrLength(S)-len+1。操作结果：从串S中删除第pos个字符起长度为len的子串。ClearString(&S)初始条件：串S存在。操作结果：将S清为空串。ADT String 在以上操作中，串赋值StrAssign、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等五种操作构成串类型的最小操作子集，即这些操作不可能利用其他串操作来实现。思考：串的基本操作和线性表一样，无非也就是查找、插入和删除等，那么它们能否用线性表的操作来替代呢？串的基本操作和线性表有很大的区别，同样是查找、插入和删除，但对线性表而言操作对象是“数据元素”，而对串言，是以整个串作为操作对象。由此可见，串类型不能和线性表类型混为一谈。42 串的表示和实现 1.定长顺序存储 用一组地址连续的存储单元存储串值的字符序列，类似于线性表的顺序存储结构。可以用定长数组来描述：#define MAXSTRLEN 255/用户可在255以内定义最大串长 typedef char SStringMaxstrlen+1;/0号单元存放串的长度 3 b o y 串长0255SString类型图示SString有效字符1.定长顺序存储时串的操作(1)串串联结Contcat（&T,S1,S2）算法描述：算法描述：Status Concat(SString&T,SString S1,SString S2)/用用T返回由返回由S1和和S2联接而成的新串。若未截断，接而成的新串。若未截断，则返回返回TRUE，否否则FALSE。if(S10+S20=Maxstrlen)/未截断未截断T1.S10=S11.S10;T S10+1.S10+S20 =S21.S20;T0=S10+S20;uncut=TRUE;else if(S10 Maxstrsize)/截断 T1.S10=S11.S10;TS10+1.Maxstrlen=S21.MaxstrlenS10;T0=Maxstrlen;uncut=FALSE;else /截断(仅取S1)T0.Maxstrlen=S10.Maxstrlen;/T0=S10=Maxstrlen uncut=FALSE;return uncut;/Concat（2）求子串SubString(&Sub,S,pos,len)Status SubString(SString&Sub,SString S,int pos,int len)/用Sub返回串S的第pos个字符起长度为len的子串。/其中1pos StrLength(S)且 0lenStrLength(S)-pos+1 if(posS0|lenS0-pos+1)return ERROR;Sub1len=Spospos+len-1；Sub0=len；return OK;/SubString例：例：SubString(Sub,“commander”,4,3)得到的结果是：得到的结果是：Sub=man。2.堆分配存储 堆:一块自由存储区，,C语言用malloc()分配，C+用new 分配。串的堆存储：以一组地址连续的存储单元存储串值 的字符序列，在程序执行过程中由动态分配而得到。串的堆分配存储表示：typedef struct char*ch;/若非空串则按串长分配存储区,否则为NULL int length;/串长度 HString;chlengthHStringchar注：1、C语言中提供的串类型就是以这种存储方式实现的2、系统利用函数malloc()和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。C+中用new 和delete操作符来进行堆空间的分配和回收.3、C语言中的串以一个空字符0为结束符，串长是一个隐含值。3b o yT“boy”的堆存储结构null0空串结构3.串的块链存储表示 串值也可用链表来存储，和线性表的链接存储类似，不同的是一个结点中存放的不一定是一个字符，可以是一个子串，当串长不是结点大小的整数倍时，最后一个结点用其他字符补上（如：#）。例如:在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即:同一行的串用定长结构(80个字符),行和行之间用指针相联接。块链结构块链结构：为了便于进行串的操作，当以链表存：为了便于进行串的操作，当以链表存储串值时，除头指针外还可以储串值时，除头指针外还可以附设一个尾指针附设一个尾指针指示链指示链表中的最后一个结点，表中的最后一个结点，并给出当前串的长度并给出当前串的长度。#define CHUNKSIZE 4/#define CHUNKSIZE 4/可由用户定义的块大小可由用户定义的块大小 typedeftypedef structstruct Chunk /Chunk /结点结构结点结构 char char chCHUNKSIZEchCHUNKSIZE;structstruct Chunk*next;Chunk*next;Chunk;Chunk;ch0 ch1 ch2 h3 nextChunkChunktypedef struct /串的链表结构 Chunk*head,*tail;/串的头和尾指针 int curlen;/串的当前长度 LString；Chunkhead curlen tailChunkLStringA B C D 9E#F G H I#NULL“ABCDEFGHI”可能的一种存储方式S.headS.crulenS.tailT h i sas tr i ngi s本章小结n串的概念（定义）n串的存储（实现）n串的操作
