课程设计实验报告

1、数据结构 课程设计课程设计成绩总评成绩指导老师签名 数据结构课程设计报告学院（系）： 计算机科学与工程学院 班 级： 112030901 学生姓名: 余钱 学号：11203090136 指导教师： 何波 傅由甲时间：从 2014 年 1 月 6 日到 2014 年 1 月 12日目录一、课程设计概述2二、课程设计题目及分析21、题目一21.1、问题描述21.2、基本要求21.3、系统分析31.4、运行结果分析31.5、设计总结32、题目二42.1、问题描述42.2、实现提示42.3、系统分析42.4、运行结果分析52.5、设计总结53、题目三63.1、问题描述63.2、基本要求63.3、系统分

2、析63.4、运行结果分析63.5、设计总结94、 题目四94.1、问题描述94.2、基本要求94.3、系统分析104.4、运行结果分析104.5、设计总结11三、附录111、源程序清单及结果111.1、题目一：111.2、题目二：151.3、题目三：171.4、题目四：22四、参考文献27五、课程设计心得27一、课程设计概述本次课程设计共完成4个题目： 1、二叉排序树于平衡二叉树的实现 2、背包问题 3、学生成绩分析系统 4、一元稀疏多项式简单计算器C语言 C#语言编译环境：VC 6.0 Microsoft Visual Studio2010 数据库（SQL Server 2008 R2）二、

3、课程设计题目及分析1、题目一二叉排序树于平衡二叉树的实现1.1、问题描述分别采用二叉链表和顺序表作存储结构，实现对二叉排序树与平衡二叉树的操作1.2、基本要求（1）用二叉链表作存储结构。1）以回车（n）为输入结束标志，输入数列L，生成一棵二叉排序树T；2）对二叉排序树T作中序遍历，输出结果；3）计算二叉排序树T查找成功的平均长度，输出结果；4）输入元素X，查找二叉排序树T，若存在含X的结点，则删除该结点，并作中序遍历图；否则，输出信息“无X”；5）用数列L，生成平衡的二叉排序树BT；当插入新元素之后，发现当前的二叉排序树BT不是平衡二叉排序树，则立即将它转换成新的平衡的二叉排序树BT6）计算平

4、衡的二叉排序树BT的平均查找长度，输出结果。（2）用顺序表（一位数组）作存储结构。1）以回车（n）为输入结束标志，输入数列L，生成一棵二叉排序树T；2）对二叉排序树T作中序遍历，输出结果3）计算二叉排序树T查找成功的平均长度，输出结果；4）输入元素X，查找二叉排序树T，若存在含X的结点，则删除该结点，并作中序遍历图；否则，输出信息“无X”；1.3、系统分析按先根序序列建立二叉树的二叉链表，在遍历二叉树的时候执行一个递归程序，需要借助栈的作用，因此可以直接使用栈；在查找二叉树结点的过程中，按照遍历的顺序将每个结点遍历一遍与输入的值进行比较。用顺序表做存储结构的时候，用带头节点的单链表来标明二叉树

5、的双亲和左右孩子结点的位置，以便遍历，遍历过程中，则按照先后次序遍历二叉树的各个结点。1.4、运行结果分析测试数据：5 6 4 3 2 1 4 0 /0输入的作为结束符中序遍历结果：1 2 3 4 5 6结点个数：6 树的深度：28 平均长度：4.67输入查找的元素：5删除输入元素后的结果：1 2 3 4 61.5、设计总结树和二叉树之层序遍历二叉树中的先序遍历、中序遍历、后序遍历、层序遍历均采用递归算法，而构建二叉树时也采用的是递归算法。在层序遍历中采用队列的入队进队的方法从而实现层序遍历二叉树。本次实验通过九个函数分别多二叉树进行先序、中序、后序以及层序四种遍历操作，层序遍历开始没有得到预

6、想结果，原来是自己写程序不够谨慎，没有在层序遍历中写相应的输出语句，另外，在创建队列时由于自己的粗心大意，没有很好将空间分配控制语句完善好，最后导致层序遍历结果输出，经多次仔细观察才返现。2、题目二背包问题2.1、问题描述假设有一个能够装入总体积为T的背包和n件体积分别为w1，w2，w3.wn。的物品，能否从n件物品中挑选出若干件恰好装满背包，即使w1+w2+w3+.+wn=T要求找出所有满足条件的解。例如：当T等于10，各件物品的体积1，8，4，3，5，2时，可以找到下列四组解：（1，4，3，2）（1，4，5）（8，2）（3，5，2）2.2、实现提示可利用回溯法的设计思想来解决背包问题。首先

