算法與數(shù)據(jù)結(jié)構(gòu)－課程設(shè)計(jì)報(bào)告

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

算法與數(shù)據(jù)結(jié)構(gòu)－課程設(shè)計(jì)報(bào)告_第1頁

已閱讀1頁，還剩33頁未讀，繼續(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ì)報(bào)告　　目錄　　1、模塊2：一元多項(xiàng)式計(jì)算

2、　　2、模塊8：建立二叉樹，層序、先序遍歷　　3、模塊9：赫夫曼樹的建立　　1、模塊2：一元多項(xiàng)式計(jì)算　?。?）系統(tǒng)分析　　建立一元多項(xiàng)式并按照指數(shù)降序排列輸出多項(xiàng)式，將一元多項(xiàng)式輸入并存儲(chǔ)在內(nèi)存中，能夠完成

3、兩個(gè)多項(xiàng)式的加減運(yùn)算并輸出結(jié)果　　（2）概要設(shè)計(jì)　　存儲(chǔ)結(jié)構(gòu)：一元多項(xiàng)式的表示在計(jì)算機(jī)內(nèi)可以用鏈表來表示，為了節(jié)省存儲(chǔ)空間，只存儲(chǔ)多項(xiàng)式中系數(shù)非零的項(xiàng)。鏈表中的每一個(gè)結(jié)點(diǎn)存放多項(xiàng)式的一個(gè)系數(shù)非零項(xiàng)，它包含三個(gè)域，分別存放該項(xiàng)的系數(shù)、指數(shù)以及指向下一個(gè)多項(xiàng)式項(xiàng)結(jié)點(diǎn)的指針。創(chuàng)建一元多項(xiàng)式鏈表，對(duì)一元多項(xiàng)式的運(yùn)算中會(huì)出現(xiàn)的

4、各種可能情況進(jìn)行分析，實(shí)現(xiàn)一元多項(xiàng)式的相加、相減操作。　　1．單連表的抽象數(shù)據(jù)類型定義：　　ADT List{ 數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 數(shù)據(jù)關(guān)系：R1={<ai-1,ai>| ai-1, ai∈D,i=2,…,n} 　　基本操作：&

5、lt;/b>　　InitList（＆L）　　//操作結(jié)果：構(gòu)造一個(gè)空的線性表 　　CreatPolyn(&L) 　　//操作結(jié)果：構(gòu)造一個(gè)以單連表存儲(chǔ)的多項(xiàng)試 　　DispPolyn(L) &

6、lt;p>　　//操作結(jié)果：顯示多項(xiàng)試 　　Polyn(&pa,&pb) 　　//操作結(jié)果：顯示兩個(gè)多項(xiàng)試相加，相減的結(jié)果 　　} ADT List 　　2．本程序包含模塊： typedef struct LNode //定義單鏈表 </p&

7、gt;　　{　　}LNode,*LinkList; 　　void InitList(LinkList &L) //定義一個(gè)空表　　{ } 　　void CreatPo

8、lyn(LinkList &L) //用單鏈表定義一個(gè)多項(xiàng)式　　{ } 　　void DispPolyn(LinkList L) //顯示輸入的多項(xiàng)式　　{ } 　　void Polyn(

9、LinkList &pa,LinkList &pb) 　　{} 　　void main() 　　{ 　　//定義一個(gè)單連表； 　　cout

10、<<endl<<" *****************歡迎來到一元多項(xiàng)式計(jì)算程序 　　*************** "<<endl; 　　LNode *L1,*L2;　　Polyn(L1,L2); } 　　2.1

11、加，減操作模塊——實(shí)現(xiàn)加減操作　　各模塊之間的調(diào)用關(guān)系如下：　　主程序模塊 　　加法操作模塊減法操作模塊　　基本算法：　　1、輸入輸出

