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

上海应用技术学院课程设计报告
课程名称 《数据结构课程设计》
设计题目 猴子选大王；建立二叉树；各种排序；有序表的合并；成绩管理系统；
院系 计算机科学与信息工程 专业计算机科学与技术 班级
姓名 学号 指导教师 日期

一. 目的与要求
1. 巩固和加深对常见数据结构的理解和掌握
2. 掌握基于数据结构进行算法设计的基本方法
3. 掌握用高级语言实现算法的基本技能
4. 掌握书写程序设计说明文档的能力
5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力

二. 课程设计内容说明
1. 项目一
(1) 对设计任务内容的概述
学生成绩管理**
任务：要求实现对学生资料的录入、浏览、插入和删除等功能。
输入：设学生成绩以记录形式存储，每个学生记录包含的信息有：学号和各门课程的成绩，设学生成绩至少3门以上。存储结构：采用线性链式结构。

(2) 详细设计
LinkList *create()：输入学生成绩记录函数；
void print(LinkList *head)：显示全部记录函数
LinkList *Delete(LinkList *head)：删除记录函数
LinkList *Insert(LinkList *head)：插入记录函数
void menu_select()：菜单选择
void ScoreManage()：函数界面

(3) 程序流程图
3．删除学生记录
4．插入学生记录
1．输入学生记录
输入n（0<n<6）
主界面
2．输出学生记录
退出
学生成绩管理系统
5．退出
判断n
n=5
n=1、2、3、4

(4) 程序模块及其接口描述
该程序可以分为以下几个模块：
1、菜单选择：void menu_select();
提供五种可以选择的操作，在main函数中通过switch语句调用菜单menu_select()函数，进入不同的功能函数中完成相关操作。
2、输入功能：LinkList *create();
通过一个for循环语句的控制，可以一次完成无数条记录的输入。并将其存入链表。
3、输出功能：void print(LinkList *head);
通过一个while的循环控制语句，在指针p!=NULL时，完成全部学生记录的显示。知道不满足循环语句，程序再次回到菜单选择功能界面。
4、删除功能：LinkList *Delete(LinkList *head);
按想要删除的学生的学号首先进行查找，通过指针所指向结点的下移来完成，如果找到该记录，则完成前后结点的连接，同时对以查找到的结点进行空间的释放，最后完成对某个学生记录进行删除，并重新存储。
5、插入功能：LinkList *Insert(LinkList *head)；
输入你想插入的位置，通过指针所指向结点的下移，找到该位置，将该新的学生记录插入到该结点，并对该结点后面的指针下移。链表长度加一，重新存储。

(5) 程序的输入与输出描述
输入：调用LinkList *create()函数，输入学生的姓名、学号、三门功课的成绩；
输出：调用void print(LinkList *head)函数，输出学生的记录。

(6) 程序测试
主菜单：

成绩管理系统的主界面：

学生成绩记录的输入：

输出学生成绩记录：

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

插入新的学生成绩记录（插入学号为1103的学生记录）

(7) 尚未解决的问题或改进方向
尚未解决的问题：该成绩管理系统还存在不少缺陷，而且它提供的功能也是有限的，只能实现学生成绩的输入、输出、删除、插入。对于，学生成绩记录的文件保存以及按学号、姓名等的查询也是缺少的。还有就是，对于多个学生成绩的操作也是不够的。
改进的方向：在时间许可的条件下，尽量的完善该系统的各种功能，同时也应修改系统，让它更为人性化、简单化，被广大用户所接受。

(8) 对软件的使用说明
该软件是属于比较低级的软件，只是包含了课程设计的要求的几个功能：输入、输出、删除、插入。所以用户在使用的过程中肯定会受到一定的局限性、不方便性，但由于时间的缘故，无法将软件做到尽善尽美。

