(論文)數(shù)據(jù)結(jié)構(gòu)及算法的設(shè)計(jì)與實(shí)現(xiàn) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告最新優(yōu)秀畢業(yè)論文資料搜集嘔血奉獻(xiàn)

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