第1页 / 共27页
第2页 / 共27页
第3页 / 共27页
第4页 / 共27页
第5页 / 共27页
第6页 / 共27页
第7页 / 共27页
第8页 / 共27页
数据结构+实验报告+线性表及其应用(多项式相加、相乘)等.doc
实验一 线性表及其应用
一、 实验目的和要求
1、掌握线性表的插入、删除、查找等基本操作设计与实现
2、学习利用线性表提供的接口去求解实际问题
3、熟悉线性表的的存储方法
二、 实验内容和原理
1、实验内容：设计一个一元多项式的简单计算器，其基本功能有①
输入并建立多项式；②输出多项式；③多项式相加。可利用单链表
或单循环链表实现之。
2、实验原理：以线性表来描述一元多项式，存储结构采用单链表，
每个结点存储的多项式中某一项的系数和指数，建立单链表时指数
高的结点列于指数低的 结点之后，即线性表的元素按指数递增有序
排列。
三、 实验环境
Visual C++ 6.0 及 PC 机
四、 算法描述及实验步骤
思想算法：
以线性表来描述一元多项式，存储结构采用单链表，每个结点存储的多项
式中某一项的系数和指数，建立单链表时指数高的结点列于指数低的结点之后，
即线性表的元素按指数递增有序排列。
例如构造两个多项式 ha:
5X3+4X2+3X+2
hb: X2+X+1
多项式加法：定义指针 p,q 分别指向 ha,hb
i.p->exp==q->exp ,r->coef=p->coef+q->coef,pa,pb 下移;
1
ii.p->expexp ,r->coef=q->coef;r->exp=q->exp;,q 下移
iii.pa->exp>pb->exp, r->exp=p->exp;r->coef=p->coef;,p 下移
iv.p!=NULL,pb==NULL.相当于 iii.
V.q==NULL,pb!=NULL.相当于 ii.
其流程图如下：
多项式乘法：定义指针 fp,gp 分别指向 f,g
1.将两多项式最大指数相加并赋于 maxp，并置 g
2.用 for 循环求指数等于 maxp 时相乘的系数
3. (fp!=NULL)&&(gp!=NULL), p=fp->exp+gp->exp
1.p>maxp, fp=fp->next;
2. pnext;
3.p=maxp, x+=fp->coef*gp->coef; fp=fp->next;gp=gp->next;
2
五、 实验结果
1.分别输入两个多项式: 5X3+4X2+3X+2 和 X2+X+1,然后输出结果如下:
2.分别输入两个多项式：6X4+4X2+2 和 5X+6，然后输出结果如下：
3
六、 总结
此次上机实验应用了线性表实现了一次实际操作，完成了一个一元多项式
的简单计算器，不仅对此次编译程序的算法思想有了新的认识，还让我深刻的
体会到了线性表的重要性以及其应用的方便，并且对指针加深了映象，应用了
书本中的算法思想，对我以后的编译以及完成新的程序有很大的帮助。
附录：
1.建立多项式列表代码如下：
mulpoly *creatpoly()/*建立多项式列表*/
{mulpoly *head,*r,*s;/*设中间变量*/
int m,n;
head=(mulpoly *)malloc(sizeof(mulpoly));/*头结点申请空间*/
printf("\ninput coef and exp:\n");
scanf("%d%d",&n,&m);/*输入多项式系数和指数*/
r=head;/*尾指针指向头指针*/
while(n!=0)/*将输入的多项式存放在 S 中*/
{s=(mulpoly*)malloc(sizeof(mulpoly));
s->coef=n;
s->exp=m;
r->next=s;
r=s;
/*printf("input coef and exp:\n");*/
scanf("%d%d",&n,&m);/*再次输入多项式系数和指数*/
}
r->next=NULL;/*将尾指针置空*/
4
head=head->next;/*将 head 哑结点向前跑一个结点，使其不为空*/
return (head);/*返回多项式*/
}
2.两个多项式相加代码如下：
mulpoly *polyadd(mulpoly *ha,mulpoly *hb)/*两个多项式相加*/
{mulpoly *hc,*p,*q,*s,*r;/*声明结构体型*/
int x;
p=ha;
q=hb;
hc=(mulpoly *)malloc(sizeof(mulpoly));/*申请结点空间*/
s=hc;
while((p!=NULL)&&(q!=NULL))/*两多项式不为空*/
if(p->exp==q->exp)/*指数相等*/
{x=p->coef+q->coef;/*系数相加*/
if(x!=0)/*系数不为零*/
{r=(mulpoly*)malloc(sizeof(mulpoly));/*结果放 r 中存放*/
r->exp=q->exp;
r->coef=x;
s->next=r;
s=r;
}
p=p->next;/*多项式前进一项*/
q=q->next;/*多项式前进一项*/
}
else if(p->expexp)/*比较指数大小*/
{r=(mulpoly *)malloc(sizeof(mulpoly));
r->coef=q->coef;
r->exp=q->exp;
s->next=r;
s=r;
q=q->next;
}
else
{r=(mulpoly *)malloc(sizeof(mulpoly));
r->exp=p->exp;
r->coef=p->coef;
s->next=r;
s=r;
p=p->next;
}
while(p!=NULL)/*当多项式 p 中不为空时照抄*/
{r=(mulpoly *)malloc(sizeof(mulpoly));
r->exp=p->exp;
5
r->coef=p->coef;
s->next=r;
s=r;
p=p->next;
}
while(q!=NULL)/*当多项式 q 中不为空时照抄*/
{r=(mulpoly *)malloc(sizeof(mulpoly));
r->exp=q->exp;
r->coef=q->coef;
s->next=r;
s=r;
q=q->next;/*将最终尾指针置空*/
}
s->next=NULL;
r=hc;
hc=hc->next;
free(r);/*释放 r*/
return(hc);/*返回结果*/
}
3.两个多项式相乘代码如下：
mulpoly*polymulti(mulpoly *f,mulpoly *g)
{mulpoly *fp,*gp,*hp,*q,*h;
/*两个多项式相乘*/
int maxp,p,r,x;
mulpoly *reverse(mulpoly *q);/*函数声明*/
maxp=f->exp+g->exp;/*将两多项式最大指数相加并赋于 maxp*/
h=(mulpoly *)malloc(sizeof(mulpoly));
hp=h;
g=reverse(g);/*逆置 g*/
for(r=maxp;r>=0;r--)/*循环求指数等于 r 时相乘的系数*/
{x=0;/*设 x 初始值为 0*/
fp=f;
gp=g;
while((fp!=NULL)&&(gp!=NULL))/*循环求相乘之后指数为 r 时的系数*/
{p=fp->exp+gp->exp;/*f 的指数加上 g 逆置后的指数并给 p*/
if(p>r)/*比较 p，r*/
fp=fp->next;/*p 大，fp 到下一个结点，以确保 p 等于 r*/
else
if(pnext;/*p 小，gp 到下一个结点，以确保 p 等于 r*/
else/*p 等于 r*/
{x+=fp->coef*gp->coef;/*将相乘之后指数为 r 时的系数给 x*/
fp=fp->next;
gp=gp->next;
6
}
}
if(abs(x)>1e-6)/*条件限制，使得所求多项式系数绝对值不能太小*/
{q=(mulpoly *)malloc(sizeof(mulpoly));
q->exp=r;
q->coef=x;
q->next=NULL;
hp->next=q;
hp=q;
}/*将所求结果给 hp，h*/
}
hp=h;
h=h->next;/*将 h 的哑结点前进，使不为空*/
free(hp);/*释放 hp*/
return h;/*返回结果*/
}
4.定义链表逆置函数
mulpoly *reverse(mulpoly *q)/*定义链表逆置函数*/
{mulpoly *p1,*p2;
if(q!=NULL)/*确保所要逆置多项式不为空*/
{p1=q->next;/*使 p1 指向下一个结点*/
q->next=NULL;/*将 q->next 为空*/
while(p1!=NULL)/*循环使相邻两个结点逆置，直到最后一个逆置为头结点
*/
}
{p2=p1->next;
p1->next=q;
q=p1;
p1=p2;
}
}
return q;/*返回逆置结果*/
5.输出多项式代码如下：
void polyout(mulpoly *head) /*输出多项式*/
{mulpoly *q,*p;
/*p=head->next;*/
p=head;
while(p!=NULL)/*循环输出多项式的系数和指数*/
{printf("%dx%d ",p->coef,p->exp);
p=p->next;
}
printf("\n");
}
7
实验二 哈弗曼树及哈弗曼编码译码的实现
一、 实验目的和要求
1、掌握树的有关图相关操作算法;
2、熟悉树的基本存储方法;
3、学习利用树求解实际问题。
二、 实验内容和原理
1、实验内容：（1）构造哈弗曼树；（2）对单个结点编码；（3）输出树；（4）编
码；（5）译码。
2、实验原理：通过树的有关图的相关操作算法，以及树的基本存储方法，利用
树来构造哈夫曼树及哈夫曼编码，输出哈夫曼树及哈夫曼编码，完成编码与译
码的算法。
三、 实验环境
Visual C++ 6.0 及 PC 机
四、 算法描述及实验步骤
思想算法：
一棵有 n 个叶子结点的哈夫曼树有 2n-1 个结点，所以可用大小为 2n-1 个元
素的数组构造静态链表来存储哈夫曼树，一个数组元素中存放一个结点。结点的
结构可以这样来考虑，由于每个叶子结点都有一个权重，构造哈夫曼树的过程中
每个分枝结点的权重等于两个孩子结点权重的和，所以应该有一个权重域和指向
左右孩子的两个指针域；另外在建成哈夫曼树之后，为了求得每个叶子结点的哈
夫曼编码，需要走一条从叶子结点到根结点的路径，而译码的过程是从根结点出
发到叶子结点的不断匹配的过程，所以既需要知道孩子结点的信息，也需要知道
双亲结点的信息，应该再有一个指向双亲结点的指针域。由此可知，每个结点至
少应该有一个权重域 weight 和 3 个指针域 parent,lchild 和 rchild，也是就是说，
要用静态三叉链表来表示哈夫曼树。
由于在实际构造哈夫曼树时，是由叶子结点的权重逐级构造最后生成树根，
且在构造过程中公与叶子结点的权重有关而与叶子结点的数据域外无关，所以构
造算法的实现中可以不考虑叶子结点的数据域，并且在静态三叉链表中从叶子结
点开始存放，然后不断地反两棵权重最小的子树合并成为一棵权值为其和的较大
的子树，逐步生成各内部结点直到树根。
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
