魔王語言解釋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告

1、魔王語言解釋程序一、 問題引入1. 問題描述有一個(gè)魔王總是使用自已的一種非常精練而抽象的語言講話，沒有人能聽得懂。但他的語言是可以逐步解釋成人能懂的語言的，因?yàn)樗恼Z言是由以下兩種形式的規(guī)則由人的語言逐步抽象上去的： （1）12m （2）(12m)(m21) 在這兩種形式中，從左到右均表示解釋。寫一個(gè)魔王解釋程序，將魔王的話解釋成人能聽懂的話。2. 基本要求用下述兩種規(guī)則和下述規(guī)則（2）實(shí)現(xiàn)。設(shè)大寫字母表示魔王語言的詞匯，小寫字母表示人的詞匯，希臘字母表示可以用大寫字母或小寫字母代換的變量。魔王語言可含人的詞匯。(1) BtAdA (2) Asae 3. 測(cè)試數(shù)據(jù)B(einxgz)B解釋成ts

2、aedsaeezegexeneietsaedsae若將小寫字母與漢字建立下表所示的對(duì)應(yīng)關(guān)系，則魔王說的話是：“天上一只鵝地上一只鵝鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一只鵝地上一只鵝”。tdsaezgxnh天地上一只鵝追趕下蛋恨4實(shí)現(xiàn)提示 將魔王的語言自右至左進(jìn)棧，總是處理?xiàng)ｍ斪址Ｈ羰情_括號(hào)，則逐一出棧，將字母順序入隊(duì)列，直至閉括號(hào)出棧，并按規(guī)則要求逐一出隊(duì)列在處理后入棧。5.本程序采用的是順序棧?；静僮髁斜恚?1) 據(jù)括號(hào)的個(gè)數(shù)設(shè)一個(gè)標(biāo)記。記下括號(hào)的位置。(2) 根據(jù)標(biāo)記來執(zhí)行依次的操作。(3) 沒有括號(hào)，直接進(jìn)隊(duì)，據(jù)翻譯函數(shù)2輸出人的語言。(4) 有括號(hào)，分為括號(hào)內(nèi)的和括號(hào)外的。，根據(jù)括號(hào)的位置

