【正文】 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實習報告班 級：地信11102班 學生姓名： 任亮 學 號： 201101252 長江大學32 目 錄一、需求分析 1二、邏輯設(shè)計 2三、詳細設(shè)計 5四、程序編碼 9五、程序調(diào)試與測試 35六、結(jié)果分析 39 需求分析：程序一：單鏈表的應(yīng)用（1）要求生成線性表時，可以鍵盤上讀取元素。通過在鍵盤上輸入的數(shù)據(jù)構(gòu)造成單鏈表，進而對構(gòu)造成的單鏈表進行插入、刪除、遍歷等操作的實現(xiàn)。（2）限制條件是要求在生成線性表的時候，線性表中的元素是從鍵盤上輸入而不是自動生成，這樣就可以對自己想要進行的元素序列進行各種操作。程序二：二叉排序樹的操作（1）建立二叉樹，并輸出二叉樹的先序，中序和后序遍歷序列，以及二叉樹的葉子數(shù)。（2）要求根據(jù)讀取的元素建立二叉樹，能輸出各種遍歷。（3）可通過輸入帶空格的前序序列建立二叉鏈表。附加功能：輸出了二叉樹的深度。 程序三：哈夫曼編碼器（未嚴格依照要求）從鍵盤接受一串電文字符，輸出對應(yīng)的Huffman編碼。同時，能翻譯由Huffman編碼生成的代碼串，輸出對應(yīng)的電文字符串。 程序四：停車場管理設(shè)停車場是一個可以停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內(nèi)按車輛到達時間的先后順序，依次有北向南排列（大門在最南端，最先到達的第一車停放在車場的最北端），若車場內(nèi)已停滿n輛車，那么后來的車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內(nèi)某輛車要離開時，在它之后進入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。一、二叉樹的基本操作 邏輯設(shè)計：主函數(shù)二、單鏈表的基本操作三、哈夫曼編碼器四、停車場管理圖一、主函數(shù)總體設(shè)計功能一鏈表主函數(shù)頭插法建立單鏈表尾插法建立單鏈表鏈表元素的刪除單鏈表操作鏈表元素的插入輸出鏈表取單鏈表結(jié)點求單鏈表長度圖二、單鏈表的基本操作功能二求二叉樹的葉子節(jié)點數(shù)求二叉樹的深度二叉樹操作后序遍歷先序遍歷中序遍歷圖三、二叉樹的基本操作功能三哈夫曼編碼器編碼譯碼建立哈夫曼樹圖四、哈夫曼樹的基本操作功能四停車場管理系統(tǒng)車輛離開車輛進入列表顯示記錄信息打印發(fā)票返回上層車在車場車在車道圖五、停車場管理系統(tǒng) 詳細設(shè)計：單鏈表的操作（流程圖）圖六、單鏈表插入 圖七、單鏈表的刪除二叉樹的基本操作（流程圖）圖八、二叉樹的前序遍歷 圖九、二叉樹的中序遍歷圖十、二叉樹的后序遍歷 哈夫曼樹的詳細設(shè)計(1) 、構(gòu)造哈夫曼樹。根據(jù)Huffman算法：若已知有n個葉子節(jié)點，則構(gòu)造的huffman樹有2n1個結(jié)點。先輸入字符集中的n個字符（葉子節(jié)點）和表示其概率分布的權(quán)值，存儲在HuffNode型數(shù)組的前n個數(shù)組元素中。然后將2n1個結(jié)點的雙親和左右孩子均置為0。在所有的節(jié)點中，選取雙親為0，且具有最小權(quán)值m1和次小權(quán)值m2的兩個結(jié)點，用p1和p2指示這兩個結(jié)點在數(shù)組中的位置。將根為ht[p1]和ht[p2]的兩顆樹合并，使其成為新節(jié)點ht[i]的左右孩子，ht[i]的權(quán)值為最小權(quán)值m1和次小權(quán)值m2之和；ht[p1]和ht[p2]的雙親指向i。重復上述過程，共進行n1次合并就構(gòu)造了一顆Huffman樹。當進行n1次合并時，產(chǎn)生n1個結(jié)點，依次放在ht數(shù)組中，數(shù)組的下標從n到2n2。（2） 、編碼。基本思想：從Huffman樹的葉子節(jié)點ht[i]出發(fā)，通過雙親parent找到其雙親ht[f]，通過ht[f]的left和right域，可知ht[i]是ht[f]的左分支還是右分支，若是左分支，生成代碼0；若是右分支，生成代碼1，代碼存放在數(shù)組cd[start]中，然后把ht[f]作為出發(fā)點，重復上述過程，直到找到根節(jié)點為止。（3） 、譯碼?；舅枷耄菏紫容斎攵M制代碼串，存放在數(shù)組ch中，以“”為結(jié)束標志。接下來，將代碼與編碼表比較，如果為0，轉(zhuǎn)為左子樹；若為1，轉(zhuǎn)為右子樹，直到葉子節(jié)點結(jié)束，此時輸出葉子結(jié)點的數(shù)據(jù)域，即所對應(yīng)的字符。繼續(xù)譯碼，直到代碼結(jié)束。 停車場管理系統(tǒng)的詳細設(shè)計（1） 、模擬停車場車輛進出時需要輸入車輛的信息，包括車牌號碼以及進入和離開的時刻，因此可以定義一個時間節(jié)點類型和一個車輛信息結(jié)點類型，在順序棧及鏈式隊列中定義結(jié)點類型為車輛信息結(jié)點類型。（2） 、當車輛離開后，需要打印輸出車輛離開后的信息，如離開時間、離開時的所在位置和應(yīng)繳納的費用等，定義函數(shù)Print實現(xiàn)。（3） 、車輛到達時需要用戶輸入車輛的信息，接著要判斷棧是否已滿，如果當前站未滿，則進行入棧操作，即車輛進入停車場；如果棧已滿，則車輛必須進入便道等待。用函數(shù)Arrival實現(xiàn)。（4）、車輛的離開，則需要另設(shè)一個棧，給要離去的汽車讓路而從停車場退出來的汽車臨時停放，也用順序棧實現(xiàn)，車輛離開后需檢查便道內(nèi)是否有車等待，如有等待的車輛則進行便道內(nèi)的車輛進入停車場的操作，即將車輛信息結(jié)點進行入棧操作，輸入當前時間后開始計費，最后進行出棧操作，表示車輛離開便道以進入停車場。用函數(shù)Leave()實現(xiàn)。 程序編碼：（源碼）主函數(shù)include includeincludeincludeincludeinclude includeincludevoid main(){ int k。 char ch=39。y39。 while(ch==39。y39。) { printf(\t\t****歡迎進入我的課設(shè)工程****\n)。 printf(\t\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n)。 printf(\t如果碰到意外結(jié)束的情況或者排序不正確的情況\n\n)。 printf(\t\t 請及時聯(lián)系我 \n \n)。 printf(\t\t☆ 請選擇以下題目展示: ☆\n)。 printf(\t\t★ (★★★) ★\n)。 printf(\t\t★ (★★) ★\n)。 printf(\t\t★ (★★★) ★\n)。 printf(\t\t★ (★★★★★) ★\n)。 printf(\t\t★ ★\n)。 printf(\n\n\n)。 printf(請選擇(04)：)。 scanf(%d,amp。k)。 switch (k) { case 1: printf(您選擇的是二叉樹操作系統(tǒng)\n)。 Treemenu()。 break。 case 2: printf(您選擇進入的是單鏈表操作系統(tǒng)\n)。 LListmenu()。 break。 case 3:printf(您選擇進入的是哈夫曼樹編碼器\n)。 Huffmanmenu()。 break。 case 4:printf(您選擇的是停車場管理系統(tǒng)\n)。 Parkingmenu()。 break。 case 0: exit(0)。 default: printf(您的輸入有誤，請重新輸入！)。 } }}功能函數(shù) 二叉樹的操作頭文件typedef char DataType。define MAX 100typedef struct BiTNode//二叉鏈表數(shù)據(jù)結(jié)構(gòu)定義{ DataType data。 struct BiTNode *lchild,*rchild。 }BiTree。菜單函數(shù)includeincludeincludeint Treemenu()//(int argc,char *argv[]){ BiTree *tree。 int deep,sum。 printf(\t\t歡迎進入二叉樹基本操作系統(tǒng)\n\n\n)。 tree=Create()。 /* 建立二叉樹 */ deep=DepthPost(tree)。/* 求二叉樹高度 */ printf(\n1:輸出先序序列: )。 PreTra(tree)。 printf(\n2:輸出中序序列: )。 InTra(tree)。 printf(\n3:輸出后序序列: )。 PostTra(tree)。 printf(\n4:輸出二叉樹的高度：%d\n,deep)。 sum=LeafCount(tree)。 printf(\n5:輸出二叉樹的葉子節(jié)點：%d\n,sum)。 printf(\n操作結(jié)束！謝謝您的使用。\n)。 return 0。 }各個源文件子函數(shù)includeincludeincludeBiTree *Create()//非遞歸方法建立二叉鏈表{ BiTree *Q[MAX]。 DataType ch。 int front,rear。 BiTree *s,*root。 root=NULL。 front=1。