數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)習(xí)報(bào)告

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁(yè)數(shù)：33 大?。?63.50KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)習(xí)報(bào)告_第1頁(yè)

已閱讀1頁(yè)，還剩32頁(yè)未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)習(xí)報(bào)告　　目錄　　一、需求分析1　　二、邏輯設(shè)計(jì)2　　三、詳細(xì)設(shè)計(jì)5&

2、lt;/p>　　四、程序編碼9　　五、程序調(diào)試與測(cè)試35　　六、結(jié)果分析39　　需求分析：　　1、程序一：?jiǎn)捂湵淼膽?yīng)用<

3、;/p>　?。?）要求生成線性表時(shí)，可以鍵盤上讀取元素。通過在鍵盤上輸入的數(shù)據(jù)構(gòu)造成單鏈表，進(jìn)而對(duì)構(gòu)造成的單鏈表進(jìn)行插入、刪除、遍歷等操作的實(shí)現(xiàn)。　?。?）限制條件是要求在生成線性表的時(shí)候，線性表中的元素是從鍵盤上輸入而不是自動(dòng)生成，這樣就可以對(duì)自己想要進(jìn)行的元素序列進(jìn)行各種操作。　　2、程序二：二叉排序樹的操作</p&

4、gt;　?。?）建立二叉樹，并輸出二叉樹的先序，中序和后序遍歷序列，以及二叉樹的葉子數(shù)。　?。?）要求根據(jù)讀取的元素建立二叉樹，能輸出各種遍歷。　?。?）可通過輸入帶空格的前序序列建立二叉鏈表。　　附加功能：輸出了二叉樹的深度。　　程序三：哈夫曼編碼

5、器（未嚴(yán)格依照要求）　　從鍵盤接受一串電文字符，輸出對(duì)應(yīng)的Huffman編碼。同時(shí)，能翻譯由Huffman編碼生成的代碼串，輸出對(duì)應(yīng)的電文字符串。　　程序四：停車場(chǎng)管理　　設(shè)停車場(chǎng)是一個(gè)可以停放n輛汽車的狹長(zhǎng)通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)間的先后

6、順序，依次有北向南排列（大門在最南端，最先到達(dá)的第一車停放在車場(chǎng)的最北端），若車場(chǎng)內(nèi)已停滿n輛車，那么后來的車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場(chǎng)內(nèi)某輛車要離開時(shí)，在它之后進(jìn)入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開出大門外，其他車輛再按原次序進(jìn)入車場(chǎng)，每輛停放在車場(chǎng)的車在它離開停車場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。<p

7、>　　邏輯設(shè)計(jì)：　　圖一、主函數(shù)總體設(shè)計(jì)　　1、功能一　　圖二、單鏈表的基本操作　　2、功能二　　圖三、二叉樹

8、的基本操作　　3、功能三　　圖四、哈夫曼樹的基本操作　　4、功能四　　圖五、停車場(chǎng)管理系統(tǒng)　　詳細(xì)設(shè)計(jì)：</p

9、>　　1、單鏈表的操作（流程圖）　　圖六、單鏈表插入圖七、單鏈表的刪除　　2、二叉樹的基本操作（流程圖）　　圖八、二叉樹的前序遍歷圖九、二叉樹的中序遍歷　　圖十、二叉樹的

10、后序遍歷　　哈夫曼樹的詳細(xì)設(shè)計(jì)　　、構(gòu)造哈夫曼樹。　　根據(jù)Huffman算法：若已知有n個(gè)葉子節(jié)點(diǎn)，則構(gòu)造的huffman樹有2n-1個(gè)結(jié)點(diǎn)。　　先輸入字符集中的n個(gè)字符（葉子節(jié)點(diǎn)）和表示其概率分

