云南大學(xué)軟件學(xué)院大數(shù)據(jù)結(jié)構(gòu)實驗3

1、實驗難度：A B C 序號學(xué)號姓名成績指導(dǎo)教師（簽名）學(xué) 期：2017秋季學(xué)期任課教師：實驗題目：組員及組長:承擔(dān)工作：聯(lián)系電話：電子郵件:完成提交時間：年 月 日一、【實驗構(gòu)思(Conceive )】(10%)(本部分應(yīng)包括：描述實驗實現(xiàn)的基本思路，包括所用到的離散數(shù)學(xué)、工程數(shù)學(xué)、程 序設(shè)計等相關(guān)知識，對問題進(jìn)行概要性地分析)魔王語言的解釋規(guī)則：B tAdA ； sae ； (cluixgz) _* ezegexenehe貝lj盧王語百解釋成UnegzzugCK切燈hWMchaj大寫字母表示魔王語言的詞匯，小寫字母表示人的詞匯語言，魔王語言中可以包含括號，魔王語言的產(chǎn)生式規(guī)則在程序中給定，當(dāng)

2、接收用戶輸入的合法的魔王語言時， 通過調(diào)用魔王語言翻譯函數(shù)來實現(xiàn)翻譯。在A的基礎(chǔ)上，(根據(jù)產(chǎn)生式)自定義規(guī)則，將一段魔王的話翻譯為有意義的人 類語言(中文)：輸入wasjg,則魔王語言解釋為“我愛數(shù)據(jù)結(jié)構(gòu)”。運(yùn)用了離散數(shù)學(xué)的一些基本知識及程序設(shè)計知識。二、【實驗設(shè)計(Design)】(20%)(本部分應(yīng)包括：抽象數(shù)據(jù)類型的定義和基本操作說明，程序包含的模塊以及各模塊 間的調(diào)用關(guān)系，關(guān)鍵算法偽碼描述及程序流程圖等，如有界面則需包括界面設(shè)計，功 能說明等)/ 抽象數(shù)據(jù)類型的定義 /#define STACK_INIT_SIZE 50#define STACKINCREMENT 10#define

3、OVERLOW -2#define ERROR -1typedef struct char *base; /順序棧的棧底指針int top; / 順序棧的棧頂int size; /棧元素空間的大小SqStack; / 結(jié)構(gòu)體類型順序棧typedef struct char *base;int front;int rear;SqQueue; /結(jié)構(gòu)體類型隊列/ 各個模塊功能的描述/void Init_SqStack(SqStack & s) /初始化順序桟void Push_SqStack(SqStack &s, char c) /壓入數(shù)據(jù)int Pop_SqStack(SqStack &s,

