數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---利用線性表進(jìn)行算式計(jì)算

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---利用線性表進(jìn)行算式計(jì)算_第1頁

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

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

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告　　利用線性表進(jìn)行算式計(jì)算　　一：問題描述：　　在計(jì)算機(jī)中，算術(shù)表達(dá)式由常量、變量、運(yùn)算符號和括號組成，由于不同的運(yùn)算符具有不同的優(yōu)先級，又要考慮到括號，因此，算術(shù)表達(dá)式的求值不可能嚴(yán)格地從左往右進(jìn)行，因而在程序設(shè)計(jì)時(shí)，借助棧實(shí)現(xiàn)。&

2、lt;/p>　　算法要點(diǎn)：設(shè)置運(yùn)算符棧和運(yùn)算數(shù)隊(duì)列輔助分析算符優(yōu)先關(guān)系，在讀入表達(dá)式的字符序列的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)的識別處理，以及相應(yīng)運(yùn)算。　　二：需求分析　　1、輸入的形式和輸入值的范圍　　一個(gè)算術(shù)表達(dá)式，由常量、變量、運(yùn)算符和括號組成（以

3、字符串的形式輸入）。為簡化，規(guī)定操作數(shù)只能為整數(shù)，操作符為“+”、“-”、“*”、“/”、“%”，用“#”開始且用“#”結(jié)束，優(yōu)先級為：括號--%--*,/--+,-。　　2、輸出的形式　　即輸出表達(dá)式運(yùn)算結(jié)果，本算法中輸出的形式為The end is：.....　　3、程序

4、所能達(dá)到的功能　　界面上出現(xiàn)一個(gè)文本框，輸入一個(gè)表達(dá)式（以“#”開始并以“#”結(jié)束，此表達(dá)式包括“+”、“-”、“*”、“/”、“%”、括號以及整數(shù)），點(diǎn)擊回車，顯示結(jié)果。　　4、測試結(jié)果　　正確的輸入一個(gè)表達(dá)式是指輸入一個(gè)正確的表達(dá)式即不能連續(xù)輸入兩個(gè)運(yùn)算符（括號除外），切

5、以“#”開始以“#”結(jié)束，點(diǎn)擊回車界面上出現(xiàn)The end is：……即此表達(dá)式的結(jié)果。　　輸入表達(dá)式錯(cuò)誤有兩種形式：　?。?）、所輸入的表達(dá)式未以“#”開始則點(diǎn)擊回車，系統(tǒng)會(huì)提示“RROE!Please begin with "#“，“且下面輸出”Continue?(y/n):“，若輸入Y或者y，則再次進(jìn)入主界面輸入表達(dá)式，若輸入N或者n,則

6、跳出系統(tǒng)。　?。?）、所輸入的表達(dá)式錯(cuò)誤，即連續(xù)輸入兩個(gè)運(yùn)算符，此時(shí)系統(tǒng)會(huì)提示“ERROE!Please input another time!“，　　三：概要設(shè)計(jì) 　　主程序的流程圖為<

