数据结构课程设计(附代码)-数据结构设计说明

应用技术学院课程设计报告

课程名称《数据结构课程设计》

设计题目猴子选大王；建立二叉树；各种排序；有序表的合并；成绩管理系统；

院系计算机科学与信息工程专业计算机科学与技术班级

学号指导教师日期

一.目的与要求

1.巩固和加深对常见数据结构的理解和掌握

2.掌握基于数据结构进行算法设计的基本方法

3.掌握用高级语言实现算法的基本技能

4.掌握书写程序设计说明文档的能力

5.提高运用数据结构知识及高级语言解决非数值实际问题的能力

二.课程设计容说明

1.项目一

(1)对设计任务容的概述

学生成绩管理秣

任务：要现对学生资料的录入、浏览、插入和删除等功能。

揄入：设学生成绩以记录形式存储，每个学生记录包含的信息有：学号和各

门课程的成绩，设学生成绩至少3门以上。存储结构：采用线性链式结构。

(2)详细设计

LinkList米create。:输入学生成绩记录函数；

voidprint(LinkList*head):显示全部记录函数

LinkListWeleteCLinkList*head)：删除记录函数

LinkList*Insert(LinkList*head):插入记录函数

voidmenu_select():菜单选择

voidScoreManageO:函数界面

(3)程序流程图

学生成绩管理系统

七

.5

输

插

入

入退

学

学出

生

生

记

记

录

录

退出)

(4)程序模块及其接口描述

该程序可以分为以下几个模块：

1'菜单选择:voidmcnu_select();

提供五种可以选择的操作，在main函数过switch语句调用菜单menu_select()

函数，进入不同的功能函数中完成相关操作。

2、输入功能:LinkList*crcatc();

通过一个for循环语句的控制，可以一次完成无数条记录的榆入。并将其存入链

表。

3、输出功能：voidprint(LinkList米head);

通过一个while的循环控制语句，在指针p!=NULL时，完成全部学生记录的显示。

知道不满足循环语句，程序再次回到菜单选择功能界面。

4'删除功能：LinkList*Delete(LinkList米head);

按想要删除的学生的学号首先进行查找，通过指针所指向结点的下移来完成，

如果找到该记录，则完成前后结点的连接，同时对以查找到的结点进行空间的释

放，最后完成对某个学生记录进行删除，并重新存储。

5、插入功能:LinkList*Insert(LinkList米head)；

输入你想插入的位置，通过指针所指向结点的下移，找到该位置，将该新的学生

记录插入到该结点，并对该结点后面的指针下移。链表长度加一，重新存储。

(5)程序的输入与输出描述

输入：调用LinkList米create。函数，输入学生的、学号、三门功课的成绩；

输出：调用voidprintCLinkList*head)函数，输出学生的记录。

(6)程序测试

主菜单：

E:\数据结构课程设计'主程序.exe

主菜单

成

膏

系统

靠

M1理*

各

2序

二

M立*

建

M3叉^*

表

序<

M4并*

的

口

选*

M5/

*

大

M6王

一

“

XXQ"“X

输入您的选择＜1F〉：

B中，

成绩管理系统的主界面：

武“G:\主程序.exe”

Weleoneto

Thestudentscoremanagesystem

输入您的选择“F〉：

学生成绩记录的输入：

输出学生成绩记录：

百“G:\主程序.exe”□1x

*充XXXXX-XXXXXXX充XXXXX*X*XLinkLiStxXXXXWMXxxXMMX"

；布丁病一1爸丁数季JSiTT

!1102：hu：82：92：93：

!1101!wang；88：78：89!

XXXXXXXXXXXXXXXXXXXXXXENDXXXXXXXXXXXXXXXXXXXXXX*

SSr%e

de『nt

co一

s3re一an

一

一

一

入

一

生

„„生

z记

录

出

记

录

生

H订

除

录

记

生

的

入

学

