导图社区 数据结构
- 6
- 0
- 0
- 举报
数据结构
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，它们之间存在某种关系，这种数据元素相互之间的关系称为结构。
编辑于2025-10-23 15:19:52- 数据结构
- 线性表
- 栈，队列和数组
- 相似推荐
- 大纲
数据结构
绪论
线性表
栈，队列和数组
栈
队列
队列的基本概念
队列的定义
队列简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除，向队列插入元素称为入队或进队，删除元素称为出队或离队
队头(Front)，允许删除的一端，也称队首，出队gogogo
队尾(Rear)，允许插入的一端，进队
空队列，不含任何元素的空表
先进先出(FIFO)
队列常见的基本操作
InitQueue(&Q)，初始化队列，构造一个空队列
QueueEmpty(Q)，判队列空
EnQueue(&Q,x),入队
DeQueue(&Q,&x),出队
GetHead(Q,&x),读队首元素
队列的顺序存储结构
队列的顺序存储
队列的顺序实现是指分配一块连续的存储单元存放队列训练的元素，并附设两个指针:队首指针front指向队首元素，队尾指针rear指向队尾元素的下一个位置
循环队列
将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。当队首指针Q.front=MaxSize-1后，再前进一个位置就自动到0，这可以利用除法取模运算(%)来实现
特定条件下循环队列队头/队尾指针的初值
初始时
Q.front=Q.rear=0
队首指针进1
Q.front=(Q.front+1)%MaxSize
队尾指针进1
Q.rear=(Q.rear+1)%MaxSize
队列长度
(Q.rear+MaxSize-Q.front)%MaxSize
出入队时
指针都按顺时针方向进1
特定条件下循环队列队空/队满的判断条件
为了区分是队空还是队满的情况
1，牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法，约定以“队首指针在队尾指针的下一位置作为队满的标志”
队满条件 (Q.rear+1)%MaxSize==Q.front
队空条件 Q.front==Q.rear
队列中元素的个数 (Q.rear-Q.front+MaxSize)%MaxSize
2，类型中增设size数据成员，表示元素个数。若删除成功，则size-1，若插入成功，则size+1，队空时Q.size==0，队满时，Q.size==MaxSize，两种情况都有Q.front==Q.rear
3，类型中增设tag数据成员，以区分是队满还是队空。删除成功置tag=0，若导致Q.front==Q.rear，则为队空，插入成功置tag=1，若导致Q.front==Q.rear，则为队满
循环队列的操作
初始化
判队空
入队
出队
队列的链式存储结构
队列的链式存储
根据需求分析队列适合的存储结构
队列的链式表示称为链式队列，它实际上是一个同时有队首指针和队尾指针的单链表
队列的链式存储类型可描述为
链式队列队空的判断
入队时，建立一个新结点，将新结点插入到链表的尾部，并将Q.rear指向这个新插入的结点(若原队列为空队，则令Q.front也指向该结点) 出队时，首先判断队列是否为空，若不空，则取出队首元素，将其从链表中删除，并让Q.frony指向下一个结点(若该结点为最后一个结点，则置Q.front和Q.rear都为空)
用单链表表示的链式队列特别适合于数据元素变化较大的情形，而且不存在队列满且产生溢出的问题。另外，假如程序中要使用多个队列，与多个栈的情形一样，最好使用链式队列，这样就不会出现存储分配不合理和“溢出”的问题
链式队列的基本操作
初始化
判队空
入队
出队
双端队列
双端队列是允许两段都可以进行插入和删除操作的线性表
输入受限的双端队列，可以看做一个栈，然后加上输出
输出受限的双端队列，可以看做一个栈，然后加上输入
栈和队列的应用
数组和特殊矩阵
数组的定义
数组是由n(n≥1)个相同类型的数据元素构成的有限序列，每一个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界
数组的存储结构
大多数计算机语言都提供了数组数据类型，逻辑意义上的数组可采用计算机语言中的数组类型进行存储，一个数组的所有元素在内存中占用一段连续的存储空间
二维数组按行优先存储下标对应关系
对于多维数组，有两种映射方法，按行优先和按列优先
按行优先存储的基本思想是，先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素，
设二维数组的行下标与列下标的范围分别为[0，h₁]和[0，h₂]
按行优先
LOC(ai，j)=LOC(a₀,₀)+[i×(h₂+1)+j]×L
按列优先
LOC(ai，j)=LOC(a₀,₀)+[j×(h₁+1)+i]×L
特殊矩阵的压缩存储
压缩存储:指为多个值相同的元素只分配一个存储空间，对零元素不分配空间
特殊矩阵:指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵
特殊矩阵的压缩存储方法，找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的，值相同的多个矩阵元素压缩存储到一个存储空间中
1，对称矩阵
若对一个n阶矩阵A中的任意一个元素ai，j都有ai，j=aj，i(1≤i，j≤n)，则称其为对称矩阵
对于n阶对称矩阵，上三角区的所有元素和下三角区的对应元素相同，因此只存下三角区(含主对角线)
2，三角矩阵
下三角矩阵中，上三角区的所有元素均为同一常量
上三角矩阵采用行优先存储的应用
存储完下三角区(含对角线)后，紧接着存储对角线上方的常量一次
3，三对角矩阵
对角矩阵也称带状矩阵。 对n阶矩阵A中的任意一个元素ai，j，当｜i-j｜＞1时，若有ai，j=0(1≤i，j≤n)，则称为三对角矩阵
将3条对角线上的元素按行优先方式存放在一维数组B中，且a₁，₁存放在B[0]中
三对角矩阵压缩存储的下标对应关系
由此可以计算矩阵A中三条对角线上的元素ai，j(1≤i，j ≤n，｜i-j｜≤1)在一维数组B中存放的下标k=2i+j-3
稀疏矩阵
矩阵中非零元素的个数t，相对于矩阵元素的个数s来说非常少，即s＞＞t的矩阵称为稀疏矩阵
常规方法存储稀疏矩阵相当浪费空间，因此存储非零元素
存储稀疏矩阵需要保存的信息
1，数组存储，将非零元素及其相应的行和列构成一个三元组
2，十字链表存储，不仅要保存三元组表，而且要保存稀疏矩阵的行数，列数和非零元素的个数
适合稀疏矩阵压缩存储的存储结构
归纳总结
P108
串
串的定义和实现
串的定义
串是由零个或多个字符组成的有限序列。一般记为S='a₁a₂...an'(n≥0)，其中，S是串名，单引号(或双引号)括起来的字符序列是串的值，ai可以是字母数字或其他字符，串中字符的个数n称为串的长度。n=0时的串称为空串(用∅表示)
串中任意多个连续的字符组成的子序列称为该串的子串，包含子串的串称为主串
子串在主串中的位置以子串的第一个字符在主串中的位置来表示
串的基本操作以子串为操作对象
串的基本操作
StrAssign(&T,chars),赋值操作
StrCopy(&T,S),复制操作
StrEmpty(S)，判空操作
StrCompare(S,T),比较操作
StrLength(S),求串长
SubString(&Sub,S,pos,len),求子串
Concat(&T,S1,S2),串联接
Index(S,T),定位操作
ClearString(&S),清空操作
DestroyString(&S)，销毁串
串的存储结构
1，定长顺序存储表示
类似于线性表的顺序存储结构，用一组地址连续的存储单元来存储串值的字符序列
#define MAXLEN 255 typedef struct{ char ch[MAXLEN]; int length; ｝SString;
串的实际长度只能小于或等于MAXLEN，超过预定义长度的串值会被舍去，称为截断
用一个额外的变量len来存放串的长度 在串值后面加上一个不计入串长的结束标记字符“\0”，此时串长为隐含值
2，堆分配存储表示
堆分配存储表示仍然以一组地址连续的存储单元存放串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的
typedef struct{ char *ch; //按串分配存储区，ch指向串的基地址 int length; //串的长度 }HString;
子主题
3，块链存储表示
类似于线性表的链式存储结构，也可以采用链表方式存储串值。由于串的特殊性，在具体实现事，每个结点既可以存放一个字符，又可以存放多个字符。每个结点称为块，整个链表称为块链结构
typedef struct{ char ch[4]；//每个结点有4个字符 struct StringNode *next； }StringNode，*String；
串的模式匹配
1，简单的模式匹配算法
模式匹配是指在主串中找到与模式串(想要搜索的某个字符串)相同的子串，并返回其所在的位置。这里采用定长顺序存储结构，给出一种不依赖于其他串操作的暴力匹配算法
int Index(SString S,SString T){ int i=1，j=1； while(i<=S.length&&j<=T.length){ if(S.ch[i]==T.ch[j]){ ++i;++j; ｝ else{ i=i-j+2;j=1; ｝ ｝ if(j＞T.length) return i-T.legth; else return 0; }
算法思想:从主串的第一个字符起，与模式串T的第一个字符比较，若相等，则继续逐个比较后续字符。否则从主串的下一个字符起，再重新和模式串T的字符比较。以此类推，直至模式串T中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，函数值为与模式串T中第一个字符相等的字符在主串S中的序号，否则成匹配不成功，函数值为0
在简单模式匹配算法中，设主串与模式串的长度分别为n和m(n＞＞m)，则最多需要进行n-m+1趟匹配，每趟最多需要进行m次比较，最坏时间复杂度为O(nm)
2，串的模式匹配算法——KMP算法
1，kmp原理，若已匹配相等的前缀序列中有某个后缀正好是模式串的前缀，则可将模式串向后滑动到与这些相等字符对齐的位置，主串指针i无需回溯，并从该位置开始继续比较，而模式串向右滑动位数的计算仅与模式串本身的结构有关，与主串无关
1，KMP算法的原理
前缀，是指除最后一个字符外，字符串的所有头部子串
后缀，是指除最后一个字符外，字符串的所有尾部子串
部分匹配值，是指字符串的前缀和后缀的最长相等前后缀长度
求“ababa”的部分匹配值PM “a”的前缀和后缀都为空集，最长相等前后缀长度为0 “ab”的前缀为{a}，后缀为{b}，{a}∩{b}=∅，最长相等前后缀长度为0 “aba”的前缀{a，ab}∩后缀{a，ba}={a｝，最长相等前后缀长度为1 “abab”的前缀{a，ab，aba}∩后缀{b，ab，bab}={a，ab}，最长相等前后缀长度为2 “ababa”的前缀{a，ab，aba，abab}∩后缀{a，ba，aba，baba}={a，ab，aba}，最长相等前后缀长度为3 因此模式串“ababa”的部分匹配值为00123
如果j=k时才发现匹配失败，说明1～k-1都匹配成功，若j=1时发生不匹配，i++，j=1，可以先令j=0再加一
用PM表来进行字符串匹配时，右滑位数=已匹配的字符数-对应的部分匹配值
某趟发生失配时，若已匹配相等的序列中没有相等的前后缀，则对应的部分匹配值为0，此时滑动的位数最大，直接将模式串首字符向右滑动到主串当前位置进行下一趟比较，若已匹配相等的序列中存在最大相等前后缀，则将模式串向右滑动到和主串中该相等后缀对齐，然后从主串当前位置进行下一趟比较。
2，next数组的手算方法
在实际的匹配过程中，模式串在内存中是不会滑动的，发生变化的是指针
KMP算法中指针变化，比较次数的分析
每趟匹配失败时，只有模式串指针i在变化，主串指针j不会回溯，为此可以定义一个next数组，next[j]的含义是当模式串的第j个字符失配时，跳到next[j]位置继续比较
P114
next[j]=j-右滑位数=j-(已匹配的字符数-对应的部分匹配值)
注意，当模式串匹配到位置j失配时，已匹配成功的字符数为j-1
next[1]=0
上述kmp算法的举例中，都假设串的编号是从1开始的，若串的编号是从0开始的，则next数组需要整体减1
3*，next数组的推理公式
next[j]={0，j=1；max{k｜1<k<j且'P₁...Pk-1'='Pj-k+1...Pj-1'｝，当此集合不为空时；1，其他情况；}
4*，kmp算法的实现
通过上述分析写出next值的程序如下 void get_next(SString T,int next[]){ int i=1,j=0; next[1]=0; while(i<T.length){ if(j==0｜｜T.ch[i]==T.ch[j]){ ++i;++j; next[i]=j;//若Pi=Pj，则next[j+1]=next[j]+1 else j=next[j];//否则令j=next[j]，循环继续 ｝ ｝
kmp匹配算法
具体代码如下 int Index_KMP(SString T,int next[]){ int i=1,j=1; while(i<=S.length&&j<=T.length){ if(j==0｜｜S.ch[i]==T.ch[j]){ ++i;++j; ｝ else j=next[j]; ｝ if(j＞T.length) return i-T.length; else return 0; ｝
3，KMP算法的进一步优化
nextval数组的计算
问题在于不应该出现Pj=Pnext[j]。当Pj≠Si时，下次匹配必然是Pnext[j]跟Si比较，若Pj=Pnext[j]，则 相当于拿一个和Pj相等的字符跟Si比较，这必然导致继续失配，这样的比较毫无意义
若出现Pj=Pnext[j]，则需要再次递归，将next[j]修正为next[next[j]]，直至两者不相等为止，更新后的 数组命名为nextval。计算next数组修正值的算法如下，此时匹配算法不变
void get_nextval(SString T，int nextval[]){ int i=1，j=0; nextval[1]=0; while(i<T.length){ if(j==0｜｜T.ch[i]==T.ch[j]){ ++i;++j; if(T.ch[i]!=T.ch[j]) nextval[i]=j; else nextval[i]=nextval[j]; ｝ else j=nextval[j]; ｝ }
归纳总结
P123
树与二叉树
5.1树的基本概念
5.1.1树的定义
树是n(n≥0)个结点的有限集。当n=0时，称为空树。在任意一棵非空树中应满足
1有且仅有一个特定的称为根的结点
2当n＞1时，其余结点可分为m(m＞0)个互不相交的有限集T1，T2，...，Tm，其中每个集合本身又是一棵树，并且称为根的子树
树的定义是递归的，即在树的定义中又用到了其自身，树是一种递归的数据结构 树是一种逻辑结构，同时也是一种分层结构
1树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱
2树中所有结点都可以有零个或多个后继
根结点没有直接上层结点，因此在n个结点的树中有n-1条边
5.1.2基本术语
1祖先，子孙，双亲，孩子兄弟和堂兄弟
2结点的层次，深度和高度
3结点的度和树的度
4分支结点和叶结点
5有序树和无序树
6路径与路径长度
7森林
森林中树的数量，边数和结点数的关系
5.4讨论
5.1.3树的性质
1树的结点数n等于所有结点的度数之和(边数之和)加1
2度为m的树中第层上至多有mⁱ⁻¹个结点
3高度为h的m叉树至多有(mʰ-1)/(m-1)个结点
4度为m，具有n个结点的树的最小高度h为
指定结点数的三叉树的最小高度分析
5度为m，具有n个结点的树的最大高度h为n-m+1
高度为h，度为m的树至少有h+m-1个结点
5.2二叉树的概念
5.2.1二叉树的定义及其主要特性
1，二叉树的定义
二叉树是一种特殊的树形结构，其特点是每个结点至多有两棵子树(二叉树中不存在度大于2的结点)，二叉树的子树有左右之分，其次序不能任意颠倒
或者为空二叉树，即n=0
或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成 左子树和右子树又分别是一棵二叉树
二叉树与度为2的有序树的区别
度为2的有序树至少有3个结点，而二叉树可以为空
度为2的有序树的孩子的左右次序是相对于另一个孩子而言的，若某个结点只有一个孩子，则这个孩子就无需区分左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，即二叉树的结点次序不是相对于另一结点而言，而是确定的
2，几种特殊的二叉树
1，满二叉树
一棵高度为h，且有2ʰ-1个结点的二叉树称为满二叉树
2，完全二叉树
完全二叉树中结点个数和叶结点数的关系
高度为h，有n个结点的二叉树，当且仅当每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为完全二叉树
3，二叉排序树
左子树上所有的结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于根结点的关键字;左子树和右子树又各是一棵二叉排序树
4，平衡二叉树
树中任意一个结点的左子树和右子树的高度之差的绝对值不超过1。
5，正则二叉树
树中每个分支都有2个孩子，即
图
查找
排序