12、　　（1）功能：將要進(jìn)行運(yùn)算的多項(xiàng)式輸入輸出。　　（2）數(shù)據(jù)流入：要輸入的多項(xiàng)式的系數(shù)與指數(shù)。　?。?）數(shù)據(jù)流出：合并同類項(xiàng)后的多項(xiàng)式。　?。?）程序流程圖：多項(xiàng)式輸入流程圖如圖1所示。　?。?）測(cè)試要點(diǎn)：輸入

13、的多項(xiàng)式是否正確，若輸入錯(cuò)誤則重新輸入　　2、多項(xiàng)式的加法　?。?）功能：將兩多項(xiàng)式相加。　?。?）數(shù)據(jù)流入：輸入函數(shù)。　?。?）數(shù)據(jù)流出：多項(xiàng)式相加后的結(jié)果。　?。?）程序流程圖：多項(xiàng)式的加

14、法流程圖如圖2所示。　?。?）測(cè)試要點(diǎn)：兩多項(xiàng)式是否為空，為空則提示重新輸入，否則，進(jìn)行運(yùn)算。　　圖表 2　　3、多項(xiàng)式的減法　?。?）功能：將兩多項(xiàng)式相減。<p&g

15、t;　?。?）數(shù)據(jù)流入：調(diào)用輸入函數(shù)。　　（3）數(shù)據(jù)流出：多項(xiàng)式相減后的結(jié)果。　?。?）程序流程圖：多項(xiàng)式的減法流程圖如圖3所示。　?。?）測(cè)試要點(diǎn)：兩多項(xiàng)式是否為空，為空則提示重新輸入，否則，進(jìn)行運(yùn)算。　　1. 根據(jù)題目要求采用單連表存儲(chǔ)結(jié)構(gòu)&l

16、t;p>　　typedef struct LNode //定義單鏈表　　{　　}LNode,*LinkList;　　void InitList(LinkList &L) //定義一個(gè)空表　　{ } &l

17、t;/b>　　void CreatPolyn(LinkList &L) //用單鏈表定義一個(gè)多項(xiàng)式　　{ } 　　void DispPolyn(LinkList L) //顯示輸入的多項(xiàng)式 　　{ }&

18、lt;/b>　　void Polyn(LinkList &pa,LinkList &pb) 　　{} 　　2．主函數(shù) main　　void main()

19、;　　{ 　　LNode *L1,*L2; 　　Polyn(L1,L2);　　} 　　2. 函數(shù)的調(diào)用關(guān)系層次結(jié)構(gòu)　　多項(xiàng)式 Polyn 用單鏈表定義多項(xiàng)式 CreatPo

20、lyn 定義一個(gè)空表 InitList 顯示輸入的多項(xiàng)式 DispPolyn　　}　　五. 調(diào)試分析　　采用單連表形式按照指數(shù)降序排列建立并輸出多項(xiàng)式；在相加，相減的過程中如果指數(shù)相同就執(zhí)行系數(shù)相加，相減，否則就把大的項(xiàng)直接寫入。完成兩

21、個(gè)多項(xiàng)式的相加、相減;將從新得到的單連表結(jié)果輸出；該算法的時(shí)間復(fù)雜度為兩個(gè) 多項(xiàng)式的項(xiàng)式之和　　(3)詳細(xì)設(shè)計(jì)　　#include<stdio.h>　　#include<malloc.h>　　typedef

22、struct Polynomial{　　float coef;　　int expn;　　struct Polynomial *next;　　}*Polyn,Polynomial; //Polyn為結(jié)點(diǎn)指針類