11、布的權(quán)值，存儲(chǔ)在HuffNode型數(shù)組的前n個(gè)數(shù)組元素中。然后將2n-1個(gè)結(jié)點(diǎn)的雙親和左右孩子均置為0。　　在所有的節(jié)點(diǎn)中，選取雙親為0，且具有最小權(quán)值m1和次小權(quán)值m2的兩個(gè)結(jié)點(diǎn)，用p1和p2指示這兩個(gè)結(jié)點(diǎn)在數(shù)組中的位置。將根為ht[p1]和ht[p2]的兩顆樹合并，使其成為新節(jié)點(diǎn)ht[i]的左右孩子，ht[i]的權(quán)值為最小權(quán)值m1和次小權(quán)值m2之和；ht[p1]和ht[p2]的雙親指向i。重

12、復(fù)上述過程，共進(jìn)行n-1次合并就構(gòu)造了一顆Huffman樹。當(dāng)進(jìn)行n-1次合并時(shí)，產(chǎn)生n-1個(gè)結(jié)點(diǎn)，依次放在ht數(shù)組中，數(shù)組的下標(biāo)從n到2n-2。　　、編碼。　　基本思想：從Huffman樹的葉子節(jié)點(diǎn)ht[i]出發(fā)，通過雙親parent找到其雙親ht[f]，通過ht[f]的left和right域，可知ht[i]是ht

13、[f]的左分支還是右分支，若是左分支，生成代碼0；若是右分支，生成代碼1，代碼存放在數(shù)組cd[start]中，然后把ht[f]作為出發(fā)點(diǎn)，重復(fù)上述過程，直到找到根節(jié)點(diǎn)為止。　　、譯碼。　　基本思想：首先輸入二進(jìn)制代碼串，存放在數(shù)組ch中，以“#”為結(jié)束標(biāo)志。接下來，將代碼與編碼表比較，如果為0，轉(zhuǎn)為左子樹；若為1，轉(zhuǎn)

14、為右子樹，直到葉子節(jié)點(diǎn)結(jié)束，此時(shí)輸出葉子結(jié)點(diǎn)的數(shù)據(jù)域，即所對(duì)應(yīng)的字符。繼續(xù)譯碼，直到代碼結(jié)束。　　停車場(chǎng)管理系統(tǒng)的詳細(xì)設(shè)計(jì)　　、模擬停車場(chǎng)車輛進(jìn)出時(shí)需要輸入車輛的信息，包括車牌號(hào)碼以及進(jìn)入和離開的時(shí)刻，因此可以定義一個(gè)時(shí)間節(jié)點(diǎn)類型和一個(gè)車輛信息結(jié)點(diǎn)類型，在順序棧及鏈?zhǔn)疥?duì)列中定義結(jié)點(diǎn)類型為車輛信息結(jié)點(diǎn)類型。　　、當(dāng)

15、車輛離開后，需要打印輸出車輛離開后的信息，如離開時(shí)間、離開時(shí)的所在位置和應(yīng)繳納的費(fèi)用等，定義函數(shù)Print實(shí)現(xiàn)。　　、車輛到達(dá)時(shí)需要用戶輸入車輛的信息，接著要判斷棧是否已滿，如果當(dāng)前站未滿，則進(jìn)行入棧操作，即車輛進(jìn)入停車場(chǎng)；如果棧已滿，則車輛必須進(jìn)入便道等待。用函數(shù)Arrival實(shí)現(xiàn)。　?。?）、車輛的離開，則需要另設(shè)一個(gè)棧，給要離去的汽車讓路而從停車場(chǎng)

16、退出來的汽車臨時(shí)停放，也用順序棧實(shí)現(xiàn)，車輛離開后需檢查便道內(nèi)是否有車等待，如有等待的車輛則進(jìn)行便道內(nèi)的車輛進(jìn)入停車場(chǎng)的操作，即將車輛信息結(jié)點(diǎn)進(jìn)行入棧操作，輸入當(dāng)前時(shí)間后開始計(jì)費(fèi)，最后進(jìn)行出棧操作，表示車輛離開便道以進(jìn)入停車場(chǎng)。用函數(shù)Leave()實(shí)現(xiàn)。　　程序編碼：（源碼）　　主函數(shù)</b&g

