云南大學(xué)軟件學(xué)院數(shù)據(jù)結(jié)構(gòu)實驗3
《云南大學(xué)軟件學(xué)院數(shù)據(jù)結(jié)構(gòu)實驗3》由會員分享，可在線閱讀，更多相關(guān)《云南大學(xué)軟件學(xué)院數(shù)據(jù)結(jié)構(gòu)實驗3（11頁珍藏版）》請在裝配圖網(wǎng)上搜索。
云南大學(xué)軟件學(xué)院 數(shù)據(jù)結(jié)構(gòu)實驗報告 實驗難度： 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ī)則： 大寫字母表示魔王語言的詞匯，小寫字母表示人的詞匯語言,魔王語言中可以包含括號，魔王語言的產(chǎn)生式規(guī)則在程序中給定，當(dāng)接收用戶輸入的合法的魔王語言時，通過調(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 OVERLOW -2 #define ERROR -1 typedef 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, char &e) //出桟 char GetTop_SqStack(SqStack s)//或得棧頂 int IsEmpty_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, SqQueue &q)//魔王語言操作 調(diào)用關(guān)系： 三、【實現(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 ch[100]; char ch1[100]; char ch2[100]; 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(e); } } else printf("輸入的括號不匹配!"); //左括號比右括號多，不匹配 //********************************************************中文解密 printf("\n"); printf("請輸入魔王語言："); gets(ch1); Init_SqStack(s); Init_SqQueue(q); Reverse(ch1,ch2); { for(int i=0;ch2[i]!=\0;i++) Push_SqStack(s,ch2[i]); while(Pop_SqStack(s,e) == 1) { switch(e) { casew: printf("我"); 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)行分析，可附截圖） 輸入的魔王語言為：B(ehnxgz)B 翻譯的結(jié)果為： tsaedsaeezegexenehetsaedsae 錯誤模式：括號匹配錯誤提示。 輸入的魔王語言為：wasjg 翻譯為漢語的結(jié)果為： 我愛數(shù)據(jù)結(jié)構(gòu) 結(jié)論：此程序能夠按照給定的翻譯規(guī)則解釋魔王語言。 五、【實驗總結(jié)】(10%) （本部分應(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中，直至遇到右括號，將其壓入棧S1中，并將棧S2彈出依次壓入棧S1中，直至遇到左括號壓入棧S1中，這樣棧S1中存放的內(nèi)容就是匹配的第一個內(nèi)重括號，將棧S1棧頂元素左括號彈出，將左括號下面的那個元素保存在e1變量中，然后將其他元素彈出依次壓入棧S3中，在將e1與棧S3中依次彈出的元素壓入棧S2中，重復(fù)這個過程，直至將魔王語言中所有的括號都處理完為止，所以這個思路可以處理多重括號嵌套的問題。 六、思考題或【項目運(yùn)作描述（Operate）】(10%) （注：選擇C難度的才需要填寫“項目運(yùn)作描述”，其他難度的只需完成思考題） （項目運(yùn)作描述應(yīng)包括：項目的成本效益分析，應(yīng)用效果等的分析。） 1.棧：特點就是一個先進(jìn)后出的結(jié)構(gòu)。 主要用途：函數(shù)調(diào)用和返回，數(shù)字轉(zhuǎn)字符，表達(dá)式求值，走迷宮等等。在CPU內(nèi)部棧主要是用來進(jìn)行子程序調(diào)用和返回，中斷時數(shù)據(jù)保存和返回。在編程語言中：主要用來進(jìn)行函數(shù)的調(diào)用和返回?？梢哉f在計算機(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)包括：完整的代碼及充分的注釋。 注意紙質(zhì)的實驗報告無需包括此部分。格式統(tǒng)一為，字體: Georgia , 行距: 固定行距12，字號: 小五） #include下載提示(請認(rèn)真閱讀)
- 1.請仔細(xì)閱讀文檔，確保文檔完整性，對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點此舉報后獲取現(xiàn)金獎勵！
下載文檔到電腦，查找使用更方便
15 積分
| 下載 |
還剩頁未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 云南大學(xué) 軟件 學(xué)院 數(shù)據(jù)結(jié)構(gòu) 實驗
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
鏈接地址：http://m.zhongcaozhi.com.cn/p-11057749.html