數(shù)據(jù)結(jié)構(gòu)課程設(shè)計魔王語言解釋

1、山東理工大學計算機學院課 程 設(shè) 計（數(shù)據(jù)結(jié)構(gòu)）班 級姓 名學 號指導教師二七 年 七 月 二十 日課程設(shè)計任務書及成績評定課題名稱魔王語言解釋、題目的目的和要求： 設(shè)計中要求綜合運用所學知識，上機解決一些與實際應用結(jié)合緊密的、規(guī)模較大的問題。通過分析、設(shè)計、編碼、調(diào)試等各環(huán)節(jié)的訓練，使學生深刻理解、牢固掌握數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計技術(shù)，掌握分析、解決實際問題的能力。通過這次設(shè)計，要求在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應用、算法的設(shè)計及其實現(xiàn)等方面，加深對課程基本內(nèi)容的理解。同時，在程序設(shè)計方法以及上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練。、設(shè)計進度及完成情況日 期內(nèi)

2、容7.2-7.4熟悉設(shè)計任務，查閱有關(guān)文獻資料，確定所采用的數(shù)據(jù)結(jié)構(gòu)，初步制定解決問題的方法，完成課程設(shè)計說明書內(nèi)容1-3部分。7.57.10選擇合適的存儲結(jié)構(gòu)，明確解決問題的算法，上機編寫并調(diào)試源程序。7.117.12整體調(diào)試程序并記錄調(diào)試中的問題，完成課程設(shè)計說明書第4-7部分。7.13演示設(shè)計成果，考核成績。整理課程設(shè)計說明書，上午11時，由學習委員交課程設(shè)計說明書(計算機科學系9#213或直接交給指導教師)、主要參考文獻及資料1 嚴蔚敏、吳偉民主編，數(shù)據(jù)結(jié)構(gòu)（c語言版），清華大學出版社，2002。2 殷人昆等著，數(shù)據(jù)結(jié)構(gòu)（c+版），清華大學出版社，2001。3 金遠平著，數(shù)據(jù)結(jié)構(gòu)（c+

3、描述），清華大學出版社，2005。4 許卓群等著，數(shù)據(jù)結(jié)構(gòu)與算法，高等教育出版社，2004。5 frank m.carrano等著,數(shù)據(jù)結(jié)構(gòu)與+高級教程，清華大學出版社，2004。6 嚴蔚敏、吳偉民著，數(shù)據(jù)結(jié)構(gòu)習題集（c語言版），清華大學出版社。、成績評定：設(shè)計成績： （教師填寫）指導老師： （簽字）二七年七月二十日目 錄第一章 概述.1第二章 系統(tǒng)分析.2第三章 系統(tǒng)設(shè)計.3第四章 程序設(shè)計流程圖.7第五章 源程序清單.9第六章 調(diào)試過程中的問題及系統(tǒng)測試情況.13第七章 結(jié)束語.14第一章 概述1.1本課程設(shè)計意義 課程設(shè)計是實踐性教學中的一個重要環(huán)節(jié)，它以某一課程為基礎(chǔ)，可以涉及和課程相

4、關(guān)的各個方面，是一門獨立于課程之外的特殊課程。課程設(shè)計是讓同學們對所學的課程進行更全面的學習和應用，理解和掌握課程的相關(guān)知識。數(shù)據(jù)結(jié)構(gòu)是一門重要的專業(yè)基礎(chǔ)課，是計算機理論和應用的核心基礎(chǔ)課程。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，要求學生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應用、算法的設(shè)計及其實現(xiàn)等方面，加深對課程基本內(nèi)容的理解。同時，在程序設(shè)計方法以及上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練。第二章 系統(tǒng)分析1.1主要功能：魔王總是使用自己的一種非常精練而抽象的語言講話,沒人能聽懂,但他的語言是可逐步解釋成人能聽懂的語言,因為他的語言是由以下兩種形式的規(guī)則由人的語言逐步抽象上去的:

5、- 1)a- (b1)(b2).(bm) 2)(op1)(p2).(pn)-o(pn)o(p(n-1).o(p1)o -在這兩種形式中,從左到右均表示解釋.試寫一個魔王語言的解釋系統(tǒng),把他的話解釋成人能聽得懂的話. 1.2基本要求: 用下述兩條具體規(guī)則和上述規(guī)則形式(2)實現(xiàn).設(shè)大寫字母表示魔王語言的詞匯;小寫字母表示人的語言的詞匯;希臘字母表示可以用大寫字母或小寫字母代換的變量.魔王語言可含人的詞匯. 1) b - tada 2) a - sae第三章 系統(tǒng)設(shè)計功能模塊層次結(jié)構(gòu)圖：調(diào)用link（）把括號中的字符全部進隊列，按規(guī)則翻譯按規(guī)則進行翻譯根據(jù)用pop（）出棧的字符進行判斷：a：大寫字