17、t;　　#include<stdio.h> 　　#include<string.h>　　#include<malloc.h>　　#include<stdlib.h>　　#includ

18、e"LinkedList.h"　　#include"Huffman.h" 　　#include"Parking.h"　　#include"Tree.h"　　void main()</p&

19、gt;　　{ 　　int k;　　char ch='y';　　while(ch=='y')　　{<

20、;/p>　　printf("\t\t#*#*#*#*歡迎進(jìn)入我的課設(shè)工程*#*#*#*#\n");　　printf("\t\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");　　printf("\t如果碰到意外結(jié)束的情況或者排序不正確的情況\n

21、\n");　　printf("\t\t 請(qǐng)及時(shí)聯(lián)系我 \n \n");　　printf("\t\t☆ 請(qǐng)選擇以下題目展示: ☆\n");　　printf("\t\t★

22、 1.二叉樹簡(jiǎn)單操作(★★★) ★\n");　　printf("\t\t★ 2.單鏈表簡(jiǎn)單操作(★★) ★\n");　　printf("\t\t★ 3.哈夫曼樹編碼器(★★★) ★\n");</p&

23、gt;　　printf("\t\t★ 4.停車場(chǎng)管理系統(tǒng)(★★★★★) ★\n");　　printf("\t\t★ 0.退出程序 ★\n");　　printf("\n\n\n");</

24、p>　　printf("請(qǐng)選擇(0-4)：");　　scanf("%d",&k);　　switch (k)　　{　　case 1:printf("

25、您選擇的是二叉樹操作系統(tǒng)\n");　　Treemenu();　　break;　　case 2: printf("您選擇進(jìn)入的是單鏈表操作系統(tǒng)\n");　　LListmenu();&

26、lt;p>　　break;　　case 3:printf("您選擇進(jìn)入的是哈夫曼樹編碼器\n");　　Huffmanmenu();　　break;　　case 4:pri

27、ntf("您選擇的是停車場(chǎng)管理系統(tǒng)\n");　　Parkingmenu();　　break;　　case 0:　　exit(0);<

28、/p>　　default:　　printf("您的輸入有誤，請(qǐng)重新輸入！");　　}　　}

29、　}　　功能函數(shù)　　二叉樹的操作　　頭文件　　typedef char DataType;　　#

30、define MAX 100　　typedef struct BiTNode//二叉鏈表數(shù)據(jù)結(jié)構(gòu)定義　　{　　DataType data;　　struct BiTNode *lchild,*rchild; &

31、lt;p>　　}BiTree;　　菜單函數(shù)　　#include<stdio.h>　　#include<stdlib.h>　　#include"Tree.h&

32、quot;　　int Treemenu()//(int argc,char *argv[])　　{　　BiTree *tree;　　int deep,sum;　　printf("\t

33、\t歡迎進(jìn)入二叉樹基本操作系統(tǒng)\n\n\n");　　tree=Create(); /* 建立二叉樹 */ 　　deep=DepthPost(tree);/* 求二叉樹高度 */　　printf("\n1:輸出先序序列: ");

34、　　PreTra(tree);　　printf("\n2:輸出中序序列: ");　　InTra(tree);　　printf("\n3:輸出后序序列: ");　　PostTra(tree);&

35、lt;p>　　printf("\n4:輸出二叉樹的高度：%d\n",deep);　　sum=LeafCount(tree);　　printf("\n5:輸出二叉樹的葉子節(jié)點(diǎn)：%d\n",sum);　　printf("\n操作結(jié)束！謝謝您的使用。\n"

36、;);　　return 0; 　　}　　各個(gè)源文件子函數(shù)　　#include<stdio.h>　　#include<stdlib.