7、;b>　　四：詳細(xì)設(shè)計(jì)　　1、本系統(tǒng)中所用到的抽象數(shù)據(jù)類型有棧的抽象數(shù)據(jù)類型以及隊(duì)列的抽象數(shù)據(jù)類型。　　棧的抽象數(shù)據(jù)類型定義：　　ADT Stack{　　數(shù)據(jù)對象：D={ai| ai ∈ElemSet,i=1,2,3……n,n≥0}</p&

8、gt;　　數(shù)據(jù)關(guān)系：R1={ <ai-1, ai ∈D,i=2,3……n}　　基本操作：　　InitStack（&S）　　操作結(jié)果：構(gòu)造一個(gè)空棧　　DestoryStack（&S）</

9、p>　　初始條件：棧S已存在。　　操作結(jié)果：棧S被銷毀。　　ClearStack（&S）　　初始條件：棧S已存在。　　操作結(jié)果：將S清為空棧。　　StackEmpty（&S）</p

10、>　　初始條件：棧S已存在。　　操作結(jié)果：若棧S為空棧，則返回TRUE,否則返回FALSE。　　StackLength（&S）　　初始條件：棧S已存在。　　操作結(jié)果：返回S的元素個(gè)數(shù)，即棧的長度。

11、;　　GetTop（S，&e）　　初始條件：棧S已存在且非空。　　操作結(jié)果：用e返回S的棧頂元素。　　Push（S，&e）　　初始條件：棧S已存在。　　操作結(jié)果：插入元素e為新的棧頂元素。&

12、lt;p>　　Pop（S，&e）　　初始條件：棧S已存在且非空。　　操作結(jié)果：刪除S的棧頂元素，并用e返回其值。　　StackTraverse（S，visit()）　　初始條件：棧S已存在且非空。

13、　　操作結(jié)果：從棧底到棧頂一次對S的每個(gè)元素調(diào)用函數(shù)visit（）。一旦visit（）失敗，則操作失敗。　　}ADT stack　　隊(duì)列的抽象數(shù)據(jù)類型定義：　　ADT Queue{　　數(shù)據(jù)對象：D={ai| ai ∈ElemSet,i=1,2,3……n,

14、n≥0}　　數(shù)據(jù)關(guān)系：R1={ <ai-1, ai ∈D,i=2,3……n}　　約定其中ai端為隊(duì)列頭，an端為隊(duì)列尾　　基本操作：　　InitQueue（&Q）　　操作結(jié)果：構(gòu)

15、造一個(gè)空隊(duì)列Q。　　DestoryQueue（&Q）　　初始條件：隊(duì)列Q已存在。　　操作結(jié)果：隊(duì)列Q被銷毀。　　ClearQueue（&Q）　　初始條件：隊(duì)列Q已存在。

16、操作結(jié)果：將Q清為空隊(duì)列。　　QueuekEmpty（&Q）　　初始條件：隊(duì)列Q已存在。　　操作結(jié)果：若隊(duì)列Q為空棧，則返回TRUE,否則返回FALSE。　　QueueLength（Q）　　初始條件：隊(duì)列Q已存在。<

17、/p>　　操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列的長度。　　GetHead（Q，&e）　　初始條件：隊(duì)列Q已存在且非空。　　操作結(jié)果：用e返回Q的隊(duì)頭元素。　　EnQueue（Q，&e）

18、初始條件：隊(duì)列Q已存在。　　操作結(jié)果：插入元素e為新的隊(duì)尾元素。　　DeQueue（Q，&e）　　初始條件：隊(duì)列Q已存在且非空。　　操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。　　QueueTraverse（Q，visit

19、()）　　初始條件：Q已存在且非空。　　操作結(jié)果：從隊(duì)頭到隊(duì)尾一次對Q的每個(gè)元素調(diào)用函數(shù)visit（）。一旦visit（）失敗，則操作失敗。　　}ADT queue　　2、主要算法流程圖　　算

20、符間的優(yōu)先關(guān)系為如下圖，其中#代表表達(dá)式的結(jié)束符，為了算法簡潔，在表達(dá)式的最左邊也虛設(shè)一個(gè)“#“構(gòu)成整個(gè)表達(dá)式的一對括號。　　3、各模塊間的層次調(diào)用　?。?）.算法思路 　　a.若導(dǎo)入的是操作數(shù)，則直接輸出到隊(duì)列。　　b.若當(dāng)前運(yùn)算符

21、的優(yōu)先級高于棧頂運(yùn)算符的優(yōu)先級，則入棧。　　c.若當(dāng)前運(yùn)算符的優(yōu)先級低于棧頂運(yùn)算符的優(yōu)先級，則棧頂運(yùn)算符退棧，并輸出到隊(duì)列，當(dāng)前運(yùn)算符再與新的棧頂運(yùn)算符比較。　　d.若當(dāng)前運(yùn)算符的優(yōu)先級等于棧頂運(yùn)算符的優(yōu)先級，且棧頂運(yùn)算符為左括號，當(dāng)前運(yùn)算符為右括號，則棧頂運(yùn)算符退棧，繼續(xù)讀下一個(gè)符號。　　e.若當(dāng)前運(yùn)算符的優(yōu)先

