數(shù)據(jù)結構_課程設計報告

1、數(shù)據(jù)結構課程設計報告學院：計算機科學與工程 專業(yè)：計算機科學與技術 班級：09級班 學號：姓名：指導老師：時間：2010年12月一、課程設計題目:1、哈夫曼編碼的實現(xiàn)2、城市轄區(qū)地鐵線路設計3、綜合排序算法的比較二、小組成員：三、題目要求：哈夫曼編碼的實現(xiàn)打開若干篇英文文章，統(tǒng)計該文章中每個字符出現(xiàn)的次數(shù)，進一步統(tǒng)一 各字符出現(xiàn)的概率。針對上述統(tǒng)計結果，對各字符實現(xiàn)哈夫曼編碼對任意文章，用哈夫曼編碼對其進行編碼對任意文章，對收到的電文進行解碼某城市要在其各個轄區(qū)之間修建地鐵來加快經濟發(fā)展，但由于建設地鐵的費 用昂貴，因此需要合理安排地鐵的建設路線。從包含各轄區(qū)的地圖文件中讀取轄區(qū)的名稱和各轄區(qū)

2、的直接距離根據(jù)上述讀入的信息，給出一種鋪設地鐵線路的解決方案。使乘客可以 沿地鐵到達各個轄區(qū)，并使總的建設費用最小。輸出應該建設的地鐵路線及所需要建設的總里程信息。綜合排序算法的比較各種內部排序算法的時間復雜度分析結果只給出了算法執(zhí)行時間的階，或大 概的執(zhí)行時間。試通過隨機的數(shù)據(jù)比較各算法的關鍵字比較次數(shù)和關鍵字移 動的次數(shù)。對以下各種常用的內部排序算法進行比較：直接插入排序，折半插入排序，二路歸并排序，希爾排序，冒泡排序，快速 排序簡單選擇排序，堆排序，歸并排序，基數(shù)排序。待排 序的表長不少于100，要求采用隨機數(shù)。至少要用5組不同的輸入數(shù)據(jù)做比較：比較的次數(shù)為有關鍵字參加的 比較次數(shù)和關鍵

3、字移動的次數(shù)改變數(shù)據(jù)量的大小，觀察統(tǒng)計數(shù)據(jù)的變化情況。對試驗統(tǒng)計數(shù)據(jù)進行分析。對各類排序算法進行綜合評價。四、項目安排：1、小組內分工合作分工：負責哈夫曼編碼的實現(xiàn)，負責城市轄區(qū)地鐵線路設計，負責綜合排序 算法的比較。合作：組內，組外進行交流，組長幫助解決組員的在項目過程中的困難，并 控制進度。五、完成自己的任務：任務：城市轄區(qū)地鐵線路設計1.實現(xiàn)方案創(chuàng)建城市轄區(qū)圖表信息將信息寫入文件從文件讀取信息 最優(yōu)路徑的選擇 / 輸出最優(yōu)路 I徑的相關信)在整個編程中，我是通過手動輸入的方式把數(shù)據(jù)寫到文件中，而不是直接從 文件中讀取，這個不是題目要求的，但是我想當拿到數(shù)據(jù)之后都要對數(shù)據(jù)進行處 理，干脆直

4、接手動輸入得出結果。在這個代碼中，最重要的是鐵路線路的最優(yōu)設計。在這個代碼的實現(xiàn)中，我 用了 Kruscal的想法，然后通過函數(shù)的嵌套實現(xiàn)最優(yōu)路徑的選取的。2.代碼的實現(xiàn)#include#include#include#include #include #define MAXSIZE 100typedef struct link(int connect;int feeJ/費用struct link *next;edgenode;typedef struct node (char name10;/ 名稱edgenode *link;city;typedef struct(city vexMAXS

