考研算法

① 计算机考研：数据结构常用算法解析(7)

第七章：
对于无向图，e的范围是：
数据结构中所讨论的图都是简单图，任意两结点间不会有双重的边。
对于有向图，e的范围是：
图的各种存储结构
邻接矩阵很方便访问任意两点的边，但是不方便计算其邻接点。在深度和广度遍历中广泛的需要求某点的邻接点。所以邻接矩阵只在Floyed和Prim和Dijstra中采用。
邻接表能很方便的求某顶点的邻接点，索引对于与遍历有关的算法大多都采用邻接表。如深度、广度、拓扑排序、关键路径。但他也有不足的地方，就是不方便求入度或是那些薯早握点可以到他的操作。所以有人引进逆邻接表。最后人们把这两种表结合到一起就是十字链表和邻接多重表。一个是存储有向图，另一个是存储无向图。
在十字链睁历表和邻接多重表很方便求邻接点的操作和对应的逆操作。所以实际应用中，凡是能用邻接表实现的一定能用十字链表和邻接多重表实现。并且它们的存储效率更高。
1.邻接矩阵(有向图和无向图和网)又称为数组表示法
typedef struct
{ vextype vexs[maxn]; ∥顶点存储空间∥
adjtype A[maxn][maxn]; ∥邻接矩阵∥
int vexnum,arcnum; //图的顶点数和边数
GraphKind Kind; //图的类型
} mgraph;
2.邻接表(有向图和无向图和网)
typedef struct node ∥边
{ int adj; int w; ∥邻接点、权∥
struct node *next; ∥指向下一弧或边∥
}linknode;
typedef struct ∥顶点类型∥
{ vtype data; ∥顶点值域∥
linknode *farc; ∥指向与本顶点关联的第一条弧或边∥
}Vnode;
typedef struct
{
Vnode G[maxn]; ∥顶点表∥
int vexnum,arcnum;
GraphKind kind;
}ALGraph;
adjvexnextarcinfo
边结点
datafirstarc
顶点结点
3.十字链表(有向图和有向网)
headvextaivexhlinktlinkinfo
边结点
datafirstinfirstout
顶点结点
4.邻接多重表(无向图)
markivexjvexilinkjlinkinfo
边结点
datafirstedge
顶点结点
有向无环图(DAG)：是描述含有公共子式的表达式的有效工具。二叉树也能表示表达式，但是利用有向无环图可以实现对相同子式的共享，从而节省存储空间。
顶点的度：
无向图：某顶点V的度记为D(V)，代表与V相关联的边的条数
有向图：顶点V的度D(V)=ID(V)+OD(V)
强连通分量:在有向图中，若图中任意两顶点间都存在路径，则称其是强连通图。图中极大 强连通子图称之为强连通分量
“极大”在这里指的是：往一个连通分量中再加入顶点和边，就构不成原图中的一个 连通子图，即连通分量是一个最大集的连通子图。有向图的连通就是指该有向图是强连通的。

考研有疑问、不知道如何总结考研考点内容、不清楚数庆考研报名当地政策，点击底部咨询官网，免费领取复习资料：https://www.87dh.com/xl/

② 考研<<数据结构>>哪些算法比较重要是不是严的那本书上所有的算法都要掌握!

不是！
★计算机研究生法的考察主要以线性表 +排序（结合）为主 排序（结合）为主 排序（结合）为主 ,其 他知识算法只要求理解，不会在考研试中出现。之是 他知识算法只要求理解，不会在考研试中出现。之是 他知识算法只要求理解，不会在考研试中出现。之是 以线性表 +排序知识为依托，更重要的是考察算法思想 排序知识为依托，更重要的是考察算法思想 。你是 。你是 怎样用线性表 +排序解决问题的，思 想对了才能拿工具做。而排序解决问题的，思 想对了才能拿工具做。而排序解决问题的，思 想对了才能拿工具做。而想的融会贯通则是建 立在对线性表 +排序知识的熟练程度上 。所 以建议多做这方面的工作，在熟练掌握线性表 以建议多做这方面的工作，在熟练掌握线性表 +排序知识的基础 上，多锻炼算法的思想。
★数据结构：小题目理 数据结构：小题目理 数据结构：小题目理 数据结构：小题目理 数据结构：小题目理 数据结构：小题目理 数据结构：小题目理 数据结构：小题目理 数据结构：小题目理 解知识最重要；大题目图 解知识最重要；大题目图 解知识最重要；大题目图 解知识最重要；大题目图 解知识最重要；大题目图 解知识最重要；大题目图 解知识最重要；大题目图 解知识最重要；大题目图 解知识最重要；大题目图 解知识最重要；大题目图 解知识最重要；大题目图 /查找 和算法， 算法最重要。中，思想只正确程 算法最重要。中，思想只正确程 算法最重要。中，思想只正确程 算法最重要。中，思想只正确程 算法最重要。中，思想只正确程 序写，基本上就能得到 一半以的分数。当然在考场想序写，基本上就能得到 一半以的分数。当然在考场想序写，基本上就能得到 一半以的分数。当然在考场想的方法 就是最好， 时间复杂度和空能最优好不能就写想到的 。所以 。所以 数据结构的 复习，最重要是算法思想数据结构的 复习，最重要是算法思想训