2. 项目二
(1) 对设计任务内容的概述
各种排序
任务：用程序实现插入法排序、选择法排序、起泡法改进算法排序；
利用插入排序、选择法排序和冒泡法的改进算法,将用户随机输入的一列数按递增的顺序排好。
输入的数据形式为任何一个正整数，大小不限。
输出的形式：数字大小逐个递增的数列。
(2) 功能描述
该函数有以下几个功能：
1) 对R[0..n-1]按递增有序进行直接插入排序
2) 对R[0..n-1]按递增有序进行冒泡排序
3) 对R[0..n-1]按递增有序进行直接选择排序
4) 排序后的输出
5)调用所有排序，实现排序

(3) 程序流程图
直接插入排序InsertSort()
退出
排序Sort（）
直接选择排序SelectSort()
冒泡排序BubbleSort()

(4) 详细设计
void InsertSort(RecType R[],int n)：对R[0..n-1]按递增有序进行直接插入排序
void BubbleSort(RecType R[],int n)：对R[0..n-1]按递增有序进行冒泡排序
void SelectSort(RecType R[],int n)：对R[0..n-1]按递增有序进行直接选择排序
void disp(RecType R[],int n)：排序后的输出
void Sort()：调用所有排序，实现排序

(5) 程序模块及其接口描述
该程序分为五个模块:
1.输入功能：void Sort()
建立一个数组存放用户在键盘上输入的关键字，在分别调用各种排序的函数，对关键字进行排序。

2.直接插入排序功能：void InsertSort(RecType R[],int n)
将后一个数与前一个数比较，将其插入到第一个比它大的大的数前面，其余数字往后移一个位置。每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

3.冒泡排序功能：void BubbleSort(RecType R[],int n)
在排序过程中，执行完最后的排序后，虽然数据已全部排序完备，但程序无法判断是否完成排序，为了解决这一不足，可设置一个标志位exchange，将其初始值设置为非0，表示被排序的表是一个无序的表，每一次排序开始前设置exchange值为0，在进行数据交换时，修改exchange为非0。在新一轮排序开始时，检查此标志，若此标志为0，表示上一次没有做过交换数据，则结束排序；否则进行排序。

4.直接选择排序功能：void SelectSort(RecType R[],int n)
在无序区里找最小的数，第i小的数字放在第i个位置上，与原来第i个位置上的数字交换。

5.输出功能：void disp(RecType R[],int n)

(6) 程序的输入与输出描述
输入：要求是10个为数字的关键字；
输出：排序后新的序列。

(7) 程序测试
输入关键字，调用各种排序函数

(8) 尚未解决的问题或改进方向
改进方向：虽然给出了它的各种排序的结果，但是没有它的箱子过程，
这是我的改进的方向，希望能将每种排序的过程也能展示给用户，来体现它们的不同。

(9) 对软件的使用说明
用户只需根据提示，在键盘上输入要排序的10个关键字。

3. 项目三
(1) 对设计任务内容的概述
有序表的合并
要求输入有序表的数据，利用顺序表和链表结构分布完成两个有序表合并功能，并输出合并后的信息。

(2) 功能描述
该程序有如下几个功能：
1) 初始化顺序表
2) 初始化链表
3) 建立顺序表
4) 尾插法建表
5) 输出合并后的顺序表
6) 输出合并后的单链表
7) 合并顺序表
8) 合并单链表
9) 调用以上的函数，实现有序表的合并

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

初始化链表
初始化顺序表

建立顺序表
尾插法建表

合并顺序表
合并单链表

输出

结束

(4) 详细设计
void InitList(SqList *&L)：初始化顺序表
void InitList1(LinkList1 *&L)：初始化链表
void CreateList(SqList *&L,ElemType a[],int n)：建立顺序表
void CreateListR(LinkList1 *&L,ElemType a[],int n)：尾插法建表
void DispList(SqList *L)：输出合并后的顺序表
void DispList1(LinkList1 *L)：输出合并后的单链表
void UnionList(SqList *LA,SqList *LB,SqList *&LC)：合并顺序表
void UnionList1(LinkList1 *LA,LinkList1 *LB,LinkList1 *&LC)：合并单链表
void Union()：调用以上的函数，实现有序表的合并。

