数据结构实验一题目3一元多项式.docx
《数据结构实验一题目3一元多项式.docx》由会员分享，可在线阅读，更多相关《数据结构实验一题目3一元多项式.docx（22页珍藏版）》请在冰点文库上搜索。
数据结构实验一题目3一元多项式
数据结构实验报告
实验名称：
实验一题目3一元多项式
学生姓名：
卢跃凯
班级：
信通12班
班内序号：
13号
学号：
日期：
2013/11/13
1．实验要求
1实验目的
通过选择下面两个题目之一进行实现，掌握如下内容：
Ø掌握二叉树基本操作的实现方法
Ø学习使用二叉树解决实际问题的能力
题目1
Ø根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。
Ø二叉树的基本功能：
Ø1、二叉树的建立
Ø2、前序遍历二叉树
Ø3、中序遍历二叉树
Ø4、后序遍历二叉树
Ø5、按层序遍历二叉树
Ø6、求二叉树的深度
Ø7、求指定结点到根的路径
Ø8、二叉树的销毁
Ø9、其他：
自定义操作
Ø编写测试main（）函数测试线性表的正确性
2.程序分析
2.1存储结构
采用二叉树的存储结构，其中每个二叉树的结点定义了一个结构体BiNode*lch;，该结构体包含三个元素，分别是一个T类型的数据域data，一个指向T类型的指针左孩子BiNode*lch;，一个指向T类型的指针右孩子，示意图如图所示。
在对二叉树的层序遍历算法的实现过程中，采用了队列的存储结构。
队列的存储结构示意如图所示：
在二叉树的创建中，对于二叉树中每个结点的data域的赋值，我们事先把这些data储存在一个数组
中，通过对数组元素的调用事先对二叉树中每个结点的data域的赋值。
2.2关键算法分析
一：
二叉树的建立：
A．自然语言描述：
1首先判断调用的数组是否为空，如果该数组不为空，则把调用的数组的第一个元素的赋给根节点的data域。
2采用递归的思想，分别将根节点的左右孩子作为根节点，递归调用该函数。
完成对左右子树的赋值。
3如果为空，直接将一个已经初始化好的根节点置为空。
B．代码详细分析：
voidBiTree:
:
Create（BiNode*&R,Tdata[],inti）
{
//i表示位置，从1开始
if（data[i-1]!
=0）
{
R=newBiNode;//创建根结点
R->data=data[i-1];
Create（R->lch,data,2*i）;//创建左子树
Create（R->rch,data,2*i+1）;//创建右子树
}
else
R=NULL;
}
二：
前序遍历二叉树：
A.自然语言描述：
1.首先判断根结点是否为空，如果不为空，输出根结点data域中所存储的值。
2.递归调用函数PreOrder,遍历左子树。
3.递归调用函数PreOrder,遍历右子树。
B．代码详细分析：
voidBiTree:
:
PreOrder（BiNode*R）
{
if（R!
=NULL）
{
cout<data;//访问结点
PreOrder（R->lch）;//遍历左子树
PreOrder（R->rch）;//遍历右子树
}
}
三：
中序遍历二叉树：
B.自然语言描述：
1.首先判断根结点是否为空，如果不为空，递归调用函数InOrder,遍历左子树。
2.输出根结点data域中所存储的值。
3.递归调用函数InOrder,遍历右子树。
B．代码详细分析：
voidBiTree:
:
InOrder（BiNode*R）
{
if（R!
=NULL）
{
InOrder（R->lch）;//遍历左子树
cout<data;//访问结点
InOrder（R->rch）;//遍历右子树
}
}
三：
后序遍历二叉树：
C.自然语言描述：
1.首先判断根结点是否为空，如果不为空，递归调用函数PostOrder,遍历左子树。
2.递归调用函数PostOrder,遍历右子树。
3.输出根结点data域中所存储的值。
B．代码详细分析：
voidBiTree:
:
PostOrder（BiNode*R）
{
if（R!
=NULL）
{
PostOrder（R->lch）;
PostOrder（R->rch）;
cout<data<<'';
}
}
三：
层序遍历二叉树：
D.自然语言描述：
1.根节点非空，入队。
2.如果队列不空
{
队头元素出队
访问该元素
若该结点的左孩子非空，则左孩子入队；
若该结点的右孩子非空，则右孩子入队；
}
B．代码详细分析
voidBiTree:
:
LevelOrder（BiNode*R）
{
BiNode*queue[100];
intf=0,r=0;
if（R!
=NULL）
queue[++r]=R;
while（f!
=r）
{
BiNode*p=queue[++f];
cout<data<<'';
if（p->lch!
=NULL）
queue[++r]=p->lch;
if（p->rch!
=NULL）
queue[++r]=p->rch;
}
}
六：
求二叉树的深度：
A.自然语言描述：
1：
判断根节点是否为空，如果根节点为空，返回值d.
2：
递归调用求二叉树的深度，函数的参数改为根节点的左孩子，返回值d+1
3：
递归调用求二叉树的深度，函数的参数改为跟结点的右孩子，返回值d+1
6：
返回4与5步中得出深度较大的那个数作为二叉树的深度数
B．代码详细分析
intBiTree:
:
GetDepth（BiNode*R,intd）
{
if（R==NULL）
returnd;
else
{
intm=GetDepth（R->lch,d+1）;
intn=GetDepth（R->rch,d+1）;
returnn>m?
n:
m;
}
}
八：
求二叉树的叶子结点数：
B.自然语言描述：
1：
判断根节点是否为空，如果为空，返回0
2：
如果根节点不为空，切根节点的左右孩子同时为空，返回1
3：
递归调用求二叉树的叶子节点数函数，参数改为根节点的左孩子
4：
递归调用求二叉树的叶子结点数函数，参数改为根节点的右孩子
5：
返回根节点的左右子树的叶子结点数之和
C.代码详细分析：
intBiTree:
:
GetLeafNum（BiNode*R）
{
if（R==NULL）return0;
if（（R->lch==NULL）&&（R->rch==NULL））return1;
else
{
intm=GetLeafNum（R->lch）;
intn=GetLeafNum（R->rch）;
returnm+n;
}
}
7、求指定结点到根的路径。
自然语言描述：
1.判断根结点是否为空，若为空，returnfalse.
2.否则判断根结点的data值是否等于指定值，若等于returntrue。
3.否则判断根结点的左孩子的data值是否等于指定值，若等于returntrue。
4.否则判断根结点的右孩子的data值是否等于指定值，若等于returntrue。
5.否则returnfalse。
代码详细分析：
boolBiTree:
:
path（BiNode*R,Te）
{
if（R==NULL）
returnfalse;
else
{
if（R->data==e）
{cout<data;returntrue;}
elseif（path（R->lch,e））
{cout<data;returntrue;}
elseif（path（R->rch,e））
{cout<data;returntrue;}
elsereturnfalse;
}
}
七：
二叉树的销毁：
A.自然语言描述：
1：
判断根节点是否为空
2：
如果根节点不为空
3：
递归调用二叉树的销毁函数，参数改为根节点的左孩子
4：
递归调用二叉树的销毁函数，参数改为根节点的右孩子
5：
释放根节点指向的内存
B.代码详细分析：
voidBiTree:
:
Release（BiNode*R）
{
if（R!
=NULL）
{
Release（R->lch）;//释放左子树
Release（R->rch）;//释放右子树
deleteR;//释放根结点
}
}
3.程序运行结果
主函数流程图如下：
一、头插法构造单链表：
1建立并初始化头指针front=newNode；front->next=NULL
2在堆中建立新结点：
Node*s=newNode；
3将a[i]写入到新结点的数据域：
s->data=a[i]；
4修改新结点的指针域：
s->next=front->next；
5修改头结点的指针域，将新结点加入到链表中：
front->next=s；
二、
一元多项式求和：
第一种情况：
若p->data.expndata.expn，即A链表当前结点p的指数小于B链表的当前结点q的指数,则p结点保留不变,然后p指向A链表的下一个结点继续进行比较。
1p_prior=p；
2p=p->next；
第二种情况：
若p->data.expn＜q->data.expn，即A链表当前结点p的指数大于B链表的当前结点q的指数,则应将ｑ结点加入到Ａ链表ｐ结点之前，然后ｑ指向Ｂ链表的下一个结点，继续进行比较。
1p_prior->next=q；
2p_prior=q；
3
q=q->next；
4p_prior->next=p；
第三种情况：
若p->data.expn＝＝q->data.expn，即A链表当前结点p的指数等于B链表的当前结点q的指数,则两结点为同类项，应将两结点的系数求和，此时又分为两种情况：
（ａ）若合并的系数为０，计量同类项抵消，则删除ｐ结点；
（ｂ）若合并的系数不为０，将其重新赋予ｐ结点。
两结点合并后可删除ｑ结点，并且令ｐ和ｑ分别指向各自的下一个结点继续进行比较。
（ａ）若合并的系数为０：
①p_prior->next=p->next；
②deletep；
3p=p_prior->next；
4Node*temp=q；
5q=q->next；
6deletetemp；
（ｂ）若合并的系数不为０：
①p_prior=p；
2p=p->next；
③Node*temp=q；
④q=q->next；
5deletetemp；
第四种情况：
若ｐ为空且ｑ不为空，则应将ｑ结点及其后续所有结点追加到Ａ链表的最后：
p_prior->next=q；
注：
减法和加法用的是同一个函数，若是减法则将减数的多项式系数变成相反数，再进行加法运算即刻
6
三、一元多项式相乘
1申请三个动态数组d1、d2、d3，其长度为两个多项式最高幂相乘后的幂数；
2为d1与d2赋初为0；
3分别用d1与d2分别储存两个多项式的系数，比如说的一个多项式指数为i的系数存在d1[i]里面，其他没有存过系数的元素均为0（相当于将二项式延长，没有的项则系数为0）；
4利用柯西乘积完成多项式相乘，用d3储存乘积结果，即系数，并且系数不为0的项通过申请动态结构数组来储存，最后构造链表，具体代码：
Node*p_prior=GetFirst（）;
Node*p=p_prior->next;
Node*q=B.GetFirst（）->next;
intm=GetMax（）;
double*d1=newdouble[m+B.GetMax（）+1];
double*d2=newdouble[m+B.GetMax（）+1];
double*d3=newdouble[m+B.GetMax（）+1];
for（inti=0;i<=m+B.GetMax（）;i++）
{
d1[i]=0;
d2[i]=0;
}
for（inti=0;i<=m+B.GetMax（）;i++）
{
if（i==p->data.exp）//有这一指数项则在i的位置存储此项系数，为数组赋值
{
d1[i]=p->data.coef;
p=p->next;
if（p==NULL）//一旦p为空就跳出循环,p所指的一项后面的项系数在前面已经设为0
{
break;
}
}
}
for（inti=0;i<=m+B.GetMax（）;i++）
{
if（i==q->data.exp）
{
d2[i]=q->data.coef;
q=q->next;
if（q==NULL）
{
break;
}
}
}
intn=0;//记录新二项式的项数
for（inti=0;i<=m+B.GetMax（）;i++）
{
d3[i]=0;
for（intj=0;j<=i;j++）//算法柯西乘法原理
{
d3[i]+=d1[j]*d2[i-j];
}
if（d3[i]!
=0）//不为0的就自增一项
{
n++;
}
}
element*e3=newelement[n];
for（inti=0,j=0;i<=m+B.GetMax（）;i++）//构造每一项
{
if（d3[i]!
=0）
{
e3[j].coef=d3[i];
e3[j].exp=i;
j++;
}
}
四、一元多项式求导
1初始化工作指针element*p=front->next；
2系数：
p->coef*=p->exp；
3指数：
p->exp-=1；
4p后移；
具体代码：
voidPoloyList:
:
Der（）
{
Node*p_prior=GetFirst（）;
Node*p=p_prior->next;
intm=GetMax（）;
if（p->data.exp==0）//常数求导
{
p_prior->next=p->next;
Node*temp=p;
p=p->next;
deletetemp;
}
while（p）//一般非常数求导
{
p->data.coef*=p->data.exp;
p->data.exp-=1;
if（p->next==NULL）
{
m=p->data.exp;
}
p=p->next;
}
}
计算关键算法的时间、空间复杂度：
1.头插法构造单链表：
O（n）
2.求和：
O（n）
3.求导：
O（n）
4.乘法：
O（n^2）
空间复杂度：
50%
3.程序运行结果
1.测试主函数流程：
流程图如下图所示：
2.测试条件：
一次只能进行两个多项式的操作，只能按升幂输入二项式。
每次运行程序，只可进行一种操作运算。
3.测试结论：
4.
5.
相乘
6.
求导：
7.
相加：
4.总结
1、调试时出现的问题及解决的方法
调试时，总会遇到一些循环错误及一些未知的重复定义和语法错误，之后就是自己一遍一遍的调试及上网查阅资料或问同学。
在编程的过程中，自己一些语法规范及良好的习惯仍没有养成，导致小错误不断，都是花费了大量的时间与精力，最终才获得了成功！
2、心得体会
通过此次试验，我更加深刻地了解到了线性表，尤其是单链表的使用和类的运用。
并且也感受到了在编一个相对比较大的程序时，良好编程习惯的重要性，它能极其方便的帮助你找到错误，并最终得到解决。
3、下一步的改进
通过本次试验，我总结出自己很多的问题，尤其是自己的良好编程习惯仍未养成，以致自己在调试时耗费大量的时间与精力。
因此，在日后的编程学习过程中时，一定要养成良好的编程习惯，多看看老师平时编的程序，养成好习惯！
！
升级会员 