22、級等于棧頂運(yùn)算符的優(yōu)先級，且棧頂運(yùn)算符為“#“，當(dāng)前運(yùn)算符也為”#“，則棧頂運(yùn)算符退棧，輸出隊(duì)列中的數(shù)值即可。　?。?）.各個(gè)函數(shù)的含義　　頭函數(shù)結(jié)束以后用typedef struct snode{ }定義棧的結(jié)構(gòu)體，void initiatels(slnode *h){ }此函數(shù)是對棧的初始化，即構(gòu)造一個(gè)空棧，void pushls( slnode *

23、h,char *x){ }、char *popls( slnode *h,char *x){ }，分別是進(jìn)棧出棧函數(shù)的實(shí)現(xiàn)。typedef struct qnode{ }隊(duì)列的結(jié)構(gòu)體定義，typedef struct{ }此函數(shù)是對隊(duì)列的初始化，即構(gòu)造一個(gè)空隊(duì)列，void initiatelq(lqtype *q){ }、void enterlq(lqtype *q,char *x){ }，分別是入隊(duì)列以及出隊(duì)列的實(shí)現(xiàn)。這就是函數(shù)模塊的

24、實(shí)現(xiàn)，除此之外在主函數(shù)main（）函數(shù)中利用函數(shù)while（c！=“#“）{ }即可獲取屏幕上輸入的字符，數(shù)據(jù)和運(yùn)算符并分別將其存放在結(jié)點(diǎn)中，利用函數(shù)while（x【0】！=35）{ }來判斷x進(jìn)入符號棧還是隊(duì)列，enterlq（operand，x）；說明x是數(shù)據(jù)則進(jìn)入隊(duì)列，利用函數(shù)if（a<=b）{ }判斷如果x的優(yōu)先級大于當(dāng)前棧頂元素的優(yōu)　　五：調(diào)試分析</b&

25、gt;　　本實(shí)驗(yàn)要調(diào)試成功在此之前肯定遇到很多困難經(jīng)常會(huì)出現(xiàn)一些說明語法錯(cuò)誤以及出現(xiàn)一些語法錯(cuò)誤等各種各樣的問題，此時(shí)要檢查自己的代碼，找到自己代碼的問題所在，不折不撓多次調(diào)試即可。　　本實(shí)驗(yàn)的時(shí)間復(fù)雜度是O（n），空間復(fù)雜度為O（n）。此實(shí)驗(yàn)是利用一個(gè)棧和一個(gè)隊(duì)列，可以改進(jìn)為兩個(gè)棧的運(yùn)算，一個(gè)棧存放運(yùn)算符，另外一個(gè)棧存放運(yùn)算數(shù)據(jù)。

26、　　本實(shí)驗(yàn)算法采用了鏈?zhǔn)酱鎯Y(jié)構(gòu)，以開辟新空間為代價(jià)，有效降低了算法時(shí)間復(fù)雜度和空間復(fù)雜度，并且對表達(dá)式的長度沒有要求。　　六：測試結(jié)果　　調(diào)試成功后進(jìn)入的頁面為　　輸入正確的表達(dá)式后<p

27、>　　點(diǎn)擊y重新進(jìn)入主頁面　　若輸入錯(cuò)誤的表達(dá)式后　　七：附錄　　源程序　　#include<stdio.h>　　#include &l

28、t;conio.h>　　#include<stdlib.h>　　#include<math.h>　　#include<string.h>　　#include<graphics.h><p&g

29、t;　　#define null 0　　typedef struct snode //定義結(jié)構(gòu)體　　{　　char data[11];　　struct snode *next;<b&g

