數(shù)據(jù)結(jié)構(gòu)-哈夫曼-二叉樹-農(nóng)夫過河【最新】

1、數(shù)據(jù)結(jié)構(gòu)2課程設(shè)計目 錄實(shí)驗一 農(nóng)夫過河3一、問題描述3二、基本要求3三、設(shè)計思想3四、執(zhí)行過程41.思想概要42.主要功能模塊4實(shí)驗二 求二叉樹中葉子結(jié)點(diǎn)個數(shù)7一、問題描述7二、基本要求7三、設(shè)計思想7四、執(zhí)行過程8實(shí)驗三 哈夫曼編碼的實(shí)現(xiàn)11一、設(shè)計內(nèi)容11二、基本要求11三、算法設(shè)計111.設(shè)計思想112.執(zhí)行過程113.算法思想124. 主要模塊說明135. 部分重要函數(shù)的實(shí)現(xiàn)14總結(jié)14參考資料15附錄161、農(nóng)夫過河源代碼162、求二叉樹葉子結(jié)點(diǎn)個數(shù)源代碼173、哈夫曼算法源代碼2172實(shí)驗一 農(nóng)夫過河一、問題描述一個農(nóng)夫帶著一只狼，一棵白菜和一只山羊要從一條河的南岸到北岸，農(nóng)夫每

2、次只能帶一樣?xùn)|西過過河，但是任意時刻如果農(nóng)夫不在場時，狼要吃羊、狼要吃菜，輕微農(nóng)夫設(shè)計過河方案。二、基本要求為農(nóng)夫過河問題抽象數(shù)據(jù)模型，體會數(shù)據(jù)模在問題求解中的重要性；設(shè)計一個算法求解農(nóng)夫果核問題，并輸出過河方案；分析算法的時間復(fù)雜度。三、設(shè)計思想要求解農(nóng)夫過河問題，首先要選擇一個對問題中每個角色的位置進(jìn)行描述的方法。用四位二進(jìn)制數(shù)順序表表示農(nóng)夫、狼、白菜和羊的位置。用1表示在南岸，0表示在北岸。共有00001111中狀態(tài)，以每一種狀態(tài)為圖的一個頂點(diǎn)，判斷狀態(tài)中可行的點(diǎn)。四、執(zhí)行過程 南岸（1） 北岸（0） 狀態(tài)農(nóng)夫、狼、羊、白菜0000農(nóng)夫、羊農(nóng)夫、白菜1010羊農(nóng)夫、狼、白菜0010農(nóng)夫、

3、羊、白菜狼1011白菜農(nóng)夫、狼、羊0001農(nóng)夫、狼、白菜羊1101狼、白菜農(nóng)夫、羊0101農(nóng)夫、狼、羊、白菜11111.思想概要根據(jù)可能出現(xiàn)的情況創(chuàng)建無向圖，農(nóng)夫的運(yùn)動狀態(tài)建立鄰接矩陣，確定起始狀態(tài)頂點(diǎn)為狀態(tài)0000，終結(jié)狀態(tài)頂點(diǎn)為1111，即開始時農(nóng)夫、狼、羊和白菜都在北岸，頂點(diǎn)狀態(tài)為0000，運(yùn)用遞歸調(diào)用深度優(yōu)先遍歷圖，從開始狀態(tài)頂點(diǎn)到結(jié)束狀態(tài)頂點(diǎn)遍歷，輸出過河情況。2.主要功能模塊2.1創(chuàng)建無向圖以農(nóng)夫，狼，羊和白菜安全的情況為頂點(diǎn)創(chuàng)建無向圖。public void graph()for(int i=0;imaxsize;i+)for(int j=0;jmaxsize;j+)fwscij

