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

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

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

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

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

5、s, &e)初始條件：棧s已存在且非空。操作結(jié)果：刪除棧s的棧頂元素，并用e返回其值。StackLenth(&s)初始條件：棧s已存在。操作結(jié)果：返回s的元素個數(shù)，即棧的長度。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、隊列抽象數(shù)據(jù)類型定義ADT Queue數(shù)據(jù)對象：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)造一個空隊列Q。EnQueue(&q, e)初始條件：隊列Q已存在。操作結(jié)果：插入元素e為Q的新的隊尾元素。QueueLenth(&q)初始條件：隊列已存在。操作結(jié)果：返回Q的元素個數(shù)，即隊列的長度。DeQueue(&q, &e)初始條件：隊列已存在。操作結(jié)果：刪除Q的隊尾元素，并用e返回其值。QueueEmpty(&q)初始條件：隊列Q已存在。操作結(jié)果：若Q為空隊列，則返回TRUE，否則返回FA

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

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請輸入要翻譯的魔王語言: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主程序四、詳細設(shè)計本程序中的主要函數(shù)有：void InitStack(SeqStack *s);/*初始化棧*/void Push(SeqStack *s,StackElementType x); /*進棧操作*/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ù)（初始化棧，進棧，出棧，取棧頂元素，判斷?？眨源藖韺崿F(xià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); /*進棧操作*/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;/*進棧操作*/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請輸入要翻譯的魔王語言:);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.若是括號外的從左到右入棧，并進行翻譯，則出來的運行結(jié)果是反著的，并未達到要求的結(jié)果。所以進行調(diào)試，發(fā)現(xiàn)應(yīng)該從右到左入棧，根據(jù)出棧的順序，先進后出，正好可以達到相應(yīng)的結(jié)果。2. 括號內(nèi)的字符的入棧錯誤。本來只是將括號內(nèi)的字符也是據(jù)1從右到左入棧。并且循環(huán)插入括號內(nèi)的第一個字符。發(fā)現(xiàn)結(jié)果又是反的。據(jù)調(diào)試，發(fā)現(xiàn)括號內(nèi)的字符應(yīng)該是從左到右入棧，正好符合規(guī)則1，結(jié)果未相反。3. 將括號內(nèi)的第一個字符按照循環(huán)，進一個字符，再插一個括號內(nèi)的第一個字符。發(fā)現(xiàn)結(jié)果與規(guī)則1不符，所以據(jù)調(diào)試，應(yīng)在循環(huán)外先插入一個括號內(nèi)的第一個字符，后再進行以上的循環(huán)，這樣輸出的結(jié)果與規(guī)則1相符，并且第一個輸出的不會少了括號內(nèi)的

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

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

25、多，同時也讓我發(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); /*進棧操作*/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;/*進棧操作*/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)