37、h>　　#include"Tree.h"　　BiTree *Create()//非遞歸方法建立二叉鏈表　　{　　BiTree *Q[MAX];　　DataType c

38、h;　　int front,rear;　　BiTree *s,*root; 　　root=NULL;　　front=1;　　rear=0; //隊(duì)列初始化 <p

39、>　　printf("\t請(qǐng)按完全二叉樹的編號(hào)順序依次輸入結(jié)點(diǎn)序列\(zhòng)n");　　printf("\t注：空結(jié)點(diǎn)用'@'表示，輸入序列以'#'結(jié)束\n\n");　　printf("\t輸入的順序?yàn)椋?quot;);　　ch=ge

40、tchar();　　while(ch!='#')　　{　　s=NULL; 　　if(ch!='@')　　{ <

41、/p>　　s=(BiTree *)malloc(sizeof(BiTree));//申請(qǐng)新結(jié)點(diǎn) 　　s->data=ch; 　　s->lchild=NULL; 　　s->rchild=NULL; 　　}<

42、;/b>　　rear++;　　Q[rear]=s; //空結(jié)點(diǎn)和新結(jié)點(diǎn)都入隊(duì)　　if(rear==1) 　　root=s; //rear是1，是根結(jié)點(diǎn)，用root指向它

43、　　else　　{　　if(s&&Q[front]) // 當(dāng)前結(jié)點(diǎn)和雙親結(jié)點(diǎn)都非空 　　if(rear%2==0)// rear是偶數(shù)，新結(jié)點(diǎn)為雙親的左孩子

44、;　　Q[front]->lchild=s;　　else // rear是奇數(shù)，新結(jié)點(diǎn)為雙親的右孩子 　　Q[front]->rchild=s;　　if(rear%2==1) 　　front++; // rear是奇數(shù)，頭指針front

45、指向下一個(gè)雙親　　}　　ch=getchar(); 　　} 　　return root; 　　}

46、;　　void PreTra(BiTree *t) //遞歸算法先序遍歷二叉樹　　{　　if(t) // 初始條件：二叉樹存在　　{

47、　　printf("%c",t->data); // 訪問結(jié)點(diǎn) 　　PreTra(t->lchild); // 先序遍歷左子樹 　　PreTra(t->rchild); // 先序遍歷右子樹 　　}

48、;　　} 　　void InTra(BiTree *t)//遞歸算法中序遍歷二叉樹　　{　　if(t)　　{<

49、;/p>　　InTra(t->lchild); // 中序遍歷左子樹 　　printf("%c",t->data); // 訪問根結(jié)點(diǎn) 　　InTra(t->rchild); // 中序遍歷右子樹 　　}&

50、lt;/p>　　} 　　void PostTra(BiTree *t)//遞歸算法后序遍歷二叉樹　　{　　if(t)<

51、b>　　{　　PostTra(t->lchild); //后序遍歷左子樹 　　PostTra(t->rchild); // 后序遍歷右子樹 　　printf("%c",t->data); // 訪問根結(jié)點(diǎn)

52、　　}　　}　　int DepthPost(BiTree *t) //遞歸算法后序遍歷求二叉樹的高度　　{　　int hl,hr,max;

53、;　　if(t)　　{　　hl= DepthPost(t->lchild); // 求左子樹的深度 　　hr= DepthPost(t->rchild); // 求右子樹的深度

54、　　max=hl>hr?hl:hr; // 得到左、右子樹深度較大者　　return max+1; // 返回樹的深度 　　}　　else

55、;　　return 0; // 如果是空樹，則返回0 　　} 　　int LeafCount(BiTree *t) //遍歷求葉子結(jié)點(diǎn)的個(gè)數(shù)　　{<

56、p>　　int sum=0,m,n;　　if(t)　　{ 　　if((!t->lchild)&&(!t->rchild)) 　　sum++; &

57、lt;/b>　　m=LeafCount(t->lchild); 　　sum+=m; 　　n=LeafCount(t->rchild); 　　sum+=n;

58、　　} 　　return sum; 　　}　　單鏈表的操作　　頭文件<