23、型　　void Insert(Polyn p,Polyn h){ 　　if(p->coef==0) free(p); //系數(shù)為0的話釋放結(jié)點(diǎn)　　else{　　Polyn q1,q2;

24、　　q1=h;q2=h->next;　　while(q2&&p->expn<q2->expn){ //查找插入位置　　q1=q2;　　q2=q2->next;<

25、b>　　}　　if(q2&&p->expn==q2->expn){ //將指數(shù)相同相合并　　q2->coef+=p->coef;　　free(p);　　if(!

26、q2->coef){ //系數(shù)為0的話釋放結(jié)點(diǎn)　　q1->next=q2->next;　　free(q2);　　}　　}</b&g

27、t;　　else{ //指數(shù)為新時(shí)將結(jié)點(diǎn)插入　　p->next=q2;　　q1->next=p;　　}　　}&l

28、t;/b>　　}//Insert　　Polyn CreatePolyn(Polyn head,int m){//建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式　　int i;

29、;　　Polyn p;　　p=head=(Polyn)malloc(sizeof(struct Polynomial));　　head->next=NULL;　　for(i=0;i<m;i++){　　p=(Polyn)malloc(size

30、of(struct Polynomial));//建立新結(jié)點(diǎn)以接收數(shù)據(jù)　　printf("請(qǐng)輸入第%d項(xiàng)的系數(shù)與指數(shù):",i+1);　　scanf("%f %d",&p->coef,&p->expn);　　Insert(p,head); //

31、調(diào)用Insert函數(shù)插入結(jié)點(diǎn)　　}　　return head;　　}//CreatePolyn　　void DestroyPolyn(Polyn p){//銷毀多項(xiàng)式p　　Polyn q1,q

32、2;　　q1=p->next;　　q2=q1->next;　　while(q1->next){　　free(q1);　　q1=q2;//指針后移<

33、;p>　　q2=q2->next;　　}　　}　　void PrintPolyn(Polyn P){ 　　Polyn q=P->next; <p&g

34、t;　　int flag=1;//項(xiàng)數(shù)計(jì)數(shù)器　　if(!q) { //若多項(xiàng)式為空，輸出0　　putchar('0'); 　　printf("\n");　　return;&l

35、t;p>　　} 　　while (q){　　if(q->coef>0&&flag!=1) putchar('+'); //系數(shù)大于0且不是第一項(xiàng)　　if(q->coef!=1&&q->coef!

36、=-1){//系數(shù)非1或-1的普通情況　　printf("%g",q->coef); 　　if(q->expn==1) putchar('X');　　else if(q->expn) printf("X^%d",q->expn);&l

37、t;/p>　　}　　else{　　if(q->coef==1){　　if(!q->expn) putchar('1'); 　　else if

38、(q->expn==1) putchar('X'); 　　else printf("X^%d",q->expn);　　}　　if(q->coef==-1){　　if(!q->

39、expn) printf("-1"); 　　else if(q->expn==1) printf("-X"); 　　else printf("-X^%d",q->expn);　　}

40、　　}　　q=q->next; 　　flag++;　　}//while　　printf("\n");</p&

41、gt;　　}//PrintPolyn　　int compare(Polyn a,Polyn b){　　if(a&&b){　　if(!b||a->expn>b->expn) return 1;<

42、;p>　　else if(!a||a->expn<b->expn) return -1;　　else return 0;　　}　　else if(!a&&b) return -1;//a多項(xiàng)式已空，但b多項(xiàng)式非空

43、　　else return 1;//b多項(xiàng)式已空，但a多項(xiàng)式非空　　}//compare　　Polyn AddPolyn(Polyn pa,Polyn pb){//求解并建立多項(xiàng)式a+b，返回其頭指針　　Polyn qa=pa->next;　　Po

44、lyn qb=pb->next;　　Polyn headc,hc,qc;　　hc=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn)　　hc->next=NULL;　　headc=hc;</

45、b>　　while(qa||qb){　　qc=(Polyn)malloc(sizeof(struct Polynomial));　　switch(compare(qa,qb)){　　case 1:<

46、p>　　{　　qc->coef=qa->coef;　　qc->expn=qa->expn;　　qa=qa->next;　　break;&

47、lt;p>　　}　　case 0:　　{ 　　qc->coef=qa->coef+qb->coef;　　qc->expn=qa-

48、>expn;　　qa=qa->next;　　qb=qb->next;　　break;　　}　　case -1:<

49、/b>　　{　　qc->coef=qb->coef;　　qc->expn=qb->expn;　　qb=qb->next;　　break;&

50、lt;/b>　　} 　　}//switch　　if(qc->coef!=0){　　qc->next=hc->next;　　hc-&

51、gt;next=qc;　　hc=qc;　　}　　else free(qc);//當(dāng)相加系數(shù)為0時(shí)，釋放該結(jié)點(diǎn)　　}//while<

