數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)_魔王語言解釋系統(tǒng)

1、石家莊經(jīng)濟(jì)學(xué)院 本科生課程設(shè)計(jì)報(bào)告書題 目 魔王語言解釋系統(tǒng) 姓名 XXXXXX 學(xué)號 學(xué) 院 信息工程學(xué)院 專業(yè) 電氣信息類 指導(dǎo)教師 XXXXXX 完成日期： 魔王語言解釋系統(tǒng)1 需求分析問題描述 有一個魔王總是使用自己的一種非常精練而又抽象的語言講話，沒有人能聽得懂，但他的語言是可以逐步解釋成人能聽懂的語言，因?yàn)樗恼Z言是由以下兩種形式的規(guī)則由人的語言逐步抽象上去的： （1） > 12m （2）（12n)>nn1 1 在這兩種形式中，從左到右均表示解釋。試寫一個魔王語言的解釋系統(tǒng)，把他的話解釋成人能聽得懂的話。 基本要求 用下述兩條具體規(guī)則和上述規(guī)則形式（2）實(shí)現(xiàn)。設(shè)大寫字母

2、表示魔王語言的詞匯；小寫字母表示人的語言詞匯；希臘字母表示可以用大寫字母或小寫字母代換的變量。魔王語言可含人的詞匯。 （1）B > tAdA （2）A > sae 測試數(shù)據(jù) B(ehnxgz)B解釋成tsaedsaeezegexenehetsaedsae 若將小寫字母與漢字建立下表所示的對應(yīng)關(guān)系，則魔王說的話是：“天上一只鵝地上一只鵝鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一只鵝地上一只鵝”。 tdsaezgxnh天地上一只鵝追趕下蛋恨過程分析(1)以一維數(shù)組demon i 表示魔王語言。 (2)魔王語言由用戶輸入,初始保存在demon i 中。 (3)魔王語言與人類語言對應(yīng)關(guān)系固化在程序中。

3、(4)實(shí)現(xiàn)過程： A：初始將魔王語言接收后存放在demon i 中。 B：初次遍歷數(shù)組，將數(shù)組中括號內(nèi)的元素入棧，同時插入相應(yīng)的首字母； C：再次遍歷數(shù)組，將數(shù)組元素依次入隊(duì)。（小寫字母直接入隊(duì)；大寫字母經(jīng)翻譯成相應(yīng)字符后入隊(duì)；遇到括號，將棧中保存的元素依次出棧入隊(duì)）在翻譯過程中，如果依舊包含大寫字母或括號，則置flag為1，否則為0。 D：將隊(duì)列中元素賦值給demon i 。如果此時flag=1，則再次重復(fù)C過程。直至所有元素為人類語言。 E：輸出demon i ，此時數(shù)組中元素為對應(yīng)的人類語言。注：如果程序中沒有相應(yīng)的對應(yīng)關(guān)系，則翻譯成“*”。F:將輸出數(shù)據(jù)存盤。2 概要設(shè)計(jì)為實(shí)現(xiàn)上述程序

4、功能，應(yīng)以棧和隊(duì)列來表示。 1）.設(shè)定棧的抽象數(shù)據(jù)類型定義為：ADT Stack 數(shù)據(jù)對象：D=ai|aiCharSet,i=1，2，,n,n0 數(shù)據(jù)關(guān)系：R1=<ai-1,ai>|ai-1,aiD,i=1,2,n基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個空棧S DestroyStack（&S）初始條件：棧S已存在。操作結(jié)果：棧S被銷毀。 ClearStack（&S）初始條件：棧S已存在。操作結(jié)果：將S清為空棧。 StackEmpty（S）初始條件：棧S已存在。操作結(jié)果：若棧S為空，則返回TURE，否則FLASE。 StackLength（S）初

