|
写在前面：本文写于吴签时期，在家备考时刷完数据结构王道书之后想着把书中重点梳理汇总一下。本文内容涵盖大部分王道数据结构每章的知识点及其课后习题所涉及的知识点，方便自己和有需要的人在没带书且无聊的时候可以看看。本人曾在大三期间打过一些程序设计类比赛，所以本文所涉及到的代码不一定局限于王道书，但思想都一样。 希望今年自己可以成功上岸中南财，也祝各位读者一战成硕！
期末复习和备考408均可使用
第一章：绪论（不在考研大纲但很重要）第二章：线性表第三章：栈和队列第四章：串（重点为KMP，但统考通常不考）第五章：树与二叉树第六章：图第七章：查找第八章：排序
第一章：绪论（不在考研大纲但很重要）
数据结构三要素：逻辑结构、存储结构、数据的运算；其中逻辑结构包括线性结构（线性表、栈、队列）和非线性结构（树、图、集合）数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位，可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位，数据对象是具有相同性质的数据元素的集合，是数据的一个子集数据类型是一个值的集合和定义在此集合上的一组操作的总称 数据类型包括：原子类型、结构类型、抽象数据类型数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括逻辑结构、存储结构和数据运算三方面内容数据的逻辑结构和存储结构是密不可分的，算法的设计取决于所选定的逻辑结构，而算法的实现依赖于采用的存储结构数据的存储结构主要有顺序存储、连式存储、索引存储和散列存储施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤在存储数据时，通常不仅要存储各数据元素的值，而且要存储数据元素之间的关系对于两种不同的数据结构，逻辑结构或物理结构一定不同吗？ 数据运算也是数据结构的一个重要方面。对于两种不同的数据结构，他们的逻辑结构和物理结构完全有可能相同（比如二叉树和二叉排序树）链式存储设计时，各个不同结点的存储空间可以不连续，但结点内的存储单元地址必须连续算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令包括一个或多个操作。算法的五个特性：有穷性、确定性、可行性、输入、输出（字面意思，第一遍看的话建议看看书具体概念）通常设计一个好的算法应考虑：正确性、可读性、健壮性、效率与低存储量需求算法的时间复杂度不仅依赖于问题的规模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
++i; ++j;
}
else{ i=i-j+2; j=1;}
}
if(j>T.length) return i-T,length;
else return 0;
}
KMP算法：（非王道代码）
求Next数组：
//s[]是模式串，p[]是模板串，n是s的长度，m是p的长度
for(int i=2,j=0;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(keydata) 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(kkey)
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
for(i=0;i
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
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
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
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
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
for(int j=1;j
dis[i][j]=dis[i][k]+dis[k][j];
9.拓扑排序
bool TopoLogicalSort(Graph G){
InitStack(S);
for(int i=0;i
v=p->adjvex;
if(!(--indegree[v])) Push(S,v);
}
}
if(count
mid=(low+high)/2;
if(L.elem[mid]==key) return mid;
else if(L.elem[mid]>key) high=mid-1;
else low=mid+1;
}
return -1;
}
因为折半查找需要方便地定位查找区域，所以它要求线性表必须具有随机存取的特性，因此该查找法仅适合于顺序存储结构，不适合链式存储结构且要求元素按关键字顺序排列分块查找又称索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有动态结构又适用于快速查找分块查找要求块内可无序，但块间有序，块间可以对各块的关键字建立一个索引表分块查找分为两步：第一步是在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表；第二步是在块内顺序查找B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示B树所有的叶节点都出现在用一层次上，并且不带信息B树是所有结点的平衡因子均等于0的多路平衡查找树在B树查找包含两个基本操作：在B树中找结点；在结点内找关键字；前一个是在磁盘上进行，后一个操作在内存中进行（顺序或折半）散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr(这里的地址可以是数组下标、索引表或内存地址)散列表：根据关键字而直接进行访问的数据结构。也就是说散列表建立了关键字和存储地址之间的一种直接映射关系散列函数构造方法：
散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围 2）散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中，从而减少冲突的发生 3）散列函数应尽量简单，能够在较短的时间内计算出任一关键字对应的散列地址
散列函数：直接定址法、除留余数法、数字分析法、平方取中法散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子
第八章：排序
在排序过程中，根据数据元素是否在内存中，可以将排序算法分为内部排序和外部排序通常将排序算法分为插入排序、交换排序、选择排序、归并排序和基数排序五大类插入排序基本思想是每次将一个待排序记录按其关键字大小插入前面已排好序的子序列直到全部记录插入完成，可以引申为：直接插入排序、折半插入排序、希尔排序直接插入排序算法：时间复杂度为O(n2)；空间复杂度O(1);稳定算法；适用于顺序存储和链式存储的线性表
void InsertSort(ElemType A[],int n){
int i,j;
for(i=2;i
int i,j,low,high,mid;
for(i=2;i
mid=(low+high)/2;
if(A[mid]>A[0]) high=mid-1;
else low=mid+1;
}
for(j=i=1;j>=high+1;--j)
A[j+1]=A[j];
A[high+1]=A[0];
}
}
希尔排序又称缩小增量排序，基本思想为：先将待排序表分割成若干形如L[i,i+d,i+2d,…,i+kd]的“特殊”子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序
void ShellSort(ElemType A[],int n){
for(dk=n/2;dk>=1;dk=dk/2)
for(i=dk+1;i
for(i=0;i
swap(A[j-1],A[j]);
flag=true;
}
if(flag==false) return;
}
}
快速排序:空间复杂度为O(n)；时间复杂度为O(nlogn);不稳定
void QuickSort(ElemType A[],int low,int high){
if(low
for(i=0;i |