52、;p>　　return headc;　　}//AddPolyn　　Polyn SubtractPolyn(Polyn pa,Polyn pb){//求解并建立多項(xiàng)式a+b，返回其頭指針　　Polyn h=pb;　　Polyn p=pb->next;</p

53、>　　Polyn pd;　　while(p){ //將pb的系數(shù)取反　　p->coef*=-1;　　p=p->next;　　}</

54、p>　　pd=AddPolyn(pa,h);　　for(p=h->next;p;p=p->next) //恢復(fù)pb的系數(shù)　　p->coef*=-1;　　return pd;　　}//SubtractPolyn</p

55、>　　int main(){　　int m,n,flag=0;　　float x;　　Polyn pa=0,pb=0,pc,pd,pe,pf;//定義各式的頭指針，pa與pb在使用前付初值NULL　　pri

56、ntf("請(qǐng)輸入a的項(xiàng)數(shù):");　　scanf("%d",&m);　　pa=CreatePolyn(pa,m);//建立多項(xiàng)式a　　printf("請(qǐng)輸入b的項(xiàng)數(shù):");　　scanf("%d&

57、quot;,&n);　　pb=CreatePolyn(pb,n);//建立多項(xiàng)式a　　//輸出菜單　　printf("**********************************************\n");&l

58、t;p>　　printf("操作提示：\n\t1.輸出多項(xiàng)式a和b\n\t2.建立多項(xiàng)式a+b\n\t3.建立多項(xiàng)式a-b\n");　　printf("\t4.退出\n**********************************************\n");　　for(;;flag=0){<

59、/p>　　printf("執(zhí)行操作：");　　scanf("%d",&flag);　　if(flag==1){　　printf("多項(xiàng)式a：");PrintPolyn(pa);

60、　　printf("多項(xiàng)式b：");PrintPolyn(pb);continue;　　}　　if(flag==2){　　pc=AddPolyn(pa,pb);　　printf("多項(xiàng)式a+b："

61、;);PrintPolyn(pc);　　DestroyPolyn(pc);continue;　　}　　if(flag==3){　　pd=SubtractPolyn(pa,pb);　　print

62、f("多項(xiàng)式a-b：");PrintPolyn(pd);　　DestroyPolyn(pd);continue;　　}　　if(flag==4) break;　　if(flag<1||flag>4) p

63、rintf("Error!!!\n");continue;　　}//for　　DestroyPolyn(pa);　　DestroyPolyn(pb);　　return 0;&l

64、t;/p>　　}　　(4)測(cè)試記錄　　測(cè)試的數(shù)據(jù)及結(jié)果　　(5)總結(jié)：　　算法的時(shí)間復(fù)雜度及

