一、串
1、串的定义
计算机上的非数值处理的对象大部分是字符串数据,字符串一般简称为串
串是一种特殊的线性表,其特殊性体现在数据元素是一个字符,也就是说,串是一种内容
受限的线性表串(string)(或字符串)是由零个或多个字符组成的有限序列
串中字符的数目 n 称为串的长度。零个字符的串称为空串(null string) , 其长度为零
只有当两个串的长度相等, 并且各个对应位置的字符都相等时才相等
由一个或多个空格组成的串 ” ” 称为空格串 (blank string, 请注意:此处不是空串),
其长度为串中空格字符的个数
2、串的存储结构及其运算
2.1、串的存储结构
1)串的顺序存储
用一组地址连续的存储单元存储串值的字符序列。
按照预定义的大小,为每个定义的串变量分配一个固定长度的存储区,则可用定长数
组如下描述:
#define MAXLEN 255 // 串的最大长度
typedef struct{
char ch[MAXLEN + 1]; // 存储串的一位数组
int length; // 串的当前长度
} SString;
在C语言中,存在一个称之为“堆”(Heap) 的自由存储区,可以 为每个新产生的串动态分配一块实际串长所需的存储空间,若分配成功,则返回一个指向起始地址的指针,作为串的基址,同时为了以后处理方便,约定串长也作为存储结构的一部分。这种字符串的存储方式也称为串的堆式顺序存储结构。
串的堆式顺序存储结构
typedef struct{
char *ch; // 若是非空串,则按串长分配存储区,否则 ch 为NULL
int length; // 串的当前长度
} HString;
2)串的链式存储
用链表存储串值时,存在一个“结点大小”的问题,即每个结点可以存放一个字符,也可以存放多个字符
(a)所示为 结点大小为 4 (即每个结点存放 4 个字符)的链表,图 4.3 (b)所示为结点大小为 1 的链表
当结点大小大于 1 时,由于串长不一定是结点大小的整倍数,则链表中的最后一个结点不一定全被串值占满,此时通常补上”#”或其他的非串值字符(通常”#”不属于串的字符集,是一个特殊的符号)
为了便于进行串的操作,当以链表存储串值时,除头指针外,还可附设一个尾指针指示链
表中的最后一个结点,并给出当前串的长度。称如此定义的串存储结构为块链结构。
串的链式存储结构
#define CHUNKSIZE 80 // 可由用户定义的块大小
typedef struct CHUNK{
char ch[CHUNKSIZE];
struct Chunk *next;
} Chunk;
typedef struct{
Chunk *head,*tail; // 串的头尾指针
int length; // 串的当前长度
} LString;
在链式存储方式中,结点大小的选择直接影响着串处理的效率。
一般来说,字符集小,则字符的机内编码就短,这也影响串值存储方式的选取。
串值的链式存储结构对某些串操作,如联接操作等,有一定方便之处,但总地说来,不如顺序存储结构灵活,它占用存储量大且操作复杂。
2.2、串的模式匹配算法
子串的定位运算通常称为串的模式匹配或串匹配。
串的模式匹配设有两个字符串S和T, 设S为主串,也称正文串;设T为子串,也称为模式。
1)BF 算法
最简单直观的模式匹配算法是 BF (Brute-Force) 算法
最好情况下的平均时间复杂度是 O(n + m)
最坏情况下的平均时间复杂度是 O(n * m)
步骤:
- 分别利用计数指针 i 和 j 指示主串 S 和模式 T 中当前正待比较的字符位置,i 初值为 pos,j 初值为 1
- 如果两个串均未比较到串尾,即 i 和 j 均分别小于等于 S 和 T 的长度时,则循环执行以下操作:
- S[i].ch 和 T[j].ch 比较,若相等,则 i 和 j 分别指示串中下个位置,继续比较后续字符
- 若不等,指针后退重新开始匹配,从上一次匹配主串的起始位置的下一个字符(i = i – j + 2)起再重新和模式的第一个字符(j = 1)比较
- 如果 j > T.length ,说明模式 T 中的每个字符依次和主串 S 中的一个连续的字符序列相等,则匹配成功,返回和模式 T 中第一个字符相等的字符在主串 S 中的序号(i – T.length);否则称匹配不成功,返回 0
int Index_BF(SString S,SString T,int pos){
// 返回模式 T 在主串 S 中的第 pos 个字符开始第一次出现的位置,若不存在,则返回值为 0
// 其中,T 非空,1 ≤ pos ≤ S.length
i = pos;
j = 1; // 初始化
while(i <= S.length && j <= T.length){ // 两个串均未比较到串尾
if(S[i].ch == T[j].ch){ // 继续比较后继字符
++i;
++j;
}else{ // 指针后退重新开始匹配
i = i - j + 2; // 上一次匹配主串的起始位置的下一个字符
j = 1;
}
}
if(j > T.length)
return i - T.length; // 匹配成功
else
return 0; // 匹配失败
}
BF 算法的匹配过程
2)KMP 算法
这种改进算法是由 Knuth 、 Morris 和 Pratt 同时设计实现的, 因此简称 KMP 算法。
此算法可以在 O(n + m) 的时间数量级上完成串的模式匹配操作。
改进内容:
每当一趟匹配过程中出现字符比较不等时,不需回溯 i 指针,而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后,继续进行比较。当匹配过程中产生 “失配” 时,指针 i 不变,指针 j 退回到 next[j] 所指示的位置上重新进行比较,并且当 指针 j 退至零时,指针 i 和指针 j 需同时增 1。即若主串的第 i 个字符和模式的第 1 个字符不等,应从主串的第 i + 1个字符起重新进行匹配。
int Index_KMP(SString S,SString T,int pos){
// 利用模式串 T 的 next 函数求 T 在主串 S 中第 pos 个字符之后的位置
// 其中,T 非空,1 ≤ pos ≤ S.length
i = pos;
j = 1; // 初始化
while(i <= S.length && j <= T.length){ // 两个串均未比较到串尾
if(j == 0 || S[i] == T[j]){ // 继续比较后继字符
++i;
++j;
}else{ // 模式串向后移动
j = next[j];
}
}
if(j > T[0])
return i - T[0]; // 匹配成功
else
return 0; // 匹配失败
}
计算 next 函数值
// 时间复杂度为O(m)。
// 通常,模式串的长度m比主串的长度n要小得多,对整个匹配算法来说,所增加的
这点时间是值得的。
void get_next(SString T,int next[]){
// 求模式串 T 的 next 函数值并存入数组 next
i = 1;
next[1] = 0;
j = 0;
while(i < T[0]){
if(j == 0 || T[i] == T[j]){
++i;
++j;
next[i] = j;
}else{
j = next[j];
}
}
}
计算 next 函数修正值
void get_nextVal(SSTring T,int nextVal[]){
// 求模式串 T 的 next 函数修正值并存入数组 nextVal
i = 1;
nextVal[1] = 0;
j = 0;
while(i < T[0]){
if(j == 0 || T[i] == T[j]){
++i;
++j;
if(T[i] != T[j]){
nextVal[i] = j;
}else{
nextVal[i] = nextVal[j];
}
}else{
j = nextVal[j];
}
}
}
二、数组
1、数组的定义
数组是由类型相同的数据元素构成的有序集合。
数组中每个元素处于 n(n ≥ 1) 个关系中,故称该数组为 n 维数组。
特点是结构中的元素本身可以是具有某种结构的数据, 但属于同一数据类型。
2、特殊矩阵的压缩存储
所谓压缩存储,是指为多个值相同的元只分配一个存储空间, 对零元不分配空间。
假若值相同的元素或者零元素在矩阵中的分布有一定规律,则称此类矩阵为特殊矩阵。
1)对称矩阵
若 n 阶矩阵A中的元满足下述性质 = 1 ≤ i,j ≤ n 则称为 n 阶对称矩阵。
对于对称矩阵,可以为每一对对称元分配一个存储空间,则可将 个元压缩存储到 个元的空间中。
2)三角矩阵
上三角矩阵是指矩阵下三角(不包括对角线)中的元均为常数 c 或零的 n 阶矩阵, 下三角矩阵与之相反。
3)对角矩阵
对角矩阵所有的非零元都集中在以主对角线为中心的带状区域中,即除了主对角线上和直接在对角线上、下方若干条对角线上的元之外,所有其他的元皆为零。
4)稀疏矩阵
非零元较零元少,且分布没有一定规律, 称之为稀疏矩阵。
三、广义表
3.1、广义表的定义
广义表是线性表的推广,也称为列表。
在线性表的定义中,(1 ≤ i ≤ n)只限于是单个元素。
而在广义表的定义中,ai可以是单个元素,也可以是广义表,分别称为广义表 LS 的原子和子表。
习惯上,用大写字母表示广义表的名称,用小写字母表示原子。
广义表的定义是一个递归的定义。
例子:
(1) A = () —— A 是一个空表, 其长度为零
(2) B=(e) —— B 只有一个原子 e, 其长度为 1
(3) C= (a, (b, c, d)) —— C的长度为2, 两个元素分别为原子 a 和子表(b,c, d)。
(4) D = (A, B, C) —— D 的长度为3,3个元素都是广义表。显然,将子表的值代入后,则有 D = ((), (e), (a, (b, c, d)))。
(5) E = (a, E) —— 这是一个递归的表, 其长度为2。E 相当于一个无限的广义表 E=(a, (a,(a, ···)))。
结论:
- 广义表的元素可以是子表,而子表的元素还可以是子表。
- 广义表可为其他广义表所共享。
- 广义表可以是一个递归的表,即广义表也可以是其本身的一个子表。
广义表最重要的两个运算:
- 取表头 GetHead(LS):取出的表头为非空广义表的第一个元素,它可以是一个单原子,也可以是一个子表。
- 取表尾 GetTail(LS):取出的表尾为除去表头之外,由其余元素构成的表。即表尾一定是一个广义表。
3.2、广义表的存储结构
由于广义表中的数据元素可以有不同的结构(或是原子,或是列表),因此难以用顺序存储结构表示,通常采用链式存储结构。
常用的链式存储结构有两种, 头尾链表的存储结构 和 扩展线性链表的存储结构 。
1)头尾链表的存储结构
一对确定的表头和表尾可唯一确定广义表。
一个表结点可由3个域组成:标志域、 指示表头的指针域和指示表尾的指针域。
原子结点只需两个域 :标志域和值域。
广义表的头尾链式存储结构
typedef enum{
ATOM, // ATOM == 0:原子
LIST // LIST == 1:子表
} ElemTag;
typedef struct GLN ode{
ElemTag tag; // 公共部分,用于区分原子结点和表结点
union{
AtomType atom; // atom是原子结点的值域,AtomType有用户定义
struct{
struct GLN ode *hp,*tp;
}ptr; // ptr是表结点的指针域,ptr.hp和ptr.tp分别指向表头和表尾
};
}*GList; // 广义表类型
- 除空表的表头指针为空外,对任何非空广义表,其表头指针均指向一个表结点, 且该结点中的 hp 域指示广义表表头(或为原子结点,或为表结点),tp 域指向广义表表尾(除非表尾为空,则指针为空,否则必为表结点)
- 容易分清列表中原子和子表所在层次
- 最高层的表结点个数即为广义表的长度
2)扩展线性链表的存储结构
在这种结构中, 无论是原子结点还是表结点均由三个域组成。
扩展线性链表表示的存储结构示例
一 叶 知 秋,奥 妙 玄 心
今天的文章数据结构题集c语言版严蔚敏_数据结构c语言版严蔚敏pdf第四版分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/84006.html