30、t;　　}slnode;　　void initiatels(slnode *h) //初始化　　{　　h->next = null;　　}void pushls( slnode *h,char *x) //壓

31、棧　　{　　slnode *p;　　p = (slnode *)malloc(sizeof(slnode));　　strcpy(p->data,x);　　p->next = h-&

32、gt;next;　　h->next = p;　　}　　char *popls( slnode *h,char *x) //出棧　　{　　slnod

33、e *p;　　p = h->next;　　if(p!=null)　　{　　h->next = p->next;　　return(p->data);

34、　　}　　return(x);　　}　　typedef struct qnode //定義鏈隊(duì)列結(jié)構(gòu)體　　{&l

35、t;p>　　char data[11];　　struct qnode *next;}qlnode;　　typedef struct　　{　　qlnode *h;　　qlnode *rea

36、r;　　}lqtype;　　void initiatelq(lqtype *q) //初始化　　{　　q->rear = q->h;　　q-

37、>h->next = null;　　}　　void enterlq(lqtype *q,char *x) //入隊(duì)　　{　　qlnode *p;<p&g

38、t;　　p = (qlnode *)malloc(sizeof(qlnode));//申請新結(jié)點(diǎn)　　strcpy(p->data,x); //新結(jié)點(diǎn)數(shù)據(jù)域賦值　　p->next = null;　　if(q->h==null)　　q-&g

39、t;h = p;　　q->rear->next = p;　　q->rear = p; //修改尾指針　　}　　char *deletelq(lqtype *q,char *x) //出隊(duì)<

40、/p>　　{　　qlnode *p;　　p = q->h->next; // 暫存原隊(duì)頭指針　　if(q->h->next!=null) //隊(duì)非空　　{ q->h-

41、>next=p->next; //刪除隊(duì)頭元素　　if(q->h->next==null)　　q->rear->next=null;　　return(p->data);　　}</p&g

42、t;　　return(x);　　}　　void main()　　{　　char ch[8]={'#','+','-','

43、;*','/','%','(',')'};　　char c,cc, x[11],y[11],z[11];　　int i,j,a,b,n;　　int t;　　sln

44、ode *operater,*pp;　　lqtype *mid,*operand;　　qlnode *ee;　　int mm;　　operater = (slnode *)malloc(sizeof(slnode));</p&g

45、t;　　mid = (lqtype *)malloc(sizeof(lqtype));　　mid->h = (qlnode *)malloc(sizeof(qlnode));　　mid->rear = (qlnode *)malloc(sizeof(qlnode));　　oper

46、and = (lqtype *)malloc(sizeof(lqtype));　　operand->h = (qlnode*)malloc(sizeof(qlnode));　　operand->rear = (qlnode *)malloc(sizeof(qlnode));　　textmode(C80

47、);　　textbackground(3);　　clrscr();　　window(8,8,70,18);　　textbackground(7);　　textcolor(18);</p&

48、gt;　　clrscr();　　while(1)　　{ //初始化　　initiatelq(mid);　　initiatels(operater);&l

49、t;/p>　　initiatelq(operand);　　j = 0;　　a = 0;　　b = 0;　　n =

50、 0;　　for(i=0;i<11;i++)　　x[i]='\0';　　clrscr();　　cprintf( "\nPlease input the biaodashi(begin

51、 by\"#\"from left and stop by\"#\"from right)\n");　　cprintf("\nThe string is:");　　c = getchar();　　x[0]=c;</b&g

52、t;　　enterlq(mid,x); //將“#“進(jìn)隊(duì)　　c=getchar();　　x[0]=c;　　j=1;　　c=getchar();</

53、p>　　while(c!='#') //獲取屏幕上輸入的字符，數(shù)據(jù)和運(yùn)算符分別存放在結(jié)點(diǎn)中　　{　　if(c<48&&c!=46)　　{<p

54、>　　if(x[0]!=0)　　{　　enterlq(mid,x);　　for(i = 0;i < 11;i++)　　x[i]='\0';　　j

55、= 0;　　continue;　　}　　else　　{&l

56、t;b>　　x[0] = c;　　j = 1;　　ee=mid->rear;　　if(ee->data[0]!='(')　　{</p&g

57、t;　　enterlq(mid,x);　　for(i = 0;i < 11;i++)　　x[i]='\0';　　j=0;　　}&

58、lt;p>　　}　　}　　else　　{　　x[j] = c;</p&

59、gt;　　j++;　　}　　c=getchar();　　}　　if(x[0]!=0)<b

60、>　　{　　enterlq(mid,x);　　for(i = 0; i < 11;i++)　　x[i]='\0';　　}　　x

61、[0] = c;　　enterlq(mid,x);　　for(i = 0;i <11; i++)　　x[i]='\0';　　getchar();　　ee = mid->h->n

62、ext; //表達(dá)式合法性檢驗(yàn)　　if(ee->data[0]!='#')　　{　　printf("\n ERROE!Please begin with \"#\"\n");

63、　　printf(" Continue?(y/n):",x);　　cc = getchar();　　getchar();　　if(cc =='n'||cc=='N')

64、　break;　　else　　if(cc =='y'||cc=='Y')　　continue;　　}<

