数据结构课程设计报告

1、山东理工大学计算机学院课 程 设 计（数据结构）班 级姓 名学 号 指导教师二一一年一月二十日课程设计任务书及成绩评定课题名称 魔王语言、题目的目的和要求： 1、设计目的巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。2、设计题目要求： 程序设计中要求综合运用所学的知识，本次上机实习的目的是更能综合了解数据结构所学的知识，并解决一些与实际应用结合紧密的、规模较大的问

2、题。通过分析、设计，编写代码、调试等各个步骤环节的训练，使我们深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。通过做这次课程设计，要求在数据结构的逻辑特性和物理表示，数据结构的选择和应用，算法的设计及其实现等方面，加深对数据结构基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。1、设计进度及完成情况日 期内 容1.10-1.11选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。1.121.14创建相关数据结构,录入源程序。1.171.19调试程序并记录调试中的问题，初步完成课程设计报告。1.201.21上交课程设计

3、报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。、主要参考文献及资料1 严蔚敏 数据结构（c语言版）清华大学出版社 19992 严蔚敏 数据结构题集（c语言版）清华大学出版社 19993 谭浩强 c语言程序设计 清华大学出版社4 与所用编程环境相配套的c语言或c+相关的资料、成绩评定：设计成绩： （教师填写）指导老师： （签字）二一一 年 一 月 二 十一 日目 录第一章 概述1第二章 系统分析2第三章 概要设计3第四章 详细设计6第五章 运行与测试16第六章 总结与心得18参考文献19第一章 概述

4、1.1魔王语言课程设计的意义课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。1.2问题描述在这次的课程设计中我选择的题目是魔王语言的设计。有一个魔王总是使用自己的一种非常精

5、练而抽象的语言讲话，没人能听的懂。但他的语言是可以逐步解释成人能懂得语言的，因为他的语言是由以下两种形式的规则由人的语言逐 步抽象上去的： （1）-12.n（2）(12.n)-nn-1.1 在这两种形式中，从左到右均表示解释；从右到左表示抽象。试写一个魔王解释系统，把他的话解释成人能听懂得话。 第二章 系统分析 2.1基本要求用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字 母表示人的语言词汇；希腊字母（a,b1,s,y1等）表示可以用大写或小写字母代换的变量。 魔王语言可含人的词汇。 （1）b-tada (2) a-sae 测试数据 b（ehnxgz）b 解释

6、成 tsaedsaeezegexenehetsaedsae 若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是“天上一个鹅地上一个鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一个鹅地上一个鹅。” 2.2实现提示 将魔王的语言自右至左进栈，总是处理栈顶。若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者思考如何处理，应首先实现栈和队列的基本运算第三章 概要设计1、数据结构的设计 由于问题的特殊性，可以用栈和队列的顺序存储实现该程序设计。实现同题目中的实现提示相仿。重要数据结构包括一个栈和一个辅助队列，一张记录大写字母处理规则的表以及记录闭合

7、左括号对应的括号表达式的表。处理方法是从左至右依次读入待翻译的字符串，根据读入字符做出不同操作。如果读到小写字母，如果当前栈中压入的左括号数目为0，则直接输出，否则入栈；如果读到大写字母，如果当前栈中压入的左括号数目为0，则输出大写字母对应的规则，否则入栈；如果读到左括号，记下在串中的位置，然后入栈；如果读到右括号，则依次弹出栈中的元素并将这些元素加入辅助队列，直到弹出左括号为止。如果当前栈中压入的左括号数目为0，则根据括号内表达式处理规则将队列中存放的从栈中弹出的元素输出，否则将这些元素加入对应左括号位置的表项中进行记录，并生成记录左括号位置的元素然后压栈。最后处理完毕后，翻译后的串输出并且