记

H录

新

个

出

订

“

“

八

x>XXXXXX

输入您的选择

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

|武"G:\主程序.exe_olx

请输入要删除的学生的学号：I。】

；学号；姓名；语文；数学；英语；

1101Mang88?889

您确定要删除该学生的记录吗V/N?y

学号为1101的学生记录己被删除.

Welcometo

Thestudentscoremanagesystem

1

2输出生生记录

3删除学生记录

4输入一个新的学生记录

5

d

插入新的学生成绩记录(插入学号为1103的学生记录)

(7)尚未解决的问题或改进方向

尚未解决的问题：该成绩管理系统还存在不少缺陷，而且它提供的功能也是

有限的，只能实现学生成绩的输入、输出、删除'插入。对于，学生成绩记录的

文件保存以及按学号、等的查询也是缺少的。还有就是，对于多个学生成绩的操

作也是不够的。

改进的方向：在时间许可的条件下，尽量的完善该系统的各种功能，同时也

应修改系统，让它更为人性化、简单化，被广大用户所接受。

(8)对软件的使用说明

该软件是属于比较低级的软件，只是包含了课程设计的要求的几个功能：输

入、输出、删除、插入。所以用户在使用的过程中肯定会受到一定的局限性、不

方便性，但由于时间的缘故，无法将软件做到尽善尽美。

2.项目二

(1)对设计任务容的概述

各种排序

任务：用程序实现插入法排序、选择法排序、起泡法改迸算法排序；

利用插入排序、选择法排序和冒泡法的改进算法，将用户随机输入的一列数

按递增的顺序排好。

输入的数据形式为任何一个正整数，大小不限。

输出的形式：数字大小逐个递增的数列。

(2)功能描述

该函数有以下几个功能：

1)对R[0..n-l]按递增有序进行直接插入排序

2)对R[0..n-1]按递增有序进行冒泡排序

3)对R[0..n-l]按递增有序进行直接选择排序

4)排序后的输出

5)调用所有排序，实现排序

(3)程序流程图

排序Sort()

退出

(4)详细设计

voidInsertSort(RecTypeR[],intn):对R[0..nT]按递增有序进行直接

插入排序

voidBubbleSort(RecTypeR[],intn):对R[0..n-1]按递增有序进行冒泡

排序

voidSelectSort(RecTypeR[],intn):对R[0..n-1]按递增有序进行直接

选择排序

voiddisp(RecTypeR[],intn):排序后的输出

voidSortO:调用所有排序,实现排序

(5)程序模块及其接口描述

该程序分为五个模块：

1.输入功能:voidSortO

建立一个数组存放用户在键盘上输入的关键字，在分别调用各种排序的函数，

对关键字进行排序。

2.直接插入排序功能•voidInsertSort(RecTypeR[],intn)

将后一个数与前一个数比较，将其插入到第一个比它大的大的数前面，其余数

字往后移一个位置。每次从无序表中取出第一个元素，把它插入到有序表的合适

位置，使有序表仍然有序。

3.冒泡排序功能:voidBubb1eSort(RecTypeR[],intn)

在排序过程中，执行完最后的排序后，虽然数据已全部排序完备，但程序无法判

断是否完成排序‘为了解决这一不足，可设置一个标志位exchange，将其初始

值设置为非0，表示被排序的表是一个无序的表，每一次排序开始前设置

exchange值为0，在进行数据交换时，修改exchange为非0。在新一轮排序开

始时，检查此标志，若此标志为0，表示上一次没有做过交换数据，则结束排序；

否则进行排序。

4,直接选择排序功能：voidSe1ectSort(RecTypeR[],intn)

在无序区里找最小的数，第i小的数字放在第i个位置上，与原来第i个位置上

的数字交换。

5.输出功能:voiddisp(RecTypeR[],intn)

(6)程序的揄入与输出描述

输入：要10个为数字的关键字；