4、=0;for(int farmer=0;farmer=1;farmer+)for(int wolf=0;wolf2;wolf+)for(int sheep=0;sheep2;sheep+)for(int cabbage=0;cabbage2;cabbage+)if(issafety(farmer,wolf,sheep,cabbage)k+;for(int i=k-1;ik;i+)vertexi=8*farmer+4*wolf+2*sheep+1*cabbage;for(int i=0;ik;i+)for(int j=0;jk;j+)fwscij=1;fwscji=1;2.2圖的深度遍歷深度遍歷

5、無向圖，并調(diào)用遞給算法。public void dfstraverse()route=new booleank;for(int i=0;ik;i+)if(routei=false)dfs(i);public void dfs(int i)routei=true;system.out.println(vertexi);for(int j=0;jlchild=null&root-rchild=null) count+; countleaf(root-lchild); countleaf(root-rchild);非遞歸算法求葉子節(jié)點(diǎn)：void countleaf(bittree bt) stack

6、 s; s = (stack)malloc(sizeof(struct stack); s-top = 0; while(bt != null|s-top != 0) if(bt != null) printf(%2c,bt-data); s-maxsizes-top = bt; s-top+; bt=bt-lchild; else bt=s-maxsizes-top-1; s-top-; if(bt-rchild = null & bt-lchild = null) count+; bt=bt-rchild; 實(shí)驗三 哈夫曼編碼的實(shí)現(xiàn)一、設(shè)計內(nèi)容將任意一個指定的文本文件中的字符進(jìn)行哈夫曼編碼

7、,生成一個編碼文件(壓縮文件);反過來,可將一個壓縮文件解碼還原為一個文本文件。二、基本要求假設(shè)文檔內(nèi)容從鍵盤輸入；設(shè)計哈夫曼算法的存儲結(jié)構(gòu)；設(shè)計哈夫曼編碼和解碼算法；分析時間復(fù)雜度和空間復(fù)雜度。三、算法設(shè)計1.設(shè)計思想對于給定的文檔，首先通過掃描確定文檔中出現(xiàn)了哪些字符以及出現(xiàn)的次數(shù)，以出現(xiàn)的次數(shù)作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹，獲得各字符的哈夫曼編碼；然后在掃描一遍文檔將其進(jìn)行哈夫曼壓縮編碼，將文本文檔轉(zhuǎn)換為二進(jìn)制編碼輸出；最后將二進(jìn)制流進(jìn)行解碼，并與原文檔進(jìn)行對照，以驗證算法的正確性。2.執(zhí)行過程選擇要壓縮的文檔，掃描確定文檔中字符出現(xiàn)的次數(shù)，根據(jù)出現(xiàn)頻數(shù)建哈夫曼樹，根據(jù)哈夫曼樹編碼。編碼

8、后寫入新文件，對讀入的編碼對照表進(jìn)行排序，長度短的排在前面，將字符編碼對照表寫入文件。將編碼讀入內(nèi)容，進(jìn)行解碼工作。建立哈夫曼樹根據(jù)哈夫曼樹編碼根據(jù)哈夫曼樹解碼統(tǒng)計字符，得出統(tǒng)計出字符的權(quán)值n對二進(jìn)制文件進(jìn)行解碼對編碼進(jìn)行壓縮生成哈夫曼樹生成二進(jìn)制文件生成對應(yīng)文件3.算法思想3.1輸入要壓縮的文件首先運(yùn)行的時候，用戶主界面上有菜單提示該如何使用軟件，根據(jù)菜單提示選擇所要執(zhí)行的 項，依次進(jìn)行，因為各個環(huán)節(jié)之間有先后順序。第一步為輸入壓縮軟件的名稱，由鍵盤輸入文件路徑和文件名稱，讀入字符數(shù)組中，打開該文件，按照提示進(jìn)行壓縮。若打不開，則繼續(xù)輸入。3.2讀文件并計算字符頻率文件將信息存放在字符數(shù)組中

9、；計算每個字符出現(xiàn)的次數(shù)，申請一個結(jié)構(gòu)體數(shù)組空間， 用讀取的字符減去字符結(jié)束符作為下標(biāo)記錄字符的頻率。3.3根據(jù)字符的頻率，利用哈夫曼編碼思想創(chuàng)建哈夫曼樹將所記錄的字符的頻率作為權(quán)值來創(chuàng)建huffman樹，依次選擇權(quán)值最小的兩個字符作為左右孩子，其和作為父結(jié)點(diǎn)的權(quán)值，依次進(jìn)行下去，直到所有的字符結(jié)點(diǎn)都成為葉子結(jié)點(diǎn)。3.4由創(chuàng)建的哈夫曼樹來決定字符對應(yīng)的編碼，進(jìn)行文件的壓縮根據(jù)創(chuàng)建的huffman樹來確定個字符的01編碼，左孩子為0，右孩子為1。讀取文件，依次將每個字符用他們的編碼表示，即完成一次編碼。3.5解碼壓縮即根據(jù)哈夫曼樹進(jìn)行譯碼讀取編碼文件，依據(jù)創(chuàng)建的huffman樹，定義一個指針指向

10、根結(jié)點(diǎn)。從根結(jié)點(diǎn)開始，每讀一個字符，指針變化一次（當(dāng)讀取的字符是1時，指針指向當(dāng)前所指結(jié)點(diǎn)的右孩子，當(dāng)讀取的字符是0時，指針指向當(dāng)前所指結(jié)點(diǎn)的左孩子），直至該指針?biāo)附Y(jié)點(diǎn)為葉子結(jié)點(diǎn)時結(jié)束（即當(dāng)結(jié)點(diǎn)的左右孩子均為空時）。將當(dāng)前葉子結(jié)點(diǎn)所代表的字符值輸出到譯碼文件中，依次讀取編碼文件中的字符，按照上述方法依次進(jìn)行下去直至文件4. 主要模塊說明下面是該系統(tǒng)的模塊：4.1首先定義一個結(jié)構(gòu)體：struct headunsigned char b;/記錄字符long count; /權(quán)重int parent,lch,rch;/定義雙親，左孩子，右孩子char bits256; /存放哈夫曼編碼的數(shù)組hea

11、der512,tmp;/頭部一要定設(shè)置至少512個,因為結(jié)點(diǎn)最多可達(dá)256,所有結(jié)點(diǎn)數(shù)最多可達(dá)5114.2然后是實(shí)現(xiàn)各個功能的函數(shù)：void show()/顯示文本文件的內(nèi)容 unsigned char ctoa(char a) /將數(shù)組的前八位轉(zhuǎn)成二進(jìn)制形式bit位char *code(unsigned char temp,int leafnum) /尋找對應(yīng)字符的編碼串，并返回void yasuo(char *infilename,char *outfilename)/ 對文本編碼函數(shù)void jieya(char *infiname,char *outfilename) /對壓縮文件解碼

12、void ctoa(unsigned char a,char code) / 字符轉(zhuǎn)為二進(jìn)制形式存入8位數(shù)組int strcmp1(char buf,struct head head,int n,unsigned char &c) /將buf字符串與headeri.bits中匹配，成功后對應(yīng)的字符由c帶回void strcpy1(char buf,char a,int) /將字符串a(chǎn)中長度為j的部分復(fù)制到buf數(shù)組中4.3最后是主函數(shù)：在主函數(shù)中含有菜單函數(shù)void mainmenu()和幫助函數(shù)void help()，最后通過switch語句，調(diào)用各種函數(shù)，分別完成各自的功能。5. 部分重要

13、函數(shù)的實(shí)現(xiàn)5.1.void yasuo(char *name,char *name1)的實(shí)現(xiàn)：1）記錄文件中字符頻度；2）根據(jù)頻度建樹；3）根據(jù)哈夫曼樹編碼；4）對文件進(jìn)行編碼，寫入新文件(核心)； 5）將字符編碼對照表寫入文件；6) 將文件的哈夫曼編碼輸出到顯示器上。5.2.void jieya(char *name,char *name1)的實(shí)現(xiàn)：1）讀入必要的數(shù)據(jù)；2) 讀入編碼對照表，放入headeri.bits數(shù)組中；3) 對讀入的編碼對照表進(jìn)行排序，長度短的排在前面；4) 將編碼讀入內(nèi)容，進(jìn)行解碼工作?？偨Y(jié)其實(shí)在這次課程設(shè)計中遇到很多問題，第一就是知識學(xué)的不扎實(shí)，必須從最基本的書本

