《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告書(shū)123

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告報(bào)告（論文）題目：1.迷宮問(wèn)題2.哈夫曼編碼作者姓名：作者學(xué)號(hào)：指導(dǎo)教師姓名:《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告書(shū)2.1輸入/輸出形式和輸出值的范圍（1） 迷宮定義外圍為1,作為墻壁，內(nèi)部用0、1輸入，0表示有可走，1表示不可走。入口默認(rèn)為左上角，出口默認(rèn)為右下角。（2） 哈夫曼編碼，輸入信息以加載存檔的reading.txt文件為方式，加載不成功，提示出錯(cuò)信息，加載成功后，系統(tǒng)對(duì)其編碼，并按照選擇對(duì)各種相關(guān)信息存檔。2.2程序功能（1） 迷宮問(wèn)題在迷宮問(wèn)題中，可由操作者自己輸入迷宮的大小，系統(tǒng)會(huì)對(duì)輸入的數(shù)據(jù)進(jìn)行判斷其合法性，如不正確，系統(tǒng)會(huì)有提示語(yǔ)句，讓操作者重新輸入。最后輸出一條迷宮的出路。（2） 哈夫曼編碼問(wèn)題可以讀入操作者存在指定文件里的信息，并對(duì)其進(jìn)行哈夫曼編碼以及將編碼信息存檔。2.3測(cè)試數(shù)據(jù)2.3.1正確的輸入及輸出結(jié)果（1）迷宮問(wèn)題：在生成迷宮后，將迷宮路徑輸出，如圖2-1所示:產(chǎn)生隨機(jī)迷宮.吾:輸出可行的所有路徑.季退出為>ir{pMpwpMp^p^!pwp^!p^pev!p^pMpwp^!p^p^!p^p^!p^p^!p^f^ ^p^p^sp^p^sp^p^sp^p^請(qǐng)輸入操作代碼：1輸入迷宮太小（行數(shù),列數(shù)）:"產(chǎn)生RS機(jī)迷宮成功：1oo-uoo011oo-uoo1：0I11*1：產(chǎn)生Sfi機(jī)迷宮.吾:輸出可行的所有路徑歹1出聲'I請(qǐng)輸入操作代碼：2第1條可行路徑：（ugii1,3-02n13|2j第2條可行路徑：（1；1）K2,1）I（過(guò)I3我A迷宮共有2條可行路徑圖2-1迷宮的正確輸入、輸出結(jié)果截圖（2）哈夫曼編碼問(wèn)題：在讀入文件信息后，對(duì)文件進(jìn)行編碼，并顯示編碼規(guī)則等信息，如圖2-2所示：幻：從文件讀取信息2：顯示編碼規(guī)則 /將原文件信息寫(xiě)進(jìn)文件 ?荒祉將編碼規(guī)則寫(xiě)進(jìn)文件5：將編碼后的信息寫(xiě)進(jìn)文件&將譯碼后的信息寫(xiě)進(jìn)文件7：退出米.請(qǐng)輸入操作代碼E1讀取文件成功幻『從文件讀取信息 '%顯示編碼規(guī)則 安'潮原文件信息寫(xiě)進(jìn)文件M：將編碼規(guī)則寫(xiě)進(jìn)文件與將編碼后的信息寫(xiě)進(jìn)文件電將譯碼后的信息寫(xiě)進(jìn)文件7：退出*請(qǐng)輸入操作代碼：2I11111110a10m1111110s111110t0umwdmoe110n111111112.3.2錯(cuò)誤的輸入及輸出結(jié)果迷宮問(wèn)題：在輸出迷宮的可行路徑前，需要先生成迷宮。因此，在未生成迷宮時(shí)輸入“輸出可行路徑”的命令時(shí)，將提示出錯(cuò)信息，如圖2-3所示：￥1：產(chǎn)生隨機(jī)迷宮2Y輸出可行的所有路徑&退出漿 r請(qǐng)輸入操作代碼：2 :￡未產(chǎn)生隨機(jī)迷宮，請(qǐng)先生成隨機(jī)迷宮圖2-3測(cè)迷宮的錯(cuò)誤輸入、輸出結(jié)果截圖哈夫曼編碼問(wèn)題：在進(jìn)行編碼、譯碼及存儲(chǔ)編碼規(guī)則和編碼、譯碼后的信息前，需要先讀取文件信息，因此，在未讀取文件信息時(shí)，輸入“顯示編碼規(guī)則”等命令時(shí)，會(huì)提示出錯(cuò)：如圖2-4所示：幻：從文件讀取信息-2：顯示編碼規(guī)則 &將原文件信息寫(xiě)進(jìn)文件 M：將編碼規(guī)則寫(xiě)進(jìn)文件5：將編碼后的信息寫(xiě)進(jìn)文件6：將譯碼后的信息寫(xiě)進(jìn)文件7：退出*」請(qǐng)輸入操作代碼：2請(qǐng)先從文件中讀取信息！圖2-4哈夫曼的錯(cuò)誤輸入、輸出結(jié)果截圖第3章概要設(shè)計(jì)3.1設(shè)計(jì)思想用二維數(shù)組來(lái)表示迷宮，用棧來(lái)保存走過(guò)的路徑和方向，用一結(jié)構(gòu)體存儲(chǔ)方向。哈夫曼樹(shù)用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)，借助靜態(tài)鏈表來(lái)實(shí)現(xiàn)遍歷。3.2函數(shù)間的關(guān)系(1)迷宮問(wèn)題，函數(shù)間的關(guān)系，如圖3-1所示：圖3-1迷宮問(wèn)題中函數(shù)間的關(guān)系(2)哈夫曼系統(tǒng)，函數(shù)間的關(guān)系如圖3-2所示:第4章詳細(xì)設(shè)計(jì)4.1迷宮的主要結(jié)構(gòu)結(jié)構(gòu)定義如下：#defineMAXSIZE100typedefstruct{intx,y,d;}Datatype;〃棧中元素類型定義typedefstruct{Datatypedata[MAXSIZE*MAXSIZE];inttop;}Seqstack;〃棧定義typedefstruct{intx;inty;}zuobiao;〃元素坐標(biāo)定義Seqstack*s1,*s2;//定義兩個(gè)棧方便按順序輸出棧中元素Datatypeitem;//定義臨時(shí)坐標(biāo)intnumber;//定義可行路徑條數(shù)intmaze[MAXSIZE][MAXSIZE];//定義迷宮數(shù)組各功能函數(shù)的聲明及說(shuō)明如下：Seqstack*Init_Seqstack();棧初始化voidPush_Seqstack(Seqstack*s,Datatypeitem);入棧voidPop_Seqstack(Seqstack*s,Datatype*item);出棧voidInit_Move(zuobiaomove[4]);Move[]方向數(shù)組初始化voidInit_Maze(intm,intn);產(chǎn)生隨機(jī)迷宮voidoutput(intm,intn);顯示迷宮voidMaze(zuobiaomove[4],intm,intn,intmark);搜索迷宮路徑voidresult(Seqstack*s);輸出迷宮路徑4.2哈夫曼的主要結(jié)構(gòu)(1)結(jié)構(gòu)定義：#defineMAXVALUE1000//定義最大權(quán)值#defineMAXBIT100//定義哈夫曼樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)typedefstruct{chardata;//字符值intnum;//某個(gè)值的字符出現(xiàn)的次數(shù)}TotalNode;〃統(tǒng)計(jì)結(jié)點(diǎn)，包括字符種類和出現(xiàn)次數(shù)typedefstruct{TotalNodetot[300];//統(tǒng)計(jì)結(jié)點(diǎn)數(shù)組intnum;//統(tǒng)計(jì)數(shù)組中含有的字符個(gè)數(shù)}Total;〃統(tǒng)計(jì)結(jié)構(gòu)體，包括統(tǒng)計(jì)數(shù)組和字符種類數(shù)typedefstruct{charmes[300];//字符數(shù)組intnum;//總字符數(shù)}Message;〃信息結(jié)構(gòu)體，包括字符數(shù)組和總字符數(shù)typedefstruct{intlocked[500];//密碼數(shù)組intnum;//密碼總數(shù)}Locking;〃哈夫曼編碼后的密文信息typedefstruct{chardata;//字符intweight;//權(quán)值intparent;//雙親結(jié)點(diǎn)在數(shù)組HuffNode[]中的序號(hào)intlchild;//左孩子結(jié)點(diǎn)在數(shù)組HuffNode[]中的序號(hào)intrchild;//右孩子結(jié)點(diǎn)在數(shù)組HuffNode[]中的序號(hào)}HNodetype;〃哈夫曼樹(shù)結(jié)點(diǎn)類型，包括左右孩子，權(quán)值和信息typedefstruct{intbit[MAXBIT];intstart;}HCodetype;〃哈夫曼編碼結(jié)構(gòu)體，包括編碼數(shù)組和起始位(2)主要函數(shù)聲明及功能描述如下：voidreading_file(Message*message);從文件中讀取信息voidwriting_file(Message*message);將信息寫(xiě)進(jìn)文件voidtotal_message(Message*message,Total*total);統(tǒng)計(jì)信息中各字符的出現(xiàn)次數(shù)voidHaffmanTree(Total*total,HNodetypeHuffNode[]);構(gòu)建哈夫曼樹(shù)voidHaffmanCode(HNodetypeHuffNode[],HCodetypeHuffCode[],Total*total);建立哈夫曼編碼voidwriting_HCode(HNodetypeHuffNode[],HCodetypeHuffCode[],Total*total);將編碼規(guī)則寫(xiě)進(jìn)文件voidlock(Message*message,HNodetypeHuffNode[],HCodetypeHuffCode[],Total*total,Locking^locking);給文件信息加密編碼voidwriting_lock(Locking*locking);將已編碼信息寫(xiě)進(jìn)文件voidwriting_translate(Locking*locking,HCodetypeHuffCode[],HNodetypeHuffNode[],Total*total);將已編碼信息翻譯過(guò)來(lái)并寫(xiě)進(jìn)文件第5章調(diào)試分析5.1問(wèn)題描述（1） 用什么樣的儲(chǔ)存方式。（2） 考慮棧和隊(duì)列對(duì)迷宮探究的不同。5.2解決方案（1） 采用靜態(tài)鏈表儲(chǔ)存。（2） 棧是先進(jìn)后出，隊(duì)列是先進(jìn)先出。5.3對(duì)設(shè)計(jì)實(shí)現(xiàn)的回顧討論和分析程序使用了文件來(lái)編碼和譯碼，創(chuàng)建哈夫曼樹(shù)并用層次遍歷輸出，把編碼后的信息存入文件并譯碼，再輸出并保存。系統(tǒng)二是對(duì)迷宮問(wèn)題探究的系統(tǒng)，其核心思想用棧是實(shí)現(xiàn)對(duì)迷宮通路的求解。該過(guò)程中應(yīng)用了棧的先進(jìn)后出的特點(diǎn)去探究路徑，保存后輸出。建立了數(shù)組實(shí)現(xiàn)迷宮的虛擬化，用move[]數(shù)組來(lái)指示求路徑時(shí)的方向。5.4對(duì)算法的分析和改進(jìn)設(shè)想（1） 功能不是很強(qiáng)大，對(duì)錯(cuò)誤字符編碼但不輸出，要能輸入入口坐標(biāo)。（2） 棧和隊(duì)列是受限制的線性表，是軟件中常用的兩種數(shù)據(jù)結(jié)構(gòu)，可以很方便的對(duì)它們進(jìn)行操作。還可改進(jìn)成更為簡(jiǎn)潔、靈活的程序。5.5經(jīng)驗(yàn)和體會(huì)（1） 編程時(shí)要認(rèn)真，出現(xiàn)錯(cuò)誤要及時(shí)找出并改正，遇到問(wèn)題要去查相關(guān)的資料。反復(fù)的調(diào)試程序，把各個(gè)注意的問(wèn)題要想到；同時(shí)要形成自己的調(diào)試程序的風(fēng)格，從每個(gè)細(xì)節(jié)出發(fā)，不放過(guò)每個(gè)知識(shí)點(diǎn)。另外，要注意符號(hào)的使用。（2） 通過(guò)此次課設(shè)我學(xué)到了好多東西，以前會(huì)的知識(shí)更加熟悉了，而且有了更深的認(rèn)識(shí)；不太清楚的知識(shí)點(diǎn)也有了新的理解。

第6章測(cè)試并列出測(cè)試結(jié)果6.1迷宮問(wèn)題測(cè)試結(jié)果選擇“產(chǎn)生隨機(jī)迷宮，，，輸入迷宮的行數(shù)和列數(shù)，生成隨機(jī)迷宮，如圖6-1所示:*T：產(chǎn)生隨機(jī)迷宮2;輸出可行的所有路徑2退出*請(qǐng)輸入操作代碼：1輸入迷宮大小W行數(shù)i列數(shù)).；54產(chǎn)生隨切迷宮成功：111O11O1oO一―一―-on-一―oooO-11：0i1i0■:1：圖6-1產(chǎn)生隨機(jī)迷宮截圖選擇“輸出可行的所有路徑”，輸出迷宮的可行路徑條數(shù)及每條路徑所經(jīng)過(guò)的點(diǎn)，點(diǎn)用坐標(biāo)形式表示，方向用箭頭指明，如圖6-2所示:、.十、.十、.十、.十、"t：產(chǎn)生隨機(jī)迷宮輸出可行的所有路徑3退出'請(qǐng)輸入操作代碼：藝第1條可行路徑：(1,1.)1(2,1.)1(瀏)f(：3留)1(4,2)-(4,<01(5.箴)一第2條可行路徑：〈1,1)1(玲)」3,1)1(4,1)-C4?2T戚)I(5覆)-迷宮共有2條可行路徑圖6-2輸出迷宮所有路徑截圖6.2哈夫曼系統(tǒng)測(cè)試結(jié)果選擇“從文件讀取信息”，程序?qū)奈募x取信息，如果讀取失敗（不存在該信息文件），則結(jié)束，如果讀取成功，則輸出讀取成功的提示信息，如圖6-3及圖6-4所示：玨從文件iUft息 2：顯示編礙規(guī)則 3：將原文件信息寫(xiě)進(jìn)文件*燭將■編隔規(guī)則寫(xiě)述文件5：將編碼后的信息寫(xiě)進(jìn)文件6：將譯碼后的信息寫(xiě)進(jìn)文件7：退蝌'上"土\L*"J/1?'**L\L**土'，1'*\L*r~J/r'JL'hl"\L*°￡‘**L ，JL‘**L\L* \L**%!?*值'**卜\L**‘即**上\L" \Li7Jz1，土『-上，』上，，晝.=■■,心*?】_』■?,上,日；laj》■［，，即,j.史,,史項(xiàng).土1，和.上 4:，'**?_!/4*1'***L"\L**史’「L%L-4/*4,.上*8土1 k七L*，i?%L、L*浦轆入操作代碼；1淮取文件成功圖6-3從文件讀取信息截圖?屆di面吁記事本Iamastudent圖6-4存放原信息的文檔reading.txt截圖選擇“顯示編碼規(guī)則”，則將信息編碼并輸出編碼規(guī)則，如圖6-5所示:<文件讀取信息2：顯示編碼規(guī)則 3；將原文件信息寫(xiě)進(jìn)文件?凌:料；將編碼規(guī)則寫(xiě)進(jìn)文件5：將編碼后的信息寫(xiě)進(jìn)文件6|將譯碼后的信息寫(xiě)進(jìn)文件7：退出*請(qǐng)輸入操作代碼：2I1111111。aWm111111。t0u1111。d111。e110n11111111圖6-5顯示編碼規(guī)則截圖選擇“將原文件信息寫(xiě)進(jìn)文件”，則將讀入內(nèi)存中的文件信息存儲(chǔ)到文檔writing.txt中，如圖6-6及圖6-7所示：「「葉、.中..■!■..，卞 -代 .中..■!■. .■!,..,(■..■(■. .■!■..■!■..,十■..，甲、.座、葉、可、葉、,■代外從文件讀取信息'%顯示編碼規(guī)則 3：將原文件信息寫(xiě)進(jìn)文件>|荊：將編碼規(guī)則寫(xiě)進(jìn)文件盡.將編碼后的信息寫(xiě)進(jìn)文件6：：將譯碼后的信息寫(xiě)進(jìn)文件7,...1出*葉■?押、■?押■?押、「.中、.中、汗、永 ■?押.中、.中、請(qǐng)輸入操作代碼：a t信息寫(xiě)進(jìn)文件成功圖6-6將原文件信息寫(xiě)入文件截圖|lamastudent 口|圖6-7存放原信息的文檔writing.txt截圖在讀入信息的前提下，選擇“將編碼規(guī)則寫(xiě)進(jìn)文件”，則對(duì)信息編碼并將編碼規(guī)則寫(xiě)入文檔HCode.txt中，如圖6-8及圖6-9所示：.十..-|■.--|■.-■!,..,!■■.■|,..■|-..十.--|■.--|,..中..■|,..■|,..十..十.--|■.-■!,..中..■|,..■|-..十..-|■.--|,..中..■!,■.■|,..■|-..十.--|■.--|,..中..■|,..■|,..十..-|■.--|■.-■!,..,!■■.■|,..■|-..十..-|■.--|,..中..■!,■.■|-..十..十.--|■.-■!,..中..■|,..■|,..十..-|■.--|■.-■!,..小*.■|,.幻：從文件讀取信息2：顯示編碼規(guī)則 尊將原文件信息寫(xiě)進(jìn)文件 米M：將編碼規(guī)則寫(xiě)進(jìn)文件5：將編碼后的信息寫(xiě)進(jìn)文件&將譯碼后的信息寫(xiě)進(jìn)文件7：退出來(lái)請(qǐng)輸入操作代碼：4編碼規(guī)則寫(xiě)進(jìn)文件成功圖6-8將編碼規(guī)則寫(xiě)入文件截圖祐藏匚匏事本 -FF文件E編輯E格式廷)查看如幫助但)||11111110 口a10m1111110s111110t0u11110d1110e110n11111111圖6-9存放編碼規(guī)則的文檔HCode.txt截圖選擇“將編碼后的信息寫(xiě)進(jìn)文件”，則對(duì)信息編碼并將編碼后的信息寫(xiě)入文檔locking.txt中，如圖6-10及圖6-11所示：小..■|,..十.--|,..■!■■.■|-..-|,..小..■|,..-|,..小..■|,..十.--|,..■!■■.■|-..-|,..小..■|-..-|,..小..■|,..十.--|,..■!■■.■|-..-|,..小..■|-..-|,..小..■|,..十.--|,..■!■■.■|-..-|,..小..■|-..-|,..小..■|,..十.--|,..■!■■.■|-..-|,..小..■|-..-|,..小..■|,..十.--|■.*1：從文件讀取信息2：顯示編碼規(guī)則 盅將原文件信息寫(xiě)進(jìn)文件 湄物：將編碼規(guī)則寫(xiě)進(jìn)文件巽將編碼后的信息寫(xiě)進(jìn)文件理將譯碼后的信息寫(xiě)進(jìn)文件宣退出*請(qǐng)輸入操作代碼：5已編碼信息寫(xiě)進(jìn)文件成功圖6-10將編碼后的信息寫(xiě)入文件截圖locking-,也事本[]史件E編輯E，格式回查看0幫助(H)|11111110101111110101111100111101110110111111110 ;圖6-11存放編碼后的信息的文檔locking.txt截圖選擇“將譯碼后的信息寫(xiě)進(jìn)文件”，則對(duì)編碼信息譯碼并將譯碼后的信息寫(xiě)入文檔translate.txt中，如圖6-12及圖6-13所示：初*從文件讀取信息?寵顯示編碼規(guī)則 與m將原文件信息寫(xiě)進(jìn)文件YM：將編碼規(guī)則寫(xiě)進(jìn)文件5：將編碼后的信息寫(xiě)進(jìn)文件?.：將譯碼后的信息寫(xiě)進(jìn)文件7：退出陽(yáng).中*中、*中、請(qǐng)輸入操作代碼庭6醐譯信息寫(xiě)進(jìn)文件成功圖6-12將譯碼后的信息寫(xiě)入文件截圖Iamastudent圖6-13存放譯碼信息的文檔translate.txt截圖第7章總結(jié)7.1設(shè)計(jì)體會(huì)7.1.1系統(tǒng)的優(yōu)點(diǎn)（1）特色：有完整的界面管理，清楚的信息提示，方便的執(zhí)行過(guò)程，嚴(yán)謹(jǐn)?shù)慕Y(jié)構(gòu)控制。7.1.2本系統(tǒng)的不足（1） 操作選擇中，對(duì)字符和整型間的輸入無(wú)法判斷，只能終止程序。迷宮問(wèn)題中，出入口為默認(rèn)，迷宮地圖為隨機(jī)生成，用戶無(wú)法自定義。哈弗曼問(wèn)題中，只能對(duì)存入文檔的信息進(jìn)行編碼、譯碼，且文件名及位置已指定，用戶無(wú)法進(jìn)行直接輸入。（2） 函數(shù)間的兼容性弱，結(jié)構(gòu)不明了，不便于改變參數(shù)和數(shù)據(jù)。（3） 程序代碼不夠簡(jiǎn)練，并且可讀性也不是很好。7.1.3可改進(jìn)的地方（1） 各個(gè)菜單界面可以設(shè)計(jì)的更為美觀，更簡(jiǎn)潔易懂。（2） 可以從各個(gè)方面考慮設(shè)置容錯(cuò)機(jī)制使程序更健壯。7.2結(jié)束語(yǔ)通過(guò)將近兩周的課設(shè)練習(xí)，認(rèn)識(shí)到知識(shí)的遷移運(yùn)用，理論應(yīng)用實(shí)際和相互間的密切聯(lián)系，感受到理論知識(shí)的重要，在今后的學(xué)習(xí)中一定會(huì)更加努力，認(rèn)真。體會(huì)到自己知識(shí)有所缺乏，和個(gè)人能力的有限，只有通過(guò)同學(xué)、老師間的密切配合才能完成一項(xiàng)不錯(cuò)的工作。從中也體會(huì)到了學(xué)習(xí)中的樂(lè)趣，可以自由的創(chuàng)作自己喜歡的東西并自己調(diào)試。致謝在課程設(shè)計(jì)過(guò)程中遇到了很多問(wèn)題，不過(guò)在老師和和同學(xué)們的幫助下大部分都得以解決，首先要對(duì)他們表示感謝。同時(shí)，我們也要感謝學(xué)校為我們提供了大量的圖書(shū)，通過(guò)看書(shū)我們也學(xué)到了很多課堂上學(xué)不到的東西。通過(guò)此次課程設(shè)計(jì)我最大的收獲是學(xué)會(huì)了自主學(xué)習(xí)，也增加了與老師和同學(xué)們的交往、增進(jìn)了相互之間的感情。參考文獻(xiàn)嚴(yán)蔚敏，吳偉民.《數(shù)據(jù)結(jié)構(gòu)：C語(yǔ)言版》.北京：清華大學(xué)出版社，1997.劉國(guó)鈞、鄭如斯.《中國(guó)書(shū)的故事》.北京：中國(guó)青年出版社，1979.周靄如、林偉健.《C++程序設(shè)計(jì)基礎(chǔ)》.北京：電子工業(yè)出版社.耿國(guó)華.《數(shù)據(jù)結(jié)構(gòu)》.北京：高等教育出版社，2005.姚伯元.《課程設(shè)計(jì)（論文）規(guī)范化管理與培養(yǎng)學(xué)生綜合素質(zhì)》.中國(guó)高等教育網(wǎng)教學(xué)研究，2005.附錄附錄1:迷宮問(wèn)題源代碼：(1)頭文件head.h#defineMAXSIZE100typedefstruct{intx,y,d;}Datatype;〃棧中元素類型定義typedefstruct{Datatypedata[MAXSIZE*MAXSIZE];inttop;}Seqstack;//棧定義typedefstruct{intx;inty;}zuobiao;〃元素坐標(biāo)定義Seqstack*s1,*s2;//定義兩個(gè)棧方便按順序輸出棧中元素Datatypeitem;//定義臨時(shí)坐標(biāo)intnumber;//定義可行路徑條數(shù)intmaze[MAXSIZE][MAXSIZE];//定義迷宮數(shù)組Seqstack*Init_Seqstack();//棧初始化voidPush_Seqstack(Seqstack*s,Datatypeitem);//入棧voidPop_Seqstack(Seqstack*s,Datatype*item);//出棧voidInit_Move(zuobiaomove[4]);//MOVE方向數(shù)組初始化voidInit_Maze(intm,intn);//產(chǎn)生隨機(jī)迷宮voidoutput(intm,intn);//顯示迷宮voidMaze(zuobiaomove[4],intm,intn,intmark);//搜索迷宮路徑voidresult(Seqstack*s);//輸出迷宮路徑(2)源文件source.cpp#include"head.h"#include<iostream>#include<time.h>#include<stdlib.h>usingnamespacestd;intmain(){intm,n,mm,nn,mark=0;zuobiaomove[4];//定義方向數(shù)組，包含上、下、左、右四個(gè)方向Init_Move(move);//MOVE方向數(shù)組初始化s1=Init_Seqstack();//棧1初始化s2=Init_Seqstack();//棧2初始化while(1){intchoice;一一一一 coutvv*************************************************vvendl：coutvv"*1：產(chǎn)生隨機(jī)迷宮2：輸出可行的所有路徑3退出*"vvendl;一"一一 ■■coutvv*************************************************vvendl;coutvv"請(qǐng)輸入操作代碼：”；cin>>choice;switch(choice){case1:number=0;//可行路徑條數(shù)初始化coutvv"輸入迷宮大小(行數(shù)，列數(shù))：":cin>>mm>>nn;//輸入迷宮行列數(shù)if(mm>25lln>25)coutvv"迷宮地圖太大，無(wú)法生成"vvendl;elseif(mmv1llnnv1)coutvv"參數(shù)錯(cuò)誤，無(wú)法生成迷宮"vvendl;else{m=mm+2;n=nn+2;mark=-1;//mark初始化while(number==0)//直到找到所有迷宮的可行路徑為止{Init_Maze(m,n);//產(chǎn)生隨機(jī)迷宮Maze(move,m,n,mark);//搜索迷宮可行路徑}cout<<"產(chǎn)生隨機(jī)迷宮成功："<<endl;output(m,n);//顯示迷宮cout<<endl;}break;case2:number=0;//可行路徑條數(shù)初始化if(mark==0)cout<<"未產(chǎn)生隨機(jī)迷宮，請(qǐng)先生成隨機(jī)迷宮"<<endl;else{mark=1;//mark賦值為1表示再次搜索路徑時(shí)輸出路徑Maze(move,m,n,mark);//搜索路徑并輸出可行路徑coutvv"迷宮共有"vvnumbervv"條可行路徑"<<endl;cout<<endl;}break;case3:exit(1);default:coutvv"輸入錯(cuò)誤，請(qǐng)重新輸入"vvendl;}}return0;}Seqstack*Init_Seqstack(){Seqstack*s;s=newSeqstack;s->top=-1;returns;}〃棧初始化voidPush_Seqstack(Seqstack*s,Datatypeitem){s->top++;s->data[s->top].x=item.x;s->data[s->top].y=item.y;s->data[s->top].d=item.d;}//入棧voidPop_Seqstack(Seqstack*s,Datatype*item){(*item).x=s->data[s->top].x;(*item).y=s->data[s->top].y;(*item).d=s->data[s->top].d;s->top--;}//出棧voidInit_Move(zuobiaomove[4]){move[0].x=0;move[0].y=1;//向右move[1].x=1;move[1].y=0;//向下move[2].x=0;move[2].y=-1;〃向左move[3].x=-1;move[3].y=0;//向上}//MOVE方向數(shù)組初始化voidInit_Maze(intm,intn){inti,j;srand((unsigned)time(NULL));for(i=0;i<m;i++)//對(duì)迷宮數(shù)組遍歷for(j=0;j<n;j++){if(i=0||i=m-1llj=0llj=n-1)//迷宮外圍墻壁maze[i][j]=1;elsemaze[i][j]=rand()%2;//產(chǎn)生0或1的隨機(jī)數(shù)}maze[m-2][n-2]=0;//出口可行maze[1][1]=-1;//入口不可重復(fù)}〃產(chǎn)生隨機(jī)迷宮，左上角為入口，右下角為入口voidMaze(zuobiaomove[4],intm,intn,intmark){intx,y,d,i,j;item.x=item.y=1;//初始化入口坐標(biāo)item.d=-1;Push_Seqstack(s1,item);while(s1->top!=-1)//?？談t搜索完畢，否則繼續(xù)搜索{Pop_Seqstack(s1,&item);if(item.d!=-1)maze[item.x+move[item.d].x][item.y+move[item.d].y]=0;x=item.x;y=item.y;d=item.d+1;while(d<4)//每個(gè)節(jié)點(diǎn)的四個(gè)方向均搜索一遍{i=x+move[d].x;j=y+move[d].y;if(maze[i][j]=0)//下一個(gè)節(jié)點(diǎn)可行{item.x=x;item.y=y;item.d=d;Push_Seqstack(s1,item);//壓入棧中x=i;y=j；maze[x][y]=-1;//表示已經(jīng)走過(guò)的路徑，以防重復(fù)if(x==m-2&&y==n-2)//輸出迷宮路徑并且搜索下條可行路徑{number++;//可行路徑條數(shù)加1maze[x][y]=0;//初始化終點(diǎn)坐標(biāo)if(mark==1)result(s1);//輸出可行路徑d++;x=s1->data[s1->top].x;y=s1->data[s1->top].y;}elsed=0;//方向初始化}elsed++;//從下一個(gè)方向開(kāi)始}}}〃搜索迷宮路徑voidresult(Seqstack*s1){cout<<"第"<<number<<"條可行路徑："<<endl;while(s1->top!=-1)//將棧1中路徑倒入棧2{Pop_Seqstack(s1,&item);//出棧1Push_Seqstack(s2,item);//入棧2}while(s2->top!=-1)//將棧2中路徑倒入棧1，同時(shí)輸出路徑順序{Pop_Seqstack(s2,&item);〃出棧2cout<<"("<<item.x<<","<<item.y<<")";if(item.d==0)cout<<"f";if(item.d==1)cout<<"I";if(item.d==2)cout<<"";if(item.d==3)cout<<"t";Push_Seqstack(s1,item);//入棧1}cout<<endl;}〃輸出迷宮路徑voidoutput(intm,intn){inti,j;for(i=0;i<m;i++){for(j=0;j<n;j++){if(maze[i][j]==-1)maze[i][j]=0;//恢復(fù)迷宮cout<<maze[i][j]<<"";//顯示迷宮}cout<<endl;}}〃顯示迷宮附錄2：哈夫曼編碼問(wèn)題源代碼：(1)頭文件head.h#defineMAXVALUE1000//定義最大權(quán)值#defineMAXBIT100//定義哈夫曼樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)typedefstruct{chardata;//字符值intnum;//某個(gè)值的字符出現(xiàn)的次數(shù)}TotalNode;〃統(tǒng)計(jì)結(jié)點(diǎn)，包括字符種類和出現(xiàn)次數(shù)typedefstruct{TotalNodetot[300];//統(tǒng)計(jì)結(jié)點(diǎn)數(shù)組intnum;//統(tǒng)計(jì)數(shù)組中含有的字符個(gè)數(shù)}Total;〃統(tǒng)計(jì)結(jié)構(gòu)體，包括統(tǒng)計(jì)數(shù)組和字符種類數(shù)typedefstruct{charmes[300];//字符數(shù)組intnum;//總字符數(shù)}Message;〃信息結(jié)構(gòu)體，包括字符數(shù)組和總字符數(shù)typedefstruct{intlocked[500];//密碼數(shù)組intnum;//密碼總數(shù)}Locking;〃哈夫曼編碼后的密文信息typedefstruct{chardata;//字符intweight;//權(quán)值intparent;//雙親結(jié)點(diǎn)在數(shù)組HuffNode[]中的序號(hào)intlchild;//左孩子結(jié)點(diǎn)在數(shù)組HuffNode[]中的序號(hào)intrchild;//右孩子結(jié)點(diǎn)在數(shù)組HuffNode[]中的序號(hào)}HNodetype;〃哈夫曼樹(shù)結(jié)點(diǎn)類型，包括左右孩子，權(quán)值和信息typedefstruct{intbit[MAXBIT];intstart;}HCodetype;〃哈夫曼編碼結(jié)構(gòu)體，包括編碼數(shù)組和起始位voidreading_file(Message*message);//從文件中讀取信息voidwriting_file(Message^message);//將信息寫(xiě)進(jìn)文件voidtotal_message(Message*message,Total*total);//統(tǒng)計(jì)信息中各字符的次數(shù)voidHaffmanTree(Total*total,HNodetypeHuffNode[]);//構(gòu)建哈夫曼樹(shù)voidHaffmanCode(HNodetypeHuffNode[],HCodetypeHuffCode[],Total*total);//建立哈夫曼編碼voidwriting_HCode(HNodetypeHuffNode[],HCodetypeHuffCode[],Total*total);//將編碼規(guī)則寫(xiě)進(jìn)文件voidlock(Message*message,HNodetypeHuffNode[],HCodetypeHuffCode[],Total*total,Locking^locking);//給文件信息加密編碼voidwriting_lock(Locking*locking);//將已編碼信息寫(xiě)進(jìn)文件voidwriting_translate(Locking*locking,HCodetypeHuffCode[],HNodetypeHuffNode[],Total*total);//將已編碼信息翻譯過(guò)來(lái)并寫(xiě)進(jìn)文件(2)源文件source.cpp#include"head.h”#include<iostream>#include<fstream>usingnamespacestd;intmain(){inti,j,choice,mark=0;//mark標(biāo)記文件信息是否讀入到內(nèi)存中HNodetypeHuffNode[500];//保存哈夫曼樹(shù)中各結(jié)點(diǎn)信息HCodetypeHuffCode[300];Locking^locking;Total*total;Message*message;locking=newLocking;locking->num=0;total=newTotal;total->num=0;message=newMessage;message->num=0;〃初始化變量while(1){J一-II“““““““““““““““““““““““““““““““““““““““““““““““““““““““““““11

