大连科技学院数据结构毕业设计题目单链表的基本操作- 建立和遍历学生成绩管理系统- 排列排序问题-选择排序, 直接插入排序学生姓名李易霖专业班级计算机10-1指导教师宋丽芳职称副教授所在单位信息科学系软件教研室系主任王立娟完成日期2012 年1 月6 日大连科技学院数据结构毕业设计成绩考核表计算机学生姓名李易霖专业班级学号100102011210-1单链表的基本操作，学生成绩管理系统，排序问题题目注：总评标准采用优良制：优秀（ 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 个工作日：软件验收、答辩，成绩评定。

指导教师签字：2011 年12月26日目录题目一：单链表的基本操作. (1)1 需求分析 (1)1.1问题描述. (1)1.2实现要求. (1)2.概要设计 (1)2.1逻辑结构设计 (1)2.2功能结构设计 (2)2.3物理结构设计 (2)3 算法设计与实现 (3)3.1算法设计 (3)3.2算法实现与调试 (3)题目二：线性表的应用——学生成绩管理. (4)1 需求分析 (4)1.1问题描述. (4)1.2实现要求. (4)2.概要设计 (4)2.1逻辑结构设计 (4)2.2功能结构设计 (5)2.3物理结构设计 (5)3 算法设计与实现 (6)3.1算法设计 (6)3.2算法实现与调试 (7)题目三：排序问题 (8)1 需求分析 (8)1.1问题描述. (8)1.2实现要求. (8)2. 概要设计 (8)2.1逻辑结构设计 (8)2.2功能结构设计 (8)2.3物理结构设计 (9)3 算法设计与实现 (9)3.1算法设计 (9)3.2算法实现与调试 (11)总结. (13)参考文献. (14)附录全部代码 (15)题目一 (15)题目二 (19)题目三 (23)题目一：单链表的基本操作1 需求分析1.1问题描述用学过的方法建立单链表, 掌握单链表的建立、插入，查找、删除、逆置等基本算法和操作。

掌握指针类型的应用和结构体的具体操作，初步掌握采用自底向上，分模块进行的程序的调试与测试。

1.2实现要求(1)建立单链表用尾插法建立带头结点的单链表h，从键盘输入各整型数据元素，以“ -1 ” 作为输入结束标志符。

(2)遍历单链表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)D=(q,a,z,w,s,x) S={r}R={<q,a>,<a,z>,<z,w>,<w,s>,<s,x>}2.2 功能结构设计图 2 链式存储示意图(2) c 语言描述如下： #include <stdio.h>/*denition of datatype*/(T ypedef char datatype; typedef struct node {datatype data; struct node *next; }linklist; 3 算法设计与实现 3.1 算法设计1. 用于定义单链表的存储结构的函数 LinkList() 。

图 1 功能设计图本人在该小组中主要负责完成建立和遍历模块的功能实现物理结构 (1) 链式存储示意图如下：2. 用带头结点的尾插法创建链表的函数createList() 。

3.用于查找第i 位元素的函数get () 。

4.用于遍历单链表的函数visit() 。

5.用于获得表长的函数lengthList() 。

6.用于在第i 位元素后插入新元素的函数insert () 。

7.用于删除第i 位元素的函数delete () 。

8.用于逆置单链表的函数reverse () 。

9.用于在程序开始输出欢迎和提示信息的函数start() 。

10.用于在程序结束时输出提示信息的函数end() 。

