【正文】 圖 18 圖課程設計流程圖 四、詳細設計 include define MAX_VERTEX_NUM 100 define INFINITY 99999 int map[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。 int n,e。 struct { int adjvex。 int lowcost。 }closedge[MAX_VERTEX_NUM]。 //構造連通圖 void LoadMap() { j？ 輸出最小樹 結束 j++ 新頂點并入后重新選擇最小邊 The genral stf(1mpoyidvc,uh)0jb。5wT27 int i,j,v,u,c。 for( i=1。i=n。i++) for( j=1。j=n。j++) map[i][j]=INFINITY。 for( i=1。i=e。i++) { scanf(%d%d%d,amp。u,amp。v,amp。c)。 map[u][v]=c。 map[v][u]=c。 } } //輸出生成樹的每條邊 void MiniSpanTree_PRIM() { int i,j,k,min,u。 u=1。 for( j=1。 j=n。 ++j) if( j!=u ) { closedge[j].adjvex = u。 closedge[j].lowcost = map[u][j]。 } closedge[u].lowcost = 0。 for( i=1。in。++i) { min = INFINITY。 for ( j=1。j=n。j++) { if( closedge[j].lowcost0 amp。amp。 closedge[j].lowcostmin ) The genral stf(1mpoyidvc,uh)0jb。5wT28 { k = j。 min = closedge[j].lowcost。 } } printf(%d%d\n,closedge[k].adjvex,k)。 closedge[k].lowcost = 0。 for( j=1。 j=n。 j++) if( map[k][j] closedge[j].lowcost ) { closedge[j].adjvex = k。 closedge[j].lowcost = map[k][j]。 } } } void main() { printf(圖 第 14 題 \n)。 printf(請輸入連通圖的頂點數(shù)目 : )。 scanf(%d,amp。n)。 printf(請輸入連通圖的邊的數(shù)目 : )。 scanf(%d,amp。e)。 printf(請依次輸入每條邊的兩個頂點名和權值 (頂點 _頂點 _權值 )(如： 1 2 5):\n)。 LoadMap()。 printf(最小生成樹所包括的邊如下 :\n)。 MiniSpanTree_PRIM()。 } 五、調試分析 調試結果 The genral stf(1mpoyidvc,uh)0jb。5wT29 圖 19 圖課程設計調試 結果 時間復雜度 普里姆算法的時間復雜度為 O( 2n )。 6 查找和排序 7題 編寫函數(shù)實現(xiàn)直接插入算法、希爾排序算法。 一、 數(shù)據結構說明 插入排序的主要操作是插入，其基本思想是：每次將一個待排序的元素按其大小插入到一個已經排好序的有序序列中，直到全部記錄排好序為止。 希爾排序 基本思想是：將整個待排序記錄分割成若干個子序列，在子序列內分別進行直接插入排序，待整個序列中的記錄基本有序時，對全體記錄進行直接插入排序。 二、 數(shù)組 存儲結構 設計 A[length] B[length] 三、算法設計（程序流程圖） The genral stf(1mpoyidvc,uh)0jb。5wT30 圖 20 直接插入排序流程圖 圖 21 希爾排序流程圖 四、詳細設計 include include define length 100 void InsertSort(int a[],int n) { int i,j,temp。 for(i=0。in1。i++) { temp=a[i+1]。 j=i。 while(j1amp。amp。tempa[j]) { a[j+1]=a[j]。 j。 } a[j+1]=temp。 } 開始 輸入數(shù)組 A[n] 通過直接插入排序 輸出有序數(shù)組A[n] 結束 開始 輸入數(shù)組 B[m] 通過希爾 排序 輸出有序數(shù)組B[m] 結束 The genral stf(1mpoyidvc,uh)0jb。5wT31 } void Shellsort(int A[], int N ) { int i,j,Increment。 int Tmp。 for (Increment=N/2。Increment0。 Increment/=2 ) /*h sequence */ for (i=Increment。iN。i++) { /* insertion sort */ Tmp=A[i]。 for (j=i。j=Increment。j=Increment) if(TmpA[jIncrement]) A[j]=A[jIncrement]。 else break。 A[j]=Tmp。 } /* end forI and forIncrement loops */ } void main() { int A[length],B[length]。 int i,j,n,m。 printf(排序和查找 第 7 題 \n)。 printf(元素個數(shù) n=)。 scanf(%d,amp。n)。 printf(輸入元素 \n)。 for(i=0。in。i++) { The genral stf(1mpoyidvc,uh)0jb。5wT32 scanf(%d,amp。A[i])。 } InsertSort(A,n)。 printf(通過直接插入排序后序列為： )。 for(i=0。in。i++) printf(%d ,A[i])。 printf(\n)。 printf(元素個數(shù) m=)。 scanf(%d,amp。m)。 printf(輸入元素 \n)。 for(i=0。im。i++) { scanf(%d,amp。B[i])。 } Shellsort(B,m)。 printf(通過希爾排序后序列為： )。 for(i=0。im。i++) printf(%d ,B[i])。 printf(\n)。 } 五、調試分析 調試結果 圖 23 排序和查找課程設計調試結果 The genral stf(1mpoyidvc,uh)0jb。5wT33 時間復雜度 直接插入排序的時間復雜度為 O( 2n )。 希爾排序的時間復雜度為 O( 2/3n )。 課程設計總結 數(shù)據結構是計算機專業(yè)的專業(yè)基礎課，它在教學計劃中的地位是承上啟下的核心課程，屬于武術中的“練功”科目。通過本次的數(shù)據結構課程設計讓我對本課程有了更深刻的認識， 掌握了基本的數(shù)據結構，對線性表、隊列和棧、二叉樹、圖等基本數(shù)據結構的基本操作有了更加深入的了解，提高了算法設計能力、程序設計能力和算法分析能力等，同時，我也發(fā)現(xiàn)了自己的一些不足，如指針的操作還不熟練，對一些問題的考 慮還不周全等，在往后的學習 中加以改進和彌補自己的不足之處。 參 考 文 獻 [1] 嚴蔚敏 ,吳偉民編 .數(shù)據結構 [M].北京 :清華大學出版社 ,2021.