《数据结构第04章 串》由会员分享，可在线阅读，更多相关《数据结构第04章 串（18页珍藏版）》请在金锄头文库上搜索。
1、第四章 串教学目的与要求本章目的是介绍串的逻辑结构、存储结构及其串上的基本运算。重点和难点本章重点是掌握串上实现的模式匹配算法，其也是本章难点。教学内容第一节串的基本概念4.1.1基本概念串：是零个或多个字符组成的有限序列。串中所包含的字符个数称为 串的长度。空串：长度为0的串称为空串，它不包含任何字符。空白串：仅由一个或多个空格组成的串称为空白串。应注意空串和空 白串的区别。子串、主串：串中任意个连续字符组成的子序列称为该串的子串，包 含子串的串相应地称为主串。空串是任意串的子串，任意串是其自身 的子串。子串在主串中的位置：通常，将子串在主串中首次出现时子串首字符 对应的主串中的序号定义为子
2、串在主串中的位置。2. 串的基本运算(1) 求串的长度(Length)(2) 串复制(Copy):(3) 串联接(Concat)（4）串比较（Compare）（5）字符定位（Index）除上述基本运算外，串运算还有求子串、子串的定位、子串的置换等 操作。这些操作，一般可由这些基本操作实现。第二节串的存储结构4.2.1串的顺序存储1. 静态存储分配的顺序串顺序串最简单的描述形式是直接使用定长的字符数组来定义。其定义 形式为# define maxstrsize 256typedef char Seqstringmaxstrsise;利用类型描述符Seqstrsring可定义数组变量存储串，利用特
3、定字符 表示串的结束（C语言用转义字符0）。例如Seqstrstring s; 变量s可存储长度不超过255个字符的字符串，以0作为串的结 束。顺序串的类型定义也可以象线性表的顺序存储一样，在定义字符数组 的基础上，引入描述长度的成员。其定义形式为# define maxstrsize 256typedef struct char chmaxstrsise;int length;Sqestring;动态存储分配的顺序串（堆）上述两种方式的共同缺点是主串值的存储空间是静态分配的是定长 的。动态分配则克服了上述缺点，其余定义形式为typedef struct char *ch;int length
4、;Hstring;成员ch为指针型，若串非空，按实际需要动态分配存储空间，ch指 向其起始地址，否则ch为FULL。成员length存储串长度。（3）串的链式存储用单链表的方式来存储串值，就是串的链式存储，简称为链串。每 个结点可以存储一个字符（数据域data为字符型），也可以存储多个 字符（数据域data定义为字符型数组）。3. 基本运算的实现串匹配算法很多，这里只讨论的是一种简单的朴素的串匹配算 法。在串匹配中，一般将主串称为日标（串），子串称为模式（串）。 设T为日标串，设P为模式串。串匹配实际上是对合法的位置0Wi Wn-m，依次将日标串中的子串Ti.i+m-1和模式串P0.m-1进行
5、 比较，若相等，则称从位置i开始的匹配成功，否则，则称从位置i 开始的匹配失败。位置i称为位移，匹配成功时，位置i称为有效位 移，匹配失败时，位置i称为无效位移。(1)顺序串上的子串的定位运算(模式匹配)算法思想：通过一个循环依次检查n-m+1个合法的位移i(0WiWn-m)是否为 有效位移。i初值为0，终值为n-m，其确定了日标串中子串的起始 位置，每趟匹配结束后通过i值加1(i+)使i指向下一合法位移。语言算法：Int naivestrmatch(Seqstring T, Seqstring P)查找模式P在日标T中首次出现位置，成功时返回有效位移i, 失败返回-1int i,j,k;in
6、t m=P.length, n=T.length;/模式和目标串的长度for (i=0;i=n-m;i+) /循环控制匹配的趟数，其由合法位移 的个数确定 j=0;k=i; /确定模式串起始位置j、日标串动中子串的起始 位置k，即合法位移iwhile (jdata=p1-data)(t1=t1-next; p1=p1-next; else shift二shift-next; t1=shift;p1=P; /对应结点字符相等,t1,p1后移指向下一结点，否则，合法 位移shift后移指向下一子串，t1、pl重新定位开始下趟匹配。if (p1=NULL)return shift;elseretur
7、n NULL;/退出循环后，判定匹配成功与否算法时间复杂度与顺序串上的子串的定位运算相同。分析：顺序串和链串上实现串的模式匹配，算法思想相同，但应注意，存 储结构不同所导致的算法实现时具体操作上的区别。在顺序串上位移 为整数，链串上位移为结点的地址；子串与模式匹配时工作变量后移 在顺序串上通过加1实现，链串上靠指针变量后移实现；匹配成功与 否的判令条件顺序串上为j=m，链串上为p=NULL。对于不同的存储结构能够写出算法这是学习数据结构的基本要求， 改变存储结构要求应写出算法这也是一个重点。这一点大家应给予足 够的重视。应用举例算法阅读题1 .下列算法的功能是比较两个链串的大小，其返回值为：r
8、-1s1s2请在空白处填入适当的内容。2001int comstr(linkstring s1,linkstring s2)(/s1和s2为两个链串的头指针while(s1&s2) if(s1-datadata) return - 1;if(s1-datas2-data) return 1;if()return - 1;if()return 1;分析该题考核点是串的比较操作。While型循环通过指针s1、s2 将两个串中字符逐一比较，若发现不等字符，则不等字符的大小就是 两个串的大小；若所比较字符均相等，直到有串被扫描完为止，退出 循环。然后判断，若某个串未被扫描完，则其值大，若两个串同时被
9、扫描完，则两个串相等。答案 s1=s1-next; s2=s2-next; s2(或 s2!=NULL) s1(或 s1!=NULL) return 02. 编写算法实现现两个串的连接。算法如下: void stringcat(Hstring S,Hstring T) char *p,*q;p=S.ch+S.length;q=t.ch;while(pS.ch+maxsize&qT.ch+T.length)*p+ =*q+;if(qT.ch+maxsize) S.lengh=maxsize;else S.length二S.lengh+T.length;3. 删除主串中所有指定子串。算法如下：vo
10、id delsubstring(Hstring S,Hstring T)int i=0,j,k;while(iS.length)for(j=i,k=0;k=T.length)while(jS.length)S.chj-T.length=S.chj;j+;S.length二S.length-T.length;elsei+；【历届试题分析】一、选择题1. 下所述中正确的是()2001A. 串是一种特殊的线性表B.串的长度必须大于零C.串中元素只能是字母D.空串就是空白串答案A2. 若目标串的长度为n,模式串的长度为n/3,则执行模式匹配算法时，在最坏情况下的时间复杂度是() 2001A. O(n/
11、3)B. O(n)C. O(n2)D. O(n3)分析最坏情况下模式匹配的时间复杂度为O(n-n/3+1)*n/3),由于n和n/3是同阶的，所以，时间复 杂度可写为O(n2)。答案C3. 设有两个串T和P,求P在T中首次出现的位置的串运算称作()2003A. 联接B.求子串C .字符定位Id.子串定位分析该题考核点是串的基本操作。答案D4. 为查找某一特定单词在文本中出现的位置，可应用的串运算是()2002人.插入B.删除C.串联接D子串定位答案D5. 已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=SCI
12、ENCESTUDY”，则调用函数Scopy(P,Sub(S,1,7)后得到()2002A. P=SCIENCEB. P=STUDY”C. S=SCIENCED. S=STUDY”分析该题考核点是串的基本操作，函数Scopy(P,Sub(S,1,7)将串中子串 SCIENCE复制到P中，而 串S值未变。正确答案为A。答案A二、填空题6. 在串S=structure”中，以t为首字符的子串有 个。2001分析该题考核点是子串的概念。其中存在两个长度为1的子串。答案127. 串 S=I am a worker的长度是。2002分析该题考核点是串长度的概念。答案138. 设 S1=good”,S2= ,S3=book”，【JS1，S2 和 S3 依次联接后的结果是。2003分析该题考核点是串的连接操作及空白串的概念。答案good book三、算法阅读题9. 下列算法的功能是比较两个链串的大小，其返回值为:-1s1s2请在空白处填入适当的内容。2001int comstr(linkstring s1,linkstring s2)(/s1和s2为两个链串的头指针while(s1&s2) if(s1-datadata) return -
