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、因為後序遍歷棧中保留當前結點的祖先的資訊，用一變數儲存棧的最高棧頂指標，每當退棧時，棧頂指標高於儲存最高棧頂指標的值時，則將該棧倒入輔助棧中，輔助棧始終儲存最長路徑長度上的結點，直至後序遍歷完畢，則輔助棧中內容即為所求。

void longestpath(bitree bt)//求二叉樹中的第一條最長路徑長度

//沿左分枝向下

if(tag[top]==1) //當前結點的右分枝已遍歷

//保留當前最長路徑到l棧，記住最高棧頂指標，退棧

}else if(top>0) //沿右子分枝向下

}//while(p!=null||top>0)

}//結束longestpath