《數(shù)據(jù)結(jié)構(gòu)課程設計報告》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結(jié)構(gòu)課程設計報告（21頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、
山東理工大學計算機學院
課 程 設 計
（數(shù)據(jù)結(jié)構(gòu)）
班 級
姓 名
學 號
指導教師
二○一一年一月二十日
課程設計任務書及成績評定
課題名稱
魔王語言
Ⅰ、題目的目的和要求：
1、設計目的
鞏固和加深對數(shù)據(jù)結(jié)構(gòu)的理解，通過上機實驗、調(diào)試程序，加深對課本知識的理解，最終使學生能夠熟練應用數(shù)據(jù)結(jié)構(gòu)的知識寫程序。
（1）通過本課程的學習，能熟練掌握幾種基本數(shù)據(jù)結(jié)構(gòu)的基本操作。
（2）能針對給定題目，選擇相應的數(shù)據(jù)結(jié)構(gòu)，分析并設計算法，進而給出問題的正
2、確求解過程并編寫代碼實現(xiàn)。
2、設計題目要求：
程序設計中要求綜合運用所學的知識，本次上機實習的目的是更能綜合了解數(shù)據(jù)結(jié)構(gòu)所學的知識，并解決一些與實際應用結(jié)合緊密的、規(guī)模較大的問題。通過分析、設計，編寫代碼、調(diào)試等各個步驟環(huán)節(jié)的訓練，使我們深刻理解、牢固掌握數(shù)據(jù)結(jié)構(gòu)和算法設計技術，掌握分析、解決實際問題的能力。
通過做這次課程設計，要求在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示，數(shù)據(jù)結(jié)構(gòu)的選擇和應用，算法的設計及其實現(xiàn)等方面，加深對數(shù)據(jù)結(jié)構(gòu)基本內(nèi)容的理解。同時，在程序設計方法以及上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練。1
Ⅱ、設計進度及完成情況
日 期
內(nèi)
3、 容
1.10-1.11
選取參考書，查閱有關文獻資料，完成資料搜集和系統(tǒng)分析工作。
1.12~1.14
創(chuàng)建相關數(shù)據(jù)結(jié)構(gòu),錄入源程序。
1.17~1.19
調(diào)試程序并記錄調(diào)試中的問題，初步完成課程設計報告。
1.20~1.21
上交課程設計報告打印版并進行課程設計答辯，要求每個同學針對自己的設計回答指導教師3-4個問題。
考核結(jié)束后將課程設計報告和源程序的電子版交班長統(tǒng)一刻光盤上交。
Ⅲ、主要參考文獻及資料
[1] 嚴蔚敏 數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學出版社 1999
[2] 嚴蔚敏 數(shù)據(jù)結(jié)構(gòu)題集（C語言版）清華大學出版社
4、1999
[3] 譚浩強 C語言程序設計 清華大學出版社
[4] 與所用編程環(huán)境相配套的C語言或C++相關的資料
Ⅳ、成績評定：
設計成績： （教師填寫）
指導老師： （簽字）
二○一一 年 一 月 二 十一 日
目 錄
第一章 概述……………………………………………………………1
第二章 系統(tǒng)分析………………………………………………………2
第三章 概要設計………………………………………………………3
第四章
5、詳細設計………………………………………………………6
第五章 運行與測試……………………………………………………16
第六章 總結(jié)與心得……………………………………………………18
參考文獻………………………………………………………………19
第一章 概述
1.1魔王語言課程設計的意義
課程設計是實踐性教學中的一個重要環(huán)節(jié)，它以某一課程為基礎，可以涉及和課程相關的各個方面，是一門獨立于課程之外的特殊課程。課程設計是讓同學們對所學的課程更全面的學習和應用，理解和掌握課程的相關知識。《數(shù)據(jù)結(jié)構(gòu)》是一門重要的專業(yè)基礎課，是計算機理論和應用的核心基礎課程。
數(shù)據(jù)結(jié)
6、構(gòu)課程設計，要求學生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應用、算法的設計及其實現(xiàn)等方面，加深對課程基本內(nèi)容的理解。同時，在程序設計方法以及上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練。
1.2問題描述
在這次的課程設計中我選擇的題目是魔王語言的設計。有一個魔王總是使用自己的一
種非常精練而抽象的語言講話，沒人能聽的懂。但他的語言是可以逐步解釋成人能懂
得語言的，因為他的語言是由以下兩種形式的規(guī)則由人的語言逐 步抽象上去的：
（1）α->β1β2...βn
（2）(θδ1δ2...δn)->θδnθδn-1...θδ1θ
在這兩種形式中，從左到
7、右均表示解釋；從右到左表示抽象。試寫一個魔王解釋系統(tǒng)，把他的話解釋成人能聽懂得話。
第二章 系統(tǒng)分析
2.1基本要求
用下述兩條具體規(guī)則和上述規(guī)則形式（2）實現(xiàn)。設大寫字母表示魔王語言的詞匯；小寫字
母表示人的語言詞匯；希臘字母（a,b1,s,y1等）表示可以用大寫或小寫字母代換的變量。
魔王語言可含人的詞匯。
（1）B->tAdA
(2) A->sae
[測試數(shù)據(jù)]
B（ehnxgz）B
解釋成 tsaedsaeezegexenehetsaedsae
8、
若將小寫字母與漢字建立下表所示的對應關系，則魔王說的話是“天上一個鵝地上一個鵝鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一個鵝地上一個鵝?！?
2.2實現(xiàn)提示
將魔王的語言自右至左進棧，總是處理棧頂。若是開括號，則逐一出棧，將字母順序入隊列，直至閉括號出棧，并按規(guī)則要求逐一出隊列再處理后入棧。其他情形較簡單，請讀者思考如何處理，應首先實現(xiàn)棧和隊列的基本運算
第三章 概要設計
1、數(shù)據(jù)結(jié)構(gòu)的設計
由于問題的特殊性，可以用棧和隊列的順序存儲實現(xiàn)該程序設計。實現(xiàn)同題目中的實現(xiàn)提示相仿
9、。重要數(shù)據(jù)結(jié)構(gòu)包括一個棧和一個輔助隊列，一張記錄大寫字母處理規(guī)則的表以及記錄閉合左括號對應的括號表達式的表。處理方法是從左至右依次讀入待翻譯的字符串，根據(jù)讀入字符做出不同操作。如果讀到小寫字母，如果當前棧中壓入的左括號數(shù)目為0，則直接輸出，否則入棧；如果讀到大寫字母，如果當前棧中壓入的左括號數(shù)目為0，則輸出大寫字母對應的規(guī)則，否則入棧；如果讀到左括號，記下在串中的位置，然后入棧；如果讀到右括號，則依次彈出棧中的元素并將這些元素加入輔助隊列，直到彈出左括號為止。如果當前棧中壓入的左括號數(shù)目為0，則根據(jù)括號內(nèi)表達式處理規(guī)則將隊列中存放的從棧中彈出的元素輸出，否則將這些元素加入對應左括號位置的表項中
10、進行記錄，并生成記錄左括號位置的元素然后壓棧。最后處理完畢后，翻譯后的串輸出并且隊列和棧中為空。由于問題的特殊性，可以用棧和隊列的順序存儲實現(xiàn)該程序設計。
2、程序設計流程
(1)程序開始先由用戶輸入一種規(guī)則。
(2)接著再讀入想要解釋的魔王語言。
(3)程序?qū)斎氲囊?guī)則進行翻譯，翻譯成人類語言。
(4)對魔王語言進行解釋，首先用POP（）函數(shù)把魔王語言的每一個字符讀出。
(5)對每個字符進行篩選，符合輸入規(guī)則的立即翻譯，并保存。
(6)對括號中的字符，即人類語言。先把括號中的字符全部出棧并保存。
(7)按規(guī)則把隊列中的字符進行翻譯，并保存。
(8)依次執(zhí)行，
11、直至翻譯完畢。
3、算法的設計
1. 本設計程序從總體上劃分四個模塊：
1） 主程序模塊：
Void main()
{
初始化；
For（）
{
接受處理命令；
}
接受處理；
}
2） 棧模塊——實現(xiàn)棧的抽象數(shù)據(jù)類型；
3） 隊列模塊——實現(xiàn)隊列的抽象數(shù)據(jù)類型。
4） 魔王語言解釋模塊——定義線性表的結(jié)點結(jié)構(gòu)。
各模塊的之間的調(diào)用關系如下：
主程序模塊
魔王語言解釋模塊
12、
棧模塊
隊列模塊
4、抽象數(shù)據(jù)類型的設計
(1)設定棧的抽象數(shù)據(jù)類型定義為：
ADT Stack｛
數(shù)據(jù)對象：D=｛ai | ai∈CharSet，I=1，2，......，n,n≥0｝
數(shù)據(jù)關系：R1=｛< ai-1，ai > |ai-1，ai∈D,I=1，2，......，n｝
基本操作：
ListInitiate (&S)
操作結(jié)果：構(gòu)造一個空棧S。
StackEmpty（S）
初始條件：棧S已經(jīng)存在。
操作結(jié)果：若棧S為空棧，則返回TRUE，否則返
13、回FALSE。
Push（&S,e）
初始條件：棧S已經(jīng)存在。
操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。
Pop（&S,&e）
初始條件：棧S已經(jīng)存在。
操作結(jié)果：刪除S的棧頂元素，并以e返回其值。
} ADT Stack
(2. ) 設定隊列的抽象數(shù)據(jù)類型定義為：
ADTQueue｛
數(shù)據(jù)對象：D=｛ai | ai∈ElemSet，I=1，2，......，n,n≥0｝
數(shù)據(jù)關系：R1=｛< ai-1，ai > |ai-1，ai∈D,I=1，2，......，n｝
基本操作：
ListInitiate (&Q)
操作結(jié)果：構(gòu)造一個空隊列Q。
Stac
14、kEmpty（Q）
初始條件：隊列Q已經(jīng)存在。
操作結(jié)果：若隊列Q為空棧，則返回TRUE，否則返回FALSE。
EnQueue（&Q,e）
初始條件：隊列Q已經(jīng)存在。
操作結(jié)果：插入元素e為Q的新的隊尾元素。
DeQueue（&Q,&e）
初始條件：隊列Q已經(jīng)存在。
操作結(jié)果：刪除Q的對頭元素，并以e返回其值。
} ADT Queue
第四章 詳細設計
1、 設計抽象數(shù)據(jù)類型對應的類定義。
（1）棧類型
typedef struct
{
char *base;
char *top;
int stacksiz
（2） 隊列
15、類型
typedef struct QNode
{
char data;
struct QNode * e;
}stack;next;
}QNode,*LinkQueueNode;
typedef struct
{
LinkQueueNode front;
LinkQueueNode rear;
}LinkQueue;
（3）棧的基本操作
int Initstack(stack &s)
{
s.base=(char*)malloc(100*sizeof(char));
if(!s.base)exit(0);
s.top=s.base
16、;
s.stacksize=100;
return 1;
}
int IsEmpty(stack s)
{
if(s.top==s.base)return 1;
return 0;
}
void push(stack &s,char e)
{
if(s.top-s.base>=s.stacksize)
{
s.base=(char*)realloc(s.base,(s.stacksize+10)*sizeof(char));
if(!s.base)exit(0);
s.top=s.base+s.stacksize;
s.st
17、acksize+=10;
}
*s.top++=e;
}
int pop(stack &s,char &e)
{
if(s.top==s.base)exit(0);
e=*--s.top;
return 1;
}
4隊列的基本操作
int initQueue(LinkQueue &Q)
{
Q.front=Q.rear=(LinkQueueNode)malloc(sizeof(LinkQueueNode));
if(!Q.front)exit(-1);
Q.front->next=NULL;
return 1;
}
int Isempt
18、y(LinkQueue Q)
{
if(Q.front==Q.rear)return 1;
return 0;
}
int EnQueue(LinkQueue &Q,char e)
{
LinkQueueNode p;
p=(LinkQueueNode)malloc(sizeof(QNode));
if(!p)exit(-1);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return 1;
}
char DeQueue(LinkQueue &Q,char &e)
{
LinkQu
19、eueNode p;
if(Q.front==Q.rear)return 0;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
free(p);
return e;
}
2. 主函數(shù)和其他函數(shù)的算法：
#include
#include
#include
using namespace std;
typedef struct
{
char letter;
char *ch
20、inese;
}ElemType;//字母-漢字元素表的對應類型
typedef struct SqList
{
ElemType *elem;
int length;
}SqList;//字母-漢字對應表
//----------------生成字母-漢字對應表----------------//
void BuildLookupTable(SqList *&sq)
{
sq = new SqList;
sq->length = 10;
sq->elem = new ElemType[10];
sq->el
21、em[0].letter = t;
sq->elem[0].chinese = "天";
sq->elem[1].letter = d;
sq->elem[1].chinese = "地";
sq->elem[2].letter = s;
sq->elem[2].chinese = "上";
sq->elem[3].letter = a;
sq->elem[3].chinese = "一個";
sq->elem[4].letter = e;
sq->e
22、lem[4].chinese = "鵝";
sq->elem[5].letter = z;
sq->elem[5].chinese = "追";
sq->elem[6].letter = g;
sq->elem[6].chinese = "趕";
sq->elem[7].letter = x;
sq->elem[7].chinese = "下";
sq->elem[8].letter = n;
sq->elem[8].chinese = "蛋";
sq
23、->elem[9].letter = i;
sq->elem[9].chinese = "恨";
}
//---------定義元素e在字母-漢字對應表中的位置------------//
int LocateElem(SqList *sq,char e)
{
int i;
for(i=0;i<10;i++)
{
if (sq->elem[i].letter == e)
return i;
}
return -1;
}
//------------------定義全局變量-----------------------
24、-//
int top=0;
int find=0;
char transl[200];
char leag[200];
char link[100];
int rear=1;
//----------------------main（）主函數(shù)---------------------//
int main()
{
system(colour “b”);
SqList *sq;
sq=new SqList;
char pop(); //定義出棧函數(shù)
char ml[2][200];
25、 //定義兩個規(guī)則，把它們存放到ml中
cout<
26、 "<
27、 ** "<ββββ... ** "<θβθβθβθ
28、 ** "<
29、t<<" **套已輸入的規(guī)則。 ** "<
30、 ** "<
31、********************************************";
//本程序可以翻譯魔王語言且按以下兩條形式規(guī)則由人的語言逐步抽象上去：
// ①α->ββββ...
// ②(θβββ)θβθβθβθ
//下面只輸入個第一種形式的規(guī)則，且后輸入的可以嵌套已輸入的規(guī)則
/*開始輸入規(guī)則A和B，A比B先輸入，再輸入B，這樣B就可以嵌套A*/
cout<<"以下請開始翻譯："<";
cin>>ml[0];
cout<<"B
32、->";
cin>>ml[1];
cout<>leag;
char temp[100]; //定義一個緩沖區(qū)，存放B的翻譯
int sizeA=0; //定義A的長度
sizeA=strlen(ml[0]);
int wh=0;
33、 //定義緩沖區(qū)中的位置變量
for(int i=0;ml[1][i]!=\0;i++) //開始翻譯B
{
if(ml[1][i]==A) //如果嵌套了A
{
for(int n=0;n
34、 //如果不是A則原樣寫入
wh++;
}
}
temp[wh]=0; //為緩存區(qū)加上結(jié)束符
strcpy(ml[1],temp); //把緩存區(qū)中的串給ml[1]
int sizeB=0; //定義B的長度
sizeB=strlen(ml[1]);
int length;
length=strlen(leag); //取得魔王語言的長度
int ch;
35、 //定義一個變量保存字符
int a;
int b;
/*-------開始翻譯魔王語言，并把結(jié)果存至transl中------------*/
for(int t=0;t
36、 break;
case B: //如果是B的話
for(b=0;b
37、=ch; //記得rear的初值為1
rear++;
}
//由于while循環(huán)的原因，在link隊列中多加了一個右括號字符，且rear指針向后多移了個單位
//故使rear減2
rear=rear-2;
transl[find++]=link[0];
for(rear;rear!=0;rear--)
{
transl[find++]=link[rear];
transl[find++]=link[0];
38、
}
//為了使后面的翻譯可行話，得把rear還原為初值，即rear=1
rear=1;
break;
default:break;
}//switch結(jié)束
/*--------翻譯魔鬼語言結(jié)束，結(jié)果已存至transl中------------*/
}//for結(jié)束cout<<"經(jīng)過翻譯，魔王想表達的語言是:";
//輸出得到的翻譯語言是
cout<
39、ildLookupTable(sq); //調(diào)用該函數(shù)生成字母-漢字對應表
//--------------輸出轉(zhuǎn)換之后的漢字--------------------//
while (transl[i]!=NULL)
{
*word = transl[i];
cout<elem[LocateElem(sq, *word)].chinese;
i++;
}
delete word;
char wc;
cout<<"輸入任意字符加回車鍵退出程序!!";
cin>>wc;
retu
40、rn 0;
}
char pop()//出棧函數(shù)的實現(xiàn)
{
return leag[top++];
}
第五章 運行與測試
1.程序調(diào)試所注意的事項即遇到的問題
1)函數(shù)調(diào)用。函數(shù)的調(diào)用是語言中一塊十分重要的一部分。它可以把程序分成若干部分，然后進行配置，它使程序更容易理解。所以學好這一塊內(nèi)容很重要。
2)棧和隊列的綜合應用，棧是后進先出的線性表，隊列是先進先出的線性表。
3)還利用了函數(shù)的嵌套，后輸入的嵌套先輸入的。再進行測試時人類
41、語言的小寫字符必須用括號括起來，魔王字符必須是大寫字符。
2、數(shù)據(jù)的測試和測試結(jié)果是
1）數(shù)據(jù)的測試
輸入
A->sae 回車
B->tAdA 回車
如下圖所示的輸入
2）測試結(jié)果
請輸入要解釋的魔王語言
B(einxgz)B
運行結(jié)果為下圖所示
結(jié)果為魔王所說的話。
第六章 總結(jié)與心得
經(jīng)過一個學期對數(shù)據(jù)結(jié)構(gòu)的學習，使我對其有了更深的了解。在近兩周的魔王語言的課程設計期間，在這個過程中，遇到了不少困難，但最終還是在自己的努力和同學老師的幫助下完成了設計
42、。它使我學到了不少，使我明白了數(shù)據(jù)結(jié)構(gòu)在生活中的應用，也知道了自己在學習數(shù)據(jù)結(jié)構(gòu)的某方面的不足之處，并提醒我要在不足的地方繼續(xù)努力。
本次程序設計任務完成情況良好，能夠較好的解決題目所給的要求，達到了程序設計的輸入、輸出、有窮性、確定性、可行性、確定性的程序要求。
在做程序設計的過程中，我學到了不少，使我對數(shù)據(jù)結(jié)構(gòu)的認識上升到了一個新的高度，使我對自己所學的專業(yè)有了新的認識，對自己的定位也更清楚了，對自己以后應該怎樣學，學什么有了一個新的目標。
首先我要感謝所有幫助我的同學，他們幫我度過了難關。最后我還要感謝我的指導老師，給了我很大的幫助，使我的工作事半功倍。
43、
參考文獻:
[1] 嚴蔚敏、吳偉民主編 《數(shù)據(jù)結(jié)構(gòu)》（C語言版） 清華大學出版社 2002
[2] 殷人昆等著 《數(shù)據(jù)結(jié)構(gòu)》（C++版） 清華大學出版社 2001
[3] 金遠平著 《數(shù)據(jù)結(jié)構(gòu)》（C++描述） 清華大學出版社 2005
[4] 許卓群等著 《數(shù)據(jù)結(jié)構(gòu)與算法》 高等教育出版社 200
[5] Frank M.Carrano 等著 《數(shù)據(jù)結(jié)構(gòu)與Ｃ++高級教程》清華大學出版社 2004
[6] 嚴蔚敏、吳偉民 《數(shù)據(jù)結(jié)構(gòu)習題集》（C語言版）清華大學出版社
17
數(shù)據(jù)結(jié)構(gòu)課程設計報告
