考研演算法

① 計算機考研：數據結構常用演算法解析(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/