1、 数据结构课程设计 题 目 单链表的基本操作-建立和遍历 学生成绩管理系统-排列 排序问题-选择排序,直接插入排序 完成日期完成日期 20122012 年年 1 1 月月 6 6 日日 课程设计任务书 一、任务及要求 1. 设计（研究）内容和要求 研究内容：单链表的基本操作，学生成绩管理系统，二叉树的运算 任务和要求： （1）学习数据结构基础知识，掌握数据结构典型的算法的使用。 （2）对指导教师下达的题目进行任务分析。 （3）根据分析结果完成设计。 （4）编程：在计算机上实现题目的代码实现。 （5）完成对程序的测试和调试。 （6）提交课程设计报告(约二十页)，含程序代码及运行结果。 2. 原始
2、依据 结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应 的存储结构，并能设计出解决问题的有效算法。提高程序设计和调试能力。学生通过上机实习， 验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修 改。 二、工作量 2 周（10 个工作日）时间。 三、计划安排 第 1 个工作日第 2 个工作日：查找相关资料、书籍，阅读示例文档，选择题目。 第 3 个工作日：题目分析，设计算法。 第 4 个工作日-5 个工作日: 功能模块的划分和设计。 第 6 个工作日：实现具体数据结构和模块。 第 7 个工作日第 8 个工作日：程序设计与调试，编写
3、课程设计报告。 第 9 个工作日：上交课程设计报告。 第 10 个工作日：软件验收、答辩，成绩评定。 指导教师签字： 2011 年 12 月 26 日 目目 录录 题目一：单链表的基本操作题目一：单链表的基本操作 1 1 1 需求需求分析分析 1 1.1 问题描述 . 1 1.2 实现要求 . 1 2.2.概要设计概要设计 1 2.1 逻辑结构设计 . 1 2.2 功能结构设计 . 2 2.3 物理结构设计 . 2 3 3 算法设计与实现算法设计与实现 3 3.1 算法设计 . 3 3.2 算法实现与调试 . 3 题目二：线性表的应用题目二：线性表的应用学生成绩管理学生成绩管理 4 1 1 需
4、求分析需求分析 4 1.1 问题描述 . 4 1.2 实现要求 . 4 2.2.概要设计概要设计 4 2.1 逻辑结构设计 . 4 2.2 功能结构设计 . 5 2.3 物理结构设计 . 5 3 3 算法设计与实现算法设计与实现 6 3.1 算法设计 . 6 3.2 算法实现与调试 . 7 题目三：排序问题题目三：排序问题 . 8 1 1 需求分析需求分析 8 1.1 问题描述 . 8 1.2 实现要求 . 8 2.2.概要设计概要设计 8 2.1 逻辑结构设计 . 8 2.2 功能结构设计 . 8 2.3 物理结构设计 . 9 3 3 算法设计与实现算法设计与实现 9 3.1 算法设计 .
5、9 3.2 算法实现与调试 11 总总 结结 13 参考文献参考文献 . 14 附录附录 全部代码全部代码 . 15 题目一题目一 . 15 题目二题目二 . 19 题目三题目三 . 23 1 题目一：单链表的基本操作题目一：单链表的基本操作 1 需求分析需求分析 1.1 问题描述 用学过的方法建立单链表,掌握单链表的建立、插入，查找、删除、逆置等基本算 法和操作。掌握指针类型的应用和结构体的具体操作，初步掌握采用自底向上，分模块 进行的程序的调试与测试。 1.2 实现要求 (1)建立单链表 用尾插法建立带头结点的单链表 h，从键盘输入各整型数据元素，以“-1” 作为输入结束标志符。 (2)
6、遍历单链表 h 依次输出链表中各数据元素。 (3) 按序号查找 查找单链表 h 中第 i 个元素并输出该元素。 (4) 插入 在单链表 h 的第 i 个元素位置上插入 x 数据元素 并遍历单链表 h (5) 删除 删除单链表 h 的第 i 个数据元素，并返回第 i 个元素 同时遍历单链表 h (6）求表长 求单链表的表长并输出表长 (7) 逆置单链表 逆置带头结点的单链表 h，逆置后的单链表利用原表中的结点空间，不重新申请空间， 逆置后进行遍历。 (8) 将一个元素插入到有序表中使表仍然有序 带头结点的单链表中的数据元素是整型数且有序。将 x 插入到顺序表的适当位置上，保 持表的有序性,将两个递增的有序表归并成一个递减的有序表，利用原表空间，不能重 新申请空间 2.概要设计概要设计 2.1 逻辑结构设计 逻辑结构: 线性结构 二元组图式 G=(D,S) 2 D=(q,a,z,w,s,x) S=r R=, 2.2 功能结构设计 图 1 功能设计图 本人在该小组中主要负责完成建立和遍历模块的功能实现 2.3 物理结构设计