输出：排序后新的序列。

(7)程序测试

揄入关键字，调用各种排序函数

|武"G:\主程序.exe”□X

请输入排序的关模字＜1。个数字)

893215678345510

直接插入排序：123781034555689

冒泡排序：123781034555689

直接选择排序：123781034555689

主菜单

成

系统

绩工

X理

各

种

晶

X序X

建

反

立

二

兴*

的

并

表

兴g*

"*

输入您的选择

(8)尚未解决的问题或改进方向

改进方向：虽然给出了它的各种排序的结果，但是没有它的箱子过程，

这是我的改进的方向，希望能将每种排序的过程也能展示给用户，来体现它

们的不同。

（9）对软件的使用说明

用户只需根据提示，在键盘上输入要排序的10个关键字。

3.项目三

（1）对设计任务容的概述

有序表的合并

要求输入有序表的数据，利用顺序表和链表结构分布完成两个有序表合并功

Ab

月匕，并揄出合并后的信息。

（2）功能描述

该程序有如下几个功能：

1）初始化顺序表

2）初始化链表

3）建立顺序表

4）尾插法建表

5）输出合并后的顺序表

6）输出合并后的单链表

7）合并顺序表

8）合并单链表

9）调用以上的函数，实现有序表的合并

（3）概要设计或程序流程图

初始化顺序初始化链表

表

建立.顺序表尾插法建表

合并顺序表合并单链表

结束

(4)详细设计

voidInitList(SqList*&L):初始化顺序表

voidInitListKLinkListl*&L):初始化链表

voidCreateListCSqList*&L,ElemTypea[],intn):建立顺序表

voidCreateListR(LinkListl槌L,ElemTypea[],intn):尾插法建表

voidDispListCSqList*L):输出合并后的顺序表

voidDispListKLinkListl札):输出合并后的单链表

voidUnionListCSqList*LA,SqList*LB,SqList*&LC):合并顺序表

voidUnionListKLinkListl*LA,LinkListl*LB,LinkListl*&LC):合并

单链表

voidUnionO:调用以上的函数，实现有序表的合并。

(5)程序模块及其接口描述

程序有以下几个模块：

1)初始化、建立顺序表

2)初始化、建立链表

3)输出合并后的表

4)合并表

(6)调试分析或程序测试

有序表的合并：

*了:注明exe”

J=：abc

bt]=：dgef

质序表存放有序表的合并

LI：abc

L2：dgef

胞并

L3：abcdgef

国链表存放有序表的合并

主菜单

系

成

工

统

*理

X1|X

2序

各

树

兴

兴3

“

建

合

一

隹

并

兴4

表

毒

兴5

输入您的选择＜lf):

(7)尚未解决的问题或改进方向

不足：不能重复使用程序。

(8)对软件的使用说明

用户只需根据界面的提示，采用对应的操作。

4•项目四

(1)对设计任务容的概述

建立二叉树，层序、先序、中序、后序遍历(用递归或非递归的方法都可

以)**

任务：

要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别

建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序

列的函数、输出个序遍历序•列的函数、揄出后序遍历序列的函数；

(2)功能描述

1)建立二叉树

2)输出二叉树

3)先序遍历非递归算法：

不为空时，访问根一左一右，采用递归的方法。

4)中序遍历非递归算法：

不为空时，访问左一根一右，采用递归的方法。

5)后序遍历非递归算法：

不为空时，访问左一右一根，采用递归的方法。

6)层序遍历：

运用队列，队列不空时，有左孩子将其入队，有右孩子将其入队，同时出队。

7)调用以上函数实现二叉树的各种遍历

(3)梢I要设计或程序流程图

开始

输入二叉树的按层结

点值

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

结束

(4)详细设计

voidCreateBTNodeCBTNode*&b,char*str)•建立二叉树

voidDispBTNode(BTNode*b):输出二叉树

