《云南大學(xué)軟件學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)3》由會(huì)員分享，可在線閱讀，更多相關(guān)《云南大學(xué)軟件學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)3（11頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

云南大學(xué)軟件學(xué)院 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)難度： A □ B □ C □ 序號(hào) 學(xué)號(hào) 姓名 成績(jī) 指導(dǎo)教師 （簽名） 學(xué)　　期：　　2017秋季學(xué)期 任課教師: 　　 　　 實(shí)驗(yàn)題目: 組員及組長(zhǎng): 　 　　 承擔(dān)工作：　 　　 聯(lián)系電話: 　 　　　　　 電子郵件: 　 完成提交時(shí)間： 年 月 日 　 一、【實(shí)驗(yàn)構(gòu)思（Conceive）】(10%) （本部分應(yīng)包括：描述實(shí)驗(yàn)實(shí)現(xiàn)的基本思路，包括所用到的離散數(shù)學(xué)、工程數(shù)學(xué)、程序設(shè)計(jì)等相關(guān)知識(shí)，對(duì)問(wèn)題進(jìn)行概要性地分析） 魔王語(yǔ)言的解釋規(guī)則： 大寫字母表示魔王語(yǔ)言的詞匯，小寫字母表示人的詞匯語(yǔ)言,魔王語(yǔ)言中可以包含括號(hào)，魔王語(yǔ)言的產(chǎn)生式規(guī)則在程序中給定，當(dāng)接收用戶輸入的合法的魔王語(yǔ)言時(shí)，通過(guò)調(diào)用魔王語(yǔ)言翻譯函數(shù)來(lái)實(shí)現(xiàn)翻譯。 在 A 的基礎(chǔ)上，（根據(jù)產(chǎn)生式）自定義規(guī)則，將一段魔王的話翻譯為有意義的人類語(yǔ)言（中文）：輸入wasjg,則魔王語(yǔ)言解釋為“我愛(ài)數(shù)據(jù)結(jié)構(gòu)”。 運(yùn)用了離散數(shù)學(xué)的一些基本知識(shí)及程序設(shè)計(jì)知識(shí)。 二、【實(shí)驗(yàn)設(shè)計(jì)(Design)】(20%) （本部分應(yīng)包括：抽象數(shù)據(jù)類型的定義和基本操作說(shuō)明，程序包含的模塊以及各模塊間的調(diào)用關(guān)系，關(guān)鍵算法偽碼描述及程序流程圖等，如有界面則需包括界面設(shè)計(jì)，功能說(shuō)明等） //---------------抽象數(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)體類型隊(duì)列 //---------------各個(gè)模塊功能的描述------------------// 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)隊(duì)列 int De_SqQueue(SqQueue &q, char &e) //出隊(duì)列 void Translate(char c) //打印字符 void Reverse(char str[],char strtmp[])//將字符串反向 int Execute(char ch[], SqStack &s, SqQueue &q)//魔王語(yǔ)言操作 調(diào)用關(guān)系： 三、【實(shí)現(xiàn)（Implement）】(30%) （本部分應(yīng)包括：抽象數(shù)據(jù)類型各操作的具體實(shí)現(xiàn)代碼、 關(guān)鍵操作的具體算法實(shí)現(xiàn)、 函數(shù)實(shí)現(xiàn)，主程序?qū)崿F(xiàn)等，并給出關(guān)鍵算法的時(shí)間復(fù)雜度分析。如有界面則需包括界面的關(guān)鍵實(shí)現(xiàn)方法等。） 主程序模塊： int main() { char ch[100]; char ch1[100]; char ch2[100]; char e; //********************************************************英文解密 printf("請(qǐng)輸入魔王語(yǔ)言："); 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("輸入的括號(hào)不匹配!"); //左括號(hào)比右括號(hào)多，不匹配 //********************************************************中文解密 printf("\n"); printf("請(qǐng)輸入魔王語(yǔ)言："); 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("愛(ài)"); break; cases: printf("數(shù)據(jù)"); break; casej: printf("結(jié)"); break; caseg: printf("構(gòu)"); break; } } } return 0; } 其他函數(shù)實(shí)現(xiàn)代碼見(jiàn)七、【代碼】部分。 時(shí)間復(fù)雜復(fù)分析：o(n)。 四、【測(cè)試結(jié)果（Testing）】(10%) （本部分應(yīng)包括：對(duì)實(shí)驗(yàn)的測(cè)試結(jié)果，應(yīng)具體列出每次測(cè)試所輸入的數(shù)據(jù)以及輸出的數(shù)據(jù)，并對(duì)測(cè)試結(jié)果進(jìn)行分析，可附截圖） 輸入的魔王語(yǔ)言為：B(ehnxgz)B 翻譯的結(jié)果為： tsaedsaeezegexenehetsaedsae 錯(cuò)誤模式：括號(hào)匹配錯(cuò)誤提示。 輸入的魔王語(yǔ)言為：wasjg 翻譯為漢語(yǔ)的結(jié)果為： 我愛(ài)數(shù)據(jù)結(jié)構(gòu) 結(jié)論：此程序能夠按照給定的翻譯規(guī)則解釋魔王語(yǔ)言。 五、【實(shí)驗(yàn)總結(jié)】(10%) （本部分應(yīng)包括：自己在實(shí)驗(yàn)中完成的任務(wù)，及存在的問(wèn)題，所完成實(shí)驗(yàn)過(guò)程中的具體經(jīng)驗(yàn)總結(jié)、心得） 問(wèn)題關(guān)鍵： 1.棧的初始化，入棧出棧操作，棧為空的判斷條件，隊(duì)列的初始化，入隊(duì)和出隊(duì)操作，隊(duì)列為空的判斷。以及隊(duì)列中最后一個(gè)元素被刪除后尾指針的修改。 2.主函數(shù)的操作。由于隊(duì)列和棧的操作始終為同一個(gè)，所以在主函數(shù)中，采用指針函數(shù)的調(diào)用，確保操作在同一個(gè)隊(duì)列和棧上。 3.一些細(xì)節(jié)處理，比如數(shù)組操作等。 4.另在查閱資料時(shí)候發(fā)現(xiàn)：將魔王語(yǔ)言作為一個(gè)字符串讀入進(jìn)來(lái)，首先檢查括號(hào)是否匹配，如果不匹配就無(wú)法解釋。如果匹配，然后將字符串從尾到頭依次壓入棧S中，將棧S中的內(nèi)容依次彈出壓入棧S2中，直至遇到右括號(hào)，將其壓入棧S1中，并將棧S2彈出依次壓入棧S1中，直至遇到左括號(hào)壓入棧S1中，這樣棧S1中存放的內(nèi)容就是匹配的第一個(gè)內(nèi)重括號(hào)，將棧S1棧頂元素左括號(hào)彈出，將左括號(hào)下面的那個(gè)元素保存在e1變量中，然后將其他元素彈出依次壓入棧S3中，在將e1與棧S3中依次彈出的元素壓入棧S2中，重復(fù)這個(gè)過(guò)程，直至將魔王語(yǔ)言中所有的括號(hào)都處理完為止，所以這個(gè)思路可以處理多重括號(hào)嵌套的問(wèn)題。 六、思考題或【項(xiàng)目運(yùn)作描述（Operate）】(10%) （注：選擇C難度的才需要填寫“項(xiàng)目運(yùn)作描述”，其他難度的只需完成思考題） （項(xiàng)目運(yùn)作描述應(yīng)包括：項(xiàng)目的成本效益分析，應(yīng)用效果等的分析。） 1.棧：特點(diǎn)就是一個(gè)先進(jìn)后出的結(jié)構(gòu)。 主要用途：函數(shù)調(diào)用和返回，數(shù)字轉(zhuǎn)字符，表達(dá)式求值，走迷宮等等。在CPU內(nèi)部棧主要是用來(lái)進(jìn)行子程序調(diào)用和返回，中斷時(shí)數(shù)據(jù)保存和返回。在編程語(yǔ)言中：主要用來(lái)進(jìn)行函數(shù)的調(diào)用和返回?？梢哉f(shuō)在計(jì)算機(jī)中，只要數(shù)據(jù)的保存滿足先進(jìn)后出的原理，都優(yōu)先考慮使用棧，所以棧是計(jì)算機(jī)中不可缺的機(jī)制。 隊(duì)列：特點(diǎn)就是一個(gè)先進(jìn)先出的結(jié)構(gòu)。只要滿足數(shù)據(jù)的先進(jìn)先出原理就可以使用隊(duì)列。 2. 可以采用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因?yàn)樗麄兌际蔷€性表，就像一排站在一條線上的人，位置關(guān)系是一個(gè)挨一個(gè)的，這樣的順序不會(huì)改變，而改變點(diǎn)都在頭或者尾，仍然保持形態(tài)不變的。 七、【代碼】(10%) （本部分應(yīng)包括：完整的代碼及充分的注釋。 注意紙質(zhì)的實(shí)驗(yàn)報(bào)告無(wú)需包括此部分。格式統(tǒng)一為，字體: Georgia , 行距: 固定行距12，字號(hào): 小五） #include #include #include #define STACK_INIT_SIZE 50 #define STACKINCREMENT 10 #define OVERLOW -2 #define ERROR -1 typedef struct { char *base; int top; int size; }SqStack; typedef struct { char *base; int front; int rear; }SqQueue; void Init_SqStack(SqStack &s) //初始化順序桟 { 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.base[s.top] = c; s.top ++; } int Pop_SqStack(SqStack &s, char &e) //出桟 { if(s.top == 0) return 0; s.top --; e = s.base[s.top]; return 1; } char GetTop_SqStack(SqStack s) { return s.base[s.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(sizeof(char) * STACK_INIT_SIZE); if(!q.base) exit(OVERLOW); q.front = 0; q.rear = 0; } void En_SqQueue(SqQueue &q, char c)//進(jìn)隊(duì)列 { if((q.rear + 1) % STACK_INIT_SIZE == q.front) exit(ERROR); q.base[q.rear] = c; q.rear = (q.rear + 1) % STACK_INIT_SIZE; } int De_SqQueue(SqQueue &q, char &e) //出隊(duì)列 { if(q.front == q.rear) return 0; e = q.base[q.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--) strtmp[t++] = str[i]; strtmp[t] = \0; } int Execute(char ch[], SqStack &s, SqQueue &q) { SqStack ss; Init_SqStack(ss); char ch1[100]; char ch2[100]; char ch3[100]; char c1,e,c; int flag=0,t = 0,i=0,len; Reverse(ch,ch1); //將輸入進(jìn)來(lái)的ch 反向 for(i=0;ch1[i]!=\0;i++) Push_SqStack(s,ch1[i]); while(Pop_SqStack(s,e) == 1) { if(flag != 0 && e != )) //此處是為了將找到第一個(gè)左括號(hào)之后的字符全部進(jìn)入括號(hào)操作 桟ss 中 { Push_SqStack(ss,e); if(GetTop_SqStack(ss) == () //遇到左括號(hào) ( flag加1 { flag ++; } continue; } if(e == B) //如果是字符B就進(jìn)桟 { Push_SqStack(s,A); Push_SqStack(s,d); Push_SqStack(s,A); Push_SqStack(s,t); } else if(e == A) //如果是字符A就相對(duì)應(yīng)的字符進(jìn)隊(duì)列 { En_SqQueue(q,s); En_SqQueue(q,a); En_SqQueue(q,e); } else if(e == () { Push_SqStack(ss,e); flag ++; //flag每加一次，都有一個(gè)左括號(hào),用flag來(lái)表示左括號(hào)的數(shù)量 } else if(e == )) { if(flag == 0) { printf("輸入的括號(hào)不匹配!\n"); //左括號(hào)和右括號(hào)不匹配，右括號(hào)比左括號(hào)多 exit(-1); } t=0; while(GetTop_SqStack(ss) != () { Pop_SqStack(ss,c); ch2[t++] = c; } Pop_SqStack(ss,c); //彈出左括號(hào) ( flag --; //每彈出一個(gè)左括號(hào)就flag減少 1 ch2[t] = \0; len = strlen(ch2); if(len == 0) //此處是處理空括號(hào)的情況 continue; c1 =ch2[len - 1]; t = 0; for(i=0;i