4、char &e) /出桟char GetTop_SqStack(SqStack s)/或得棧頂int lsEmpty_SqStack(SqStack s)/判斷是否空棧void Init_SqQueue(SqQueue & q)初始化void En_SqQueue(SqQueue &q, char c)/進(jìn)隊歹int De_SqQueue(SqQueue &q, char & e) / 出隊列 void Translate(char c) / 打印字符void Reverse(char str,char strtmp)/將字符串反向int Execute(char ch, SqStack &s

5、, SqQueue & q)魔王語言操作調(diào)用關(guān)系：初始化棧初始化從列進(jìn)仃魔衛(wèi)語言的操作出隊列逬棧出棧操作將魔王語言翻詳再中文三、【實現(xiàn)(Implement)】(30%)(本部分應(yīng)包括：抽象數(shù)據(jù)類型各操作的 具體實現(xiàn)代碼、關(guān)鍵操作的具體算法實現(xiàn)、 函數(shù)實現(xiàn)，主程序?qū)崿F(xiàn)等，并給出關(guān)鍵算法的時間復(fù)雜度分析。如有界面則需包括界面的關(guān)鍵實現(xiàn)方法等。)主程序模塊：int main()char ch100;char ch1100;char ch2100;char e;/* printf(”請輸入魔王語言：);gets(ch);SqStack s;SqQueue q;lnit_SqStack(s);Init_

6、SqQueue(q);if(Execute(ch,s,q) = 1)英文解密while(De_SqQueue(q,e) = 1)Translate(e);不匹配 中文解密elseprintf(”輸入的括號不匹配！)； /左括號比右括號多,*printf(n);printf(請輸入魔王語言：);gets(chl);lnit_SqStack(s);Init_SqQueue(q);Reverse(ch1,ch2);for(int i=0;ch2i!=0;i+)Push_SqStack(s,ch2i);while(Pop_SqStack(s,e) = 1)switch(e)casew:printf(我

7、);break;casea:printf(愛)；break;cases:printf(數(shù)據(jù));break;casej:printf(結(jié));break;caseg:printf(構(gòu));break;return 0;其他函數(shù)實現(xiàn)代碼見七、【代碼】部分。時間復(fù)雜復(fù)分析：o(n)。四、【測試結(jié)果（Testing ）】（10%）（本部分應(yīng)包括：對實驗的測試結(jié)果，應(yīng)具體列出每次測試所輸入的數(shù)據(jù)以及輸出的數(shù)據(jù)，并對測試結(jié)果進(jìn)行分析，可附截圖）a D:IDEcodebl o 匚 kc+_codeMBS-2.exe請輸入魔王語言:B(ehbxgz)Btsaedsaeezegexebehetsaedsae 諳輸入

8、魔王語言：wasjg我愛數(shù)據(jù)結(jié)構(gòu)Process returned 0 (0x0) execution time : 15.150 s Press anv kev to continue. D:IDEcodeblockc + + codeHiiB.exe浦輸入魔王語言:B(ehbxgz)B；輸入的話號不匹配！譜輸入歳工語言:輸入的魔王語言為：B(eh nxgz)B翻譯的結(jié)果為： tsaedsaeezegexe nehetsaedsae錯誤模式：括號匹配錯誤提示。輸入的魔王語言為：wasjg翻譯為漢語的結(jié)果為：我愛數(shù)據(jù)結(jié)構(gòu)結(jié)論：此程序能夠按照給定的翻譯規(guī)則解釋魔王語言。五、【實驗總結(jié)】(10%)(

9、本部分應(yīng)包括：自己在實驗中完成的任務(wù)，及存在的問題，所完成實驗過程中的具體經(jīng)驗總結(jié)、心得)問題關(guān)鍵：1. 棧的初始化，入棧出棧操作，棧為空的判斷條件，隊列的初始化，入隊和出隊操作，隊列為空的判斷。以及隊列中最后一個元素被刪除后尾指針的修改。2. 主函數(shù)的操作。由于隊列和棧的操作始終為同一個，所以在主函數(shù)中，采用指針函數(shù)的調(diào)用，確保操作在同一個隊列和棧上。3. 一些細(xì)節(jié)處理，比如數(shù)組操作等。4. 另在查閱資料時候發(fā)現(xiàn)：將魔王語言作為一個字符串讀入進(jìn)來，首先檢查括號是否匹配，如果不匹配就無法解釋。如果匹配，然后將字符串從尾到頭依次壓入棧S中，將棧S中的內(nèi)容依次彈出壓入棧 S2中，直至遇到右括號，將

10、其壓入棧 S1中，并將棧S2彈出依次壓入棧S1中，直至遇到左括號壓入棧S1中，這樣棧S1中存放的內(nèi) 容就是匹配的第一個內(nèi)重括號，將棧S1棧頂元素左括號彈出，將左括號下面的那個元素保存在el變量中，然后將其他元素彈出依次壓入棧 S3中，在將el與棧S3中依 次彈出的元素壓入棧S2中，重復(fù)這個過程，直至將魔王語言中所有的括號都處理完 為止，所以這個思路可以處理多重括號嵌套的問題。六、思考題或【項目運(yùn)作描述（Operate ）】（10%）（注：選擇C難度的才需要填寫“項目運(yùn)作描述”，其他難度的只需完成思考題）（項目運(yùn)作描述應(yīng)包括：項目的成本效益分析，應(yīng)用效果等的分析。）1. 棧：特點就是一個先進(jìn)后出

11、的結(jié)構(gòu)。主要用途：函數(shù)調(diào)用和返回，數(shù)字轉(zhuǎn)字符，表達(dá)式求值，走迷宮等等。在CPU內(nèi)部棧主要是用來進(jìn)行子程序調(diào)用和返回，中斷時數(shù)據(jù)保存和返回。在編程語言中：主 要用來進(jìn)行函數(shù)的調(diào)用和返回。可以說在計算機(jī)中，只要數(shù)據(jù)的保存滿足先進(jìn)后出的 原理，都優(yōu)先考慮使用棧，所以棧是計算機(jī)中不可缺的機(jī)制。隊列：特點就是一個先進(jìn)先出的結(jié)構(gòu)。只要滿足數(shù)據(jù)的先進(jìn)先出原理就可以使用 隊列。2. 可以采用順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，因為他們都是線性表，就像一排站 在一條線上的人，位置關(guān)系是一個挨一個的，這樣的順序不會改變，而改變點都在頭 或者尾，仍然保持形態(tài)不變的。七、【代碼】（10%）（本部分應(yīng)包括：完整的代碼及充分的注

12、釋。注意紙質(zhì)的實驗報告無需包括此部分。格式統(tǒng)一為，字體：Georgia , 行距：固定行距12，字號：小五）#include#include#include#define STACK_INIT_SIZE 50#define STACKINCREMENT 10#define OVERLOW -2#define ERROR -1typedef struct char *base;int top;int size;SqStack;typedef struct char *base;int front;int rear;SqQueue;void lnit_SqStack(SqStack & s) /初

13、始化順序桟s.base = (char *)malloc(sizeof(char) * STACK_INIT_SIZE);if(!s.base) exit(OVERLOW);s.top = 0;s.size = STACK_INIT_SIZE;void Push_SqStack(SqStack &s, char c) /壓入數(shù)據(jù)if(s.top = s.size)s.base = (char *)realloc(s.base,(sizeof(char) * (s.size + STACKINCREMENT); s.size += STACKINCREMENT;s.bases.top = c;s

14、.top +;int Pop_SqStack(SqStack &s, char &e) /出桟if(s.top = 0)return 0;s.top -;e = s.bases.top;return 1;char GetTop_SqStack(SqStack s)return s.bases.top - 1;int IsEmpty_SqStack(SqStack s)if(s.top = 0)return 1;elsereturn 0;void Init_SqQueue(SqQueue & q)初始化q.base = (char *)malloc(sizeof(char) * STACK_IN

15、IT_SIZE);if(!q.base)exit(OVERLOW);q.front = 0;q.rear = 0;void En_SqQueue(SqQueue &q, char c)進(jìn)隊歹if(q.rear + 1) % STACK_INIT_SIZE = q.front) exit(ERROR);q.baseq.rear = c;q.rear = (q.rear + 1) % STACK_INIT_SIZE;int De_SqQueue(SqQueue &q, char & e) / 出隊列if(q.front = q.rear)return 0;e = q.baseq.front;q.f

16、ront = (q.front + 1) % STACK_INIT_SIZE;return 1;void Translate(char c) / 打印字符printf(%c,c);void Reverse(char str,char strtmp)/將字符串反向int len = strlen(str);int i,t=0;for(i=len - 1;i=0;i_)strtmpt+ = stri;strtmpt = 0;int Execute(char ch, SqStack &s, SqQueue &q)SqStack ss;Init_SqStack(ss);char ch1100;char

17、 ch2100;char ch3100;char c1,e,c;int flag=0,t = 0,i=0,len;Reverse(ch,ch1);/將輸入進(jìn)來的ch反向for(i=0;ch1i!=0;i+)Push_SqStack(s,ch1i);while(Pop_SqStack(s,e) = 1)if(flag!= 0 & e != ) /此處是為了將找到第一個左括號之后的字符全部進(jìn)入括號操作桟ss中Push_SqStack(ss,e);if(GetTop_SqStack(ss) = () /遇到左括號(flag力口 1flag +;continue;if(e = B) /如果是字符B就進(jìn)

18、桟Push_SqStack(s,A);Push_SqStack(s,d);Push_SqStack(s,A);Push_SqStack(s,t);else if(e = A) /如果是字符A就相對應(yīng)的字符進(jìn)隊列En _SqQueue(q,s);En _SqQueue(q,a);En _SqQueue(q,e);else if(e =()Push_SqStack(ss,e);flag +; /flag每加一次，都有一個左括號，用flag來表示左括號的數(shù)量else if(e =) printf(” exit(-1);if(flag = 0)輸入的括號不匹配!n); /左括號和右括號不匹配，右括號比

19、左括號多 t=0;while(GetTop_SqStack(ss) !=() Pop_SqStack(ss,c); ch2t+ = c;Pop_SqStack(ss,c); / flag -;/ch2t = 0;len = strlen(ch2);if(len = 0)/continue;cl =ch2len - 1;t = 0;for(i=0;ilen - 1;i+) /ch3t+ = c1;ch3t+ =ch2i;ch3t+= c1; /作到最后第二個字符)彈岀左括號(每彈岀一個左括號就flag減少1此處是處理空括號的情況此步是對括號中的操作對第一個字符的操作(在最后一個字符處加上第一個字符：上一步的操作時只操ch3t = 0;if(lsEmpty_SqStack(ss) = 1) /如果操作括號的ss桟里面為空，則說明處理過程結(jié)束，ch3字符串現(xiàn)在是標(biāo)準(zhǔn)處理好的字符串，將ch3字符串倒著進(jìn)入原來的桟sReverse(ch3,ch2);for(i=0;ch2i!=0;i+)Push_SqStack(s,ch2i); /進(jìn)入之前操作的桟else /如果括號操作 桟ss不空，則將操作好的一個括