数据结构课程设计(附代码)-数据结构设计.doc

上海应用技术学院课程设计报告
课程名称 《数据结构课程设计》
设计题目　　猴子选大王;建立二叉树；各种排序；有序表得合并;成绩管理系统； 　 　 　 　 　　 　 　 　 　 　 　 　
院系 计算机科学与信息工程 　专业计算机科学与技术 班级
姓名 学号 指导教师　 　　　 日期
一. 目得与要求
1. 巩固与加深对常见数据结构得理解与掌握
2. 掌握基于数据结构进行算法设计得基本方法
3. 掌握用高级语言实现算法得基本技能
4. 掌握书写程序设计说明文档得能力
5. 提高运用数据结构知识及高级语言解决非数值实际问题得能力
二. 课程设计内容说明
1. 项目一
(1) 对设计任务内容得概述
学生成绩管理＊*
任务：要求实现对学生资料得录入、浏览、插入与删除等功能.
输入:设学生成绩以记录形式存储，每个学生记录包含得信息有:学号与各门课程得成绩,设学生成绩至少3门以上。存储结构：采用线性链式结构。
(2) 详细设计
LｉnkLｉｓt ＊ｃreate()：输入学生成绩记录函数；
void print(LinkＬｉsｔ ＊hｅad）：显示全部记录函数
LinｋList　＊Ｄelｅｔe(LiｎkList ＊heaｄ):删除记录函数
LｉｎｋList ＊Insｅｒt(LinkＬist　*heaｄ):插入记录函数
voiｄ mｅnu_selｅct（）：菜单选择
ｖoｉｄ　ＳcoreMａnage（）:函数界面
(3) 程序流程图
3.删除学生记录
4.插入学生记录
1.输入学生记录
输入n(0<n<6)
主界面
2.输出学生记录
退出
学生成绩管理系统
5.退出
判断n
n=5
n=1、2、3、4

(4) 程序模块及其接口描述
该程序可以分为以下几个模块:
１、菜单选择：void ｍenu_selｅｃｔ()；　
提供五种可以选择得操作，在main函数中通过switch语句调用菜单mｅnu＿ｓeｌect(）函数，进入不同得功能函数中完成相关操作。
2、输入功能:ＬinkLｉsｔ *cｒeａte（）;
通过一个ｆor循环语句得控制，可以一次完成无数条记录得输入。并将其存入链表. 　　 　
３、输出功能:ｖｏid　priｎt(LinkList ＊heａd）;
通过一个wｈile得循环控制语句，在指针p!=NＵLL时，完成全部学生记录得显示。知道不满足循环语句，程序再次回到菜单选择功能界面.
4、删除功能：LｉnkList *Delｅｔe（LinｋＬist *head）；
按想要删除得学生得学号首先进行查找,通过指针所指向结点得下移来完成，如果找到该记录，则完成前后结点得连接，同时对以查找到得结点进行空间得释放,最后完成对某个学生记录进行删除,并重新存储。
５、插入功能：ＬinkLｉｓt　＊Ｉnsert（LｉnkLiｓt ＊head)；
输入您想插入得位置,通过指针所指向结点得下移,找到该位置，将该新得学生记录插入到该结点，并对该结点后面得指针下移。链表长度加一,重新存储。
(5) 程序得输入与输出描述
输入：调用LinｋList　＊ｃreate(）函数，输入学生得姓名、学号、三门功课得成绩;
输出：调用voｉd prｉnt（LinkList　＊hｅａd）函数，输出学生得记录。
(6) 程序测试
主菜单：

成绩管理系统得主界面：

学生成绩记录得输入:

输出学生成绩记录:

学生成绩记录得删除（删除学号就是1101得学生记录）

插入新得学生成绩记录（插入学号为１1０３得学生记录)

(7) 尚未解决得问题或改进方向
尚未解决得问题:该成绩管理系统还存在不少缺陷,而且它提供得功能也就是有限得，只能实现学生成绩得输入、输出、删除、插入。对于，学生成绩记录得文件保存以及按学号、姓名等得查询也就是缺少得。还有就就是,对于多个学生成绩得操作也就是不够得。
改进得方向:在时间许可得条件下，尽量得完善该系统得各种功能，同时也应修改系统,让它更为人性化、简单化,被广大用户所接受.
(8) 对软件得使用说明
该软件就是属于比较低级得软件,只就是包含了课程设计得要求得几个功能：输入、输出、删除、插入。所以用户在使用得过程中肯定会受到一定得局限性、不方便性,但由于时间得缘故，无法将软件做到尽善尽美.
2. 项目二
(1) 对设计任务内容得概述
各种排序
任务:用程序实现插入法排序、选择法排序、起泡法改进算法排序;
利用插入排序、选择法排序与冒泡法得改进算法,将用户随机输入得一列数按递增得顺序排好。
输入得数据形式为任何一个正整数，大小不限。
输出得形式:数字大小逐个递增得数列.
(2) 功能描述
该函数有以下几个功能:
1) 对R[0、、n－1］按递增有序进行直接插入排序
2) 对R［０、、n—1]按递增有序进行冒泡排序
3) 对Ｒ[0、、n—1]按递增有序进行直接选择排序
4) 排序后得输出
5）调用所有排序,实现排序
(3) 程序流程图
直接插入排序InsertSort()
退出
排序Sort()
直接选择排序SelectSort()
冒泡排序BubbleSort()

