数据结构课程设计报告参考模板.docx
- 文档编号:17857680
- 上传时间:2023-08-04
- 格式:DOCX
- 页数:15
- 大小:101.07KB
数据结构课程设计报告参考模板.docx
《数据结构课程设计报告参考模板.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计报告参考模板.docx(15页珍藏版)》请在冰点文库上搜索。
数据结构课程设计报告参考模板
山东理工大学计算机学院
课程设计
(数据结构)
班级
姓名
学号
指导教师
二○一一年一月二十日
课程设计任务书及成绩评定
课题名称
魔王的语言解释
Ⅰ、题目的目的和要求:
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
若将小写字母与汉字建立下表所示的对应关系,则魔王说的话是:
“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。
t
d
s
a
e
z
g
x
n
h
天
地
上
一
只
鹅
追
赶
蛋
恨
[实现提示]
将魔王的语言自右至左进栈,总是处理栈顶字符。
若是开括号,则逐一出栈,将字母顺序入队列,直至闭括号出栈,并按规则要求逐一出队列再处理后入栈。
其他情形较简单,请读者思考应如何处理。
应首先实现栈和队列的基本操作。
Ⅱ、设计进度及完成情况
日期
内容
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.输入魔王的语言(一串字符如B(ehnxgz)),解释按照以下规则进行1、(θδ1δ2……δn)—>θδnθδn-1……θδ1θ2、B->tAdA3、A->sae解释成一串小写字母(如tsaedsaeezegexenehe),然后转化成对应的汉字(如“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”)。
2.大体的过程是先将魔王的语言自左向右依次入队列,然后依次处理队列元素,若遇左括号则将其中元素依次如队列直到遇右括号,然后依次处理括号内的元素。
3.程序包括桟的结构定义、初始化、入桟、出桟、判空。
队列的结构定义、初始化、入队、出队、判空。
主函数中进行语言的翻译。
这道题目就是考桟和队列的熟练应用,主要体现在main函数里。
5.测试数据。
第三章概要设计
本章主要介绍
1、数据结构的设计
在实验中采用(或设计)的数据结构是桟和队列,因为需要将字符串的字母逐个处理,逆序,插入等操作,用桟和队列比较方便。
2、算法的设计
本次设计总体分为两个阶段:
栈和队列的基本操作,主函数中的翻译解释。
思路如下:
首先是栈和队列的基本操作。
然后主函数中进行翻译解释,先把输入的魔王语言从左至右依次入队列1,按照规则一次将大写字母翻译成小写字母,并小写字母一起输出,若遇到左括号则将左括号后第一个字符记录,按从左至右入栈并每入一个字符后把记录字符入栈之后再依次出栈,把所有小写字母及翻译后的大写字母从左至右依次入队列2。
再用switch语句翻译成汉字语言。
3、抽象数据类型的设计
ADT{
voidInitStack(structStack&s)//构造栈void
Push(structStack&s,chare)//元素压桟void
InitQueue(structLinkQueue&q)//构造队void
EnQueue(structLinkQueue&q,chare)//元素入队void
Pop(structStack&s,char&e)//元素出桟int
StackEmpty(structStacks)//栈是否为空void
DeQueue(structLinkQueue&q,char&e)//元素出队intQueueEmpty(structLinkQueueq)//队是否为空void
Main()//main函数
}
第四章详细设计
#include
#include
#include
#definestack_init_size100
#definestackincrement10
#defineOVERFLOW0
usingnamespacestd;
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){//元素出栈
if(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){//元素入队列
structQNode*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()
{
cout<<"******************************"< cout<<"****==魔王语言的翻译程==****"< cout<<"****==计科0905==****"< cout<<"****==滕飞==****"< cout<<"****==0911051180==****"< cout<<"******************************"< cout<<"请输入魔王的语言: "< cin>>MoWang; 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') cout<<"tsaedsae"; elseif(e=='A') cout<<"sae"; else cout< 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') cout<<"tsaedsae"; elseif(n=='A') cout<<"sae"; elsecout< EnQueue(Q2,n); } } } cout< cout<<"翻译为人类语言为: "; while(! 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<<"赶";break; case'x': cout<<"下";break; case'n': cout<<"蛋";break; case'h': cout<<"恨";break; case'B': cout<<"天上一只鹅地上一只鹅";break; case'A': cout<<"上一只鹅";break; default: cout<<"*";break; } } cout< return0; } 第五章运行与测试 1、调试时出现了若干编译错误,根据错误信息修改后通过。 2、测试数据1: 测试数据2: 测试数据3: 第六章总结与心得 刚开始拿到题时候觉得有点难,因为之前写程序的机会不是很多,练得都是纸上的功夫,真正上机实验的机会不多,而且对于这道题有很多地方不懂,但仔细分析后感觉思路还是很明确的。 通过这次课程设计我感觉我对程序设计的兴趣更深了,在其中不但锻炼了程序设计的能力,也培养了兴趣,而且也感觉到了不要知难而退,要勇于克服困难的道理,只要努力用心就没有解决不了的难题。 个人对程序设计的语法使用还不是很熟练,导致第一次写完后出现了各种各样的错误而无法运行,以后这方面应该加强。 参考文献: [1]严蔚敏、吴伟民主编《数据结构》(C语言版)清华大学出版社2002 [2]殷人昆等著《数据结构》(C++版)清华大学出版社2001 [3]金远平著《数据结构》(C++描述)清华大学出版社2005 [4]许卓群等著《数据结构与算法》高等教育出版社2004 [5]FrankM.Carrano等著《数据结构与C++高级教程》清华大学出版社2004 [6]严蔚敏、吴伟民《数据结构习题集》(C语言版)清华大学出版社
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 报告 参考 模板