当前位置：文档之家 › 20111-《数据结构项目实践集中_...

20111-《数据结构项目实践集中_...

  • 格式：doc
  • 大小：65.50 KB
  • 文档页数：5

《数据结构项目实践集中上机》任务书 一、 教学目的及基本要求 1．了解并掌握数据结构的设计方法，具备初步的独立分析和设计能力； 2．初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3．提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4．训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

二、进程安排 本次集中上机总学时为16学时，总共分为三次。 时间 内容 学时 备注

3周 下达任务书，讲解任务安排，选题。 2 指导教师将自己联系方式QQ、电子邮箱等告知学生以便答疑。

3-13周 1．问题分析和任务定义。 2．逻辑设计。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。 3．物理设计。定义相应的存储结构并写出各函数的伪码算法。 4．详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。 5．程序编码。 6．程序调试与测试。 7．结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。 8．编写设计报告。 12 通过自主学习、教师指导和答疑的方式课下开放机房完成设计调试工作

14周 1．检查：  运行程序；  介绍设计的思路与方法；  对教师提出的相关问题进行回答。 2．提交内容：  程序源代码。  报告以电子文档的形式进行提交。

2

其中：S331机房周末开放。 三、要求 1、在后面的课题表中列出了多个设计课题，每个课题都有相应的要求或说明。学生首先要了解设计的任务，仔细阅读各题的设计要求，然后根据自己的基础和能力情况从中选择一题。若学生对课题表以外的相关课题较感兴趣，希望选作课程设计的课题时，应征得指导教师的认可，并写出明确的设计要求和说明。 2 、 关于设计的总要求 ：在设计时，要严格按照题意要求独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。 3 、 验收 ：在设计完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算设计部分的结束。 4 、 设计报告 ：设计结束后要写出课程设计报告，以作为整个集中上机评分的书面依据和存档材料。设计报告以规定格式的电子文档书写，排版及图、表要清楚、工整。内容及要求如下： 1) 简述题目要解决的问题是什么，并说明输入和输出数据的形式。 2) 简述存储结构和算法的基本思想。 3) 列出调试通过的源程序。 4) 列出上面程序对应的运行结果。 5) 分析程序的优缺点、时空性能以及改进思想，写出心得体会。

三、成绩评定 ：

课程设计的成绩评定以选定课题的难易度、完成情况和设计报告为依据综合评分，设计报告占30％，设计作品占70％。从总体来说，所设计的程序应该全部符合要求，问题模型、求解算法以及存储结构清晰；具有友好、清晰的界面；设计要包括所需要的辅助程序，如必要的数据输入、输出、显示和错误检测功能；操作使用要简便；程序的整体结构及局部结构要合理；设计报告要符合规范。