voidPreOrder(BTNode*b)：先序遍历非递归算法

voidInOrder(BTNode*b):中序遍历非递归算法

voidPostOrder(BTNode米b):后序遍历非递归算法

voidLeve1Order(BTNode*b):层序遍历

(5)程序模块及其接口描述

(6)程序的输入与输出描述

输入二叉树的按层结点值；

输出二叉树先序遍历访问结点的顺序；输出二叉树中序遍历访问结点的顺序；

输出二叉树后序遍历法问结点的顺序；输出二叉树层次遍历访问结点的顺序；

(7)调试分析或程序测试

用户从键盘上输入要创建的二叉树结点：

c("G:\主程序.exe"

a<b<dGg>>,c<e,f>>

二叉树b的先序遍历序列abdgce£

二叉树b的中序遍历序列dgbaecf

二叉树b的后序遍历序列gdbefca

二叉树b的层次遍历序列abcdefg

主菜单

成

系统

膏靠

X1理*

各

2序

X二*

立

建

3反^

共*

表^

的

并

4盘

兴*

口

X5X

(8)尚未解决的问题或改进方向

改进方向：希望能将系统改进的更为人性化，让界面更舒适，操作更简单。

(9)对软件的使用说明

用户只需按照界面的提示，采取相应的措施，到时界面会提醒用户键盘输入。

5•项目五

(1)对设计任务容的概述

猴子选大王权

任务：一堆猴子都有编号，编号是1，2，3...用，这群猴子(m个)按照

1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这

样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

要求：

揄入数据：输入m,nin,n为整数,n<m

揄出形式：中文提示按照m个猴子，数n个数的方法，榆出为大王的猴子

是几号，建立一个函数来实现此功能

(2)需求分析或功能漏述

为猴子编号out，编号out=pass(pass为密码值)该猴子离圈，次数step++。

剩下的猴子继续次操作'直到次数51〃=猴子iiiuukey时结束。

(3)概要设计或程序流程图

开始

(结束)

(4)详细设计或源代码说明

为猴子编号out，编号out=pass(pass为密石马值)该猴子离圈，次数step++°

剩下的猴子继续次糅作，直到次数step=猴子monkey时结束。

函数intMonkey。实现了这一功能。

(5)程序模块及其接口描述

运用队列(环形队列)，编号:密码值入队；为猴子编号out，编号out=pass

(pass为密码值)，该猴子离圈，次数step++。剩下的猴子继续次操作，直到次

数step二猴子monkey时结束。

函数intMonk6y()实现了这一功能。

(6)程序的输入与输出描述

揄入数据：输入m,nm,n为整数»n<m

输出形式：中文提示按照m个猴子，数n个数的方法，输出为大王的猴子

是几号，建立一个函数来实现此功能。

(7)调试分析或程序测试

猴子数量8,密码值9(猴子数)密码值)

-lolX

c〈效据结构课程设计、主程序.exe-

XXMMXXXxxx猴子选大王XXXXXXXXXX

共有几只很子：8

密码数字：9

No.lout.

No.3out.

No.6out.

No.4out.

No.5out.

No.2out.

No.7out.

No.8out.

主菜单

1.成绩售理系统

2.答种排序

3.建立二叉树

4.有序表的合d

(8)尚未解决的问题或改进方向

不足：不能重复使用程序，如果数字大的话，输出繁琐。

(9)对软件的使用说明

用户只需根据软件界面的提示进行相关操作。

三•结论及体会

本学期，我学会了常用数据结构：数组（连续空间），栈（先进后出），队列

（先进先出），链表（指针），树（前驱、后继，根、叶子），图（点、边），堆（特

殊的树，根节点的值最大或最小）还有线性表存储结构：顺序存储结构和链式存

储，常用的排序算法。

在这一周里，自己用了C—Free做了一个程序，分别实现了学生成绩管理系

统、各种排序、有序表的合并、二又树的建立及遍历以及猴子选大王，通过本次