65、改進(jìn)：　　一元多項(xiàng)式的加法運(yùn)算的時(shí)間復(fù)雜度為O(m+n）,減法運(yùn)算的時(shí)間復(fù)雜度為O(m-n)，其中m，n分別表示二個(gè)一元多項(xiàng)式的項(xiàng)數(shù)。　　問題和改進(jìn)思想：在設(shè)計(jì)該算法時(shí)，出現(xiàn)了一些問題，例如在建立鏈表時(shí)頭指針的設(shè)立導(dǎo)致了之后運(yùn)用到相關(guān)的指針時(shí)沒能很好的移動(dòng)指針出現(xiàn)了數(shù)據(jù)重復(fù)輸出或是輸出系統(tǒng)缺省值，不能實(shí)現(xiàn)算法。實(shí)現(xiàn)加法時(shí)該鏈表并沒有向通常那樣通過建立第三

66、個(gè)鏈表來存放運(yùn)算結(jié)果，而是再度利用了鏈表之一來進(jìn)行節(jié)點(diǎn)的比較插入刪除等操作。為了使輸入數(shù)據(jù)按指數(shù)降序排列，可在數(shù)據(jù)的輸入后先做一個(gè)節(jié)點(diǎn)的排序函數(shù)，通過對(duì)鏈表排序后再進(jìn)行之后加減運(yùn)算。　　一元多項(xiàng)式計(jì)算是一個(gè)的單鏈表的運(yùn)用，通過這個(gè)程序可以測(cè)我們以前的學(xué)習(xí)情況，看看我們是否對(duì)單鏈表真正的理解。　　一元多項(xiàng)式計(jì)算器的基本功能定為：

67、　　(1) 建立多項(xiàng)式 　　(2) 輸出多項(xiàng)式　　(3) 兩個(gè)多項(xiàng)式相加，建立并輸出和多項(xiàng)式 　　(4) 兩個(gè)多項(xiàng)式相減，建立并輸出差多項(xiàng)式能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式；能夠完成兩個(gè)多項(xiàng)式的相加、相減，并將結(jié)果輸出；<

68、p>　　2、模塊8：建立二叉樹，層序、先序遍歷　?。?）系統(tǒng)分析　　要求能夠輸入樹的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立二叉樹存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；程序功能包括，建立二叉樹，輸出二叉樹，對(duì)二叉樹進(jìn)行層序遍歷和先序遍歷。&l

69、t;p>　?。?）概要設(shè)計(jì)或程序流程圖　　主函數(shù)設(shè)計(jì)　　void main ()　　{　　BTNode * b,*p;　　CreateBTNode

70、(b,"a(b(d,e),c(f,g)) ");　　printf("(1)輸出二叉樹:");DispBTNode (b);printf("\n");　　printf("(2)層次遍歷序列：");TravLevel(b);printf("\n");</

71、p>　　printf("(3)先序遍歷序列：");PreOrder(b);printf("\n");}　　用遞歸算法的先序遍歷函數(shù)　　void PreOrder(BTNode *b)　　{

72、　　if(b!=NULL)　　{　　printf ("%c",b->data);　　PreOrder(b->lchild);　　PreOrder(b->rchild);<

73、;/p>　　}　?。?）詳細(xì)設(shè)計(jì)或源代碼說明　　#include <stdio.h>　　#include <malloc.h>　　#define MaxSize 100</p&

74、gt;　　typedef char ElemType;　　typedef struct node　　{　　ElemType data;　　struct node *lchild;<p

75、>　　struct node *rchild;　　}BTNode;　　void CreateBTNode(BTNode *&b,char *str)//創(chuàng)建二叉樹　　{　　BTNod

76、e *St[MaxSize],*p=NULL;　　int top=-1,k,j=0;　　char ch;　　b=NULL;　　ch=str[j];　　wh

77、ile (ch!='\0')　　{　　switch (ch)　　{　　case'(':top++;St[top]=p;k=1;break;&

78、lt;p>　　case')':top--;break;　　case',':k=2;break;　　default:p=(BTNode *)malloc(sizeof(BTNode));　　p->data=ch;　　p->l

79、child=p->rchild=NULL;　　if(b==NULL)　　b=p;　　else　　{<b&

80、gt;　　switch(k)　　{　　case 1:St[top]->lchild=p;break;　　case 2:St[top]->rchild=p;break;　　}</b

81、>　　}　　}　　j++;　　ch=str[j];　　}</p&g

82、t;　　}　　void DispBTNode(BTNode *b)//括號(hào)表示法輸出二叉樹　　{　　if (b!=NULL)　　{<

83、;/p>　　printf ("%C",b->data);　　if(b->lchild!=NULL||b->rchild!=NULL)　　{　　printf("(");

84、　　DispBTNode(b->lchild);　　if(b->rchild!=NULL)printf(",");　　DispBTNode(b->rchild);　　printf(")");<

85、;b>　　}　　}　　}　　void TravLevel(BTNode *b)//層次遍歷　　{<p&

86、gt;　　BTNode *Qu[MaxSize];　　int front,rear;　　front=rear=0;　　if(b!=NULL)　　printf("%c",b->data);