cout<<***********************************************************;cout<<"*1:從文件讀取信息 2：顯示編碼規(guī)則 3：將原文件信息寫(xiě)進(jìn)文件*";cout<<"*4:將編碼規(guī)則寫(xiě)進(jìn)文件 5：將編碼后的信息寫(xiě)進(jìn)文件6：將譯碼后的信息寫(xiě)進(jìn)文件7：退出*";一"一一■■cout<<*****************************************************<<enQi:cout<<"請(qǐng)輸入操作代碼："；cin>>choice：switch(choice){case1:reading_file(message)：//從文件中讀取信息mark=1;break：case2://顯示編碼規(guī)則if(mark=0)cout<<"請(qǐng)先從文件中讀取信息!"<<endl：else{total_message(message,total)：//統(tǒng)計(jì)信息中各字符的出現(xiàn)次數(shù)HaffmanTree(total,HuffNode);//構(gòu)建哈夫曼樹(shù)HaffmanCode(HuffNode,HuffCode,total)：//建立哈夫曼編碼for(i=0：ivtotal->num：i++)//顯示編碼規(guī)則{coutvvtotal->tot[i].data<<”":for(j=HuffCode[i].start+1：j<total->num：j++)cout<<HuffCode[i].bit[j]：cout<<endl：}}break：case3://將原文件信息寫(xiě)進(jìn)文件if(mark=0)cout<<"請(qǐng)先從文件中讀取信息!"<<endl：elsewriting_file(message)：//將信息寫(xiě)進(jìn)文件break：case4://將編碼規(guī)則寫(xiě)進(jìn)文件if(mark=0)cout<<"請(qǐng)先從文件中讀取信息!"<<endl：else{total_message(message,total)：//統(tǒng)計(jì)信息中各字符的出現(xiàn)次數(shù)HaffmanTree(total,HuffNode);//構(gòu)建哈夫曼樹(shù)HaffmanCode(HuffNode,HuffCode,total);//建立哈夫曼編碼writing_HCode(HuffNode,HuffCode,total);//將編碼規(guī)則寫(xiě)進(jìn)文件}break;case5://將編碼后的信息寫(xiě)進(jìn)文件if(mark==0)cout<<"請(qǐng)先從文件中讀取信息!"<<endl;else{total_message(message,total);//統(tǒng)計(jì)信息中各字符的出現(xiàn)次數(shù)HaffmanTree(total,HuffNode);//構(gòu)建哈夫曼樹(shù)HaffmanCode(HuffNode,HuffCode,total);//建立哈夫曼編碼lock(message,HuffNode,HuffCode,total,locking);//給文件信息加密編碼writing_lock(locking);//將已編碼信息寫(xiě)進(jìn)文件}break;case6://將譯碼后的信息寫(xiě)進(jìn)文件if(mark==0)cout<<"請(qǐng)先從文件中讀取信息!"<<endl;else{total_message(message,total);//統(tǒng)計(jì)信息中各字符的出現(xiàn)次數(shù)HaffmanTree(total,HuffNode);//構(gòu)建哈夫曼樹(shù)HaffmanCode(HuffNode,HuffCode,total);//建立哈夫曼編碼writing_translate(locking,HuffCode,HuffNode,total);//將已編碼信息翻譯過(guò)來(lái)并寫(xiě)進(jìn)文件}break;case7:exit(1);default:cout<<"輸入錯(cuò)誤，請(qǐng)重新選擇"<<endl;}}for(i=0;i<locking->num;i++)if(locking->locked[i]==-1)cout<<"";elsecout<<locking->locked[i];cout<<endl;for(i=0;i<total->num;i++)cout<<total->tot[i].data<<""<<total->tot[i].num<<endl;for(i=0;i<2*(total->num)-1;i++)cout<<HuffNode[i].parent<<"";cout<<endl;return0;}voidreading_file(Message*message){/打開(kāi)reading文件，失敗則結(jié)束。不斷讀取字符并保存進(jìn)message數(shù)組中，直到遇到#結(jié)束，記錄字符總數(shù)*/inti=0;charch;ifstreaminfile("c:\\reading.txt”,ios::in|ios::out);if(!infile)//打開(kāi)失敗則結(jié)束{cout<<"打開(kāi)c:\\reading.txt文件失敗"<<endl;exit(1);}elsecout<<"讀取文件成功"<<endl;while(infile.get(ch)&&ch!='#')//讀取字符直到遇到#{message->mes[i]=ch;i++;}message->num=i;//記錄總字符數(shù)infile.close();//關(guān)閉文件}〃從文件中讀取信息voidwriting_file(Message^message)//將信息寫(xiě)進(jìn)文件{/*打開(kāi)writing文件，失敗則結(jié)束。將信息寫(xiě)進(jìn)文件*/inti;ofstreamoutfile("c:\\writing.txt”,ios::inlios::out);//打開(kāi)文件if(!outfile)//打開(kāi)失敗則結(jié)束{cout<<"打開(kāi)c:\\writing.txt文件失敗"<<endl;exit(1);}for(i=0;i<message->num;i++)//寫(xiě)文件outfile.put(message->mes[i]);cout<<"信息寫(xiě)進(jìn)文件成功"<<endl;outfile.close();//關(guān)閉文件}〃將原信息寫(xiě)入文件voidtotal_message(Message*message,Total*total){/*將message中的字符種類及出現(xiàn)次數(shù)統(tǒng)計(jì)保存到total數(shù)組中，重復(fù)字符用mark標(biāo)記，否則新建字符種類。記錄下字符種類的個(gè)數(shù)*/inti,j,mark;for(i=0;i<message->num;i++)//遍歷message中的所有字符信息{if(message->mes[i]!='')//字符不為空格時(shí){mark=0;for(j=0;j<total->num;j++)//在total中搜索當(dāng)前字符if(total->tot[j].data==message->mes[i])//搜索到，則此字符次數(shù)加1，mark標(biāo)志為1{total->tot[j].num++;mark=1;break;}if(mark==0)//未搜索到，新建字符種類，保存進(jìn)total中，字符類加1{total->tot[total->num].data=message->mes[i];total->tot[total->num].num=1;total->num++;}}}}〃統(tǒng)計(jì)信息中各字符的出現(xiàn)次數(shù)voidHaffmanTree(Total*total,HNodetypeHuffNode[]){/*通過(guò)每次選取最小和次小兩權(quán)值建立二叉樹(shù)，最終構(gòu)建成哈夫曼樹(shù)，且左孩子權(quán)值比右孩子小*/inti,j,min1,min2,x1,x2;for(i=0;i<2*(total->num)-1;i++)//初始化哈夫曼樹(shù)并存入葉子結(jié)點(diǎn)權(quán)值和信息{if(i<=total->num-1)HuffNode[i].data=total->tot[i].data;HuffNode[i].weight=total->tot[i].num;HuffNode[i].parent=-1;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;}for(i=0;i<total->num-1;i++){min1=min2=MAXVALUE;x1=x2=0;for(j=0;j<total->num+i;j++)//選取最小x1和次小x2的兩權(quán)值{if(HuffNode[j].parent==-1&&HuffNode[j].weight<min1){min2=min1;x2=x1;min1=HuffNode[j].weight;x1=j;elseif(HuffNode[j].parent==-1&&HuffNode[j].weight<min2)min2=HuffNode[j].weight;{x2習(xí)；}}HuffNode[x1].parent=total->num+i;//修改親人結(jié)點(diǎn)位置HuffNode[x2].parent=total->num+i;HuffNode[total->num+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;HuffNode[total->num+i].lchild=x1;//左孩子比右孩子權(quán)值小HuffNode[total->num+i].rchild=x2;}}〃構(gòu)建哈夫曼樹(shù)voidHaffmanCode(HNodetypeHuffNode[],HCodetypeHuffCode[],Total*total){/*在建立的哈夫曼樹(shù)基礎(chǔ)上，左分支為0,右分支為1,從葉結(jié)點(diǎn)向上直到根結(jié)點(diǎn)建立哈夫曼編碼，并保存每個(gè)葉結(jié)點(diǎn)起始位*/inti,j,c,p;HCodetypecd;for(i=0;i<total->num;i++)//建立葉子結(jié)點(diǎn)個(gè)數(shù)的編碼{cd.start=total->num-1;//起始位初始化p=HuffNode[i].parent;c=i;while(p!=-1)//從葉結(jié)點(diǎn)向上爬直到到達(dá)根結(jié)點(diǎn){if(HuffNode[p].lchild==c)//左分支則為0cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;//右分支則為1cd.start--;//起始位向前移動(dòng)c=p;p=HuffNode[p].parent;}for(j=cd.start+1;j<total->num;j++)//保存求出的每個(gè)葉結(jié)點(diǎn)編碼和起始位HuffCode[i].bit[j]=cd.bit[j];HuffCode[i].start=cd.start;}}〃建立哈夫曼編碼voidwriting_HCode(HNodetypeHuffNode[],HCodetypeHuffCode[],Total*total){/*打開(kāi)HCode文件，失敗則結(jié)束。將信息寫(xiě)進(jìn)文件*/inti,j;ofstreamoutfile("c:\\HCode.txt",ios::inlios::out);if(!outfile)//打開(kāi)失敗則結(jié)束{cout<<"打開(kāi)c:\\HCode.txt文件失敗"<<endl;exit(1);}for(i=0;ivtotal->num;i++)//寫(xiě)文件{outfile.put(HuffNode[i].data);outfile<<"";for(j=HuffCode[i