第一篇：数据结构课程设计报告
青岛理工大学
数据结构课程设计报告
题目：宿舍管理查询软件
院（系）：计算机工程学院
学生姓名:谢茂盛
班级：网络121学号: 201207131
起迄日期:2014.07.07-2014.07.20
指导教师:张艳
一、需求分析（所有大标题宋体加粗四号，下同）（小标题宋体加粗小四，下同）
1.问题描述：
以无歧义的陈述详细说明对自己所选题目的解释性描述，可以补充说明该设计中要做的具体任务。强调的是程序要做什么？
2.基本功能
要求分别列出该设计要实现的功能，（每个功能要尽量和概要设计中的模块函数对应起来）。
二、概要设计
1.设计思路：
解决问题的思路概述，拟采用的算法的简介。
2.数据结构设计：
要求分别列出拟采用的数据结构及其定义，分为逻辑结构（线性？树状？图状？）和存储结构（顺序？链式？）。采用该结构的原因，如果有定义的抽象数据类型，可以列出其定义及各种操作。如下为抽象数据类型定义的模板。
定义程序中用到的抽象数据类型；
设计中所用到的数据结构或抽象数据类型的说明，以及在程序中的作用
抽象数据类型线性表的定义如下：
ADT List{
数据对象：D={ai| ai ∈ElemSet,i=1,2,3……，n,n≥0}
数据关系：R1={
基本操作：
Insert(&L,i,j)
初始条件：线性表L已存在，1≤i≤n+1。
操作结果：在L中第i个位置之前插入新的数据元素j,L的长度加1。
Del(&L,i,j)
初始条件：线性表L已存在，1≤i≤n。
操作结果：删除L的第i个数据元素,L的长度减1
Xg(&L,i,j)
初始条件：线性表L已存在。
操作结果：用新的输入数据项j代替原有的指定要修改的数据项i。
Search(&L,i,e)
初始条件：线性表L已存在。
操作结果：查找指定的某元素i，并将值赋给e,用e 输出。
}
3.软件结构设计：
按需求分析中的功能进行模块划分，建立模块的层次结构及调用关系。
三、详细设计
实现概要设计中定义的所有数据类型，对每个操作只需要写出伪代码算法；对主程序和其他模块也都需要写出伪代码算法（伪代码算法达到的详细程度建议为：按照伪代码算法可以在计算机键盘直接输入高级程序设计语言程序）)；可采用流程图、活动图进行描述，画
出函数和过程的调用关系图。
实现设计中主程序和其他子模块的算法，以流程图的形式表示，需画出函数和过程的调用关系图。
本小节内所有的图均要求用Visio或Word进行绘制，不允许用bmp或其他格式的图片。绘图内文字均采用宋体五号（如果图比较大，排版不好看的话，可以根据需要缩小字体），单倍行间距，段前段后均设置为0行。
1.定义程序中所有用到的数据及其数据结构，及其基本操作的实现；
2．主函数和其他函数的伪码算法；
3.主要函数的程序流程图，实现设计中主程序和其他子模块的算法，以流程图的形式表示。
4.画出函数之间的调用关系图。
四、调试分析
内容包括：调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析。
1.实际完成的情况说明（完成的功能，支持的数据类型等）；
2.程序的性能分析，包括时空分析；
3.上机过程中出现的问题及其解决方案；
4.程序中可以改进的地方说明；
5.程序中可以扩充的功能及设计实现假想。
五、测试结果
列出你的测试结果，包括输入和输出。注意测试数据应该完整和严格，至少给出2组测试结果（含合法数据与非法数据）。
六、用户手册
说明如何使用你编写的程序，详细列出每一步的具体操作步骤。这里可以有适当的运行结果抓图。用户手册与开发过程无关，只与使用有关，必须是Step by Step的。
所有运行结果截图均要求有实际数据的内容，截图尺寸要求按页宽排版两张大小，且要求有每张图下面有规范的标题说明如何使用你编写的程序，详细列出每一步的操作步骤。
七、体会与自我评价
写出本设计的总结思考，收获心得体会，要求不少于600字，不得摘抄网上资料，只能参考。
正文（各标题除外），均采用宋体和Times New Roman字体，小四号字，1.25倍行距。
八、参考文献（列出你参考的书，格式按照下面的例子来写）例如：
[1]严蔚敏．数据结构(C语言)．清华大学出版社，2007
第二篇：数据结构课程设计报告
计算机科学与工程系
数据结构课程设计报告
课程设计题目 迷宫 航班信息查询系统 学 号 姓 名 班 级
专 业 网络工程 完 成 时 间 2013-1-4 指 导 教 师
数据结构课程设计
迷宫
题目一
1.设计内容 1.1问题描述
求迷宫从入口到出口的所有路径。1.2设计要求
1．迷宫中不能使用递归算法查找路径。2．试探方向限定为上、下、左、右四个方向。3．迷宫采用随机生成和手工生成两种方式。4．生成从迷宫入口到出口的最短和最长路径。5．迷宫的入口和出口由键盘输入。
1.3开发环境
Visual C++6.0的集成化环境 1.4研究思路
对这样的矩形迷宫，可以用N*M的矩阵来描述，N和M分别代表迷宫的行数和列数。这样，迷宫中的每一个位置都可以用行号和列号来指定。从入口到出口的路径则是由一个位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居。为了描述迷宫中位置（i,j）处有无障碍，规定：当位置（i,j）处有一个障碍时，其值为1，否则为0。
经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。即所谓的回溯法。
2.设计步骤
2.1 需求分析
（1）题目：迷宫的生成与路由。生成一个N*M（N行M列）的迷宫，0和
1-1数据结构课程设计
迷宫
在该程序中，首先进入的是菜单选择，在菜单中有3种选择，选1是手动输入迷宫函数；选2是随机自动生成迷宫；选3是退出程序。在手动生成迷宫时，有两种输出方式，一是矩阵输出，二是图形输出。在矩阵输出时，直接将数组中的数进行输出，在图形输出时，则要判断该点的情况，然后输入迷宫的出入口，再调用mgpath（）函数进行判断是否存在路径，如果存在则将路径经过的点进行输出，并且将经过的点进入到辅助数组中（辅助数组是辅助图形界面的输出），并且将辅助数组初始为1，辅助数组中点为路径的重新赋值为0，然后根据情况输出图形界面。在自动生成迷宫时，用到了c语言随机函数，对于其它问题，和手动情况基本相同。
2.3 详细设计（1）主菜单伪代码：
while(flag1){
}
{shuru();//输入行列数
printf(“手动建立迷宫矩阵(0表示可通1表示障碍):n”);for(i=1;i<=m;i++)
for(j=1;j<=n;j++)scanf(“%d”,&mg[i][j]);showplay(mg);// 迷宫输出 churukou();//迷宫出入口的输入 x=Mazepath(mg);// 判断路径函数
数据结构课程设计
迷宫
和“class ‘maze’has an illegal zero-sized array”两行错误。双击错误信息，找到出错的程序段，经过查阅资料发现，在利用顺序栈时，没有定义顺序栈的向量空间大小，导致程序出错。但不要对向量空间定义过大，否则会浪费空间。
（2）算法的时空分析：
由于链栈实际上是运算受限制的单链表。所以取栈顶元素运算的算法、置空栈运算的算法执行时间与问题的规模无关，则该算法的时间复杂度为O(1)；而其入栈运算的算法与出栈运算的算法相当于在链表的表尾进行插入和删除操作，不需要移动元素，时间复杂度也为O（1）。建立迷宫矩阵的时间复杂度为O（x*y）。在查找路径的过程中，最坏的情况下可能要考察每一个非障碍的位置。因此，查找路径的时间复杂度应为O（unblocked）。
链栈的入栈算法、出栈算法、取栈顶元素算法、置空栈算法执行时所需要的空间都是用于存储算法本身所用的指令、常数、变量，各个算法的空间性能均较好。只是对于存放顺序栈的向量空间大小的定义很难把握好，如果定义过大，会造成不必要的空间浪费。所以在定义时要慎重考虑。
3.用户使用说明
运行该程序，运行的界面的会出现菜单界面，然后用户可根据界面的提示进行相应的操作，生成迷宫的方式有两种方式，手动生成和自动生成，手动生成时、，用户可根据自己的要求输入迷宫的格式，还需输入相应的入出口，确认程序就会生成相应的路径图形；自动生成只需输入所需的行数和列数，就会生成迷宫，接下来的操作和手动操作相同了。
图数据结构课程设计
迷宫
图1-2
图1-3 退出
5.总结与心得体会
本次课程设计过程中由于掌握的知识不牢固，在编程序的过程中得到了同学的帮助和指导，在此表示感谢。课程设计的过程中，遇到了一些问题，大部分是课本中的知识掌握的不牢固，还有就是在以前学习C++的过程中相关的知识掌握的不够全面。在以后的学习过程中，自己一定要把各种知识掌握牢固。
{ }
mg[i][j]=1;//初始化
矩阵,将最外围置为1
printf(“n输入迷宫入口：n”);scanf(“%d%d”,&x1,&y1);printf(“输入迷宫出口：n”);scanf(“%d%d”,&x2,&y2);
}mlink;mlink *stack;//定义一个栈 int m,n,x1,x2,y1,y2;//定义全局变量
}
void showplay(int mg[][M+2])//迷宫输出
{
n“);
for(i=1;i<=m;i++){
printf(”n“);for(j=1;j<=n;j++)
printf(”%d “,mg[i][j]);
int i,j;
printf(”迷宫矩阵如下(0可通)：printf(“输入行数：n”);scanf(“%d”,&m);printf(“输入列数：n”);scanf(“%d”,&n);数据结构课程设计
迷宫
} } printf(“n迷宫图形如下(白色for(i=1;i<=m;i++){
}
printf(”n“);for(j=1;j<=n;j++){
} if(mg[i][j]==0)printf(”
if(mg[i][j]==1)printf(“
if(mg[stack->row][stack->col+1]==
p->next=stack;
stack=p;{
p=(mlink 可通)：n”);0)//下面位置可通
*)malloc(sizeof(mlink));
p->row=stack->row;p->col=stack->col+1;□“);//为0的输出□ ■”);//为1的输出■
//入栈
mg[stack->row][stack->col]=1;//将
} else
访问过的标记为1 int Mazepath(int mg[][N+2]){
mlink *p;if(mg[x1][y1]==0){ p=(mlink p->row=x1;p->col=y1;p->next=NULL;stack=p;
//将入口
mg[stack->row][stack->col]=1;/while((!(stack->row==NULL&
if(mg[stack->row][stack->col-1]==0)//上面可通
//入栈
stack=p;
p->next=stack;
{
p=(mlink *)malloc(sizeof(mlink));
*)malloc(sizeof(mlink));
p->row=stack->row;p->col=stack->col-1;放入堆栈 /标志入口已访问
&stack->col==NULL))&&(!(stack->row==x2&&stack->col==y2)))//循环条件直到找到输入的出口
{
mg[stack->row][stack->col]=1;//将
访问过的标记为1
数据结构课程设计
迷宫
void tonglu()//将坐标的顶点输出 {
始化
printf(“(%d%3d)n”,q->row,q->col);
情况
else printf(“□”);//0的 } q=stack;{
} for(i=0;i for(j=0;j = while(q!=NULL)//循环条件 q=q->next;for(j=0;j 情况 } void create(int mg[][N+2])//创建和菜单 { int i,j,x,choice,flag1=1;chushi();while(flag1){ } printf(“n”);printf(“所有通道为（由下而q=stack;{ 上）：n”);while(q!=NULL)//循环条件 printf(“ ## printf(”# n“); *********选择菜单********** #n”); printf(“ ## printf(”输入选项：“);scanf(”%d“,&choice);switch(choice){ case 1://手动建立迷宫 { shuru(); printf(”手动建立for(i=1;i<=m;i++) n“); printf(”# 1-手动生成迷 宫 2-自动生成迷宫 3-退出 #n“);0;//将路径中的点赋给辅助数组a 形的界面输出 迷宫矩阵(0表示可通1表示障碍):n”); for(j=1;j<=n;j++)scanf(“%d”,&mg[i][j]); 数据结构课程设计 航班信息查询与检索系统 题目二 1.设计内容 1.1问题描述 设计一个航班信息查询系统，提供信息的管理和使用功能，管理包括更新、添加、删除功能。 1.2设计要求 （1）原始信息存储在文件中，记录不少于50条。（2）用户界面至少包括以下功能： 创建 修改（插入、添加、删除、更新） 查询 浏览 退出管理系统（3）航班信息包括： 航班号：字符序列，具体字符表达的意思上网查询 起点站和终点站：字符串 班期：指一周中哪些天有航班 起飞时间：可将时间定义成一个时、分组成的序列 到达时间：可将时间定义成一个时、分组成的序列 机型：字符序列，具体字符表达的意思上网查询 票价：整型数，具体值可上网查询 （4）创建是指从文件中读取数据，并存入所定义的顺序表中。 （5）可按航班号、起点站、终点站、起飞时间、到达时间等进行查询。查询时要用到顺序查找、二分查找方法。输出查询结果时必须排序。 （6）可按航班号、起点站、起飞时间、票价进行删除和更新操作，删除的记录存入另外的文件中，作为日志文件保存。 （7）作插入操作前，先对信息按起点站进行排序。新记录插入为起点站相同的最后一条记录。 数据结构课程设计 航班信息查询与检索系统 typedef struct node { Time rh;Time lv;}Pnode;（2）飞机结构体： struct Plane { };（3）静态链表： typedef struct Sqlist { int length;struct Plane *plane;char key[10],sted[20],sche[10];Time rh,lv;int price;}Sqlist;2.3 详细设计（1）主函数： do{printf(“* * * * * * * * * * * * * 航班查询系统* * * * * * * * * * * * *n”); printf(“* 1.创建 2.修改 3.查询 4.浏览 5.表长 6.文件 0.退出 *n”); printf(“* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *n”); scanf(“%d”,&opt);switch(opt){ case 1:Initlist(L);break; case 2:handle(L);break; case 3:search(L);break; case 4:print(L);break;case 5:Get_Sq(L);break;case 6:File(L);break; 数据结构课程设计 航班信息查询与检索系统 } }while(opt!=0);} （4）文件操作： void File(Sqlist &L){ int ch;do{ printf(“* * * * * * * * * * * * * * * * * * * * * * * * *n”); printf(“* *n”); printf(“* 1.保存信息到文件 2.从文件读取信息 0 退出 *n”); printf(“* *n”); printf(“* * * * * * * * * * * * * * * * * * * * * * * * *n”); printf(“请输入选项n”); scanf(“%d”,&ch); switch(ch) { case 1:SaveList(L);break; } }while(ch!=0);case 2:ReadList(L);break; case 0:printf(“退出！n”);break;} （5）浏览信息：就是循环使用输出函数，在此就不必多说了 2.4 调试分析 （1）在课设过程中，遇到问题时，通过与同学、老师交流，在图书馆查阅资料，使问题得以解决。 （2）算法中有许多不是很优化的地方。3.用户使用说明 程序运行后用户根据提示输入要进行的操作选项（应先选择创建选项，这样可以直接读取保存好的文件），然后选择要进行的操作选项。由于主菜单中有修改、查询和浏览项目，每个项目又有各自的子菜单，所以在进行管理和使用时要注意输入的元素是否正确，需按照提示输入。输入操作元素时，元素之间以空格隔开。程序将按输入的操作元素找到相应的算法，然后进行处理，然后将结果打 数据结构课程设计 航班信息查询与检索系统 图2-2 查询信息 图2-3插入 图2-4删除 数据结构课程设计 航班信息查询与检索系统 时就需要重新写出一个子函数，哪怕这个子函数就是在原有的一个子函数的基础上改那么一丁点的地方，例如航班信息查询系统中的查询函数，其实每个子函数只是改了一下关键码而已。 6.附录 #include { } void search_key(Sqlist L)//按航班号查找 { 号：“); Time rh;Time lv; scanf(”%s“,n);int i; printf(”此航班的航班号，起点char n[20]; printf(“请输入要查找的航班 printf(”%dn“,L.length);//表长 }Time;typedef struct node { }Pnode;struct Plane { };typedef struct Sqlist { int length;struct Plane *plane;char key[10],sted[20],sche[10];Time rh,lv;int price; 终点，班期，起飞时间，到达时间，票价：n”); if(strcmp(L.plane[i].key,n)==0) ted，L.plane[i].sche,L.plane[i].lv.hour,L.{ for(i=L.length-1;i>=0;i--){ printf(“%s %s %s %d:%d % d:%d %dn”,L.plane[i].key,L.plane[i].s}Sqlist;int get_Sq(Sqlist &L){ } void Get_Sq(Sqlist &L)return L.length; plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane [i].price); 0数据结构课程设计 航班信息查询与检索系统 printf(“此航班的航班号，起点 ted，{ 终点，班期，起飞时间，到达时间，票价：n”); if(L.plane[i].lv.hour<=hour) ted，L.plane[i].sche,L.plane[i].lv.hour,L.{ for(i=L.length-1;i>=0;i--){ printf(“%s %s %s %d:%d % d:%d %dn”,L.plane[i].key,L.plane[i].s L.plane[i].sche,L.plane[i].lv.hour,L.plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane } void search(Sqlist L){ int i;do { printf(“* * * * * * * * * * * } } printf(”%s %s %s %d:%d %d:%d %dn“,L.plane[i].key,L.plane[i].s[i].price);plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane } void search_rh(Sqlist L){ int hour;printf(”请输入你所要求的最scanf(“%d”,&hour);printf(“此航班的航班号，起点 } } [i].price); * * * * * * * * * * * * * ** * * * * * * * * * * * * * * *n”); printf(“* 1.航班号查询 2.起点终点查询 3.班期查询 4.起飞时间查询 5.到达时间查询 0.退出 *n”); printf(“* * * * * * * * * * * * * * * * * * * * * * * * ** * * * * * * * * * * * * * * *n”); scanf(“%d”,&i); switch(i) { case 晚时间：“);终点，班期，起飞时间，到达时间，票价：n”); if(L.plane[i].rh.hour<=hour)for(int i=L.length-1;i>=0;i--){ 1:search_key(L);break; 2数据结构课程设计 航班信息查询与检索系统 n“); } else { } printf(”查找不成功。 i--;if(i==0) { char c[20]; printf(“输入修改后的scanf(”%s“,c); 内容：”); strcpy(L.plane[i].sche,c); printf(“修改成功！n”);}break;{ int a,b; printf(“输入修改后的int opt;printf(”选择修改对象：“);scanf(”%d“,&opt);switch(opt){ case 1: printf(”修改成功！n“);printf(”修改成功！n“);{ char a[10];printf(”输入修改后的scanf(“%s”,a); case 4: 内容：“); char b[20];printf(”请输入修改后scanf(“%s”,b); scanf(“%d:%d”,&a,&b); L.plane[i].lv.hour=a;L.plane[i].lv.min=b;printf(“修改成功！n”);航班号：“); }break;{ int a,b; printf(”输入修改后的strcpy(L.plane[i].key,a);}break;{ case 5: case 2: 内容：“); scanf(”%d:%d“,&a,&b); L.plane[i].rh.hour=a;L.plane[i].rh.min=b;printf(”修改成功！n“);的内容：”);strcpy(L.plane[i].sted,b);}break; }break;{ int a; case 6: case 3: 4数据结构课程设计 航班信息查询与检索系统 *n“); printf(”* * * * * * * * * * * * * * * * * * * * * * * * *n“); printf(”请输入选项n“); scanf(”%d“,&ch); switch(ch) { case 1:SaveList(L);break;case 2:ReadList(L);break; L.plane[i].sche,&L.plane[i].lv.hour，&L.plane[i].lv.min,&L.plane [i].rh.hour,&L.plane[i].rh.min,&L.pl } void delet_Sq1(Sqlist &L){ char n[10];int i,j; printf(”请输入您要删除的航scanf(“%s”,n);if(L.length==0){ printf(“没有选项！n”);for(i=0;i L.length++; ane[i].price); case 0:printf(“退出！n”);break; } void Initlist(Sqlist &L)//插入存储 { “); 容：”);价n“); scanf(”%s%s%s%d:%d%d:%d%d“,L.plane[i].key,L.plane[i].sted, for(i=0;i 班期 起飞时间 到达时间 票scanf(”%d“,&n);L.length=0;L.plane=(Plane if(!L.plane)exit(0);printf(”请输入顺序表中的内 int i,n;printf(“输入表中航班的数量： } }while(ch!=0); 班号：”); if(strcmp(L.plane[i].key,n)==0) { printf(“所删除的班机*)malloc((n+10000)*sizeof(Plane));的信息：n”); printf(“n航班号 起点终点 printf(”%s %s %s %d:%d %d:% d %dn“,L.plane[i].key,L.plane[i].sted，L.plane[i].sche,L.plane[i].lv.hour,L.plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane [i].price); 6数据结构课程设计 航班信息查询与检索系统 n”);} printf(“无法打开文件！} }while(opt!=0); void insert_Sq(Sqlist &L){ 数量 价n”); for(i=0;i printf(“* * * * * * * * * * * scanf(”%s%s%s%d:%d%d:%d%d“,&L.plane[L.length].key,&L.plane[L.length].sted，&L.plane[L.length].sche,&L.plane[ { int a=get_Sq(L); printf(”请输入要添加班机的scanf(“%d”,&n); printf(“请输入要添加的班机printf(”n航班号 起点终点 int i,n; //n表示添加的fprintf(fp,“航班号：%sn起点站：%s 终点站：%sn班期：%dn起飞时间：%d:%d 到达时间：%d:%dn价格：%dnn”, p.key,p.sted,p.sche,p.lv.hour,p.lv.mi n“);} void delet_Sq(Sqlist &L){ int opt;do { fclose(fp);printf(”保存删除的信息成功。n,p.rh.hour,p.rh.min,p.price); 数量：“); 信息：n”); 班期 起飞时间 到达时间 票* * * * * * * * * *n“); printf(”* 1.航班号删除 printf(“* * * * * * * * * * printf(”输入你的选择：“);2.路线删除 0.退出 *n”);* * * * * * * * * * *n“); scanf(”%d“,&opt); switch(opt){ case 1:delet_Sq1(L);break; case 2:delet_Sq2(L);break; case 0:printf(”退出。} L.length].lv.hour,&L.plane[L.length].lv.min，&L.plane[L.length].rh.hour,&L.plan e[L.length].rh.min,&L.plane[L.length].price); } void handle(Sqlist &L){ } L.length++; n");break; 《数据结构》课程设计 哈希表实现电话号码查询系统一目的 利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C++语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。 二需求分析 1、程序的功能 1)读取数据 ① 读取原电话本存储的电话信息。 ② 读取系统随机新建电话本存储的电话信息。2)查找信息 ① 根据电话号码查询用户信息。② 根据姓名查询用户信息。3)存储信息 查询无记录的结果存入记录文档。 2、输出形式 1)数据文件“old.txt”存放原始电话号码数据。 2)数据文件“new.txt”存放有系统随机生成的电话号码文件。3)数据文件“out.txt”存放未查找到的电话信息。4)查找到相关信息时显示姓名、地址、电话号码。 3、初步测试计划 1)从数据文件“old.txt”中读入各项记录，或由系统随机产生各记录，并且把记录保存到“new.txt”中。 2)分别采用伪随机探测再散列法和再哈希法解决冲突。3)根据姓名查找时显示给定姓名用户的记录。4)根据电话号码查找时显示给定电话号码的用户记录。 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 1 《数据结构》课程设计 5)将没有查找的结果保存到结果文件Out.txt中。 6)系统以菜单界面工作，运行界面友好，演示程序以用户和计算机的对话方式进行。 三概要设计 1、子函数功能 int Collision_Random(int key,int i)//伪随机数探量观测再散列法处理冲突 void Init_HashTable_by_name(string name,string phone,string address)//以姓名为关键字建立哈希表 int Collision_Rehash(int key,string str)//再哈希法处理冲突 void Init_HashTable_by_phone(string name,string phone,string address)//以电话号码为关键字建立哈希表 void Outfile(string name,int key)//在没有找到时输出未找到的记录，打开文件out.txt并将记录储存在文档中 void Outhash(int key)//输出哈希表中的记录 void Rafile()//随机生成数据，并将数据保存在new.txt void Init_HashTable(char*fname,int n)//建立哈希表 int Search_by_name(string name)//根据姓名查找哈希表中的记录 int Search_by_phone(string phone)//根据电话号码查找哈希表中的记录 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 2 《数据结构》课程设计 2、函数调用图 main()Refile()init-hashtable()init-hashtable-by-name()init-hashtable-by-phone()Seach-by-name()Seach-by-phone()Coiiision-random()Collision-rehash()Outhash()xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 3 《数据结构》课程设计 四详细设计 1、主函数流程图 开始选择数据来源21建“new.txt”选择查找方式12姓名查找电话号码查找12021输入姓名显示哈希表0显示哈希表输入电话号码无此记录显示信息无此记录显示信息0写入“out.txt”写入“out.txt”结束 2、“伪随机探测再散列处理冲突”伪代码 若对应位置上已经存在其他数据，则新的关键字=（原关键字+伪随机数）%哈希表长。若新的位置上也存在其他数据，则用伪随机序列的下一个数求新的关键字，直到找到合适的位置。 3、“再哈希法处理冲突”伪代码 用“折叠法”将电话号码的ASCII码值定义为关键字，分别为前四位、中四位、后三位。 再用“除留余数法”求的新的关键字=原关键字%哈希表长。 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 《数据结构》课程设计 4、“以姓名为关键字建立哈希表”伪代码 用“除留余数法”将姓名的ASCII码值定义为关键字。 若对应位置上存在其他数据，则调用伪随机处理冲突，然后将数据存入哈希表。 5、“以电话号码为关键字建立哈希表”伪代码 用“除留余数法”将电话号码的ASCII码值定义为关键字。若对应位置上存在其他数据，则调用再哈希处理冲突。然后将数据存入哈希表。 五调试分析 1、程序的关键是掌握文件的相关操作、哈希函数的创建和运用、伪随机法处理冲突、再哈希法处理冲突等。在编程的过程中，出现了很多问题，如文件无法正常打开、程序进入死循环、无法实现文件的写入操作、忘了添加头文件等错误。修改后程序运行正确。 2、创建“new.txt”内容用子函数来实现，但是原数据是从“old.txt”文件中读取的，刚开始不知道怎样实现二者之间的选择，在同学和参考书的帮助下终于得到解决。 3、关于伪随机和再哈希的相关内容觉得很难懂，看了很久参考书才有所了解 六测试结果 1、根据姓名查找 1)姓名查找成功 2)姓名查找失败 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 5 《数据结构》课程设计 3)哈希表 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 6 《数据结构》课程设计 2、根据电话号码查找 1)电话号码输入错误 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 7 《数据结构》课程设计 2)电话号码查询成功 3)电话号码查询失败 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 8 《数据结构》课程设计 4)哈希表 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 9 《数据结构》课程设计 七用户使用说明 1、选择数据来源 根据提示信息进行操作，选择已存在的“old.txt”文件中的数据或系统当前自动生成的“new.txt”文件。 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 10 《数据结构》课程设计 2、选择查找方式 根据提示信息进行操作，选择“根据姓名查找”或“根据电话号码查找”两种查找方式。 3、选择功能 根据提示信息进行操作，选择输入已知信息或查看哈希表。 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 11 《数据结构》课程设计 4、显示结果 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 《数据结构》课程设计 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 13 《数据结构》课程设计 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 14 《数据结构》课程设计 5、查看文件 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 15 《数据结构》课程设计 八课程设计总结 1、收获 学会了C++的跟踪。更进一步了解和熟悉了关于哈希表的运用和文件的读取与写入操作。同时锻炼了对话形式的菜单的创建和熟练运用。 2、心得体会 在这次数据结构设计中遇到了很多实际性的问题，在实际设计中才发现，书本上理论性的东西与在实际运用中的还是有一定的出入的，所以有些问题要不断地更正以前的错误思维。通过这次设计，我懂得了学习的重要性，了解到理论知识与实践相结合的重要意义，xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 16 《数据结构》课程设计 学会了坚持、耐心和努力，这将为自己今后的学习和工作做出了最好的榜样。我觉得作为一名计科专业的学生，这次课程设计是很有意义的。更重要的是如何把自己平时所学的东西应用到实际中。虽然自己对于这门课懂的并不多，很多基础的东西都还没有很好的掌握，觉得很难，也没有很有效的办法通过自身去理解，但是靠着学习，渐渐对这门课逐渐产生了些许的兴趣，自己开始主动学习并逐步从基础慢慢开始弄懂它。 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 《数据结构》课程设计 附录：源程序 #include using namespace std; ifstream in_file;ofstream out_file; int D[10]={1,3,5,8,13,15,17,21,27,34};//伪随机数序列 int count;//当前数据元素个数 int sizeindex;//哈希表的长度 char *sign;//冲突的标志 struct Data { string name;string phone;string address;};Data *intermediate_data; int Collision_Random(int key,int i)//伪随机数探量观测再散列法处理冲突{ int Re_key;if(sign[key]=='1'){ xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 18 《数据结构》课程设计 } Re_key=(key+D[i])%sizeindex;return Re_key;//归回新的要害码 return-1;} void Init_HashTable_by_name(string name,string phone,string address)//以姓名为关键字建立哈希表 { int i=0;int key;char*p;for(key=0,p=&name[0];*p;p++)key=key+*p;key=key%42;while(sign[key]=='1'){ } if(key==-1)exit(1);key=Collision_Random(key,i+1);count++;intermediate_data[key].name=name;//将数据存入哈希表 intermediate_data[key].address=address;intermediate_data[key].phone=phone;sign[key]='1';//设置冲突标志 } xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 19 《数据结构》课程设计 int Collision_Rehash(int key,string str)//再哈希法处理冲突 { int Re_key;int num1=(str[0]-'0')*1000+(str[1]-'0')*100+(str[2]-'0')*10+(str[3]-'0');int num2=(str[4]-'0')*1000+(str[5]-'0')*100+(str[6]-'0')*10+(str[7]-'0');int num3=(str[8]-'0')*100+(str[9]-'0')*10+(str[10]-'0');Re_key=num1+num2+num3;Re_key=(Re_key+key)%sizeindex;return Re_key;} void Init_HashTable_by_phone(string name,string phone,string address)//以电话号码为关键字建立哈希表 { int key;char*p;for(key=0,p=&phone[0];*p;p++)key=key+*p;key=key%42;while(sign[key]=='1'){ } count++;intermediate_data[key].name=name;intermediate_data[key].address=address;intermediate_data[key].phone=phone;key=Collision_Rehash(key,phone);xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 20 《数据结构》课程设计 sign[key]='1';} void Outfile(string name,int key)//在没有找到时输出未找到的记录，打开文件out.txt并将记录储存在文档中 { if((key==-1)||(sign[key]=='0')){ out_file.open(“out.txt”); if(out_file.fail()) { cout<<“n”<<“文件打开失败！!n”< exit(1); } out_file< out_file.close();} } void Outhash(int key)//输出哈希表中的记录 { unsigned i;if((key==-1)||(sign[key]=='0')){ cout<<“n”<<“无此记录！!n”< } else xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 21 《数据结构》课程设计 { for(i=0;i cout< for(i=0;i<8;i++) cout<<“ ”; cout< for(i=0;i<8;i++) cout<<“ ”; cout< void Rafile()//随机生成数据，并将数据保存在new.txt { int i,j;out_file.open(“new.txt”);if(out_file.fail()){ cout<<“n”<<“文件打开失败！!n”< exit(1);} for(j=0;j<30;j++){ string name=“"; for(i=0;i<20;i++) name+=rand()%26+'a';out_file< 《数据结构》课程设计 string phone=”“; for(i=0;i<11;i++) phone+=rand()%10+'0'; out_file< string address=”“; for(i=0;i<29;i++) address+=rand()%26+'a'; address+=','; out_file< void Init_HashTable(char*fname,int n)//建立哈希表{ string name=”“;string phone=”“;string address=”“;int i,j;in_file.open(fname);if(in_file.fail()){ cout<<”n“<<”文件打开失败！!n“< exit(1);} while(!in_file.eof()){ xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 23 《数据结构》课程设计 字 键字 } char* str=new char[100];name=”“;phone=”“;address=”“;in_file.getline(str,100,'n');//按行读入数据 if(str[0]=='*')//判断数据结束 i=0;while(str[i]<=97||str[i]>=122)i++;break;for(;str[i]!=' ';i++)name+=str[i];while(str[i]==' ')i++;for(j=0;str[i]!=' ';j++,i++)phone+=str[i];while(str[i]==' ')i++;for(j=0;str[i]!=',';j++,i++)address+=str[i];if(n==1)Init_HashTable_by_name(name,phone,address);//以姓名为关键else Init_HashTable_by_phone(name,phone,address);//以电话号码为关delete str;in_file.close();} xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 《数据结构》课程设计 int Search_by_name(string name)//根据姓名查找哈希表中的记录 { int i=0;int j=1;int key;char*p;for(key=0,p=&name[0];*p;p++)key=key+*p;key=key%42;while(sign[key]=='1'&&(intermediate_data[key].name!=name)){ key=Collision_Random(key,i+1); j++; if(j=count) return-1;} return key;} int Search_by_phone(string phone)//根据电话号码查找哈希表中的记录{ int key;char*p;for(key=0,p=&phone[0];*p;p++)key=key+*p;key=key%42;int j=1;xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 25 《数据结构》课程设计 while(sign[key]=='1'&&(intermediate_data[key].phone!=phone)){ key=Collision_Rehash(key,phone); j++; if(j=count) return-1;} return key;} void main(){ count=0;sizeindex=50;int i,k;int ch;char *Fname; sign=new char[sizeindex]; intermediate_data=new Data[sizeindex]; for(i=0;i for(i=0;i 《数据结构》课程设计 { } cout<<”§**********************************************************§“< *§”< *§“< *§”< *§“< *§”< *§“< cout<<”§**********************************************************§“< do { switch(k)cout<<”n“<< ” 请输入选择 : n“;cin>>k;cout<<”§* 0.退 出 程 序 cout<<“§* 2.随 机 生 成 cout<<”§* 1.old.TXT cout<<“§* cout<<”§* 请选择用于查找的数据来源 cout<<“§* intermediate_data[i].name=”“;intermediate_data[i].phone=”“;intermediate_data[i].address=”“;xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 27 《数据结构》课程设计 { case 0: return;case 1: Fname=”old.txt“;break;case 2: Rafile();Fname=”new.txt“;break;default: } while((k!=1)&&(k!=2)&&(k!=0)); //system(”cls“); cout<<”§**********************************************************§“< *§”< *§“< *§”< *§“< *§”< cout<<”输入序号有误，请重新输入！!n“< 《数据结构》课程设计 *§”< cout<<”§**********************************************************§“< //system(”cls“); endl; *§”< } while((ch!=1)&&(ch!=2));cout<<”n“<< ” 请输入选择 : n“;cin>>ch;if(ch!=1&&ch!=2){ } cout<<” 输入序号有误，请重新输入！!n“< 《数据结构》课程设计 *§”< cout<<”§* *§“< *§”< *§“< *§”< *§“< cout<<”§**********************************************************§“< do { cout<<”n“<< ” 请输入选择 : n“; cin>>choice;cout<<”§* cout<<“§* 0.退 出 程 序！!cout<<”§* 2.显 示 哈 希 表 cout<<“§* 1.输 入 姓 名 查 找 数 据 switch(choice){ case 1: { int key1;string name; cout<<”n“<<” 请输入姓名: n“; cin>>name; key1=Search_by_name(name);xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 30 《数据结构》课程设计 Outfile(name,key1);cout<<”n“<<”查找结果:n“< Outhash(key1); } break; case 2: { cout<<”n“<<” 哈希表: n“< for(i=0;i { if(sign[i]!='0') { cout<<”* “; Outhash(i); } } cout<<”* *“< } break; case 0: return;default: xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 31 《数据结构》课程设计 cout<<” 输入序号有误，请重新输入！!n“< endl; *§”< *§“< *§”< *§“< *§”< *§“< cout<<”§**********************************************************§“< cout<<”n“<< ” 请输入选择 : n“; } } } while((choice!=1)&&(choice!=2)&&(choice!=0)); while(ch==2){ int choice; cout<<”§**********************************************************§“< cout<<”§* 1.输 入 电 话 查 找 数 据 cout<<“§* 2.显 示 哈 希 表 cout<<”§* 0.退 出 cout<<“§* do { xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 《数据结构》课程设计 cin>>choice; switch(choice) { case 1: { int key2; string phone;do { cout<<”* 请输入11位的电话号码: “; cin>>phone; if(strlen(&phone[0])!=11) { cout<<”n“<<”电话号码输入不正确!请重新输入！!n“< key2=Search_by_phone(phone);Outfile(phone,key2); } while(strlen(&phone[0])!=11);cout<<”n“<<”查找结果:n“< cout<<”* “; xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 《数据结构》课程设计 Outhash(key2); } break; case 2: { cout<<”n“<<”哈希表:n“< for(i=0;i { if(sign[i]!='0') { cout<<”* “; Outhash(i); } } cout<<”* *“< } break; case 0: return; default: cout<<” 输入序号有误，请重新输入！!n"< 《数据结构》课程设计 } while((choice!=1)&&(choice!=2)&&(choice!=0)); } } xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 35 《数据结构》 课程设计报告 目录 《数据结构》...................................................................................................................................1 课程设计报告...................................................................................................................................1 目录..................................................................................................................................................2 课题一：表达式求值.......................................................................................................................3 一：算数表达式后缀版...........................................................................................................3 1、问题描述：.................................................................................................................3 2、设计思路：.................................................................................................................3 3、程序代码：.................................................................................................................3 4、运行与测试.................................................................................................................6 5、设计心得：.................................................................................................................6 二：算术表达式中缀版...........................................................................................................7 1、问题描述：.................................................................................................................7 2、设计思路：.................................................................................................................7 3、代码：.........................................................................................................................7 4、调试及测试...............................................................................................................13 5、设计心得：...............................................................................................................13 课题四：迷宫求解.........................................................................................................................14 一：问题描述：.............................................................................................................14 二：设计思路：.............................................................................................................14 三：功能函数设计.........................................................................................................14 四：代码.........................................................................................................................14 五：测试及调试.............................................................................................................21 六：设计心得.................................................................................................................23 课题一：表达式求值 一：算数表达式后缀版 1、问题描述：一个算术表达式是由操作数、运算符和界线符组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界线符有左右括号和表达式起始、结束符“#”，如：“1285-*+42/-#”。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。 2、设计思路：在C++环境下，用字符数组A，保存算数式，一“#”表示结束。用栈对数字和运算符号进行操作。当扫描A不是‘#’时，判断数组成员是数字还是字符，若数字，则将数字的ASCII码入栈，若不是，则弹出两个数字，并根据字符进行相应的运算，并将结果入栈保存，以便下一次的运算操作。 3、程序代码： #include base=new int[Size]; top=base; size=Size;};~stack(){ delete[] base; base=NULL; top=NULL;};};int stack::empty_stack(){ return((top==base));} int stack::push_stack(int e){ if(top-base *top=e; top++; return 1;} else return 0;} int stack::pop_stack(int &e){ if(top>base){ top--; e=*top; return 1;} else return 0;} int stack::get_stack(int &e){ if(top>base){ e=*(top-1); return 1;} else return 0;} int match(char A[]){ stack s;int i=0,x,y,z;while(A[i]!='#'){ while(A[i]>'0'&&A[i]<='9')//char型 A[],其中0~9存储的是48~57！！! { s.push_stack(A[i]-'0');//存储 数字0~9 char-char i++; } if(A[i]<'0'||A[i]>'9') { s.pop_stack(x); s.pop_stack(y); switch(A[i]) { case '+':s.push_stack(x+y);break;//switch,case 'ch'的用法 case '-':s.push_stack(x-y);break; case '*':s.push_stack(x*y);break; case '/':s.push_stack(x/y);break; } } i++;} s.pop_stack(z);printf(“%dn”,z);return z;} int main(){ char A[100];int m;scanf(“%s”,A);m=match(A);printf(“%dn”,m);return 0;} 4、运行与测试 5、设计心得：考察栈的应用，在c++环境下栈的构建与操作，在输入数组A时（用于存放数组），注意当数组元素是数字时，将A[i]-’0’，（ASCII码）作为栈相应函数的参数。后缀表达式还是相应比较简单的。 二：算术表达式中缀版 1、问题描述：一个算术表达式是由操作数、运算符和界线符组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界线符有左右括号和表达式起始、结束符“#”，如：“1285-*+42/-#”。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。 2、设计思路：在C++环境下，在后缀表达式的基础上，增加将中缀转换为后缀存储的算法。自左向右扫描表达式，当扫描到的是操作数时直接输出，扫描到运算符时不能马上输出，因为后面可能还有更高的运算；若运算符栈栈顶字符比这个字符低，则入栈，继续向后处理；若高，则从运算符栈出栈一个运算符输出，继续处理当前字符；若相等，则为括号，从栈中出栈，继续向后处理，直到遇到字符’#‘，求值结束。例如：“1+2*（8-5）-4/2#”。 3、代码： #include base=new int[Size]; top=base; size=Size;};~stack(){ delete[] base; base=NULL; top=NULL;};};int stack::empty_stack(){ return((top==base));} int stack::push_stack(char e){ if(top-base *top=e; top++; return 1;} else return 0;} int stack::pop_stack(char &e){ if(top>base){ top--; e=*top; return 1;} else return 0;} int stack::get_stack(char &e){ if(top>base){ e=*(top-1); return 1;} else return 0;} class temp { private: int *base;int *top;public: int size;int empty_temp();int push_temp(int e);int pop_temp(int &e);int get_temp(int &e);temp(int Size=100){ base=new int[Size]; top=base; size=Size;};~temp(){ delete[] base; base=NULL; top=NULL; };};int temp::empty_temp(){ return((top==base));} int temp::push_temp(int e){ if(top-base *top=e; top++; return 1;} else return 0;} int temp::pop_temp(int &e){ if(top>base){ top--; e=*top; return 1;} else return 0;} int temp::get_temp(int &e){ if(top>base){ e=*(top-1); return 1;} else return 0;} char fhcg(char a,char b)//#不能传进a { int i,j;char h;char CH[7]={'+','-','*','/','(',')','#'};char R[7][7]={{'>','>','<','<','<','>','>'}，{'>','>','<','<','<','>','>'}，{'>','>','>','>','<','>','>'}，{'>','>','>','>','<','>','>'}，{'<','<','<','<','<','=','/'}，{'>','>','>','>','/','>','>'}，{'<','<','<','<','<','/','='}};for(i=0;i<7;i++){ if(CH[i]==a) break;} for(j=0;j<7;j++){ if(CH[j]==b) break;} h=R[i][j];return(h);} int matchcg(char A[],char B[])// { stack s;char h,x,y;int i,j;i=0;j=0;s.push_stack('#');//#没传入 // s.get_stack(y);//cout<<“栈顶”< while(!s.empty_stack())//最后的-4/2有问题，/没进入B[j] { if(A[i]>'0'&&A[i]<='9') { B[j]=A[i]; j++; i++; } else//(A[i]<'0'||A[i]>'9') { s.get_stack(y); // s.pop_stack(x);// h=fhcg(y,A[i]);// switch(h) { case '>': { s.pop_stack(x); B[j++]=x;//x没有下移，还是‘-’只有这一步把数据压入B，j++ break;/////////// } case '<':s.push_stack(A[i]);i++;break; case '=':s.pop_stack(x);i++;break; default: return 0; } } } B[j]='#';//B[]由j控制进程 B[++j]=' ';// printf(“%sn”,B);return 1;} int matchfn(char A[]){ temp s;int i=0;int n,x,y,z;n=strlen(A);//printf(“n=%dn”,n);// printf(“%sn”,A);while(A[i]!='#')//！！！！!{ if(A[i]>'0'&&A[i]<='9')//char型 A[],其中0~9存储的是48~57！！! { s.push_temp(A[i]-'0');//存储 数字0~9 char-char i++; } else//(A[i]<'0'||A[i]>'9') { s.pop_temp(x); s.pop_temp(y); switch(A[i]) { case '+':s.push_temp(y+x);break;//switch,case 'ch'的用法 case '-':s.push_temp(y-x);break; case '*':s.push_temp(x*y);break; case '/':s.push_temp(y/x);break; } i++; } } s.pop_temp(z);return z;} int main(){ //char A[100]={“1+2*(8-5)-4/2#”};char A[100];printf(“A[]=以#结束:”);scanf(“%s”,A); } char B[100];int m,n,i=0;m=matchcg(A,B);m=matchfn(B);printf(“%s”,A);printf(“=%dn”,m);return 0; 4、调试及测试 5、设计心得： 中缀算法是在后缀的基础上，增加了处理，是的中缀在栈的存储中为后缀，然后只用后缀的算法运算。最容易忽略的是字符数组处理是的’ ‘问题，所以加上了B[j]='#';B[++j]=' ';在int matchcg(char A[],char B[])函数后。课题四：迷宫求解 一：问题描述：设二维数组maze[m][n]为’0‘，表示此路可通,为’1‘表示此路不通.入口是maze[1][1]出口为maze[m][n]且maze[1][1]=0, maze[m][n]=0.编写寻找从入口到出口的一条路径的程序。必须沿4个方向搜索.二：设计思路：回溯法，从入口出发，按某一方向探索，若能走通并未走过（maze[i][j]==0），即该处可以到达，并标记为已走过（maze[i][j]=-1），并入栈保存前一步到达的位置，否则探索下一个方向（d++）；若所有的方向均没有通路，则按原路返回前一步到达的位置，换下一个方向继续探索，直到找到一条同路。 三：功能函数设计 typedef struct _Befor//前一点的坐标方向 typedef struct//链栈 void play(Befor temp)//temp void play(Befor temp)//temp用于实现在DOS下的界面显示 typedef struct MOVE和typedef struct _Path//用于计算四个方向的位移量 int Export(int(*maze)[10],int x0,int y0,int m,int n,PStack s)//用于探索迷宫寻找出路 四：代码 //用c表示栈 //改进，加入动态演示（子弹打飞机） //最重大的错误，ij的位置反了，i是行，对应的是y坐标；j是列，对应的是x坐标。#include 0x48 #define Down 0x50 #define Left 0x4b #define Right 0x4d #define Esc 0x1b void gotoxy(int x, int y)//光标移到（x,y）friend函数（COORD,HANDLE）屏幕宽80、高25 { COORD point;// 创建光标位置坐标。COORD类（x,y） HANDLE hOutput = GetStdHandle(STD_OUTPUT_HANDLE);// 控制台屏幕缓冲区的把手。HANDLE类 point.X = x;point.Y = y; SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),point);//设置控制台光标位置 } void clear(int left,int top,int width,int higth)//！！!{ //函数消除轨迹 gotoxy(left,top);for(int i=0;i<=width;i++) for(int j=0;j<=higth;j++) { gotoxy(left+i,top+j); cout<<“ ”< } } void sound(DWORD freq)//按freq HZ频率发声（50ms）{ Beep(freq,50);} void delay(DWORD dur)//延时dur毫秒 { Sleep(dur);} //////正文 typedef struct _Befor { int x,y,d;}Befor;//前一点的坐标方向 typedef struct//链栈 { int top;Befor Node[100];//结构体每一个都是Befor型 }Stack,*PStack;//初始化栈 PStack Inite_Stack(){ PStack s;s=(PStack)malloc(sizeof(Stack));if(s){ s->top=-1;} return s;} int empty_Stack(PStack s){ return(s->top==-1);//s.top==0即为空 } int push_Stack(PStack s,Befor temp){ if(s->top==MAX-1)//限定了栈的容量 return 0;else { s->top++; s->Node[s->top]=temp; return 1;} } int pop_Stack(PStack s,Befor &temp){ if(empty_Stack(s)) return 0;else { temp=s->Node[s->top]; s->top--; return 1;} } int get_Stack(PStack s,Befor &temp){ if(empty_Stack(s))return 0;else { temp=s->Node[s->top]; return 1;} } void play(Befor temp)//temp { delay(500);clear(20+temp.y+temp.y*3,5+temp.x+temp.x*3,1,1);gotoxy(20+temp.y+temp.y*3,5+temp.x+temp.x*3);printf(“$”);} ////////////////////////////////////////栈完成 //迷宫点的设计，保存的坐标，保存前一点的坐标（方向），此点的四个方向坐标 //加入难度，也就是迷宫复杂化，1出现在中间区域。/*typedef struct _Befor { int x,y,d;}Befor;//前一点的坐标方向*/ typedef struct MOVE { int dx,dy;}move;typedef struct _Path { move x,y;}Path;int Export(int(*maze)[10],int x0,int y0,int m,int n,PStack s)//二维数组做实参形参 {//(x0,y0)起始点,(m,n)将要到达的点 Befor temp;int i,j,x,y,d;struct MOVE move[4];move[0].dx=-1;//位置错误。向上i-1;向左j+1;向下i+1;向左j-1;！！！！！！！move[0].dy=0;move[1].dx=0;move[1].dy=1;move[2].dx=1;move[2].dy=0;move[3].dx=0;move[3].dy=-1;//栈初始化temp(x,y,d),入栈 temp.x=x0;temp.y=y0;temp.d=-1;push_Stack(s,temp);while(!empty_Stack(s)){ pop_Stack(s,temp);//出栈，存储为之前的点 x=temp.x;y=temp.y;d=temp.d+1;while(d<4)//四个方向转换 { i=x+move[d].dx;//一直是1 j=y+move[d].dy;//当前点坐标y值不对，一直增长 if(maze[i][j]==0)//当前的可走 改变了，maze[i][j]没变 { temp.x=x; temp.y=y; temp.d=d; push_Stack(s,temp);//入栈保存 //加入动态（temp） play(temp);// x=i; y=j; maze[x][y]=-1;//记录当前点已走过 if(x==m&&j==n)//已走出则输出路径 { temp.x=x; temp.y=y; temp.d=d; push_Stack(s,temp);//入栈保存最后一个点，出口点///////////////////// //加入动态（temp） play(temp);///////////// gotoxy(0,2); while(!empty_Stack(s)) { pop_Stack(s,temp);///////////////////////// printf(“(%d,%d,%d)t”,temp.x,temp.y,temp.d);//没有改变！！!正确 } for(i=x0;i<=m;i++)//复位迷宫 for(j=y0;j<=n;j++) { if(maze[i][j]==-1) maze[i][j]=0; } return 1;//已成功 } else d=0; } else d++; } } //空栈后，恢复迷宫 for(i=x0;i<=m;i++)//复位迷宫 for(j=y0;j<=n;j++) { if(maze[i][j]==-1) maze[i][j]=0; } return 0;//失败 } //迷宫的初始化maze[m+2][n+2] int main(){ int maze[10][10];int m,n,i=0,j=0;char c_0;int nx,ny;PStack s=Inite_Stack();printf(“迷宫的规格：”);scanf(“%d%d”,&m,&n);gotoxy(20,5);//通过键盘控制迷宫中间区域 for(i=0;i for(j=0;j { maze[i][j]=1; gotoxy(20+i+3*i,5+j+3*j); printf(“1”); } for(i=1;i<=m;i++) for(j=1;j<=n;j++) { maze[i][j]=0; gotoxy(20+i+3*i,5+j+3*j); printf(“0”); } gotoxy(3,0);printf(“请修改迷宫，增加难度。n”);printf(“输入0为此位置可行，输入1为此位置不可行。请不要修改外部。n”); } printf(“向上;向左;向右；向下n”);nx=20;ny=5;gotoxy(20,5);c_0=getch();while(c_0!='q')//增加改错了，改为0的选项 { switch(c_0){ case Esc:break;case Up:ny--; gotoxy(nx,ny); break;case Left:nx--; gotoxy(nx,ny); break;case Down:ny++; gotoxy(nx,ny); break;case Right:nx++; gotoxy(nx,ny); break;case '1':j=(nx-20)/4; i=(ny-5)/4; maze[i][j]=1;// delay(100); clear(nx,ny,1,1); gotoxy(nx,ny); printf(“%d”,maze[i][j]);// break;case '0':j=(nx-20)/4; i=(ny-5)/4; maze[i][j]=0;// delay(100); clear(nx,ny,1,1); gotoxy(nx,ny); printf(“%d”,maze[i][j]);// break; } c_0=getch();} Export(maze,1,1,m,n,s);return 0;20 五：测试及调试 1、初始化迷宫及操作提示 2、增加难度修改迷宫 3、运行结果 22 六：设计心得 1、最麻烦的是几个结构体之间的关联，比如“typedef struct//链栈中{Befor Node[100];}//结构体每一个都是Befor型”；“typedef struct _Path// {move x,y;}”move类型的变量x，y。 2、还有四个位移的变化（move[d].dx,move[d].dy）他的变化是与i,j的位置的变化相关的。 3、迷宫的探索中，一但按某一方向探索，若能走通并未走过（maze[i][j]==0），即该处可以到达，并标记为已走过（maze[i][j]=-1），并入栈保存前一步到达的位置，这是值得注意的，因为可能返回，要保存前面的位置。 4、界面的设计以及增加迷宫复杂性时，更改迷宫位置是的处理，也是要注意的。 数据结构课程设计 散列表的应用:插队买票 专业 计算机科学与技术（网络技术） 金玲 计算机131 1310704114 张静林 2015年1月23日 学生姓名 班学级 号 指导教师 完成日期 目录概述……………………………………………………………………………………1 1.1 课程设计目的……………………………………………………………………….1 1.2 课程设计内容……………………………………………………………………….1 2 系统需求分析……………………………………………………………………….1 2.1 主体功能…………………………………………………………………………....2 3系统概要设计…………………………………………………………………………2 3.1 系统流程图………………………………………………………………………….2 4 系统详细设计…………………………………………………………………………3 5 测试……………………………………………………………………………………5 5.1 测试方案…………………………………………………………………………….5 5.2 测试结果…………………………………………………………………………….5 6 小结……………………………………………………………………………………5 参考文献…………………………………………………………………………………5 附录………………………………………………………………………………………7 附录1 源程序清单……………………………………………………………………...7 概述 1.1 课程设计目的 数据结构课程设计是为数据结构课程独立开设的实践性教学环节。数据结构课程设计对于巩固数据结构知识，加强学生的实际动手能力和提高学生综合素质是十分必要的。课程设计的目的： 1．要求学生达到熟练掌握C语言的基本知识和技能。 2．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。3．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 4．培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。 5．初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。 1.2课程设计内容 本课程设计的任务是写一个程序模拟这种情况。每个队伍都允许插队。如果你在排队，有一个以上的朋友要求插队，则你可以安排他们的次序。每次一个人入队，并且如果这个入队的人发现队伍中有自己的朋友，则可以插入到这个朋友的后面；当队伍中的朋友不止一个的时候，这个人会排在最后一个朋友的后面；如果队伍中没有朋友，则他只能够排在这个队伍的最后面。每一个入队的人都先进行上述的判断。当队伍前面的人买到车票之后，依次出队。系统需求分析 2.1 主体功能 程序从“input.txt”文件读入测试用例，一个文件可包含多个测试用例。每个用例的第一行是朋友组的数目n（1<=n<=1000)。对于一个朋友组以朋友的数目j（1<=j<=1000）开始，由朋友的个数以及他们的名字组成，一个空格后接该组朋友的名字，以空格分开，并且每个人的名字都不同。每个名字不超过四个字母，由{A，B，...，Z，a，b，...，z}组成。一个朋友组最多有1000个人，每个人只属于一个朋友组。n=0时，测试数据结束。 下面是一些具体命令：.ENQUEUE——X入队;.DEQUEUE——排队头的人买票，离开队伍，即出队；.STOP——一个测试用例结束。 测试结果输出到“output.txt”文件中。每个测试用例第一行输出“Scenario#k”，k是测试用例的序号（从1开始）。对每一个出队命令，输出刚买票离开队伍的人名。两个测试试用例 之间隔一空行，最后一个用例结束不输出空行。系统概要设计 3.1 系统流程图 系统详细设计 本题目主要解决两个问题：一是怎么存放和查找大量数据（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。 用散列表来存放和查找数据。由于最多有1000个朋友组，每组最多有1000人，使用平方探测法解决冲突，则表的大小是2*（1000*1000），所以选择TableSize=2000003（2000003是大于2000000的最小素数）。同一个组内的都是朋友，所以每个人除了记录他的名字name，还要记录他属于哪个组group，另外用info来表示该单元是否被占用，数据结构如图4.1所示。散列函数是根据Honer法则计算一个以64为阶的多项式，如图4.2所示。冲突解决方法采用平方探测法，如图4.3所示。 #define TabSize 2000003 typedef struct hashtab *PtrToHash;struct hashtab /*散列表数据结构*/ { char name[5]; /*名字*/ int group; /*属于哪个朋友组*/ char info; /*标志位，该单元是否被占用*/ };图4.1数据结构：散列表 Int Hash(char *key,int TableSize){ Int HashVal=0; While(key!=NULL) HashVal=(HashVal<<6)+*key; Return HashVal%TableSize;} 图4.2散列函数 Long int Find(PtrToHash hash,char *c){ key=c; CurrentPos=Hash(key,TableSize); CollisionNum=0; While((单元被占用)and(单元内的名字与查找的名字不同)) { CurrentPos+=2*(++CollisionNum)-1; If(CurrentPos>=TabSize) CurrentPos=TabSize; } Return CurrentPos;} 图4.3用平方探测法解决冲突 第二个问题是关于怎么操作“ENQUEUE”和“DEQUEUE”命令。这可以用队列来模拟。由于有插队现象的存在，不能单纯的用一个数组来表示队列，因为这样的话，插入一个朋友，则他后面的人都要往后移一个单位，删除一个人，则他后面的人都要前移一个，会降低效率。所以，采用一个Index标记来表示当前元素的后继元素，最后一个单元的后继元素是第0个，形成环，数据结构如图4.4所示。不用链表是因为链表存放指针也需要空间，并且链表插入、删除的效率没有数组高。 typedef struct Que *PtrToQue;struct Que /*队列数据结构*/ { long int HashVal; /*散列值*/ long int Index; /*在中的队列序号*/ };图4.4数据结构：队列 输入ENQUEUE命令，如果队伍里有朋友，则排在朋友后面；如果没有朋友，则排在队尾。入队时，用一个数组记录每个朋友组的最后一位，以便下一个朋友到来时排到他后面，这个数组被称为“插队数组”。 输入DEQUEUE命令，则根据“先进先出”，按照各个元素和它后继元素的先后顺序，每次删除队列重的第一个。程序结构如图4.5所示。 While(读测试文件){ if(输入”ENQUEUE”) { 读入名字； 插入散列表； 插入队列； } else if(输入”DEQUEUE”) { 删除队列第一个名字； 将该名字输出到文件； } else stop;} 图4.5入队、出队操作 测试 5.1 测试方案 按输入要求输入正常测试数据，测试程序是否能正确解决问题，得到正确答案。应注意边界测试。例如，将n，j分别取为1的用例和n为1000的用例。n，j比较大时需写程序生成测试用例。 不按输入要求输入数据，测试程序能否对输入内容进行数据合法性检测并进行相应的异常处理。例如，将n或j取为小于1或大于1000的数，名字超过4个字母等情况下的测试用例。5.2 测试结果 小结 在前面的学习过程中我们学到了很多知识而这次课程设计又是对我们所学的 一次总结，刚开始，可以说是没有头绪，于是就去图书馆找资料，找到了一些关于程序方面的，可这远远不够，这只是小小的开始。我们必须掌握很多已学的知识才能很好的完成本次的课程设计。在这次课程设计中，总的感觉是我遇到了很多困难这主要是由于我编写代码的经验不足，有时虽然是一个很小的问题但解决起来却花费了我不少的时间，值得欣慰的是，当自己苦思冥想或者和其它同学一起探讨把问题解决的时候我还是觉得获益非浅，这就是在摸索中寻求到的知识。在设计时也免不了存在着些不足，所以在今后的学习中我会努力取得更大的进步。虽然对着电脑做程序，有些累，可当看到劳动成果时，却有另一番滋味。 参考文献 [1]范策，周世平，胡晓琨.《算法与数据结构（C语言版）》[M].北京：机械工业出版社，2004 [2]严蔚敏.《数据结构（C语言版）》.北京：清华大学出版社，2004 [3]许卓群，杨冬青，唐世渭，张铭.《数据结构与算法》.北京：高等教育出版社，2004 [4]徐孝凯.《数据结构实用教程（第二版）》.北京：清华大学出版社，2006 附录 附录1 源程序清单 #include /*散列表大小TabSize 是大于表最大空间的素数*/ #define Max 1000001 /*队列空间最大值*/ struct hashtab;typedef struct hashtab *PtrToHash;struct hashtab /*散列表数据结构*/ { char name[5]; /*名字*/ int group; /*属于哪个朋友组*/ char info; /*标志位，该单元是否被占用*/ };struct Que;typedef struct Que *PtrToQue;struct Que /*队列数据结构*/ { long int HashVal; /*散列值*/ long int Index; /*在中的队列序号*/ }; int hashedx=0; /*标记元素是否已经在散列表里*/ long int Find(PtrToHash hash,char *c)/*查找在散列表中的位置*/ { char *key;long int CurrentPos,CollisionNum; key=c;for(CurrentPos=0;*key;++key) /*散列函数，计算散列值*/ CurrentPos=(CurrentPos<<6)+*key;CurrentPos%=TabSize; /*散列值*/ CollisionNum=0;/*如果当前单元被占用：单元内的元素与当前操作的名字不同，使用平方探测法解决冲突；与当前操作的名字相同，则直接返回在散列中的位置*/ while((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c))) { /*平方探测法*/ CurrentPos+=2*(++CollisionNum)-1; if(CurrentPos>=TabSize) CurrentPos-=TabSize;} if((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)==0)) /*元素已经在散列表里*/ hashedx=1;else /*元素不在散列表里*/ hashedx=0;return CurrentPos;/*返回在散列表中的位置*/ } int main(){ long int Find(PtrToHash hash,char *c); /*查找在散列表中的位置*/ PtrToHash hash; /*散列表*/ PtrToQue queue; /*队列*/ int *grouppos; /*记录每个朋友组的最后一位，即插队数组*/ int n; /*测试用例数目*/ int num; /*当前测试用例序号*/ long int i,ii,j,key,temp;long int head,last; /*队列的头和尾*/ char c[8],tempc[8]; /*名字*/ FILE *fpin,*fpout; /*输入、输出文件指针*/ if(!(fpin=fopen(“input.txt”,“r”))) /*打开测试文件*/ { printf(“fopen error!”); /*文件打开错误*/ return-1;} if(!(fpout=fopen(“output.txt”,“w”))) /*打开输出文件*/ { printf(“fopen error!”); return-1;} hash=(PtrToHash)malloc(sizeof(struct hashtab)*TabSize);/*为散列表申请空间*/ queue=(PtrToQue)malloc(sizeof(struct Que)*Max);/*为队列申请空间*/ grouppos=(int *)malloc(sizeof(int)*1000);/*申请空间记录每个朋友组的最后一位*/ for(i=0,j=1;i queue[i].Index=j;queue[i-1].Index=0;/*最后一个单元的后继单元是第0个，形成环*/ num=0;for(fscanf(fpin,“%d”,&n);n;fscanf(fpin,“%d”,&n))/*输入当前测试用例的朋友组数*/ { if(n<1||n>1000) /*处理异常输入n*/ { fprintf(fpout,“n is out of rangen”); return-1; } num++; if(num!=1) /*两个测试用例间输入一空行*/ fprintf(fpout,“n”); for(i=0;i hash[i++].info=0; /*初始化散列表，标记位置0*/ for(i=0;i /*对每一组朋友*/ { fscanf(fpin,“%d”,&j); /*当前组里的人数*/ if(j<1||j>1000) /*处理异常输入j*/ { fprintf(fpout,“j is out of rangen”); return-1; } for(;j;--j) { fscanf(fpin,“%s”,c); /*输入名字*/ for(ii=0;ii tempc[ii]=' '; strcpy(tempc,c); ii=0; while(tempc[ii]!=' ') /* 是否由四个以内字母组成*/ { if(tempc[ii]<'A'||('Z' { fprintf(fpout,“Group %d: Nonstandard namen ”,i); return-1; } ii++; } key=Find(hash,c); /*找到在散列表中的位置*/ if(hashedx==1)/*重名*/ { fprintf(fpout,“repeated name %sn”,c); return-1; } strcpy(hash[key].name,c);/*插入散列表*/ hash[key].info=1; /*标记置1，该单元被占用*/ hash[key].group=i; /*记录他属于哪个组*/ } } for(i=0;i<1000;) grouppos[i++]=0;/*初始化插队数组*/ head=0; /*初始化队列头、尾标记*/ last=0;fprintf(fpout,“Scenario #%dn”,num);/*输出当前用例序号到文件*/ for(fscanf(fpin,“%s”,c);;fscanf(fpin,“%s”,c))/*输入命令*/ { if(*c=='E') /*入队命令*/ { fscanf(fpin,“%s”,c); /*输入名字*/ key=Find(hash,c); /*查找在散列表中的位置*/ if(hashedx==0)/*散列表里没这个人*/ { fprintf(fpout,“no %sn”,c); return-1;} temp=queue[0].Index; /*队列第0个位置记录队尾的后继单元*/ queue[0].Index=queue[temp].Index; /*在队列中申请一个新单元，队尾标记后移一个位置 */ queue[temp].HashVal=key;/*入队*/ if(!head)/*如果是队列里的第一个元素 */ last=head=temp;/*队头、队尾标记指向第一个元素*/ if(!grouppos[hash[key].group])/*如果队列里没朋友*/ { queue[temp].Index=0;/*队尾指向对头，形成环*/ queue[last].Index=temp;/*前一次队尾的后继元素是当前元素*/ last=temp; /*队尾标记指向当前元素*/ grouppos[hash[key].group]=temp;/*插队数组记录该朋友组里已入队的最后一位*/ } else/*如果队列中已经有他的朋友*/ { queue[temp].Index=queue[grouppos[hash[key].group]].Index; /*插队到朋友的后面*/ queue[grouppos[hash[key].group]].Index=temp; /*插队到朋友后面一位的前面*/ grouppos[hash[key].group]=temp; /*替换插队数组里该组的元素为当前元素*/ if(hash[queue[last].HashVal].group==hash[key].group) /*如果当前元素和前一元素是朋友，队尾标志指向当前元素*/ last=temp; } } else if(*c=='D')/*出队命令*/ { if(last==0) /*不能对空队列执行出队命令*/ { fprintf(fpout,“Empty queue!nCan't execute DEQUEUE!n”); return-1; } fprintf(fpout,“%sn”,hash[queue[head].HashVal].name); /*输出队头元素到文件*/ temp=head; head=queue[temp].Index; /*队列第一位出队，队头标记后移一位*/ queue[temp].Index=queue[0].Index; /*队列第0个元素后移一位*/ queue[0].Index=temp; /*释放空间*/ if(grouppos[hash[queue[temp].HashVal].group]==temp) /*当前删除的元素是该朋友组在队列里的最后一位*/ grouppos[hash[queue[temp].HashVal].group]=0; if(last==temp) /*出队后，队列为空*/ last=0; } else /*输入 “STOP”*/ break; /*测试结束*/ } } fprintf(fpout,“b”);fclose(fpin);fclose(fpout);return 1;}第三篇：数据结构课程设计报告
第四篇：数据结构课程设计报告
第五篇：数据结构课程设计报告
点击咨询 