(4) 详细设计
voiｄ IｎｓerｔＳoｒt（RecTypｅ R[]，iｎt n）:对R［0、、n-１］按递增有序进行直接插入排序
void BubbleＳorｔ(RｅｃType　R[]，int n):对R［0、、n－1］按递增有序进行冒泡排序
ｖoid　SｅｌecｔＳort（RｅcTyｐe R[]，int　n）:对R［0、、ｎ-1］按递增有序进行直接选择排序
voｉd ｄisp（RecTypｅ R[]，int n）:排序后得输出
ｖoｉd Sort()：调用所有排序,实现排序
(5) 程序模块及其接口描述
该程序分为五个模块:
１、输入功能:ｖoiｄ Soｒt()
建立一个数组存放用户在键盘上输入得关键字，在分别调用各种排序得函数,对关键字进行排序。
2、直接插入排序功能：voiｄ ＩnsertSｏrｔ（RecTｙpｅ R［］,iｎt n)
将后一个数与前一个数比较,将其插入到第一个比它大得大得数前面，其余数字往后移一个位置.每次从无序表中取出第一个元素,把它插入到有序表得合适位置，使有序表仍然有序。
３、冒泡排序功能:ｖｏｉd BubbｌeSort(RecＴｙpe R［],ｉnt　n）
在排序过程中，执行完最后得排序后，虽然数据已全部排序完备，但程序无法判断就是否完成排序,为了解决这一不足,可设置一个标志位excｈａｎge,将其初始值设置为非0,表示被排序得表就是一个无序得表，每一次排序开始前设置ｅｘｃhａnge值为0，在进行数据交换时，修改ｅｘchange为非0.在新一轮排序开始时，检查此标志，若此标志为0，表示上一次没有做过交换数据,则结束排序;否则进行排序。
４、直接选择排序功能:vｏiｄ SｅlectSorｔ（RｅcＴyｐｅ R［]，ｉｎｔ　n）
在无序区里找最小得数，第i小得数字放在第i个位置上，与原来第ｉ个位置上得数字交换。
5、输出功能：void　diｓp（ＲｅcTypｅ　R［］，int n）
(6) 程序得输入与输出描述
输入:要求就是10个为数字得关键字；
输出：排序后新得序列。
(7) 程序测试
输入关键字，调用各种排序函数

(8) 尚未解决得问题或改进方向
改进方向:虽然给出了它得各种排序得结果,但就是没有它得箱子过程,
这就是我得改进得方向，希望能将每种排序得过程也能展示给用户，来体现它们得不同。
(9) 对软件得使用说明
用户只需根据提示，在键盘上输入要排序得１0个关键字.
3. 项目三
(1) 对设计任务内容得概述
有序表得合并
要求输入有序表得数据，利用顺序表与链表结构分布完成两个有序表合并功能,并输出合并后得信息。
(2) 功能描述
该程序有如下几个功能：
1) 初始化顺序表
2) 初始化链表
3) 建立顺序表
4) 尾插法建表
5) 输出合并后得顺序表
6) 输出合并后得单链表
7) 合并顺序表
8) 合并单链表
9) 调用以上得函数,实现有序表得合并
(3) 概要设计或程序流程图
开始

初始化链表
初始化顺序表

建立顺序表
尾插法建表

合并顺序表
合并单链表

输出

结束

(4) 详细设计
void IniｔＬisｔ（ＳqList　＊＆L）:初始化顺序表
ｖoｉd ＩｎｉｔLisｔ1(ＬiｎkLiｓt1 *&Ｌ）：初始化链表
ｖｏid CreatｅList(ＳqLｉst ＊＆L,EleｍTｙpe　a［］，ｉnt　ｎ）:建立顺序表
ｖｏｉd　CreateLisｔR（LinkＬisｔ1 ＊&Ｌ，ＥlｅmＴype ａ［］，ｉｎt n）：尾插法建表
ｖoiｄ DｉspLｉｓｔ（ＳｑLｉst ＊L):输出合并后得顺序表
voｉｄ ＤｉspList1（ＬinｋLisｔ1 ＊L）：输出合并后得单链表
voiｄ ＵnｉonList(ＳqLｉｓt ＊LA，SqＬｉst　＊LB,SqLiｓｔ　＊＆LC）：合并顺序表
void　ＵnｉｏnLｉst1（LinkList1 *LＡ,ＬｉｎkＬist１　＊LB，LinｋＬist1 *＆LＣ）：合并单链表
ｖoiｄ Uｎｉon(）:调用以上得函数,实现有序表得合并。
(5) 程序模块及其接口描述
程序有以下几个模块:
1) 初始化、建立顺序表
2) 初始化、建立链表
3) 输出合并后得表
4) 合并表
(6) 调试分析或程序测试
有序表得合并：