③ 2015考研：计算机数据结构常用算法（9）

第九章内部排序(在内存中进行的枝银排序不需要访问外存的)外部排序(排序量很大，过分批的读写外存，最终完成排序)
稳定排猛猛宴序和非稳定排序：看相同记录的相对次序是否回发生改变。主要看在排序过程中的比较是不是相邻记录，如果是相知衡邻比较，一定是稳定的排序。如果不是相邻的比较，就是不稳定的。
内排序方法 截止目前，各种内排序方法可归纳为以下五类：
(1)插入排序(2)交换排序(3)选择排序(4)归并排序 (5)基数排序。
插入排序：包括直接插入排序和希尔排序
直接插入排序：(稳定的)
算法描述
void Insort (sqList &L) ∥对顺序文件F直接插入排序的算法∥
int i,j
for (i=2i<=L.leni++) ∥插入n-1个记录∥

if(L.R[i].key
L.R[0]=L.R[i] ∥待插入记录先存于监视哨∥
L.R[i]=L.R[i-1]
for(j=i-2L.R[0].key
L.R[j+1]=L.R[j] ∥记录顺序后移∥
L.R[j+1]=L.R[0] ∥原R[i]插入j+1位置∥

算法分析
设排序中key比较次数为C，C最小时记为Cmin，最大时记为Cmax。
(1)当原来就有序(正序)时，每插入一个R[i]只需比较key一次，即：
(2)当原本逆序(key从大到小)时，每插入一个R[i]要和子表中i-1个key比较，加上同自身R[0]的比较，此时比较次数最多，即：
(3)记录总的移动次数m(m最小时记为mmin，最大时记为mmax)
正序时，子表中记录的移动免去，即：
逆序时，插入R[i]牵涉移动整个子表。移动次数为2+(i-1)=i+1，此时表的移动次数最大，即：
排序的时间复杂度取耗时最高的量级，故直接插入排序的T(n)=O(n2)。
Shell(希尔)排序又称“缩小增量”排序(不稳定的)
交换类的排序：(起泡排序和快速排序)
起泡排序算法描述
void Bubsort (sqList &L)
int i,flag ∥flag为记录交换的标记∥
Retype temp
for (i=L.leni>=2i--) ∥最多n-1趟排序∥
flag=0 //记录每一趟是否发生了交换
for (j=1j<=i-1j++) ∥一趟的起泡排序∥
if (L.R[j].key>L.R[j+1].key) ∥两两比较∥
temp=L.R[j] ∥R[j] Û R[j+1]∥
L.R[j]=L.R[j+1]
L.R[j+1]=temp
flag=1

if (flag==0) break ∥无记录交换时排序完毕∥

算法分析
设待排长度为n，算法中总的key比较次数为C。若正序，第一趟就无记录交换，退出循环，Cmin=n-1=O(n)若逆序，则需n-1趟排序，每趟key的比较次数为i-1(2&lei&len)，故：
同理，记录的最大移动次数为：
故起泡排序的时间复杂度T(n)=O(n2)。并且是稳定的。
快速排序：(不稳定的，时间复杂度O(nlogn))，不需要辅助空间，但有最好和最差之分
分割算法
int Partition(Sqlist&L,int low,int high)
L.R[0]=L.R[low]
pivotkey=L.R[low].key
while(low
while(low=pivotkey)
--high
L.R[low]=L.R[high]
while(low
++low
L.R[high]= L.R[low]

return low

总控函数：
void QSort(Sqlist&L,int low,int high)
if(low

pivotloc=Partition(L,low,high)
QSort(L,low,pivotloc-1)
QSort(L,pivotloc+1,high)

调用方法：QSort(L,1,L,lenght)
算法分析：
若 原本就正序或逆序，每次调用一次后，记录数只减少了一个，故此时T(n)=C(n+(n-1)+……+1)=O(n2)。这是快速排序效率最差的情况。所以快速排序算法有待改进。
简单选择排序： 属于稳定排序时间复杂度(O(n2))
算法描述
void Slectsort (Sqlist& L) ∥直接选择排序的算法∥

for (i=1i

j=SeloctMinkey(L,i) //从i到L.len中选择key最小的记录
if (i!=j)
temp=L.R[i]
L.R[i]=L.R[j]
L.R[j]=temp

堆排序：属于选择排序 不稳定，时间复杂度(O(nlogn))，没有最好和最差的分别，也需 要辅助的栈空间
若ki&gek2i、ki&gek2i+1。此时，根结点k1的值最大，称为“大根堆”。
若ki&lek2i、ki&lek2i+1满足“”关系，则k1最小，称为“小根堆”。
在堆排序中，我们采用的是大根堆，原因是大根堆中，根最大，对删除很方便，直接把它与最后一个叶子结点交换就可以了。
记录key集合k=k1 k2……kn， 排序 分两步进行：
(1)将k1 k2……kn建成一个大根堆
(2)取堆的根(key最大者)，然后将剩余的(n-1)个key又调整为堆，再取当前堆
的根(key次大者)，……，直到所有key选择完毕。
一个元素的堆调整算法：
//已知H.R[s...m]除H.R[s]之外，均满足堆的定义，本函数只是将H.R[s]放到已经是堆的堆中
void HeapAdjust (SqList& H, int s, int m) ∥将(H.R[s]……H.R[m])调整成大根堆∥

rc=H.R[s] ∥暂存H.R[s]∥
for(j=2sj<=m j=2 )//沿key较大的孩子结点向下筛选

if (jL.R[j].key) j++ ∥令j为s的左右孩子key最大者的序号
if (rc.key>L.R[j].key)
break//说明H.R[s]已经比当前堆中的所有元素大，已经是堆了，不需要调整了
L.R[s]=L.R[j] ∥把最大的放到根结点
s=j ∥把s与j交换，使得s与下层的堆比较

L.R[s]=rc ∥最初的根回归∥

void Heapsort (SqList& H) ∥ 堆排序算法∥

//初始建堆
for (i=L.len/2 i>=1 i--) //从完全二叉树的最后一个非叶子结点开始
HeapAdjust (L,i,L.len) ∥调整(R[i]……R[n])为堆∥
//每次取下根(最大的元素)所谓的取下，只是放到数组最后，改变一下数组的下界
for (i=L.leni>=2i--) ∥总共摘n-1次∥
temp=F.R[1] ∥根与当前最后一个结点互换∥
F.R[1]=F.R[i]
F.R[i]=temp
HeapAdjust (L ,1,i-1) ∥把最后一个元素调整到合适的位置∥

二路归并排序：(稳定的，时间复杂度O(nlogn)又稳定又效率高，但需要辅助空间TR[1....n]
二路归并得核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列
(注意这就是线型表中我们常考的那个，两个有序链表合成一个新的有序表)
算法描述如下：
void Merge(RcdType SR[],RcdType&TR[],int i,int m,int n)
//将有序的SR[i...m]和SR[m+1....n]归并为有序的TR[i....n]

for(j=m+1,k=i i<=m&&j<=n ++k) //谁小就先将谁放进TR
if(SR[i].key<=SR[j].key)
TR[k]=SR[i++]
else
TR[k]=SR[j++]

if(i<=m) //将剩余的SR 直接放到TR
TR[k....n]=SR[i...m]
if(j<=n) //将剩余的SR 直接放到TR
TR[k...n]=SR[j....n]

void MSort(RcdType SR[], RcdType&TR1[], int s, int t)
//将SR[s...t]归并排序为TR1[s...t]
if(s= =t) //只有一个元素
TR1[s]=SR[s]
else

m=(s+t)/2//将SR[]平分为两半
MSort(SR, TR2, s, m)
MSort(SR, TR2, m+1, t)
Merge(TR2, TR1, s, m, t)

以上就是第9章节有关数据结构算法，希望考生对于这些算法能够熟记于心，方便考试的应用和日后的实际操作。最后，猎考考研祝大家考试成功!
推荐阅读：
2015考研：计算机数据结构常用算法汇总

考研有疑问、不知道如何总结考研考点内容、不清楚考研报名当地政策，点击底部咨询官网，免费领取复习资料：https://www.87dh.com/xl/