第一篇：数据结构课程设计
课程设计说明书
设计名称： 数据结构课程设计
题 目： 设计五 ：二叉树的相关操作
学生姓名： 专 业： 计算机科学与技术 班 级： 学 号： 指导教师： 日 期： 2012 年 3 月 5 日
课程设计任务书
计算机科学与技术 专业 年级 班
一、设计题目
设计五 二叉树的相关操作
二、主要内容
建立二叉树，并对树进行相关操作。
三、具体要求
1)利用完全二叉树的性质建立一棵二叉树。（层数不小于4层）2)统计树叶子结点的个数。3)求二叉树的深度。
4)能够输出用前序，中序，后序对二叉树进行遍历的遍历序列。
四、进度安排
依照教学计划，课程设计时间为：2周。
本设计要求按照软件工程的基本过程完成设计。建议将时间分为三个阶段：第一阶段，根据题目要求，确定系统的总体设计方案：即系统包括哪些功能模块，每个模块的实现算法，并画出相应的流程图．同时编写相应的设计文档；第二阶段，根据流程图编写程序代码并调试，再将调试通过的各个子模块进行集成调试；第三阶段，归纳文档资料，按要求填写在《课程设计说明书》上，并参加答辩。三个阶段时间分配的大概比例是：35: 45: 20。
五、完成后应上交的材料
本课程设计要求按照学校有关规范的要求完成，在课程设计完成后需要提交的成果和有关文档资料包括课程设计的说明书，课程设计有关源程序及可运行程序（含运行环境）。其中课程设计说明书的格式按学校规范(见附件)，其内容不能过于简单，必须包括的内容有：
1、课程设计的基本思想，系统的总功能和各子模块的功能说明；
2、课程设计有关算法的描述，并画出有关算法流程图；
3、源程序中核心代码的说明。
4、本课程设计的个人总结，主要包括以下内容：
（1）课程设计中遇到的主要问题和解决方法；
（2）你的创新和得意之处；
（3）设计中存在的不足及改进的设想；
（4）本次课程设计的感想和心得体会。
5、源代码要求在关键的位置有注释，增加程序的可读性。程序结构和变量等命名必须符合有关软件开发的技术规范（参见有关文献）。
此外，填写在《课程设计说明书》中，必须根据要求认真填写课程设计任务书，排版要求整齐，美观，打印后与课程设计说明书封面一起装订好，并于本学期第6周星期1下午前交到致用楼5楼。
六、总评成绩
指导教师 签名日期 年 月 日
系 主 任 审核日期 年 月 日 佛山科学技术学院课程设计用纸
目 录
一、总体思想„„„„„„„„„„„„„„„„„„„„„„6 1.1基本思想„„„„„„„„„„„„„„„„„„„„„6 1.2系统的总功能„„„„„„„„„„„„„„„„„„„6 1.3各子模块的功能说明„„„„„„„„„„„„„„„„6 1.3.1 结构体部分„„„„„„„„„„„„„„„„„„„„„„6 1.3.2主函数部分„„„„„„„„„„„„„„„„„„„„„„6 1.3.3子函数部分„„„„„„„„„„„„„„„„„„„„„„6
二、具体内容„„„„„„„„„„„„„„„„„„„„„„6 2.1 对应模块的算法流程图„„„„„„„„„„„„„„„6 2.1.1总的设计思想流程图„„„„„„„„„„„„„„„„„„7 2．1.2创建二叉树函数流程图„„„„„„„„„„„„„„„„„7 2.1.3统计叶子数函数流程图„„„„„„„„„„„„„„„„„8 2.1.4计算二叉树深度函数流程图„„„„„„„„„„„„„„„8 2.1.5前序遍历函数流程图„„„„„„„„„„„„„„„„„„9 2.1.6中序遍历函数流程图„„„„„„„„„„„„„„„„„„9 2.1.7后序遍历函数流程图„„„„„„„„„„„„„„„„„„10 2.2课程设计的算法描述„„„„„„„„„„„„„„„„10 2.3程序运行情况截图„„„„„„„„„„„„„„„„„16 2.3.1程序运行的目录以及创建二叉树操作：„„„„„„„„„„16
2.3.2计算二叉树叶子数和深度的相关操作：„„„„„„„„„„17 2.3.3对二叉树分别进行前序，中序和后序遍历的情况：„„„„„18 2.3.4选择错误及结束操作的运行情„„„„„„„„„„„„„„18
2.4程序备注„„„„„„„„„„„„„„„„„„„„„19
三、源程序中核心代码的说明„„„„„„„„„„„„„„„19 3.1总设计思想说明„„„„„„„„„„„„„„„„„„19 3.2创建二叉树函数说明„„„„„„„„„„„„„„„„19 3.3统计叶子数函数说明„„„„„„„„„„„„„„„„20 佛山科学技术学院课程设计用纸
3.4计算二叉树深度函数说明„„„„„„„„„„„„„„20 3.5前序遍历函数说明„„„„„„„„„„„„„„„„„20 3.6中序遍历函数说明„„„„„„„„„„„„„„„„„20 3.7后序遍历函数说明„„„„„„„„„„„„„„„„„21
四、个人总结„„„„„„„„„„„„„„„„„„„„„„21 4.1课程设计中遇到的问题„„„„„„„„„„„„„„„21 4.2对应问题的解决办法„„„„„„„„„„„„„„„„22 4.3程序中的得意之处„„„„„„„„„„„„„„„„„23 4.4设计中存在的不足及改进方法„„„„„„„„„„„„23 4.5设计中的感想以及心得体会„„„„„„„„„„„„„30
佛山科学技术学院课程设计用纸
一、总体思想
1.1基本思想
基本思想是利用完全二叉树的性质，用数组去创建一棵完全二叉树，再用函数调用去调用去调用相应的函数实现选项对应的操作。1.2系统的总功能
本系统的主要功能是为用户提供一个选择操作的菜单目录，并且实现对应选项的功能，具体功能有如下几点：
1、创建二叉树
2、统计叶子个数
3、求二叉树的深度
4、前序遍历输出列表
5、中序遍历输出列表
6、后序遍历输出序列
7、退出操作
1.3各子模块的功能说明
本程序主要分为三大子模块： 1.3.1 结构体部分
BiTNode的结构体包含权值，左孩子存放地址和右孩子存放地址，是一个为了存放二叉树结点信息所创建的结构体。1.3.2主函数部分
该模块主要是实现对其他操作的函数调用的功能。1.3.3子函数部分
部分是实现对应子函数的操作，有：创建二叉树、统计叶子个数、求二叉树的深度、前序遍历输出列表、中序遍历输出列表和后序遍历输出序列的功能。
二、具体内容
2.1对应模块的算法流程图 2.1.1总的设计思想流程图
2．1.2创建二叉树函数流程图
2.1.3统计叶子数函数流程图
2.1.4计算二叉树深度函数流程图 2.1.5前序遍历函数流程图
2.1.6中序遍历函数流程图 2.1.7后序遍历函数流程图
2.2课程设计的算法描述 #include
int i,j;printf(“需要输入权值个数：n”);scanf(“%d”,&j);if(j<8)//判断二叉树是否达到4层
{ printf(“错误：二叉树的层数少于4层！n”);
return;} printf(“开始输入权值：n”);for(i=1;i<=j;i=i+1)//权值的录入
{
scanf(“%d”,&tree[i].c);
tree[i].lchild=2*i;
tree[i].rchild=2*i+1;
} printf(“成功创建二叉树n”);} int leaves()//统计叶子个数函数 { int l,i;l=0;for(i=1;tree[i].c!=NULL;i++)//计算二叉树结点的个数
{
l++;} if((l%2))//判断结点的奇偶性从而计算叶子的个数 {
return(((l-1)/2)+1);} else
return(l/2);} int deep()//求二叉树的深度
{ int d,i,sum;sum=1;for(i=1;tree[i].c!=NULL;i++);//计算二叉树结点的个数
for(d=1;sum<=i;d++)//求出二叉树的深度
{
if(d!=1)
{
sum=sum+sum*2;
} } return(d-1);} void qian(int a)//前序遍历输出列表 { if(tree[a].c!=NULL)//判断当前结点是否有值，若有执行如下操作，若无则返回上一层
{
printf(“%d,”,tree[a].c);
//首先输出当前结点（根节点）的权值
qian((a*2));
//递归调用，用当前结点的左孩子作根节点重复当前函数的操作
qian((a*2+1));
//递归调用，用当前结点的右孩子作根节点重复当前函数的操作 } else return;
} void zhong(int a)//中序遍历输出列表 { if(tree[2*a].c!=NULL)//首先判断当前结点的左孩子是否为空，不是就进行递归调用，用当前结点的左孩子作根节点重复当前函数的操作
{
} printf(“%d,”,tree[a].c);//输出当前结点的权值
if(tree[2*a+1].c!=NULL)//判断当前结点的右孩子是否为空，不是就进行递归调用，用当前结点的右孩子作根节点重复当前函数的操作
{
} } void hou(int a)//后序遍历输出序列 { if(tree[2*a].c!=NULL)//判断当前结点的左孩子是否为空，不是就进行递归调用，用当前结点的左孩子作根节点重复当前函数的操作
{
} if(tree[2*a+1].c!=NULL)//判断当前结点的右孩子是否为空，不是就进行递归调用，用当前结点的右孩子作根节点重复当前函数的操作 hou((2*a));zhong((2*a+1));zhong((2*a));13 {
hou((2*a+1));} printf(“%d,”,tree[a].c);//输出当前结点的权值 } void main(){ int d,l,i;i=10;printf(“******************目录******************n”);printf(“
1、创建二叉树n”);printf(“
2、统计叶子个数n”);printf(“
3、求二叉树的深度n”);printf(“
4、前序遍历输出列表n”);printf(“
5、中序遍历输出列表n”);printf(“
6、后序遍历输出序列n”);printf(“0、退出操作n”);printf(“*****************************************n”);while(i!=0){
printf(“选择操作：n”);
scanf(“%d”,&i);
if(i==0)
{
break;
}
else if(i==1){ 14 printf(“开始创建二叉树(层数不少于4层)n”);creat();} else if(i==2){ l=leaves();printf(“叶子个数为：%dn”,l);} else if(i==3){ d=deep();printf(“二叉树的深度是%dn”,d);} else if(i==4){ printf(“用前序遍历输出的结果是：n”);qian(1);printf(“n”);} else if(i==5){ printf(“用中序遍历输出的结果是：n”);zhong(1);printf(“n”);} else if(i==6){ printf(“用后序遍历输出的结果是：n”);hou(1);
} } printf(“n”);else printf(“错误：没有该操作！n”);printf(“欢迎使用！n”);}
2.3程序运行情况截图
2.3.1程序运行的目录以及创建二叉树操作：
本程序一开始会弹出一个目录，里面有七种操作供用户选择。此处是选择创建二叉树的操作。本程序要求创建的二叉树一定要在4层或者是以上的层数才可以成功创建，当条件不符合的时候会弹出错误的消息并且提醒用户不满足的原因。如下分别是创建不成功和成功创建的运行情况：
2.3.2计算二叉树叶子数和深度的相关操作：
2.3.3对二叉树分别进行前序，中序和后序遍历的情况：
2.3.4选择错误及结束操作的运行情况：
当用户选择到菜单栏中没有的选项时，会提示错误信息。2.4程序备注
程序创建结点数的上限是：1000个。
三、源程序中核心代码的说明 3.1总设计思想说明
本程序主要由三个大部分组合而成，它们分别为：主函数、子函数（创建二叉树子函数，计算叶子节点数子函数，计算二叉树深度子函数，前序、中序、后序遍历的子函数）和存储叶子节点信息的结构体。
首先，我为二叉树的每一个节点创建一个数组元素是BiTNode数据类型的数组，其中数据类型BiTNode包含三个信息：c（保存节点的权值），lchild（保存左孩子所在数组的位置）以及rchild（保存右孩子所在数组的位置）。然后，在主函数中，我们先用代码输出如下菜单供用户选择对应的c操作，那么用户就会根据自己的需要选择相应的操作。对于操作的选择，我用了一个while(){}循环来控制用户是否退出操作，果用户不选择退出操作，程序就将一直地运行下去。而对于其他的6种操作，就用if(){}„„else if(){}的语句来实现用户的选择。不过如果用户选择了目录以外的选择键，程序就会反馈回一个错误的信息，告诉用户该操作不存在。******************目录******************
1、创建二叉树
2、统计叶子个数
3、求二叉树的深度
4、前序遍历输出列表
5、中序遍历输出列表
6、后序遍历输出序列
0、退出操作
***************************************** 3.2创建二叉树函数说明
本题目中要求用户创建的二叉树一定要大于等于4层，因此，在子程序的一 19 开始就要用户输入创建的节点数目，并用if语句判断节点数是否少于8个（节点数为8的二叉树刚刚好是4层的），若是就显示错误信息，告诉用户所创建的二叉树少于4层，不满足条件，并且返回主函数。若不是，就用一个for循环将权值、左、右孩子信息分别录入到存储节点信息的数组之中，这样就可以成功创建二叉树。
3.3统计叶子数函数说明
由于本程序所创建的是完全二叉树，因此，求其叶子数个数可以利用完全二叉树的性质来求。首先我用一个for循环求出二叉树的结点个数。然后再用2对节点数进行求余，用if语句进行判断，如果右余数，就返回叶子个数：((结点个数-1)/2)+1；如果没有余数，就返回叶子结点个数：（结点个数、2）。3.4计算二叉树深度函数说明
计算二叉树深度的方法跟计算叶子节点个数的方法都差不多，同样都是要利用到完全二叉树的性质去实现算法。首先，我用一个for循环去计算了二叉树的结点个数，然后，用深度作为一个参数放进for循环里面，继续循环的条件是：当前d层数最多的结点数<=二叉树的结点数目。最后，经过这次循环后得到参数d-1（因为在结束是的d值刚刚好是不满足条件的）的值就是要返回的二叉树深度。
3.5前序遍历函数说明
前序遍历子函数的实现我们就用了函数的调用来实现。子函数的一开始就是要判断当前子函数所处理的结点是否有值，如果没有，就返回上一层操作；如果有，由于是先根遍历就先输出当前结点的权值，然后再用递归调用，用当前结点的左孩子作根节点重复当前函数的操作，跟着等前一个函数调用返回时就递归调用，用当前结点的右孩子作根节点重复当前函数的操作，那么输出的序列就是一个对二叉树进行先序遍历的序列。3.6中序遍历函数说明
中序遍历子函数的算法实现方法跟前序遍历子函数的差不多，也是要用到多个递归调用。在函数的一开始就用一个if语句判断当前结点的左孩子是否为空，如果不是就一直以当前结点的左孩子作为新的根结点调用自身；如果当前结点的左孩子已经是空的了，就不用进行以当前结点左孩子为根结点自身调用，直接输 20 出当前结点的权值。输出操作完成后，就判断当前结点的右孩子是否为空，如果是，就直接退出当前函数，返回上一层；如果不是，就要以当前结点的右孩子作为新的根结点，对该子函数进行自身的调用。经过这些操作之后所输出的序列就是对二叉树进行中序遍历的结果。3.7后序遍历函数说明
后序遍历跟之前的前序遍历和中序遍历差别不会太大，都是要用到函数的递归调用。首先，在函数的开头就用一个if语句判断当前结点的左孩子是否为空，如果不是就一直以当前结点的左孩子作为新的根结点调用自身；如果当前结点的左孩子已经是空的了，就不用进行以当前结点左孩子为根结点自身调用，而要再用一个if语句判断当前结点的右孩子是否为空，如果不是就一直以当前结点的右孩子作为新的根结点调用自身；如果当前结点的右孩子已经是空的了，就不用进行以当前结点右孩子为根结点自身调用，直接输出当前结点的权值。经过这些操作后所输出的序列就是二叉树按照后续遍历所得出的序列了。
四、个人总结
4.1课程设计中遇到的问题
每一个人，做每一件事情，哪怕是再小的事情都不是说你想做，就马上能够完成，取得成功。在做的过程之中，或多或少，我们都会遇到一些问题。当然，在这次课程设计之中，我也遇到了很多的问题，具体的问题有如下几个方面：
编写代码时出现的问题：（1）在刚开始做题目的时候，我还以为是要构建一般的二叉树，而不是完全二叉树。
（2）在编程之前，我没有多加思考就决定将创建二叉树之间的逻辑关系用指针来表示，可是做起来的时候才发现如果坚持用指针表示的话虽然可以动态分配内存空间，从而达到减少类存空间的效果。但是这样做就会给用户在操作上带来比较大的麻烦。因此用指针来实现逻辑关系，想来想去都不知道在创建二叉树输入权值的时候应该怎么样一次性输入所有的权值。
写说明书时出现的问题：
21（1）在画流程图的时候，我画得很快，一下子就画完了几个。但是在画图之前我完全没有留意到流程图的是与写程序有很大的区别。因为在别人还没有看过我们所编的程序之前再看我们画的流程图的时候可以很容易而且明确地明白我们的程序要实现的是一些怎么样的操作，但是当我看了看自己画的流程图的时候，才猛然发现我自己画的流程图简直就是我所编的那个程序的翻版，只不过是少了一点点字母，多了一点点中文而已。如果真的要找人来看，我敢打赌别人肯定很难完全明白我要实现一些怎么样的操作。
4.2对应问题的解决办法
编写代码时出现的问题：（1）在经过好一番的折腾和苦思冥想，还没有得到一个比较方便，比较简单的方法之后，我终于决定静下心来再重新研究一下题目究竟要求我们实现一些怎样的操作，而题目中又隐含了什么提示和条件。再从新看和研究完题目之后，在题目 “利用完全二叉树的性质建立一棵二叉树”中的利用完全二叉树的性质给了我莫大的帮助。这时候我才明白原来题目提示我们这个题目要构建的其实是完全二叉树这个模型，而不是一般的二叉树。对于我自己而言，构建完全二叉树远比构建一般的二叉树简单得多，而且考虑的情况也会少很多。
（2）不错，指针所建立的逻辑关系的确对计算机内部的系统带来了比较多的好处，但是，相比较而言，我觉得还是让用户觉得我所编写的程序操作简单一点比较重要。因此，我回顾这书上老师所讲过用来表示数据结构的方法究竟有哪一些。当时，我第一时间就想到了数组，虽然用数组做创建出来的二叉树所占用的内存空间是要比用指针创建出来的二叉树需要的内存空间大一点，但是，他就胜在操作简单、方便。而且如果用数组的话，还可以让用户在创建二叉树的时候按照顺序一次性的将创建完全二叉树所需要的权值一次性的按顺序输入到对应的位置之中，同时还可以实现与指针构建出来的二叉树一样的逻辑关系。
写说明书时出现的问题
（1）鉴于我一开始所画的那几个流程图太不符合流程图的要求，没有办法，我只好将已有的流程图框架之上将所有的陈述尽量用文字的意思表述出来。在修改完成之后，我自己还要再看一次看满不满足要求。4.3程序中的得意之处
对于我自己所编写的这个程序，虽然不一定是最好的，但是它还是让我觉得比较满意，有较多的优点，具体有如下机点：
（1）首先，本程序是采用结构体来定义结点的数据类型，方便，而且明了地表明结点与其左右孩子之间的逻辑关系；
（2）而且，本程序采用目录菜单的方式。用户只要根据目录菜单上的选择提示就可以轻松方便地多次使用相应操作，直到选择结束的操作才会退出整个程序。
（3）同时，我在实现前序、中序和后序遍历完全二叉树子函数的时候，用到了函数的递归调用，使源代码容易了解，而且还大大地缩短了程序的长度。4.4设计中存在的不足及改进方法
（1）如果程序的操作对象从完全二叉树推广到一般的二叉树，那样程序就会更加完善。如果要实现的话，我会用函数调用来实现：
如果当前结点有左孩子：递归调用创建二叉树函数creat(lchild);如果当前结点有右孩子：creat(rchild);这样进行创建二叉树，达到一定条件之后就退出操作。或者用二维数组也可以实现操作。
(2)在做该数据结构的课程设计题目的时候，我一开始想快一点写完程序因此忽略了很多可以优化的细节。我如今觉得便于用户使用固然是重要，但是如果还能够动态分配内存空间就更好了。因此，后来我在原有的程序基础上编了如下的程序，既可以一次性输入所有的权值，而且还可以根据用户的需要进行动态分配内存空间【优化版二叉树相关程序可运行】： #include“stdio.h” #include“stdlib.h” #include“malloc.h” 23 #include“string.h” #include“limits.h” typedef struct BiTNode{ int c;//权值
struct BiTNode *lchild,*rchild;}BiTNode,*tree;int jie;//二叉树的结点
tree creat(tree p)//创建二叉树函数 {
int i,j;printf(“需要输入权值个数：n”);scanf(“%d”,&j);jie=j;if(j<8)
//判断二叉树是否达到4层
{
printf(“错误：二叉树的层数少于4层！n”);
return(p);} p=(tree)malloc(j*sizeof(struct BiTNode));//动态分配内存空间，一次性分配用户所需的内存空间
printf(“开始输入权值(权值取值范围0--1000)：n”);//限定了权值的取值范围
for(i=1;i<=j;i=i+1)//权值的录入
{
scanf(“%d”,&p[i].c);
p[i].lchild=&p[2*i];
p[i].rchild=&p[2*i+1];} printf(“成功创建二叉树n”);return(p);} int leaves(tree p)//统计叶子个数函数 { int l,i;l=0;for(i=1;i //计算二叉树结点的个数 { l++;} l++;if((l%2)) //判断结点的奇偶性从而计算叶子的个数 { return(((l-1)/2)+1);} else return(l/2); } int deep(tree p)//求二叉树的深度 { int d,i,sum;sum=1;for(i=1;i for(d=1;sum<=i;d++) //求出二叉树的深度 { if(d!=1) { sum=sum+sum*2; } } if(d%2){ return(d-1);} else { return(d);} } void qian(int a,tree p)//前序遍历输出列表{ if((p[a].c>=0)&&(p[a].c<=1000)){ printf(“%d,”,p[a].c); //首先输出当前结点（根节点）的权值 qian(a*2,p); qian(a*2+1,p);} else return;} void zhong(int a,tree p)//中序遍历输出列表 { if((p[2*a].c>=0)&&(p[2*a].c<=1000)){ zhong((2*a),p); } printf(“%d,”,p[a].c);//输出当前结点的权值 if((p[2*a+1].c>=0)&&(p[2*a+1].c<=1000)){ zhong((2*a+1),p);} } void hou(int a,tree p)//后序遍历输出序列 { if((p[2*a].c>=0)&&(p[2*a].c<=1000)){ hou((2*a),p);} if((p[2*a+1].c>=0)&&(p[2*a+1].c)<=1000){ hou((2*a+1),p);} printf(“%d,”,p[a].c);//输出当前结点的权值 } void main(){ int d,l,i;tree p;i=10;p=(tree)malloc(sizeof(struct BiTNode));printf(“******************目录******************n”);printf(“ 1、创建二叉树n”);printf(“ 2、统计叶子个数n”);printf(“ 3、求二叉树的深度n”);printf(“ 4、前序遍历输出列表n”);printf(“ 5、中序遍历输出列表n”);printf(“ 6、后序遍历输出序列n”);printf(“0、退出操作n”);printf(“*****************************************n”);while(i!=0){ printf(“选择操作：n”); scanf(“%d”,&i); if(i==0) { break; } else if(i==1) { printf(“开始创建二叉树(层数不少于4层)n”); p=creat(p); } else if(i==2) { l=leaves(p); printf(“叶子个数为：%dn”,l); } else if(i==3) { d=deep(p); printf(“二叉树的深度是%dn”,d); } else if(i==4) { printf(“用前序遍历输出的结果是：n”); qian(1,p); printf(“n”); } else if(i==5) { printf(“用中序遍历输出的结果是：n”); zhong(1,p); printf(“n”); } else if(i==6) { printf(“用后序遍历输出的结果是：n”); hou(1,p); printf(“n”); } else printf(“错误：没有该操作！n”);} printf(“欢迎使用！n”);} 4.5设计中的感想以及心得体会 在每一次做课程设计的时候，我都会觉得获益良多，当然，这次的数据结构课程设计也不会有例外。在这一次课程设计过程中，我尝试了用错数据结构所给我带来的郁闷，因为有一点小小问题而不可以使程序继续运行的纠结，写课程设计任务书不规范再从新编排而带来的伤感，当然，同时还会感觉到一个个子函数通过编译然后得出正确结果的无限欣喜，看着数据结构课程设计任务书一点点增加时所带来的成就感，还有想到一些更好的改进方法时所带来的愉悦感等等。再设计的过程之中，各种各样的情感交织在一起，真的是痛并快乐着。 当然，长时间的专注在数据结构的课程设计之中让我我在编写程序和巩固数据结构知识这两个方面都有了很大的收获。 我还记得我在做之前的C语言课程设计，以及上一学期的数据结构的实验之前都要很认真地看书上要管操作的源代码之后才编写程序的。我觉得如果我这次数据结构的课程设计我还是这样做的话，对于我自己就很难会有所提升，而且我看过题目之后，我所要做的那道课程设计题目其实跟我之前所做的那些数据结构实验内容有点出入，因此，我这一次想要突破自己，尝试一下在不看相关代码的情况下用自己所有的知识编写属于自己操作实现的代码。当然，用这样的方法编写代码，让我在设计的过程之中增加了不少麻烦，但我从来不会觉得后悔。也因为这样，我对自己所编出来的程序更加了解，印象更加深刻，更便于我对程序作修改以及优化。 我在开始写整一个程序的时候，会先把程序总体的结构、大概的框架都写出来（包括要创建的结构体，各个子函数（不包括各内容实现的代码）和主函数与子函数之间的逻辑关系）。写完总体框架之后，我再写完一个子函数就马上编译运行一下程序，看看新写的子函数有没有问题，如果有的话就针对新写的函数段进行修改，直至没有错误，以及运行结果正确之后才去编写下一个子函数。我发现这次课程设计用了这个方法之后，我在编写程序的时候条理清晰了很多，编写程序很顺利，就损友出现错误，很快就能够找到出错的地方，也没有出现那一种因为一两个小错误就修改了一整个晚上的情况了。 同时，这次我在设计的时候，遇到了想不明白的时候，我总会用一张纸将我 30 创建的完全二叉树画在纸上，认认真真的分析我要实现的操作与我所创建的完全二叉树究竟有什么逻辑上的关系，然后再从关系上找出实现对应操作的方法。这样虽然在分析的时候会耗掉一点时间，可是，却让我很顺利地实现程序，让我真真正正的明白什么叫做“磨刀不误砍柴工”。 最后，我觉得这次的数据结构课程设计不仅让我巩固了数据结构的知识，更重要的是让我领悟到了一套适合自己编写程序的方法,使我以后编程都更加得心应手。 数 据 结 构 课程设计报告 题 目： 一元多项式计算 专 业： 信息管理与信息系统 班 级： 2012级普本班 学 号： 201201011367 姓 名： 左帅帅 指导老师： 郝慎学 时 间： 一、课程设计题目分析 本课程设计要求利用C语言或C++编写，本程序实现了一元多项式的加法、减法、乘法、除法运算等功能。 二、设计思路 本程序采用C语言来完成课程设计。 1、首先，利用顺序存储结构来构造两个存储多项式A(x)和 B(x)的结构。 2、然后把输入，加，减，乘，除运算分成五个主要的模块：实现多项式输入模块、实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块。 3、然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能，尽量减少程序运行时错误的出现。 4、最后编写main()主函数以实现对多项式输入输出以及加、减、乘、除，调试程序并将不足的地方加以修改。 三、设计算法分析 1、相关函数说明： (1)定义数据结构类型为线性表的链式存储结构类型变量 typedef struct Polynomial{} (2)其他功能函数 插入函数void Insert(Polyn p,Polyn h) 比较函数int compare(Polyn a,Polyn b) 建立一元多项式函数Polyn Create(Polyn head,int m) 求解并建立多项式a+b，Polyn Add(Polyn pa,Polyn pb) 求解并建立多项式a-b，Polyn Subtract(Polyn pa,Polyn pb)2 求解并建立多项式a*b，Polyn Multiply(Polyn pa,Polyn pb) 求解并建立多项式a/b，void Device(Polyn pa,Polyn pb) 输出函数输出多项式，void Print(Polyn P) 销毁多项式函数释放内存，void Destroy(Polyn p) 主函数，void main（） 2、主程序的流程基函数调用说明(1)typedef struct Polynomial { float coef; int expn; struct Polynomial *next;} *Polyn,Polynomial; 在这个结构体变量中coef表示每一项前的系数，expn表示每一项的指数，polyn为结点指针类型，属于抽象数据类型通常由用户自行定义，Polynomial表示的是结构体中的数据对象名。 (2)当用户输入两个一元多项式的系数和指数后，建立链表，存储这两个多项式，主要说明如下： Polyn CreatePolyn(Polyn head,int m)建立一个头指针为head、项数为m的一元多项式 p=head=(Polyn)malloc(sizeof(struct Polynomial));为输入的多项式申请足够的存储空间 p=(Polyn)malloc(sizeof(struct Polynomial));建立新结点以接收数据 Insert(p,head);调用Insert函数插入结点 这就建立一元多项式的关键步骤 (3)由于多项式的系数和指数都是随即输入的，所以根据要求需要对多项式按指数进行降幂排序。在这个程序模块中，使用链表，根据对指数大小的比较，对各种情况进行处理，此处由于反复使用指针对各个结点进行定位，找到合适的位置再利用void Insert(Polyn p,Polyn h)进行插入操作。(4)加、减、乘、除、的算法实现： 在该程序中，最关键的一步是实现四则运算和输出，由于加减算法原则是一样，减法可通过系数为负的加法实现；对于乘除算法的大致流程都是：首先建立多项式a*b，a/b，然后使用链表存储所求出的乘积，商和余数。这就实现了多项式计算模块的主要功能。 (5)另一个子函数是输出函数 PrintPolyn（）； 输出最终的结果，算法是将最后计算合并的链表逐个结点依次输出，便得到整链表，也就是最后的计算式计算结果。由于考虑各个结点的指数情况不同，分别进行了判断处理。 四、程序新点 通过多次写程序，发现在程序在控制台运行时总是黑色的，本次写程序就想着改变一下，于是经过查资料利用system(“Color E0”);可以函数解决，这里“E0，”E是控制台背景颜色，0是控制台输出字体颜色。 五、设计中遇到的问题及解决办法 首先是，由于此次课程设计里使用指针使用比较多，自己在指针多的时候易脑子混乱出错，对于此问题我是采取比较笨的办法在稿纸上写明白后开始进行 4 代码编写。 其次是，在写除法模块时比较复杂，自己通过查资料最后成功写出除法模块功能。 最后是，前期分析不足开始急于写代码，中途出现各种问题，算是给自己以后设计时的一个经验吧。 六、测试（程序截图） 1.数据输入及主菜单 2.加法和减法模块 3.乘法和除法模块 七、总结 通过本次应用C语言设计一元多项式基本计算程序，使我更加巩固了C语言程序设计的知识，以前对指针这一点使用是比较模糊，现在通过此次课程设计对指针理解的比较深刻了。而且对于数据结构的相关算法和函数的调用方面知识的加深。本次的课程设计，一方面提高了自己独立思考处理问题的能力；另一方面使自己再设计开发程序方面有了一定的小经验和想法，对自己以后学习其他语言程序设计奠定了一定的基础。 八、指导老师评语及成绩 附录：（课程设计代码） #include float coef;6 int expn; struct Polynomial *next;} *Polyn,Polynomial; //Polyn为结点指针类型 void Insert(Polyn p,Polyn h){ if(p->coef==0)free(p); //系数为0的话释放结点 else { Polyn q1,q2; q1=h;q2=h->next; while(q2&&p->expn { q1=q2;q2=q2->next;} if(q2&&p->expn==q2->expn)//将指数相同相合并 { q2->coef+=p->coef; free(p); if(!q2->coef)//系数为0的话释放结点 { q1->next=q2->next;free(q2);} } else { p->next=q2;q1->next=p; }//指数为新时将结点插入 } 7 } //建立一个头指针为head、项数为m的一元多项式 Polyn Create(Polyn head,int m){ int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL; for(i=0;i { p=(Polyn)malloc(sizeof(struct Polynomial));//建立新结点以接收数据 printf(“请输入第%d项的系数与指数:”,i+1); scanf(“%f %d”,&p->coef,&p->expn); Insert(p,head); //调用Insert函数插入结点 } return head;} //销毁多项式p void Destroy(Polyn p){ Polyn q1,q2; q1=p->next;8 q2=q1->next; while(q1->next) { free(q1); q1=q2;//指针后移 q2=q2->next; } } //输出多项式p int Print(Polyn P){ Polyn q=P->next; int flag=1;//项数计数器 if(!q)//若多项式为空，输出0 { putchar('0'); printf(“n”); return; } while(q) { if(q->coef>0&&flag!=1)putchar('+');//系数大于0且不是第一项 9 if(q->coef!=1&&q->coef!=-1)//系数非1或-1的普通情况 { printf(“%g”,q->coef); if(q->expn==1)putchar('X'); else if(q->expn)printf(“X^%d”,q->expn); } else { if(q->coef==1){ if(!q->expn)putchar('1'); else if(q->expn==1)putchar('X'); else printf(“X^%d”,q->expn);} if(q->coef==-1){ if(!q->expn)printf(“-1”); else if(q->expn==1)printf(“-X”); else printf(“-X^%d”,q->expn);} } q=q->next; flag++; } printf(“n”);} int compare(Polyn a,Polyn b){ if(a&&b) { if(!b||a->expn>b->expn)return 1; else if(!a||a->expn else return 0; } else if(!a&&b)return-1;//a多项式已空，但b多项式非空 else return 1;//b多项式已空，但a多项式非空 } //求解并建立多项式a+b，返回其头指针 Polyn Add(Polyn pa,Polyn pb){ Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 11 hc->next=NULL; headc=hc; while(qa||qb){ qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)) { case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; case-1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break;12 } if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//当相加系数为0时，释放该结点 } return headc;} //求解并建立多项式a-b，返回其头指针 Polyn Subtract(Polyn pa,Polyn pb){ Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p)//将pb的系数取反 { p->coef*=-1;p=p->next;} pd=Add(pa,h); for(p=h->next;p;p=p->next) //恢复pb的系数 p->coef*=-1;13 return pd;} //求解并建立多项式a*b，返回其头指针 Polyn Multiply(Polyn pa,Polyn pb){ Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 hf->next=NULL; for(;qa;qa=qa->next) { for(qb=pb->next;qb;qb=qb->next) { pf=(Polyn)malloc(sizeof(struct Polynomial)); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);//调用Insert函数以合并指数相同的项 } } return hf;} //求解并建立多项式a/b，返回其头指针 void Device(Polyn pa,Polyn pb){ Polyn hf,pf,temp1,temp2; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点,存储商 hf->next=NULL; pf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点，存储余数 pf->next=NULL; temp1=(Polyn)malloc(sizeof(struct Polynomial)); temp1->next=NULL; temp2=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next=NULL; temp1=Add(temp1,pa); while(qa!=NULL&&qa->expn>=qb->expn) { temp2->next=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next->coef=(qa->coef)/(qb->coef); temp2->next->expn=(qa->expn)-(qb->expn); Insert(temp2->next,hf); pa=Subtract(pa,Multiply(pb,temp2));15 qa=pa->next; temp2->next=NULL; } pf=Subtract(temp1,Multiply(hf,pb)); pb=temp1; printf(“商是:”); Print(hf); printf(“余数是:”); Print(pf);} void main(){ int choose=1;int m,n,flag=0;system(“Color E0”);Polyn pa=0,pb=0,pc,pd,pf;//定义各式的头指针，pa与pb在使用前付初值NULL printf(“请输入A(x)的项数:”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多项式A printf(“n”);printf(“请输入B(x)的项数:”);16 scanf(“%d”,&n);printf(“n”);pb=Create(pb,n);//建立多项式B printf(“n”);printf(“**********************************************n”);printf(“* 多项式操作菜单 printf(”**********************************************n“);printf(”tt 1.输出操作n“);printf(”tt 2.加法操作n“);printf(”tt 3.减法操作n“);printf(”tt 4.乘法操作n“);printf(”tt 5.除法操作n“);printf(”tt 6.退出操作n“);printf(”**********************************************n“);while(choose){ printf(”执行操作:“); scanf(”%d“,&flag); switch(flag) { case 1: printf(”多项式A(x):“);Print(pa);*n”); printf(“多项式B(x):”);Print(pb); break; case 2: pc=Add(pa,pb); printf(“多项式A(x)+B(x):”);Print(pc); Destroy(pc);break; case 3: pd=Subtract(pa,pb); printf(“多项式A(x)-B(x):”);Print(pd); Destroy(pd);break; case 4: pf=Multiply(pa,pb); printf(“多项式A(x)*B(x):”); Print(pf); Destroy(pf); break; case 5: Device(pa,pb);18 break; case 6: exit(0); break; } } Destroy(pa); Destroy(pb);} 数据结构课程设计 1.赫夫曼编码器 设计一个利用赫夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。要求： 1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 2)初始化：键盘输入字符集大小26、26个字符和26个权值（统计一篇英文文章中26个字母），建立哈夫曼树； 3)编码：利用建好的哈夫曼树生成哈夫曼编码； 4)输出编码（首先实现屏幕输出，然后实现文件输出）； 5)界面优化设计。 代码如下： #include typedef struct HTNode //结构体 { int Weight; char ch;int Parent,Lchild,Rchild;}HTNode;typedef char * * HCode; void Save(int n,HTNode *HT) //把权值保存到文件 { FILE * fp; int i; if((fp=fopen(“data.txt”,“wb”))==NULL) { printf(“cannot open filen”); return; } for(i=0;i if(fwrite(&HT[i].Weight,sizeof(struct HTNode),1,fp)!=1) printf(“file write errorn”); fclose(fp); system(“cls”); printf(“保存成功！”); } void Create_H(int n,int m,HTNode *HT) //建立赫夫曼树，进行编码 { int w,k,j;char c;for(k=1;k<=m;k++){ if(k<=n) { printf(“n请输入权值和字符(用空格隔开): ”); scanf(“%d”,&w); scanf(“ %c”,&c);HT[k].ch=c; HT[k].Weight=w; } else HT[k].Weight=0; HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0;} int p1,p2,w1,w2; for(k=n+1;k<=m;k++){ p1=0;p2=0; w1=32767;w2=32767; for(j=1;j<=k-1;j++) { if(HT[j].Parent==0) { if(HT[j].Weight { w2=w1;p2=p1; w1=HT[j].Weight; p1=j; } else if(HT[j].Weight { w2=HT[j].Weight; p2=j; } } } HT[k].Lchild=p1;HT[k].Rchild=p2;HT[k].Weight=HT[p1].Weight+HT[p2].Weight; HT[p1].Parent=k;HT[p2].Parent=k; } printf(“输入成功！”);} void Coding_H(int n,HTNode *HT) //对结点进行译码 { int k,sp,fp,p;char *cd;HCode HC; HC=(HCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char));cd[n-1]=' '; printf(“************************n”);printf(“Char Codingn”); for(k=1;k<=n;k++) { sp=n-1;p=k;fp=HT[k].Parent; for(;fp!=0;p=fp,fp=HT[fp].Parent) if(HT[fp].Lchild==p) cd[--sp]='0'; else cd[--sp]='1'; HC[k]=(char *)malloc((n-sp)*sizeof(char)); strcpy(HC[k],&cd[sp]); printf(“%c %sn”,HT[k].ch,HC[k]); } printf(“************************n”);free(cd);} void Read(int n,HTNode *HT) //从文件中读出数据 { int i;FILE * fp;if((fp=fopen(“data.txt”,“rb”))==NULL){ printf(“cannot open filen”); exit(0);} for(i=0;i fread(&HT[i].Weight,sizeof(struct HTNode),1,fp);// printf(“%d n”,HT[i].Weight); } Coding_H(n,HT); fclose(fp);} void Print_H(int m,HTNode *HT) //输出赫夫曼造树过程 { int k;printf(“************************n”);printf(“Num Weight Par LCh RCh n”);for(k=1;k<=m;k++){ printf(“%d ”,k); printf(“ %d”,HT[k].Weight); printf(“ %d”,HT[k].Parent); printf(“ %d”,HT[k].Lchild); printf(“ %dn”,HT[k].Rchild); } printf(“************************n”);} void Decode(int m,HTNode *HT) //对输入的电文进行译码 { int i,j=0;char a[10];char endflag='2';i=m;printf(“输入发送的编码，以‘2’结束:”);scanf(“%s”,&a);printf(“译码后的字符：”);while(a[j]!='2'){ if(a[j]=='0') i=HT[i].Lchild; else i=HT[i].Rchild; if(HT[i].Lchild==0) //HT[i]是叶结点 { printf(“%c”,HT[i].ch); i=m; //回到根结点 } j++;} printf(“n”);if(HT[i].Lchild!=0&&a[j]!='2') printf(“ERROR”);} int main() //主函数 { int n,m,c;HTNode HT[N];do { system(“color 2f”); //运行环境背景颜色.printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt 赫夫曼编译码系统 ttt”); printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt1.输入权值、字母nttt2.把数据写入文件nttt3.输出赫夫曼编码表nttt”); printf(“4.输出赫夫曼译码表nttt5.输入编码并译码.nttt6.从文件中读出数据nttt7.退出”); printf(“nnttt请选择:”); scanf(“%d”,&c); switch(c) { case 1:system(“cls”);printf(“输入多少结点:”); scanf(“%d”,&n);m=2*n-1;Create_H(n,m,HT);break; case 2:system(“cls”);Save(n,HT);break; case 3:system(“cls”);Print_H(m,HT);break; case 4:system(“cls”);Coding_H(n,HT);break; case 5:system(“cls”);Decode(m,HT);break; case 6:system(“cls”);Read(n,HT);break; case 7:system(“cls”);exit(0); } }while(1);return 0;} 运行界面如下： 2.学生成绩管理（链表实现）要求： 实现如下功能：增加、查找、删除、输出、退出。 代码如下： #include //定义成绩信息结构体 { char Number[20];char Name[20];char Chinese[20];char English[20];char Math[20];}score;typedef struct node_score //定义成绩信息链表结点，包括数据域和指针域 { score data;struct node_score *next;}node_score,*p_node_score;p_node_score headScore;//定义链表的头指针为全局变量 void PrintScore(score s)//输出信息函数 { printf(“ %10s”,s.Number);printf(“ | %-6s”,s.Name);printf(“ | %-3s”,s.Chinese);printf(“ | %-3s”,s.English); printf(“ | %-3sn”,s.Math);} void View()//输出函数 { p_node_score pNodeScore; pNodeScore=headScore;printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”);while(pNodeScore!= NULL){ PrintScore(pNodeScore->data);//输出学生信息和成绩信息 pNodeScore=pNodeScore->next;} } void Add(){ p_node_score pNodeScore;// 定义一个节点 pNodeScore=(p_node_score)malloc(sizeof(node_score));//为节点分配存储空间 printf(“请输入学号：”);scanf(“%s”,pNodeScore->data.Number);printf(“请输入姓名：”);scanf(“%s”,pNodeScore->data.Name);printf(“请输入语文成绩：”);scanf(“%s”,pNodeScore->data.Chinese);printf(“请输入英语成绩：”);scanf(“%s”,pNodeScore->data.English);printf(“请输入高数成绩：”);scanf(“%s”,pNodeScore->data.Math);if(headScore==NULL){ //如果头结点为空 headScore=pNodeScore; pNodeScore->next=NULL;} else { //如果头结点不为空 pNodeScore->next=headScore; headScore=pNodeScore;//将头结点新结点 } } void Input(){ int n,i;printf(“输入几个学生的数据：”);scanf(“%d”,&n);for(i=0;i Add();printf(“输入成功！”);} int Delete(){ p_node_score pNodeScore,p1;//p1为pNodeScore的前驱 p1=headScore;if(p1==NULL){ printf(“成绩表中没有数据！请先添加数据！n”); return 0;} char DeleteNumber[20]; printf(“请数入要删除的学生学号:”);scanf(“%s”,DeleteNumber);if(strcmp(p1->data.Number,DeleteNumber)==0) { //如果要删除的结点在第一个 headScore=p1->next; pNodeScore=p1; printf(“学号为%s的学生信息已经删除！n”,DeleteNumber); return 0;} else { pNodeScore=p1->next; while(pNodeScore!=NULL) { if(strcmp(pNodeScore->data.Number,DeleteNumber)==0) { p1->next=pNodeScore->next; printf(“学号为%s的学生信息已经删除！n”,DeleteNumber); return 0; } else { //否则，结点向下一个，p1仍为pNodeScore的前驱 p1=pNodeScore; pNodeScore=pNodeScore->next; } } } printf(“没有此学号的学生！”);} int Change(){ p_node_score pNodeScore; pNodeScore=headScore;if(pNodeScore==NULL){ printf(“成绩表中没有数据！请先添加数据！n”); return 0;} char EditNumber[20];printf(“请输入你要修改的学生学号：”);scanf(“%s”,EditNumber);while(pNodeScore!=NULL){ if(strcmp(pNodeScore->data.Number,EditNumber)==0) { //用strcmp比较两字符串是否相等，相等则返回0 printf(“原来的学生成绩信息如下：n”);//输出原来的成绩信息 printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”); PrintScore(pNodeScore->data); printf(“语文新成绩:”); scanf(“%s”,pNodeScore->data.Chinese); printf(“英语新成绩:”); scanf(“%s”,pNodeScore->data.English); printf(“高数新成绩:”); scanf(“%s”,pNodeScore->data.Math); printf(“成绩已经修改！”); return 0; } pNodeScore=pNodeScore->next;//如果不相等，pNodeScore则指向下一个结点 } printf(“没有此学号的学生！n”);//如果找到最后都没有，则输出没有此学号的学生 } int Find(){ p_node_score pNodeScore; pNodeScore=headScore;if(pNodeScore==NULL){ printf(“成绩表中没有数据！请先添加数据！n”); return 0;} char FindNumber[20];printf(“请输入你要查找的学生学号：”);scanf(“%s”,FindNumber);while(pNodeScore!=NULL){ if(strcmp(pNodeScore->data.Number,FindNumber)==0) { printf(“你要查找的学生成绩信息如下：n”); printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”); PrintScore(pNodeScore->data); return 0; } pNodeScore=pNodeScore->next;} printf(“没有此学号的学生！n”);} int main() //主函数 { int choice=0;headScore=NULL;int c;do { system(“color 2f”); //运行环境背景颜色.printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt 学生成绩管理系统 ttt”); printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt1.输入成绩信息nttt2.输出成绩信息nttt3.添加成绩信息nttt”); printf(“4.修改成绩信息nttt5.删除成绩信息nttt6.查询成绩信息nttt7.退出”); printf(“nnttt请选择:”); scanf(“%d”,&c); switch(c) { case 1:system(“cls”);Input();break; case 2:system(“cls”);View();break; case 3:system(“cls”);Add();break; case 4:system(“cls”);Change();break; case 5:system(“cls”);Delete();break; case 6:system(“cls”);Find();break; case 7:system(“cls”);exit(0); } }while(1);return 0;} 运行界面如下： 课程设计报告的内容 设计结束后要写出课程设计报告,以作为整个课程设计评分的书面依据和存档材料.设计报告以规定格式的电子文档书写,打印并装订,排版及图,表要清楚,工整.装订顺序如下:封面、目录、正文.正文包括以下7个内容: 1.需求分析 陈述说明程序设计的任务,强调的是程序要做什么，需要什么结果、所能达到的功能.2.概要设计 说明本程序中用到的所有抽象数据类型的定义,主程序的流程以及各程序模块之间的层次(调用)关系.3.详细设计 实现概要设计中定义的所有数据类型,对每个操作只需要写出伪码算法;对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为:按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序);可采用流程图、N S 图进行描述,画出函数和过程的调用关系图.4.调试分析 内容包括: a.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析;b.算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和 改进设想; c.经验和体会等.5.测试结果 列出你的测试结果,包括输入和输出.这里的测试数据应该完整和严格,最好多于需求分析中所列.6.参考文献 列出参考的相关资料和书籍.封面格式如下： 数据结构课程设计报告 班级：_____ _____ _____ _________ 姓名：____________________ 指导教师：___________________ 成绩：__________________________ 信息工程学院 年月日 目录 1.需求分析 ……………………………………………… 22．概要设计………………………………………………2 3.详细设计 ………………………………………………2 4.调试分析 ………………………………………………2 5.测试结果… ……………………………………………2 参考文献 …………………………………………………6 附录…………………………………………………… 一、需求分析 二、概要设计 三、详细设计 四、调试分析 五、测试结果 六、参考文献 七、附录 附录为程序代码！4 课程设计题目 1、运动会分数统计 任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=10 , w=8 , n=15）功能要求： 1).可以输入各个项目的前三名或前五名的成绩； 2).能统计各学校总分（用链表）； 3).可以按学校编号、学校总分、男女团体总分排序输出（快速、基数）； 4).可按学校编号查询学校某个项目的情况；可按项目编号查询取得前三或前五名的学校。 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。 测试数据：要求使用 1、全部合法数据； 2、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明； 2、迷宫求解 任务：可以读入一个任意大小的迷宫数据，分别用广度和深度搜索的方法求出一条走出迷宫的路径，并将路径输出（最佳路径）； 要求：以较为直观的方式显示结果 3、Huffman编码 任务 ：对一篇英文文章，统计各字符出现的次数，实现Huffman编码； 要求：输出每个字符出现的次数和编码，其中求最小权值要求用堆实现； 4、营业窗口队列模拟 任务：实现具有n（n=3）个窗口的现实队列模拟，统计每人的等待时间。要求： 1).随机产生顾客的到达时间和服务时间存盘。2).利用存盘数据实现队列的插入和删除。2).当有顾客离开时，根据队列长度调整队尾。3).考虑顾客中途离队的情况。4).考虑顾客具有优先级的情况。 5、公交线路提示 任务：建立南京主要公交线路图。要求：输入任意两站点，给出最佳的乘车线路和转车地点。 6、家谱管理系统 任务：实现具有下列功能的家谱管理系统 功能要求： 1).输入文件以存放最初家谱中各成员的信息，成员的信息中均应包含以下内容：姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡），也可附加其它信息、但不是必需的。 2).实现数据的存盘和读盘。3).以图形方式显示家谱。 4).显示第n 代所有人的信息。 5).按照姓名查询，输出成员信息（包括其本人、父亲、孩子的信息）。6).按照出生日期查询成员名单。7).输入两人姓名，确定其关系。8).某成员添加孩子。 9).删除某成员（若其还有后代，则一并删除）。10).修改某成员信息。 11).按出生日期对家谱中所有人排序。 12).打开一家谱时，提示当天生日的健在成员。 要求：建立至少30个成员的数据，以较为直观的方式显示结果，并提供文稿形式以便检查。 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求相关数据要存储在数据文件中。测试数据：要求使用 1、全部合法数据； 2、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明； 7、排序算法比较 设计要求：利用随机函数产生10个样本，每个样本有50000随机整数，利用直接插入排序、折半插入排序，表插入排序，希尔排序，起泡排序、快速排序、选择排序、堆排序，归并排序，基数排序十种排序方法进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的平均时间（统计为图表坐标形式）。 8、算术表达式求值 [问题描述] 一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。[基本要求]（1）从键盘读入一个合法的算术表达式，输出正确的结果。（2）显示输入序列和栈的变化过程。 9、电子小字典 基本要求：建立一个微型电子字典，实现生词的加入，单词的查找、删除，修改等操作。 数据结构：键树 10、校园导游程序 [问题描述]用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。[基本要求]（1）查询各景点的相关信息； （2）查询图中任意两个景点间的最短路径。（3）查询图中任意两个景点间的所有路径。 （4）增加、删除、更新有关景点和道路的信息。 11、稀疏矩阵相乘 任务：以三元组形式存储稀疏矩阵，实现矩阵相乘。 12、平衡二叉树 任务：平衡二叉树的建立、结点的插入和删除。 13、B-树 任务：3阶B-树的结点的插入和删除。 14、HASH表 任务：以班级学生姓名（拼音）为关键字，建立HASH涵数，实现HASH表存储，用链地址方法解决冲突。 15、„„（自选合适的题目） 成绩评定细则： 1.正确性：程序是否可以运行，结果是否正确（20分）2.功能的完备性：是否实现要求的所有子功能（20分） 3.课程设计报告中的算法说明的清晰程度，课程设计报告中总结的深刻程度（20分）4.独立完成情况(40分）总计：100分 加分项目： 1.健壮性：异常处理的情况 2.可读性：代码编写是否规范，是否便于阅读。如函数、变量命名，‘{ }’的缩进，关键位置适量注释等 3.功能的完善：除要求实现的功能外，完成了其它的功能，实现了功能的完善 4.界面的设计：可视化界面，或者交互良好的DOS界面 5.……（自荐加分项目） 代码量要求：>=1000行。 代码总量 = 课设题目1 代码量 + 课设题目2 代码量…… 若代码总量低于1000行，则成绩按比例打折。 编程语言：C或C++语言 编程环境：Microsoft Visual C++ 6.0 检查方式: 1.总体上检查程序的代码量，正确性，可读性，健壮性，功能的完备性,代码量，程序的结构是否合理；局部检查三个以上函数块 2.检查程序时同时检查课程设计报告的电子文档 时间安排： 上机时间安排 课程设计报告上交时间 3 课程设计检查时间 课程设计报告要求： 1.所有的课程设计报告，均要有封面，包括：课题名称、班级、学号、学生姓名、成绩和指导教师； 2.给出自己采用的数据结构； 3.给出算法设计思想； 4.给出实现的源程序，并在必要的代码处给出注释； 5.给出测试数据和结果； 6.给出算法的时间复杂度、另外可以提出算法的改进方法； 7.给出结束语：说明完成课程设计的情况，心得体会；课程设计报告的电子文档在上机检查程序时一并检查；书面文档在指定的时间内上交。第二篇：2012数据结构课程设计
第三篇：数据结构课程设计
第四篇：《数据结构》课程设计文档格式（定稿）
第五篇：课程设计(数据结构)
点击咨询 