数据结构课程设计，我学习了很多课上没弄懂的动西，巩固了关于二叉树、栈、

链表等知识。

在设计程序时，虽然很用心的做，但还是遇到种种难题，通过上网查找资料、

图书馆查阅资料、问老用的方式，最终还是解决多数，虽然最后的程序不是很完

美，但是因为是通过自己的努力完成的，还是感觉很满意，也收获很大东西。

经过了这次课程设计，现在已经可以了解很多错误在英文里的提示，这对我来说

是一个突破性的进步，眼看着一个个错误通过自己的努力在我眼前消失，觉得很

是开心。在这一段努力学习的过程中，我的编程设计有了明显的提高，其实现在

想起来，收获还真是不少，虽然说以前非常不懂这门语言，在它上面花费了好多

心血，觉得它很难，是需用花费了大量的时间编写出来的。现在真正的明白了一

些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。只要努力

去学习，就会灵活的去应用它。

总之，通过这次的课程设计，我们收获匪浅，首先由衷感老师提供这样的一

个机会锻炼自己，感受到学来的知识不只是用来完成试卷的。一向习惯独立思考

的自己学会了积极的与别人交流，取长补短，共同进步。课程设计使自己发现考

试不是最重要的，最重要的是能运用所学的知识。在整个课程设计的学习过程中，

不再是学到知识解题，而是在实际运用时遇到什么学什么，重在把知识应用于实

际。

附录1:参考文献

[1]《数据结构教程（第3版）》，春葆，清华大学，2010

[2]《数据结构》，剑，清华大学»2011

[3]《数据结构（C语言版）》，严蔚敏吴伟民，清华大学，1997

[4]（DataStructuresUsingC数据结构（C语言版）》，RKrishnamoorthy'GIndirani

Kumaravel?清华大学，2009-9

[5]《C++数据结构与程序设计（美）RobertL.Kruse/AlexanderJ.Ryba著/钱丽萍译》，

清华大学，2004

[6]《计算机算法设计与分析（第2版）》，王晓东，电子工业，2004

附录2:部分源代码清单

#include<stdio.h>

#include<malloc.h>

#include<string.h>

#include<iostream>

#include<stdlib.h>

#defineLENsizeof(LinkList)

#defineMaxSize50

//\lz\lz\1/\A/\l/\lz51/\1/\1/51/\lz\lz\1/\t/si/\1/\lz\l/>1/\lz\Jz\lzxlz\i/51/\1/\t/51/51/\lz\lz\1/

//小/j\小/I*/TV/T\r(\/l\人小小小Zr\/T*/S<(\/T>/IV/IX/JV/(>Z(\/y\7l\

//成绩管理系统

typedefstructLNode/*定义单链表结点类型*/

charname[10];//

charnum[10];〃学号

intscore[3];

structLNode米next;

}LinkList;

LinkList*init()

(

returnNULL;/*返回空指针*/

)

LinkList"create。