14、知識看起。其次通過網(wǎng)絡(luò)資源使我了解的知識更加豐富，增強(qiáng)了我對網(wǎng)絡(luò)資源的檢索能力，使我能夠更好的應(yīng)用網(wǎng)絡(luò)資源來完成自己需要完成的任務(wù)。所以課程設(shè)計不僅能培養(yǎng)我們的專業(yè)知識，而且還能培養(yǎng)我們的動手能力，使我們以后能夠更加適應(yīng)社會的發(fā)展。通過這次課程設(shè)計，使我的自學(xué)能力有所提高，讓我知道了怎么去接受一個新的知識并且能夠很好的掌握它。同時也增強(qiáng)我的獨(dú)立思考能力和動手能力；通過編寫程序代碼和調(diào)試運(yùn)行，我們可以逐步積累調(diào)試程序的經(jīng)驗，逐漸培養(yǎng)我們的編程能力和利用計算機(jī)解決實(shí)際問題的能力。課程設(shè)計為我們提供了一個自己動手實(shí)踐的平臺。另一方面，在課程設(shè)計的過程中，使我明白了面向?qū)ο笈c面向?qū)ο蟮牟顒e。在面向?qū)ο?/p>

15、過程中，類的設(shè)計是至關(guān)重要的，類設(shè)計好了等于程序就成功了一半，所以這次的課程設(shè)計幫助我復(fù)習(xí)了這一學(xué)期面向?qū)ο笳n程的學(xué)習(xí)，剛好可以彌補(bǔ)這一學(xué)期面向?qū)ο髮W(xué)習(xí)的不足。同時，也使我對數(shù)據(jù)結(jié)構(gòu)與算法的知識有了一定的了解，幫我在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的課程中奠定了一定的基礎(chǔ)，使我以后學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的時候可以更加輕松。 這次課程設(shè)計不但使我掌握了一些知識，更重要的是使我認(rèn)識到了作為程序員的艱辛和辛苦。一個星期面對著電腦，在你面前只有一行行的代碼，在你的耳旁只有鍵盤的敲擊聲和點(diǎn)擊鼠標(biāo)的聲音，說實(shí)話確實(shí)很無聊也很辛苦。但當(dāng)自己看到自己編寫的程序順利通過的時候，心里的成就感就油然而生，心中的疲倦也消失了，我想，當(dāng)