7、，将物品排成一列，然后，顺序选取物品装入背包，若已选取第i件物品后未满，则继续选取第i+1件，若该件物品“太大”不能装入，则弃之，继续选取下一件，直至背包装满为止。如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入的物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直到求得满足条件的解，或者无解。由于回溯求解的规则是“后进先出”，自然要用到“栈”。进一步考虑：如果每件物品都有体积和价值，背包又有大小限制，求解背包中存放物品总价值最大的问题解-最优解或近似最优解。2.3、系统分析本算法采用先进后出的算法来一个一个测试可行的全部解，所以很显然要用到栈。

8、我通过建立顺序表来录入我要输入的各个物体的体积，然后通过结构体类型定义栈，把顺序表中的各个物体逐一入栈，如果各物体体积总和sum比我预定的目标体积小，那就继续入栈，有合适的组合则输出，否则说明刚才选入的物体体积即栈最顶端的那个不适合导致后面没有合适的解，所以把它POP掉，然后从它后面继续选取所要考察的物体体积。当第一个物体做栈底的所有情况满足后，我们就要考虑以第二个物体为栈底的情况，其实我并没有把第一个物体出栈，只是我读的时候把第一个物体“屏蔽”了，也就是说它虽然在栈中，但是我不考虑它，而是考虑新的栈也就是总栈中截取的我需要的那部分目标栈段，依次类推，当顺序表中所有物体都做过“栈底”后，那么就

9、没有物体可以作为参数入栈或出栈了，所有循环结束。本算法采用3重while循环嵌套来实现算出所有不重复的解2.4、运行结果分析2.5、设计总结主要是要考虑到用栈和回溯的思想，定义循环进行回溯。当然，这也用到顺序栈，首先进行判断输入时否正确。在用到循环实现每一次的回溯，找出所有的结果。3、题目三学生成绩分析系统3.1、问题描述录入、保存一个班级学生的多门课程的成绩，并对成绩进行分析。3.2、基本要求（1）通过键盘输入各学生的多门课程的成绩，建立相应的数据库；（2）对数据库中的数据进行处理，要求具有如下功能：1）按各门成绩排序；2）计算每人的平均成绩，按平均成绩排序；3）求出各门课程的平均成绩、最高

10、分、最低分、不及格人数、6069分人数，7079分人数，8089分人数，90分以上人数。4）根据姓名或学号查询某人的各门课成绩，重名情况也能处理（3）界面美观3.3、系统分析利用C#中的window窗体应用程序，将管理系统界面可视化，利用控件的相互关联实现对系统的操作，利用SQL Server数据库来对学生信息的保存，通过DataSet将数据库与窗体应用程序相互连接起来，在窗体上实现对数据库中学生信息的操作，并将其更新到数据库中。3.4、运行结果分析添加学生信息界面：学生成绩信息浏览、修改：平均成绩分析界面：按线性代数降序排列后的结果：3.5、设计总结学生成绩管理系统是基于C# window窗

11、体应用开发的程序，在编写的过程要用到数据库，最大的难度是在window窗体应用程序与数据库之间的连接问题，在连接字符串上，必需正确的写好连接字符串的服务器名称和数据库的名称。在窗体设计过程中，必须将窗体界面设计的美观和人性化，每个控件的使用必须合理。最大的难度是在将数据库的信息显示到window窗体中时，必须将数据重新处理一遍，这需要dataGridView1控件的使用，而这个控件的最大难度就是就将数据库的表返回显示到其中。4、 题目四 一元稀疏多项式简单计算器4.1、问题描述 设计一个一元稀疏多项式简单计算器4.2、基本要求一元稀疏多项式简单计算器的基本功能是：（1） 输入并建立多项式；（2

12、） 输出多项式，输出形式为整数数列：n，c1，e1，c2，e2，.，cn，en,其中n是多项式的项数，ci，ei分别是第i项的系数和指数，序列按指数降序列排序；（3） 多项式a和b相加，建立多项式a+b；（4） 多项式a和b相减，建立多项式a-b；（5） 计算多项式在x处的值；（6） 计算器的仿真界面（选做）。4.3、系统分析A：数据结构的选用 为了实现任意多项式的加法，减法，因此选择单链表的结构体，它有一个系数，指数，下一个指针3个元属； B：多项式的输入 采用头插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它；为了判断一个多项式是否输入结束

13、，定义一个结束标志，当输入非0时就继续，当输入0时，就结束一个多项式的输入； C：2个多项式的加法 它从2个多项式的头部开始，2个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为0的话，用头插法建立一个新的节点。 p的系数小于q的系数的话，就应该复制q接点到多项式中。p的系数大于q的系数的话，就应该复制p接点到多项式中。当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生。当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生 D：2个多项式的减法 它从2个多项式的头部开始，2个多项式的某一项都不为空时，如果指数相等的话，系数就应该相减；相加的

14、和不为0的话，用头插法建立一个新的节点。 p的系数小于q的系数的话，就应该复制q接点到多项式中。p的系数大于q的系数的话，就应该复制p接点到多项式中，并且建立的接点的系数为原来的相反数；当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生。当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生，并且建立的接点的系数为原来的相反数。4.4、运行结果分析测试多项式：（2x+5x8-3.1x11）+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)4.5、设计总结应该创建链表，用以表示多项式的每一项，其中链表中有表示x系数的c和指数e，以及指向下一个结点的ne

