数据结构第08讲-串的定义、表示和实现c

1、期中考试Class 1 4月16日 10,11,12课时Class 3 4月17日 6,7,8课时期中考试内容第一章 绪论第二章 线性表第三章 栈和队列第四章 串第五章 数组和广义表第六章 树和二叉树带星号的不考第4章 串4.1 串类型的定义4.2 串的表示和实现4.3 串的模式匹配算法4.4 串操作应用举例4.1 串类型的定义1.串的概念 由零个或多个字符组成的有限序列，记作 s = a1a2an 其中：s 为串的名字；用成对的单引号括起来的字符序列为串的值，但两边的单引号不算串值，不包含在串中；ai(1in)可以是字母、数字或其它字符；n为串中字符的个数，称为串的长度。空串：不含任何字符的

2、串。长度n=0，记为 s= ； 空格串：含有空格的串，长度n0， 记为s= 。子串、主串: 串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时，该子串的首字符对应的主串中的序号称为子串在主串中的位置。 例：A 和 B 分别为 A=This is a string B=is 空串是任意串的子串，任意串是其自身的子串。串的比较大小： aab， abcabd两串相等：当且仅当这两个串的值相等（长度相等,对应位置上的字符也相等）时。2.串的抽象类型定义ADT String 数据对象：D ai |aiCharacterSet, i=1,2,n, n0

3、数据关系：R1 | ai-1, ai D, i=2,n 基本操作：ADT String串的常用操作(1) StrAssign (&T, chars) 条件：chars是字符串常量；结果：把chars赋为T的值(2) StrCopy (&T, S) 条件：串S存在； 结果：将串S的值复制到串T(3) DestroyString (&S) 条件：串S存在； 结果：串S被销毁(4) StrEmpty (S) 条件：串S存在； 结果：若S为空串，返回真，否则假(5) pare (S, T) 条件：串S和T存在； 结果：若S T，则返回值0；若S = T，则返回值=0 若S T，则返回值 0) n =

4、StrLength(S); m = StrLength(T); i = p; while ( i = n-m+1) SubString (&sub, S, i, m); if ( pare(sub,T) != 0) +i ; else return i ; / while / if return 0; / S中不存在与T相等的子串 / Index;算法4.1第4章 串4.1 串类型的定义4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 串的块链存储表示4.3 串的模式匹配算法4.4 串操作应用举例4.2 串的表示和实现 串是一种特殊的线性表，特殊在于

5、每个结点仅由一个字符组成，因此，存储串的方法也是存储线性表的一般方法，则串的存储表示有三种形式：定长顺序存储表示、堆分配存储表示、串的块链存储表示。4.2.1 定长顺序存储表示 用一组地址连续的存储单元存储串值的字符序列。使用定长字符数组来定义，数组的上界预先给出，故也称静态存储分配。 定义说明： #define MAXSTRLEN 255 / 用户可在255以内定义最大串长 typedef unsigned char SStringMAXSTRLEN+1; / 0号单元存放串的长度 串的实际长度可在预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为“截断” 。1.串的联接需考虑

6、三种情况： (1) 联接后的串长度未超过预定义长度； (2) 联接后的串长度超过预定义长度；又分： a：第一个串长度小于预定义长度； b：第一个串长度等于预定义长度。Status Concat(SString S1, SString S2, SString &T) / 用T返回由S1和S2联接而成的新串。若未截断返回真，否则假 if (S10+S20 = MAXSTRLEN) / 未截断 T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20; uncut = TRUE; else if (S10 MAXSTRSIZE) / 截断 T1

7、.S10 = S11.S10; TS10+1.MAXSTRLEN = S21.MAXSTRLEN S10; T0 = MAXSTRLEN; uncut = FALSE; else / 截断(仅取S1) T0.MAXSTRLEN = S10.MAXSTRLEN; uncut = FALSE; return uncut; / Concat2.求子串 思路：求子串的过程即为复制字符序列的过程，将串 S 中从第 i 个字符开始长度为 L的字符序列复制到新串中。显然，此操作不存在截断的问题，但与顺序表类似，会出现参数错误的情形： (1)子串的位置非法； (2)子串的位置加上子串长已经超出原串长。Stat

8、us SubString (SString &Sub, SString S, int pos, int len) /用Sub返回S的第pos个字符起长度为len的子串。/ 1=pos=StrLength(S)且0=len= StrLength(S)-pos+1 if (posS0 | lenS0-pos+1) return ERROR; Sub1.len = Spos.pos+len-1; Sub0=len; return OK; / SubString4.2.2 堆分配存储表示 由于多数情况下串是以整体形式参与操作，而在实际应用中，各种串变量的长度的不同，并且操作中串值长度的也会发生变化，故

9、为串变量设定固定大小空间不尽合理。 串的堆分配存储表示特点： 仍以一组地址连续的存储单元存放串值字符序列，但串变量的存储空间是在程序执行过程中动态分配而得，程序中出现的所有串变量可用的存储空间是一个称之为“堆”的共享空间。定义说明：typedef struct char *ch; / 若是非空串，则按串长分 / 配存储区，否则ch为NULL int length; / 串长度 HString;称之为“堆”的共享空间 通常，C语言中提供的串类型就是以该存储方式实现。系统利用函数 malloc( )和 free( )进行串值空间的动态管理，为每个新产生的串分配一个存储区，称串值共享的存储空间为“堆

