🙊🙊作者主页：🔗求不脱发的博客
📔📔 精选专栏：🔗数据结构与算法
📋📋 精彩摘要：本章将介绍串的定义和存储结构，以及重点介绍数据结构与算法中重要的串的模式匹配算法：BF和KMP。
💞💞觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论💬支持博主🤞
📚目录
📖【数据结构与算法】第九章：串、数组和广义表
📝1️⃣串的结构定义及表示
✨定义
零个或多个字符组成的优先序列。
编辑
✨类型定义
ADT String { 数据对象；D 数据关系；R 基本操作； (1) StrAssign (&T,chars)//串赋值 (2) StrCompare (S,T)//串比较 (3) StrLength (S)//求串长 (4) Concat(&T,S1,S2)//串联 (5) SubString(&Sub,S,pos,len)//求子串 (6) StrCopy(&T,S)//串拷贝 (7) StrEmpty(S)//串判空 (8) ClearString (&S)//清空串 (9) Index(S,T,pos)//子串的位置 (11) Replace(&S,T,V)//串替换 (12) StrInsert(&S,pos,T)//子串插入 (12) StrDelete(&S,pos,len)//子串删除 (13) DestroyString(&S)//串销毁 }ADT String;
✨存储结构
顺序存储结构：
typedef String { char *ch;//字符 int length;//串长 }
链式存储结构：
链式存储结构顾名思义，将字符以块的形式，并用指针将一个个的块呈链式连接起来整体形成一个完整的串。
编辑
代码实现：
#define CHUNKSIZE 80 //可自定义块的大小 typedef struct Chunk { char ch[CHUNKSIZE]; stuct Chunk *next; }Chunk; typedef struct LString { Chunk *head,*tail;//串的头指针和尾指针 int curlen;//串的当前长度 }LString;
优点：操作方便。
缺点：存储密度低。
编辑
可将多个字符存放在一个结点中，增大存储密度。
编辑
📝2️⃣串的模式匹配算法
✨算法目的
给定一个主串和一个子串，确定主串中所含子串第一次出现的位置（定位）
✨算法种类
- BF算法（又称古典的、经典的、朴素的、穷举的）
- KMP算法（特点：速度快）
✨BF算法：
【算法设计思想】
编辑
Index(S,T,pos)：
- 将主串的第pos个字符和模式的第一个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符起，重新与模式的第一个字符比较。
- 直到主串的一个连续子串字符序列与模式相等 。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。
- 否则，匹配失败，返回值 0
【代码实现】
int Index(Sstring S,Sstring T,int pos){ i=pos; j=1; while (i<=S[ 0 ] && j <=T[ 0 ]){ if ( S[ i ]=T[ j ]) { ++i; ++j; } else { i=i-j+2; j=1; } if ( j>T[ 0 ]) return i－T[0]; else return 0; } }
【时间复杂度】
例： S=‘0000000001’，T=‘0001’，pos=1
若n为主串长度，m为子串长度，最坏情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位各比较了m次 最后m位也各比较了1次。
总次数为：(n-m)*m+m＝(n-m+1)*m
若m<<n，则时间复杂度为：O(n*m)。
✨KMP算法：
【算法设计思想】
利用已经部分匹配的结果而加快模式串的滑动速度？ 且主串S的指针i不必回溯！可提速到O(n+m)！
编辑
相对于BF算法，KMP算法最大的改进在于，每趟匹配过程中出现字符比较不等时，不回溯主指针i，利用已得到的“部分匹配”结果将模式向右滑动尽可能远的一段距离，继续进行比较。
为此,定义next[j]函数，表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。
编辑
【代码实现】
int Index_KMP (SString S,SString T, int pos) { i= pos,j =1; while (i<S[0] && j<T[0]) { if (j==0 || S[i]==T[j]) { i++;j++; } else j=next[j]; /*i不变,j后退*/ } if (j>T[0]) return i-T[0]; /*匹配成功*/ else return 0; /*返回不匹配标志*/ }
📝3️⃣数组
本章所讨论的数组与高级语言中的数组不同之处在与，高级语言中的数组是顺序结构，而本章的数组既可以是顺序的，也可以是链式结构，用户可根据需要选择。
✨抽象数据类型
ADT Array { 数据对象：D 数据关系：R 基本操作： (1) InitArray (&A,n,bound1, boundn) //构造数组A (2) DestroyArray (&A) // 销毁数组A (3) Value(A,&e,index1,…,indexn) //取数组元素值 (4) Assign (A,&e,index1,…,indexn) //给数组元素赋值 }ADT Array
【一维数组】
存储地址：LOC(0) = a,当 i > 0 时，LOC(i-1)+l = a+i*l。
存储图示：
编辑
第i个元素存储地址：LOC(i) = LOC(i-1)+l = a+i*l。
【二维数组】
编辑
编辑
编辑(p = m 或 n)
编辑 （二维数组以行序为主序）
编辑
编辑 （二维数组以行序为主序）
编辑
存储地址：
设数组开始存放位置 LOC( 0, 0 ) = a ， 则 LOC ( j, k ) = a + j * m + k。
【三维数组】
三维数组类似二维的基础上＋一维，可以按页/行/列存放，页优先的顺序存储。
编辑
定义一个三维数组：
a[m1][m2] [m3] 各维元素个数为 m1, m2, m3
下标为 i1, i2, i3的数组元素的存储位置：LOC ( i1, i2, i3 ) = a + i1* m2 * m3 + i2* m3 + i3
其中
- i1* m2 * m3 表示： 前i1页总 元素个数
- i2* m3 表示： 第i1页的 前i2行总元素个数
- i3 表示：第 i2 行前 i3 列元素个数
除了以上基本的维度数组外，还可以将其类似的推广到 n维数组。
各维元素个数为 m1, m2, m3, …, mn 下标为 i1, i2, i3, …, in 的数组元素的存储位置：
编辑
📝4️⃣广义表（列表）
✨定义
广义表（列表）：n个元素组成的有限序列，（n>=0），记作 LS = （a0,a1,...an-1）。
其中，LS为表名，ai是表元素，它可以是表（称为子表），可以是数据元素（称为原子）。n为表的长度。n=0的广义表为空表。
✨广义表与线性表的区别
- 线性表的成分都是结构上不可分的单元素。
- 广义表的成分可以是单元素，也可以是有结构的表。
- 线性表是一种特殊的广义表。
- 广义表不一定是线性表，也不一定是线性结构。
✨广义表的特点
- 有次序性 一个直接前驱和一个直接后继
- 有长度 表中元素个数
- 有深度 表中括号的重数
- 可递归 自己可作为自己的子表
- 可共享 可以为其他广义表所共享
