线性表及多项式操作.docx
- 文档编号:16398730
- 上传时间:2023-07-13
- 格式:DOCX
- 页数:12
- 大小:17.58KB
线性表及多项式操作.docx
《线性表及多项式操作.docx》由会员分享,可在线阅读,更多相关《线性表及多项式操作.docx(12页珍藏版)》请在冰点文库上搜索。
线性表及多项式操作
实验报告
实验名称
线性表及多项式的运算
指导教师
邹志强
实验类型
验证
实验学时
2+2
实验时间
一、实验目的和要求
1.掌握线性表的两种基本存储结构及其应用场合:
顺序存储和链接存储。
2.掌握顺序表和链表的各种基本操作算法。
3.理解线性表应用于多项式的实现算法。
二、实验环境(实验设备)
Dev-C++
三、实验原理及内容
内容:
1.参照程序~程序,编写程序,完成顺序表的初始化、查找、插入、删除、输出、撤销等操作。
2.已知代表头节点的单链表的类型定义,参照程序~程序,编写程序,完成带表头节点的单链表的初始化、查找、插入、删除、输出、撤销等操作。
3.以第2题所示带表头节点的单链表为例,编写程序实现单链表的逆置操作(原单链表为(a0,a1,...an-1),逆置后为(an-1,an-2,...,a0),要求不引入新的存储空间。
)
4.以第2题所示带表头节点的单链表为存储结构,编写程序实现将单链表排序成为有序单链表的操作。
5.已知带表头节点一元多项式的类型定义,编写程序实现一元多项式的创建、输出、撤销以及两个一元多项式相加和相乘的操作。
实验报告
三、实验过程及代码等
1.顺序表的基本运算
顺序表的类型定义:
typedefstruct
{
intn;
intmaxLength;
int*element;
}SeqList;
顺序表的初始化:
typedefintStatus;
StatusInit(SeqList*L,intmSize)
{
L->maxLength=mSize;
L->n=0;
L->element=(int*)malloc(sizeof(Status)*mSize);
if(!
L->element)
链表逆置操作
statusNizhi(headerList*L)
{
Node*p,*q,*r;
p=L->head;
q=p->link;
while(q)
{
r=q->link;
q->link=p;
p=q;
q=r;
}
L->head->link->link=NULL;
L->head->link=p;
return0;
}调用结果:
4.单链表排序操作(冒泡)
#include<>
#include<>
typedefstructnode
{
intelement;
structnode*next;
}Node,*LinkList;
LinkListCreat(void)/*创建链表,输入数据,结束标志为当输入的数据为0*/
{
LinkListH,p,q;
intn;
n=0;
p=q=(LinkList)malloc(sizeof(Node));
printf("输入数据:
(输入0标志着输入完成)\n");
scanf("%d",&p->element);
H=NULL;
while(p->element!
=0)
{
n=n+1;
if(n==1)
H=p;
else
q->next=p;
q=p;
p=(LinkList)malloc(sizeof(Node));
scanf("%d",&p->element);
}
q->next=NULL;
return(H);
}
LinkListPaixu(LinkListl)/*排序*/
{
LinkListp,q;
inttemp;
for(p=l;p!
=NULL;p=p->next)
{
for(q=p->next;q!
=NULL;q=q->next)
{
if(p->element>q->element)
{
temp=q->element;
q->element=p->element;
p->element=temp;
}
}
}
returnl;
}
intmain()
{
LinkListL,S,K;
L=Creat();
printf("初始化的单链表为:
\n");
for(S=L;S!
=NULL;S=S->next)
printf("%d",S->element);
Paixu(L);
printf("\n按递增排序后的链表为:
\n");
for(K=L;K!
=NULL;K=K->next)
printf("%d",K->element);
return0;
}
调用结果:
5.多项式操作
多项式的类型定义():
typedefstructPNode
{
intcoef;
intexp;
structPNode*link;
}PNode;
typedefstruct
{
structPNode*head;
}polynominal;
多项式的创建():
voidCreate(polynominal*p)
{
PNode*pn,*pre,*q;
p->head=(void*)malloc(sizeof(PNode));
p->head->exp=-1;
p->head->link=NULL;
printf("请输入多项式\n");
for(;;)
{
pn=(void*)malloc(sizeof(PNode));
printf("coef:
\n");
scanf("%d",&pn->coef);
printf("exp:
\n");
scanf("%d",&pn->exp);
if(pn->exp<0)break;
pre=p->head;
q=p->head->link;
while(q&&q->exp>pn->exp)
{
pre=q;
q=q->link;
}
pn->link=q;
pre->link=pn;
}
}
多项式的输出():
voidOutput(polynominalL)
{
PNode*p;
p=>link;
while(p->link!
=NULL)
{
printf("%d*X^%d+",p->coef,p->exp);
p=p->link;
}
printf("%d*X^%d\n",p->coef,p->exp);
}
多项式的析构():
voidDestroy(polynominal*L)
{
PNode*p;
while(L->head)
{
p=L->head->link;
free(L->head);
L->head=p;
}
}
两个多项式的加法():
voidAdd(polynominal*px,polynominal*qx)
{
PNode*q,*q1=qx->head,*p,*temp;
p=px->head->link;
q=q1->link;
while(p&&q)
{
while(p->exp
{
q1=q;q=q->link;
}
if(p->exp==q->exp)
{
q->coef=q->coef+p->coef;
if(q->coef==0)
{
q1->link=q->link;
free(q);
q=q1->link;
p=p->link;
}
else
{
q1=q;
q=q->link;
p=p->link;
}
}
else
{
temp=(void*)malloc(sizeof(PNode));
temp->coef=p->coef;
temp->exp=p->exp;
temp->link=q1->link;
q1->link=temp;
p=p->link;
}
}
}
两个多项式的乘法():
polynominal*Mult(polynominal*a,polynominal*b)
{
PNode*an,*bn;
polynominaltemp;
printf("初始化temp,输入000-1");
Create(&temp);
an=a->head;
bn=b->head;
while(an->link)
{
an=an->link;
while(bn->link)
{
bn=bn->link;
bn->exp+=an->exp;
bn->coef*=an->coef;
}
Add(b,&temp);
bn=b->head;
while(bn->link)
{
bn=bn->link;
bn->exp-=an->exp;
bn->coef/=an->coef;
}
bn=b->head;
}
return&temp;
}
调用主函数测试:
voidmain()
{
polynominallistA,listB,listC,listD,temp;
intchoose=0;
printf("请选择操作:
1.多项式相加2.多项式相乘\n");
scanf("%d",&choose);
switch(choose)
{
case1:
{
Create(&listA);
Create(&listB);
printf("多项式A为:
");
Output(listA);
printf("多项式B为:
");
Output(listB);
Add(&listA,&listB);
printf("\n");
printf("A与B相加得:
");
Output(listB);
Destroy(&listA);
Destroy(&listB);
}break;
case2:
{
Create(&listC);
Create(&listD);
printf("多项式C为:
");
Output(listC);
printf("多项式D为:
");
Output(listD);
//Mult(&listC,&listD);
Output(*Mult(&listC,&listD));
Destroy(&listC);
Destroy(&listD);
}break;
}
}
运行结果:
(1)多项式加法:
(2)多项式乘法:
实验报告
四、实验小结(包括问题和解决方法、心得体会、意见与建议等)
一、前面写顺序表的时候没有遇到什么问题,只是有两个地方有点小问题但很快解决了;
(1)(void*)malloc(sizeof(PNode))在malloc前面漏掉强制类型转换。
(2)for(inti=1,i 二、刚开始写链表的代码时,总是搞不清一个链表内的成员和关系,后来一直到完成多项式加法时才对链表有了一个较为全面的认识。 三、在写多项式乘法时,在网上找了一个乘法的算法,可是改来改去还是会出问题,在输出最终结果时输出的系数和指数是地址而不是数,和舍友讨论了很久也没有解决,我后来在舍友的帮助下完成了多项式的乘法;但是之前的那段没有找出问题的代码还是没有找到答案,而且目前还以注释的形式保留在源代码中。 四、希望自己能够在实验和作业中有所收获,使得自己的代码水平有一定的提升。 五、指导教师评语 成绩 批阅人 日期
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性 多项式 操作
![提示](https://static.bingdoc.com/images/bang_tan.gif)