三、数据结构集中上机课题表 1． 排序算法性能分析（95分） 编程实现希尔、快速、堆排序、归并排序算法，并计算每种排序算法的比较、交换次数。要求待排数据从磁盘文件读入，实施排序后将数据写入另一个文件中。 2． 散列表实现学生情况表（85分） 设有学生情况表，每个记录有下列数据项：学号、姓名、性别、年龄。现使用散列表表示该学生情况表，并采用二次探测法解决冲突。试设计一个系统使之具有下列功能：  从一个文本文件中输入各记录（记录项用空格分隔）来建立散列表  搜索并显示给定学号的学生记录  删除一个学生记录  在多次删除后，重新整理学生情况表；  打印学生情况表 3． 三件有制约关系物品过河问题（75分） 有一人要将自己的兔子、蔬菜和狐狸等三件物品运过河。但过河所用的船每次只能装其中的两件，而这三件物品之间又存在一定的制约关系：兔子不能单独和狐狸以及不能和蔬菜在一起，因为狐狸要吃兔子，兔子也能吃蔬菜。试构造出问题模型，并编程实现这一问题的求解。 4． 设计和实现多项式运算（80分）  实现带头结点的单循环链表表示的多项式  设计和实现多项式相加和相乘运算算法  设计一个测试程序：测试多项式加法和乘法运算。要求：  建立一个多项式  打印（显示）一个多项式  实现两个多项式相加；  实现两个多项式相乘。 在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法； 5． 迷宫求解（参见教材描述）（85分） 任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出； 6． 运动会分数统计（95分） 任务：参加运动会有n个学校，学校编号为1„„n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1„„m，女子m+1„„m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20） 功能要求：1).可以输入各个项目的前三名或前五名的成绩； 2)．能统计各学校总分， 3)．可以按学校编号、学校总分、男女团体总分排序输出； 4).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称） 输出形式：有中文提示，各学校分数为整形 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构； 测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明； 7． 订票系统（90分）  任务：通过此系统可以实现如下功能：  录入： 可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）  查询：  可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；  可以输入起飞抵达城市，查询飞机航班情况；  订票：（订票情况可以存在一个数据文件中，结构自己设定） 可以订票，如果该航班已经无票，可以提供相关可选择航班；  退票： 可退票，退票后修改相关数据文件； 客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。  修改航班信息： 当航班信息改变可以修改航班数据文件  要求： 根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能； 8． 文章编辑（85分）  功能：输入一页文字，程序可以统计出文字、数字、空格的个数。  静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。  存储结构使用线性表，分别用几个子函数实现相应的功能；  输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。  输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"（3）输出删除某一字符串后的文章； 9． joseph环 （70分）  任务：编号是1，2，„„,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。  要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。  测试数据： m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？  要求：  输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。  输出形式：建立一个输出函数，将正确的输出序列 10． 停车场管理（95分） 问题描述： 设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在停车场的最北端）,若停车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 基本要求 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 测试数据 设n=2，输入数据为：（‘A’,1,5）,（‘A’,2,10）,（‘D’,1,15）,（‘A’,3,20）,（‘A’,4,25）,（‘A’5,30）,（‘D’,2,35）,（‘D’,4,40）,（‘E’,0,0）。其中：‘A’表示到达（arrival）；‘D’表示离去（departure）；‘E’表示输出结束（end）。 实现提示

合集下载

数据结构实验报告(C语言)(强力推荐)

数据结构实验报告(C语言)(强力推荐)

数据结构实验实验内容和目的：掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。

学习基本的查找和排序技术。

让我们在实际上机中具有编制相当规模的程序的能力。

养成一种良好的程序设计风格。

实验教材：数据结构题集（C语言版）清华大学出版社2007年实验项目：实验一、栈和循环队列㈠、实验内容：①栈掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。

本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所有栈里的元素四个功能。

②循环队列掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。

本程序具有初始化一个队列、入队、出队、显示队列的所有元素、队列长度五个功能。

