1、中北大學數據結構與算法課程設計說 明 書 學 院、系：軟件學院專 業：軟件工程學 生 姓 名：xx學 號：xxx設 計 題 目：最小生成樹問題 起 迄 日 期:2021年12月9日- 2021年12月20日指 導 教 師:李波   2021 年12月 20 日1 需求分析 設計內容：給定一個地區的n個城市間的距離網，用prim算法或kruskal算法建立最小生成樹，并計算得到的最小生成樹的代價。 基本要求：（1）城市間的距離網采用鄰接矩陣表示，鄰接矩陣的存儲結構定義采用課本中給出的定義，若兩個城市之間不存在道路，則將相應邊的權值設為自己定義的無窮大值。要

2、求在屏幕上顯示得到的最小生成樹中包括了哪些城市間的道路，并顯示得到的最小生成樹的代價；（2）表示城市間距離網的鄰接矩陣（要求至少6個城市，10條邊）；（3）最小生成樹中包括的邊及其權值，并顯示得到的最小生成樹的代價。 2本設計所采用的數據結構 本程序設計所采用的數據結構為圖。3 設計思想 普里姆算法4 核心代碼int main() /主函數 mgraph g; vertextype u; int k; createUDN(&g); /* 生成鄰接矩陣結構的圖 */ printf("nThe graph is:n"); print(g); /*輸出鄰接矩陣*/ pri

3、ntf("input the city you want to start:"); scanf("%s",u); /* 輸入最小生成樹的起點 */ k=locatedvex(g,u); while(k=-1) printf("the name of the city is wrong!n"); printf("input the city you want to start again:"); scanf("%s",u); k=locatedvex(g,u); minispantree(g,u)

4、; /* 普里姆算法求最小生成樹 */ 4 代碼#include"stdio.h"#include"string.h"#define maxnum 20 /* 圖的最大頂點數 */#define INFINITY 1000 /* 定義一個權值的最大值 */typedef char vertextype20; /*定義城市名稱*/typedef struct arccellint adj; /*弧的權值*/int *info; /*弧上相關信息的指針*/arccell;typedef struct arrayvertextype adjvex; /*頂點的

5、鄰接點*/int lowcost; /* 某頂點與已構造好的部分生成樹的頂點之間的最小權值 */array;typedef struct vertextype vexsmaxnum; /*頂點向量*/arccell arcsmaxnummaxnum; /*鄰接矩陣*/int vexnum,arcnum; /*圖的頂點個數和弧個數*/array closedgemaxnum; /* 用普里姆算法求最小生成樹時的輔助數組 */ mgraph;void createUDN(mgraph *g) /* 用鄰接矩陣構造n個城市間的距離網g */int i,j,m,n,k,a,b,c;vertextype