(5) 程序模块及其接口描述
程序有以下几个模块：
1) 初始化、建立顺序表
2) 初始化、建立链表
3) 输出合并后的表
4) 合并表

(6) 调试分析或程序测试
有序表的合并：

(7) 尚未解决的问题或改进方向
不足：不能重复使用程序。

(8) 对软件的使用说明
用户只需根据界面的提示，采用对应的操作。

4．项目四
(1)对设计任务内容的概述
建立二叉树，层序、先序、中序、后序遍历（ 用递归或非递归的方法都可以）**
任务：
要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数；

(2)功能描述
1) 建立二叉树
2) 输出二叉树
3) 先序遍历非递归算法：
不为空时，访问根--左--右，采用递归的方法。
4) 中序遍历非递归算法：
不为空时，访问左--根--右，采用递归的方法。
5) 后序遍历非递归算法：
不为空时，访问左--右--根，采用递归的方法。
6) 层序遍历：
运用队列，队列不空时，有左孩子将其入队，有右孩子将其入队，同时出队。
7） 调用以上函数实现二叉树的各种遍历

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

输入二叉树的按层结点值

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

结束

(4)详细设计
void CreateBTNode(BTNode * &b,char *str)：建立二叉树
void DispBTNode(BTNode *b)：输出二叉树
void PreOrder(BTNode *b)：先序遍历非递归算法
void InOrder(BTNode *b)：中序遍历非递归算法
void PostOrder(BTNode *b)：后序遍历非递归算法
void LevelOrder(BTNode *b)：层序遍历

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

(6)程序的输入与输出描述
输入二叉树的按层结点值；
输出二叉树先序遍历访问结点的顺序；输出二叉树中序遍历访问结点的顺序；
输出二叉树后序遍历访问结点的顺序；输出二叉树层次遍历访问结点的顺序；

(7)调试分析或程序测试
用户从键盘上输入要创建的二叉树结点：

(8)尚未解决的问题或改进方向
改进方向：希望能将系统改进的更为人性化，让界面更舒适，操作更简单。
(9)对软件的使用说明
用户只需按照界面的提示，采取相应的措施，到时界面会提醒用户键盘输入。
5．项目五
（1）对设计任务内容的概述
猴子选大王**
任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
要求：
输入数据：输入m,n m,n 为整数，n<m
输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能

（2）需求分析或功能描述
为猴子编号out，编号out=pass（pass为密码值），该猴子离圈，次数step++。剩下的猴子继续次操作，直到次数step=猴子monkey时结束。

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

开始

输入猴子的数量和密码值

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

N

次数=猴子数

Y

结束

（4）详细设计或源代码说明
为猴子编号out，编号out=pass（pass为密码值），该猴子离圈，次数step++。剩下的猴子继续次操作，直到次数step=猴子monkey时结束。
函数int Monkey()实现了这一功能。

（5）程序模块及其接口描述
运用队列（环形队列），编号=密码值 入队；为猴子编号out，编号out=pass（pass为密码值），该猴子离圈，次数step++。剩下的猴子继续次操作，直到次数step=猴子monkey时结束。
函数int Monkey()实现了这一功能。

（6）程序的输入与输出描述
输入数据：输入m,n m,n 为整数，n<m
输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能。

（7）调试分析或程序测试
猴子数量8,密码值9（猴子数>密码值）

（8）尚未解决的问题或改进方向
不足：不能重复使用程序，如果数字大的话，输出繁琐。

（9）对软件的使用说明
用户只需根据软件界面的提示进行相关操作。