8、队列和栈中为空。由于问题的特殊性，可以用栈和队列的顺序存储实现该程序设计。2、程序设计流程 (1)程序开始先由用户输入一种规则。 (2)接着再读入想要解释的魔王语言。 (3)程序对输入的规则进行翻译，翻译成人类语言。 (4)对魔王语言进行解释，首先用pop（）函数把魔王语言的每一个字符读出。(5)对每个字符进行筛选，符合输入规则的立即翻译，并保存。(6)对括号中的字符，即人类语言。先把括号中的字符全部出栈并保存。(7)按规则把队列中的字符进行翻译，并保存。(8)依次执行，直至翻译完毕。3、算法的设计1. 本设计程序从总体上划分四个模块：1） 主程序模块：void main()初始化；for（）

9、接受处理命令；接受处理；2） 栈模块实现栈的抽象数据类型；3） 队列模块实现队列的抽象数据类型。4） 魔王语言解释模块定义线性表的结点结构。各模块的之间的调用关系如下： 主程序模块 魔王语言解释模块 栈模块队列模块 4、抽象数据类型的设计 (1)设定栈的抽象数据类型定义为： adt stack 数据对象：d=ai | aicharset，i=1，2，.，n,n0 数据关系：r1= |ai-1，aid,i=1，2，.，n 基本操作： listinitiate (&s) 操作结果：构造一个空栈s。stackempty（s）初始条件：栈s已经存在。操作结果：若栈s为空栈，则返回true，否则返回fa

10、lse。push（&s,e）初始条件：栈s已经存在。操作结果：在栈s的栈顶插入新的栈顶元素e。pop（&s,&e）初始条件：栈s已经存在。操作结果：删除s的栈顶元素，并以e返回其值。 adt stack(2. ) 设定队列的抽象数据类型定义为：adtqueue 数据对象：d=ai | aielemset，i=1，2，.，n,n0 数据关系：r1= |ai-1，aid,i=1，2，.，n 基本操作： listinitiate (&q) 操作结果：构造一个空队列q。stackempty（q）初始条件：队列q已经存在。操作结果：若队列q为空栈，则返回true，否则返回false。enqueue（&q

11、,e）初始条件：队列q已经存在。操作结果：插入元素e为q的新的队尾元素。dequeue（&q,&e）初始条件：队列q已经存在。操作结果：删除q的对头元素，并以e返回其值。 adt queue第四章 详细设计1、 设计抽象数据类型对应的类定义。（1）栈类型typedef structchar *base;char *top;int stacksiz（2） 队列类型typedef struct qnodechar data;struct qnode * e;stack;next;qnode,*linkqueuenode;typedef structlinkqueuenode front;linkq

12、ueuenode rear;linkqueue;（3）栈的基本操作int initstack(stack &s) s.base=(char*)malloc(100*sizeof(char); if(!s.base)exit(0); s.top=s.base; 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.sta

13、cksize+10)*sizeof(char);if(!s.base)exit(0);s.top=s.base+s.stacksize;s.stacksize+=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;retur

14、n 1;int isempty(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)linkqueuenode p;if(q.front=q.rear)return 0;p=q.f

15、ront-next;e=p-data;q.front-next=p-next;if(q.rear=p)q.rear=q.front;free(p);return e;2. 主函数和其他函数的算法：#include #include #includeusing namespace std;typedef struct char letter; char *chinese;elemtype;/字母-汉字元素表的对应类型typedef struct sqlist elemtype *elem; int length;sqlist;/字母-汉字对应表/-生成字母-汉字对应表-/void buildlo

16、okuptable(sqlist *&sq) sq = new sqlist; sq-length = 10; sq-elem = new elemtype10; sq-elem0.letter = t; sq-elem0.chinese = 天; sq-elem1.letter = d; sq-elem1.chinese = 地; sq-elem2.letter = s; sq-elem2.chinese = 上; sq-elem3.letter = a; sq-elem3.chinese = 一个; sq-elem4.letter = e; sq-elem4.chinese = 鹅; sq