16、程序員看到自己的程序能夠編譯成功的話，也是這種感覺吧！雖然這次課程設(shè)計結(jié)束了，但我們學(xué)習(xí)c+等語言的步伐不能停止，在今后的學(xué)習(xí)過程中，我會更加努力，爭取在今后的課程中學(xué)得更好，下次的課程設(shè)計能夠更加成功。參考資料數(shù)據(jù)結(jié)構(gòu)（c+版）（第二版） 王紅梅、胡明、王濤編著數(shù)據(jù)結(jié)構(gòu)（c+版）學(xué)習(xí)輔導(dǎo)與實(shí)驗指導(dǎo)（第二版） 王紅梅、胡明、王濤編著附錄1、農(nóng)夫過河源代碼package procedure;public class farmerprocedure public static final int maxsize=10;int farmer;int wolf;int sheep;int cabbag

17、e;static int k=0;boolean route;int vertex=new int16;int fwsc=new intmaxsizemaxsize;boolean issafety(int farmer,int wolf,int sheep,int cabbage)if(sheep!=farmer&(wolf=sheep|sheep=cabbage)return false;else return true;public void graph()for(int i=0;imaxsize;i+)for(int j=0;jmaxsize;j+)fwscij=0;for(int f

18、armer=0;farmer=1;farmer+)for(int wolf=0;wolf2;wolf+)for(int sheep=0;sheep2;sheep+)for(int cabbage=0;cabbage2;cabbage+)if(issafety(farmer,wolf,sheep,cabbage)k+;for(int i=k-1;ik;i+)vertexi=8*farmer+4*wolf+2*sheep+1*cabbage;for(int i=0;ik;i+)for(int j=0;jk;j+)fwscij=1;fwscji=1;public void dfstraverse()

19、route=new booleank;for(int i=0;ik;i+)if(routei=false)dfs(i);public void dfs(int i)routei=true;system.out.println(vertexi);for(int j=0;jk;j+)if(fwscij=1&routej=false)dfs(j);public static void main(string args)farmerprocedure temp=new farmerprocedure();system.out.println(過河情況);temp.graph();temp.dfstra

20、verse();2、求二叉樹葉子結(jié)點(diǎn)個數(shù)源代碼遞歸算法：#includeint count=0;struct binodechar c;binode *lchild,*rchild;class bitreepublic: bitree(); bitree(); binode* getroot(); void preorder(binode *root); void inorder(binode *root); void postorder(binode *root); void countleaf(binode *root); void release(binode *root); binod

21、e *getroot()return root;private: binode *root; binode *creat(); ;bitree:bitree() root=creat(); binode *bitree:creat() binode *root; char ch;cinch;if(ch=#) return null;else root=new binode;root-c=ch; root-lchild=creat(); root-rchild=creat();return root;bitree:bitree ()release(root);void bitree:releas

22、e (binode *root)if(root!=null)release(root-lchild );release(root-rchild );delete root;void bitree:preorder(binode *root)if(root=null) return;elsecoutclchild);preorder(root-rchild);void bitree:inorder(binode *root)if(root=null) return;else inorder(root-lchild);coutcrchild);void bitree:postorder(binod

23、e *root)if(root=null) return;else postorder(root-lchild);postorder(root-rchild);coutclchild=null&root-rchild=null) count+; countleaf(root-lchild); countleaf(root-rchild);binode* bitree:getroot( )return root;void main() cout 請輸入二叉樹的結(jié)點(diǎn)數(shù)據(jù): ; bitree b;binode *root = b.getroot( ); /獲取指向根結(jié)點(diǎn)的指針cout前序遍歷 ：;