5、始條件：棧S已存在。操作結(jié)果：返回S的元素個數(shù)，即棧的長度。 GetTop（S，&e）初始條件：棧S已存在。操作結(jié)果：用e 返回S的棧頂元素。 Push（&S，&e）初始條件：棧S已存在。操作結(jié)果：插入元素e為新的棧頂元素。Pop（&S,&e）初始條件：棧S已存在。操作結(jié)果：刪除S的棧頂元素，并用e的返回其值。 StackTraverse（S,Visit（）初始條件：棧S已存在且非空。操作結(jié)果：從棧底到棧頂依次對S的每個數(shù)據(jù)元素調(diào)用函數(shù)visit（）。一旦visit（）失敗，則操作失效。ADT Stack2）. 設(shè)定隊(duì)列的抽象數(shù)據(jù)類型定義為：ADT Qu

6、eue 數(shù)據(jù)對象：D=ai|aiElemSet,i=1，2，,n,n0 數(shù)據(jù)關(guān)系：R1=<ai-1,ai>|ai-1,aiD,i=1,2,n基本操作：InitQueue(&Q)操作結(jié)果：構(gòu)造一個空隊(duì)列Q。 DestroyQueue（&Q）初始條件：隊(duì)列Q已存在。操作結(jié)果：隊(duì)列Q被銷毀，不再存在。 ClearQueue（&Q）初始條件：隊(duì)列Q已存在。操作結(jié)果：將Q清為空隊(duì)列。 QueueEmpty（Q）初始條件：隊(duì)列Q已存在。操作結(jié)果：若隊(duì)列Q為空，則返回TURE，否則FLASE。 QueueLength（Q）初始條件：隊(duì)列Q已存在。操作結(jié)果：返回Q的元素個數(shù)

7、，即隊(duì)列的長度。 GetHead（Q，&e）初始條件：Q為非空隊(duì)列。操作結(jié)果：用e 返回Q的對頭元素。 EnQueue（&Q，&e）初始條件：隊(duì)列Q已存在。操作結(jié)果：插入元素e為Q的新隊(duì)尾元素。DeQueue（&Q,&e）初始條件：Q為非空隊(duì)列。操作結(jié)果：刪除Q的對頭元素，并用e的返回其值。 QueueTraverse（Q,Visit（）初始條件：Q已存在且非空。操作結(jié)果：從對頭到棧隊(duì)尾依次對Q的每個數(shù)據(jù)元素調(diào)用函數(shù)visit（）。一旦visit（）失敗，則操作失效。ADT Queue3）.各模塊之間調(diào)用關(guān)系: 主函數(shù)模塊 括號內(nèi)元素入棧處理模塊; 排序

8、入隊(duì)模塊 翻譯大寫處理模塊; 圖2.1 3 詳細(xì)設(shè)計(jì)流程圖 圖 3.1本程序包含四個模塊：A主函數(shù)模塊。其中主函數(shù)為：Status main()初始化棧；初始化隊(duì)列; 接收魔王語言輸入到數(shù)組demoni ; 遍歷數(shù)組將括號中元素進(jìn)棧; while(數(shù)組demoni 中元素有大寫字母) 翻譯排序處理后入隊(duì)列; 將對列元素保存在數(shù)組demoni ; 輸出人類語言(數(shù)組demon i); B.括號內(nèi)元素入棧處理模塊. tempstack(&temps) 將括號內(nèi)元素入棧,依次插入首字符.。舉例：(abcd)>adacaba.。C.排序入隊(duì)列模塊. sort(&s,&q)