6、符b：左括號輸入魔王語言輸入一組規(guī)則調(diào)用gzcin（）輸入規(guī)則調(diào)用mycin（）輸入語言調(diào)用change（）進行翻譯在屏幕輸出數(shù)據(jù)結(jié)構(gòu)的名稱及描述:（1）棧：adt stack數(shù)據(jù)對象：d=ai|ai elemset,i=1,2,n, n=0數(shù)據(jù)關(guān)系：r1=|ai-1,ai d,i=2,n 約定an端為棧頂，a1端為棧底?；静僮鳎?initstack(&s)操作結(jié)果：構(gòu)造一個空棧s。 destroystack(&s)初始條件：棧s已存在。操作結(jié)果：棧s被取消。 clearstack(&s)初始條件：棧s已存在。操作結(jié)果：將s清為空棧。 stackempty(s)初始條件：棧s已存在。操作結(jié)果

7、：若棧s為空棧，則返回true，否則false。 stacklength(s)初始條件：棧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 stack棧的

8、順序存儲表示：#define stack_init_size 100; /存儲空間初始分配量#define stackincrement 10; /存儲空間分配增量typedef struct selemtype *base; /在棧構(gòu)造之前和銷毀之后，base的值為null selemtype *top; /棧頂指針 int stacksize; /當前已分配的空間，以元素為單位sqstack;（2）隊列：adt queue數(shù)據(jù)對象:d=ai|ai elemset,i=1,2,n, n=0數(shù)據(jù)關(guān)系：r1=|ai-1,ai d,i=2,n 約定其中a1端為隊列頭，an端為隊列尾。基本操作：in

9、itqueue(&q) 操作結(jié)果：構(gòu)造一個空隊列q。destroyqueue(&q) 初始條件：隊列q已存在。 操作結(jié)果：隊列q被銷毀，不再存在。clearqueue(&q) 初始條件：隊列q已存在。 操作結(jié)果：將q清空為空隊列。queueempty(q) 初始條件：隊列q已存在。 操作結(jié)果:若隊列q為空隊列，則返回true,否則false。queuelength(q) 初始條件：隊列q已存在。 操作結(jié)果: 返回q的元素個數(shù)，即隊列的長度。gethead(q,&e) 初始條件：q為非空隊列。 操作結(jié)果: 用e返回q的隊頭元素。enqueue(&q,e) 初始條件：隊列q已存在。 插入元素e作為

10、q的隊尾元素。dequeue(&q,&e) 初始條件：q為非空隊列。 操作結(jié)果: 刪除q的隊頭元素，并用e返回其值。queuetraverse(q,visit() 初始條件：隊列q已存在且非空。 操作結(jié)果: 從隊頭到隊尾,依次對q的每個數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。adt queue隊列的鏈式存儲結(jié)構(gòu)：typedef struct qnode qelemtype data; struct qnode *next;qnode,*queueptr;typedef struct queueptr front; /對頭指針 queueptr rear; /隊尾指針

11、linkqueue; 第四章 程序設(shè)計流程圖（1）程序開始先由用戶輸入一種規(guī)則使用cin和cout函數(shù)。（2）接著程序再讀入想要翻譯的魔王語言。（3）程序?qū)斎氲囊?guī)則進行翻譯，翻譯成人類語言。（4）對魔王語言進行翻譯，首先用pop（）函數(shù)把魔王語言每一個字符讀出。（5）再對字符進行篩選，符合輸入規(guī)則的立即翻譯。保存至transl中。（6）對于括號中的字符，即人類語言。先把括號中的字符全部出棧，保存至link中。（7）按規(guī)則把隊列中的字符串進行翻譯，保存至transl中。（8）依次執(zhí)行，直到翻譯完所有字符串。程序設(shè)計流程圖如下：第五章 源程序清單程序清單如下：魔王.cpp/*-定義頭文件-*/#

