魔王語言數(shù)據(jù)結構實驗報告課案

1、數(shù)據(jù)結構實驗報告2.2 魔王語言解釋 問題描述有一個魔王總是使用自己的一種非常精練而又抽象的語言講話，沒有人能聽得懂，但他的語言是可以逐步解釋成人能聽懂的語言，因為他的語言是由以下兩種形式的規(guī)則由人的語言逐步抽象上去的：（1） 1 2, m（2）（ 1 2, n） nn 1, 1在這兩種形式中，從左到右均表示解釋。試寫一個魔王語言的解釋系統(tǒng)，把他的話解釋成人能聽得懂的話。 基本要求用下述兩條具體規(guī)則和上述規(guī)則形式（2）實現(xiàn)。設大寫字母表示魔王語言的詞匯；小寫字母表示人的語言詞匯；希臘字母表示可以用大寫字母或小寫字母代換的變量。魔王語言可含人的詞匯。（ 1） B tAdA （ 2） A sae

2、測試數(shù)據(jù)B（ehnxgz）B 解釋成 tsaedsaeezegexenehetsaedsae若將小寫字母與漢字建立下表所示的對應關系，則魔王說的話是： “天上一只鵝地上一只鵝鵝追鵝趕鵝下鵝蛋鵝恨鵝天 上一只鵝地上一只鵝”。 t d s a e z g x nh 天 地 上 一只 鵝 追 趕 下 蛋 恨一：需求分析以一維數(shù)組demon i 表示魔王語言魔王語言由用戶輸入, 初始保存在demon i 中 (3)魔王語言與人類語言對應關系固化在程序中(4) 實現(xiàn)過程：A：初始，魔王語言接收后存放在demon i 中B：初次遍歷數(shù)組，將數(shù)組中括號內的元素入棧，同時插入相應首字母；C：再次遍歷數(shù)組，將數(shù)

3、組元素依次入隊。(小寫字母直接入隊；大寫字母經(jīng)翻譯成相應字符后入隊；遇到括號，將棧中保存的元素依次出棧入隊)在翻譯過程中，如果依舊包含大寫字母，則置flag 為 1，否則為0。D：將隊列中元素賦值給demon i 。如果此時flag=1 ，則再次重復C過程。直至所有元素為人類語言。E：輸出demon i 。此時數(shù)組中元素為對應的人類語言。注： 如果程序中沒有相應的對應關系，則翻譯成 “ ?”。 二：概要設計：1：設定棧的抽象數(shù)據(jù)類型定義：ADT stack 數(shù)據(jù)對象：Dai|ai CharSet,i 1,2, , ,n,n=0 數(shù)據(jù)關系：R1 |ai-1,ai D,i 2, , ,n 基本操作

4、： TOC o 1-5 h z initstack ( s)操作結果: 構造一個空棧s. push ( s,e)初始條件: 棧 s 已存在.操作結果: 在棧 s 的棧頂插入新的棧頂元素e.pop( s, e)初始條件: 棧 s 已存在 .操作結果: 刪除 s 的棧頂元素, 并以 e 返回其值 . ADT stack設定隊列的抽象數(shù)據(jù)類型:ADT queue數(shù)據(jù)對象：Dai|ai Elemset,i 1,2, , ,n,n=0 數(shù)據(jù)關系：R1 |ai-1,ai D,i 2, , ,n 基本操作：initqueue(&q)操作結果: 構造一個空隊列q.enqueue(&q, e)初始條件: 隊列

5、q 已存在 .操作結果: 插入元素e 為 q 的新隊尾元素.dequeue(&q,&e) TOC o 1-5 h z 初始條件: q 為非空隊列.操作結果: 刪除 q 的隊頭元素, 并用 e 返回其值 . ADT queue本程序包含四個模塊:1)主函數(shù)模塊. 其中主函數(shù)為:status main() 初始化棧; 初始化隊列;接收魔王語言輸入到數(shù)組demoni ; 遍歷數(shù)組將括號中元素進棧;while( 數(shù)組 demoni 中元素有大寫字母) 翻譯排序處理后入隊列;將對列元素保存在數(shù)組demoni ;輸出人類語言( 數(shù)組 demon i); 括號內元素入棧處理模塊. tempstack(&te

6、mps)將括號內元素入棧, 依次插入首字符. 舉例： (abcd) adacaba.排序入隊列模塊. sort(&s,&q) TOC o 1-5 h z 遍歷數(shù)組; 遇到小寫字母, 直接入隊列;遇到大寫字母, 翻譯大寫后入隊列;遇到括號, 將棧中保存的元素依次出棧入隊列 ; 翻譯大寫處理模塊. spenqueue(&*q,key) switch(key) 找到各個大寫字母對應的字符串. 沒有相應的則解釋為? 各模塊之間調用關系: 主函數(shù)模塊括號內元素入棧處理模塊;排序入隊模塊翻譯大寫處理模塊; 三 : 詳細設計定義全局變量#define TRUE 1 #define FALSE 0 #defi

7、neOK 1 #define ERROR 0 #define NULL0 #define OVERFLOW -2 #define MAXSIZE100 #define stack_init_size 100 #define stackincrement 10typedef char selemtype; typedef char qelemtype;typedef char elemtype; typedef int status;char e;char demonMAXSIZE;棧類型及其基本操作typedef struct selemtype *base; selemtype *top;

8、intstacksize; sqstack;status initstack (sqstack *s) s-base=(selemtype*)malloc(stack_init_size*sizeof(selemtype);if(!s-base) exit (OVERFLOW); s-top=s-base;s-stacksize=stack_init_size; returnOK; /*創(chuàng)建棧 */status push (sqstack *s,selemtype e) if(s-top-s-base=s-stacksize) s-base=(elemtype *)realloc(s-base

9、,(s-stacksize+stackincrement)*sizeo f(elemtype); if(!s-base) exit(OVERFLOW);s-top=s-base+s-stacksize;s-stacksize+=stackincrement; *(s-top+)=e; return OK; /*入棧 */status pop(sqstack *s,selemtype *e) if(s-top=s-base) return ERROR;*/*e=*(-(s-top); return OK; /*/隊列類型及其基本操作typedef struct qnode qelemtype d

10、ata; struct qnode*next; qnode,*queueptr; typedef struct queueptr front; queueptr rear; linkqueue;status initqueue(linkqueue *q) q-front=q-rear=(queueptr)malloc(sizeof(qnode);OK; /* OK; /* 創(chuàng)建隊列*/q-front-next=NULL; returnstatus enqueue(linkqueue *q,qelemtype e) queueptr p;p=(queueptr)malloc(sizeof(qno

11、de); if(!p) exit(OVERFLOW); p-data=e; p-next=NULL; q-rear-next=p; q-rear=p; return OK; /* 入隊 */status dequeue(linkqueue *q,qelemtype *e) queueptr p;if(q-front=q-rear) return ERROR;p=q-front-next; *e=p-data;q-front-next=p-next; if(q-rear=p) q-rear=q-front; free(p);return OK; /*return OK; /*/四 : 調試分析函數(shù)調用比較多, 因而得仔細對待數(shù)值和地址的傳遞.由于魔王語言中B 中仍然包含著大寫字母(tAdA).所以考慮設置flag.函數(shù)數(shù)組遍歷. 進棧出棧. 入隊出隊中都要牽扯指針的移動, 所以要仔細考慮一循環(huán)的條件以及進棧元素的個數(shù) . 五 : 用戶手冊1. 本程序運行環(huán)境為DOS/WINDOW操作系統(tǒng)S, 執(zhí)行文件為 : 魔王語言解釋.exe