5、IZE;int city_n,city_e;city_graph;city_graph ga;int total_fee=0;/記錄總費用void creat(city_graph *ga)/創(chuàng)建轄區(qū)總信息(int i=0 ,a,b;edgenode *q;edgenode *p;printf(-請輸入城市轄區(qū)個數(shù)：);/城市中轄區(qū)的個數(shù)scanf(%d,&ga-city_n);printf(-請輸入城市轄區(qū)間路徑的總個數(shù)：);/轄區(qū)間的路徑scanf(%d,&ga-city_e);for(i=1;icity_n+1;i+)/建 立城市轄區(qū)信息表(printff請輸入第d個城市轄區(qū)名稱：,i)

6、;scanf(%s,);ga-vexi.link=NULL;for(i=0;icity_e;i+)/轄區(qū)聯(lián)系表(頭插法)(printf(請輸入第d組兩個相鄰轄區(qū)的編號,i+1);/還沒有處理 數(shù)據(jù)，比如輸入的是超出規(guī)定范圍的數(shù)據(jù)p=(edgenode *)malloc(sizeof (edgenode );q=(edgenode *)malloc(sizeof (edgenode );scanf(%d%d,&a,&b);printf(-請輸入兩轄區(qū)間的費用：，兩轄區(qū)間路程的費用scanf(%d,&p-fee);q-fee=p-fee;p-connect=b;q-conn

7、ect=a;p-next=ga-vexa.link;/建立兩轄區(qū)間的聯(lián)系ga-vexa.link=p;q-next=ga-vexb.link;ga-vexb.link=q;void view(city_graph *ga)/出(system(Hcls);/清 屏。int i;edgenode *p;for(i=1;icity_n+1;i+)(p=ga-vexi.link;/printf(%sn,);printf(n 與轄區(qū) %s 相連的轄區(qū)有：n,);printf(n 名稱費用n);if(p=NULL)printf(n);while(p!=NUL

8、L)(printf(%s %5dn,,p-fee);p=p-next;printf(nn);void insert(city_graph *ga)/導入文件中(FILE *fp;edgenode *p;int i=0;if(fp=fopen(e: 轄區(qū).txt,w+)=NULL)(printf(-打開文件失敗!n);exit(0);for(i=1;icity_n+1;i+)(p=ga-vexi.link;fputs(,fp);fprintf(fp,n);fprintf(fp,%dn,p-connect);fprintf(fp,%d

9、n,p-fee);fclose(fp);/*city_graph * load(city_graph *gb)/從 文件中導出待解決FILE *fp;int i=1;edgenode *p;if(fp=fopen(e: 轄區(qū).txt,r+)=NULL)(printf(打開文件失敗!n);exit(0);while(fscanf(fp,%s%d%d,,&p-connect,&p-fee)!=EOF)(p=(edgenode *)malloc(sizeof (edgenode );p-next=gb-vexi.link;gb-vexi.link=p;i+;fclose(fp

10、);return gb;*/city_graph * change(city_graph *ga,int min_a,int min_b)/改 變倆轄區(qū)間的費用(edgenode *p,*q,*t,*t1;p=ga-vexmin_a.link;q=ga-vexmin_a.link;t1=ga-vexmin_b.link;while(p!=NULL)(if(p-connect=min_b)(p-fee=0;/q-next=p;q=p;p=p-next;t=ga-vexmin_b.link;while(t!=NULL)(if(t-connect=min_a)t-fee=0;/ t1-next=t;

11、t1=t;t=t-next;return ga;city_graph * find_next(city_graph *ga,int i)/(edgenode *p,*q;int j,min,min_sign,min_record;q=ga-vexi.link;min=q-fee;min_sign=q-connect;min_record=i;for(j=1;jcity_n+1;j+)/找 費用最少的兩個轄區(qū)(p=ga-vexj.link;/記下當前轄區(qū)，以便在此轄區(qū)的聯(lián)系鏈中找到此鏈下的最小花費路徑while(p!=NULL)if(p-feefee!=0)(min=p-fee;min_sign

12、=p-connect;min_record=j;p=p-next;if(min!=0)/把費用為0的濾去(因為在改變費用時把原來的費用給 置成了 0，以便判斷哪些路徑是比較過的)(printf(%s%s %dn,ga-vexmin_,ga-vexmin_,min);/輸出建設路徑total_fee=total_fee+min;ga=change(ga,min_record,min_sign); /改變兩轄區(qū)間的費用，以便區(qū)分return ga;void find(city_graph *ga)/Kruscal 算法(int i;printf(nn以下是建

13、設路徑nn);printf(轄區(qū)名-轄區(qū)名-費用nn);for(i=1;icity_n+1;i+)(ga=find_next(ga,i);/調用函數(shù)找全部路徑中最小費用的轄區(qū)printf(n 總費用 = %dnn,total_fee);void main()(/city_graph *gb;creat(&ga);view(&ga);insert(&ga);/讀入文件/gb=(city_graph *)malloc(sizeof(city_graph);/gb=load(gb); 導出到文件中find（&ga）;/未使用到從文件導出的圖，而是使用了導入文件的圖， 因為導出文件有問題。3.運行結果：（1）城市轄區(qū)圖表的信息尸4-r待的i車擊e n褂,-HNN 1 2to 平“K pbJb so與斗舌ITT柞連K.I字莒盡有M日林辭一 FJ=.*1)112M亍FB1精1,或有=費41pc勺可害心-杜在口勺可咨略白=土1彳小用fSfCM SCIX與猿皿XXtl iT日勺耗皿