1、数据结构课程设计 学生成绩管理系统部分大 连 科 技 学 院数据结构课程设计题 目 单链表的基本操作-建立和遍历 学生成绩管理系统-排列 排序问题-选择排序,直接插入排序学生姓名 李易霖专业班级 计算机10-1指导教师 宋 丽 芳 职 称 副教授 所在单位 信息科学系软件教研室 系 主 任 王立娟 完成日期 2012年1月6日大连科技学院数据结构课程设计成绩考核表学生姓名李易霖专业班级计算机10-1学号1001020112题 目单链表的基本操作，学生成绩管理系统，排序问题 考 核 项 目分值评分1出勤情况102完成原理分析103设计分析104完成代码编写与调试105独立工作能力、综合运用所学知
2、识分析和解决问题能力及实际工作能力提高的程度106回答问题207课程设计报告格式规范性30合计100总评成绩注：总评标准采用优良制：优秀（90分以上）、良好（80-90）、中等（70-80）、及格（60-70）、不及格（60分以下）指导教师签字： 课程设计任务书一、任务及要求1. 设计（研究）内容和要求研究内容：单链表的基本操作，学生成绩管理系统，二叉树的运算任务和要求：（1）学习数据结构基础知识，掌握数据结构典型的算法的使用。（2）对指导教师下达的题目进行任务分析。（3）根据分析结果完成设计。（4）编程：在计算机上实现题目的代码实现。（5）完成对程序的测试和调试。（6）提交课程设计报告(约二
3、十页)，含程序代码及运行结果。2. 原始依据结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。二、工作量2周（10个工作日）时间。三、计划安排第1个工作日第2个工作日：查找相关资料、书籍，阅读示例文档，选择题目。第3个工作日：题目分析，设计算法。第4个工作日-5个工作日: 功能模块的划分和设计。第6个工作日：实现具体数据结构和模块。第7个工作日第8个工作日：程序设计与调试，编写课程设计报告。第9
4、个工作日：上交课程设计报告。第10个工作日：软件验收、答辩，成绩评定。指导教师签字： 2011年12月26日题目一：单链表的基本操作1 需求分析1.1 问题描述用学过的方法建立单链表,掌握单链表的建立、插入，查找、删除、逆置等基本算法和操作。掌握指针类型的应用和结构体的具体操作，初步掌握采用自底向上，分模块进行的程序的调试与测试。1.2 实现要求(1)建立单链表用尾插法建立带头结点的单链表h，从键盘输入各整型数据元素，以“-1”作为输入结束标志符。 (2) 遍历单链表h依次输出链表中各数据元素。 (3) 按序号查找查找单链表h中第i个元素并输出该元素。(4) 插入在单链表h的第i个元素位置上插
5、入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=,2.2功能结构设计 图
6、1功能设计图本人在该小组中主要负责完成建立和遍历模块的功能实现2.3物理结构设计物理结构(1) 链式存储示意图如下： 图2链式存储示意图 (2) c语言描述如下： #include /*denition of datatype*/( T ypedef char datatype; typedef struct node datatype data; struct node *next; linklist;3 算法设计与实现3.1算法设计1.用于定义单链表的存储结构的函数 LinkList()。2.用带头结点的尾插法创建链表的函数 createList()。3.用于查找第i位元素的函数 get
7、()。4.用于遍历单链表的函数 visit()。5.用于获得表长的函数lengthList()。6.用于在第i位元素后插入新元素的函数 insert ()。7.用于删除第i位元素的函数 delete ()。8.用于逆置单链表的函数 reverse ()。9.用于在程序开始输出欢迎和提示信息的函数 start()。10.用于在程序结束时输出提示信息的函数 end()。11.用于调用上述函数的主函数main()，主函数中对各函数的调用次序及方法为：定义了必要的变量后，先使用system()函数设置操作台背景色；再调用程序开始时的输出函数start()；然后调用创建单链表的函数createList(
8、)并用相应类型的变量接 收它返回的头结点地址；然后询问是否遍历（询问步骤下同），需要的话将刚接收的头结点地址作为参数调用遍历函数visit()；遍历后传递头结点的地址调用查找函数get ()，该函数具有判断查找位置合法性的功能；查找操作结束后传递头结点地址给inser ()调用它（插入操作带有判断插入位置是否合法的功能，故还要调用lengthList()获得表长作为插入函数的另一个参数）插入操作完成后将再次调用遍历函数visit()显示插入结果；结束插入后将头结点地址作为参数调用删除函数delete ()，删除成功后将调用遍历函数显示删除后的结果（插入函数也具有判断位置合法性的功能）；最后是调
9、用逆置函数reverse ()，同样是以头结点为参数。3.2算法实现与调试（1）建立单链表： 123456 图3建立单链表（2）遍历单链表 图4遍历单链表题目二：线性表的应用学生成绩管理1 需求分析1.1 问题描述编写一个简单的学生信息管理程序，能实现对学生信息的简单管理。编写一个简单的学生信息管理程序，能实现对学生信息的简单管理。1.2 实现要求 （1）创建成绩链表，学生数据包含学生的学号、姓名和成绩。 （2）可以在指定学号学生前插入学生成绩数据。 （3）可以删除指定学号的学生数据。 （4）可以计算学生的总数。 （5）可以按学号和姓名查找学生。 （6）可以显示所有学生的成绩。 （7）可以把学
10、生成绩按从高到低的顺序排列。2.概要设计2.1逻辑结构设计逻辑结构，线性结构二元组图式如下: G=(D,S) D=(q,a,z,w,s,x) S=r R=, 图5二元组图式2.2功能结构设计图6功能结构设计图本人在该小组中主要负责完成排列功能实现2.3物理结构设计 物理结构:链式存储， c语言描述如下：#include #include #include #include typedef struct Student int score; char sno5,sname8;Student;typedef struct Node Student studentInfo; struct Node
11、* next;LinkList;3 算法设计与实现3.1算法设计1. 定义学生数据类型 stu。2. 定义结点存储类型 LinkList。3. 函数声明部分。4. 学生信息的输入函数 input()。5. 用带头结点的尾插法建立单链表来存储学生信息的函数createTailList()。6. 遍历单链表显示出学生数据的函数 showList()，此函数由罗聪同学编写。7. 按学号查找学生信息的函数getElem()，此函数由贾利洋同学编写。8. 显示单个学生信息的函数showElem()，此函数由罗聪同学编写。9. 按姓名查找学生信息的函数locateElem()，此函数由贾利洋同学编写。10
12、. 求学生总人数（即表长）的函数lengthList()，此函数由华政同学编写。11. 在指定学号前插入学生数据的函数insertElem()，此函数由孟繁章同学编写。12. 删除指定学号学生信息的函数deleteElem()，此函数由华政同学编写。13. 用直接插入法按分数从高到底排序的函数SIS()。此函数由本人编写。14. 程序开始时的显示函数 start()。15. 程序结束时的显示函数 end()。16. 调用上述各函数的主函数 main()，调用顺序及方法是：首先定义必要的变量；调用程序开始时的显示函数start()；选择后循环语句嵌套选择语句；接着是循环语句中嵌套选择语句和判断语
13、句，根据用户的选择，赋予适当的参数来调用各个功能函数；结束时调用程序结束时的显示函数end()。3.2算法实现与调试（1）开始的菜单图7开始界面(2)当前学生成绩从高到低排序 图8排序题目三：排序问题1 需求分析1.1 问题描述排序是数据处理中最常见，最基本的操作。在解决很多实际问题是，都离不开排序。排序还是另一种基本操作查找操作的基础，排序可以提高查找的效率。因此，学习和 研究排序方法是计算机程序人员课题之一。 1.2 实现要求 利用直接插入和选择排序的方法对一组无序的序列进行排序，使其能正确的按顺序输出2.概要设计2.1逻辑结构设计选择排序：在要排序的一组数中，选出最小的一个数与第一个位置
14、的数交换，然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。直接插入排序：将一个待排序记录按照排序码的大小插入到一个有序序列的适当位置，使得插入后的序列仍然有序，直到所有的记录全部插入到有序序列中。2.2功能结构设计图9功能结构设计图 关键码序列为（42，20，17，27，13，8，17*，48），用直接插入排序算法进行排序。排序过程如图所示。 2.3物理结构设计选择排序 第i趟排序开始时，当前有序区和无序区分别为R1.i-1和R(1in-1)。该趟排序从当前无序区中选出关键字最小的记录 Rk，将它与无序区的第1个记录R交换，使R1.i和R分别变为记
15、录个数增加1个的新有序区和记录个数减少1个的新无序区。 这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 直接插入排序用函数实现直接插入排序，并输出每趟排序的结果.输入格式第一行：键盘输入待排序关键的个数n第二行：输入n个待排序关键字，用空格分隔数据输出格式每行输出一趟排序结果，数据之间用一个空格分隔输入样例105 4 8 0 9 3 2 6 7 1输出样例4 5 8 0 9 3 2 6 7 14 5 8 0 9 3 2 6 7 10 4 5 8 9 3 2 6 7 10 4 5 8 9 3 2 6 7 10 3 4 5 8 9 2 6 7 10 2 3 4 5 8
16、9 6 7 10 2 3 4 5 6 8 9 7 10 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 93 算法设计与实现3.1算法设计功能：选择排序输入：数组名称（也就是数组首地址）、数组中元素个数*/void select_sort(int *x, int n)int i, j, min, t;for (i=0; in-1; i+) /*要选择的次数：0n-2共n-1次*/ min = i; /*假设当前下标为i的数最小，比较后再调整*/ for (j=i+1; jn; j+)/*循环找出最小的数的下标是哪个*/ if (*(x+j) *(x+min) min =
17、j; /*如果后面的数比前面的小，则记下它的下标*/ if (min != i) /*如果min在循环中改变了，就需要交换数据*/ t = *(x+i); *(x+i) = *(x+min); *(x+min) = t; 功能：直接插入排序输入：数组名称（也就是数组首地址）、数组中元素个数*/void insert_sort(int *x, int n)int i, j, t;for (i=1; i=0 & t*(x+j); j-) /*注意：j=i-1，j-，这里就是下标为i的数，在它前面有序列中找插入位置。*/ *(x+j+1) = *(x+ j ); /*如果满足条件就往后挪。最坏的情况
18、就是t比下标为0的数都小，它要放在最前面，j=-1，退出循环*/ *(x+j+1) = t; /*找到下标为i的数的放置位置*/3.2算法实现与调试1直接插入排序（1）第一行：键盘输入待排序关键的个数n图10输入界面 ( 2 )第二行：输入n个待排序关键字，用空格分隔数据 图11排序演示图（3）每行输出一趟排序结果，数据之间用一个空格分隔2直接选择排序（1）输入几个字符串，直到输入！结束 图12输入数字（2）分别以升序和降序排列字符串数组。图13排序结果总 结通过这次两周的数据结构课程设计，我学会了许多知识并且提高了自己的动收能力与团队合作能力，在完成这次课程设计的过程中，我认真查找资料。和队
19、友配合，共同努力完成了这次课程设计。本次课程设计的主题分为三个，分别为单链表的基本操作，学生成绩管理系统 排序问题，通过上机实践，我对这些知识有了更进一步的了解，通过这次课程设计，我的专业知识也丰富了许多。在程序调试阶段，一个小小的错误就会让程序无法运行，我在这个过程中认真查找错误，最后通过我的不懈努力终于把程序调试成功了。这次课程设计的过程让我学会了很多，成长了很多，同时也让我看到了自己身上的不足，许多看似简单的问题在自己操作的时候发现并不那么简单。以后我要继续努力学习专业知识，提高自己的动手能力，不断的丰富自己，完善自己。 参考文献1 赵波,霍利等编著数据结构实用教程(C语言版)清华大学出
20、版社，200992 唐策善，李龙澍，黄刘生数据结构用C语言描述M 北京：高等教育出版社19993 严蔚敏, 吴伟民著.据结构(C语言版)，清华大学出版，19994 陈一华等编.数据结构-使用C 语言，电子科技大学出版社, 19985 谭浩强.C语言程序设计（第二版）.北京：高等教育出版社，20026标准C语言程序设计及应用 周纯杰 ,刘正林等 编著 华中科技大学 7C语言课程设计案例精编 姜灵芝,余健 编著 清华大学出版社附录 全部代码题目一 #include #include #include /*denition of datatype*/typedef int datatype; typ
21、edef struct node datatype data; struct node *next; linklist;/*function of create*/linklist *create() int x; linklist *head,*s,*r; head = (linklist*)malloc(sizeof(linklist); r=head; scanf(%d,&x); while(x!=-1) s = (linklist*)malloc(sizeof(linklist); s-data=x; r-next = s; r = s; scanf(%d,&x); r-next =
22、NULL; return head;/*function of visit*/void visit(linklist *head) linklist *p; p=head-next; while(p) printf( %d,p-data); p=p-next; printf(n);void main() linklist *h1,*q,*h2; int i,b=1; int x; int in,de,ins; datatype *e; while(b) int a; printf(nn); printf( -菜单-n); printf( -n); printf( (1)创建(带头尾插) (2)
23、遍历 (3)查找n); printf( (4)插入(无序) (5)删除 (6)求表长n); printf( (7)逆置 (8)插入(有序) (9)归并n); printf( (10)退出 n); printf( -); printf(n请输入功能选项: ); scanf(%d,&a); switch(a) case 1: printf(Creat linklist h1:n); h1=create(); break; case 2: printf(visit LinkList h1:n); visit(h1); break; case 3: printf(please input the st
24、ation of locate:); scanf(%d,&i); q=get(h1,i); if (q) printf(%d,q-data); else printf(location is error); printf(n); break; case 4: printf(please input the station and data of insert:); scanf(%d,%d,&i,&x); in=insert(h1,i,x); printf(n); if (in=0) printf(location is error); else visit(h1); printf(n); br
25、eak; case 5: printf(please input the staion of delete:); scanf(%d,&i); e=(datatype *) malloc(sizeof(datatype); de=delete(h1,i,e); if (de=0) printf(location is error); else visit(h1); printf(the dele is %d,*e); printf(n); break; case 6: printf(n the table long: %d n,lengthList(h1); break; case 7: rev
26、erse(h1); visit(h1); break; case 8: printf(please input the data of insertSort:); scanf(%d,&x); ins=insertSort(h1,x); printf(n); visit(h1); printf(n); break; case 9: h1=create(); visit(h1); h2=create(); visit(h2); visit(meger(h1,h2); break; case 10: printf(n退出n); b=0; break; 题目二#include#include#include #include typedef struct Student /*学生类型定义*/ int score; /*成绩*/ char sno5,sname8; /*学号,姓名*/ Student; typedef struct Node /*结点类型定义*/ Student studentInfo; /*学生信息*/ struct Node *next; /*指向后继元素的指针域*/ LinkList; void insertSort(L