三． 结论及体会
本学期，我学会了常用数据结构：数组（连续空间），栈（先进后出），队列（先进先出），链表（指针），树（前驱、后继，根、叶子），图（点、边），堆（特殊的树，根节点的值最大或最小）还有线性表存储结构：顺序存储结构和链式存储，常用的排序算法。
在这一周里，自己用了C—Free做了一个程序，分别实现了学生成绩管理系统、各种排序、有序表的合并、二叉树的建立及遍历以及猴子选大王，通过本次数据结构课程设计，我学习了很多课上没弄懂的动西，巩固了关于二叉树、栈、链表等知识。
在设计程序时，虽然很用心的做，但还是遇到种种难题，通过上网查找资料、图书馆查阅资料、问老师的方式，最终还是解决多数，虽然最后的程序不是很完美，但是因为是通过自己的努力完成的，还是感觉很满意，也收获很大东西。
经过了这次课程设计，现在已经可以了解很多错误在英文里的提示，这对我来说是一个突破性的进步，眼看着一个个错误通过自己的努力在我眼前消失，觉得很是开心。在这一段努力学习的过程中，我的编程设计有了明显的提高，其实现在想起来，收获还真是不少，虽然说以前非常不懂这门语言，在它上面花费了好多心血，觉得它很难，是需用花费了大量的时间编写出来的。现在真正的明白了一些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。只要努力去学习，就会灵活的去应用它。
总之，通过这次的课程设计，我们收获匪浅，首先由衷感谢老师提供这样的一个机会锻炼自己，感受到学来的知识不只是用来完成试卷的。一向习惯独立思考的自己学会了积极的与别人交流，取长补短，共同进步。课程设计使自己发现考试不是最重要的，最重要的是能运用所学的知识。在整个课程设计的学习过程中，不再是学到知识解题，而是在实际运用时遇到什么学什么，重在把知识应用于实际。

附录1：参考文献
[1] 《数据结构教程（第3版）》，李春葆，清华大学出版社，2010
[2]《数据结构》，杨剑，清华大学出版社，2011
[3]《数据结构(C语言版)》，严蔚敏 吴伟民，清华大学出版社，1997
[4]《Data Structures Using C数据结构（C语言版）》，R Krishnamoorthy、G Indirani Kumaravel，清华大学出版社，2009-9
[5]《C++数据结构与程序设计 （美）Robert L.Kruse/Alexander J.Ryba著/钱丽萍译》，
清华大学出版社，2004
[6]《计算机算法设计与分析（第2版）》，王晓东， 电子工业出版社， 2004

附录2：部分源代码清单

#include <stdio.h>
#include <malloc.h>
#include<string.h>
#include <iostream>
#include <stdlib.h>
#define LEN sizeof(LinkList)
#define MaxSize 50

//************************************************************
//成绩管理系统
typedef struct LNode /*定义单链表结点类型*/
{
char name[10]; //姓名
char num[10]; //学号
int score[3];
struct LNode *next;
} LinkList;

LinkList *init()
{
return NULL; /*返回空指针*/
}

LinkList *create()
{ int i,s,k;
int j=0;
LinkList *head=NULL,*p; /* 定义函数.此函数带回一个指向链表头的指针*/
system("cls");
printf("\n请输入您想输入的学生个数：");
scanf("%d",&k);
for(j=0;j<k;j++)
{ p=(LinkList *)malloc(LEN); /*开辟一个新的单元*/
if(p==NULL) /*如果指针p为空*/
{ printf("\n输出内存溢出."); /*输出内存溢出*/
return (head); /*返回头指针,下同*/
}
printf("输入学号:");
scanf("%s",p->num);
printf("输入姓名:");
scanf("%s",p->name);
printf("请分别输入语文、数学、英语的分数 %d scores\n",3);/*开始输入*/
for(i=0;i<3;i++) /*3门课程循环3次*/
{
do{
printf("score%d:",i+1);
scanf("%d",&p->score[i]);
if(p->score[i]<0 || p->score[i]>100) /*确保成绩在0~100之间*/
printf("Data error,please enter again.\n");
}while(p->score[i]<0 || p->score[i]>100);
}
p->next=head; /*将头结点做为新输入结点的后继结点*/
head=p; /*新输入结点为新的头结点*/
}
return(head);
}