11.用于调用上述函数的主函数main() ，主函数中对各函数的调用次序及方法为：定义了必要的变量后，先使用system() 函数设置操作台背景色；再调用程序开始时的输出函数start() ；然后调用创建单链表的函数createList() 并用相应类型的变量接收它返回的头结点地址；然后询问是否遍历(询问步骤下同) ，需要的话将刚接收的头结点地址作为参数调用遍历函数visit() ；遍历后传递头结点的地址调用查找函数get () ，该函数具有判断查找位置合法性的功能；查找操作结束后传递头结点地址给inser () 调用它(插入操作带有判断插入位置是否合法的功能，故还要调用lengthList() 获得表长作为插入函数的另一个参数)插入操作完成后将再次调用遍历函数visit() 显示插入结果；结束插入后将头结点地址作为参数调用删除函数delete () ，删除成功后将调用遍历函数显示删除后的结果(插入函数也具有判断位置合法性的功能) ；最后是调用逆置函数reverse () ，同样是以头结点为参数。

3.2算法实现与调试( 1)建立单链表：123456图 3 建立单链表2)遍历单链表图 4 遍历单链表题目二：线性表的应用——学生成绩管理1 需求分析1.1问题描述编写一个简单的学生信息管理程序，能实现对学生信息的简单管理。

编写一个简单的学生信息管理程序，能实现对学生信息的简单管理。

1.2实现要求（1）创建成绩链表，学生数据包含学生的学号、姓名和成绩。

（2）可以在指定学号学生前插入学生成绩数据。

（3）可以删除指定学号的学生数据。

（4）可以计算学生的总数。

（5）可以按学号和姓名查找学生。

（6）可以显示所有学生的成绩。

（7）可以把学生成绩按从高到低的顺序排列。

2. 概要设计2.1逻辑结构设计逻辑结构，线性结构二元组图式如下:G=（D,S）D=（q,a,z,w,s,x）S={r}R={<q,a>,<a,z>,<z,w>,<w,s>,<s,x>}图 5 二元组图式图 6 功能结构设计图 本人在该小组中主要负责完成排列功能实现 2.3 物理结构设计物理结构: 链式存储， c 语言描述如下：#include <string.h> #include <malloc.h> #include <stdlib.h>#include <stdio.h> typedef struct Student { int score;char sno[5],sname[8]; }Student;typedef struct Node2.2 功能结构设计开始 菜单选择按 号 查 找连 接 链 表 成绩成绩否否插 入 ？删 除 ？按 名 查 找是成 绩{ Student studentInfo;struct Node * next;}LinkList;3 算法设计与实现3.1算法设计1. 定义学生数据类型stu 。

2. 定义结点存储类型LinkList 。

3.函数声明部分。

4.学生信息的输入函数input() 。

5.用带头结点的尾插法建立单链表来存储学生信息的函数createTailList() 。

6.遍历单链表显示出学生数据的函数showList() ，此函数由罗聪同学编写。

7.按学号查找学生信息的函数getElem() ，此函数由贾利洋同学编写。

8.显示单个学生信息的函数showElem()，此函数由罗聪同学编写。

9.按姓名查找学生信息的函数locateElem() ，此函数由贾利洋同学编写。

10.求学生总人数(即表长)的函数lengthList() ，此函数由华政同学编写。

11.在指定学号前插入学生数据的函数insertElem() ，此函数由孟繁章同学编写。

12.删除指定学号学生信息的函数deleteElem() ，此函数由华政同学编写。

13.用直接插入法按分数从高到底排序的函数SIS() 。

此函数由本人编写。

14.程序开始时的显示函数start() 。

15.程序结束时的显示函数end() 。

16.调用上述各函数的主函数main() ，调用顺序及方法是：首先定义必要的变量；调用程序开始时的显示函数start() ；选择后循环语句嵌套选择语句；接着是循环语句中嵌套选择语句和判断语句，根据用户的选择，赋予适当的参数来调用各个功能函数；结束时调用程序结束时的显示函数end() 。

3.2算法实现与调试(1)开始的菜单图 7 开始界面(2)当前学生成绩从高到低排序图 8 排序题目三：排序问题1 需求分析1.1问题描述排序是数据处理中最常见，最基本的操作。

在解决很多实际问题是，都离不开排序。

排序还是另一种基本操作——查找操作的基础，排序可以提高查找的效率。