6、 x,y;printf("input the number of cities (at least 6 cities) :"); scanf("%d",&g->vexnum); /* 輸入城市的個數（圖的頂點數） */printf("input the number of roads (at least 10 roads):");scanf("%d",&g->arcnum); /* 輸入道路的邊數（圖的邊數） */printf("input the name of %d cit

7、ies :",g->vexnum);for(i=0;i<g->vexnum;i+) scanf("%s",g->vexsi); /* 輸入城市名稱（圖的頂點） */for(m=0;m<g->vexnum;m+)for(n=0;n<g->vexnum;n+)g->arcsmn.adj=INFINITY; /* 初始化鄰接矩陣 */for(k=0;k<g->arcnum;k+)printf("input the distance of a road :");scanf("%

8、s%s%d",x,y,&c); /* 輸入城市間的距離（圖中邊的起點和終點及權值） */a=locatedvex(*g,x);b=locatedvex(*g,y);while(a=-1|b=-1)printf("the name of the city is wrong!n");printf("input the distance of a road again :");scanf("%s%s%d",x,y,&c); a=locatedvex(*g,x);b=locatedvex(*g,y);g->ar

9、csab.adj=c;g->arcsba=g->arcsab;void print(mgraph g) /*輸出用鄰接矩陣構造的n個城市間距離網g*/ int i,j; for (i=0;i<g.vexnum;i+) for(j=0;j<g.vexnum;j+) printf("%-4d ",g.arcsij.adj); printf("n"); void minispantree(mgraph g,vertextype x) /* 從第k個頂點出發構造圖g的最小生成樹 */int i,j,t,k,sum=0;k=locatedv

10、ex(g,x);for(j=0;j<g.vexnum;j+) /*輔助數組初始化*/if(j!=k) g.closedgej.lowcost=g.arcskj.adj; strcpy(g.closedgej.adjvex,x); g.closedgek.lowcost=0; /* 初始，U=u */for(i=1;i<g.vexnum;i+) /* 選擇其余的G->vexnum-1個頂點 */k=min(g); /* 求出生成樹的下一個頂點 */printf("(%s,%s) %dn",g.closedgek.adjvex,g.vexsk,g.closed

11、gek.lowcost); /* 輸出生成樹的邊和權值 */sum+=g.closedgek.lowcost; /*計算最小生成樹的代價*/ g.closedgek.lowcost=0; /* 第k頂點并入U集 */ for(t=0;t<g.vexnum;t+) /* 新頂點并入U后，修改輔助數組*/ if(g.arcskt.adj<g.closedget.lowcost)strcpy(g.closedget.adjvex,g.vexsk);g.closedget.lowcost=g.arcskt.adj;printf("The shortest distance is

12、%dn",sum); /*輸出最小生成樹的代價*/int min(mgraph g) /* 在輔助數組g.closedgei中選擇權值最小的頂點，并返回其位置 */int i,a=0,min;min=maxnum;for(i=1;i<g.vexnum;i+)if(g.closedgei.lowcost<min&&g.closedgei.lowcost!=0)a=i;min=g.closedgei.lowcost; return a;int locatedvex(mgraph g,vertextype u) /*確定任一城市在距離網g中的位置*/int i;

13、for(i=0;i<g.vexnum;i+) if(strcmp(u,g.vexsi)=0) return i; return -1; int main() mgraph g; vertextype u; int k; createUDN(&g); /* 生成鄰接矩陣結構的圖 */ printf("nThe graph is:n"); print(g); /*輸出鄰接矩陣*/ printf("input the city you want to start:"); scanf("%s",u); /* 輸入最小生成樹的起點

14、 */ k=locatedvex(g,u); while(k=-1) printf("the name of the city is wrong!n"); printf("input the city you want to start again:"); scanf("%s",u); k=locatedvex(g,u); minispantree(g,u); /* 普里姆算法求最小生成樹 */5 程序運行結果 8 心得體會 本次課程設計我們經歷了最短時間最繁重的設計任務，作為兩人組的課程設計任務難度相對來說較大，我和我的合作伙伴盡了

15、最大的努力來做到課程設計的要求，仍然不是很滿意最后的結果。但是，總的來說也讓我們體會到了一些軟件開發的辛苦，有時候你確實需要在有限的時間內來完成任務。最后本次課程任務教給我們很多，讓我們客觀的正視了自己一個學期的學習成果。我們相信自己通過這樣的任務能學到我們平時僅僅上課所學不到的知識，并發現、體會到了一種經過辛苦編程，糾正代碼后所獨有的快樂。也讓我們發現了自己對于編程所潛藏的熱愛。 教師見習報告總結期待已久的見習已經結束了，在龍巖三中高中部見習聽課，雖然只是短短的兩個星期，但感觸還是蠻深的，以前作為一名學生坐在課室聽課，和現在作為一名準教師坐在課室聽課是完全不同的感受，感覺自己學到了一些在平時

16、課堂上學不到的東西。在這里，我獲得的不僅是經驗上的收獲，更多是教學管理，課堂教學等的理念，以及他們帶給我的種種思考。教育見習實踐過程：聽課。教育見習的主要目的是讓學生在指導教師的引導下，觀摩教師上課方法、技巧等。聽課是教育見習的主要內容。我院規定在一周的見習中需完成至少6課的見習任務。我在教師的安排指導下，分別對高一、高二物理專業課型為主，其他課型齊頭的方式，積極主動的完成了聽課任務，收到良好的效果。我聽的第一節課是高二（8）班，這是一個平衡班，水平不如實驗班高。在上課前。科任老師已經跟我說了這個班的紀律是比較差的，而且成績也不是很好。在我聽課期間，確實有幾個學生在課堂上說話，但是我發現了一個

17、有趣的現象，這個現象我在往后的幾個班都發現了，就是絕大部分的學生的學習熱情都好高漲，積極舉手發言，積極參與課堂活動。我跟老師們提起這個現象的時候，科任老師就跟我說，一個班里不可能所有的學生都能全神貫注地聽完一節課，所以作為一名教師，應該想辦法吸引學生的注意力，調動的積極性，比如可以以小組為單位，以搶答計分的形式調動學生的積極性，這樣課堂氣氛就會活躍起來了。在為期兩周的見習工作中，我真的有很大的感觸，我第一次感受到自己已經從一名學生向一名教師靠近，走在校園里，每當有學生叫我一聲老師，我在感到無比自豪的同時，還感受到了自己的責任。見習工作結束了，我要回到學校繼續我的學習了，但是我會好好記住我從*中

18、學學到的一切，并應用于我的專業學習中去。一、教學管理理念 在龍巖三中，從領導階層到一位普通的科任老師，都秉承以學生為主體的宗旨進行學校的管理，進行教學工作的開展。作為一個課程改革的示范學校，一個教育實驗基地。這所學校鼓勵著老師做各種研究，各種改革。每個班主任都有著自己的管理經驗與管理宗旨。有了這種思想的自由，自然這里也就充滿著探索與嘗試，從而有所創造與進步。在我見習的班集體中，班主任對他的學生說：“我要讓你們成為學習型的管理者，也是管理型的學習者。”這樣一句簡單的話，讓我感到這里老師進行班級管理的良苦用心。他們關心的不只是學生的學習，更多的是從一個完整的人的概念出發，去培養學生多方面

19、的素質。二、教學理念 在見習期間，借著錄課的機會，我聽了很多的市級，校級的公開棵，還有理科實驗班的課。在這些課堂上，讓我看到教學改革正在悄然進行，有意識的老師正在努力體會“以學生為主體”的課堂模式。學生的創造也逐步成為教師追求的教學效果。其次，這里的老師也都在適應著多媒體教學，信息化教學，使得課堂更加生動，資源更加豐富，學生獲取學習資源的渠道也就更多。盡管，這種教學理念、教學模式的推廣仍然有很長的路，但似乎也并不遙遠，相信，這股改革的浪潮會給教育領域帶來很大的沖擊。 三、實際工作經驗 在上面，是我在這所學校感受最深刻，也是認為最有意義的收獲。實際工作經驗上，由于在指導老師的指導下，也獲取了許多。 在班主任工作上，我認識到了一個老師的表率作用是很大的，學生時刻看老師，作為一個老師，應該從自己嚴格要求，并影響感染學生。這就要求師生之間的相互交流必須是貼心的，也是帶有希望的。見習期間，班主任老師教給了我許多的班級管理經驗。我想這些經驗是寶貴的，更為寶貴的是老師的主動精神。在他的言談中，看出一個老師對于班級管理的深度認識。所以我想：一個好的班主任不應只是從學習上給學生幫助，而是從一種“管理”的角度上去讓班級受益，讓班級體的每個成員成長。 教學工作上，由于指導老師的認真指導，我較好地完成了教學任務。同時，與合作伙伴一同對各種教學模式進行了探