17、-elem5.letter = z; sq-elem5.chinese = 追; sq-elem6.letter = g; sq-elem6.chinese = 赶; sq-elem7.letter = x; sq-elem7.chinese = 下; sq-elem8.letter = n; sq-elem8.chinese = 蛋; sq-elem9.letter = i; sq-elem9.chinese = 恨; /-定义元素e在字母-汉字对应表中的位置-/int locateelem(sqlist *sq,char e) int i; for(i=0;ielemi.letter =

18、e) return i; return -1; /-定义全局变量-/int top=0;int find=0;char transl200;char leag200;char link100;int rear=1;/-main（）主函数-/int main()system(colour “b”); sqlist *sq; sq=new sqlist; char pop(); /定义出栈函数 char ml2200; /定义两个规则，把它们存放到ml中 coutendl; cout * 魔王语言程序设计 * endl; cout * endl; cout * endl; cout * 本程序可以

19、翻译魔王语言且按以下两条形式规则由人* endl; cout * * endl; cout *的语言逐步抽象上去： * endl; cout * * endl; cout. * endl; cout * * endl; cout * endl; cout * * endl; cout * 下面只输入个第一种形式的规则，且后输入的可以嵌* endl; cout * * endl; cout *套已输入的规则。 * endl; cout * 魔王语言支持下列字符： * endl; cout *a, b, a, d, e, g, i, n, s,t, * endl; cout *x, z, (, )

20、 * endl; cout * endl; cout * endl; cout. / () /下面只输入个第一种形式的规则，且后输入的可以嵌套已输入的规则/*开始输入规则a和b，a比b先输入，再输入b，这样b就可以嵌套a*/ cout以下请开始翻译：endl; cout请先输入一组形式规则：endl; cout; cinml0; cout; cinml1; coutendl;/*输入魔王语言，其规则为大写为魔王语言，只限定a和b（暂时），小写为人类语言，输入时用括号括起来*/ coutleag; char temp100; /定义一个缓冲区，存放b的翻译 int sizea=0; /定义a的长

21、度 sizea=strlen(ml0); int wh=0; /定义缓冲区中的位置变量 for(int i=0;ml1i!=0;i+) /开始翻译b if(ml1i=a) /如果嵌套了a for(int n=0;nsizea;n+,wh+) tempwh=ml0n; /翻译至缓存区 else tempwh=ml1i; /如果不是a则原样写入 wh+; tempwh=0; /为缓存区加上结束符 strcpy(ml1,temp); /把缓存区中的串给ml1 int sizeb=0; /定义b的长度 sizeb=strlen(ml1); int length; length=strlen(leag)

22、; /取得魔王语言的长度 int ch; /定义一个变量保存字符 int a; int b; /*-开始翻译魔王语言，并把结果存至transl中-*/ for(int t=0;tlength;t+) ch=pop(); switch(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

23、=ch; /先把第一个字符存入，后面的从link1开始 while(ch!=) ch=pop(); linkrear=ch; /记得rear的初值为1 rear+; /由于while循环的原因，在link队列中多加了一个右括号字符，且rear指针向后多移了个单位 /故使rear减2 rear=rear-2; translfind+=link0; for(rear;rear!=0;rear-) translfind+=linkrear; translfind+=link0; /为了使后面的翻译可行话，得把rear还原为初值，即rear=1 rear=1; break; default:break

24、; /switch结束/*-翻译魔鬼语言结束，结果已存至transl中-*/ /for结束cout经过翻译，魔王想表达的语言是:; /输出得到的翻译语言是 coutendl; couttransl; coutendl; char *word; word=new char; buildlookuptable(sq); /调用该函数生成字母-汉字对应表 /-输出转换之后的汉字-/ while (transli!=null) *word = transli; coutelemlocateelem(sq, *word).chinese; i+; delete word;char wc; coutwc; return 0;char pop()/出栈函数的实现 return leagtop+; 第五章 运行与测试1.程序调试所注意的事项即遇到的问题1)函数调用。函数的调用是语言中一块十分重要的一部