15、xt指针域，用数字1，2来表示是否是加或者减。采用冒泡排序，按指数的大小进行排序最后输出。在设计当中必须要进行多次判断，首先就要判断输入的只是否相等，相等的才能够进行加减运算；其次还要判断是否含有这项指数的系数，没有就直接复制到先得聊表中去，最后输出。三、附录1、源程序清单及结果1.1、题目一：二叉排序树于平衡二叉树的实现源程序清单：/ 二叉排序树与平衡二叉树的实现.cpp : Defines the entry point for the console application./#include stdafx.h#include stdio.h#include malloc.h#inclu

16、de stdlib.h#define NULL 0#define maxsize 100typedef struct nodeint data; /数据域struct node * left, * right; /*left指向左孩子，*right 指向右孩子dnode;int n,m,total;void sort(dnode *t,int c) /将C插入到二叉排序树t中dnode * p;if(c=t-data)if(t-right=NULL)p=(dnode *)malloc(sizeof(dnode);p-data=c;p-left=p-right=NULL;t-right=p;el

17、se sort(t-right,c);if(cdata)if(t-left=NULL)p=(dnode *)malloc(sizeof(dnode);p-data=c;p-left=p-right=NULL;t-left=p;else sort(t-left,c); dnode * creat() /创建二叉树dnode * ht;int x;ht=(dnode *)malloc(sizeof(dnode);printf(创建二叉树:);scanf(%d,&x);ht-data=x;n+;ht-left=ht-right=NULL; /先将二叉树的初始结点全部置为空scanf(%d,&x);w

18、hile(x0) /0作为结尾sort(ht,x);n+;scanf(%d,&x); return ht;void inorder(dnode * t) /中序遍历二叉排序树if(t!=NULL)m+;inorder(t-left);printf(%d,t-data);total+=m;inorder(t-right);void asl() /计算平均长度float w;w=(float)total/n;printf(结点个数为:%d,数的深度:%d,平均长度:%3.2fn,n,total,w);void find(dnode * b,int x,dnode * a) /将数据域为x的结点的地

19、址给a0，其父结点的地址给a1dnode * stackmaxsize,*p;int top;a1=NULL;if(b!=NULL)top=1;stacktop=b;while(top0)p=stacktop;top-;if(p-left-data=x|p-right-data=x) /查找两结点是否相等a1=p;if(p-data=x)a0=p;return;if(p-right!=NULL)top+;stacktop=p-right;if(p-left!=NULL)top+;stacktop=p-left;a0=p;dnode * del(dnode *t) /删除 x结点dnode *

20、p,* q,* s,* f,* a2;int flag=0,x;p=(dnode *)malloc(sizeof(dnode);f=(dnode *)malloc(sizeof(dnode);printf(请输入X的值:);scanf(%d,&x);find(t,x,a);p=a0;f=a1;if(p=NULL) /当遍历到最后也没有该结点元素时printf(没有该结点数据);exit(0);if(p-left=NULL)s=p-right;else if(t-right=NULL)s=p-left;elseq=p;s=q-left;while(s-right!=NULL)q=s;s=s-ri

21、ght;if(q=p) /找到后执行删除操作q-left=s-right;elseq-right=s-left;p-data=s-data;free(s);flag=1; /找到结点后标记为1if(flag=0)if(f=NULL)t=s;else if(f-left=p)f-left=s;elsef-right=s;return t;int main(int argc, char* argv)dnode * h;n=m=total=0;h=creat();printf(中序遍历结果为 :);inorder(h);printf(n);asl();h=del(h);inorder(h);getc

22、har();return 0;1.2、题目二：背包问题源程序清单：/ stdafx.cpp : source file that includes just the standard includes/背包问题.pch will be the pre-compiled header/stdafx.obj will contain the pre-compiled type information#include stdafx.h#include#define M 100int main()int wM;int T=0;int N=0;int k=0;int i=0;int j=1;struct

23、int sM;int top;things;printf(n请输入选择的物品的数目：);scanf(%d,&N);printf(n请输入选择的物品的体积n);for(i=0;iN;i+)printf(n第%d个物品的体积为：,i+1);scanf(%d,&wi);printf(n请输入背包最大容量：);scanf(%d,&T);for(i=0;i0&k=wk)things.sthings.top+=k;/入栈操作T-=wk;k+;if(T=0)printf(n第%d种挑选方法（ ,j );for(i=0;inext=NULL;do /*当n小于1，则重新输入*/printf(enter n:);scanf(%d,&n);while(n1);for(i=1;ic=c;p-e=e;p-next=h-next;/*用头插法建立链表*/h-next=p;return