87、　　rear++;　　Qu[rear]=b;　　while (rear!=front)　　{　　front=(front+1)%MaxSize;　　b=Qu[front];

88、　　if(b->lchild!=NULL)　　{printf("%c",b->lchild->data);　　rear=(rear+1)%MaxSize;　　Qu[rear]=b->lchild;<

89、p>　　}　　if(b->rchild!=NULL)　　{　　printf ("%c",b->rchild->data);　　rear=(rear+1)

90、%MaxSize;　　Qu[rear]=b->rchild;　　}　　}　　printf("\n");　　}&

91、lt;/b>　　void PreOrder(BTNode *b)//用遞歸算法的先序遍歷函數(shù)　　{　　if(b!=NULL)　　{　　printf

92、("%c",b->data);　　PreOrder(b->lchild);　　PreOrder(b->rchild);　　}　　}&l

93、t;p>　　void main ()　　{　　BTNode * b,*p;　　CreateBTNode (b,"a(b(d,e),c(f,g)) ");　　printf("(1)輸出二叉樹:&quo

94、t;);DispBTNode (b);printf("\n");　　printf("(2)層次遍歷序列：");TravLevel(b);printf("\n");　　printf("(3)先序遍歷序列：");PreOrder(b);printf("\n")

95、;　　}　　測(cè)試記錄　?。?）總結(jié)　　因?yàn)楸境绦蜃罱K要與其他兩個(gè)程序合并在一起，在主界面進(jìn)行選擇。所以在進(jìn)入主界面時(shí)要在本程序的主函數(shù)處修改字符，否則在調(diào)用本

96、程序時(shí)主函數(shù)會(huì)發(fā)生沖突。　　3、模塊9：赫夫曼樹的建立　?。?）系統(tǒng)分析　　建立函數(shù)輸入二叉樹，能夠輸出所輸入權(quán)值的赫夫曼編碼。　?。?）概要設(shè)計(jì)或程序流程圖　　通過控制臺(tái)輸入的形式得到建立赫

97、夫曼樹需要的參數(shù)——>調(diào)用生成赫夫曼樹的算法來生成赫夫曼樹，這個(gè)過程中還不斷的調(diào)用select方法來尋找當(dāng)前結(jié)點(diǎn)中權(quán)值最小的結(jié)點(diǎn)來生成樹的新結(jié)點(diǎn)，然后添加到樹中去——>通過用戶的選擇來輸出赫夫曼樹，其輸出的形式為：每個(gè)自符對(duì)應(yīng)的赫夫曼編碼。　　詳細(xì)設(shè)計(jì)或源代碼說明　　# include <stdio.h>&

98、lt;p>　　# include <malloc.h>　　# include <iostream.h>　　# include <conio.h>　　# include <string.h>　　# define MAX_

99、LENGTH 100　　typedef char **HuffmanCode;　　//數(shù)據(jù)結(jié)構(gòu)　　typedef struct 　　{ 　　int

100、 weight; //權(quán)值　　int parent,lchild,rchild; //雙親，左右孩子　　}HTNode,*HuffmanTree;　　//select函數(shù)　　void Select(HuffmanTree HT,int i,int &s1,int

101、&s2) 　　//在建立赫夫曼樹的所有結(jié)點(diǎn)中選擇權(quán)值最小的兩個(gè)結(jié)點(diǎn)存放在s1,s2中　　{　　int j,k=1;　　while(HT[k].parent!=0)

102、　k++;　　s1=k;　　for(j=1;j<=i;++j)　　if(HT[j].parent==0&&HT[j].weight<HT[s1].weight)　　s1

103、=j;　　k=1;　　while((HT[k].parent!=0||k==s1))　　k++;　　s2=k;&l

104、t;p>　　for(j=1;j<=i;++j)　　if(HT[j].parent==0&&HT[j].weight<HT[s2].weight&&j!=s1)　　s2=j;　　} <

105、/p>　　//構(gòu)建赫夫曼樹　　void HuffmanCoding(HuffmanTree &HT,HuffmanCode&HC,int *w,int n) 　　{　　int m,i,s1,s2