㈡、实验代码①栈程序代码：#include <stdio.h>#include <malloc.h>#define Stack_Size 6#define ERROR 0#define OK 1typedef int SElemType;typedef struct SNode{SElemType data;struct SNode *next;}SNode,*LinkStack;int CreatTwo(LinkStack &head,int n){int i;SNode *p;head=(LinkStack)malloc(sizeof(SNode));head->next=NULL;printf("请输入数据(数字):\n");for(i=n;i>0;--i){p=(SNode *)malloc(sizeof(SNode));scanf("%d",&p->data);p->next=head->next;head->next=p;}return 1;}int menu_select(){int sn;for(;;){scanf("%d",&sn);if(sn<1||sn>6)printf("\n\t输入错误，请重新输入\n");elsebreak;}return sn;}int Push(LinkStack &top,SElemType e){SNode *q;q=(LinkStack)malloc(sizeof(SNode));if(!q){printf("溢出!\n");return(ERROR);}q->data=e;q->next=top->next;top->next=q;return(OK);}int Pop(LinkStack &top,SElemType &e){SNode *q;if(!top->next){printf("error!\n");return(ERROR);}e=top->next->data;q=top->next;top->next=q->next;free(q);return(OK);}void main(){ int e;LinkStack top;printf("1.初始化一个栈;\n2.PUSH;\n3.POP;\n4.显示所有栈里的元素;\n5.结束;\n");while(1){switch(menu_select()){case 1:if(CreatTwo(top,Stack_Size))printf("Success!\n");break; case 2:printf("Push:\n");scanf("%d",&e);if(Push(top,e))printf("Success!\n");break;case 3:if(Pop(top,e))printf("Success!\n");printf("%d\n",e);break;case 4:LinkStack p;printf("所有栈里的元素:\n");p=top;while(p->next){p=p->next;printf("%7d",p->data);}printf("\n");break;case 5:return;}}}运行结果：②循环队列程序代码：#include<stdlib.h>#include<stdio.h>#define OVERFLOW -1#define OK 1#define ERROR 0#define MAXSIZE 100typedef struct{int *elem;//队列存储空间int front;int rear;}SqQueue;//判断选择是否正确int menu_select(){int sn;for(;;){scanf("%d",&sn);if(sn<1||sn>6)printf("\n\t输入错误，请重新输入\n");elsebreak;}return sn;}//参数(传出)SqQueue &Q,循环队列(空)int InitQueue(SqQueue &Q){Q.elem=(int *)malloc(MAXSIZE*sizeof(int));if(!Q.elem)exit(OVERFLOW);Q.front=Q.rear=-1;for(int i=0;i<MAXSIZE;i++)Q.elem[i]=-1;return OK;}//返回Q的元素个数int QueueLength(SqQueue Q){return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;}//显示队列的元素void Display(SqQueue Q){for(int i=0;i<=QueueLength(Q);i++)if(Q.elem[i]!=-1)printf("%d ",Q.elem[i]);printf("\n");}//入队int EnQueue(SqQueue &Q,int e){Q.rear=(Q.rear+1)%MAXSIZE;if(Q.rear==Q.front)return ERROR;Q.elem[Q.rear]=e;return OK;}//出队int DeQueue(SqQueue &Q,int &e){if(Q.front==Q.rear)return ERROR;e=Q.elem[Q.front+1];Q.elem[Q.front+1]=-1;Q.front=(Q.front+1)%MAXSIZE;return OK;}void main(){SqQueue Q;InitQueue(Q);int elem,e;printf("请输入队列元素(以0结束):\n");scanf("%d",&elem);while(elem!=0){EnQueue(Q,elem);scanf("%d",&elem);}printf("队列为：\n");Display(Q);printf("1.初始化一个队列;\n2.入队;\n3.出队;\n4.显示队列的所有元素;\n5.队列长度:\n6.结束;\n");while(1){switch(menu_select()){case 1:printf("请输入队列元素(以0结束):\n");scanf("%d",&elem);while(elem!=0){EnQueue(Q,elem);scanf("%d",&elem);}printf("队列为：\n");Display(Q);fflush(stdin);break;case 2:scanf("%d",&elem);EnQueue(Q,elem);printf("队列为：\n");Display(Q);fflush(stdin);break;case 3:DeQueue(Q,elem);printf("队列为：\n");Display(Q);break;case 4:printf("\n队列的所有元素:\n");Display(Q);break;case 5:printf("%d\n",QueueLength(Q));break;case 6:return;}}}运行结果：实验二、数组㈠、实验内容：数组一般不做插入或删除操作，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。

数据结构课程设计实验报告 完整版

数据结构课程设计实验报告 完整版

第一章链表的应用线性表是数据结构中最简单、最常用的一种线性结构，也是学习数据结构全部内容的基础，其掌握的好坏直接影响着后继课程的学习。

线性表的顺序存储结构，即顺序表的概念相对比较简单，因此，本章的主要任务是使用有关单链表的操作来实现通讯录信息系统的管理。

1.1设计要求本章的设计实验要求使用有关链表的操作来实现通讯录信息系统的管理。

为了验证算法，通讯录管理包括单通讯录链表的建立、通讯者的插入、通讯者的删除、通讯者的查询及通讯录表的输出等。

主控菜单的设计要求使用数字0—5来选择菜单项，其他输入则不起作用。

程序运行后，给出6个菜单项的内容和输入提示：1．通讯录链表的建立2. 通讯者结点的插入3. 通讯者结点的查询4. 通讯者结点的删除5. 通讯录链表的输出0. 退出管理系统请选择0—5：1.2设计分析1.2.1主控菜单函数设计分析1.实现循环和功能选择首先编写一个主控菜单驱动程序，输入0—5以进入相应选择项。

假设输入选择用变量sn存储，它作为menu_select函数的返回值给switch语句。