12、include#include#include/*-定義全局變量-*/int top=0;int find=0;/top=0;char transl200;char leag200;char link100;int rear=1;/rear=1;/*-main()主函數(shù)-*/int main()char pop(); /定義出棧函數(shù)char ml2200; /定義兩個規(guī)則，把它們存放到ml中coutendl;cout * 魔王語言程序設(shè)計 * endl;cout * endl;cout * endl;cout * 本程序可以翻譯魔王語言且按以下兩條形式規(guī)則由人 * endl;cout * *

13、endl;cout *的語言逐步抽象上去： * endl;cout * * endl;cout1234. * endl;cout * * endl;cout321 * endl;cout * * endl;cout * 下面只輸入2個第一種形式的規(guī)則，且后輸入的可以嵌* endl;cout * * endl;cout *套已輸入的規(guī)則。 * endl;cout * * endl;cout * endl;cout * endl;cout1234. / (123)321 /下面只輸入2個第一種形式的規(guī)則，且后輸入的可以嵌套已輸入的規(guī)則 /*開始輸入規(guī)則a和b，a比b先輸入，再輸入b，這樣b就可以嵌

14、套a*/cout以下請開始翻譯：endl;cout請先輸入一組形式規(guī)則：endl; cout;cinml0;cout;cinml1;coutendl;/*輸入魔王語言，其規(guī)則為大寫為魔王語言，只限定a和b（暫時），小寫為人類語言，輸入時用括號括起來*/ coutleag;char temp100; /定義一個緩沖區(qū)，存放b的翻譯int sizea=0; /定義a的長度 sizea=strlen(ml0); int wh=0; /定義緩沖區(qū)中的位置變量for(int i=0;ml1i!=0;i+) /開始翻譯bif(ml1i=a) /如果嵌套了a/couthere is doing!;for(i

15、nt n=0;nsizea;n+,wh+)tempwh=ml0n; /翻譯至緩存區(qū)elsetempwh=ml1i; /如果不是a則原樣寫入wh+;tempwh=0; /為緩存區(qū)加上結(jié)束符strcpy(ml1,temp); /把緩存區(qū)中的串給ml1int sizeb=0; /定義b的長度 sizeb=strlen(ml1);int length;length=strlen(leag); /取得魔王語言的長度int ch; /定義一個變量保存字符int a;int b;/*-開始翻譯魔王語言，并把結(jié)果存至transl中-*/for(int t=0;tlength;t+) ch=pop(); swi

16、tch(ch)case a: /如果是a的話for(a=0;asizea;a+,find+)translfind=ml0a;break; case b: /如果是b的話 for(b=0;bsizeb;b+,find+)translfind=ml1b;break; case (: /但ch=(時，把括號中的小寫字母保存至link中ch=pop();link0=ch; /先把第一個字符存入，后面的從link1開始while(ch!=) ch=pop();linkrear=ch; /記得rear的初值為1rear+; /由于while循環(huán)的原因，在link隊列中多加了一個右括號字符，且rear指針向

17、后多移了2個單位 /故使rear減2rear=rear-2; translfind+=link0;for(rear;rear!=0;rear-)translfind+=linkrear; translfind+=link0; /為了使后面的翻譯可行話，得把rear還原為初值，即rear=1rear=1;break; default:break;/switch結(jié)束/*-翻譯魔鬼語言結(jié)束，結(jié)果已存至transl中-*/for結(jié)束cout經(jīng)過翻譯，魔王想表達的語言是：; /輸出得到的翻譯語言 coutendl;couttransl;coutyui回車b-tuasda回車魔王語言：baba(fqwerjijilo)abab輸出結(jié)果：翻譯輸出：結(jié)果正確。第七章 結(jié)束語經(jīng)過幾天和同學進行的程序設(shè)計合作，使我明白了做一件事情如果靠團結(jié)的力量是很容易完成的。再次感謝指導我們的老師，給了我們莫大的幫忙，使我們的工作