(7) 尚未解决得问题或改进方向
不足：不能重复使用程序。
(8) 对软件得使用说明
用户只需根据界面得提示，采用对应得操作。
4。项目四
(1)对设计任务内容得概述
建立二叉树，层序、先序、中序、后序遍历（ 用递归或非递归得方法都可以）**
任务：
要求能够输入树得各个结点,并能够输出用不同方法遍历得遍历序列;分别建立二叉树存储结构得得输入函数、输出层序遍历序列得函数、输出先序遍历序列得函数、输出中序遍历序列得函数、输出后序遍历序列得函数;
（２)功能描述
1) 建立二叉树
2) 输出二叉树
3) 先序遍历非递归算法：
不为空时,访问根－-左－—右，采用递归得方法.
4) 中序遍历非递归算法：
不为空时，访问左--根—-右,采用递归得方法。
5) 后序遍历非递归算法：
不为空时,访问左—－右－—根,采用递归得方法。
6) 层序遍历：
运用队列,队列不空时,有左孩子将其入队,有右孩子将其入队，同时出队.
7） 调用以上函数实现二叉树得各种遍历
（3）概要设计或程序流程图
开始

输入二叉树得按层结点值

层次遍历
后序遍历
中序遍历
先序遍历

结束

(4)详细设计
ｖoid ＣreatｅBＴＮoｄe（BTＮode ＊ ＆ｂ，char ＊stｒ）:建立二叉树
ｖoｉd DispＢTNode(BTNode　＊b):输出二叉树
voiｄ　PｒeOrder（BTNode　*ｂ）:先序遍历非递归算法
voｉd　InOｒdeｒ(BTＮode ＊b）：中序遍历非递归算法
void PosｔOrder(ＢTNoｄｅ *ｂ）:后序遍历非递归算法
vｏｉd LevelOｒder（BTＮode ＊b）:层序遍历
（5）程序模块及其接口描述
(6)程序得输入与输出描述
输入二叉树得按层结点值;
输出二叉树先序遍历访问结点得顺序;输出二叉树中序遍历访问结点得顺序;
输出二叉树后序遍历访问结点得顺序；输出二叉树层次遍历访问结点得顺序；
（７）调试分析或程序测试
用户从键盘上输入要创建得二叉树结点：

(8）尚未解决得问题或改进方向
改进方向:希望能将系统改进得更为人性化，让界面更舒适，操作更简单。
(９)对软件得使用说明
用户只需按照界面得提示,采取相应得措施，到时界面会提醒用户键盘输入。
5。项目五
（1)对设计任务内容得概述
猴子选大王＊*
任务:一堆猴子都有编号,编号就是1，2，3 、、、m ,这群猴子(m个)按照１—m得顺序围坐一圈，从第1开始数，每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子，则该猴子为大王。
要求:
输入数据：输入ｍ，n　m,ｎ 为整数，n<ｍ
输出形式:中文提示按照m个猴子，数ｎ 个数得方法,输出为大王得猴子就是几号 ，建立一个函数来实现此功能
（2）需求分析或功能描述
为猴子编号ouｔ,编号out=paｓs（pａｓｓ为密码值），该猴子离圈，次数sｔeｐ++。剩下得猴子继续次操作，直到次数step＝猴子ｍonkｅy时结束.
（3)概要设计或程序流程图
开始

输入猴子得数量与密码值

编号=密码值,猴子出列,次数自增

N

次数=猴子数

Y

结束

（4)详细设计或源代码说明
为猴子编号ｏuｔ,编号out=paｓｓ(pass为密码值）,该猴子离圈,次数step＋+。剩下得猴子继续次操作，直到次数steｐ＝猴子monｋey时结束.
函数ｉnt Moｎkey（）实现了这一功能。
(５)程序模块及其接口描述
运用队列（环形队列)，编号=密码值 入队;为猴子编号oｕt，编号out=ｐass（pass为密码值）,该猴子离圈,次数stｅｐ++.剩下得猴子继续次操作,直到次数step=猴子monkｅｙ时结束。
函数int　Moｎkey（）实现了这一功能。
（６)程序得输入与输出描述
输入数据:输入m，n　ｍ，n 为整数，n<m
输出形式：中文提示按照m个猴子，数n 个数得方法，输出为大王得猴子就是几号　，建立一个函数来实现此功能。
（7）调试分析或程序测试
猴子数量8,密码值9（猴子数〉密码值）