使用for循环实现重复选择，并在主函数main()中实现。

实际使用时，只有选择大于5或小于0的值，程序才能结束运行，这就要使用循环控制。

这里使用for循环语句实现菜单的循环选择，为了结束程序的运行，使用了“return”语句，也可以使用“exit(0);”语句。

2.得到sn的合理值如前所述，应该设计一个函数用来输出提示信息和处理输入，这个函数应该返回一个数值sn，以便供给switch语句使用。

假设函数名为menu_select,对于sn的输入值，在switch 中case语句对应数字1—5，对于不符合要求的输入，提示输入错误并要求重新输入。

将该函数与主函数合在一起，编译运行程序，即可检查并验证菜单选择是否正确。

1.2.2功能函数设计分析1.建立通讯录链表的设计这里实际上是要求建立一个带头结点的单链表。

建立单链表有两种方法，一种称之为头插法，另一种称为尾插法。

2011-2012-1-数据结构B-教学计划-

2011-2012-1-数据结构B-教学计划-

4.1线性表
2
1
5
5Байду номын сангаас
4.2数组作为抽象数据类型
4.3稀疏矩阵
第5章树
5.1树的基本概念
3
2
7
6
上机实验2
2
2
8
7
5.2二叉树
习题课
2
1
2
10
8
5.3树和森林
5.4哈夫曼树和哈夫曼编码
第6章集合和搜索
6.1集合及其表示
6.2顺序搜索
3
2
11
9
上机实验3
2
12
10
6.3二分搜索
第7章搜索树
7.1二叉搜索树
总复习
1
1
2
合计
40
27
8
5
参考书：
[1] Mark Allen Weiss著．数据结构与算法分析——C语言描述．冯舜玺译．北京：机械工业出版社，2004．
[2]严蔚敏，吴伟民编著．数据结构．北京：清华大学出版社，1997．
习题课
2
1
2
13
11
第8章跳表和散列表
8.1跳表和散列表
第9章图
9.1图的基本概念
3
2
14
12
上机实验4
2
17
13
9.2图的存储结构
9.3图的遍历
3
3
18
14
9.4最小代价生成树
第10内排序
10.1排序的基本概念
10.2直接插入排序
10.3冒泡排序
习题课
2
1
3
19
15
10.4快速排序
10.5简单选择排序
第11章数据结构课程实训

第11章数据结构课程实训


2． 分调 由于系统是按处理功能分成模块的，一个处理功能由一个或一个以上的
程序构成，所以在单个程序调试成功以后，就可以进行分调。所谓分调是将 一个功能内的所有程序按次序串联起来进行调试，相当于一个子系统的调试。 目的是保证模块内部控制关系的正确和数据内容的正确。 3． 总调 （1）主控制和调度程序的调试
各担负一定的局部功能，互相配合，共同完成整个系统的功能。
• 每个上一层的模块又可以进一步分解成更为简单（具体）的下一层模块，
越下层的模块，其功能越具体，越单一。
模块化的层次结构具有简明性，设计者容易思考，阅读者容易理解。只 要保证每个模块能完成其自身的功能，尽量减少模块之间的联系，整个系统 的正确性和可修改性就可以得到保证。另外，模块化的设计方法也使系统的 可扩充性得到了保证。
11.1.1 系统总体结构设计
1．结构化设计的基本思想
（1）模块化程序的设计思想
• 将系统按一定规则构造成相对独立的模块，每个模块完成一个独立功能，是模
块化设计的基本思想。
• 模块化主要目的是将一个复杂系统划分为一些具有特定功能的模块，使整个
系统设计、测试、维护更加简单。
• 从逻辑上看，模块就是处理功能，给它一定的输入信息，它能对之进行加工
（3）上层模块分解为下层模块的三种结构形式 结构化程序设计是采用科学化、标准化的规定所设计、编写的程序，它
既是一种自上而下的程序设计方法，也是一种模块化的程序设计方法。
顺序结构（Sequence Construct） 在顺序结构的程序处理中，一组语句序列，只有一个入口和一个出口。
选择结构（Selection Construct） （a）单分支选择结构：IF （表达式） 语句 （b）两分支选择结构：