65、;/p>　　while(ee->next!=null)　　{　　if(strlen(ee->data)==1&&ee->data[0]=='(')　　a++;&

66、lt;/p>　　if(strlen(ee->data)==1&&ee->data[0]==')')　　b++;　　if(strlen(ee->data)==1&&strlen(ee->next->data)==&

67、lt;/p>　　1&&ee->data[0]<48&&ee->next->data[0]<48&&ee->　　data[0]!=41&&ee->data[0]!=40&&ee->next->data[0]!=&l

68、t;p>　　41&&ee->next->data[0]!=40)　　{　　n=1;　　break;　　}&

69、lt;/b>　　ee = ee->next;　　}　　if(a!=b||n!=0)　　{　　printf("\n

70、 ERROE!Please input another time!");　　printf("\n Continue?(y/n):",x);　　cc = getchar();　　getchar();　　if(cc ==

71、9;n'||cc=='N')　　break;　　else　　if(cc =='y'||cc=='Y')　　continue

72、;　　}　　strcpy(x,deletelq(mid,z));　　pushls(operater,x); //將“#“進(jìn)入符號棧　　strcpy(x,deletelq(mid,z));//依次將mid出隊(duì)<

73、;/p>　　while (x[0]!=35)//判斷x進(jìn)入符號棧還是進(jìn)入隊(duì)列　　{　　if(x[0]>47||x[1]>47)　　enterlq(operand,x);//x是數(shù)據(jù)則進(jìn)入隊(duì)列

74、else if(x[0]!=41)　　{　　pp=operater->next;　　strcpy(y,pp->data);　　while(y[0]!=40)　　{

75、　　for(i=6;i>=0;i--)　　{　　if(ch[i]==x[0])　　a=i;　　if(ch[i]==y[0])&l

76、t;/p>　　b=i;　　}　　if(a<=b)　　{　　enterlq(operan

77、d,popls(operater,z));　　pp=operater->next;　　strcpy(y,pp->data);　　continue;　　} //如果x的優(yōu)先級大于當(dāng)前棧頂元素的優(yōu)先級，則進(jìn)棧</p&g

78、t;　　pushls(operater,x);　　break;　　}　　if(y[0]==40)　　{<p

79、>　　pushls(operater,x);　　strcpy(x,deletelq(mid,z));　　continue;　　}　　} //x是“）“，則依次輸出符號棧的元素，放進(jìn)隊(duì)列中，

80、知道遇到”（“為止　　else　　{　　pp=operater->next;　　strcpy(y,pp->data);　　while(y[0]

81、!=40)　　{　　enterlq(operand,popls(operater,z));　　pp=operater->next;　　strcpy(y,pp->data);<

82、b>　　}　　strcpy(y,popls(operater,z));　　}　　strcpy(x,deletelq(mid,z));　　}<