59、p>　　typedef char DataType; 　　#define OK 1　　#define ERROR -1　　typedef struct node//結(jié)點(diǎn)類型定義 　　{

60、　　DataType data;　　struct node *next;　　}LinkedList;　　void InitLList(LinkedList *L);　　int GetLListLength(LinkedList *L);<p&

61、gt;　　LinkedList *GetLListElem(LinkedList *L, int i);　　LinkedList *LocateLListElem( LinkedList *L,DataType key);　　int InsertLList(LinkedList *L,int i,DataType x);<p

62、>　　int DeleteLList(LinkedList *L,int i,DataType *e);　　LinkedList *CreateLList();// 建立不帶頭結(jié)點(diǎn)的單鏈表（頭插法建表)　　LinkedList *CreateLListR();//建立帶頭結(jié)點(diǎn)的單鏈表（尾插法建表）　　P

63、rintLList(LinkedList *q);　　菜單函數(shù)　　#include<stdio.h> 　　#include<string.h>　　#include<stdlib.h></p&

64、gt;　　#include<malloc.h>　　#include"LinkedList.h" 　　int LListmenu()　　{　　LinkedList *a,*p;&l

65、t;/p>　　int length,node,i,j,k;　　char value,q;　　char ch='y';　　while(ch=='y')　　{

66、;　　printf("\t\t#*#*#*#*歡迎進(jìn)入單鏈表操作系統(tǒng)*#*#*#*#\n");　　printf("\t\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");　　printf("\n\n\n");<

67、p>　　printf("\t 如果碰到意外結(jié)束的情況或者操作不正確的情況\n\n");　　printf("\t\t★★★ 請(qǐng)及時(shí)聯(lián)系18062794950 ★★★\n");　　printf("\t\t★ 注意：功能使用中應(yīng)該先建表 ★\n")

68、; 　　printf("\t\t★ 然后進(jìn)行各個(gè)操作，最后初始化鏈表 ★\n");　　printf("\t\t☆ 請(qǐng)選擇所需功能: ☆\n");　　printf("\t\t★ 1

69、.頭插法建表 ★\n");　　printf("\t\t★ 2.尾插法建表 ★\n");　　printf("\t\t★ 3.求表的長(zhǎng)度 ★\n");

70、　　printf("\t\t★ 4.取結(jié)點(diǎn)(遍歷) ★\n");　　printf("\t\t★ 5.插入運(yùn)算 ★\n");　　printf("\t\t★

71、 6.刪除運(yùn)算 ★\n");　　printf("\t\t★ 7.輸出帶頭結(jié)點(diǎn)的單鏈表 ★\n");　　printf("\t\t★★★ 8.鏈表的初始化 ★★★\n");<

72、p>　　printf("\t\t★ 0.返回主菜單 ★\n");　　printf("\n\n\n");　　printf("請(qǐng)選擇(1-8)：");　　scanf("%d",&

73、amp;k);　　switch (k)　　{　　case 1: 　　printf("\t您的選擇是頭插法建表\n");　　printf

74、("\t輸入字符串,如: abcdef@ 以@結(jié)束后回車\n");　　a=CreateLList();　　PrintLList(a);　　break;　　case 2: <

75、;/p>　　printf("\t你的選擇是尾插法建表\n");　　printf("\t輸入字符串,如: abcdef@ 以@結(jié)束后回車\n"); 　　a=CreateLListR();　　PrintLList(a);<

76、;p>　　break;　　case 3: 　　printf("\t您選擇的是計(jì)算表的長(zhǎng)度\n");　　length=GetLListLength(a);　　printf(

77、"該表的長(zhǎng)度為：%d\n",length);　　break;　　case 4: 　　printf("\t您的選擇是取結(jié)點(diǎn)\n");　　printf(&quo

78、t;請(qǐng)輸入取第幾個(gè)節(jié)點(diǎn)：\n");　　scanf("%d",&node);　　p=GetLListElem(a,node);　　if(p==NULL)　　printf("表中沒有該節(jié)點(diǎn)!\n");

79、;　　else　　printf("該節(jié)點(diǎn)的數(shù)據(jù)域?yàn)椋?c\n",p->data);　　break;　　case 5: <p

80、>　　printf("您的選擇是插入運(yùn)算\n");　　printf("請(qǐng)輸入要插入的位置：\n");　　scanf("%d",&i);　　printf("請(qǐng)輸入插入的字符");

81、　getchar();　　scanf("%c",&value);　　InsertLList(a,i,value);　　PrintLList(a);　　break;&

82、lt;b>　　case 6: 　　printf("\t您選擇的是刪除運(yùn)算\n");　　printf("請(qǐng)輸入要?jiǎng)h除的位置 \n");　　scanf("%d",&j);　　Dele

83、teLList(a,j,&q);　　PrintLList(a);　　break;　　case 7: 　　printf("\t輸出鏈表為：");&

84、lt;p>　　PrintLList(a);　　break;　　case 8:　　printf("\t您選擇的是鏈表的初始化\n");　　InitLList(a);<

85、;/p>　　PrintLList(a);　　break;　　case 0:　　printf("\t您的選擇是返回主菜單\n");

86、　main();　　default:　　printf("\t\t輸入錯(cuò)誤！請(qǐng)重新輸入！\n\t\t");　　}　　}

87、　　return 0;　　}　　各個(gè)子函數(shù)源文件　　#include<stdio.h> 　　#inclu

88、de<string.h>　　#include<malloc.h>　　#include<stdlib.h> 　　#include"LinkedList.h"　　void InitLList(LinkedList *L)

89、// 對(duì)單鏈表進(jìn)行初始化 　　{　　L->next=NULL;// 置為空表 　　}　　int GetLListLength(LinkedList *L)// 求表的長(zhǎng)度 </p&

90、gt;　　{　　LinkedList *p;　　int j;　　p=L->next;　　j=0;<p

91、>　　while(p!=NULL)　　{　　p=p->next;　　j++;　　}

92、return j;　　}　　LinkedList *GetLListElem(LinkedList *L, int i)//在帶頭結(jié)點(diǎn)的單鏈表L中查找第i個(gè)結(jié)點(diǎn)　　{ &l

93、t;b>　　int j;　　LinkedList *p;　　p=L;　　j=0; 　　while ((p->next!=NULL)&&(j<

94、i))　　{ 　　p=p->next; 　　j++; 　　}　　if(i == j)&

95、lt;p>　　return p; 　　else 　　return NULL; 　　}　　LinkedList *LocateLListElem( LinkedList *L,DataTy

96、pe key)//在帶頭結(jié)點(diǎn)的單鏈表L中查找其　　{ 　　LinkedList *p;　　p=L->next; 　　while (p!=NULL)　　{</b

97、>　　if (p->data!=key)　　p=p->next; 　　else　　break; 　　}</b&g