下載提示(請(qǐng)認(rèn)真閱讀)

• 1.請(qǐng)仔細(xì)閱讀文檔，確保文檔完整性，對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
• 2.下載的文檔，不會(huì)出現(xiàn)我們的網(wǎng)址水印。
• 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請(qǐng)點(diǎn)此認(rèn)領(lǐng)！既往收益都?xì)w您。

同意并開(kāi)始全文預(yù)覽

文檔包含非法信息？點(diǎn)此舉報(bào)后獲取現(xiàn)金獎(jiǎng)勵(lì)！

文檔加載中……請(qǐng)稍候！
如果長(zhǎng)時(shí)間未打開(kāi)，您也可以點(diǎn)擊刷新試試。

下載文檔到電腦，查找使用更方便

15 積分

下載

還剩頁(yè)未讀，繼續(xù)閱讀

舉報(bào)
版權(quán)申訴 word格式文檔無(wú)特別注明外均可編輯修改；預(yù)覽文檔經(jīng)過(guò)壓縮，下載后原文更清晰！ 立即下載

配套講稿：

如PPT文件的首頁(yè)顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。

特殊限制：

部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。

關(guān) 鍵  詞：

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

溫馨提示:
1: 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

  裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請(qǐng)勿作他用。

關(guān)于本文

