2023年雲南省資料總結深入

1、有乙個帶頭結點的單鏈表，每個結點包括兩個域，乙個是整型域info，另乙個是指向下乙個結點的指標域next。假設單鏈表已建立，設計演算法刪除單鏈表中所有重複出現的結點，使得info域相等的結點只保留乙個。

#include

typedef char datatype;

typedef struct node listnode;

typedef listnode* linklist;

/* 刪除單鏈表中重複的結點 */

linklist deletelist(linklist head)

else

p=p->next;

}return head;

}2、連通圖的生成樹包括圖中的全部n個頂點和足以使圖連通的n-1條邊，最小生成樹是邊上權值之和最小的生成樹。故可按權值從大到小對邊進行排序，然後從大到小將邊刪除。每刪除一條當前權值最大的邊後，就去測試圖是否仍連通，若不再連通，則將該邊恢復。

若仍連通，繼續向下刪；直到剩n-1條邊為止。

void spntree (adjlist g)

//用「破圈法」求解帶權連通無向圖的一棵最小代價生成樹。

node; //設頂點資訊就是頂點編號，權是整型數

node edge;

scanf( "%d%d",&e,&n) ; //輸入邊數和頂點數。

for (i=1;i<=e;i輸入e條邊：頂點，權值。

scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);

for (i=2;i<=e;i++) //按邊上的權值大小，對邊進行逆序排序。

//for

k=1; eg=e;

while (eg>=n破圈，直到邊數e=n-1.

//測試下一條邊edge[k]，權值置0表示該邊被刪除k++; //下條邊

}//while

}//演算法結束。

connect()是測試圖是否連通的函式，可用圖的遍歷實現，

3、設有乙個陣列中存放了乙個無序的關鍵序列k1、k2、…、kn。現要求將kn放在將元素排序後的正確位置上，試編寫實現該功能的演算法，要求比較關鍵字的次數不超過n。

51. 借助於快速排序的演算法思想，在一組無序的記錄中查詢給定關鍵字值等於key的記錄。設此組記錄存放於陣列r[l..

h]中。若查詢成功，則輸出該記錄在r陣列中的位置及其值，否則顯示「not find」資訊。請編寫出演算法並簡要說明演算法思想。