1、云南大學(xué)軟件學(xué)院 數(shù)據(jù)結(jié)構(gòu)實驗報告 實驗難度： a b c 序號學(xué)號姓名成績指導(dǎo)教師 （簽名）學(xué)期：2017秋季學(xué)期 任課教師: 實驗題目: 組員及組長: 承擔工作： 聯(lián)系電話: 電子郵件: 完成提交時間： 年 月 日一、【實驗構(gòu)思（conceive）】(10%)（本部分應(yīng)包括：描述實驗實現(xiàn)的基本思路，包括所用到的離散數(shù)學(xué)、工程數(shù)學(xué)、程序設(shè)計等相關(guān)知識，對問題進行概要性地分析）魔王語言的解釋規(guī)則：大寫字母表示魔王語言的詞匯，小寫字母表示人的詞匯語言,魔王語言中可以包含括號，魔王語言的產(chǎn)生式規(guī)則在程序中給定，當接收用戶輸入的合法的魔王語言時，通過調(diào)用魔王語言翻譯函數(shù)來實現(xiàn)翻譯。在 a 的基礎(chǔ)上，

2、（根據(jù)產(chǎn)生式）自定義規(guī)則，將一段魔王的話翻譯為有意義的人類語言（中文）：輸入wasjg,則魔王語言解釋為“我愛數(shù)據(jù)結(jié)構(gòu)”。運用了離散數(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 overlow -2#define error -1typedef struct char

3、 *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, char &e) /出桟char gettop_sqstack(sqstack s)/

4、或得棧頂int isempty_sqstack(sqstack s)/判斷是否空棧void init_sqqueue(sqqueue &q)/初始化void en_sqqueue(sqqueue &q, char c)/進隊列int de_sqqueue(sqqueue &q, char &e) /出隊列void translate(char c) /打印字符void reverse(char str,char strtmp)/將字符串反向int execute(char ch, sqstack &s, sqqueue &q)/魔王語言操作調(diào)用關(guān)系：三、【實現(xiàn)（implement）】(30%)

5、（本部分應(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; init_sqstack(s); init_sqqueue(q); if(execute(ch,s,q) = 1) while(de_sqqueue(q,e) = 1) translate

6、(e); else printf(輸入的括號不匹配!); /左括號比右括號多，不匹配/*中文解密 printf(n); printf(請輸入魔王語言：); gets(ch1); init_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(我); break; casea: printf(愛); break; cases: printf(數(shù)據(jù)); break;

7、 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é)果進行分析，可附截圖）輸入的魔王語言為：b(ehnxgz)b 翻譯的結(jié)果為： tsaedsaeezegexenehetsaedsae 錯誤模式：括號匹配錯誤提示。輸入的魔王語言為：wasjg翻譯為漢語的結(jié)果為： 我愛數(shù)據(jù)結(jié)構(gòu)結(jié)論：此程序能夠按照給定的翻譯規(guī)則解釋魔王語言。五、【實驗

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

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

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

11、實驗報告無需包括此部分。格式統(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 init_sqstack(sqstack &s) /初始

12、化順序桟 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

13、 = c; s.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; else return 0;void init_sqqueue(sqqueue &q)/初始化 q.base = (char *)malloc(sizeo

14、f(char) * stack_init_size); if(!q.base) exit(overlow); q.front = 0; q.rear = 0;void en_sqqueue(sqqueue &q, char c)/進隊列 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) retu

15、rn 0; e = q.baseq.front; q.front = (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 s

16、s; init_sqstack(ss); char ch1100; char ch2100; char ch3100; char c1,e,c; int flag=0,t = 0,i=0,len; reverse(ch,ch1); /將輸入進來的ch 反向 for(i=0;ch1i!=0;i+) push_sqstack(s,ch1i); while(pop_sqstack(s,e) = 1) if(flag != 0 & e != ) /此處是為了將找到第一個左括號之后的字符全部進入括號操作 桟ss 中 push_sqstack(ss,e); if(gettop_sqstack(ss) =

17、() /遇到左括號 ( flag加1 flag +; continue; if(e = b) /如果是字符b就進桟 push_sqstack(s,a); push_sqstack(s,d); push_sqstack(s,a); push_sqstack(s,t); else if(e = a) /如果是字符a就相對應(yīng)的字符進隊列 en_sqqueue(q,s); en_sqqueue(q,a); en_sqqueue(q,e); else if(e = () push_sqstack(ss,e); flag +; /flag每加一次，都有一個左括號,用flag來表示左括號的數(shù)量 else i

18、f(e = ) if(flag = 0) printf(輸入的括號不匹配!n); /左括號和右括號不匹配，右括號比左括號多 exit(-1); t=0; while(gettop_sqstack(ss) != () pop_sqstack(ss,c); ch2t+ = c; pop_sqstack(ss,c); /彈出左括號 ( flag -; /每彈出一個左括號就flag減少 1 ch2t = 0; len = strlen(ch2); if(len = 0) /此處是處理空括號的情況 continue; c1 =ch2len - 1; t = 0; for(i=0;ilen - 1;i+)

19、 /此步是對括號中的操作 ch3t+ = c1; ch3t+ =ch2i; ch3t+ = c1; /對第一個字符的操作(在最后一個字符處加上第一個字符:上一步的操作時只操作到最后第二個字符) ch3t = 0; if(isempty_sqstack(ss) = 1) /如果操作括號的ss桟里面為空，則說明處理過程結(jié)束， ch3字符串現(xiàn)在是標準處理好的字符串，將ch3字符串倒著進入原來的桟s reverse(ch3,ch2); for(i=0;ch2i!=0;i+) push_sqstack(s,ch2i); /進入之前操作的桟 else /如果括號操作 桟ss 不空，則將操作好的一個括號中的字符壓入字符操作 桟ss 等待下一個右括號字符 )的輸入 for(i=0;ch3i!=0;i+) push_s