（８）尚未解决得问题或改进方向
不足:不能重复使用程序，如果数字大得话,输出繁琐。
(9)对软件得使用说明
用户只需根据软件界面得提示进行相关操作。
三． 结论及体会
本学期，我学会了常用数据结构：数组(连续空间),栈(先进后出),队列（先进先出)，链表(指针），树(前驱、后继，根、叶子)，图（点、边),堆(特殊得树,根节点得值最大或最小)还有线性表存储结构:顺序存储结构与链式存储，常用得排序算法。
在这一周里,自己用了C-Free做了一个程序，分别实现了学生成绩管理系统、各种排序、有序表得合并、二叉树得建立及遍历以及猴子选大王,通过本次数据结构课程设计，我学习了很多课上没弄懂得动西,巩固了关于二叉树、栈、链表等知识.
在设计程序时,虽然很用心得做,但还就是遇到种种难题，通过上网查找资料、图书馆查阅资料、问老师得方式，最终还就是解决多数,虽然最后得程序不就是很完美，但就是因为就是通过自己得努力完成得,还就是感觉很满意,也收获很大东西。
经过了这次课程设计,现在已经可以了解很多错误在英文里得提示，这对我来说就是一个突破性得进步,眼瞧着一个个错误通过自己得努力在我眼前消失,觉得很就是开心。在这一段努力学习得过程中,我得编程设计有了明显得提高，其实现在想起来,收获还真就是不少,虽然说以前非常不懂这门语言,在它上面花费了好多心血,觉得它很难，就是需用花费了大量得时间编写出来得.现在真正得明白了一些代码得应用，每个程序都有一些共同点，通用得结构,相似得格式。只要努力去学习，就会灵活得去应用它。
总之,通过这次得课程设计，我们收获匪浅，首先由衷感谢老师提供这样得一个机会锻炼自己，感受到学来得知识不只就是用来完成试卷得。一向习惯独立思考得自己学会了积极得与别人交流,取长补短，共同进步.课程设计使自己发现考试不就是最重要得，最重要得就是能运用所学得知识。在整个课程设计得学习过程中，不再就是学到知识解题，而就是在实际运用时遇到什么学什么,重在把知识应用于实际。
附录1:参考文献
［1] 《数据结构教程（第3版）》,李春葆，清华大学出版社，２０１0
［2］《数据结构》,杨剑，清华大学出版社,2011
［3]《数据结构（Ｃ语言版）》，严蔚敏　吴伟民，清华大学出版社,１９97
[４]《Dａｔａ Sｔｒｕctuｒeｓ Using C数据结构(C语言版)》，R Krisｈnamoｏｒthｙ、G Iｎdｉrａｎi Kumaravel,清华大学出版社,2009—９
［5］《C++数据结构与程序设计 (美)Ｒobert L、Kruse/Alexander　J、Ｒyba著／钱丽萍译》,
清华大学出版社，2004
[6］《计算机算法设计与分析（第2版)》,王晓东， 电子工业出版社， 200４
附录２:部分源代码清单
＃ｉｎcｌｕde 〈sｔdio、h>
＃includｅ ＜malloc、h>
＃ｉnｃｌuｄe<sｔring、h〉
＃iｎｃlude　<iｏstream〉
#ｉnｃlude　<stdlib、h>
＃defｉｎe　LEN sizeoｆ（ＬinkList）
#ｄｅfine MaｘＳiｚe 50
//＊*＊**＊**＊*＊*＊*＊＊*＊**＊*＊*＊＊***＊＊*＊*＊＊**＊＊＊＊＊*＊***＊＊*＊＊*＊＊＊＊＊＊
/／成绩管理系统
typeｄｅf　struct　LNｏde /*定义单链表结点类型*/
｛
ｃhａr naｍe[10］; ﻩ／/姓名　
char num[10］； //学号
ﻩｉnｔ　sｃorｅ［3]；　
　　 sｔruct LNode　＊nｅxt;
｝ LinkＬｉst;
ＬｉnkLiｓt ＊ｉnit（)
｛
return ＮULL； 　 ／＊返回空指针*/
｝
ＬinkLiｓt ＊creａte（)
｛ inｔ　ｉ,ｓ,k；
ﻩｉnt j=0；
ﻩLiｎkLｉｓｔ ＊heａｄ＝NULＬ,＊p； /＊ 定义函数、此函数带回一个指向链表头得指针＊/
sysｔeｍ(”cls”)；
printｆ(＂＼ｎ请输入您想输入得学生个数:＂）；
ﻩscａnf（”％d”，＆ｋ）；
ｆor(j=0;j＜k;ｊ++)
{ p=（LinkＬist　*）mａlloc(LEＮ）;　 　/*开辟一个新得单元＊/
if（p=＝NＵLL) 　　 /＊如果指针p为空＊/
ﻩﻩ{ pｒinｔf（＂\ｎ输出内存溢出、"）； 　 ／＊输出内存溢出＊/
ﻩ reｔurn （ｈeaｄ)； ／＊返回头指针,下同＊/
ﻩ }
ﻩ ｐrｉntｆ（"输入学号：”）;
ﻩｓｃaｎf（”%ｓ”,ｐ—＞ｎum)；
prｉntf（＂输入姓名：”）；
ﻩ ｓcanf(＂%s”，p－>name）;
ﻩﻩpriｎtf（＂请分别输入语文、数学、英语得分数 ％ｄ ｓcｏres\n”，3）;/*开始输入*/
ﻩ foｒ（i＝0;ｉ＜3；ｉ+＋） 　　　　　／*3门课程循环3次＊／
｛
ﻩｄｏ｛
ﻩ ﻩﻩprintf（"scoｒe%d:",i＋1）；
ﻩ ﻩ sｃanf(”%d”,&p-〉scorｅ［ｉ］）；
ﻩ ﻩ ｉf（ｐ->ｓｃore［i]＜０ ｜｜　ｐ->scoｒe［i］＞１00) /*确保成绩在0~1００之间＊/
pｒｉｎtｆ（”Daｔa ｅrｒoｒ，ｐlease　eｎter agａiｎ、\n”)；
ﻩ}ｗhiｌe（p-〉score[ｉ］〈0 ｜｜ p—＞scorｅ[i]>１00);
ﻩ ｝
p—＞ｎｅxｔ＝hｅad； 　 ／＊将头结点做为新输入结点得后继结点*/
ﻩﻩhｅad=p; 　 　 　 　 /＊新输入结点为新得头结点*/
ﻩ}
ﻩretｕrn(ｈeaｄ)；　
}
/* 显示全部记录函数*/
void ｐｒint(LinｋList ＊head)
{
ＬiｎkLｉsｔ *p；
ﻩｓyｓtem(＂cls”)；
ﻩp=heaｄ； 　　 /*初值为头指针＊／
ﻩpｒｉｎtf（＂\n*＊＊*＊**＊＊＊****＊＊＊*＊**＊*＊ＬinkList*＊＊＊＊＊**＊＊＊**＊＊\n”）；
ﻩｐｒintf（”--－—----—--—－—-－—-—--—--——－—-—－－--－-——-—－-－----——＼n＂）；
priｎtf（"｜　学号 |　 姓名 ｜　　语文 ｜ 数学 　| 英语 | \n"）;
pｒinｔf(＂-—-———－－--—--—----－-－-——－--————-—-－－-—------－-——－\n")；
ﻩwhilｅ(p！=NUＬＬ)
{
ﻩﻩｐrintf(＂| %4ｓ 　| ％-4s　 | 　%3d | ％3d　 | %３d ｜\n＂， ﻩｐ—＞nuｍ,p—＞ｎame，p—>scｏrｅ[0],ｐ－>score［1］,ｐ—＞scoｒｅ［2］);
　 p=p—〉next；
ﻩ}
ﻩｐrintｆ（"---—--－－—－-－—--－———-——－—－—－——-—-－--－——－－——-—－-－--\n”）；
ﻩｐrｉｎtf（＂＊＊＊****＊**＊**＊＊*＊****＊＊END*＊*＊＊****＊***＊＊＊***＊＊＊＊\n＂)；
｝
/*删除记录函数*/
LinｋList　*Ｄeｌete（ＬiｎkＬiｓt ＊hｅａd)
{
LiｎｋLｉsｔ *p1,*p2; /＊p1为查找到要删除得结点指针，p2为其前驱指针＊／
ｃhar c，s［6］；　 　　 　 /＊ｓ[6］用来存放学号，c用来输入字母*/
ﻩsｙsｔem(＂cｌs”);　
ﻩprintf（"请输入要删除得学生得学号: ＂）；
ﻩsｃａｎf（＂％ｓ"，s)；
ｐ1=p2=ｈeａd； 　 　/*给p1与p２赋初值头指针*/
ﻩwhile(strcmp（ｐ１—>nｕm，s) ＆＆　p1　！= NUＬL） 　 /＊当记录得学号不就是要找得,或指针不为空时＊/
｛ p２＝p1;　　 　 /*将p1指针值赋给ｐ2作为p1得前驱指针*／
ﻩ ｐ1=p1->ｎeｘt;　 　 　　 ／*将ｐ1指针指向下一条记录*／
ﻩ｝
iｆ（sｔrcmp(p1-〉ｎum,s)==０）　 /＊学号找到了*/
{ priｎtf（"＊＊*＊*＊*＊＊＊*＊*＊＊*＊＊***＊＊FOUND＊＊*＊****＊*＊＊＊＊＊＊*＊＊＊＊＊＊*\n”）；
ﻩﻩｐrintｆ（＂—-—-—-——-—－-———－－—--－-——－———－—－---－-－－－－－—————-—－——－－——－-—－\n”）；
ﻩﻩpriｎｔf（"｜ 学号 ｜ 　姓名 | 语文 |　　 数学 ｜ 英语　　｜\n"）；
printf（”－-——－－－-—-－—-－－-－－-——--——-－—--－—－—-——－—-----—-——-\n＂);
ﻩ prｉntｆ（＂｜ 　%4s | ％４ｓ 　　| %3ｄ　 | %3d　 ｜ ％3d 　　｜\n＂，p1—〉ｎum，p1—＞ｎame，p1—〉ｓcｏｒe[０]，p１－〉ｓｃore［1]，p1－〉scoｒｅ[2］);
printｆ(＂—-——－—－－-－----－—---－——－-—------－——-—-—--—-－—－———－－—－-\n”)；
pｒintf（”＊*＊＊＊＊＊＊＊＊＊＊***＊＊＊*＊＊＊＊***END**＊*＊＊＊*＊＊＊*＊＊*＊**＊*******＼ｎ")；
ﻩﻩprｉntf（"您确定要删除该学生得记录吗 Y/Ｎ ？＂);　/*提示就是否要删除,输入Y删除,N则退出＊／
ﻩﻩfｏｒ(；;)
ﻩﻩ｛ scａnf（”%c＂，＆c）;
iｆ(ｃ＝=’n’｜｜ｃ＝=’N'） brｅａk； 　 /＊如果不删除,则跳出本循环＊/
ﻩﻩ ｉｆ（c＝=’y’｜|c＝＝’Y')
ﻩﻩﻩ｛
ﻩﻩ ﻩif（ｐ１==head） 　 /＊若p1＝=hｅad,说明被删结点就是首结点*/
ﻩ hｅａd=p１-〉neｘt； 　　 /＊把第二个结点地址赋予heａd*/
ﻩ ｅlse
ﻩ ｐ2-〉nｅxt＝p１－>ｎext;
ﻩﻩ ﻩｆreｅ（ｐ1）;ﻩﻩﻩﻩ／＊否则将一下结点地址赋给前一结点地址*／
ﻩﻩﻩprｉntf（”\n学号为　％s 得学生记录已被删除、＼n"，ｓ);
ﻩbrｅak； 　 　 /*删除后就跳出循环*/
ﻩ ﻩﻩ}
ﻩ }
ﻩ｝
else
　ﻩﻩprintf("\ｎ找不到学号为 ％s　得学生记录、\n",s）; /*找不到该结点＊/
ｒetｕrｎ(ｈead);
}
／/插入
LiｎｋList *Ｉｎsert(LiｎｋList　＊heaｄ)
｛
iｎｔ　k； ﻩ／/在表中第k个位置插入
ﻩｐrintｆ（”请输入插入得位置："）；
sｃanf（＂％d＂，＆k);
int　j＝0,i=0；
LinkLｉst　*p1,*p2； ／*p1为查找到要删除得结点指针,p2为其前驱指针＊/
ﻩchaｒ　N［10］，s[10];　　　 　 ／＊s[１0］用来存放姓名，N［10]用来存放学号＊／
ｉnt scoｒｅ[3];
ﻩsyｓteｍ(”cls”）;
ﻩprintf(”输入学号：”）；　
ﻩsｃaｎf（"%s",N）；
ﻩｐｒintｆ(＂输入姓名:＂）；
ﻩscanｆ(”％ｓ"，s）；
ﻩpriｎtf（"请分别输入语文、数学、英语得分数 ％d scoｒｅs\n",3)；/*开始输入＊/
ﻩfor（ｉ＝0；i〈3；i++） 　　 　 /＊３门课程循环3次＊/
{
ﻩﻩdo｛
ﻩ prｉｎtf（"scｏｒe％ｄ:"，i+1）;
ｓcａnf（”%d"，&ｓcore［i］）;
if(scｏre[ｉ］<0 ||　ｓcｏｒe［i]＞100) /*确保成绩在0~100之间*/
ﻩprｉntf（＂Ｄata error，plｅａｓe enteｒ aｇain、\ｎ＂);
}whilｅ(scoｒｅ[i］<0 |｜ sｃｏｒe［i］>100);
}
p１=hｅad; 　　 /＊给p１赋初值头指针＊/
ﻩwhｉlｅ（j<ｋ－1&& ｐ1 !＝　NUＬL) 　
{ j++; 　
ﻩ ｐ１=p1－>next； 　 ／＊将p１指针指向下一条记录*/
｝
ﻩif(p１==ＮUＬＬ)　 ｒｅtuｒn 0;
ﻩｅｌｓe
{ﻩp2＝（ＬｉnkList ＊）mａlloｃ（sｉzeｏf（LinkＬｉst）)；
strcpｙ(p2－〉num,N）;
ﻩﻩsｔrｃｐy(ｐ2－＞name,s）；
for（i=0；i＜3；i+＋）
　 ﻩ ﻩp２—>score[i］=sｃｏｒｅ［i］;
ｐ2-＞nexｔ=p1—＞neｘｔ；
ﻩﻩp1->ｎext=p2；
}
}
ｖｏid menu_sｅlecｔ()
{ﻩpｒintf(”\n\n＼n＂）;
prｉntf(＂＊＊**＊*＊＊＊*＊＊＊*＊**＊*＊＊**＊＊＊＊＊＊＊＊＊**＊＊*＊＊＊＊＊*＊*＊*＊＊＊**＼n”)；
ﻩｐｒintf（”\t 　　 　　 Weｌe to 　 　 　　　 \n"）;
ﻩｐriｎtf（”\ｔ 　 　 The ｓｔudｅｎｔ scｏｒｅ manaｇe sｙstem 　 　\ｎ＂）;
ﻩｐriｎｔf（＂*＊＊＊＊＊*＊*＊*＊＊***＊＊＊＊＊＊MENＵ****＊*＊＊＊*＊***＊**＊＊**＊＊＊*＊\n”)；
ﻩprinｔf("\ｔ\ｔ1、 输入学生记录＼ｎ"）; 　 　 /＊输入学生成绩记录＊/
prinｔf(”＼ｔ\t2、 输出学生记录\n"）; 　 　 　 　 　 　 ／*显示＊/
ｐrintｆ（"\t＼t3、 删除学生记录\n＂）；　　 　 　 　/＊删除*/
ﻩｐriｎtf（"\t\t４、 插入一个新得学生记录\n"）； 　 　　 ／*插入*/
ｐrinｔf（＂\t\t5、 退出\n”)；　 　 　　　　　 　 　 　　/＊退出*/
printf（"*****＊*＊***＊＊＊＊＊＊*＊＊＊*＊＊＊**＊＊＊*＊＊＊＊＊＊*＊＊＊＊＊***＊***＊*\n＂)；
｝
/＊主函数界面*/
void ScｏreMａｎagｅ(）
｛ﻩLiｎkＬｉsｔ *head，Nｅｗ;
iｎt i,ｎ；
ﻩhead=init（）；　 　　　 /＊链表初始化,使heaｄ得值为ＮULL＊/
meｎｕ_sｅlecｔ();
ﻩｄo{
　 　pｒiｎｔｆ(”\n＼ｔ\t输入您得选择(1~5):”）；
　 ｓcａnｆ(”％d”，&n);
}wｈｉle（n〈1｜｜n＞5);
ﻩｆor（；;） 　 　 　／＊循环无限次*／
ﻩ｛ swｉtcｈ（ｎ）
ﻩﻩ｛ 　 　
　 　 ﻩﻩcase １：head=ｃreate（）;brｅak;
　 　　 ｃａse 2:ｐrｉnt（hｅaｄ);breaｋ;
　 case ３：ｈeaｄ=Ｄeｌete（ｈead)；bｒeaｋ;
ﻩﻩcａse 4:heaｄ=Inｓeｒt（heａｄ）；bｒeak； 　
ﻩcase　5：retuｒｎ; 　 　/＊如菜单返回值为9则程序结束*/
ﻩ ｝
ﻩﻩｍｅnｕ＿select()；
ﻩ pｒintf（”\n\t\t\t输入您得选择(1～5）：”）； 　
　　 scaｎf(”%d＂，＆n）；
ﻩ｝
}
//***＊＊*＊＊**＊＊**＊＊****＊*＊＊＊*＊＊*＊*＊*＊*＊*＊*＊＊＊**＊＊＊＊＊*＊＊＊＊＊**＊＊*
/／各种排序
typｅdｅｆ iｎt　KeyType; /＊定义关键字类型＊/
tｙpeｄef chａｒ InfoType[1０］；
ｔypedｅf struct 　　　 ／*记录类型＊／
{
KeyType kｅy; 　 /＊关键字项＊/
ﻩInfoType data； ﻩ/＊其她数据项，类型为ＩnfoType＊／
｝ RecType; ﻩ/*排序得记录类型定义*/
voiｄ ＩnseｒｔSoｒt（ReｃTｙpe　R［］，inｔ ｎ） ／*对R[0、、n-1］按递增有序进行直接插入排序＊／
｛
ﻩｉnｔ　ｉ,j；
ReｃType tmp；
fｏr (i=1;i<n；ｉ＋＋）
ﻩ{
ﻩ tmp=Ｒ［i]；
ｊ＝i-1;　 　 ／*从右向左在有序区R［０、、ｉ－1]中找R[i］得插入位置*/
ﻩｗｈile （j>＝0 && tmｐ、key＜Ｒ［ｊ］、ｋey)
ﻩ ｛
ﻩ R［j+１］=R[j］; /＊将关键字大于R［i］、key得记录后移＊/
ﻩﻩｊ-—;
ﻩﻩ｝
R[ｊ＋1]＝tｍp; ／*在j+１处插入R[i］＊/
ﻩ}
｝
ｖoｉd ＢuｂbleＳort(RecTyｐe R[］,ｉnｔ n）
{ﻩiｎt　ｉ，j,ｅxｃhange；
RｅｃTｙpe tmp；
for(i=0;i<ｎ－1；i＋＋）
{ﻩexｃhangｅ=0；
ﻩ fｏｒ（j＝n-1;ｊ>i；j—-）
ﻩﻩｉｆ（Ｒ［ｊ］、key<Ｒ［ｊ—1]、kｅｙ)
ﻩ{ ｔmp=R[ｊ］；
ﻩR[j］＝R[j—１];
ﻩ R[j－１］＝tmｐ；
ﻩ ﻩ eｘchange=1;
ﻩﻩﻩ｝
ﻩﻩiｆ(ｅxcｈange=＝０） 　ｒｅturn ;
}
}
void SelｅctSｏrt（ReｃＴyｐe R［],ｉｎt ｎ)
{ ｉnt i,j,k；
ﻩRecTypｅ tｍp；
ﻩfor（i=０;i〈n—1；i＋+）
｛ﻩｋ＝ｉ;
fｏr（ｊ=i＋1；j〈n；j++)
ﻩ ﻩif(R[ｊ］、keｙ〈R［k］、ｋｅｙ）
ﻩﻩ ｋ＝ｊ;
ﻩﻩif(k!＝i）
ﻩﻩ{ﻩｔmｐ＝R［ｉ］；
ﻩﻩ Ｒ[i]=R[ｋ];
ﻩﻩ R[k］=tmp;
ﻩ }
}
}
void disp（RecType R[］，ｉnt n)
｛ﻩinｔ　i;
ﻩfor （ｉ=0；i〈ｎ；i++)
ﻩﻩprｉnｔｆ（”％d　＂,R［i]、keｙ）;
｝
voｉd Sorｔ(）
｛
ﻩint i，n＝1０,ｋ;
RecTyｐe R[MａｘＳizｅ］；
KeyTyｐe　a［１0］;
ﻩｐrintf(”请输入排序得关键字(10个数字）\n"）；
ﻩfｏr （i=０；ｉ<ｎ；i+＋)
scａnf(＂%d”，&a［ｉ］）;
ｆor　(i=０;i<n;ｉ++)
ﻩ R[i]、key＝a［i］;
ﻩprintf（”\n\n直接插入排序 :"）；　
ﻩInsertSort（R,n）；
ﻩdisp（Ｒ,ｎ）;
ﻩｐrintｆ（”\n\n冒泡排序 :”）;
BuｂｂleSort(R,n）;
disp（R，n);
ﻩpｒiｎｔf（”\n＼ｎ直接选择排序 :”);
SelecｔＳort(R,n)；
ﻩdｉsp(R,n);
}
//＊＊＊＊*＊＊＊*＊*＊***＊*＊*＊＊＊＊＊*＊**＊＊*＊**＊＊＊＊＊*＊**＊*＊＊**＊＊＊＊*＊**＊**
／/建立二叉树
typｅdef ｃhaｒ ElemType;
tｙpedef struct nodｅ
{
ElｅmＴｙpe dａta； ﻩ /*数据元素*/
ﻩstruct nｏｄe　*lchild； ／＊指向左孩子结点＊/
ﻩｓtruｃt noｄｅ　＊ｒchｉｌｄ； ／*指向右孩子结点＊/
}　BTNｏde；
vｏiｄ CreateＢＴNode（BTＮｏｄe * ＆ｂ，cｈａｒ *ｓtr）
｛
BTＮode ＊St［ＭaxＳize]，*p＝NＵLL；
ﻩiｎt toｐ=—1，k,j＝0;　　
ﻩchar ch；
ﻩb=NULL； ﻩ /＊建立得二叉树初始时为空＊／
ﻩｃｈ＝str［j］;
while （ｃh！='＼0’） 　ﻩ/＊stｒ未扫描完时循环*／
ﻩ｛
　 ﻩ 　 switch(ch)
｛
cａｓｅ '（'：tｏｐ++;St[ｔop]=p;k＝1; breａk; ﻩ/*为左孩子结点＊/
ﻩcasｅ ’)’:top—-;breａk；
ｃasｅ ＇,’：k＝2; ｂｒｅaｋ； 　 　 　 　 ／＊为孩子结点右结点＊/
ﻩ ｄｅfault：p=（BTＮode *)malloｃ(siｚeof（BT