导图社区 数据结构
- 434
- 19
- 10
- 举报
数据结构
数据结构思维导图：数据结构的基本概念，算法和算法评价，线性表，树和二叉树，树的定义是递归的，是一种递归的数据结构。等等
编辑于2022-03-31 15:00:22- 相似推荐
- 大纲
数据结构
绪论
数据结构的基本概念
基本概念和术语
数据结构三要素
算法和算法评价
算法的基本概念
算法效率的度量
线性表
线性表的定义和基本操作
线性表的定义
是具有n个相同数据类型的n（n>=0)个数据元素的有限序列。
特点
表中元素的个数有限
表中元素具有逻辑上的顺序性，表中元素有其先后次序
表中元素都是数据元素，每个元素都是单个元素。
表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。
⚠️
线性表是一种逻辑结构，表示元素之间一对一的相邻关系。
顺序表和链表是指存储结构。
线性表的基本操作
增删改查
线性表的顺序表示
顺序表的定义
线性表的顺序存储又称顺序表
特点：表中元素的逻辑顺序与其物理顺序相同。
线性表中的任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。
⚠️ 线性表中元素的位序是从1开始的，而数组中元素的下标是从0开始的。
线性表顺序存储
#define MaxSize 50 typedef struct{ ElemType data[MaxSize]; int length; }SqList;
#define MaxSize 50 typedef struct{ ElemType data[MaxSize]; int length; }SqList;
动态
#define InitSize 100 typedef struct{ ElemType *data; int MaxSize,length; }SeqList; //动态分配数组顺序表的类型定义
#define InitSize 100 typedef struct{ ElemType *data; int MaxSize,length; }SeqList; //动态分配数组顺序表的类型定义
C语言动态分配语句
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
C++的初始动态分配语句为
L.data=new ElemType[InitSize];
动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时动态决定。
线性表最主要的特点：
随机访问O（1）
存储密度高，每个结点只存储数据元素
顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。
拓展容量不方便。
顺序表上基本操作的实现
1⃣️ 插入操作
bool ListInsert(SqList &L,int i,ElemType e){ if(i<1 || i > L.length+1) return false; if( L.length >= MaxSize) return false; for(int j=L.length;j>=i;j- -) L.data[j]=L.data[j-1]; L.data[i-1]=e; L.length++; return true; }
bool ListInsert(SqList &L,int i,ElemType e){ if(i<1 || i > L.length+1) return false; if( L.length >= MaxSize) return false; for(int j=L.length;j>=i;j- -) L.data[j]=L.data[j-1]; L.data[i-1]=e; L.length++; return true; }
插入的平均时间复杂度为O（1）。
2⃣️ 删除操作
bool ListDelete(SqList &L,int i, ElemType &e){ if(i < 1 || i > L.length) return false; e=L.data[i - 1]; for(int j = i;j < L.length;j++) L.length- -; return true; }
bool ListDelete(SqList &L,int i, ElemType &e){ if(i < 1 || i > L.length) return false; e=L.data[i - 1]; for(int j = i;j < L.length;j++) L.data[j-1] = L.data[j]; L.length- -; return true; }
删除平均时间复杂度O（n）
3⃣️ 按值查找
int LocateElem(SqList L,ElemType e){ int i; for(i =0;i < L.length;i++) if(L.data[i]==e) return i+1; }
int LocateElem(SqList L,ElemType e){ int i; for(i =0;i < L.length;i++) if(L.data[i]==e) return i+1; return 0; }
查找平均情况O（n）。
线性表的链式表示
插入和删除操作不需要移动元素，而只需要修改指针，但也会失去顺序表可随机存取的优点。
单链表的定义
子主题
单链表上基本操作的实现
采用头插法建立单链表
采用尾插法建立单链表
按序号查找结点值
按值查找表结点
插入结点操作
删除结点操作
求表长操作
双链表
子主题
循环链表
静态链表
树和二叉树
树的基本概念
树的定义
树是n（n>=0)个结点的有限集。
当n=0时，称为空树
一棵非空树应满足
1⃣️ 有且仅有一个特定的称为根的结点
2⃣️ 当n>1时，其余结点可分为m（m>0)个互不相交的有限集T1，T2，•••Tm，其余每个集合本身又是一棵树，并且称为根的子树。
树的定义是递归的，是一种递归的数据结构。
树作为一种逻辑结构，同时也是一种分层结构，具有以下特点
1⃣️ 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
2⃣️ 树中所有结点可以有零个或多个后继。
树适合用于表示具有层次结构的数据。
n个结点的树中有n-1条边
树中的每个结点与其下一层的零点或多个结点有直接关系。
基本术语
1⃣️ 考虑结点 （祖先、双亲、兄弟、子孙）
根是树中唯一没有双亲的结点。
2⃣️ 树中一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度。
3⃣️ 度大于0的结点称为分支结点（又称非终端结点）度为0的结点称为叶子🍃结点（终端结点）。
在分支结点中，每个结点的分支树就是该结点的度
4⃣️ 结点的深度、高度和层次。
结点的层次是从根结点开始定义，根结点为第一层，它的子结点为第二层，依次类推。
双亲结点在同一层的结点互为堂兄弟。
结点的深度是从根结点开始自顶向下逐层累加的。
结点的高度是从叶结点开始自底向上逐层累加的。
树的高度（深度）是树中结点的最大层树。
5⃣️ 有序树和无序数
树中个子树从左到右是有次序的，不能互换，称为有序树。否则为无序树。
有序树若将子结点位置互换，则变成一棵不同的树。
6⃣️ 路径和路径长度
树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。
由于树中的分支是有向的，即从双亲指向孩子，所以树的路径是从上而下的，同一个双亲的两个孩子之间不存在路径。
7⃣️ 森林
森林是m（m>=0)棵互不相交的树的集合。
只要把树的根结点删掉就成了森林。反之只要把m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林变成了树。
树的性质
树中的结点数等于所有结点的度数之和➕1
度为m的树中第i层至多有m^（i-1）个结点（i>=1)
高度为h的m叉树至多有（m^h-1）/（m-1）个结点。
具有n个结点的m叉树的最小高度为
二叉树的概念
二叉树的概念及其主要特性
二叉树的定义
特点：每个结点至多只有两颗子树，并且有左右之分，不能颠倒
二叉树是n大于等于零的结点的有限集合：
或者为空二叉树，即n=0
或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
二叉树与度为2的有序树的区别：
1⃣️ 度为2的树至少有3个结点，而二叉树可以为空
度为2的有序树的孩子的左右次序是相对于另一个孩子而言的，而二叉树的结点次序不是相对于另一结点而言的，而是确定的。
几个特殊的二叉树
1⃣️ 满二叉树
一棵高度为h，且含有2^h-1个结点的二叉树称为满二叉树
除叶子结点外的每个结点度数均为2
编号从根结点开始
对于编号i的结点若有双亲则双亲为i/2（向下取整
若有左孩子，则左孩子为2i
若有右孩子，则右孩子为2i+1
2⃣️ 完全二叉树
满二叉树是特殊的完全二叉树
若i<=[n/2]向下取整，则结点i为分支结点，否则为叶子结点。
叶子结点只可能在层次数最大的两层出现。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。
最多只能有一个度为一的结点，且该结点只有左孩子而无右孩子。
3⃣️ 二叉排序树
左子树上所有结点的关键字均小于根结点的关键字
右子树上所有结点的关键字均大于根结点的关键字
左子树和右子树又是一棵二叉排序树
便于元素的查找
4⃣️ 平衡二叉树
🤡👹2009 树上任意结点的左子树和右子树的深度之差不超过1
二叉树的性质
🤡🐉2011 非空二叉树上的叶子结点数等于度为2的结点数➕1
n=n0+n1+n2
n=B+1
B=n1+2n2
n0=n2+1
非空二叉树上第k层上至多有2^（k-1）个结点（k>=1)(公比为2的等比数列）
高度为h的二叉树至多有2^h-1 个结点h大于等于1
完全二叉树排序
具有n个（n>0)结点的完全二叉树的高度为
二叉树的存储结构
顺序存储结构
树中结点的序号可以唯一地反应结点之间的逻辑关系
节省存储空间
利用数组元素下标值确定结点在二叉树中的位置，以及结点之间的关系。
🚬数组下表从1⃣️开始
空间利用率低
链式存储结构
包含数据域data、左指针域lchild和右指针域rchild
二叉树的链式结构描述
typedef struct BiTNode{ ElemType data; struct BiTcode *lchild,*rchild; }BiTNode,*BiTree;
typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;
含有n个结点的二叉链表中，含有n+1个空链域‼️
二叉树的遍历和线索二叉树
二叉树的遍历
二叉树的遍历是指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。
先序遍历（NLR）
若二叉树为空则什么都不做
若不空
访问根结点
先序遍历左子树
递归算法
void PreOrder（BiTree T）{ if（T！Null）{ visit(T); PreOrder(T->lchild); PreOrder(T->rchild); } }
void PreOrder（BiTree T）{ if（T！Null）{ visit(T); PreOrder(T->lchild); PreOrder(T->rchild); } }
先序遍历右子树
中序遍历
若为空什么都不做
若不为空则
中序遍历左子树
访问根结点
递归算法
void InOrder(BiTree T){ if(T！=Null){ InOrder->lchild; visit(T); InOrder->rchild; } }
void InOrder(BiTree T){ if(T！=Null){ InOrder->lchild; visit(T); InOrder->rchild; } }
中序遍历右子树
后序遍历
同上
总
遍历的左右顺序都是固定的，只是访问根结点的顺序不同。每个结点都只访问一次，时间复杂度都是O （n ）。
在递归工作站中，递归工作站的深度恰好为树的深度，在最坏情况下，二叉树是有n 个结点且深度为n 的单支树，遍历算法的空间复杂度为O （n ）。
递归算法和非递归算法的转换
线索二叉树
🤡🐉2011 统计一个二叉树中非叶子结点的个数
int NoLeafCount(BiTNode *pHead){ if(pHead=NULL) return 0; else if(NULL=pHead->lchild&&NULL=pHead->rchild) return 0; else return(1+NoLeafCount(pHead->lchild)+NoLeafCounf(pHead->rchild)); }
int NoLeafCount(BiTNode *pHead){ if(pHead=NULL) return 0; else if(NULL=pHead->lchild&&NULL=pHead->rchild) return 0; else return(1+NoLeafCount(pHead->lchild)+NoLeafCounf(pHead->rchild)); }
树，森林🌳
树的存储结构
双亲表示法
采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。
双亲表示法的存储结构
#define MAX_TREE_SIZE 100 typedef struct { ElemType data; int parent; //双亲位置域 }PTNode; typedef struct{ PTNode nodes[MAX_TREE_SIZE]; //双亲表示 int n; //结点数 }PTree;
#define MAX_TREE_SIZE 100 typedef struct { ElemType data; int parent; //双亲位置域 }PTNode; typedef struct{ PTNode nodes[MAX_TREE_SIZE]; //双亲表示 int n; //结点数 }PTree;
除根结点外只有唯一双亲的性质，可以很快得到每个结点的双亲结点，但求其结点的孩子结点时需要遍历整个结构。
树的顺序存储与二叉树的顺序存储的区别
树的顺序存储中，数组下标代表结点的编号，下标中所存的内容指示了结点之间的关系。
二叉树的顺序存储，数组下标既代表了结点的编号，又指示了二叉树中各结点之间的关系。
二叉树可以用树的存储结构来存储，但树却不能用二叉树的存储结构来存储。
孩子表示法
将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n个结点就有n个孩子链表（叶子结点的孩子链表为空）。
寻找子女的操作非常直接，而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。
孩子兄弟表示法（二叉树表示法）
以二叉链表作为树的存储结构。
每个指针包含：结点值、指向结点第一个孩子结点的指针，及指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点）。
孩子兄弟表示法的存储结构
typedef struct CSNode{ ElemType data; //数据域 struct CSNode *firstchild,*nextsibling;//第一个孩子和右兄弟指针 }CSNode,*CSTree;
typedef struct CSNode{ ElemType data; //数据域 struct CSNode *firstchild,*nextsibling;//第一个孩子和右兄弟指针 }CSNode,*CSTree;
优：可以方便的实现树转换为二叉树的操作，易于找孩子的结点等
缺：从当前结点查找其双亲结点比较麻烦。
若为每个结点增设一个parent域指向其父结点，则查找结点的父结点也很方便。
树、森林与二叉树的转换
树和森林的遍历
树的应用—-并查集
树与二叉树的应用
排序
排序的基本概念
就是重新排列表中的元素
根据数据是否在内存中分为
内部排序
全部在内存中的排序
外部排序
根据要求不断在内、外存之间移动的排序。
对于n个关键字排序的比较次数至少为2^t >= n！🤡
插入排序
直接插入法
最好O（n），最坏O（^2）
最多比较次数【n（n-1）】/2
时间复杂度O（n^2）
平均O（n^2）
稳定
在最后一趟开始之前，可能出现所有元素都不在最终位置上。
折半插入排序
时间复杂度O（n^2）
希尔排序
希尔排序组内采用的是直接插入排序。
交换排序
交换排序
选择排序
归并排序和基数排序
各种内部排序算法的比较及应用
外部排序
栈和队列
栈（Stack）
栈的基本概念
栈的定义
栈是只允许在一端进行插入或删除操作的线性表
栈顶（Top）线性表允许进行插入删除的那一端。
栈底（Bottom）固定的，不允许进行插入和删除的另一端。
空栈 不含任何元素的空表
操作特性：后进先出。（Last In First out，LIFO）
栈的数学性质：n个不同元素进栈，出栈元素不同排列的个数为【 1 / （ n + 1 ）】C^n 2n（上n下2n）称为卡特兰树。
栈的基本操作
InitStack （ & S ）：初始化一个空栈S。
StackEmpty（ S ）：判断一个栈是否为空。
若栈为空返回true
否则false
Push （ & S ，x）： 进栈
若栈S未满则将x加入使之成为新栈顶。
Pop（& S ，& x ）：出栈
若栈S非空则弹出栈顶元素，并用x返回。
GetTop （ S ，& x ）：读栈顶元素
若栈非空，则用x返回栈顶元素。
DestroyStack（ & S ）：销毁栈
并释放栈S所占的存储空间（“&”表示引用调用）。
栈的顺序存储
栈是一种操作受限的线性表，类似于线性表，也有对应的两种存储方式。
顺序栈的实现
采用顺序存储的栈成为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。
栈的顺序存储类型可描述为
＃define Maxsize 50 //定义栈中素的最大个数 typedef struct { ElemType data [ Maxsize ]; //存放栈中素 int top; //栈顶指针 } SqStack；
＃define Maxsize 50 //定义栈中素的最大个数 typedef struct { ElemType data [ Maxsize ]; //存放栈中元素 int top; //栈顶指针 } SqStack；
栈顶指针：S.top
初始时设置S.top=-1;
栈顶元素：S.data[S.top]。
进栈操作：栈不满时，栈顶指针先➕1，再送值到栈顶元素。
出栈操作：栈非空时，先取栈顶元素的值，再将栈顶指针- 1。
栈空条件：S.top==-1;栈满条件：S.top==MaxSize - 1;栈长：S.top + 1。
由于顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能发生上溢，此时应及时向用户报告消息，以便及时处理，避免差错。
🤡函数调用时，必须使用栈来保存必要的信息。
顺序栈的基本运算
1⃣️ 初始化
viod InitStack ( SqStack &S){ S.top = - 1 ; //初始化栈顶指针 }
viod InitStack ( SqStack &S){ S.top = - 1 ; //初始化栈顶指针 }
2⃣️ 判栈空
viod StackEmpty ( SqStack S){ if（S.top == - 1 ） //栈空 return true; else //不空 return false; }
viod StackEmpty ( SqStack S){ if（S.top == - 1 ） //栈空 return true; else //不空 return false; }
3⃣️ 进栈
bool push ( SqStack &S , ElemType x ){ if（S.top == MaxSize - 1） //栈满，报错 return false; S.data[++S.top]=x; //指针先➕1，再入栈 return true; }
bool Push ( SqStack &S , ElemType x ){ if（S.top == MaxSize - 1） //栈满，报错 return false; S.data[++S.top]=x; //指针先➕1，再入栈 return true; }
4⃣️ 出栈
bool push ( SqStack &S , ElemType x ){ if（S.top == - 1） //栈空，报错 return false; x=S.data[S.top- -]; //先出栈，指针再-1 return true; }
bool push ( SqStack &S , ElemType &x ){ if（S.top == - 1） //栈空，报错 return false; x=S.data[S.top- -]; //先出栈，指针再-1 return true; }
5⃣️ 读栈顶元素
bool push ( SqStack &S , ElemType x ){ if（S.top == - 1） //栈空，报错 return false; x=S.data[S.top]; //x记录栈顶元素 return true; }
bool GetTop ( SqStack &S , ElemType &x ){ if（S.top == - 1） //栈空，报错 return false; x=S.data[S.top]; //x记录栈顶元素 return true; }
仅为读取栈顶元素，并没有出栈操作，因此原栈顶元素依然保存在栈中。
共享栈
利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数組空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间沿伸。
🤡共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。
存取数据的事件复杂度均为O（1）
栈的链式结构
采用链式存储的栈称为链栈
🤡链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。
栈的链式存储类型可描述为
typedef struct Linknode{ ElemType data; //数据域 strict Linknode *next; //指针域 } *LiStack; //栈的类型定义
typedef struct Linknode{ ElemType data; //数据域 struct Linknode *next; //指针域 } *LiStack; //栈的类型定义
采用链式存储，便于结点的插入与删除。
链栈的操作与链表类似，入栈和出栈的操作都在链表的表头进行。
⚠️对于带头节点和不带头节点的链栈，具体的实现情况会有所不同。
向一个带栈顶指针为top 的链栈（不带头节点）中插入一个x 的结点，则执行：
x - > next = top;
top = x;
向一个带栈顶指针为top 的链栈（带头节点）中插入一个x 的结点，则执行：
x - > next = top - > next;
top - > next = x;
链栈（不带头节点）执行Pop操作，并将出栈的元素存在x中，应该执行：
x = top -> data;
top = top - > next;
链栈（带头节点）执行Pop 操作，并将出栈的元素存在x 中，应该执行：
x = top -> next - data;
top - > next = top - > next - > next;
栈和队列的关系
🤡栈和队列的逻辑结构都是相同的，都属于线性结构，只是他们对数据的运算不同。
🤡栈和队列都是限制存取点的线性结构。
队列
队列的基本概念
队列的定义
队列（Queue）简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。
向队列中插入元素称为入队和进队；删除元素称为出队和离队。
操作特性：先进先出（First In First Out ，FIFO）
🤡队头（Front）。允许删除的一端，又称队首。
🤡队尾（Rear）。允许插入的一端。
⚠🤡🤡🤡️循环、非循环、单链表最适合用作链队的链表主要考虑队尾rear指针（插入一端）
空队列。不含任何元素的空表。
队列常见的基本操作
InitQueue（&Q）：初始化队列构造一个空队列Q
QueueEmply（Q）：判断队空
若队列为空则返回true
否则返回false
EnQueue（&Q，x）：入队
若队列Q未满则将x加入，使之成为新的队尾。
DeQueue（Q，&x）：出队
若队列Q非空，删除对头元素，并用x返回。
GetHead（Q，&x）：读对头元素
若队列Q非空，则将队头元素赋值给x。
队列的顺序存储结构
队列的顺序存储
队列的顺序实现是指分配一块连续的存储单元存放队列的元素，并附设两个指针：
队头指针front指向队头元素
队尾指针rear指向队尾元素的下一个位置
队列的顺序存储类型
＃define Maxsize 50 //定义队列中素的最大个数 typedef struct { ElemType data [ Maxsize ]; //存放队列中素 int front，rear; //对头指针和队尾指针 } SqQueue；
＃define Maxsize 50 //定义队列中素的最大个数 typedef struct { ElemType data [ Maxsize ]; //存放队列中素 int front，rear; //对头指针和队尾指针 } SqQueue；
初始状态（队空的条件）
Q.front = = Q.rear = = 0。
进队操作：
队不满时，先送值到队尾元素，再将队尾指针➕1
出队操作：
队不空时，先取对头元素值，再将对头指针 ➕1
不能用Q.rear = = MaxSize 来判断队满的情况
队列中只有一个元素时也满足这个条件
这是入队出现“上溢出”但这种溢出不是真正的溢出而是一种假溢出。
循环队列
概念
将循环队列臆造成为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，。
当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⃣️ 类型中增设表示元素个数的数据成员。
队空条件为：
Q.size = = 0。
队满条件：
Q.size = = MaxSize。
3⃣️ 类型中增设tag成员，以区分是队满还是队空
tag等于 0
若因删除导致Q.front = = Q.rear 则为空。
tag等于 1
若因插入导致Q.front = = Q.rear 则队满。
循环队列的操作
1⃣️ 初始化
void InitQueue(SqQueue &Q){ Q.rear=Q.front=0; //初始化队首、队尾指针 ｝
void InitQueue(SqQueue &Q){ Q.rear=Q.front=0; //初始化队首、队尾指针 ｝
2⃣️ 判队空
bool isEmpty(SqQueue Q){ if(Q.rear==Q.front) return true; else return false; }
bool isEmpty(SqQueue Q){ if(Q.rear==Q.front) //队空条件 return true; else return false; }
3⃣️ 入队
bool EnQueue(SqQueue &Q,ElemType x){ if ((Q.rear+1)%MaxSize==Q.front) //队满报错 return false; Q.data[Q.rear]=x; Q.rear=(Q.rear+1)%MaxSize; //队尾指针加1取模 return true; }
bool EnQueue(SqQueue &Q,ElemType x){ if ((Q.rear+1)%MaxSize==Q.front) //队满报错 return false; Q.data[Q.rear]=x; Q.rear=(Q.rear+1)%MaxSize; //队尾指针加1取模 return true; }
4⃣️ 出队
bool DeQueue(SqQueue &Q,ElemType &x) if(Q.rear==Q.front){ return false; x=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize; return true; }
bool DeQueue(SqQueue &Q,ElemType &x) if(Q.rear==Q.front){ return false; x=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize; return true; }
队列的链式存储结构
队列的链式存储
队列的链式表示称为链队列，它实际上是一个同时带有队列指针和队尾指针的单链表。
头指针指向队头节点。
尾指针指向队尾结点，即单链表的最后一个结点。
⚠️与顺序存储的不同。
队列的链式存储类型:
typedef struct{ //链式队列结点 ElemType data; struct LinkNode *next; }LinkNode; typedef struct{ //链式队列 LinkNode *front,*rear; //队列的对头和队尾指针 }LinkQueue;
typedef struct{ //链式队列结点 ElemType data; struct LinkNode *next; }LinkNode; typedef struct{ //链式队列 LinkNode *front,*rear; //队列的对头和队尾指针 }LinkQueue;
当Q.rear==NULL且Q.front==NULL时，链式队列为空。
出队入队操作
出队
首先判断队是否为空，若不空，则取出对头元素，将其从链表中删除，并让Q.front指向下一个结点。
若该队列为最后一个结点，则置Q.front和Q.rear都为NULL。
入队
建立一个新结点，将新结点插入到链表的尾部，并改让Q.rear指向这个新插入结点。
若原队列为空，则令Q.front也指向该结点。
不带头结点的链式存储比较麻烦，通常采用一个带头结点的链式队列，将插入和删除的操作统一。
单链表表示的队列适合用于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。
若要使用多个队列，多个栈，最好使用链式队列，就不会出现存储分配不合理和溢出问题。
链式队列的基本操作
1⃣️ 初始化
void InitQueue(LinkQueue &Q){ Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); Q.front->next=NULL;//初始为空 }
void InitQueue(LinkQueue &Q){ Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); Q.front->next=NULL;//初始为空 }
2⃣️ 判队空
bool IsEmpty(LinkQueue Q){ if(Q.front==Q.rear) return true; else return false; }
bool IsEmpty(LinkQueue Q){ if(Q.front==Q.rear) return true; else return false; }
3⃣️ 入队
bool EnQueue(LinkQueue &Q,ElemType x){ LinkNode *S=(LinkNode*)malloc(sizeof(LinkNode)); s->next=x; s->next=NULL; Q.rear->next=s; }
bool EnQueue(LinkQueue &Q,ElemType x){ LinkNode *S=(LinkNode*)malloc(sizeof(LinkNode)); s->next=x; //创建新的结点，插入到队尾 s->next=NULL; Q.rear->next=s; }
4⃣️ 出队
bool DeQueue(LinkQueue &Q,Elempty &x){ if(Q.front==Q.rear){ return false; LinkNode *p=Q.front->next; x=p->data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; //如果原队列只有一个结点则删除后变空 free(p); return true; }
bool DeQueue(LinkQueue &Q,Elempty &x){ if(Q.front==Q.rear){ return false; LinkNode *p=Q.front->next; x=p->data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; //如果原队列只有一个结点则删除后变空 free(p); return true; }
双端队列
是两端都可以进行入队和出队操作的队列。
其元素的逻辑结构依然是线性结构。
将队列的两端分别称为前端和后端，两端都可以入队和出队。
进队时
前端进的元素排列在队列中后端进的元素的前面
后端进的元素排列在队列中前端进的元素的后面
出队时
无论是前端还是后端出队，先出的元素排列在后出的元素的前面。
输出与输入受限的双端队列
输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列称为输出受限的双端队列。
输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列称为输入受限的双端队列。
若限定双端队列从某个端点端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相临接的栈（后进先出）。
栈和队列的应用
栈在括号匹配中的应用
算法思想
1⃣️ 初始设置一个空栈，顺序读入括号
2⃣️ 若是右括号，则或者使置于栈顶的最急迫期待得以消解，或者是不合法的情况（若括号序列不匹配，退出程序。
3⃣️ 若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性降了一级。
算法结束时，栈为空，否则不匹配。
栈在表达式求值中的应用
中缀表达式
后缀表达式
栈在递归中的应用
概念
若一个函数、过程或数据结构的定义又应用了它自身，则这个函数、过程或数据结构称为是递归定义的，简称递归。
递归减少了代码量但它的效率低。
包含很多的计算
在递归调用过程中，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储
递归次数过多容易造成栈溢出等。
优点：代码简单，易于理解。
斐波那契数列
递归模型需满足的条件
递归表达式（递归体）
边界条件（递归出口）
递归的关键在于能否将原始问题转换为属性相同但规模较小的问题。
可以将递归算法转换为非递归算法这需要借助栈来实现这种转换。
🤡对于一个问题的求解，非递归算法通常比递归算法高一些
递归算法中包含着许多重复的计算
🤡函数调用时需要一个栈存储
局部变量
调用返回值
实参
🤡🐉2013队列在层次遍历的利用
树的层次遍历
图的广度优先遍历
队列在计算机系统中的应用
数据缓冲区
CPU处理请求
特殊矩阵的压缩存储
串
串的定义和实现
串的匹配模式
图
图的基本概念
图的存储及基本操作
图的遍历
图的应用
查找
查找的基本概念
顺序查找和折半查找
B树和B+树
散列表