98、t;　　return p;　　}　　int InsertLList(LinkedList *L,int i,DataType x)//在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置插入值為e的新結(jié)點(diǎn)s<b

99、>　　{　　LinkedList *pre,*s;　　int k;　　pre=L; 　　k=0; &l

100、t;p>　　while(pre!=NULL&&k<i-1) 　　{　　pre=pre->next;　　k=k+1; 　　} </b&g

101、t;　　if(!pre) 　　{ 　　printf("插入位置不合理!");　　return ERROR;　　}&l

102、t;/b>　　s=(LinkedList*)malloc(sizeof(LinkedList)); 　　s->data=x; 　　s->next=pre->next; 　　pre->next=s;

103、　　return OK;　　}　　int DeleteLList(LinkedList *L,int i,DataType *e)//在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)元素，并將刪除的元素保存到變量*e中　　{&l

104、t;p>　　LinkedList *pre,*r;　　int k;　　pre=L;　　k=0;　　while(pre->next!=NULL &a

105、mp;& k<i-1) 　　{　　pre=pre->next; 　　k=k+1;　　}

106、if(!(pre->next)) 　　{ 　　printf("刪除結(jié)點(diǎn)的位置i不合理!");　　return ERROR;　　}

107、;　　r=pre->next;　　pre->next=pre->next->next; 　　*e = r->data;　　free(r); 　　printf("成功刪除結(jié)點(diǎn)!");&l