10、”。 C 语言中的串以 0 为结束符，串长是一个隐含值。Status StrInsert ( HString &S, int pos, HString T ) /在串S的第pos个字符之前（包括尾部）插入串T if ( posS.length+1 ) return ERROR; if (T.length) /T非空，需重新分配空间，以便插入T S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char) if (!S.ch) exit(OVERFLOW); for (i=S.length-1;i=pos-1;-i) /为插入T腾出pos后的

11、位置 S.chi+T.length = S.chi; /从pos起全部字符均后移 S.chpos-1.pos+T.length-2 = T.ch0.T.length-1; /插入T S.length + = T.length; /刷新S串长度 return OK; /StrInsert1.串插入算法4.4Status StrAssign(HString &T, char *chars) if (T.ch) free(T.ch); /释放T原有空间 for (i=0, c=chars; *c; +i, +c); /求串长 if (!i) T.ch = NULL; T.length = 0; el

12、seif (!(T.ch = (char*)malloc(i*sizeof(char) exit(OVERFLOW);T.ch0.i-1 = chars0.i-1;T.length =i; Return OK;/StrAssign指针变量C也可以自增！意即每次后移一个数据单元。2. 串赋值直到终值为“假”停止，串尾特征是0NULL=0Status Concat(HString &T,HString S1,HString S2) /用T返回S1和S2联接而成的新串 if (T.ch) free(T.ch); / 释放T原来占据的空间 T.ch =(char*)malloc(S1.length+S

13、2.length)*sizeof(char); /为T分配空间 if (!T.ch) return ERROR; / 连接两个串的内容 T.length = S1.length + S2.length; T.ch 0.S1.length-1=S1.ch0.S1.length-1; T.ch S1.length.T.length -1=S2.ch0.S2.length-1; return OK; / Concat3.串联接status SubStr(HString &Sub,HString S,int pos,int len) /用Sub返回串S中第pos个字符起长度为len的子串 if(pos

14、S.length | lenS.length-pos+1) return ERROR /判断i和len的合理性 if Sub.ch free(Sub.ch) /释放旧空间 if (!len) Sub.ch = null; Sub.length = 0; /空子串 else /完整子串 Sub.ch = (char*) malloc( len*sizeof(char) ); if (!Sub.ch) exit(OVERFLOW); Sub.ch 0.len-1 = S.ch pos-1.pos+len -2 ; Sub.length = len; return OK; / SubStr4.求子串

15、20140318 Class34.2.3 串的块链存储表示 串的链式存储结构称为链串。其存储形式与一般的链表类似，每个结点包含字符域和指针域。 一个存储结点可以存储 1个或多个字符，通常将链串中每个结点所存储的字符个数称为结点大小。 为了便于进行诸如串的联接等操作，链表中还附设有尾指针。由于串的长度不一定是结点大小的整数倍，因此还需要一个指示串长的域。称如此定义的存储结构为串的块链存储结构。法1存储密度为 ；法2存储密度为 ；链式存储特点 ：用链表存储串值，易插入和删除。单字符结点的串的链式存储结构：结点大小取1多字符结点的串的链式存储结构：结点大小取 n( 如n=4 )1/29/15=3/5

16、 A B C I NULLheadheadA B C D E F G H I # # # NULL存储密度串值所占的存储位/实际分配的存储位定义说明：#define CHUNKSIZE 80 / 可由用户定义的块大小typedef struct Chunk / 结点结构 char chCHUNKSIZE; struct Chunk *next; Chunk;typedef struct / 串的链表结构 Chunk *head, *tail; / 串的头和尾指针 int curlen; / 串的当前长度 LString;性能分析： 在以链表存储串值时，结点大小的选择将直接影响串的处理效率。 显

17、然，存储密度小（如结点的大小为1），操作方便（结点的大小为1时），然而存储占用量大。一般以块链存储时实现串的操作比较麻烦。例：在串中插入一个子串时，可能需要分割结点；联接两个串时，若第一个串的最后一个结点没有填满，还需要添加其他字符；但在应用程序中，可将串的链式存储结构和串的定长顺序存储结构结合使用。例：在正文编辑系统中，整个“正文”可以看成是一个串，每一行是一个子串，构成一个结点。即同一个行的串用定长结构（80个字符），而行和行之间用指针相联接。q例：若x和y是两个单链表存储的串，编写一个函数找出x中第一个不在y中出现的字符。cf abecf habyxpq算法基本思想： 从头到尾扫描x，对于x中的每一个结点P，判定是否在y中，若在，则继续扫描x，否则给出该结点P的数据域并返回。ppqqqqq定义说明：typedef struct CNode / 结点结构 char data; struct CNode *next; Chunk,*LinkString;子函数编写int found(char d, LinkString h) / 若h的链表中包含有data域为x的结点则返回1，/ 否则返回 0 。 while ( h !=NULL & h-data != d) h =