《数据结构(c语言)第四章 串(string )2》由会员分享，可在线阅读，更多相关《数据结构(c语言)第四章 串(string )2（22页珍藏版）》请在金锄头文库上搜索。
1、 第四章 串(String ）本章概要本章介绍符号数据字符串的基本概念、存储结构以 及基本运算和实现。通过学习掌握：*字符串的定义及特点；*字符串上各种运算；*字符串的顺序存储、链式存储以及各种运算在存储结 构上的实现；*串的模式匹配。4.1、有关字符串的基本概念 字符集（符号集）:是一个系统中允许使用的所 有符号的集合。 字符串: 是由字符集上的符号组成的有限序列。如S=aabc ,S 为字符串名字， aabc为字符串的值。两个单引号不是字符串的 值，它们只是两个标识符。 字符串的长度 ：是两个单引号中字符的个数。 空字符串： 是不包含任何字符的串。表示为X=。其长度为0 ，常用表示。 空格
2、字符串： 是有空格符组成的字符串 。例如，Y = 是只含有一个空格符的串 。其长度为1。 子字符串 ： 是字符串中任意个连续的字符组成的子 序列称为该串的子串。例如aa,abc,aab都是S的子 串.4.2 串的表示和实现 1、串的定长顺序存储：即字符数组，如char str1000； 2、堆（heap）分配存储表示： 即动态分配的连续空间，malloc和free； 3、块链存储表示：即链表1、串的定长顺序存储 是用一组地址连续的存储单元存储字符串的字符 序列。其实现的方法是按照用户予定义的大小， 系统为每个串的变量分配一个固定长度的存储区 。 一般用定长数组描述： # define MAXS
3、TRLEN 255 Typedef char SstringMAXSTRLEN+1 （规定：0号单元存放串的长度）。 注：C语言中字符串是以0为结束。字符串上的运算字符串的定义； 字符串的赋值； 字符串的联接MyConcat(T,S1,S2); 求子串MySubString(String,Sub,pos,len); 两个串比较MyStringCompare(s,t)2.堆分配存储表示 在应用程序中，参与运算的串变量之间的长度相 差较大，并且操作中串值的长度变化也较大。因 此为串变量预分配固定大小的空间不尽合理。 堆存储结构的基本思想是：在内存中开辟能存储 足够多的串、地址连续的存储空间作为应用
4、程序 中所有串的可利用存储空间，称为堆空间，如设 storeSMAX+1; 根据每个串的长度，动态的为每个串在堆空间里 申请相应大小的存储区域，这个串顺序存储在所 申请的存储区域中，当操作过程中若原空间不够 了，可以根据串的实际长度重新申请，拷贝原串 值后再释放原空间。基于堆的串结构 typedef struct char *ch; /*起始地址*/int length; /*串长*/ Hstring；基于堆的串操作实现 串赋值; 串复制 串连接 求子串 串比较4.2.3 串的链式存储结构 串的链式存储结构有时称为链串。 链串的存储形式与一般的链表类似，是将存储 区分成许多结点，每个结点有一个
5、存放字符的 域和一个存放指向下一个结点的指针域。 链串中的一个存储结点可以存储1个或多个字 符，通常将链串中每个存储结点所存储的字符 个数称为结点大小 单字符结点的串的链式存储结构 多字符结点的串的链式存储结构 链串的类型定义define CHUNKSIZE 80 /定义的结点大小 typedef struct Chunk char chCHUNKSIZE;struct node *Chunk;Chunk; 当结点大小为1时，可将ch域简单定义为：char ch; 链串的结构定义Typedef struct Chunk *head, *tail; int curlen; LString;串的存
6、储密度存储密度为：实际所占位数 / 分配空间位数对比优缺点： 密度小：? 密度大：?4.3 串的模式匹配算法 串的模式匹配，就是判断某串T（模式串）是 否是另一个已知串S的子串，如是其子串，则 给出该子串的起始点（即从已知串的哪个字 符开始），故此运算又称为子串定位运算。 显然T是S的子串的一个必要条件是，T的长 度LT一定要小于或等于S的长度LS，即 LTLS。简单的模式匹配算法 算法思想如下： 首先将s1与t1进行比较，若不同，就将 s2与t1进行比较，.，直到s的某一个字符 si和t1相同，再将它们之后的字符进行比较， 若也相同，则如此继续往下比较，当s的某一个 字符si与t的字符tj不
7、同时，则s返回到本趟开 始字符的下一个字符，即si-j+2，t返回到t1， 继续开始下一趟的比较，重复上述过程。若t中的字符全部比完，则说明本趟匹配成功，本 趟的起始位置是i-j+1或i-t0，否则，匹配失败。 第一趟第二趟第三趟第四趟第五趟第六趟该算法简称为BF算法，描述如下: int Index (SString S,SString T,int pos) int i=pos, j=1;while (it0) return (i-t0); /*匹配成功，返回存储位置*/else return 0; BF算法的时间复杂度 最好情况下的时间复杂度是O(n+m)。 最坏情况下的时间复杂度是O(n*
8、m)。 时间复杂度： T（n）=O( n*m ) BF算法的一种改进:首尾匹配算法 算法思想： 先比较模式串的第一个字符，再比较模式 串的最后一个字符，最后比较模式串中从 第二个到第n-1个字符。 int Index_FL(SString S, SString T, int pos) int sLen = S0, tLen = T0, i = pos ,k=1, j=2;char patStartChar = T1, patEndChar = TtLength;while (i = sLen tLen + 1) if (Si != patStartChar) +i; /重新查找匹配起始点 el
9、se if (Si+tLen-1 != patEndChar) +i; / 模式串的“尾”不匹配else / 检查中间字符的匹配情况 while ( j tLen +j; if ( j = tLength ) return i;else +i; / 重新开始下一次的匹配return 0; BF算法的另一种改进：KMP算法 首先求出模式串的各个字符next回退值； 在主串中查找模式串的匹配过程中，若在 主串第i个位置与模式串第j个位置字符“失配 ”，则将主串第i个位置上字符继续与模式串 第j个位置字符的回退值所对应位置上的字 符进行匹配比较。算法设计题1. 对于采用顺序结构存储的串r，设计 一算法将串逆置。2. 采用单链表结构存储的串r，编写一 个函数将其中所有的c字符替换成s 字符。