108、t;/p>　　return OK;　　}　　LinkedList *CreateLList()// 建立不帶頭結(jié)點(diǎn)的單鏈表（頭插法建表)　　{　　c

109、har ch;　　LinkedList *l,*s;　　l=(LinkedList *)malloc(sizeof(LinkedList));　　l->next=NULL;　　ch=getchar();

110、　　while(ch!='@') 　　{　　s=(LinkedList *)malloc(sizeof(LinkedList));　　s->data=ch;　　s->next=l->next;<

111、/p>　　l->next=s;　　ch=getchar();　　}　　return l;　　}<

112、;p>　　LinkedList *CreateLListR()//建立帶頭結(jié)點(diǎn)的單鏈表（尾插法建表）　　{ 　　char ch;　　LinkedList *head,*s,*r;　　h

113、ead=(LinkedList *)malloc(sizeof(LinkedList));　　r=head;　　ch=getchar();　　while(ch!='@') 　　{

114、;　　s=(LinkedList *)malloc(sizeof(LinkedList));　　s->data=ch;　　r->next=s;　　r=s;　　ch=getchar(

115、);　　}　　r->next=NULL; 　　return head;　　}　　PrintLList(LinkedList *q)//輸出帶頭結(jié)點(diǎn)

116、的單鏈表　　{　　LinkedList *p;　　p=q->next;　　printf("字符單鏈表結(jié)果是: \n(");　　while(p!=NULL)<

117、/p>　　{　　printf("%5c,",p->data);　　p=p->next;　　}　　printf("\b)&quo

118、t;);　　}　　哈夫曼編碼器　　頭文件　　#include <stdio.h>　　typedef ch

119、ar DataType;　　#define MAXNUM 50　　typedef struct// 哈夫曼樹結(jié)點(diǎn)的結(jié)構(gòu) 　　{　　DataType data; // 數(shù)據(jù)用字符表示 　　i

120、nt weight; // 權(quán)值 　　int parent; // 雙親 　　int left; // 左孩子 　　int right; // 右孩子 　　}HuffNode;　　t

121、ypedef struct// 哈夫曼編碼的存儲(chǔ)結(jié)構(gòu) 　　{　　DataType cd[MAXNUM];// 存放編碼位串 　　int start; // 編碼的起始位置 　　}HuffCode;

122、　　菜單函數(shù)　　#include"Huffman.h"　　int Huffmanmenu()　　{　　int n,select,flag=0; //

123、flag為0時(shí)標(biāo)記第一次選擇功能 　　HuffNode ht[2*MAXNUM]; // 定義存放哈夫曼樹的數(shù)組 　　HuffCode hcd[MAXNUM]; // 定義存放編碼的數(shù)組 　　while(1)