24、b.preorder(root);coutendl;cout中序遍歷 ： ; b.inorder(root);coutendl;cout后序遍歷 ：; b.postorder(root);coutendl;cout該二叉樹的葉子結(jié)點(diǎn)數(shù)為:;b.countleaf(root);coutcountendl;coutdata = ch; creattree(&(*t)-lchild); creattree(&(*t)-rchild); void countleaf(bittree bt) stack s; s = (stack)malloc(sizeof(struct stack); s-top =

25、 0; while(bt != null|s-top != 0) if(bt != null) printf(%2c,bt-data); s-maxsizes-top = bt; s-top+; bt=bt-lchild; else bt=s-maxsizes-top-1; s-top-; if(bt-rchild = null & bt-lchild = null) count+; bt=bt-rchild; void main() bittree t; printf(請輸入二叉樹的數(shù)據(jù)：); creattree(&t); printf(前序輸出為：); countleaf(t); prin

26、tf(n); printf(%d,count); printf(n); 3、哈夫曼算法源代碼#include #include #include #include #include using namespace std;struct headunsigned char b; long count; int parent,lch,rch; char bits256; header512,tmp; unsigned char ctoa(char a) unsigned char c=0;for(int i=0;i8;i+)if(ai!=0)c=c+(int)(ai-0)*pow(2,8-1-i)

27、;return c;char *code(unsigned char temp,int leafnum) for(int i=0;ileafnum;i+)if(temp=headeri.b)return headeri.bits;return null;void yasuo(char *name,char *name1)long flength=0; long clength=8; int leafnum; int pointnum; unsigned char temp; for(int i=0;i256;i+)headeri.count=0;headeri.b=(unsigned char

28、)i; ifstream infile(name,ios:in|ios:binary);while(infile.peek()!=eof)infile.read(char *)&temp,sizeof(unsigned char); headertemp.count+; flength+; infile.close(); for(i=0;i256-1;i+) for(int j=0;j256-1-i;j+)if(headerj.countheaderj+1.count)tmp=headerj;headerj=headerj+1;headerj+1=tmp;for(i=0;i256;i+)if(

29、headeri.count=0) break；leafnum=i; pointnum=2*leafnum-1; long min; int s1,s2;for(i=leafnum;ipointnum;i+) min=999999999; for(int j=0;ji;j+) if(headerj.parent=0&headerj.countmin)min=headerj.count;s1=j;headers1.parent=i; min=999999999;for(j=0;ji;j+) if(headerj.parent=0&headerj.countmin)min=headerj.count

30、;s2=j;headers2.parent=i;headeri.count=headers1.count+headers2.count; headeri.lch=s1;headeri.rch=s2;char tmp256; tmp255=0; int start;int c; int f; for(i=0;i=8) temp=ctoa(buf);outfile.write(char *)&temp,sizeof(unsigned char); clength+; strcpy(buf,buf+8); if(strlen(buf)0)strcat(buf,0000000);temp=ctoa(b

31、uf); outfile.write(char *)&temp,sizeof(unsigned char);clength+; outfile.seekp(4);outfile.write(char *)&clength,sizeof(long); infile.close(); long bytelen; outfile.clear();outfile.seekp(clength); outfile.write(char *)&leafnum,sizeof(long); for(i=0;ileafnum;i+)outfile.write(char *)&headeri.b,sizeof(un

32、signed char); headeri.count=strlen(headeri.bits); outfile.write(char *)&headeri.count,sizeof(unsigned char);if(headeri.count%8=0) bytelen=headeri.count/8;else bytelen=headeri.count/8+1;strcat(headeri.bits,0000000);for(int j=0;jbytelen;j+)temp=ctoa(headeri.bits);outfile.write(char *)&temp,sizeof(unsi

33、gned char);strcpy(headeri.bits,headeri.bits+8); cout該文件字符對應(yīng)的哈夫曼的編碼為:endl;for(i=0;iflength;i+)coutheaderi.bitsendl;void ctoa(unsigned char a,char code) int n=9;for(int i=0;i0)coden-=c%2+0;c=c/2;int strcmp1(char buf,struct head head,int n,unsigned char &c)for(int i=0;in;i+)if(strcmp(buf,headi.bits)=0)

34、c=headi.b;return 1;return 0;void strcpy1(char buf,char a,int j) for(int i=0;ij;i+)bufi=ai;bufi=0;void jieya(char *name,char *name1)long flength; long clength; int n; string str; char code9; unsigned char temp; long readlen=0; long writelen=0; long clen; void ctoa(unsigned char a,char code);ifstream

35、infile(name,ios:binary);if(!infile) cerr文件打開失敗endl;return;infile.read(char *)&flength,sizeof(long); infile.read(char *)&clength,sizeof(long); infile.seekg(clength);infile.read(char *)&n,sizeof(int); infile.seekg(clength+4); for(int i=0;in;i+) infile.read(char *)&headeri.b,sizeof(unsigned char); infile.read(char *)&headeri.count,sizeof(unsigned char); clen=(int)headeri.count;int diff=clen%8;if(0=clen%8) cle