9、 遍歷數(shù)組; 遇到小寫字母,直接入隊(duì)列; 遇到大寫字母,翻譯大寫后入隊(duì)列; 遇到括號,將棧中保存的元素依次出棧入隊(duì)列; D.翻譯大寫處理模塊. spenqueue(&*q,key) switch(key) 找到各個大寫字母對應(yīng)的字符串. 沒有相應(yīng)的則解釋為* 4 編碼調(diào)試1. 函數(shù)調(diào)用比較多,因而得仔細(xì)對待數(shù)值和地址的傳遞. 2. 由于魔王語言中B中仍然包含著大寫字母(tAdA).所以考慮設(shè)置flag. 3. 函數(shù)數(shù)組遍歷.進(jìn)棧出棧.入隊(duì)出隊(duì)中都要牽扯指針的移動,所以要仔細(xì)考慮一循環(huán)的條件以及進(jìn)棧元素的個數(shù).5 設(shè)計(jì)體會1. 本次課程設(shè)計(jì)各階段（需求分析、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編碼調(diào)試等

10、）所遇到的問題，問題的現(xiàn)象描述，產(chǎn)生的原因，解決方案（措施），解決的結(jié)果（1） 在需求分析階段：A錯誤：再次遍歷時時，只有當(dāng)數(shù)組中包含大寫字母時flag=1，且flag=1時只重復(fù)D過程改正：再次遍歷時，應(yīng)為當(dāng)數(shù)組中含有大寫字母或者是括號時flag=1，因此flag=1時應(yīng)重復(fù)C、D兩個過程，而不應(yīng)只重復(fù)D過程 即：在初次遍歷后入棧元素中仍有可能包含括號，這就需要多次對數(shù)組內(nèi)元素進(jìn)行初次遍歷的過程，所以重復(fù)過程應(yīng)將C包含在內(nèi)。 B錯誤：E過程中沒有考慮到無相應(yīng)對應(yīng)關(guān)系的情況。 改正：添加“如果程序中沒有相應(yīng)的對應(yīng)關(guān)系，則翻譯成“*”?！保?） 在詳細(xì)設(shè)計(jì)階段 A錯誤：下面模塊語言出現(xiàn)邏輯錯誤，

11、無法正確執(zhí)行 改正：（3） 在編碼調(diào)試階段A 錯誤：在調(diào)試階段彈出問題，不能完成程序的輸出 改正：指針發(fā)生沖突，下面的函數(shù)出現(xiàn)錯誤，紅色部分為修改內(nèi)容status sort(sqstack *s,linkqueue *q) qnode b1; qnode *b=&b1; int flag=0;/*大寫字母、括號監(jiān)視哨置零*/ . . .B 錯誤：將上述問題修改后，可實(shí)現(xiàn)程序的編譯和運(yùn)行但運(yùn)行結(jié)果仍出現(xiàn)問題，不能對大寫字母B進(jìn)行二次翻譯。改正：原錯誤代碼：status reverse (sqstack *s,linkqueue *q) int a; int i,flag=0; for(i

12、=0;demoni!='#'i+)/*遍歷數(shù)組*/ a=demoni; if('A'<=a&&a<='Z')|a='(') /*翻譯后的數(shù)組若仍然含有大寫字母或是括號則將flag賦值為*/ flag=1; else flag=0; return flag; 修改后代碼：status reverse (sqstack *s,linkqueue *q) int a; int i,flag; for(i=0;demoni!='#'i+)/*遍歷數(shù)組*/ a=demoni; if('A&

13、#39;<=a&&a<='Z')|a='(')/*翻譯后的數(shù)組若仍然含有大寫字母或是括號則將flag賦值為*/ flag=1; return 1; else flag=0; 6 致謝在這次課程設(shè)計(jì)的撰寫過程中，我得到了許多人的幫助。首先我要感謝我的老師在課程設(shè)計(jì)上給予我的指導(dǎo)、提供給我的支持和幫助，這是我能順利完成這次報(bào)告的主要原因，更重要的是老師幫我解決了許多技術(shù)上的難題，讓我能把系統(tǒng)做得更加完善。在此期間，我不僅學(xué)到了許多新的知識，而且也開闊了視野，提高了自己的設(shè)計(jì)能力。其次，我要感謝幫助過我的同學(xué)，他們也為我解決了不少我不太明白的設(shè)計(jì)商的