3、：括號(hào)外的從右到左入棧；括號(hào)內(nèi)的從左到右入棧，并且依次插入括號(hào)內(nèi)的第一個(gè)字符。據(jù)翻譯函數(shù)2 出棧并且翻譯。二、需求分析1. 本演示程序中，魔王語言限制在小寫字母a-z之間，且必須限制在括號(hào)內(nèi)以及大寫字母A和B。且允許出現(xiàn)重復(fù)字符或非法字符，程序運(yùn)用時(shí)自動(dòng)過濾去，輸出的運(yùn)算結(jié)果中將不含重復(fù)字符和非法字符。2. 魔王語言遵守如下規(guī)則： （123n）nn-11BtAdA Asae 3. 演示程序以用戶和計(jì)算機(jī)對(duì)話的形式進(jìn)行，即在計(jì)算機(jī)終端中顯示提示信息之后，有用戶自行選擇下一步命令，相應(yīng)輸入數(shù)據(jù)和運(yùn)算結(jié)果在其后顯示。4. 程序的執(zhí)行命令有：1）選擇操作 2）任意鍵結(jié)束5. 數(shù)據(jù)測(cè)試 B(ehnxgz

4、)B解釋成：tsaedsaeezegexenehetsaedsae若將小寫字母與漢字建立下表所示的對(duì)應(yīng)關(guān)系，則魔王說的話是：“天上一只鵝地上一只鵝鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一只鵝地上一只鵝”。tdsaezgxnh天地上一只鵝追趕下蛋恨三、概要設(shè)計(jì)為實(shí)現(xiàn)上述功能，需要棧和隊(duì)列兩個(gè)抽象數(shù)據(jù)類型。1. 棧抽象數(shù)據(jù)類型定義ADT stack數(shù)據(jù)對(duì)象：D=ai|aiElemset,i=1,2,3,n,n=0數(shù)據(jù)關(guān)系：R1=|ai-1,aiD,i=2, n基本操作：InitStack(&s)操作結(jié)果：構(gòu)造一個(gè)空棧s。Push(&s, e)初始條件：棧s已存在。操作結(jié)果：插入元素e為新的棧頂元素。Pop(&

5、s, &e)初始條件：棧s已存在且非空。操作結(jié)果：刪除棧s的棧頂元素，并用e返回其值。StackLenth(&s)初始條件：棧s已存在。操作結(jié)果：返回s的元素個(gè)數(shù)，即棧的長(zhǎng)度。ClearStack(&s)初始條件：棧s已存在。操作結(jié)果：將s清為空棧。DestoryStack(&s)初始條件：棧s已存在。操作結(jié)果：棧s被銷毀。StackEmpty(&s)初始條件：棧s已存在。操作結(jié)果：若是為空棧，則返回TRUE,否則返回FALSE。Traverse(&s,void(*visit)()初始條件：棧s已存在。操作結(jié)果：依次遍歷棧s中的元素，依次調(diào)用函數(shù)，一旦失敗，則操作失敗。ADT stack2.

6、隊(duì)列抽象數(shù)據(jù)類型定義ADT Queue數(shù)據(jù)對(duì)象：D=ai|aiElemset,i=1,2,3,n,n=0數(shù)據(jù)關(guān)系：R1=|ai-1,aiD,i=2, n基本操作：InitQueue(&q)操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。EnQueue(&q, e)初始條件：隊(duì)列Q已存在。操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。QueueLenth(&q)初始條件：隊(duì)列已存在。操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度。DeQueue(&q, &e)初始條件：隊(duì)列已存在。操作結(jié)果：刪除Q的隊(duì)尾元素，并用e返回其值。QueueEmpty(&q)初始條件：隊(duì)列Q已存在。操作結(jié)果：若Q為空隊(duì)列，則返回TRUE，否則返回FA

7、LSE.ClearQueue(&q)初始條件：隊(duì)列Q已存在。操作結(jié)果：清空隊(duì)列Q。DestoryQueue(&q)初始條件：隊(duì)列Q已存在。操作結(jié)果：隊(duì)列Q被銷毀。不再存在。QueueTraverse(&q,Status(*visit)()初始條件：隊(duì)列Q已存在。操作結(jié)果：依次遍歷隊(duì)列Q的元素，依次調(diào)用函數(shù)，一旦失敗，則操作失敗。ADT Queue流程圖如下:本程序主要包括以下幾個(gè)模塊：主程序模塊： int main()GhostLanage();printf(nt按任意鍵退出nn);各子程序模塊： /*初始化棧*/void InitStack(SeqStack *s)s-top=-1;/*進(jìn)棧

8、操作*/void Push(SeqStack *s,StackElementType x)if(s-top=Stack_Size-1) printf(nt棧已滿！ );else s-top+;s-elems-top=x;/*出棧操作*/void Pop(SeqStack *s,StackElementType *x)if(s-top=-1)printf(nt棧為空！ );else *x=s-elems-top;s-top-;/*取棧頂元素*/void GetTop(SeqStack *s,StackElementType *x)if(s-top=-1)printf(nt棧為空！ );else

9、*x=s-elems-top;/*判斷棧是否為空*/int IsEmpty(SeqStack *s)if(s-top=-1) return(0);else return(1);/*魔王語言翻譯函數(shù)*/void GhostLanage()SeqStack B,A,s,B1,A1,r,M;StackElementType ch,ch1,ch2,x;char aa100;int choice,i=0,n;InitStack(&B);InitStack(&A);InitStack(&s);InitStack(&r);InitStack(&M);printf(魔王語言的轉(zhuǎn)換形式： B-tAdA A-sa

10、e);Push(&B,t);Push(&B,A);Push(&B,d);Push(&B,A);Push(&A,s);Push(&A,a);Push(&A,e);printf(n請(qǐng)輸入要翻譯的魔王語言:n);scanf(%s,aa);for(i=0;aai!=0;i+)Push(&s,aai);while(IsEmpty(&s)Pop(&s,&ch); if(ch=B) B1=B; while(IsEmpty(&B1) Pop(&B1,&ch1); if(ch1=A) A1=A; while(IsEmpty(&A1) Pop(&A1,&ch2); Push(&r,ch2); else Push(

11、&r,ch1); else if(ch=A) A1=A; while(IsEmpty(&A1) Pop(&A1,&ch2); Push(&r,ch2); else if(ch=) Pop(&s,&ch2); while(ch2!=() Push(&M,ch2); Pop(&s,&ch2); GetTop(&M,&ch2); x=ch2; Pop(&M,&ch2); while(IsEmpty(&M) Push(&r,x); Pop(&M,&ch2); Push(&r,ch2); Push(&r,x); else Push(&r,ch);M=r;printf(nnt翻譯的結(jié)果為： );while

12、(IsEmpty(&M) Pop(&M,&ch); printf(%c,ch); printf(nnt是否繼續(xù)翻譯為漢語：（ 1-繼續(xù)，0-不繼續(xù)）);scanf(%d,&n);if(n=1) printf(nnt翻譯為漢語的結(jié)果為： nnt); M=r; while(IsEmpty(&M) Pop(&M,&ch); if(ch=t) printf(天); else if(ch=d) printf(地); else if(ch=s) printf(上); else if(ch=a) printf(一只); else if(ch=e) printf(鵝); else if(ch=z) print

13、f(追); else if(ch=g) printf(趕); else if(ch=x) printf(下); else if(ch=n) printf(蛋); else if(ch=h) printf(恨); printf(n);else ;模塊間的關(guān)系是：棧模塊 翻譯函數(shù)2翻譯函數(shù)1主程序四、詳細(xì)設(shè)計(jì)本程序中的主要函數(shù)有：void InitStack(SeqStack *s);/*初始化棧*/void Push(SeqStack *s,StackElementType x); /*進(jìn)棧操作*/void Pop(SeqStack *s,StackElementType *x);/*出棧操作*

14、/void GetTop(SeqStack *s,StackElementType *x);/*取棧頂元素*/int IsEmpty(SeqStack *s);/*判斷棧是否為空*/void GhostLanage();/*魔王語言翻譯函數(shù)*/函數(shù)間的調(diào)用關(guān)系：主程序調(diào)用魔王語言翻譯函數(shù)，然后魔王語言翻譯函數(shù)調(diào)用其它的函數(shù)（初始化棧，進(jìn)棧，出棧，取棧頂元素，判斷?？眨源藖韺?shí)現(xiàn)整個(gè)程序的運(yùn)行。/1. 程序的頭文件及全局變量的定義#include #include #define StackElementType char#define Stack_Size 100/2.棧類型及其基本操作 t

15、ypedef structStackElementType elemStack_Size;int top;SeqStack;void InitStack(SeqStack *s);/*初始化棧*/void Push(SeqStack *s,StackElementType x); /*進(jìn)棧操作*/void Pop(SeqStack *s,StackElementType *x);/*出棧操作*/void GetTop(SeqStack *s,StackElementType *x);/*取棧頂元素*/int IsEmpty(SeqStack *s);/*判斷棧是否為空*/void GhostL

16、anage();/*魔王語言翻譯函數(shù)*/3.主函數(shù)int main()system(color 1b);GhostLanage();printf(nt按任意鍵退出nn);/*初始化棧*/void InitStack(SeqStack *s)s-top=-1;/*進(jìn)棧操作*/void Push(SeqStack *s,StackElementType x)if(s-top=Stack_Size-1) printf(nt棧已滿！);else s-top+;s-elems-top=x;/*出棧操作*/void Pop(SeqStack *s,StackElementType *x)if(s-top=

17、-1)printf(nt棧為空！);else *x=s-elems-top;s-top-;/*取棧頂元素*/void GetTop(SeqStack *s,StackElementType *x)if(s-top=-1)printf(nt棧為空！);else *x=s-elems-top;/*判斷棧是否為空*/int IsEmpty(SeqStack *s)if(s-top=-1) return(0);else return(1);/4.魔王語言翻譯函數(shù)void GhostLanage()SeqStack B,A,s,B1,A1,r,M;StackElementType ch,ch1,ch2,

18、x;char aa100;int choice,i=0,n;InitStack(&B);InitStack(&A);InitStack(&s);InitStack(&r);InitStack(&M);printf(tt*魔王語言翻譯程序*n);printf(tt*ttt*tn);printf(tt*ttt*tn);printf(tt*ttt*tn);Push(&B,t);Push(&B,A);Push(&B,d);Push(&B,A);Push(&A,s);Push(&A,a);Push(&A,e);printf(nttt請(qǐng)輸入要翻譯的魔王語言:);scanf(%s,aa);for(i=0;a

19、ai!=0;i+)Push(&s,aai);while(IsEmpty(&s)Pop(&s,&ch); if(ch=B) B1=B; while(IsEmpty(&B1) Pop(&B1,&ch1); if(ch1=A) A1=A; while(IsEmpty(&A1) Pop(&A1,&ch2); Push(&r,ch2); else Push(&r,ch1); else if(ch=A) A1=A; while(IsEmpty(&A1) Pop(&A1,&ch2); Push(&r,ch2); else if(ch=) Pop(&s,&ch2); while(ch2!=() Push(&M

20、,ch2); Pop(&s,&ch2); GetTop(&M,&ch2); x=ch2; Pop(&M,&ch2); while(IsEmpty(&M) Push(&r,x); Pop(&M,&ch2); Push(&r,ch2); Push(&r,x); else Push(&r,ch);M=r;printf(nnt翻譯的結(jié)果為：);while(IsEmpty(&M) Pop(&M,&ch); printf(%c,ch); printf(nnt是否繼續(xù)翻譯為漢語：（1-繼續(xù)，0-不繼續(xù)）);scanf(%d,&n);if(n=1) printf(nnt翻譯為漢語的結(jié)果為：nnt); M=r;

21、 while(IsEmpty(&M) Pop(&M,&ch); if(ch=t) printf(天); else if(ch=d) printf(地); else if(ch=s) printf(上); else if(ch=a) printf(一只); else if(ch=e) printf(鵝); else if(ch=z) printf(追); else if(ch=g) printf(趕); else if(ch=x) printf(下); else if(ch=n) printf(蛋); else if(ch=h) printf(恨); printf(n);else ;五、調(diào)試分析

22、1.若是括號(hào)外的從左到右入棧，并進(jìn)行翻譯，則出來的運(yùn)行結(jié)果是反著的，并未達(dá)到要求的結(jié)果。所以進(jìn)行調(diào)試，發(fā)現(xiàn)應(yīng)該從右到左入棧，根據(jù)出棧的順序，先進(jìn)后出，正好可以達(dá)到相應(yīng)的結(jié)果。2. 括號(hào)內(nèi)的字符的入棧錯(cuò)誤。本來只是將括號(hào)內(nèi)的字符也是據(jù)1從右到左入棧。并且循環(huán)插入括號(hào)內(nèi)的第一個(gè)字符。發(fā)現(xiàn)結(jié)果又是反的。據(jù)調(diào)試，發(fā)現(xiàn)括號(hào)內(nèi)的字符應(yīng)該是從左到右入棧，正好符合規(guī)則1，結(jié)果未相反。3. 將括號(hào)內(nèi)的第一個(gè)字符按照循環(huán)，進(jìn)一個(gè)字符，再插一個(gè)括號(hào)內(nèi)的第一個(gè)字符。發(fā)現(xiàn)結(jié)果與規(guī)則1不符，所以據(jù)調(diào)試，應(yīng)在循環(huán)外先插入一個(gè)括號(hào)內(nèi)的第一個(gè)字符，后再進(jìn)行以上的循環(huán)，這樣輸出的結(jié)果與規(guī)則1相符，并且第一個(gè)輸出的不會(huì)少了括號(hào)內(nèi)的

23、第一個(gè)字符，也不會(huì)重復(fù)第一個(gè)字符的輸出。4. 指針和地址符的誤用。在調(diào)用函數(shù)時(shí)，總是誤用這兩個(gè)符號(hào)，導(dǎo)致許多不必要的錯(cuò)誤。所以，經(jīng)過調(diào)試，也熟悉了這兩個(gè)符號(hào)的用法。六、用戶手冊(cè)第一步：?jiǎn)?dòng)魔王語言.exe應(yīng)用程序，進(jìn)入程序界面，如下：第二步：輸入要翻譯的魔王語言后按Enter鍵確認(rèn)，結(jié)果如下：第三步：程序?qū)⑤斎敕g為魔王語言后會(huì)再次詢問要不要翻譯為漢語，如果要翻譯為漢語，選擇1，按Enter確認(rèn)，則程序會(huì)再次將魔王語言翻譯為漢語形式。具體如下：第四步：翻譯結(jié)束后按任意鍵退出程序。七、測(cè)試結(jié)果輸入的魔王語言為：B(ehnxgz)B翻譯的結(jié)果為： tsaedsaeezegexenehetsaeds

24、ae翻譯為漢語的結(jié)果為： 天上一只鵝地上一只鵝鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一只鵝地上一只鵝結(jié)論：此程序能夠按照給定的翻譯規(guī)則解釋魔王語言。八、結(jié)束語 通過這個(gè)實(shí)驗(yàn)。特別是實(shí)驗(yàn)中對(duì)棧的應(yīng)用，讓我更深入的了解了棧的特性，更加了解了棧的構(gòu)造及構(gòu)造方法。這次實(shí)驗(yàn)實(shí)現(xiàn)了簡(jiǎn)單的魔王語言解釋，按照給定的規(guī)則能夠翻譯出一句有意義的話，但不足的是，程序中的規(guī)則是指導(dǎo)書中給定的規(guī)則，沒有定義出自己的規(guī)則，在今后的時(shí)間里，還需要自己進(jìn)行不斷的改善，爭(zhēng)取能夠自己定義規(guī)則。這次實(shí)驗(yàn)對(duì)魔王語言的解釋，讓我看到了如何對(duì)信息進(jìn)行簡(jiǎn)單的加密，看到了加密的雛形，這對(duì)于今后更深入的學(xué)習(xí)起到了啟蒙的作用。總的來說，這次實(shí)驗(yàn)讓我收獲了很

25、多，同時(shí)也讓我發(fā)現(xiàn)了很多的不足，希望在今后的學(xué)習(xí)中，不斷努力，使程序更加的完美。九、附錄程序源代碼如下：#include #include #define StackElementType char#define Stack_Size 100typedef structStackElementType elemStack_Size;int top;SeqStack;void InitStack(SeqStack *s);/*初始化棧*/void Push(SeqStack *s,StackElementType x); /*進(jìn)棧操作*/void Pop(SeqStack *s,StackEle

26、mentType *x);/*出棧操作*/void GetTop(SeqStack *s,StackElementType *x);/*取棧頂元素*/int IsEmpty(SeqStack *s);/*判斷棧是否為空*/void GhostLanage();/*魔王語言翻譯函數(shù)*/*主函數(shù)*/int main()system(color 1b);GhostLanage();printf(nt按任意鍵退出nn);/*初始化棧*/void InitStack(SeqStack *s)s-top=-1;/*進(jìn)棧操作*/void Push(SeqStack *s,StackElementType x

27、)if(s-top=Stack_Size-1) printf(nt棧已滿！);else s-top+;s-elems-top=x;/*出棧操作*/void Pop(SeqStack *s,StackElementType *x)if(s-top=-1)printf(nt棧為空！);else *x=s-elems-top;s-top-;/*取棧頂元素*/void GetTop(SeqStack *s,StackElementType *x)if(s-top=-1)printf(nt棧為空！);else *x=s-elems-top;/*判斷棧是否為空*/int IsEmpty(SeqStack

28、*s)if(s-top=-1) return(0);else return(1);/*魔王語言翻譯函數(shù)*/void GhostLanage()SeqStack B,A,s,B1,A1,r,M;StackElementType ch,ch1,ch2,x;char aa100;int choice,i=0,n;InitStack(&B);InitStack(&A);InitStack(&s);InitStack(&r);InitStack(&M);printf(tt*魔王語言解釋程序*n);printf(tt*tt *tn);printf(tt*tt *tn);printf(tt*tt *tn);Push(&B,t);Push(&B,A);Push(&B,d);Push(&B,A);Push(&A,s);Push(&A,a);Push(&A,e)