83、p>　　pp=operater->next;　　strcpy(y,pp->data);　　//mid為空后，一次輸出符號棧的元素至隊(duì)列中，直到遇到“#“為止　　while (y[0]!=35)　　{

84、;　　enterlq(operand,popls(operater,z));　　pp=operater->next;　　strcpy(y,pp->data);　　}//最終operand為后綴表達(dá)式　　ee=operand->h-&

85、gt;next;//求出后綴表達(dá)式的值　　while(operand->h->next->next!=null)　　{　　strcpy(x,ee->data);　　strcpy(y,ee->next-&g

86、t;data);　　if(ee->next->next!=null)　　strcpy(z,ee->next->next->data);　　else　　{</p&

87、gt;　　ee=operand->h->next;　　continue;　　}　　if((x[0]>47||x[1]>47)&&(y[0]>47||y[1]>47)

88、&&(z[0]<　　48&&strlen(z)==1))　　{　　switch(z[0])　　{　　case

89、9;+':mm=atof(x)+atof(y);　　break;　　case '-':mm=atof(x)-atof(y);　　break;　　case '*

90、9;:mm=atof(x)*atof(y);　　break;　　case '/':mm=atof(x)/atof(y);　　break;　　case '%':mm=

91、atoi(x)%atoi(y);　　break;　　}　　strcpy(ee->data,gcvt(mm,11,z)); ee->next=ee->next->n

92、ext->next;　　ee=operand->h->next;　　continue;　　}　　if(ee->next->next!=null)

93、　　ee=ee->next;　　else　　ee=operand->h->next;　　}　　strcpy(x,deletelq(operand,z)); /

94、/輸出最終結(jié)果　　printf("\n The end:%s\n",x);　　printf(" Continue?(y/n)",x);　　cc=getchar();　　getchar();</

95、p>　　if(cc=='n'||cc=='N')　　break;　　}　　}　　利用樹進(jìn)行哈弗曼編

96、碼　　一：問題描述　　利用哈弗曼編碼進(jìn)行通信可以大大提高信道的利用率，縮短信息傳輸時(shí)間，降低傳輸成本，但是，這要求發(fā)送端通過一個(gè)編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼，對于雙工通道（即可以雙向傳輸?shù)男诺溃?，每端都要有一個(gè)完整的編碼譯碼系統(tǒng)，因此可以設(shè)計(jì)一個(gè)編碼譯碼系統(tǒng)解決這樣一個(gè)問題。</p&

97、gt;　　二：實(shí)驗(yàn)內(nèi)容　　文件conf.txt中保存了若干字母及其出現(xiàn)的頻度，要求所有頻度加起來要為1，否則載入時(shí)報(bào)錯(cuò)。字母及其頻度保存的格式為：　　a:0.1　　b:0.2&l

98、t;/p>　　c:0.3　　……　　界面上，首先出現(xiàn)一個(gè)按鈕，點(diǎn)擊，載入conf.txt。然后輸入一個(gè)字符串，由這些字母組成。點(diǎn)擊按鈕，顯示哈夫曼編碼的結(jié)果。同時(shí)，界面上如果輸入哈夫曼編碼，也能被翻譯成相應(yīng)的字母。如果輸入格式錯(cuò)誤，要求給予提示。<

99、;/p>　　三：概要設(shè)計(jì)　　1、系統(tǒng)結(jié)構(gòu)圖（功能模塊圖）　　2、功能模塊說明　?。?）、編碼：讀取文件——建立哈夫曼樹——對文本進(jìn)行哈弗曼編碼并輸出編碼　?。?）、譯碼

100、：提示輸入需要譯碼的字符——利用建好的哈夫曼樹進(jìn)行譯碼　　(3)、退出：退出系統(tǒng)，程序運(yùn)行結(jié)束。　　四：詳細(xì)設(shè)計(jì)　　主要算法流程圖 　　創(chuàng)建哈夫曼樹<