本文標(biāo)題：云南大學(xué)軟件學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)3
鏈接地址：http://www.hcyjhs8.com/p-11057749.html

最新文檔

• 市教育局冬季運(yùn)動(dòng)會(huì)安全工作預(yù)案
• 2024年秋季《思想道德與法治》大作業(yè)及答案3套試卷
• 2024年教師年度考核表個(gè)人工作總結(jié)（可編輯）
• 2024年xx村兩委涉案資金退還保證書
• 2024年憲法宣傳周活動(dòng)總結(jié)+在機(jī)關(guān)“弘揚(yáng)憲法精神推動(dòng)發(fā)改工作高質(zhì)量發(fā)展”專題宣講報(bào)告會(huì)上的講話
• 2024年XX村合作社年報(bào)總結(jié)
• 2024-2025年秋季第一學(xué)期初中歷史上冊(cè)教研組工作總結(jié)
• 2024年小學(xué)高級(jí)教師年終工作總結(jié)匯報(bào)
• 2024-2025年秋季第一學(xué)期初中物理上冊(cè)教研組工作總結(jié)
• 2024年xx鎮(zhèn)交通年度總結(jié)
• 2024-2025年秋季第一學(xué)期小學(xué)語(yǔ)文教師工作總結(jié)
• 2024年XX村陳規(guī)陋習(xí)整治報(bào)告
• 2025年學(xué)校元旦迎新盛典活動(dòng)策劃方案
• 2024年學(xué)校周邊安全隱患自查報(bào)告
• 2024年XX鎮(zhèn)農(nóng)村規(guī)劃管控述職報(bào)告