/* 显示全部记录函数*/
void print(LinkList *head)
{
LinkList *p;
system("cls");
p=head; /*初值为头指针*/
printf("\n************************LinkList***************\n");
printf("-------------------------------------------------\n");
printf("| 学号 | 姓名 | 语文 | 数学 | 英语 | \n");
printf("-------------------------------------------------\n");
while(p!=NULL)
{
printf("| %4s | %-4s | %3d | %3d | %3d |\n", p->num,p->name,p->score[0],p->score[1],p->score[2]);
p=p->next;
}
printf("-------------------------------------------------\n");
printf("***********************END***********************\n");
}

/*删除记录函数*/
LinkList *Delete(LinkList *head)
{
LinkList *p1,*p2; /*p1为查找到要删除的结点指针，p2为其前驱指针*/
char c,s[6]; /*s[6]用来存放学号,c用来输入字母*/
system("cls");
printf("请输入要删除的学生的学号: ");
scanf("%s",s);
p1=p2=head; /*给p1和p2赋初值头指针*/
while(strcmp(p1->num,s) && p1 != NULL) /*当记录的学号不是要找的，或指针不为空时*/
{ p2=p1; /*将p1指针值赋给p2作为p1的前驱指针*/
p1=p1->next; /*将p1指针指向下一条记录*/
}
if(strcmp(p1->num,s)==0) /*学号找到了*/
{ printf("***********************FOUND************************\n");
printf("-----------------------------------------------------------\n");
printf("| 学号 | 姓名 | 语文 | 数学 | 英语 |\n");
printf("-------------------------------------------------\n");
printf("| %4s | %4s | %3d | %3d | %3d |\n",p1->num,p1->name,p1->score[0],p1->score[1],p1->score[2]);
printf("-----------------------------------------------------\n");
printf("**************************END**************************\n");
printf("您确定要删除该学生的记录吗 Y/N ?"); /*提示是否要删除,输入Y删除,N则退出*/
for(;;)
{ scanf("%c",&c);
if(c=='n'||c=='N') break; /*如果不删除,则跳出本循环*/
if(c=='y'||c=='Y')
{
if(p1==head) /*若p1==head，说明被删结点是首结点*/
head=p1->next; /*把第二个结点地址赋予head*/
else
p2->next=p1->next;
free(p1); /*否则将一下结点地址赋给前一结点地址*/
printf("\n学号为 %s 的学生记录已被删除.\n",s);
break; /*删除后就跳出循环*/
}
}
}
else
printf("\n找不到学号为 %s 的学生记录.\n",s); /*找不到该结点*/
return(head);
}
//插入
LinkList *Insert(LinkList *head)
{
int k; //在表中第k个位置插入
printf("请输入插入的位置：");
scanf("%d",&k);
int j=0,i=0;
LinkList *p1,*p2; /*p1为查找到要删除的结点指针，p2为其前驱指针*/
char N[10],s[10]; /*s[10]用来存放姓名,N[10]用来存放学号*/
int score[3];
system("cls");
printf("输入学号:");
scanf("%s",N);
printf("输入姓名:");
scanf("%s",s);
printf("请分别输入语文、数学、英语的分数 %d scores\n",3);/*开始输入*/
for(i=0;i<3;i++) /*3门课程循环3次*/
{
do{
printf("score%d:",i+1);
scanf("%d",&score[i]);
if(score[i]<0 || score[i]>100) /*确保成绩在0~100之间*/
printf("Data error,please enter again.\n");
}while(score[i]<0 || score[i]>100);
}
p1=head; /*给p1赋初值头指针*/
while(j<k-1&& p1 != NULL)
{ j++;
p1=p1->next; /*将p1指针指向下一条记录*/
}
if(p1==NULL) return 0;
else
{ p2=(LinkList *)malloc(sizeof(LinkList));
strcpy(p2->num,N);
strcpy(p2->name,s);
for(i=0;i<3;i++)
p2->score[i]=score[i];
p2->next=p1->next;
p1->next=p2;

}
}