101、/p>　　編碼　　譯碼　　五：調(diào)試分析　　從葉子節(jié)點(diǎn)開始向上遍歷樹，獲得哈弗曼編碼；　　根據(jù)哈弗曼編碼遍歷哈夫曼樹直到葉子結(jié)點(diǎn)，得

102、到譯碼；　　算法時(shí)間復(fù)雜度的分析：時(shí)間復(fù)雜度為O(n2);　　算法空間復(fù)雜度的分析：空間復(fù)雜度為O（n）。　　六：測試結(jié)果　　由于本實(shí)驗(yàn)是圖形化界面，故無法得到完整的圖形界面，但進(jìn)入主頁面以后即可看到以下界面。

103、　　這將是進(jìn)入之后點(diǎn)擊譯碼所得到的界面　　再次點(diǎn)擊回車即可看到如圖所示　　七：附錄　　#include<stdio.h>　　#include<string.h><

104、p>　　#include<graphics.h>　　#include<conio.h>　　#include<dos.h>　　#include<alloc.h>　　#include<ctype.h></

105、p>　　#define UP 50　　#define DOWN 90　　#define LEFT 60　　#define RIGHT 55　　#define ENTER 40　　#define N 50

106、　　#define M 2*N-1　　#define SIZE 6　　typedef struct //定義結(jié)構(gòu)體存放哈夫曼碼　　{　　char data;<

107、p>　　float weight;　　int parent,lchild,rchild;　　}HTNode;　　int choice;　　int key()<p

108、>　　{　　union REGS lf;　　lf.h.ah=0;　　int86(0x16,&lf,&lf);　　return lf.h.ah;　　}&l

109、t;/b>　　struct imformation　　{　　char ch;　　float fre;　　}&l

110、t;/p>　　imfor[SIZE]={{'a',0.3},{'b',0.2},{'c',0.1},{'d',0.2},{'e',0.1},{'f',0.1}};　　//給相關(guān)字符設(shè)置初值　　typedef struct</p

111、>　　{　　char cd[N];　　int start;　　}HCode;　　void CreateHT(HTNode ht[],int n)

112、　　{　　int i,k,lnode,rnode;　　float min1,min2; for (i=0;i<2*n-1;i++)　　ht[i].parent=ht[i].lchild=ht[i].rchild=-1;</p&

113、gt;　　for (i=n;i<2*n-1;i++) //構(gòu)造哈夫曼樹　　{　　min1=min2=1.1; //使用兩個(gè)最小權(quán)值的結(jié)點(diǎn)為左孩子和右孩子　　lnode=rnode=-1;　　for (k=

114、0;k<=i-1;k++)　　if (ht[k].parent==-1)　　{　　if (ht[k].weight<min1)　　{　　min

115、2=min1;rnode=lnode;　　min1=ht[k].weight;lnode=k;　　}　　else if (ht[k].weight<min2)　　{&

116、lt;p>　　min2=ht[k].weight;rnode=k;　　}　　}　　ht[lnode].parent=i;ht[rnode].parent=i;　　ht[i].weight=h

117、t[lnode].weight+ht[rnode].weight;　　ht[i].lchild=lnode;ht[i].rchild=rnode;　　}　　getchar();　　}</p&

118、gt;　　void CreateHCode(HTNode ht[],HCode hcd[],int n)　　{　　int i,f,j,c;　　HCode hc;　　for (

119、i=0;i<n;i++) //根據(jù)哈夫曼樹求哈夫曼編碼　　{　　hc.start=n;　　c=i;　　f=ht[i].parent;　　while

120、 (f!=-1) //回溯到樹根結(jié)點(diǎn)　　{　　if (ht[f].lchild==c) //遍歷做孩子結(jié)點(diǎn)　　hc.cd[hc.start--]='0';　　else //遍歷孩子的右結(jié)點(diǎn)

121、　　hc.cd[hc.start--]='1';　　c=f;f=ht[f].parent;　　}　　hc.start++;　　hcd[i]=hc;<b

