課 程 設 計設計題目： 數據結構及算法的設計與實現 I課程設計（報告） 摘要摘 要 “數據結構”是一門專業技術基礎課。它的教學要求是：學會分析研究計算機加工的數據結構的特征，以便為應用涉及的數據選擇適當的邏輯結構、存儲結構及其相應的算法，并初步掌握算法的時間分析和空間分析的技術。另一方面，本課程的學習過程也是復雜程序設計的訓練過程，要求學生編寫的程序結構清楚和正確易讀，符合軟件工程的規范。在學習中，先要學習程序設計課程的目的掌握設計程序的思路，學習會用計算機語言編寫程序，以實現所需要處理的任務。要正確處理算法與語法的關系，算法是程序的核心、是靈魂，語法是外殼、是工具。不應把學習重.點放在語法規則上，語法是重要的，不掌握語法規則就無法編寫出正確的程序。一定要把重點放在解題的思路上，通過思考，和大量的閱讀，來構造一個完整的程序。請記住：重要的是學會編程，而不是背語法。程序設計是為了鍛煉我們的實際動手能力，在一定程度上，又增加了我們的各方面的知識，特別是一些聯系實際的課程設計，它的完成需要自己平時積累的大量知識、并且需要勤于思考的能力和無限的激情。本次課設主要是學習程序設計的方法，進行程序設計的基本訓練，大多數的學生應該把精力放在最基本，最常用的內容上，學好基本功。最后，感謝老師在我們程序設計的過程中辛勤的指導和不倦的教誨。關鍵詞 ：線性表，棧和隊列，二叉樹，圖，查找，排序VII 目錄數據結構及算法課程設計成績評定表I課程設計任務書.III摘 要.VII第一章 哈夫曼編譯碼器.11.1 問題分析.11.2 數據結構與算法分析.11.3 核心代碼.31.4 運行結果8第二章 文章編輯101.1 問題分析.101.2 數據結構與算法分析101.3 核心代碼121.4 運行結果17第三章 利用Hash技術統計C源程序中關鍵字的頻度.191.1 問題分析191.2 數據結構與算法分析191.3 核心代碼211.4 運行結果32第四章 設計實現利用普里姆算法構造最小生成樹的程序341.1 問題分析.341.2 數據結構與算法分析.341.3 核心代碼.351.4 運行結果.39總 結40致 謝41參考文獻42沈陽工程學院課程設計（報告） 第二章 文章編輯第一章 哈夫曼編譯碼器當今社會，計算機技術和通信技術已不斷發展，處理和傳輸的數據量越來越龐大。如何采用有效的數據壓縮技術引起了人們的極大重視。從而產生了哈夫曼編碼，它是一種應用廣泛且非常有效的數據壓縮技術，該技術一般可將數據壓縮20%至90%，通常我們將壓縮技術稱為編碼，解壓縮過程稱為解碼。樹狀結構簡稱為樹，是一種以分支關系進行定義的層次結構，是十分重要的非線性數據結構，在計算機軟件設計方面，有著廣泛的應用。1.1 問題分析在程序的運行過程中，我們小組遇到了一些問題：不知該用哪種方法、按什么樣的順序查找各個結點。如何建立哈夫曼樹，怎樣能最簡單的通過主函數去逐步調用其他各個函數以達到題目的要求。如何利用建好的huffman樹生成huffman編碼及如何實現譯碼功能。通過查找資料我們解決了所有問題，構造哈夫曼樹時，首先將由n各字符形成的n個葉子節點存放到數組HTNode的前n個分量中，然后根據前面介紹的哈夫曼方法的基本思想，不斷將兩個小子樹合并為一個較大的子樹，每次構成的新子樹，每次構成的新子樹的根節點順序放到HTNode數組中的前n個分量的后面。譯碼功能，假定電文中只使用A、B、C、D、E、F6種字符，若進行等長編碼，它們分別需要3位二進制字符，可一次編碼為000、001、010、011、100、101。1.2 數據結構與算法設計哈夫曼編譯碼器的主要功能是先建立哈夫曼樹，然后利用建好的哈夫曼樹生成哈夫曼編碼后進行譯碼 。在數據通信中，經常需要將傳送的文字轉換成由二進制字符0、1組成的二進制串，稱之為編碼。構造一棵哈夫曼樹，規定哈夫曼樹中的左分之代表0，右分支代表1，則從根節點到每個葉子節點所經過的路徑分支組成的0和1的序列便為該節點對應字符的編碼，稱之為哈夫曼編碼。最簡單的二進制編碼方式是等長編碼。若采用不等長編碼，讓出現頻率高的字符具有較短的編碼，讓出現頻率低的字符具有較長的編碼，這樣可能縮短傳送電文的總長度。哈夫曼樹課用于構造使電文的編碼總長最短的編碼方案。其主要流程圖如圖1-1所示。開始結點數是否大于1將data和權值賦給ht輸出根結點和權值調用SELECT函數計算根結點函數父結點為兩子結點之和輸出兩子結點和已構造的結點是否為根結點？左子是否為空？此時編碼為0I2*N?I+編碼為1結束否否否右子是否為空是是否否是是是圖1-1 哈夫曼樹編譯碼器流程圖1.3 核心代碼哈夫曼編譯碼器程序的主要代碼如下所示:#include #include /要用system函數要調用的頭文件#include /用getch()要調用的頭文件#include #define N 50 /義用N表示50葉節點數#define M 2*N-1 /用M表示節點總數 當葉節點數位n時總節點數為2n-1#define MAXSIZE 100typedef struct char data; /結點值 int weight; /權值 int parent; /雙親結點 int lchild; /左孩子結點 int rchild; /右孩子結點HTNode; typedef struct char cdN; /存放哈夫曼碼 int start; /從start開始讀cd中的哈夫曼碼HCode;void CreateHT(HTNode ht,int n) /調用輸入的數組ht,和節點數n int i,k,lnode,rnode; int min1,min2; for (i=0;i2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有結點的相關域置初值-1 for (i=n;i2*n-1;i+) /構造哈夫曼樹 min1=min2=32767; /int的范圍是-3276832767 lnode=rnode=-1; /lnode和rnode記錄最小權值的兩個結點位置 for (k=0;k=i-1;k+) if (htk.parent=-1) /只在尚未構造二叉樹的結點中查找 if (htk.weightmin1) /若權值小于最小的左節點的權值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weightmin2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /兩個最小節點的父節點是i hti.weight=htlnode.weight+htrnode.weight; /兩個最小節點的父節點權值為兩個最小節點權值之和 hti.lchild=lnode;hti.rchild=rnode; /父節點的左節點和右節點void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;in;i+) /根據哈夫曼樹求哈夫曼編碼 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到樹根結點結束循環 if (htf.lchild=c) /處理左孩子結點 hc.cdhc.start-=0; else /處理右孩子結點 hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; /start指向哈夫曼編碼hc.cd中最開始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /輸出哈夫曼編碼的列表 int i,k; printf( 輸出哈夫曼編碼:n); for (i=0;in;i+) /輸出data中的所有數據，即A-Z printf( %c:t,hti.data); for (k=hcdi.start;k=n;k+) /輸出所有data中數據的編碼 printf(%c,hcdi.cdk); printf(n); void editHCode(HTNode ht,HCode hcd,int n) /編碼函數char stringMAXSIZE; int i,j,k;scanf(%s,string); /把要進行編碼的字符串存入string數組中printf(n輸出編碼結果:n);for (i=0;stringi!=#;i+) /#為終止標志for (j=0;jn;j+)if(stringi=htj.data) /循環查找與輸入字符相同的編號，相同的就輸出這個字符的編碼for (k=hcdj.start;k=n;k+) printf(%c,hcdj.cdk);break; /輸出完成后跳出當前for循環void deHCode(HTNode ht,HCode hcd,int n) /譯碼函數char codeMAXSIZE;int i,j,l,k,m,x;scanf(%s,code); /把要進行譯碼的字符串存入code數組中while(code0!=#)for (i=0;in;i+)m=0; /m為想同編碼個數的計數器 for (k=hcdi.start,j=0;k=n;k+,j+) /j為記錄所存儲這個字符的編碼個數if(codej=hcdi.cdk) /當有相同編碼時m值加1m+;if(m=j) /當輸入的字符串與所存儲的編碼字符串個數相等時則輸出這個的data數據printf(%c,hti.data);for(x=0;codex-1!=#;x+) /把已經使用過的code數組里的字符串刪除codex=codex+j;void main() int n=26,i; char orz,back,flag=1; char str=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z; /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /初始化 HTNode htM; /建立結構體 HCode hcdN; /建立結構體 for (i=0;in;i+) /把初始化的數據存入ht結構體中 hti.data=stri; hti.weight=fnumi; while (flag) /菜單函數，當flag為0時跳出循環 printf(n); printf( ); printf(n A-顯示編碼 ); printf(n B-進行編碼 ); printf(n C-進行譯碼 ); printf(n D-退出 n); printf( ); printf(n); printf( 請輸入選擇的編號:); scanf(%c,&orz); switch(orz) case a: case A: system(cls); /清屏函數 CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); printf(n按任意鍵返回.); getch(); system(cls); break; case b: case B: system(cls); printf(請輸入要進行編碼的字符串(以#結束):n); editHCode(ht,hcd,n); printf(n按任意鍵返回.); getch(); system(cls); break; case c: case C: system(cls); DispHCode(ht,hcd,n); printf(請輸入編碼(以#結束):n); deHCode(ht,hcd,n); printf(n按任意鍵返回.); getch(); system(cls); break; case d: case D: flag=0; break; default: system(cls); 1.4 運行結果下面是程序的運行結果：1. 第一步運行程序為進入主菜單，如下圖1-2所示。圖 1-2 主菜單界面2. 第二步輸入編號A顯示編碼，輸出結果如下圖1-3所示。圖1-3 輸出哈夫曼編碼界面3. 第三步返回主菜單后輸入B進行編碼，輸入“LeonLee#”回車后顯示編碼，界面如圖1-4所示。圖1-4 編碼界面4. 第四步返回主菜單后輸入C進行譯碼，輸入“01100101110001100111000#”，回車后顯示譯碼，界面如圖1-5所示。圖1-5 譯碼界面第二章 文章編輯文章編輯需要統計文章中的所有文字信息，需要分行顯示，處理起來雖然不是很復雜卻設計到很多方面，需要使用鏈表來存儲文章。2.1 問題分析功能：輸入一頁文字，程序可以統計出文字、數字、空格的個數。靜態存儲一頁文章，每行最多不超過80個字符，共N行；要求： 分別統計出其中英文字母數和空格數及整篇文章總字數。 統計某一字符串在文章中出現的次數，并輸出該次數。 刪除某一子串，并將后面的字符前移。存儲結構使用線性表，分別用幾個子函數實現相應的功能。輸入數據的形式和范圍：可以輸入大寫、小寫的英文字母、任何數字及標點符號。輸出形式： 分行輸出用戶輸入的各行字符。 分4行輸出“全部字母數”、“數字個數”、“空格個數”、“文章總字數”。 輸出刪除某一字符串后的文章。在編輯過程中，遇到的問題有對字符的統計過程中需要用ASCII碼，在自已開始直接用的是字母或者數字。不知道怎么結束文章輸入操作，最后在查找ASCII碼時發現可以用ASCII碼中的end控制符結束文章的輸入。2.2 數據結構與算法設計文章編輯程序的主要功能是統計文章中的全部字母數、數字個數、空格個數和文章總字數，并且能準確的查找、刪除字符串。主要應用的函數和語句有循環，查找，刪除等。由程序開始運行后進行字符串的錄入，之后進行字符的輸出，然后是利用循環和查找，進行字符的統計并輸出已經找到的字符（包括字母、數字、空格）出現的次數以及總共的字符數。在這些運行完之后，根據要求還有一項功能-刪除，對指定的字符進行刪除，同樣，這里也需應用到循環，查找和刪除。其主要流程圖如圖2-1所示。是是是開始ID=1Create()ID=2output()ID=3Count()ID=4FindString()ID=5delstringword()ID=66輸出breakoutput ()否否是否否否main()輸出菜單輸入IDWhile(1)退出是圖 2-1 文章編輯流程圖2.3 核心代碼文章編輯程序代碼如下：#include#include#include#define LEN sizeof(struct line)typedef struct linechar *data; /文本每行以字符串形式存儲，行與行之間以鏈表存儲 struct line *next;LINE;/創建一鏈表，同時向里面輸入文本數據void Create(LINE * &head)char tmp100;LINE *p;p=(struct line *)malloc(LEN); /開辟一個LINE結構體類型的空間，并把頭地址給p head=p; /將p賦給 表頭指針printf(請輸入文本，以Ctrl+E(E)為結尾，每行最多輸入80字符！n); /ASCII碼中第5個 end結束符 while(1) gets(tmp); /輸入字符串！ if(strlen(tmp)80) printf(每行最多輸入80字符); break; if(tmp0=5) break; /如果一開始發現輸入 E，則退出輸入 p=p-next=(struct line *)malloc(LEN); /新的一行 重新開辟空間 p-data=(char *)malloc(strlen(tmp); /為結點分配空間 strcpy(p-data,tmp); if(tmpstrlen(tmp)-1=5) /除去最后一個控制符 E，并且退出 p-datastrlen(tmp)-1=0; break; p-next=NULL; /最后的一個指針為空。 head=head-next;/統計字母數int CountLetter(LINE * &head)LINE *p=head;int count=0;do int Len=strlen(p-data); /計算當前 data 里的數據元素的個數 for(int i=0;idatai=a&p-dataidatai=A&p-datainext)!=NULL); /下一個節點不為空return count; /返回文章的字母總數/統計數字數int CountNumber(LINE * &head) LINE *p=head; int count=0; do int Len=strlen(p-data); /計算當前 data 里的數據元素的個數 for(int i=0;idatai=48 & p-datainext)!=NULL); return count;/統計空格數int CountSpace(LINE * &head) LINE *p=head; int count=0; do int Len=strlen(p-data); /計算當前 data 里的數據元素的個數 for(int i=0;idatai=32)count+; /根據空格的ASCII碼值計算個數 while(p=p-next)!=NULL); return count;/統計文章的總字數int CountAll(LINE * &head) LINE *p=head; /保存鏈表的首地址 int count=0; do /計算總字符數 count=count+strlen(p-data); while(p=p-next)!=NULL); /遍歷 鏈表 return count;/統計str在文章中出現的次數int FindString(LINE * &head,char *str) LINE *p=head; int count=0; int h=0; int len1=0; /保存當前行的總字符數 int len2=strlen(str); /待統計字符串的長度 int i,j,k; do len1=strlen(p-data); /當前行的字符數for(i=0;idatai=str0)k=0; for(j=0;jdatai+j=strj) /與輸入的字符串進行比較相同的就k加1k+;if(k=len2) /若K與字符串的長度相等count+;i=i+k-1; /跳過找到的字符串繼續找 while(p=p-next)!=NULL); return count;/刪除指定的字符串void delstringword(char *s,char *str) / *s為輸入的字符串，*str為將要刪除的字符 char *p=strstr(s,str); /從字符串s中尋找str第一次出現的位置 char tmp80; int len=strlen(s); int i=len-strlen(p); int j=i+strlen(str); int count=0,m,n; for(m=0;mi;m+)tmpcount+=sm; /把刪除字符串的前面字符串給數組tmp for(n=j;ndata,str)!=NULL) /這一行中有匹配的字符串delstringword(p-data,str);while(p=p-next)!=NULL); /遍歷 鏈表/向屏幕輸出文章void OutPut(LINE * &head) LINE *p=head; do /按行輸出文章 printf(%sn,p-data); while(p=p-next)!=NULL); /下一個節點不為空，符合條件則輸出下一行/主函數int main()LINE *head;char str120,str220;int letter,number,space,all,countstr1;Create(head);printf(文章為：n);OutPut(head);letter=CountLetter(head);printf(n全部字母數：%d,letter);number=CountNumber(head);printf(n數字個數：%d,number);space=CountSpace(head);printf(n空格個數: %d,space);all=CountAll(head);printf(n文章總字數: %d,all);printf(n請輸入要統計的字符串:);scanf(%s,str1);countstr1=FindString(head,str1);printf(%s出現的次數為:%d,str1,countstr1);printf(n請輸入要刪除的某一字符串：);scanf(%s,str2);DelString(head,str2);printf(刪除%s后的文章為：n,str2);OutPut(head); printf(n謝謝使用!n);2.4 運行結果以下是文章編輯程序的運行結果：1. 第一步按提示輸入如下文章“everyone has a great dream in his heart,what we should do is that try our best.E”輸出統計的各種信息，輸出界面如圖2-2所示。圖2-2 輸入文章信息2. 第二步輸入要統計的特定字符串，如下圖2-3所示。圖2-3 統計特定字符串3. 第三步輸入要刪除的字符，回車后顯示刪除完指定字符的文章，顯示界面如圖2-4所示。圖2-4 刪除字符1沈陽工程學院課程設計（報告） 第四章 設計實現利用普利姆算法構造最小生成樹的程序第三章 利用Hash技術統計C源程序中關鍵字的頻度隨著社會的發展，出現了減少沖突的一種散列函數，它就是哈希函數。所謂的“哈希函數”就是表尚未被占用的地址，當插入的記錄所選地地址已被占用時，即轉而尋找其它尚未開發的地址。開放地址法又稱為散列表處理沖突的方法。散列表按結構形式可分為散列表和閉散列表，所謂的閉散列表的結構是一個向量，也是一維數組，表中記錄按關鍵字經散列函數運算所得的地址直接存入數組中。3.1問題分析在這個程序設計中,我們小組遇到的不少的問題:1.我們小組決定不下要用哪種查詢方法。2.統計關鍵字發生的沖突的次數,到底應該怎么來記數,怎么樣解決沖突,最后我們用了開放地址的線型探測法來解決沖突。3.在插入哈希表之后應該怎樣重新來計算發生的沖突和頻數(頻度)。除留余數法式一種最簡單、最常用的構造哈希函數方法，這種方法關鍵在于m的選擇，選定m值后就可以決定存儲地址的數目了，為了使哈希函數的取值盡可能“分散”一些，以減少沖突，m的選擇要適當。形成探查地址序列最簡單的方法是線性探測法，線性探測法的基本思想是沿著哈希表順序向后查探，直至找到開放地址為止，如到達表末端仍未找到開放地址，則將表看做是循環的，返回到表的首端再向后找，只要尚有開放地址最終總可以找到。3.2數據結構與算法分析此哈希函數的主要功能是掃描一個C源程序，用Hash表存儲該程序中出現的關鍵字，并統計該程序中的關鍵字出現的頻度，用線性探測法解決Hash沖突。還查詢某指定關鍵字在Hash表中的情況，也能輸出Hash表，關鍵詞總數，沖突次數。其主要流程圖如圖3-1所示。開始輸入orzWhile(orz)main()orz=A否是是Read(filename)否orz=BShow(i)1是否I=C是否Show(Findhx(word)I=D是2否breakbreakbreakGetKey()break輸出輸出輸出輸出12I=E是否輸出GetKey(KeyWordsi)I=F是breakbreak圖3-1 哈希表流程圖3.3 核心代碼哈希表主要程序代碼如下：#include #include #include #include #define TOTAL 39 /39個關鍵字#define MAXLEN 10 /關鍵字長度#define HASHLEN 41 /哈希表長度typedef struct /哈希表 結構體 char keywordMAXLEN; /關鍵字int count; /記錄頻度int con; /記錄沖突次數HASH;/全局變量int cont=0; /統計關鍵詞個數char KeyWordsTOTALMAXLEN=asm,auto,break,case,cdecl,char, const,continue,default,do,double, else,enum,extern,far,float,for, goto,huge,if,int,interrupt,long, near,pascal,register,return,short, signed,sizeof,static,struct,switch, typedef,union,unsigned,void,volatile, while; /C語言中的39個關鍵字存入二維數組中HASH HSHASHLEN; /建立結構體HS/函數聲明void Show(int key);int Read(char *filename); int isLetter(char ch);int isKeyWords(char *word);int FindHX(char *keyword);int CreatHX(char *keyword);int GetFreePos(int key);int GetKey(char *keyword);void main() char orz; int flag=1,i,count,key,has;char filename128,wordMAXLEN; while(flag) printf(ttA.讀取一個文件n); printf(ttB.輸出Hash表(關鍵字總數，沖突次數)n); printf(ttC.查詢某關鍵字在Hash表中的情況n); printf(ttD.顯示Hash表中的沖突關鍵字n); printf(ttE.顯示C語言關鍵字的Hash函數值(作為對照)n); printf(ttF.退出nn);printf(tt請輸入序號(A-F):); scanf(%c,&orz);switch(orz) case a:case A:system(cls); /清屏函數 printf(請輸入要讀取的文件名(文件必須與程序在同一目錄下):); /比如輸入：a.cppscanf(%s,&filen