106、,start,c,f;　　HuffmanTree p;　　if(n<=1)　　return;　　m=2*n-1; //由得到的葉子數(shù)而計(jì)算結(jié)點(diǎn)總數(shù)</p

107、>　　HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//分配存儲(chǔ)空間　　for(p=HT+1,i=1;i<=n;++i,++p,++w) 　　{ 　　p->weight=*w;

108、 //為結(jié)點(diǎn)初始化權(quán)值　　p->parent=0;　　p->lchild=0;　　p->rchild=0;　　}　　for(;i<=m;++i,++p) <

109、/p>　　{　　p->weight=0;　　p->parent=0;　　p->lchild=0;　　p->rchild=0;　　}

110、 //初始化雙親和左右孩子，使他們成為孤立的　　for(i=n+1;i<=m;++i)　　{ 　　Select(HT,i-1,s1,s2); //調(diào)用select函數(shù)　　HT[s1].pare

111、nt=HT[s2].parent=i;　　HT[i].lchild=s1;　　HT[i].rchild=s2;　　HT[i].weight=HT[s1].weight+HT[s2].weight;//新結(jié)點(diǎn)的權(quán)值是s1和s2權(quán)值的和　　}</b&g

112、t;　　//赫夫曼編碼　　HC=(HuffmanCode)malloc((n+1)*sizeof(char *));　　char *cd;　　cd=(char *)malloc(n*sizeof(

113、char));　　cd[n-1]='\0';　　cout<<endl<<"HuffmanTree編碼是："<<endl;　　for(i=1;i<=n;++i) //從底下往上尋回編碼&

114、lt;b>　　{　　start=n-1;　　for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)　　if(HT[f].lchild==c)　　cd[--start]='0';</p&

115、gt;　　else　　cd[--start]='1';　　HC[i]=(char*)malloc((n-start)*sizeof(char));　　strcpy(HC[i],&cd[start]);<

116、;p>　　cout<<"HT[i] Huffman code is: "<<HC[i]<<endl;　　}　　free(cd);　　} ;

117、　　//主函數(shù)部分　　void main() 　　{ 　　HuffmanTree HT;　　HuffmanCode HC;<

118、;/p>　　int n,i;　　int *w,W[MAX_LENGTH];　　cout<<"***********本程序?qū)崿F(xiàn)的是赫夫曼樹的建立以及編碼*********";　　cout<<endl<

119、<"請(qǐng)輸入赫夫曼樹元素的個(gè)數(shù)： ";　　cin>>n;　　cout<<"請(qǐng)輸入各元素的權(quán)值:"<<endl;　　for(i=0;i<n;++i)&

120、lt;b>　　{　　cout<<"HT["<<i<<"].weight=";　　cin>>W[i];　　}<b&g

121、t;　　w=W;　　HuffmanCoding(HT,HC,w,n);}　　測(cè)試記錄　　當(dāng)建立一個(gè)含有5個(gè)初始結(jié)點(diǎn)，權(quán)值分別為2，4，6，8，10的赫夫曼樹的測(cè)試結(jié)果：　?。?）總結(jié)</b&

122、gt;　　算法時(shí)間復(fù)雜度：O(n2)　　此處只是赫夫曼樹的建立和輸出算法的實(shí)現(xiàn)，一個(gè)完整的赫夫曼編/譯碼系統(tǒng)其實(shí)可以進(jìn)一步完善，并且可以實(shí)現(xiàn)相關(guān)編碼解碼的功能。這也是赫夫曼樹在生活中用到最多的地方。　　總程序：　　# include

123、<stdio.h>　　# include <malloc.h>　　# include <iostream.h>　　# include <conio.h>　　# include <string.h></p&g

124、t;　　# define MAX_LENGTH 100　　typedef char **HuffmanCode;　　void e();　　//-------------------------模塊2----------------------------

