-
上海应用技术学院课程设计报告
课程名称
《数据结构课程设计》
设计题目
猴子选大王;< br>建立二叉树;
各种排序;
有序表的合并;
成绩管理系统;
院系
计算机科学与信息工程
专业计算机科学与技术
班级
姓名
学号
指导教师
日期
一
.
目的与要求
1.
巩固和加深对常见数据结构的理解和掌握
2.
掌握基于数据结构进行算法设计的基本方法
3.
掌握用高级语言实现算法的基本技能
4.
掌握书写程序设计说明文档的能力
5.
提高运用数据结构知识及高级语言解决非数值实际问题的能力
二
.
课程设计内容说明
1.
项目一
(1)
对设计任务内容的概述
学生成绩管理
**
任务:要求实现对学生资料的录入、浏览、插入和删除等功能。
输入:
设学 生成绩以记录形式存储,每个学生记录包含的信息有:学号和各
门课程的成绩,设学生成绩至少
3
门以上。存储结构:采用线性链式结构。
(2)
详细设计
LinkList *create()
:
输入学生成绩记录函数;
void print(LinkList *head)
:
显示全部记录函数
LinkList *Delete(LinkList *head)
:
删除记录函数
LinkList *Insert(LinkList *head)
:
插入记录函数
void menu_select()
:
菜单选择
void ScoreManage()
:
函数界面
(3)
程序流程图
学生成绩管理系统
主界面
输入
n
(
0
n=5
判断
n
n=1
、
2
、
3
、
4
.
输
入
学
生
记
录
(4)
程序模块及其接口描述
该程序可以分为以下几个模块:
1
、菜单选择:
void menu_select();
提
供
五
种
可
以
选
择
的
操
作
,
在
main
函
数
中
通
过
swi tch
语
句
调
用
菜
单
menu_select()
函数,进入不同的功能函数中完成相关操作。
2
、输入功能:
LinkList *create();
通 过一个
for
循环语句的控制,
可以一次完成无数条记录的输入。
并将其存入 链
表。
1
.
输
出
学
生
记
录
2
.
删
除
学
生
记
录
3
.
插
入
学
生
记
录
4
.
退
出
5
退出
3
、输出功能:
void print(LinkList *head);
通过一个
while< br>的循环控制语句,
在指针
p!=NULL
时,
完成全部学生记录的显示 。
知道不满足循环语句,程序再次回到菜单选择功能界面。
4
、删除功能:
LinkList *Delete(LinkList *head);
按想要删除的学生的学号首先进行查找,通过指针所指向结点的下 移来完成,
如果找到该记录,
则完成前后结点的连接,
同时对以查找到的结点进行空间 的释
放,最后完成对某个学生记录进行删除,并重新存储。
5
、插入功能:
LinkList *Insert(LinkList *head)
;
输入你想插入的位置,通过指针所指向结点的下移,找到该位置,< br>将该新的学生
记录插入到该结点,并对该结点后面的指针下移。链表长度加一,重新存储。
(5)
程序的输入与输出描述
输入:调用
LinkList *create()
函数,输入学生的姓名、学号、三门功课的成
绩;
输出:调用
void print(LinkList *head)
函数,输出学生的记录。
(6)
程序测试
主菜单:
成绩管理系统的主界面:
学生成绩记录的输入:
输出学生成绩记录:
学生成绩记录的删除(删除学号是
1101
的学生记录)
插入新的学生成绩记录(插入学号为
1103
的学生记录)
(7)
尚未解决的问题或改进方向
尚未 解决的问题:
该成绩管理系统还存在不少缺陷,
而且它提供的功能也是
有限的,只能实 现学生成绩的输入、输出、删除、插入。对于,学生成绩记录的
文件保存以及按学号、姓名等的查询也是 缺少的。还有就是,
对于多个学生成绩
的操作也是不够的。
改进的方向:< br>在时间许可的条件下,尽量的完善该系统的各种功能,同时也
应修改系统,让它更为人性化、简单 化,被广大用户所接受。
(8)
对软件的使用说明
该软件是属于比较低级的软件,
只是包含了课程设计的要求的几个功能:
输
入 、输出、删除、插入。所以用户在使用的过程中肯定会受到一定的局限性、不
方便性,但由于时间的缘故 ,无法将软件做到尽善尽美。
2.
项目二
(1)
对设计任务内容的概述
各种排序
任务:用程序实现插入法排序、选择法排序、起泡法改进算法排序;
利用插入排序、 选择法排序和冒泡法的改进算法
,
将用户随机输入的一列数
按递增的顺序排好。
输入的数据形式为任何一个正整数,大小不限。
输出的形式:数字大小逐个递增的数列。
(2)
功能描述
该函数有以下几个功能:
1)
对
R[0..n-1]
按递增有序进行直接插入排序
2)
对
R[0..n-1]
按递增有序进行冒泡排序
3)
对
R[0..n-1]
按递增有序进行直接选择排序
4)
排序后的输出
5)
调用所有排序,实现排序
(3)
程序流程图
排序
Sort
()
直
接
插
入
排
序
(4)
详细设计
直
接
选
择
排
序冒
泡
排
序
BubbleSort()
退出
void
InsertSort(RecType
R[],int
n)
:对
R[0..n-1]
按递增有序进行直接
插入排序
void
BubbleSort(RecType
R[],int
n)
:对
R[0..n-1]
按递增有序进行冒泡
排序
void
SelectSort(RecType
R[],int
n)
:对
R[0..n-1]
按递增有序进行直接
选择排序
void disp(RecType R[],int n)
:排序后的输出
void Sort()
:调用所有排序,实现排序
(5)
程序模块及其接口描述
该程序分为五个模块
:
1.
输入功能:
void Sort()
建立一个数组存放用户在键盘上输入的关键字,在分别调用各种排 序的函数,
对关键字进行排序。
2.
直接插入排序功能:
void InsertSort(RecType R[],int n)
将后一个数与前一个数比较,
将其插入到第一个比它大的大的 数前面,
其余数
字往后移一个位置。
每次从无序表中取出第一个元素,
把它插 入到有序表的合适
位置,使有序表仍然有序。
3.
冒泡排序功能:
void BubbleSort(RecType R[],int n)
在排序过程中,
执行完最后的排序后,虽然数据 已全部排序完备,但程序无法
判断是否完成排序,为了解决这一不足,可设置一个标志位
exc hange
,将其初
始值设置为非
0
,表示被排序的表是一个无序的表,每一 次排序开始前设置
exchange
值为
0
,在进行数据交换时,修改
exchange
为非
0
。在新一轮排序开
始时,
检查此标志,< br>若此标志为
0
,
表示上一次没有做过交换数据,
则结束排序;
否则进行排序。
4.
直接选择排序功能:
void SelectSort(RecType R[],int n)
在无序区里找 最小的数,
第
i
小的数字放在第
i
个位置上,
与原来第i
个位置
上的数字交换。
5.
输出功能:
void disp(RecType R[],int n)
(6)
程序的输入与输出描述
输入:要求是
10
个为数字的关键字;
输出:排序后新的序列。
(7)
程序测试
输入关键字,调用各种排序函数
(8)
尚未解决的问题或改进方向
改进方向:虽然给出了它的各种排序的结果,但是没有它的箱子过程,
这是我的改进 的方向,
希望能将每种排序的过程也能展示给用户,
来体现它
们的不同。
(9)
对软件的使用说明
用户只需根据提示,在键盘上输入要排序的
10
个关键字。
3.
项目三
(1)
对设计任务内容的概述
有序表的合并
要求输入有序表的数据,< br>利用顺序表和链表结构分布完成两个有序表合并功
能,并输出合并后的信息。
(2)
功能描述
该程序有如下几个功能:
1)
初始化顺序表
2)
初始化链表
3)
建立顺序表
4)
尾插法建表
5)
输出合并后的顺序表
6)
输出合并后的单链表
7)
合并顺序表
8)
合并单链表
9)
调用以上的函数,实现有序表的合并
(3)
概要设计或程序流程图
开始
初
始
化
顺
序
表
初始化链表
建立顺序表
尾插法建表
合并顺序表
合并单链表
输出
结束
(4)
详细设计
void InitList(SqList *&L)
:初始化顺序表
void InitList1(LinkList1 *&L)
:初始化链表
void CreateList(SqList *&L,ElemType a[],int n)
:建立顺序表
void CreateListR(LinkList1 *&L,ElemType a[],int n)
:尾插法建表
void DispList(SqList *L)
:输出合并后的顺序表
void DispList1(LinkList1 *L)
:输出合并后的单链表
void UnionList(SqList *LA,SqList *LB,SqList *&LC)
:合并顺序表
void UnionList1(LinkList1 *LA,LinkList1 *LB,LinkList1 *&LC)
:合并
单链表
void Union()
:调用以上的函数,实现有序表的合并。
(5)
程序模块及其接口描述
程序有以下几个模块:
1)
初始化、建立顺序表
2)
初始化、建立链表
3)
输出合并后的表
4)
合并表
(6)
调试分析或程序测试
有序表的合并:
(7)
尚未解决的问题或改进方向
不足:不能重复使用程序。
(8)
对软件的使用说明
用户只需根据界面的提示,采用对应的操作。
4
.项目四
(1)
对设计任务内容的概述
建立二叉树,层序、先序、中序、后序遍历(
用递归或非递归的方法都可
以)
**
任务:
要 求能够输入树的各个结点,
并能够输出用不同方法遍历的遍历序列;
分别
建立二叉树存 储结构的的输入函数、
输出层序遍历序列的函数、
输出先序遍历序
列的函数、输出中序 遍历序列的函数、输出后序遍历序列的函数;
(2)
功能描述
1)
建立二叉树
2)
输出二叉树
3)
先序遍历非递归算法:
不为空时,访问根
--
左
--
右,采用递归的方法。
4)
中序遍历非递归算法:
不为空时,访问左
--
根
--
右,采用递归的方法。
5)
后序遍历非递归算法:
不为空时,访问左
--
右
--
根,采用递归的方法。
6)
层序遍历:
运用队列,
队列不空时,
有左 孩子将其入队,
有右孩子将其入队,
同时出队。
7
)
调用以上函数实现二叉树的各种遍历
(3)
概要设计或程序流程图
先序遍历
(4)
详细设计
开始
输入二叉树的按层结
点值
中序遍历
后序遍历
层次遍历
结束
void CreateBTNode(BTNode * &b,char *str)
:建立二叉树
void DispBTNode(BTNode *b)
:输出二叉树
void PreOrder(BTNode *b)
:先序遍历非递归算法
void InOrder(BTNode *b)
:中序遍历非递归算法
void PostOrder(BTNode *b)
:后序遍历非递归算法
void LevelOrder(BTNode *b)
:层序遍历
(5)
程序模块及其接口描述
(6)
程序的输入与输出描述
输入二叉树的按层结点值;
输出二叉树先序遍历访问结点的顺序;输出二叉树中序遍历访问结点的顺序;
输出二叉树后序遍历访问结点的顺序;输出二叉树层次遍历访问结点的顺序;
(7)
调试分析或程序测试
用户从键盘上输入要创建的二叉树结点:
(8)
尚未解决的问题或改进方向
改进方向:希望能将系统改进的更为人性化,让界面更舒适,操作更简单。
(9)
对软件的使用说明
用户只需按照界面的提示,
采取相应的措施,
到时界面会提醒用户键盘输入。
5
.项目五
(
1
)对设计任务内容的概述
猴子选大王
**
任务:一堆猴子都有编号,编号是
1
,
2
,
3 ...m ,
这群猴子(
m
个)按照
1-m
的顺序围坐一圈,从第
1< br>开始数,每数到第
N
个,该猴子就要离开此圈,这
样依次下来,直到圈中只剩下 最后一只猴子,则该猴子为大王。
要求:
输入数据:输入
m,n m,n
为整数,
n
输出形式:中文提示按照
m
个猴子,数
n
个数的方法,输出为大王的猴子
是几号
,建立一个函数来实现此功能
(
2
)需求分析或功能描述
为猴子编号
out
,
编号
out=pass
(
pass
为密码值)
,
该 猴子离圈,
次数
step++
。
剩下的猴子继续次操作,直到次数
s tep=
猴子
monkey
时结束。
-
-
-
-
-
-
-
-
本文更新与2021-01-25 09:20,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/565063.html