数据结构毕业设计
题 目 单链表的基本操作-建立和遍历
学生成绩管理系统-排列 排序问题-选择排序,直接插入排序
学生姓名 李易霖 专业班级 计算机10-1
指导教师 宋 丽 芳 职 称 副教授
所在单位 信息科学系软件教研室
系 主 任 王立娟
完成日期 2012年1月6日
大连科技学院
数据结构毕业设计成绩考核表
学生姓名 李易霖 专业班级 计算机10-1 学号 1001020112 单链表的基本操作，学生成绩管理系统，排序问题 题 目 考 核 项 目 1 2 3 4 出勤情况 完成原理分析 设计分析 完成代码编写与调试 独立工作能力、综合运用所学知识分析和解决问题能力5 及实际工作能力提高的程度 6 7 回答问题 毕业设计报告格式规范性 20 30 100 10 分值 10 10 10 10 评分 合计 总评成绩 注：总评标准采用优良制：优秀（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)
1
D=(q,a,z,w,s,x) S={r}
R={ 2.2功能结构设计 图1功能设计图 本人在该小组中主要负责完成建立和遍历模块的功能实现 2.3物理结构设计 物理结构(1) 链式存储示意图如下： 图2链式存储示意图 (2) c语言描述如下： #include {datatype data; struct node *next; }linklist; 2 3 算法设计与实现 3.1算法设计 1.用于定义单链表的存储结构的函数 LinkList()。 2.用带头结点的尾插法创建链表的函数 createList()。 3.用于查找第i位元素的函数 get ()。 4.用于遍历单链表的函数 visit()。 5.用于获得表长的函数lengthList()。 6.用于在第i位元素后插入新元素的函数 insert ()。 7.用于删除第i位元素的函数 delete ()。 8.用于逆置单链表的函数 reverse ()。 9.用于在程序开始输出欢迎和提示信息的函数 start()。 10.用于在程序结束时输出提示信息的函数 end()。 11.用于调用上述函数的主函数main()，主函数中对各函数的调用次序及方法为：定义了必要的变量后，先使用system()函数设置操作台背景色；再调用程序开始时的输收它返回的头结点地址；然后询问是否遍历（询问步骤下同），需要的话将刚接收的头结点地址作为参数调用遍历函数visit()；遍历后传递头结点的地址调用查找函数get ()，该函数具有判断查找位置合法性的功能；查找操作结束后传递头结点地址给inser ()调用它（插入操作带有判断插入位置是否合法的功能，故还要调用lengthList()获得表长作为插入函数的另一个参数）插入操作完成后将再次调用遍历函数visit()显示插入结果；结束插入后将头结点地址作为参数调用删除函数delete ()，删除成功后将调用遍历函数显示删除后的结果（插入函数也具有判断位置合法性的功能）；最后是调用逆置函数reverse ()，同样是以头结点为参数。 3.2算法实现与调试 （1）建立单链表： 123456 出函数start()；然后调用创建单链表的函数createList()并用相应类型的变量接 图3建立单链表 （2）遍历单链表 图4遍历单链表 3 题目二：线性表的应用——学生成绩管理 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={ 图5二元组图式 4 2.2功能结构设计 开 始 菜单选择 否 录 入 否 插 入 否 删除 按名查找 否 否 按号查找 遍历 否 倒置？ 否 连接链表 是 成绩 成绩 成绩 成绩 成绩 成绩 成绩 成绩 是 成绩 是 是 是 是 是 是 是 排列 结 束 图6功能结构设计图 本人在该小组中主要负责完成排列功能实现 2.3物理结构设计 物理结构:链式存储， c语言描述如下： #include char sno[5],sname[8]; 5 }Student; typedef struct Node { 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()。 6 3.2算法实现与调试 （1）开始的菜单 图7开始界面 (2)当前学生成绩从高到低排序 图8排序 7 题目三：排序问题 1 需求分析 1.1 问题描述 排序是数据处理中最常见，最基本的操作。在解决很多实际问题是，都离不开排序。排序还是另一种基本操作——查找操作的基础，排序可以提高查找的效率。因此，学习和 研究排序方法是计算机程序人员课题之一。 1.2 实现要求 利用直接插入和选择排序的方法对一组无序的序列进行排序，使其能正确的按顺序输出 2.概要设计 2.1逻辑结构设计 选择排序：在要排序的一组数中，选出最小的一个数与第一个位置的数交换，然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。 直接插入排序：将一个待排序记录按照排序码的大小插入到一个有序序列的适当位置，使得插入后的序列仍然有序，直到所有的记录全部插入到有序序列中。 2.2功能结构设计 图9功能结构设计图 8 关键码序列为（42，20，17，27，13，8，17*，48），用直接插入排序算法进行排序。 排序过程如图所示。 2.3物理结构设计 选择排序 第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 直接插入排序 用函数实现直接插入排序，并输出每趟排序的结果. 输入格式 第一行：键盘输入待排序关键的个数n 第二行：输入n个待排序关键字，用空格分隔数据 输出格式 每行输出一趟排序结果，数据之间用一个空格分隔 输入样例 10 5 4 8 0 9 3 2 6 7 1 输出样例 4 5 8 0 9 3 2 6 7 1 4 5 8 0 9 3 2 6 7 1 0 4 5 8 9 3 2 6 7 1 0 4 5 8 9 3 2 6 7 1 0 3 4 5 8 9 2 6 7 1 0 2 3 4 5 8 9 6 7 1 0 2 3 4 5 6 8 9 7 1 0 2 3 4 5 6 7 8 9 1 0 1 2 3 4 5 6 7 8 9 3 算法设计与实现 3.1算法设计 功能：选择排序 输入：数组名称（也就是数组首地址）、数组中元素个数 */ void select_sort(int *x, int n) 9 这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 { int i, j, min, t; for (i=0; i min = 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 for (j=i-1; j>=0 && t<*(x+j); j--) /*注意：j=i-1，j--，这里就是下标为i的数，在它前面有序列中找插入位置。*/ 10 { *(x+j+1) = *(x+ j ); /*如果满足条件就往后挪。最坏的情况就是t比下标为0的数都小，它要放在最前面，j==-1，退出循环*/ } *(x+j+1) = t; /*找到下标为i的数的放置位置*/ } } 3.2算法实现与调试 1直接插入排序 （1）第一行：键盘输入待排序关键的个数n 图10输入界面 ( 2 )第二行：输入n个待排序关键字，用空格分隔数据 图11排序演示图 11 （3）每行输出一趟排序结果，数据之间用一个空格分隔 2直接选择排序 （1）输入几个字符串，直到输入\"！\"结束 图12输入数字 （2）分别以升序和降序排列字符串数组。 图13排序结果 12 总 结 通过这次两周的数据结构毕业设计，我学会了许多知识并且提高了自己的动收能力与团队合作能力，在完成这次毕业设计的过程中，我认真查找资料。和队友配合，共同努力完成了这次毕业设计。 本次毕业设计的主题分为三个，分别为单链表的基本操作，学生成绩管理系统 排序问题，通过上机实践，我对这些知识有了更进一步的了解，通过这次毕业设计，我的专业知识也丰富了许多。 在程序调试阶段，一个小小的错误就会让程序无法运行，我在这个过程中认真查找错误，最后通过我的不懈努力终于把程序调试成功了。 这次毕业设计的过程让我学会了很多，成长了很多，同时也让我看到了自己身上的不足，许多看似简单的问题在自己操作的时候发现并不那么简单。以后我要继续努力学习专业知识，提高自己的动手能力，不断的丰富自己，完善自己。 13 参考文献 [1] 赵波,霍利等编著．《数据结构实用教程》(C语言版)清华大学出版社，2009．9 [2] 唐策善，李龙澍，黄刘生．《数据结构用C语言描述》[M] 北京：高等教育出版社．1999 [3] 严蔚敏, 吴伟民著.《据结构(C语言版)，清华大学出版，1999 [4] 陈一华等编.数据结构---使用C 语言，电子科技大学出版社, 1998 [5] 谭浩强.C语言程序设计（第二版）.北京：高等教育出版社，2002 [6]《标准C语言程序设计及应用》 周纯杰 ,刘正林等 编著 华中科技大学 [7]《C语言毕业设计案例精编》 姜灵芝,余健 编著14 清华大学出版社 附录 全部代码 题目一 #include /*denition of datatype*/ typedef int datatype; typedef struct node /*function of create*/ linklist *create() { int x; linklist *head,*s,*r; head = (linklist*)malloc(sizeof(linklist)); r=head; } /*function of visit*/ void visit(linklist *head) { 15 { datatype data; struct node *next; }linklist; scanf(\"%d\while(x!=-1) { s = (linklist*)malloc(sizeof(linklist)); s->data=x; r->next = s; r = s; scanf(\"%d\ r->next = NULL; } return head; } linklist *p; p=head->next; while(p) { printf(\" %d\ 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(\"\\n\\n\"); printf(\" --------------------菜单------------------------\\n\"); printf(\" ------------------------------------------------\\n\"); printf(\" (4)插入(无序) (5)删除 (6)求表长\\n\"); printf(\" (7)逆置 (8)插入(有序) (9)归并\\n\"); printf(\" ------------------------------------------------\"); printf(\"\\n请输入功能选项: \"); scanf(\"%d\switch(a) { case 1: printf(\"Creat linklist h1:\\n\"); h1=create(); break; printf(\"visit LinkList h1:\\n\"); visit(h1); 16 printf(\" (1)创建(带头尾插) (2)遍历 (3)查找\\n\"); printf(\" (10)退出 \\n\"); case 2: break; printf(\"please input the station of locate:\"); scanf(\"%d\q=get(h1,i); if (q) printf(\"%d\else printf(\"location is error\"); printf(\"\\n\"); break; printf(\"please input the station and data of insert:\"); scanf(\"%d,%d\in=insert(h1,i,x); printf(\"\\n\"); if (in==0) printf(\"location is error\"); else visit(h1); printf(\"\\n\"); break; printf(\"please input the staion of delete:\"); scanf(\"%d\ 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\printf(\"\\n\"); break; case 3: case 4: case 5: case 6: reverse(h1); 17 printf(\"\\n the table long: %d \\n\break; case 7: case 9: } } } visit(h1); break; case 8: printf(\"please input the data of insertSort:\"); scanf(\"%d\ ins=insertSort(h1,x); printf(\"\\n\"); visit(h1); printf(\"\\n\"); break; h1=create(); visit(h1); h2=create(); visit(h2); visit(meger(h1,h2)); break; case 10: printf(\"\\n退出\\n\"); b=0; break; 18 题目二 #include typedef struct Student{ /*学生类型定义*/ int score; /*成绩*/ char sno[5],sname[8]; /*学号,姓名*/ } Student; typedef struct Node{ /*结点类型定义*/ Student studentInfo; /*学生信息*/ struct Node *next; /*指向后继元素的指针域*/ } LinkList; void insertSort(LinkList *L) /*用直接插入排序思想把学生的成绩按从高到低排序， 结果保存在新有序链表中，原链表不变*/ { LinkList *L1,*p; /*L1有序链表的表头，p插入位置前结点*/ LinkList *q,*s; /*q欲插入L1中的结点*/ int len; len=lengthList (L) ; L1=( LinkList *)malloc(sizeof (LinkList)); /*建立头结点，申请结点存储空间*/ if (L->next) /*链表L非空*/ { /*生成有序链表的第一个结点*/ s=( LinkList *)malloc(sizeof (LinkList)); /*建立结点，申请结点存储空间*/ strcpy(s->studentInfo .sno ,L->next->studentInfo.sno); strcpy(s->studentInfo .sname,L->next->studentInfo.sname); s->studentInfo .score =L->next->studentInfo.score; s->next =NULL; 19 L1->next=s; /*只有原单链表的第一个结点的有序链表L1*/ q=L->next->next; /*原单链表的第二个结点，q即要插入有序链表L1中的结点*/ } else { printf(\"\\nthe student link list is empty\\n\"); return; } while(q) /*链表L中有结点*/ { p=L1 ; /*从链表L1的第一个结点开始比较*/ while((p->next) (p->next->studentInfo.score>=q->studentInfo.score)) p=p->next ; /*查找插入位置前结点*/ /*生成欲插入有序链表中的结点*/ s=( LinkList *)malloc(sizeof (LinkList)); /*建立结点，申请结点存储空间*/ strcpy(s->studentInfo .sno ,q->studentInfo.sno); strcpy(s->studentInfo .sname ,q->studentInfo.sname); s->studentInfo .score =q->studentInfo.score; if(!p->next) /*p是有序链表的最后一个结点*/ { s->next =NULL ; p->next =s; } else { s->next =p->next ; p->next =s; } q=q->next; /*下一个欲插入有序链表的结点*/ }/*while(!q)*/ 20 && displayAll(L1); /*显示生成的有序链表*/ } void main() { LinkList *L; char ch[5]; char sname[8]; int b=1; printf(\"=============================================\\n\\n\"); printf(\" 带头结点的学生成绩管理程序\\n\\n\"); printf(\"=============================================\\n\\n\"); while(b) { int a; printf(\"\\n\\n\"); printf(\" <1>创建（带头尾插） <2>指定学号前插入 <3>按学号删除\\n \"); printf(\"<4>计算学生总数 <5> 按学号查找 <6> 按姓名查找\\n\"); printf(\" <7>显示所有学生 <8>成绩排序 <9> 退出\\n\"); printf(\"\\n请输入功能选项：\"); scanf(\"%d\ switch(a){ case 1: L=CreateTailList(); break; case 2: printf(\"\\n输入欲在哪个学号前插入数据:\"); scanf(\"%s\ insertElem(L, ch); break; case 3: printf(\"\\n输入欲删除学生的学号:\"); scanf(\"%s\ 21 deleteElem(L, ch); break; case 4: printf(\" \\n学生总数为： %d \\n\ break; case 5: printf(\"\\n输入欲查找学生的学号:\"); scanf(\"%s\ locateElemByno(L, ch) ;break; case 6: printf(\"\\n输入欲查找学生的姓名:\"); scanf(\"%s\ locateElemByname(L, sname);break; case 7: displayAll(L); break; case 8: insertSort(L); break; case 9: printf(\"\\n已退出\\n\"); b=0;break; }; } } 22 题目三 选择排序 #include void shengxu(char x[][12],int i); void jiangxu(char x[][12],int i); void main() { int i=0,n=0; char x[10][12]; do{ printf(\"string %d:\ scanf(\"%s\ }while(strcmp(x[n++],\"!\")); shengxu(x,i); jiangxu(x,i); } void shengxu(char x[][12],int i) { int n=i-1; int item; char temp[12]; for(item=0;item strcpy(temp,x[item]); strcpy(x[item],x[i]); strcpy(x[i],temp); } } } 23 printf(\"recorded ascnd of strings:\\n\"); for(i=0;i printf(\"\\n\\n\"); } void jiangxu(char x[][12],int i) { int n=i-1; int item; char temp[12]; for(item=0;item strcpy(temp,x[i]); strcpy(x[i],x[item]); strcpy(x[item],temp); } } } printf(\"recorded ascnd of strings:\\n\"); for(i=0;i printf(\"\\n\\n\"); } 直接插入排序 #include\"stdio.h\" #define MAXSIZE 20//一个用作示例的小顺序表的最大长度 int Insertsort(int r[],int n) 24 {//作直接插入排序 int i,j; for(i=2;i<=n;i++) { r[0]=r[i]; j=i-1; while(r[0] printf(\"%d \}//for printf(\"\\n\"); }//for }//Insertsort int main() { int n,i; int r[MAXSIZE]; } //r[0]用作哨兵单元 //插入到正确位置 //输出每趟排序的结果 for(j=1;j<=n;j++) //待排序的关键字个数 scanf(\"%d\ for(i=1;i<=n;i++)//输入待排序的关键字 scanf(\"%d\ Insertsort(r,n); 25 因篇幅问题不能全部显示，请点此查看更多更全内容