课程设计实验报告综述.docx
《课程设计实验报告综述.docx》由会员分享，可在线阅读，更多相关《课程设计实验报告综述.docx（38页珍藏版）》请在冰点文库上搜索。
课程设计实验报告综述
课程设计成绩
总评成绩
指导老师签名
《数据结构》
课程设计报告
学院（系）：
计算机科学与工程学院
班级：
112030901
学生姓名:
余钱学号：
11203090136
指导教师：
何波傅由甲
时间：
从2014年1月6日到2014年1月12日
目录
一、课程设计概述2
二、课程设计题目及分析2
1、题目一2
1.1、问题描述2
1.2、基本要求2
1.3、系统分析3
1.4、运行结果分析3
1.5、设计总结3
2、题目二4
2.1、问题描述4
2.2、实现提示4
2.3、系统分析4
2.4、运行结果分析5
2.5、设计总结5
3、题目三6
3.1、问题描述6
3.2、基本要求6
3.3、系统分析6
3.4、运行结果分析6
3.5、设计总结9
4、题目四9
4.1、问题描述9
4.2、基本要求9
4.3、系统分析10
4.4、运行结果分析10
4.5、设计总结11
三、附录11
1、源程序清单及结果11
1.1、题目一：
11
1.2、题目二：
15
1.3、题目三：
17
1.4、题目四：
22
四、参考文献27
五、课程设计心得27
一、课程设计概述
本次课程设计共完成4个题目：
1、二叉排序树于平衡二叉树的实现
2、背包问题
3、学生成绩分析系统
4、一元稀疏多项式简单计算器
C语言C#语言
编译环境：
VC6.0MicrosoftVisualStudio2010数据库（SQLServer2008R2）
二、课程设计题目及分析
1、题目一
二叉排序树于平衡二叉树的实现
1.1、问题描述
分别采用二叉链表和顺序表作存储结构，实现对二叉排序树与平衡二叉树的操作
1.2、基本要求
（1）用二叉链表作存储结构。
1）以回车（'\n'）为输入结束标志，输入数列L，生成一棵二叉排序树T；
2）对二叉排序树T作中序遍历，输出结果；
3）计算二叉排序树T查找成功的平均长度，输出结果；
4）输入元素X，查找二叉排序树T，若存在含X的结点，则删除该结点，并作中序遍历图；否则，输出信息“无X”；
5）用数列L，生成平衡的二叉排序树BT；当插入新元素之后，发现当前的二叉排序树BT不是平衡二叉排序树，则立即将它转换成新的平衡的二叉排序树BT
6）计算平衡的二叉排序树BT的平均查找长度，输出结果。
（2）用顺序表（一位数组）作存储结构。
1）以回车（'\n'）为输入结束标志，输入数列L，生成一棵二叉排序树T；
2）对二叉排序树T作中序遍历，输出结果
3）计算二叉排序树T查找成功的平均长度，输出结果；
4）输入元素X，查找二叉排序树T，若存在含X的结点，则删除该结点，并作中序遍历图；否则，输出信息“无X”；
1.3、系统分析
按先根序序列建立二叉树的二叉链表，在遍历二叉树的时候执行一个递归程序，需要借助栈的作用，因此可以直接使用栈；在查找二叉树结点的过程中，按照遍历的顺序将每个结点遍历一遍与输入的值进行比较。
用顺序表做存储结构的时候，用带头节点的单链表来标明二叉树的双亲和左右孩子结点的位置，以便遍历，遍历过程中，则按照先后次序遍历二叉树的各个结点。
1.4、运行结果分析
测试数据：
56432140//0输入的作为结束符
中序遍历结果：
123456
结点个数：
6树的深度：
28平均长度：
4.67
输入查找的元素：
5
删除输入元素后的结果：
12346
1.5、设计总结
树和二叉树之层序遍历二叉树中的先序遍历、中序遍历、后序遍历、层序遍历均采用递归算法，而构建二叉树时也采用的是递归算法。
在层序遍历中采用队列的入队进队的方法从而实现层序遍历二叉树。
本次实验通过九个函数分别多二叉树进行先序、中序、后序以及层序四种遍历操作，层序遍历开始没有得到预想结果，原来是自己写程序不够谨慎，没有在层序遍历中写相应的输出语句，另外，在创建队列时由于自己的粗心大意，没有很好将空间分配控制语句完善好，最后导致层序遍历结果输出，经多次仔细观察才返现。
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、实现提示
可利用回溯法的设计思想来解决背包问题。
首先，将物品排成一列，然后，顺序选取物品装入背包，若已选取第i件物品后未满，则继续选取第i+1件，若该件物品“太大”不能装入，则弃之，继续选取下一件，直至背包装满为止。
如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入的物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直到求得满足条件的解，或者无解。
由于回溯求解的规则是“后进先出”，自然要用到“栈”。
进一步考虑：
如果每件物品都有体积和价值，背包又有大小限制，求解背包中存放物品总价值最大的问题解---最优解或近似最优解。
2.3、系统分析
本算法采用先进后出的算法来一个一个测试可行的全部解，所以很显然要用到栈。
我通过建立顺序表来录入我要输入的各个物体的体积，然后通过结构体类型定义栈，把顺序表中的各个物体逐一入栈，如果各物体体积总和sum比我预定的目标体积小，那就继续入栈，有合适的组合则输出，否则说明刚才选入的物体体积即栈最顶端的那个不适合导致后面没有合适的解，所以把它POP掉，然后从它后面继续选取所要考察的物体体积。
当第一个物体做栈底的所有情况满足后，我们就要考虑以第二个物体为栈底的情况，其实我并没有把第一个物体出栈，只是我读的时候把第一个物体“屏蔽”了，也就是说它虽然在栈中，但是我不考虑它，而是考虑新的栈也就是总栈中截取的我需要的那部分目标栈段，依次类推，当顺序表中所有物体都做过“栈底”后，那么就没有物体可以作为参数入栈或出栈了，所有循环结束。
本算法采用3重while循环嵌套来实现算出所有不重复的解
2.4、运行结果分析
2.5、设计总结
主要是要考虑到用栈和回溯的思想，定义循环进行回溯。
当然，这也用到顺序栈，首先进行判断输入时否正确。
在用到循环实现每一次的回溯，找出所有的结果。
3、题目三
学生成绩分析系统
3.1、问题描述
录入、保存一个班级学生的多门课程的成绩，并对成绩进行分析。
3.2、基本要求
（1）通过键盘输入各学生的多门课程的成绩，建立相应的数据库；
（2）对数据库中的数据进行处理，要求具有如下功能：
1）按各门成绩排序；
2）计算每人的平均成绩，按平均成绩排序；
3）求出各门课程的平均成绩、最高分、最低分、不及格人数、60~69分人数，70~79分人数，80~89分人数，90分以上人数。
4）根据姓名或学号查询某人的各门课成绩，重名情况也能处理
（3）界面美观
3.3、系统分析
利用C#中的window窗体应用程序，将管理系统界面可视化，利用控件的相互关联实现对系统的操作，利用SQLServer数据库来对学生信息的保存，通过DataSet将数据库与窗体应用程序相互连接起来，在窗体上实现对数据库中学生信息的操作，并将其更新到数据库中。
3.4、运行结果分析
添加学生信息界面：
学生成绩信息浏览、修改：
平均成绩分析界面：
按线性代数降序排列后的结果：
3.5、设计总结
学生成绩管理系统是基于C#window窗体应用开发的程序，在编写的过程要用到数据库，最大的难度是在window窗体应用程序与数据库之间的连接问题，在连接字符串上，必需正确的写好连接字符串的服务器名称和数据库的名称。
在窗体设计过程中，必须将窗体界面设计的美观和人性化，每个控件的使用必须合理。
最大的难度是在将数据库的信息显示到window窗体中时，必须将数据重新处理一遍，这需要dataGridView1控件的使用，而这个控件的最大难度就是就将数据库的表返回显示到其中。
4、题目四
一元稀疏多项式简单计算器
4.1、问题描述
设计一个一元稀疏多项式简单计算器
4.2、基本要求
一元稀疏多项式简单计算器的基本功能是：
（1）输入并建立多项式；
（2）输出多项式，输出形式为整数数列：
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：
多项式的输入
采用头插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它；为了判断一个多项式是否输入结束，定义一个结束标志，当输入非0时就继续，当输入0时，就结束一个多项式的输入；
C：
2个多项式的加法
它从2个多项式的头部开始，2个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为0的话，用头插法建立一个新的节点。
p的系数小于q的系数的话，就应该复制q接点到多项式中。
p的系数大于q的系数的话，就应该复制p接点到多项式中。
当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生。
当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生
D：
2个多项式的减法
它从2个多项式的头部开始，2个多项式的某一项都不为空时，如果指数相等的话，系数就应该相减；相加的和不为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，以及指向下一个结点的next指针域，用数字1，2来表示是否是加或者减。
采用冒泡排序，按指数的大小进行排序最后输出。
在设计当中必须要进行多次判断，首先就要判断输入的只是否相等，相等的才能够进行加减运算；其次还要判断是否含有这项指数的系数，没有就直接复制到先得聊表中去，最后输出。
三、附录
1、源程序清单及结果
1.1、题目一：
二叉排序树于平衡二叉树的实现
源程序清单：
//二叉排序树与平衡二叉树的实现.cpp:
Definestheentrypointfortheconsoleapplication.
//
#include"stdafx.h"
#include"stdio.h"
#include"malloc.h"
#include"stdlib.h"
#defineNULL0
#definemaxsize100
typedefstructnode
{
intdata;//数据域
structnode*left,*right;//*left指向左孩子，*right指向右孩子
}dnode;
intn,m,total;
voidsort（dnode*t,intc）//将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;
}
else
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;
intx;
ht=（dnode*）malloc（sizeof（dnode））;
printf（"创建二叉树:
"）;
scanf（"%d",&x）;
ht->data=x;
n++;
ht->left=ht->right=NULL;//先将二叉树的初始结点全部置为空
scanf（"%d",&x）;
while（x>0）//0作为结尾
{
sort（ht,x）;
n++;
scanf（"%d",&x）;
}
returnht;
}
voidinorder（dnode*t）//中序遍历二叉排序树
{
if（t!
=NULL）
{
m++;
inorder（t->left）;
printf（"%d",t->data）;
total+=m;
inorder（t->right）;
}
}
voidasl（）//计算平均长度
{
floatw;
w=（float）total/n;
printf（"结点个数为:
%d,数的深度:
%d,平均长度:
%3.2f\n",n,total,w）;
}
voidfind（dnode*b,intx,dnode*a[]）//将数据域为x的结点的地址给a[0]，其父结点的地址给a[1]
{
dnode*stack[maxsize],*p;
inttop;
a[1]=NULL;
if（b!
=NULL）
{
top=1;
stack[top]=b;
while（top>0）
{
p=stack[top];
top--;
if（p->left->data==x||p->right->data==x）//查找两结点是否相等
a[1]=p;
if（p->data==x）
{
a[0]=p;
return;
}
if（p->right!
=NULL）
{
top++;
stack[top]=p->right;
}
if（p->left!
=NULL）
{
top++;
stack[top]=p->left;
}
}
}
a[0]=p;
}
dnode*del（dnode*t）//删除x结点
{
dnode*p,*q,*s,*f,*a[2];
intflag=0,x;
p=（dnode*）malloc（sizeof（dnode））;
f=（dnode*）malloc（sizeof（dnode））;
printf（"请输入X的值:
"）;
scanf（"%d",&x）;
find（t,x,a）;
p=a[0];
f=a[1];
if（p==NULL）//当遍历到最后也没有该结点元素时
{
printf（"没有该结点数据"）;
exit（0）;
}
if（p->left==NULL）
s=p->right;
elseif（t->right==NULL）
s=p->left;
else
{
q=p;
s=q->left;
while（s->right!
=NULL）
{
q=s;
s=s->right;
}
if（q==p）//找到后执行删除操作
q->left=s->right;
else
q->right=s->left;
p->data=s->data;
free（s）;
flag=1;//找到结点后标记为1
}
if（flag==0）
{
if（f==NULL）
t=s;
elseif（f->left==p）
f->left=s;
else
f->right=s;
}
returnt;
}
intmain（intargc,char*argv[]）
{
dnode*h;
n=m=total=0;
h=creat（）;
printf（"中序遍历结果为:
"）;
inorder（h）;
printf（"\n"）;
asl（）;
h=del（h）;
inorder（h）;
getchar（）;
return0;
}
1.2、题目二：
背包问题
源程序清单：
//stdafx.cpp:
sourcefilethatincludesjustthestandardincludes
//背包问题.pchwillbethepre-compiledheader
//stdafx.objwillcontainthepre-compiledtypeinformation
#include"stdafx.h"
#include
#defineM100
intmain（）
{
intw[M];
intT=0;
intN=0;
intk=0;
inti=0;
intj=1;
struct
{
ints[M];
inttop;
}things;
printf（"\n请输入选择的物品的数目：
"）;
scanf（"%d",&N）;
printf（"\n请输入选择的物品的体积\n"）;
for（i=0;i{
printf（"\n第%d个物品的体积为：
",i+1）;
scanf（"%d",&w[i]）;
}
printf（"\n请输入背包最大容量：
"）;
scanf（"%d",&T）;
for（i=0;i{
things.s[i]=0;//将栈中的i个元素全部值为0
things.top=0;//栈顶指针指向栈底
}
do
{
while（T>0&&k<=N）
{
if（T>=w[k]）
{
things.s[things.top++]=k;//入栈操作
T-=w[k];
}
k++;
}
if（T==0）
{
printf（"\n第%d种挑选方法（",j）;
for（i=0;i{
printf（"\t%d",w[things.s[i]]）;
}
j++;
printf（"）\n"）;
}
k=things.s[--things.top];//出栈操作
things.s[things.top]=0;
T+=w[k];
k++;
}
while（!
（things.top==0&&k==N））;
return0;
}
1.3、题目三：
学生成绩分析系统
源程序清单：
平均分分析界面主要代码：
privatevoidbutton1_Click（objectsender,EventArgse）
{
//用于连接数据库的字符串
SqlConnectionsql=newSqlConnection（"DataSource=Localhost;InitialCatalog=Mydb;IntegratedSecurity=True"）;
SqlDataAdaptersda=newSqlDataAdapter（"selectIDas学号，nameas姓名，,mathas线性代数,englishas大学英语,shujuas数据结构1,pingas平均分fromTable_studentwherepingbetween60and69",sql）;
DataSetds=newDataSet（）;
sda.Fill（ds）;
dataGridView1.DataSource=ds.Tables[0];//将查询后得出的结果返回显示º?
在dataGridView1中
textBox1.Text=（dataGridView1.RowCount-1）.ToString（）;
}
privatevoidbutton2_Click（objectsender,EventArgse）
{
SqlConnectionsql=newSqlConnection（"DataSource=Localhost;InitialCatalog=Mydb;IntegratedSecurity=True"）;
SqlDataAdaptersda=newSqlDataAdapter（"selectIDas学号,nameas姓名,mathas线性代数,englishas大学英语,shujuas数据结构1,pingas平均¨分fromTable_studentwherepingbetween70and79",sql）;
DataSetds=newDataSet（）;
sda.Fill（ds）;
dataGridView1.DataSource=ds.Tables[0];
textBox1.Text=（dataGridView1.RowCount-1）.ToString（）;
}
privatevoidbutton5_Click（objectsender,EventArgse）
{
//用于数据库连接的字符串
SqlConnectionsql=newSqlConnection（"DataSource=Localhost;InitialCatalog=Mydb;IntegratedSecurity=True"）;
//用于筛出平均分成绩高分的学生
Sq
升级会员 