大连科技学院
数据结构课程设计
题 目 单链表的基本操作—子题目
学生成绩管理系统—子题目
约瑟夫环算法的设计与实现—子题目
学生姓名 王 菲 专业班级 软件工程10-1
指导教师 翟 悦 职 称 讲 师
所在单位 信息科学系软件教研室
系 主 任 王立娟
完成日期 20##年12月16日
大连科技学院
数据结构课程设计成绩考核表
注：总评标准采用优良制：优秀（90分以上）、良好（80-90）、中等（70-80）、及格（60-70）、不及格（60分以下）
指导教师签字：
课程设计任务书
一、任务及要求
1. 设计（研究）内容和要求
研究内容：******算法设计与实现
任务和要求：
（1）学习数据结构基础知识，掌握数据结构典型的算法的使用。
（2）对指导教师下达的题目进行任务分析。
（3）根据分析结果完成设计。
（4）编程：在计算机上实现题目的代码实现。
（5）完成对程序的测试和调试。
（6）提交课程设计报告(约二十页)，含程序代码及运行结果。
2. 原始依据
结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。
二、工作量
2周（10个工作日）时间。
三、计划安排
第1个工作日－第2个工作日：查找相关资料、书籍，阅读示例文档，选择题目。
第3个工作日：题目分析，设计算法。
第4个工作日-5个工作日: 功能模块的划分和设计。
第6个工作日：实现具体数据结构和模块。
第7个工作日－第8个工作日：程序设计与调试，编写课程设计报告。
第9个工作日：上交课程设计报告。
第10个工作日：软件验收、答辩，成绩评定。
指导教师签字：
20##年12月26日
目 录
题目一：单链表算法分析与设计........................... 6
1 需求分析........................................................................................................................ 6
1.1 问题描述............................................................................................................... 6
1.2 实现要求............................................................................................................... 6
2.概要设计......................................................................................................................... 1
2.1逻辑结构设计.............................................................................................................. 1
2.2功能结构设计.............................................................................................................. 1
2.3物理结构设计.............................................................................................................. 1
3 算法设计与实现........................................................................................................... 1
3.1算法设计...................................................................................................................... 1
3.2算法实现与调试......................................................................................................... 1
题目二：学生成绩管理算法分析与设计...................... 1
1 需求分析........................................................................................................................ 1
1.1 问题描述............................................................................................................... 1
1.2 实现要求............................................................................................................... 1
2.概要设计......................................................................................................................... 1
2.1逻辑结构设计.............................................................................................................. 1
2.2功能结构设计.............................................................................................................. 1
2.3物理结构设计.............................................................................................................. 1
3 算法设计与实现........................................................................................................... 1
3.1算法设计...................................................................................................................... 1
3.2算法实现与调试......................................................................................................... 1
题目三：约瑟夫环算法分析与设计.......................... 1
1 需求分析........................................................................................................................ 1
1.1 问题描述............................................................................................................... 1
1.2 实现要求............................................................................................................... 1
2.概要设计......................................................................................................................... 1
2.1逻辑结构设计.............................................................................................................. 1
2.2功能结构设计.............................................................................................................. 1
2.3物理结构设计.............................................................................................................. 1
3 算法设计与实现........................................................................................................... 1
3.1算法设计...................................................................................................................... 1
3.2算法实现与调试......................................................................................................... 1
总 结............................................... 1
参考文献.............................................. 1
附录 全部代码......................................... 2
题目一................................................................................................................................ 2
题目二................................................................................................................................ 2
题目三................................................................................................................................ 2
（该页面可通过word“插入－引用－索引与目录”菜单自动生成，在该页面中点击鼠标右键，选择“更新域”，既可自动更新目录，也可自动更新页码。选择字体，一级标题：四号、宋体、加粗，二级标题：小四、宋体、加粗，三级以下标题小四、宋体,页码字体统一为小四、宋体，最好在一页内完成全部目录）
（该页不要页眉、页码，具体操作方法如下）
（首先通过“视图”菜单正常插入页眉、页脚，然后在“目录”页尾插入“分隔符”中的“下一页”；第三步用鼠标双击“正文”页的页眉，在“页眉和页脚”工具栏内取消“链接到前一个”功能，然后回到“目录”页，选中页眉内容并删除）
格式要求：(打印时将该页去掉)
1．一级标题（四号、宋体、加粗、居左、数字后空一格，段前段后设为1 行)
2．二级标题（小四、宋体、加粗、居左，数字后空一格，段前段后为0行）
3．正文（小四、宋体、行间距20磅，不少于15页）
4．每一大标题（一级标题）另起一页
5．图、表标注用宋体五号，图符在图下面，表符在表上面，形式如：
图1-1或表1-1
题目一：单链表算法分析与设计
1 需求分析
1.1 问题描述
用户输入整数型数据，建立单链表、遍历单链表h、按序号查找、插入、删除、求表长、逆置单链表等相关操作。
1.2 实现要求
(1) 建立单链表
用尾插法建立带头结点的单链表h，从键盘输入各字符型数据元素，以“$”
作为输入结束标志符。
(2) 遍历单链表h
依次输出链表中各数据元素。(visit算法)
(3) 按序号查找
查找单链表h中第i个元素并输出该元素。
(4) 插入
在单链表h的第i个元素位置上插入x数据元素
并遍历单链表h（visit算法）
(5) 删除
删除单链表h的第i个数据元素
并遍历单链表h（visit算法）
(6)求表长
求单链表的表长并输出表长
(7) 逆置单链表
逆置带头结点的单链表h，逆置后的单链表利用原表中的结点空间，不重新申请空间。
逆置后进行遍历。
2.概要设计
2.1逻辑结构设计
逻辑结构——线性表:
Linear_list=(D,S)
D={a1,a2,······an}
r={<a1,a2>,<a2,a3>······,<an-1,an>}
2.2功能结构设计
（画出功能结构图----模块图）
2.3物理结构设计
物理结构：单链表
C语言描述如下：
typedef struct Node /*结点的类型定义*/
{ DataType data; /*数据域*/
struct Node *next; /*指针域*/
}Linklist;
Linklist *L,*p; /*定义指针变量*/
3 算法设计与实现
3.1算法设计
(可包括程序结构设计和算法设计,利用所学过的工具给出算法流程或语言描述算法思想，注意：不需将全部代码写入，只需写明解决问题需要的主要功能函数和函数中关键代码）
3.2算法实现与调试
实现截图（代码附在附录中）
题目二：学生成绩管理算法分析与设计
1 需求分析
1.1 问题描述
创建学生成绩表，对表进行增加删除排序查找等操作。
利用单链表作为学生信息的存储结构。
1.2 实现要求
以单链表作为存储结构，设计和实现某班某门课程成绩管理的完整程序。
程序要求完成如下功能：
（1）创建成绩链表，学生数据包含学生的学号、姓名和成绩。
（2）可以在指定学号学生前插入学生成绩数据。
（3）可以删除指定学号的学生数据。
（4）可以计算学生的总数。
（5）可以按学号和姓名查找学生。
（6）可以显示所有学生的成绩。
（7）可以把学生成绩按从高到低的顺序排列
2.概要设计
2.1逻辑结构设计
2.2功能结构设计
2.3物理结构设计
物理结构：单链表
C语言描述如下：
typedef struct{
int num;
char name[STRING_LENGTH]; //学号，姓名
double score; //分数
}Elemtype; //char型数据
typedef struct LNode{ //定义存储结果
Elemtype elem; //所储存的数据
struct LNode* next; //后继指针
}Linklist;
3 算法设计与实现
3.1算法设计
(可包括程序结构设计和算法设计,利用所学过的工具给出算法流程或语言描述算法思想）
3.2算法实现与调试
实现截图，算法的测试数据及测试结果（代码附在附录中）
题目三：约瑟夫环算法分析与设计
1 需求分析
1.1 问题描述
设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。
1.2 实现要求
选择单向循环链表作为存储结构模拟整个过程，并依次输出出列的各人的编号.
2.概要设计
2.1逻辑结构设计
设定人数上限为30人，密码无上限。
1）设定游戏人数
2）为每个人设定密码
3）开始游戏
4）打印结果
2.2功能结构设计
2.3物理结构设计
3 算法设计与实现
3.1算法设计
(可包括程序结构设计和算法设计,利用所学过的工具给出算法流程或语言描述算法思想）
3.2算法实现与调试
实现截图（代码附在附录中）
总 结
在做此次设计前原以为这个设计不会太难，真正做起来时发现有些东西并不像我想象的那么简单，通过这次课程设计使我明白了自己原来知识还很欠缺，思路还很局限，很多内容都是效仿自己所见过的程序的一些东西。自己要学习的东西还太多。通过这次课程设计，我才明白学习是一个长期积累的过程，在以后的工作、生活中都应该不断的学习，努力提高自己知识和综合素质。
此次课程设计还询问了老师和同学不少问题的解决办法，从他们的思路中使自己的专业的设计知识和思路得到了拓展，这次的课程设计是对自己知识的检验，更是在实践中学习的一次好机会。
通过对数据结构这门课的学习，我了解到：“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法等）的研究，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便使查找和存取数据元素更为方便。可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一个核心内容，是从事计算机科学研究及其应用的科技工作者必须掌握的重要内容。
在课程设计中我更体会到：一个好的程序应该是一个所占空间小、运行时间短、其他性能也好的算法。然而，实际上很难做到十全十美，原因是上述要求有时相互抵触。要节约算法的执行时间往往要以牺牲更多的存储空间为代价；而为了节省存储空间又可能要以更多的时间作为代价。因此，只能根据具体情况有所侧重：如果程序的使用次数较少，则应该力求算法简明易懂，而易于转换为上机程序；如果程序反复多次使用，则应该尽可能选用快速的算法；如果待解决的问题数据量极大，机器的存储空间较小，则在编写算法时应该考虑如何节省空间。以后在编写程序时就应该注意到所编写程序的时间复杂度，以及是否运用了良好的算法，而不能只是象以前编写程序时单纯使用C++的知识，要充分考虑程序的性能，争取编写出更优良的程序来。
参考文献
[1] 赵波、霍利等编著．《数据结构实用教程》(C语言版)清华大学出版社，2009．9
[2] 唐策善，李龙澍，黄刘生．《数据结构用C语言描述》[M] 北京：高等教育出版社．1999
[3] 严蔚敏 吴伟民著.《据结构(C语言版)，清华大学出版，1999
[4] 陈一华等编.数据结构---使用C 语言，电子科技大学出版社, 1998
[5] 谭浩强.C语言程序设计（第二版）.北京：高等教育出版社，2002
附录 全部代码
题目一
（题目一的完整代码）
题目二
（题目二的完整代码）
题目三
（题目三的完整代码）