{inti,s,k;

intj=0;

LinkList米head=NULL,配；/*定义函数.此函数带回一个指向链表头的指

针*/

systein(,'clsn);

printf(”\n请揄入您想输入的学生个数：");

scanf("W",&k);

for(j=0;j<k;j++)

{p=(LinkListx)malloc(LEN);/米开辟一个新的单元*/

if(p==NULL)/*如果指针p为空引

{printf(”\n输出存溢出.”)；外输出存溢出米/

return(head);/*返回头指针，下同*/

)

printf。输入学号：”)；

scanfC%s",p->num);

printfC输入:")；

scanf("%s",p->name);

printf("请分别输入语文、数学、英语的分数%dscores'll",3);/*开始

输入*/

for(i=0;i<3;i++)/*3门课程循环3次*/

do(

printf("score%d:n,i+1);

scanf("%d",&p->score[i]);

if(p->score[i]<0I|p->score[i]>100)/*确保成绩在0~100

之间*/

printfCDataerror,pleaseenteragain.\n");

)while(p->score[i]<0IIp->score[i]>100);

p->next=head;/米将头结点做为新输入结点的后继结点

head二p;/米新输入结点为新的头结点*/

return(head);

/*显示全部记录函数X/

voidprint(LinkList*head)

LinkList迎;

svsteinC'cls'*);

p二head;/*初值为头指针到

printf(u\n*****标********糕******札inkList**************料n")；

printfC\n");

printfC|学号I语文I数学I英语I\n");

printf(H\n");

while(p!=NULL)

printfCI%4s4sI%3dI%3dI%3dI\n",

p->num,p->nane,p->score[0],p->score[1],p->score⑵);

p=p->next;

printfC\n");

printf（u标米糕**格株粽秣*米糕*米糅END标称***标糕****秣*糕**料n"）；

/米删除记录函数次/

LinkList*Delete(LinkList米head)

LinkList*pl,*p2;/*pl为查找到要删除的结点指针，p2为其前躯指针*/

charc,s[6];/*s[6]用来存放学号,c用来输入字母米/

systemC'cls'1);

printf（”请输入要删除的学生的学号:

scanf("%s",s);

pl=p2=head;/米给pl和p2赋初值头指针*/

while(strcmp(pl->num,s)&&pl!=NULL)/*当记录的学号不是要

找的,或指针不为空时*/

{p2=pl;/*将pl指针值赋给p2作为pl的前驱指针*/

pl=pl->next;/*将pl指针指向下一条记录*/

if(strcmp(pl->num,s)==0)/*学号找到了*/

printfC'******，权******，**义***杆01)必**林********糅****秣**米米\11");

printf(H

-\n");

printfC1|学号||语文|数学|英语|\n");

printfC------------------------------------------------------\n");

printfCIMsI%4sI%3dI%3dI%3d

I\n",pl->num,pl->name,pl->score[0],pl->score[l],pl->score[2]);

printfC1'-------------------------------------------------------\n”)

printf(u*******株********糕**，****END*株********株*******糕**权\11

")；

printfC您确定要删除该学生的记录吗Y/N?”)；/*提示是否要删除，

输入Y删除,N则退出米/

for(;;)

{scanf("%cn,&c);

if(c==,n*||c==,N*)break;/*如果不删除，则跳出本循环*/

if(c==y,||c==Y,)

{

if(pl==head)/*若pl==head，说明被删结点是首结

占*/

head=pl->next;/*把第二个结点地址赋予head*/

else

p2->next=pl->next;

free(pl);/*否则将一下结点地址赋给前一结点地

址*/

printf("\n学号为%s的学生记录已被删除.\n”，s);

break：/*删除后就跳出循环*/

}

else

printf(”\n找不到学号为%s的学生记录.\n",s);/*找不到该结点*/

return(head);

}

〃插入

LinkList*Insert(LinkList*head)

(

intk;〃在表中第k个位置插入

printf("请输入插入的位置:");

scanf("W",&k);

intj=0,i=0;

LinkList*pl,*p2;/*pl为查找到要删除的结点指针»p2为其前驱指针*/

charN[10],s[10];/运[10]用来存放,N[10]用来存放学号*/

intscore[3];

system。c1s");

printf("输入学号：”)；

scanf("%s",N);

printf("输入:")；

scanf("%s",s);

printf("请分别输入语文、数学、英语的分数%dscores'n",3);/次开始输

入*/

for(i=0;i<3;i++)/米3门课程循环3次米/

(

do{

printfCscore%d:",i+1);

scanfC%d",&score[i]);

if(score[i]<011score]i]>100)/米确保成绩在0T00之间*/

printfCDataerror,pleaseenteragain.\n");

}while(score[i]<0||scorefi]>100);

pl=head;/*给pl赋初值头指针