void menu_select()
{ printf("\n\n\n");
printf("****************************************************\n");
printf("\t Welcome to \n");
printf("\t The student score manage system \n");
printf("**********************MENU**************************\n");
printf("\t\t1. 输入学生记录\n"); /*输入学生成绩记录*/
printf("\t\t2. 输出学生记录\n"); /*显示*/
printf("\t\t3. 删除学生记录\n"); /*删除*/
printf("\t\t4. 插入一个新的学生记录\n"); /*插入*/
printf("\t\t5. 退出\n"); /*退出*/
printf("****************************************************\n");
}

/*主函数界面*/
void ScoreManage()
{ LinkList *head,New;
int i,n;
head=init(); /*链表初始化,使head的值为NULL*/
menu_select();
do{
printf("\n\t\t输入您的选择(1~5):");
scanf("%d",&n);
}while(n<1||n>5);
for(;;) /*循环无限次*/
{ switch(n)
{
case 1:head=create();break;
case 2:print(head);break;
case 3:head=Delete(head);break;
case 4:head=Insert(head);break;
case 5:return; /*如菜单返回值为9则程序结束*/
}
menu_select();
printf("\n\t\t\t输入您的选择(1~5):");
scanf("%d",&n);

}
}

//************************************************************
//各种排序
typedef int KeyType; /*定义关键字类型*/
typedef char InfoType[10];
typedef struct /*记录类型*/
{
KeyType key; /*关键字项*/
InfoType data; /*其他数据项,类型为InfoType*/
} RecType; /*排序的记录类型定义*/

void InsertSort(RecType R[],int n) /*对R[0..n-1]按递增有序进行直接插入排序*/
{
int i,j;
RecType tmp;
for (i=1;i<n;i++)
{
tmp=R[i];
j=i-1; /*从右向左在有序区R[0..i-1]中找R[i]的插入位置*/
while (j>=0 && tmp.key<R[j].key)
{
R[j+1]=R[j]; /*将关键字大于R[i].key的记录后移*/
j--;
}
R[j+1]=tmp; /*在j+1处插入R[i]*/
}
}

void BubbleSort(RecType R[],int n)
{ int i,j,exchange;
RecType tmp;
for(i=0;i<n-1;i++)
{ exchange=0;
for(j=n-1;j>i;j--)
if(R[j].key<R[j-1].key)
{ tmp=R[j];
R[j]=R[j-1];
R[j-1]=tmp;
exchange=1;
}
if(exchange==0) return ;
}
}

void SelectSort(RecType R[],int n)
{ int i,j,k;
RecType tmp;
for(i=0;i<n-1;i++)
{ k=i;
for(j=i+1;j<n;j++)
if(R[j].key<R[k].key)
k=j;
if(k!=i)
{ tmp=R[i];
R[i]=R[k];
R[k]=tmp;
}
}
}

void disp(RecType R[],int n)
{ int i;
for (i=0;i<n;i++)
printf("%d ",R[i].key);
}

void Sort()
{
int i,n=10,k;
RecType R[MaxSize];
KeyType a[10];
printf("请输入排序的关键字(10个数字)\n");

for (i=0;i<n;i++)
scanf("%d",&a[i]);
for (i=0;i<n;i++)
R[i].key=a[i];

printf("\n\n直接插入排序 :");
InsertSort(R,n);
disp(R,n);

printf("\n\n冒泡排序 :");
BubbleSort(R,n);
disp(R,n);

printf("\n\n直接选择排序 :");
SelectSort(R,n);
disp(R,n);
}

//************************************************************
//建立二叉树
typedef char ElemType;
typedef struct node
{
ElemType data; /*数据元素*/
struct node *lchild; /*指向左孩子结点*/
struct node *rchild; /*指向右孩子结点*/
} BTNode;

void CreateBTNode(BTNode * &b,char *str)
{

BTNode *St[MaxSize],*p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL; /*建立的二叉树初始时为空*/
ch=str[j];
while (