125、--------　　void a(); 　　typedef struct Polynomial{　　float coef;　　int expn;　　struct Polynomial *nex

126、t;　　}*Polyn,Polynomial; //Polyn為結(jié)點(diǎn)指針類型　　void Insert(Polyn p,Polyn h){ 　　if(p->coef==0) free(p); //系數(shù)為0的話釋放結(jié)點(diǎn)&

127、lt;b>　　else{　　Polyn q1,q2;　　q1=h;q2=h->next;　　while(q2&&p->expn<q2->expn){ //查找插入位置　　q1=q2;&

128、lt;/b>　　q2=q2->next;　　}　　if(q2&&p->expn==q2->expn){ //將指數(shù)相同相合并　　q2->coef+=p->coef;</

129、p>　　free(p);　　if(!q2->coef){ //系數(shù)為0的話釋放結(jié)點(diǎn)　　q1->next=q2->next;　　free(q2);

130、　　}　　}　　else{ //指數(shù)為新時(shí)將結(jié)點(diǎn)插入　　p->next=q2;　　q1->next=p;</p

131、>　　}　　}　　}//Insert　　Polyn CreatePolyn(Polyn head,int m){//建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式</

132、p>　　int i;　　Polyn p;　　p=head=(Polyn)malloc(sizeof(struct Polynomial));　　head->next=NULL;&l

133、t;p>　　for(i=0;i<m;i++){　　p=(Polyn)malloc(sizeof(struct Polynomial));//建立新結(jié)點(diǎn)以接收數(shù)據(jù)　　printf("請(qǐng)輸入第%d項(xiàng)的系數(shù)與指數(shù):",i+1);　　scanf("%f %d",&

134、;p->coef,&p->expn);　　Insert(p,head); //調(diào)用Insert函數(shù)插入結(jié)點(diǎn)　　}　　return head;　　}//CreatePolyn<p&g

135、t;　　void DestroyPolyn(Polyn p){//銷毀多項(xiàng)式p　　Polyn q1,q2;　　q1=p->next;　　q2=q1->next;　　while(q1->next){

136、;　　free(q1);　　q1=q2;//指針后移　　q2=q2->next;　　}　　}　　void PrintPolyn(

137、Polyn P){ 　　Polyn q=P->next; 　　int flag=1;//項(xiàng)數(shù)計(jì)數(shù)器　　if(!q) { //若多項(xiàng)式為空，輸出0　　putchar('0'); 　　printf("\

138、n");　　return;　　} 　　while (q){　　if(q->coef>0&&flag!=1) putchar('+'); /

139、/系數(shù)大于0且不是第一項(xiàng)　　if(q->coef!=1&&q->coef!=-1){//系數(shù)非1或-1的普通情況　　printf("%g",q->coef); 　　if(q->expn==1) putchar('X');

140、;　　else if(q->expn) printf("X^%d",q->expn);　　}　　else{　　if(q->coef==1){<p&g

141、t;　　if(!q->expn) putchar('1'); 　　else if(q->expn==1) putchar('X'); 　　else printf("X^%d",q->expn);　　}<

142、;/p>　　if(q->coef==-1){　　if(!q->expn) printf("-1"); 　　else if(q->expn==1) printf("-X"); 　　else printf("-X^%d&q

143、uot;,q->expn);　　}　　}　　q=q->next; 　　flag++;

144、　}//while　　printf("\n");　　}//PrintPolyn　　int compare(Polyn a,Polyn b){　　if(a&&b){</p&g

145、t;　　if(!b||a->expn>b->expn) return 1;　　else if(!a||a->expn<b->expn) return -1;　　else return 0;　　}

146、　　else if(!a&&b) return -1;//a多項(xiàng)式已空，但b多項(xiàng)式非空　　else return 1;//b多項(xiàng)式已空，但a多項(xiàng)式非空　　}//compare　　Polyn AddPolyn(Polyn pa,Polyn pb){//求解并建立多項(xiàng)式a+b，返回其

眾賞文庫> 全部分類> 畢業(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)頁內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲(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ì)報(bào)告

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

算法與數(shù)據(jù)結(jié)構(gòu)－課程設(shè)計(jì)報(bào)告

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載