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

魔王語(yǔ)言解釋程序一、問(wèn)題引入問(wèn)題描述有一個(gè)魔王總是使用自已的一種格外精練而抽象的語(yǔ)言講話(huà)，沒(méi)有人能聽(tīng)得懂。但他的語(yǔ)言是可以逐步解釋成人能懂的語(yǔ)言的逐步抽象上去的：〔1〕α→β1β2…βm〔2〕(θβ1β2…βm)→(θβm…β2θβ1θ)在這兩種形式中，從左到右均表示解釋。寫(xiě)一個(gè)魔王解釋程序，將魔王的話(huà)解釋成人能聽(tīng)懂的話(huà)。根本要求用下述兩種規(guī)章和下述規(guī)章〔2〕實(shí)現(xiàn)。設(shè)大寫(xiě)字母表示魔王語(yǔ)言的詞匯，小寫(xiě)字母表B→tAdAA→sae測(cè)試數(shù)據(jù)B(einxgz)B解釋成tsaedsaeezegexeneietsaedsaet天d地t天d地s上a一只e鵝z追g趕x下n蛋h恨實(shí)現(xiàn)提示將魔王的語(yǔ)言自右至左進(jìn)棧，總是處理?xiàng)ｍ斪址?。假設(shè)是開(kāi)括號(hào)，則逐一出棧，將字母挨次入隊(duì)列，直至閉括號(hào)出棧，并按規(guī)章要求逐一出隊(duì)列在處理后入棧。本程序承受的是挨次棧。根本操作列表：(1)據(jù)括號(hào)的個(gè)數(shù)設(shè)一個(gè)標(biāo)記。登記括號(hào)的位置。(2)依據(jù)標(biāo)記來(lái)執(zhí)行依次的操作。2輸出人的語(yǔ)言。有括號(hào)，分為括號(hào)內(nèi)的和括號(hào)外的的從左到右入棧，并且依次插入括號(hào)內(nèi)的第一個(gè)字符。據(jù)翻譯函數(shù)2出棧并且翻譯。二、需求分析a’-‘z’寫(xiě)字母A和B。且允許消滅重復(fù)字符或非法字符，程序運(yùn)用時(shí)自動(dòng)過(guò)濾去，輸出的運(yùn)算結(jié)果中將不含重復(fù)字符和非法字符。魔王語(yǔ)言遵守如下規(guī)章：〔θδ1δ2δ3…δn〕θδnθδn-1…θδ1θBtAdAAsae演示程序以用戶(hù)和計(jì)算機(jī)對(duì)話(huà)的形式進(jìn)展，即在計(jì)算機(jī)終端中顯示提示信息之后，有用戶(hù)自行選擇下一步命令，相應(yīng)輸入數(shù)據(jù)和運(yùn)算結(jié)果在其后顯示。程序的執(zhí)行命令有：1〕選擇操作 2〕任意鍵完畢數(shù)據(jù)測(cè)試B(ehnxgz)Btsaedsaeezegexenehetsaedsaet天d地st天d地s上a一只e鵝z追g趕x下n蛋h恨三、概要設(shè)計(jì)為實(shí)現(xiàn)上述功能，需要棧和隊(duì)列兩個(gè)抽象數(shù)據(jù)類(lèi)型。棧抽象數(shù)據(jù)類(lèi)型定義ADTstack{數(shù)據(jù)對(duì)象：D={ai|ai∈Elemset,i=1,2,3,…n,n>=0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…n}根本操作：InitStack(&s)操作結(jié)果：構(gòu)造一個(gè)空棧s。Push(&s,e)初始條件：棧s操作結(jié)果：插入元素e為的棧頂元素。Pop(&s,&e)初始條件：棧s已存在且非空。操作結(jié)果：刪除棧s的棧頂元素，并用eStackLenth(&s)初始條件：棧s操作結(jié)果：返回s的元素個(gè)數(shù)，即棧的長(zhǎng)度。ClearStack(&s)初始條件：棧s已存在。操作結(jié)果：將sDestoryStack(&s)初始條件：棧s操作結(jié)果：棧sStackEmpty(&s)初始條件：棧s操作結(jié)果：假設(shè)是為空棧，則返回TRUE,否則返回FALSE。Traverse(&s,void(*visit))初始條件：棧s操作結(jié)果：依次遍歷棧s中的元素，依次調(diào)用函數(shù)，一旦失敗，則操作失敗。}ADTstack隊(duì)列抽象數(shù)據(jù)類(lèi)型定義ADTQueue{數(shù)據(jù)對(duì)象：D={ai|ai∈Elemset,i=1,2,3,…n,n>=0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…n}根本操作：InitQueue(&q)操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。EnQueue(&q,e)初始條件：隊(duì)列Q已存在。操作結(jié)果：插入元素e為QQueueLenth(&q)初始條件：隊(duì)列已存在。操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度。DeQueue(&q,&e)初始條件：隊(duì)列已存在。操作結(jié)果：刪除Q的隊(duì)尾元素，并用eQueueEmpty(&q)初始條件：隊(duì)列Q已存在。操作結(jié)果：假設(shè)Q為空隊(duì)列，則返回TRUE，否則返回FALSE.ClearQueue(&q)初始條件：隊(duì)列Q操作結(jié)果：清空隊(duì)列Q。DestoryQueue(&q)初始條件：隊(duì)列Q已存在。操作結(jié)果：隊(duì)列Q被銷(xiāo)毀。不再存在。QueueTraverse(&q,Status(*visit))初始條件：隊(duì)列Q操作結(jié)果：依次遍歷隊(duì)列Q的元素，依次調(diào)用函數(shù)，一旦失敗，則操作失敗。}ADTQueue流程圖如下:本程序主要包括以下幾個(gè)模塊：主程序模塊：intmain{GhostLanage;printf(“\n\t\n\n“);}各子程序模塊：/*初始化棧*/voidInitStack(SeqStack*s){s->top=-1;}/*進(jìn)棧操作*/voidPush(SeqStack*s,StackElementTypex){if(s->top==Stack_Size-1)printf(“\n\telse{s->top++;s->elem[s->top]=x;}}/*出棧操作*/voidPop(SeqStack*s,StackElementType*x){if(s->top==-1)printf(“\n\telse{*x=s->elem[s->top];s->top--;}}/*取棧頂元素*/voidGetTop(SeqStack*s,StackElementType*x){if(s->top==-1)printf(“\n\telse*x=s->elem[s->top];}/*推斷棧是否為空*/intIsEmpty(SeqStack*s){if(s->top==-1)return(0);elsereturn(1);}/*魔王語(yǔ)言翻譯函數(shù)*/voidGhostLanage{SeqStackB,A,s,B1,A1,r,M;StackElementTypech,ch1,ch2,x;charaa[100];intchoice,i=0,n;InitStack(&B);InitStack(&A);InitStack(&s);InitStack(&r);InitStack(&M);printf(“魔王語(yǔ)言的轉(zhuǎn)換形式：B->tAdA A->sae“);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;aa[i]!=”\0”;i++)Push(&s,aa[i]);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);}}elsePush(&r,ch1);}}elseif(ch==”A”){A1=A;while(IsEmpty(&A1)){Pop(&A1,&ch2);Push(&r,ch2);}}elseif(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);}elsePush(&r,ch);}M=r;printf(“\n\n\twhile(IsEmpty(&M)){Pop(&M,&ch);printf(“%c“,ch);}printf(“\n\n\t是否連續(xù)翻譯為漢語(yǔ)〔10scanf(“%d“,&n);if(n==1){printf(“\n\n\t\n\n\t“);M=r;while(IsEmpty(&M)){Pop(&M,&ch);if(ch==”t”)printf(“天“);elseif(ch==”d”)printf(“地“);elseif(ch==”s”)printf(“上“);elseif(ch==”a”)printf(“一只“);elseif(ch==”e”)printf(“鵝“);elseif(ch==”z”)printf(“追“);elseif(ch==”g”)printf(“趕“);elseif(ch==”x”)printf(“下“);elseif(ch==”n”)printf(“蛋“);elseif(ch==”h”)printf(“恨“);}printf(“\n“);}else;}模塊間的關(guān)系是：主程序主程序棧模塊翻譯函數(shù)12四、具體設(shè)計(jì)本程序中的主要函數(shù)有：voidInitStack(SeqStack*s);/*初始化棧*/voidPush(SeqStack*s,StackElementTypex);/*進(jìn)棧操作*/voidPop(SeqStack*s,StackElementType*x);/*出棧操作*/voidGetTop(SeqStack*s,StackElementType*x);/*取棧頂元素*/intIsEmpty(SeqStack*s);/*推斷棧是否為空*/voidGhostLanage;/*魔王語(yǔ)言翻譯函數(shù)*/〔初始化棧，進(jìn)棧，出棧，取棧頂元素，推斷?？?，以此來(lái)實(shí)現(xiàn)整個(gè)程序的運(yùn)行。//1.程序的頭文件及全局變量的定義#include<stdio.h>#include<stdlib.h>#defineStackElementTypechar#defineStack_Size100//2.棧類(lèi)型及其根本操作typedefstruct{StackElementTypeelem[Stack_Size];inttop;}SeqStack;voidInitStack(SeqStack*s);/*初始化棧*/voidPush(SeqStack*s,StackElementTypex);/*進(jìn)棧操作*/voidPop(SeqStack*s,StackElementType*x);/*出棧操作*/voidGetTop(SeqStack*s,StackElementType*x);/*取棧頂元素*/intIsEmpty(SeqStack*s);/*推斷棧是否為空*/voidGhostLanage;/*魔王語(yǔ)言翻譯函數(shù)*///3.主函數(shù)intmain{system(“color1b“);GhostLanage;printf(“\n\t\n\n“);}/*初始化棧*/voidInitStack(SeqStack*s){s->top=-1;}/*進(jìn)棧操作*/voidPush(SeqStack*s,StackElementTypex){if(s->top==Stack_Size-1)printf(“\n\telse{s->top++;s->elem[s->top]=x;}}/*出棧操作*/voidPop(SeqStack*s,StackElementType*x){if(s->top==-1)printf(“\n\telse{*x=s->elem[s->top];s->top--;}}/*取棧頂元素*/voidGetTop(SeqStack*s,StackElementType*x){if(s->top==-1)printf(“\n\telse*x=s->elem[s->top];}/*推斷棧是否為空*/intIsEmpty(SeqStack*s){if(s->top==-1)return(0);elsereturn(1);}//4.魔王語(yǔ)言翻譯函數(shù)voidGhostLanage{SeqStackB,A,s,B1,A1,r,M;StackElementTypech,ch1,ch2,x;charaa[100];intchoice,i=0,n;InitStack(&B);InitStack(&A);InitStack(&s);InitStack(&r);InitStack(&M);printf(“\t\t*************魔王語(yǔ)言翻譯程序***************\n“);printf(“\t\t*********\t\t\t************\t\n“);printf(“\t\t*********\t\t\t************\t\n“);printf(“\t\t*********\t\t\t************\t\n“);Push(&B,”t”);Push(&B,”A”);Push(&B,”d”);Push(&B,”A”);Push(&A,”s”);Push(&A,”a”);Push(&A,”e”);printf(“\n\t\t\tscanf(“%s“,aa);for(i=0;aa[i]!=”\0”;i++)Push(&s,aa[i]);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);}}elsePush(&r,ch1);}}elseif(ch==”A”){A1=A;while(IsEmpty(&A1)){Pop(&A1,&ch2);Push(&r,ch2);}}elseif(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);}M=r;

}elsePush(&r,ch);printf(“\n\n\twhile(IsEmpty(&M)){Pop(&M,&ch);printf(“%c“,ch);}printf(“\n\n\t是否連續(xù)翻譯為漢語(yǔ)〔10scanf(“%d“,&n);if(n==1){printf(“\n\n\t\n\n\t“);M=r;while(IsEmpty(&M)){Pop(&M,&ch);if(ch==”t”)printf(“天“);elseif(ch==”d”)printf(“地“);elseif(ch==”s”)printf(“上“);elseif(ch==”a”)printf(“一只“);elseif(ch==”e”)printf(“鵝“);elseif(ch==”z”)printf(“追“);elseif(ch==”g”)printf(“趕“);elseif(ch==”x”)printf(“下“);elseif(ch==”n”)printf(“蛋“);elseif(ch==”h”)printf(“恨“);}printf(“\n“);}else;}五、調(diào)試分析結(jié)果。所以進(jìn)展調(diào)試，覺(jué)察應(yīng)當(dāng)從右到左入棧，依據(jù)出棧的挨次，先進(jìn)后出，正好可以到達(dá)相應(yīng)的結(jié)果。11，結(jié)果未相反。與規(guī)章11不會(huì)重復(fù)第一個(gè)字符的輸出。以，經(jīng)過(guò)調(diào)試，也生疏了這兩個(gè)符號(hào)的用法。六、用戶(hù)手冊(cè)第一步：?jiǎn)?dòng)魔王語(yǔ)言.exe應(yīng)用程序，進(jìn)入程序界面，如下：其次步：輸入要翻譯的魔王語(yǔ)言后按Enter鍵確認(rèn)，結(jié)果如下：第三步：程序?qū)⑤斎敕g為魔王語(yǔ)言后會(huì)再次詢(xún)問(wèn)要不要翻譯為漢語(yǔ)，假設(shè)要翻譯為漢語(yǔ)，1，按Enter第四步：翻譯完畢后按任意鍵退出程序。七、測(cè)試結(jié)果輸入的魔王語(yǔ)言為：B(ehnxgz)B翻譯的結(jié)果為：tsaedsaeezegexenehetsaedsae翻譯為漢語(yǔ)的結(jié)果為：天上一只鵝地上一只鵝鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一只鵝地上一只鵝結(jié)論：此程序能夠依據(jù)給定的翻譯規(guī)章解釋魔王語(yǔ)言。八、完畢語(yǔ)通過(guò)這個(gè)試驗(yàn)。特別是試驗(yàn)中對(duì)棧的應(yīng)用，讓我更深入的了解了棧的特性，更加了解了缺乏，期望在今后的學(xué)習(xí)中，不斷努力，使程序更加的完善。九、附錄程序源代碼如下：#include<stdio.h>#include<stdlib.h>#defineStackElementTypechar#defineStack_Size100typedefstruct{StackElementTypeelem[Stack_Size];inttop;}SeqStack;voidInitStack(SeqStack*s);/*初始化棧*/voidPush(SeqStack*s,StackElementTypex);/*進(jìn)棧操作*/voidPop(SeqStack*s,StackElementType*x);/*出棧操作*/voidGetTop(SeqStack*s,StackElementType*x);/*取棧頂元素*/intIsEmpty(SeqStack*s);/*推斷棧是否為空*/voidGhostLanage;/*魔王語(yǔ)言翻譯函數(shù)*//*主函數(shù)*/intmain{system(“color1b“);GhostLanage;printf(“\n\t\n\n“);}/*初始化棧*/voidInitStack(SeqStack*s){s->top=-1;}/*進(jìn)棧操作*/voidPush(SeqStack*s,StackElementTypex){if(s->top==Stack_Size-1)printf(“\n\telse{s->top++;s->elem[s->top]=x;}}/*出棧操作*/voidPop(SeqStack*s,StackElementType*x){if(s->top==-1)printf(“\n\telse{*x=s->elem[s->top];s->top--;}}/*取棧頂元素*/voidGetTop(SeqStack*s,StackElementType*x){if(s->top==-1)printf(“\n\telse*x=s->elem[s->top];}/*推斷棧是否為空*/intIsEmpty(SeqStack*s){if(s->top==-1)return(0);elsereturn(1);}/*魔王語(yǔ)言翻譯函數(shù)*/voidGhostLanage{SeqStackB,A,s,B1,A1,r,M;StackElementTypech,ch1,ch2,x;charaa[100];intchoice,i=0,n;InitStack(&B);InitStack(&A);InitStack(&s);InitStack(&r);InitStack(&M);printf(“\t\t*************魔王語(yǔ)言解釋程序***************\n“);printf(“\t\t*********\t\t************\t\n“);printf(“\t\t*********\t\t********\t\n“);printf(“\t\t*********\t\t**************\t\n“);Push(&B,”t”);Push(&B,”A”);Push(&B,”d”);Push(&B,”A”);Push(&A,”s”);Push(&A,”a”);Push(&A,”e”);printf(“\n\t\tscanf(“%s“,aa);for(i=0;aa[i]!=”\0”;i++)Push(&s,aa[i]);whil