数据结构课程设计报告参考模板

山东理工大学计算机学院课程设计（数据结构）班级姓名学号指导教师二○一一年一月二十日课程设计任务书及成绩评定课题名称魔王的语言解释Ⅰ、题目的目的和要求：1、设计目的巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。2、设计题目要求：（给出你所选择的题目的要求描述）【问题描述】有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没有人能听懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：（1）α-β1β2……βm（2）（θδ1δ2……δn）—θδnθδn-1……θδ1θ在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话；[基本要求]用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。（1）B-tAdA（2）A-sae[测试数据]B（ehnxgz）B解释成tsaedsaeezegexenehetsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。tdsaezgxnh天地上一只鹅追赶蛋恨[实现提示]将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者思考应如何处理。应首先实现栈和队列的基本操作。Ⅱ、设计进度及完成情况日期内容1.10-1.11选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。1.12~1.14创建相关数据结构,录入源程序。1.17~1.19调试程序并记录调试中的问题，初步完成课程设计报告。1.20~1.21上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。Ⅲ、主要参考文献及资料[1]严蔚敏数据结构（C语言版）清华大学出版社1999[2]严蔚敏数据结构题集（C语言版）清华大学出版社1999[3]谭浩强C语言程序设计清华大学出版社[4]与所用编程环境相配套的C语言或C++相关的资料Ⅳ、成绩评定：设计成绩：（教师填写）指导老师：（签字）二○一一年一月二十一日目录第一章概述……………………………………………………………1第二章系统分析………………………………………………………2第三章概要设计………………………………………………………第四章详细设计………………………………………………………第五章运行与测试……………………………………………………第六章总结与心得……………………………………………………参考文献………………………………………………………………1第一章概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。这次课程设计我选的是魔王语言的解释题目，题目的要求是输入一串字符串（魔王的语言），首先按照要求将其中的大写字母翻译成相应的小写字母，进而按规则翻译成汉字。这种解释翻译也可以用到翻译加密文件的程序之中，也就是把加密的文件相应的转换为原始文件，其中运用到了栈和队列的相关知识第二章系统分析1．输入魔王的语言（一串字符如B（ehnxgz）），解释按照以下规则进行1、（θδ1δ2……δn）—θδnθδn-1……θδ1θ2、B-tAdA3、A-sae解释成一串小写字母（如tsaedsaeezegexenehe），然后转化成对应的汉字（如“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”）。2．大体的过程是先将魔王的语言自左向右依次入队列,然后依次处理队列元素，若遇左括号则将其中元素依次如队列直到遇右括号，然后依次处理括号内的元素。3．程序包括桟的结构定义、初始化、入桟、出桟、判空。队列的结构定义、初始化、入队、出队、判空。主函数中进行语言的翻译。这道题目就是考桟和队列的熟练应用，主要体现在main函数里。5.测试数据。2第三章概要设计本章主要介绍1、数据结构的设计在实验中采用（或设计）的数据结构是桟和队列，因为需要将字符串的字母逐个处理，逆序，插入等操作，用桟和队列比较方便。2、算法的设计本次设计总体分为两个阶段：栈和队列的基本操作，主函数中的翻译解释。思路如下：首先是栈和队列的基本操作。然后主函数中进行翻译解释，先把输入的魔王语言从左至右依次入队列1，按照规则一次将大写字母翻译成小写字母，并小写字母一起输出，若遇到左括号则将左括号后第一个字符记录，按从左至右入栈并每入一个字符后把记录字符入栈之后再依次出栈，把所有小写字母及翻译后的大写字母从左至右依次入队列2。再用switch语句翻译成汉字语言。3、抽象数据类型的设计ADT{voidInitStack(structStack&s)//构造栈voidPush(structStack&s,chare)//元素压桟voidInitQueue(structLinkQueue&q)//构造队voidEnQueue(structLinkQueue&q,chare)//元素入队voidPop(structStack&s,char&e)//元素出桟intStackEmpty(structStacks)//栈是否为空voidDeQueue(structLinkQueue&q,char&e)//元素出队intQueueEmpty(structLinkQueueq)//队是否为空voidMain()//main函数}3第四章详细设计#includeiostream#includestdlib.h#includestring.h#definestack_init_size100#definestackincrement10#defineOVERFLOW0usingnamespacestd;typedefstruct{char*base;char*top;intstacksize;}sqstack;voidInitStack(sqstack&s){//构造空栈s.base=(char*)malloc(stack_init_size*sizeof(char));if(!s.base)exit(OVERFLOW);s.top=s.base;s.stacksize=stack_init_size;}intPush(sqstack&s,chare){//元素入栈if(s.top-s.base=s.stacksize){s.base=(char*)realloc(s.base,stackincrement*sizeof(char));s.top=s.base+s.stacksize;s.stacksize+=stackincrement;}*s.top++=e;return1;}intPop(sqstack&s,char&e){//元素出栈4if(s.base==s.top)return0;e=*--s.top;return1;}intStackEmpty(sqstacks){//判断栈是否为空if(s.top==s.base){return1;}else{return0;}}typedefstructQNode{chardata;structQNode*next;}QNode,*Queueptr;structLinkQueue{Queueptrfront;Queueptrrear;};intInitQueue(LinkQueue&q){//建立空队列q.front=q.rear=(Queueptr)malloc(sizeof(QNode));if(!q.front)exit(OVERFLOW);q.front-next=NULL;return1;}intEnQueue(LinkQueue&q,chare){//元素入队列5structQNode*p;p=(Queueptr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p-data=e;p-next=NULL;q.rear-next=p;q.rear=p;return1;}intDeQueue(LinkQueue&q,char&e){//元素出队列if(q.front==q.rear)return0;structQNode*p;p=q.front-next;e=p-data;q.front-next=p-next;if(q.rear==p)q.rear=q.front;free(p);return1;}intQueueEmpty(structLinkQueueq){//队是否为空if(q.front==q.rear){return1;}else{return0;}}charMoWang[200];intmain()6{cout******************************endl;cout****==魔王语言的翻译程==****endl;cout****==计科0905==****endl;cout****==滕飞==****endl;cout****==0911051180==****endl;cout******************************endl;cout请输入魔王的语言：endl;cinMoWang;sqstackS;LinkQueueQ1;LinkQueueQ2;InitQueue(Q1);InitQueue(Q2);InitStack(S);chare,c,n;inti=0;cout第一次翻译为：;while(MoWang[i]!='\0'){EnQueue(Q1,MoWang[i]);i++;}while(!QueueEmpty(Q1)){DeQueue(Q1,e);if(e!='('){if(e=='B')7couttsaedsae;elseif(e=='A')coutsae;elsecoute;EnQueue(Q2,e);}elseif(e=='('){DeQueue(Q1,c);while(e!=')'){Push(S,c);DeQueue(Q1,e);if(e==')')break;Push(S,e);}while(!StackEmpty(S)){Pop(S,n);if(n=='B')couttsaedsae;elseif(n=='A')coutsae;elsecoutn;EnQueue(Q2,n);}}}coutendl;cout翻译为人类语言为:;8while(!QueueEmpty(Q2)){DeQueue(Q2,e);switch(e){case't':cout天;break;case'd':cout地;break;case's':cout上;break;case'a':cout一只;break;case'e':cout鹅;break;case'z':cout追;break;case'g':cout