|
写在前面：本文写于吴签时期，在家备考时刷完数据结构王道书之后想着把书中重点梳理汇总一下。本文内容涵盖大部分王道数据结构每章的知识点及其课后习题所涉及的知识点，方便自己和有需要的人在没带书且无聊的时候可以看看。本人曾在大三期间打过一些程序设计类比赛，所以本文所涉及到的代码不一定局限于王道书，但思想都一样。
希望今年自己可以成功上岸瓜大，也祝各位读者一战成硕！
第一章：绪论（不在考研大纲但很重要）
- 数据结构三要素：逻辑结构、存储结构、数据的运算；其中逻辑结构包括线性结构（线性表、栈、队列）和非线性结构（树、图、集合）
- 数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。
- 数据元素是数据的基本单位，可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位，
- 数据对象是具有相同性质的数据元素的集合，是数据的一个子集
- 数据类型是一个值的集合和定义在此集合上的一组操作的总称
数据类型包括：原子类型、结构类型、抽象数据类型 - 数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括逻辑结构、存储结构和数据运算三方面内容
- 数据的逻辑结构和存储结构是密不可分的，算法的设计取决于所选定的逻辑结构，而算法的实现依赖于采用的存储结构
- 数据的存储结构主要有顺序存储、连式存储、索引存储和散列存储
- 施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤
- 在存储数据时，通常不仅要存储各数据元素的值，而且要存储数据元素之间的关系
- 对于两种不同的数据结构，逻辑结构或物理结构一定不同吗？
数据运算也是数据结构的一个重要方面。对于两种不同的数据结构，他们的逻辑结构和物理结构完全有可能相同（比如二叉树和二叉排序树） - 链式存储设计时，各个不同结点的存储空间可以不连续，但结点内的存储单元地址必须连续
- 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令包括一个或多个操作。
- 算法的五个特性：有穷性、确定性、可行性、输入、输出（字面意思，第一遍看的话建议看看书具体概念）
- 通常设计一个好的算法应考虑：正确性、可读性、健壮性、效率与低存储量需求
- 算法的时间复杂度不仅依赖于问题的规模n，也取决于待输入数据的性质
- 若输入数据所占空间只取决于问题本身而和算法无关，则只需分析除输入和程序之外的额外空间
- 算法原地工作是指算法所需辅助空间为常量，即O(1)
- 一个算法应该是问题求解步骤的描述
- 所谓时间复杂度，是指最欢情况下估算算法执行时间的一个上界
- 同一个算法，实现语言的级别越高，执行效率越低
第二章：线性表
- 线性表是具有相同数据类型的n个数据元素的有限序列。
- 线性表特点：表中元素个数有限；表中元素具有逻辑上的顺序性；表中元素都是数据元素；表中元素的数据类型都相同，即每个元素占有相同大小存储空间；表中元素具有抽象性，即仅讨论元素间的逻辑关系而不考虑元素究竟表示什么内容
- 线性表是一种逻辑结构，表示元素之间一对一的相邻关系。其顺序存储：顺序表；其链式存储：单链表、双链表、循环链表、静态链表。
- 线性表的顺序存储又称顺序表，特点是表中元素的逻辑顺序与其物理顺序相同。
- 线性表的顺序存储结构是一种随机存取的存储结构，通常用高级设计语言中的数组来描述线性表的顺序存储结构（线性表中元素位序从1开始）
- 顺序表最主要特点是随机访问。它的存储密度高，每个结点只存储数据元素，插入和删除操作需要移动大量元素
- 顺序表插入,删除和查找时间复杂度均为O(n)
- 头指针和头结点区分：不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息
- 采用头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的，每个结点插入时间为O(1)一共为O(n)
- 尾插法必须增加一个尾指针使其始终指向当前链表的尾结点
- 双链表中的按值查找和按位查找的操作与单链表相同，但双链表在插入和删除操作的实现上时间复杂度仅为O(1)
- 循环单链表中没有指针域为NULL的结点，故循环单链表的判空条件为它是否等于头指针
- 有时对单链表常做的操作是在表头和表尾进行的，此时对循环单链表不设头指针而仅设尾指针
- 在循环双链表L中，某结点*p为尾结点时，p->next==L;当循环双链表为空表时，其头结点的prior域和next域都等于L
- 静态链表借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，这里的指针是结点的相对地址（数组下标）
- 静态链表以next==-1作为其结束的标志
- 通常较稳定的线性表选择顺序存储，而频繁进行插入、删除操作的线性表宜选择链式存储
- 链式存储结构比顺序存储结构能更方便地表示各种逻辑结构
- 顺序存储方式不仅能用于存储线性结构，也可以用于非线性（树和图）
- 若用单链表来表示队列，这应该选用带尾指针的循环链表
- 给定n个元素的一维数组，建立一个有序单链表最低时间复杂度为O(nlogn)
- 单链表中，增加一个头结点的目的是方便运算的实现
- 与单链表相比，双链表的优点之一是访问前后相邻结点更灵活
- 某线性表用带头结点的循环单链表存储，头指针为head，当head->next->next=head时，线性表长度可能是0或1
第三章：栈和队列
- 栈是只允许在一端进行插入和删除操作的线性表，操作特性可以明显的概括为后进先出
- n个不同元素进栈，出栈元素不同排列的个数为C(n:2n)/n+1，即卡特兰数
- 栈是一种操作受限的线性表，类似于线性表，它也有对应的两种存储方式
- 采用顺序存储的栈称为顺序栈；栈空：S.top==-1;栈满：S.top==MaxSize-1；栈长：S.top+1
- 由于顺序栈的入栈操作受数组上界的约束，有可能发生栈上溢
下面是顺序栈上常用的基本运算的实现
1.初始化
void InitStack(SqStack &S){
S.top=-1;
}
2.栈判空
bool 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; return true;
}
4.出栈
bool Pop(SqStack &S,ElemType &x){
if(S.top==1) return false;
x=S.data[S.top--];
return true;
}
5.读栈顶元素
bool GetTop(SqStack S,ElemType &x){
if(S.top==-1) return false;
x=S.data[S.top];
return true;
}
- 利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸
- 采用连式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况，通常采用单链表实现
- 栈和队列具有相同的逻辑结构，他们都属于线性表，但是运算不同
- 队列简称队，也是一种操作受限的线性表，队尾插入队头删除，操作特性为先进先出
- 队列的顺序存储，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置
- 循环队列队空：Q.front==Q.rear ； 队满(Q.rear+1）%MaxSize == Q.front；
循环队列的操作
1.初始化
void InitQueue(SqQueue &Q){
Q.rear=Q.front=0;
}
2.判队空
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;
return true;
}
4.出队
bool DeQueue(SqQueue &Q,ElemType &x){
if(Q.rear==Q.front) return fasle;
x=Q.data[Q.front];
Q.front=(Q.front+1)%MaxSize;
return true;
}
- 队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。当Q.front== NULL且Q.rear==NULL时，链表队列为空
- 通常将链式队列设计成一个带头结点的单链表
链式队列的基本操作
1.初始化
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;
}
3.入队
void EnQueue(LinkQueue &Q,ElemType x){
LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
s->data=x; s->next=NULL;
Q.rear->next=s; Q.rear=s;
}
4，出队
bool DeQueue(LinkQueue &Q,ElemType &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;
}
- 用链式存储方式的队列进行删除操作时头尾指针可能都要修改
- 递归必须满足两个条件：递归表达式；边界条件
- 队列在层序遍历的应用：根结点入队；若队空则结束遍历，否则重复下一步操作；队列中的第一个结点出队并访问，若有左孩子则左孩子入队，若有右孩子则右孩子入队，返回上一步
- 队列在计算机系统中的作用：第一个方面是解决主机与外部设备之间速度不匹配的问题（缓冲区），第二个方面是解决由多用户引起的资源竞争的问题（请求资源队列）
- 页面置换算法（此为OS内容）用到了队列
- 压缩矩阵：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间
- 特殊矩阵：指具有许多相同矩阵元素或零元素（对称矩阵，上下三角矩阵，对角矩阵）
- 对n阶对称矩阵压缩存储时，需要表长为n（n+1）/2的顺序表
- 二维数组计算地址（行优先）LOC(i,j)=LOC(0,0)+(i*m+j)*L
- 三元组表的结点存储了行、列、值三种信息，是主要用来存储稀疏矩阵的一种数据结构
- 十字链表将行单链表和列单链表结合起来存储稀疏矩阵
- 二叉链表又名左孩子右兄弟表示法，可用来表示树或森林
第四章：串（重点为KMP，但统考通常不考）
- 字符串简称串，串由零个或多个字符组成的有限序列
- 串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为字符集
- 串的存储结构：定长顺序存储表示、堆分配存储表示、块链存储表示
- 子串的定位操作通常称为串的模式匹配，它求的是子串在主串中的位置。
暴力匹配算法：
int Index(SString S,SString T){
int i=1,j=1;
while(i<=S.length&&j<=T.length){
if(S.ch[i]==T.ch[i]){
++i; ++j;
}
else{ i=i-j+2; j=1;}
}
if(j>T.length) return i-T,length;
else return 0;
}
KMP算法：（非王道代码）
求Next数组：
for(int i=2,j=0;i<=m;i++)
{
while(j&&p[i]!=p[j+1]) j=ne[j];
if(p[i]==p[j+1]) j++;
ne[i]=j;
}
for(int i=1,j=0;i<=n;i++)
{
while(j&&s[i]!=p[j+1]) j=ne[j];
if(s[i]==p[j+1]) j++;
if(j==m)
{
j=ne[j];
}
}
第五章：树与二叉树
- 树是n个结点的有限集，当n=0时，称为空树。
- 树是一种递归的数据结构，树作为一种逻辑结构同时也是一种分层的结构
- 结点的深度是从根开始自顶向下累加；结点的高度是从叶结点自底向上累加
- 由于树中的分支是有向的，即从双亲指向孩子，所以树中的路径是从上向下的，同一双亲的两个孩子之间不存在路径
- 树的结点数等于所有结点度数和加1
- 度为m的树中第i层上至多有pow(m,i-1)个结点
- 高度为h的m叉树至多有pow(m,h)-1/(m-1)个结点
- 树的路径长度是从树根到每个结点的路径长度的总和
- 二叉树是有序树，二叉树可以为空
- 一颗高度为h且含有pow(2,h)-1个结点的二叉树为满二叉树，每层结点为pow(2,h-1)
- 完全二叉树叶子结点只可能出现在最大的两层上；若有度为1的结点只可能有一个且在左孩子上
- 非空二叉树上的叶子结点数等于度为2的结点数加1，即n0=n2+1
- 具有n个结点的完全二叉树的高度为log(n+1)或logn+1
- 二叉树的遍历分为先序、中序、后序遍历
1.先序遍历
void PreOrder(BiTree T){
if(T!=NULL){
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
2.中序遍历
void PreOrder(BiTree T){
if(T!=NULL){
PreOrder(T->lchild);
visit(T);
PreOrder(T->rchild);
}
}
3.后序遍历
void PreOrder(BiTree T){
if(T!=NULL){
PreOrder(T->lchild);
PreOrder(T->rchild);
visit(T);
}
}
时间复杂度、空间复杂度均为O(n)
- 二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到，因此线索化的实质是遍历一次二叉树
- 引入线索二叉树的目的是加快查找结点的前驱或后驱的速度
- 树转二叉树：在兄弟结点之间加一连线；对每个结点只保留它与第一个孩子的连线；以树根为轴心顺时针旋转45°
- 二叉排序树的非递归查找算法
BSTNode *BST_Search(BiTree T,ElemType key){
while(T!=NULL&&key!=T->data){
if(key<T->data) T=T->lchild;
else T=T->rchild;
}
return T;
}
- 二叉排序树的插入
int BST_Insert(BiTree &T,KeyType k){
if(T==NULL){
T=(BiTree)malloc(sizeof(BSTNode));
T->key=k;
T->lchild=T->rchild=NULL;
return 1;
}
else if(k==T->key) return 0;
else if(k<T->key)
return BST_Insert(T->lchild,k);
else
return BST_Insert(T->rchild,k);
}
- 二叉排序树的构造
void Creat_BST(BiTree &T,KeyType str[],int n){
T=NULL;
int i=0;
while(i<n){
BST_Insert(T,str[i]);
i++;
}
}
-
二叉排序树的删除：若为叶节点则直接删除；若只有左或右则让子树代替；若有左和右则在右孩子找中序第一个填补 -
从树的根到任意结点的路径长度与该结点上权值的乘积称为该节点的带权路径长度 -
树中所有叶节点的带权路径长度和称为该树的带权路径长度 -
构造哈夫曼树的过程共新建了n-1个结点，因此哈夫曼树的结点总数为2n-1 -
在二叉排序树中进行查找的效率与二叉排序树的深度有关
第六章：图
- 线性表、树都可以为空，但图不可以是空图。顶点一定非空，边集可以为空
- 不存在重复边且不存在顶点到自身的边则为简单图
- 在有向图中任意一对顶点都是强连通的（有路径），则为强连通图
- 连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点为n，则它的生成树含有n-1条边
- 在路径系列中，顶点不重复出现的路径称为简单路径
- 除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路
- 邻接多重表是无向图的存储结构，十字链表是有向图的存储结构
1.广度优先搜索
bool visited[MAX_VERTEX_NUM];
void BFSTraverse(Graph G){
for(i=0;i<G.vexnum;i++) visited[i]=FALSE;
InitQueue(Q);
for(i=0;i<G.vexnum;i++)
if(!visitde[i]) BFS(G,i);
}
void BFS(Graph G,int v){
visit(v);
visited[v]=TRUE;
Enqueue(Q,v);
while(!isEmpty(Q)){
DeQueue(Q,v);
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
{
if(!visited[w]){
visit(w);
visited[w]=TRUE;
EnQueue(Q,w);
}
}
}
2.BFS求解单源最短路
void BFS_MIN_Distance(Graph G,int u){
for(i=0;i<G.vexnum;i++) d[i]=inf;
visited[u]=TRUE; d[u]=0;
EnQueue(Q,u);
while(!isEmpty(Q)){
DeQueue(Q,u);
for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))
if(!visited[w]){
visited[w]=TRUE;
d[w]=d[u]+1;
EnQueue(Q,w);
}
}
}
3.深度优先搜索
bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G){
for(v=0;v<G.vexnum;v++) visited[v]=FALSE;
for(v=0;v<G.vexnum;v++)
if(!visited[v]) DFS(G,v);
}
void DFS(Graph G,int v){
visit(v);
visited[v]=TRUE;
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
if(!visited[w]) DFS(G,w);
}
4.最小生成树
GENERIC_MST(G){
T=NULL;
while T 未形成一颗生成树；
do 找到一条最小代价边(u,v)并且加入T后不会产生回路；
T=T U (u,v);
}
5.Prim算法
void Prim(G,T){
T=NULL;
U={w};
while(V!=U){
设(u,v)是使u∈U与v∈(V-U),且最小权值的边;
T=T∪{(u,v)};
U=U∪{v};
}
}
6.Kruskal
void Kruskal(V,T){
T=V;
numS=n;
while(numS>1){
从E中取出权值最小的边(v,u);
if(v和u属于T中不同的连通分量){
T=T∪{(v,u)};
numS--;
}
}
}
7.Dijkstra（非王道代码，很久之前写的朴素算法）
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int dist[N],g[N][N],n,m;
bool st[N];
int dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<n-1;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
if(!st[j]&&(t==-1||dist[j]<dist[t]))
t=j;
st[t]=true;
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
if(dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
memset(g,0x3f,sizeof g);
cin>>n>>m;
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
}
cout<<dijkstra();
}
8.Floyd(非王道代码)
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][j]>dis[i][k]+dis[k][j]){
dis[i][j]=dis[i][k]+dis[k][j];
9.拓扑排序
bool TopoLogicalSort(Graph G){
InitStack(S);
for(int i=0;i<G.vexnum;i++)
if(indegree[i]==0) Push(S,i);
int count=0;
while(!isEmpty(S)){
Pop(S,i);
print[count++]=i;
for(p=G.vertices[i].firstarc;p;p=p->nextarc){
v=p->adjvex;
if(!(--indegree[v])) Push(S,v);
}
}
if(count<G.vexnum) return false;
else return true;
}
第七章：查找
- 用于查找的数据集合称为查找表，它由同一类型的数据元素组成，可以是一个数组或链表等数据类型
- 项目2
- 项目3
第八章：排序
|