124、　{　　printf("\t 請(qǐng)選擇您所要實(shí)現(xiàn)的功能：\n");　　printf("\t1---建立哈夫曼樹\n");　　printf("\t2---編碼\n");　　printf(&quo

125、t;\t3---譯碼\n");　　printf("\t4---退出系統(tǒng)\n");　　printf("（請(qǐng)輸入1-4數(shù)字）\n");　　scanf("%d",&select);　　if(selec

126、t!=1&&select!=4&&flag==0)　　{ // 提示先建立哈夫曼樹或退出 　　printf("請(qǐng)先建立哈夫曼樹再選擇其他功能！\n");　　continue;</p&

127、gt;　　}　　flag=1;　　switch(select) // 選擇功能 　　{ 　　case 1:&

128、lt;/b>　　n=HuffmanCreate(ht); 　　break;　　case 2: 　　Encoding(ht,hcd,n); <b

129、>　　break;　　case 3:　　Decoding(ht,hcd,n); 　　break;　　case 4: </p&g

130、t;　　return 1;　　}　　}　　return 0;　　} <

131、;/b>　　各個(gè)子函數(shù)模塊　　#include"Huffman.h"　　int HuffmanCreate(HuffNode *ht)//建立哈夫曼樹 　　{</

132、p>　　int i,k,n,m1,m2,p1,p2;　　printf("請(qǐng)輸入元素個(gè)數(shù)：");　　scanf("%d",&n);　　for(i=1;i<=n;i++) // 輸入結(jié)點(diǎn)值和信息 </p&g

133、t;　　{　　getchar(); // 接收回車 　　printf("第%d個(gè)元素的=>\n\t結(jié)點(diǎn)值：",i);　　scanf("%c",&ht[i].data);

134、　　printf("\t權(quán) 重：");　　scanf("%d",&ht[i].weight);　　}　　for(i=1;i<=2*n-1;i++) // 對(duì)數(shù)組

135、初始化 　　ht[i].parent=ht[i].left=ht[i].right=0;　　for(i=n+1;i<=2*n-1;i++)　　{ 　　m1=m2=32767; /

136、/ 初始化，令m1、m2為整數(shù)最大值 　　p1=p2=1;　　for(k=1;k<=i-1;k++) // 從數(shù)組ht[1]到ht[i-1]中找出 　　if(ht[k].parent==0) // parent為0并且權(quán)值最小的兩個(gè)結(jié)點(diǎn) &

137、lt;/p>　　if(ht[k].weight<m1) 　　{　　m2=m1; // m1為最小權(quán)值 　　p2=p1; // p1為最小權(quán)值的位置

138、;　　m1=ht[k].weight; // m1存放最小權(quán)值 　　p1=k;　　}　　else if(ht[k].weight<m2)　　{&l

139、t;/p>　　m2=ht[k].weight; // m2為次小權(quán)值 　　p2=k; // p2為次小權(quán)值的位置 　　}　　ht[p1].parent=i; // i分別賦給下標(biāo)為p1、p

140、2的數(shù)組中 　　ht[p2].parent=i;　　ht[i].weight=m1+m2; // 新結(jié)點(diǎn)的的權(quán)值為最小權(quán)值和次小權(quán)值的和 　　ht[i].left=p1; // p1為新結(jié)點(diǎn)的左孩子 　　ht[i].right

141、=p2; // p2為新結(jié)點(diǎn)的右孩子 　　}　　printf("哈夫曼樹已成功建立！\n");　　return n; 　　}&l

142、t;/b>　　void Encoding(HuffNode ht[],HuffCode hcd[],int n)// 哈夫曼編碼 　　{ 　　HuffCode d;　　int i,k,f,c;

143、 　　for(i=1;i<=n;i++) // 對(duì)所有結(jié)點(diǎn)循環(huán) 　　{　　d.start=n+1; // 起始位置 　　c=i;

144、 // 從葉結(jié)點(diǎn)開始向上 　　f=ht[i].parent;　　while(f!=0) // 直到樹根為止 　　{　　if(ht[f].left==c)

145、　　d.cd[--d.start]='0';// 規(guī)定左樹為代碼0 　　else　　d.cd[--d.start]='1';// 規(guī)定右樹為代碼1 　　c=f; // c指孩子的位置

眾賞文庫(kù)> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)習(xí)報(bào)告

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)習(xí)報(bào)告

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載