122、>　　}　　}　　void huffmancode(HTNode ht[],HCode hcd[],int n)　　{　　char b[M],*p;

123、　　int i,j,m,k;　　printf("please input the words:\n");　　scanf("%s",b);　　m=strlen(b);　　for(i=0,p=b;i<m;i++

124、,p++)　　{　　for(j=0;j<n;j++)　　if(ht[j].data==*p)　　for (k=hcd[j].start;k<=n;k++)　　printf(&quo

125、t;%c",hcd[j].cd[k]);　　}　　getch();　　printf("\n");　　}&

126、lt;p>　　void words(HTNode ht[],int n)　　{　　int c;　　char code[1000],*p;　　printf("please input

127、 numbers:\n");　　scanf("%s",code);　　for(p=code,c=2*n-2;*p!='\0';p++)　　{　　if(*p=='0')<

128、;/p>　　{　　c=ht[c].lchild;　　if(ht[c].lchild==-1)　　{　　printf("%c",ht[c].data)

129、;　　c=2*n-2;　　continue;　　}　　}　　else if(*

130、p=='1')　　{　　c=ht[c].rchild;　　if(ht[c].lchild==-1)　　{　　printf("%c

131、",ht[c].data);　　c=2*n-2;　　continue;　　}　　}&l

132、t;p>　　}　　getch();　　printf("\n");　　}　　mainmenu()<p&g

133、t;　　{　　cleardevice();　　setbkcolor(3); //設(shè)置當(dāng)前背景顏色　　setcolor(2); //設(shè)置當(dāng)前畫筆顏色　　rectangle(40,60,600,440);&l

134、t;p>　　line(40,100,600,100);　　outtextxy(240,80,"Huffman");　　rectangle(150,145,350,195);　　setfillstyle(1,12);　　floodfill(160,

135、150,14);　　outtextxy(152,150,"a. Print huffman code");　　outtextxy(152,200,"b. Print words");　　outtextxy(152,250,"c. Quit");</

136、p>　　}　　void change(char *select[],int n1,int n2,int x0,int len,int y0,int wid1,int wid2)　　//完成兩個(gè)窗口間的互換　　{

137、　　setviewport(x0,y0+wid2*n1,x0+len,y0+wid1+wid2*n1,1);　　clearviewport();　　setcolor(2); //設(shè)置當(dāng)前背景顏色　　settextstyle(4,0,10);&l

138、t;p>　　outtextxy(2,5,select[n1]);　　setviewport(x0,y0+wid2*n2,x0+len,y0+wid1+wid2*n2,1);　　clearviewport();　　setfillstyle(1,12);　　setcol

139、or(2);　　rectangle(0,0,len,wid1);　　floodfill(30,5,1);　　setcolor(1);　　settextstyle(4,0,10);　　outtextxy(2,5,select[n2]

140、);　　}　　void main()　　{　　int n=SIZE,i,a,j,n1=0,n2=0;　　float sum=0;&

141、lt;p>　　char *select[3]={"a.Print huffman code","b.Print words","c.Quit"};　　HTNode ht[M];　　HCode hcd[N];　　FILE *fp;&

142、lt;/b>　　char b[M];　　int graphdriver=DETECT,graphmode;　　initgraph(&graphdriver,&graphmode,"\\TC++");　　registerbgidri

143、ver(EGAVGA_driver);　　cleardevice();　　setbkcolor(1);　　setviewport(0,0,639,479,1);　　clearviewport();　　setbkcolor(1);&

144、lt;/p>　　setcolor(2);　　rectangle(250,200,390,280);//在圖形界面上畫一個(gè)矩形框　　setfillstyle(1,5);　　floodfill(300,240,14);　　settextstyle(

145、4,0,10);　　outtextxy(252,202,"ENTER");　　outtextxy(200,10," THE HUFFMANCODE TRANSLATOR"); line(0,30,640,30);　　getchar();<

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

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---利用線性表進(jìn)行算式計(jì)算

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---利用線性表進(jìn)行算式計(jì)算

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載