线性表及多项式操作.docx
- 文档编号:17896150
- 上传时间:2023-08-04
- 格式:DOCX
- 页数:18
- 大小:19.19KB
线性表及多项式操作.docx
《线性表及多项式操作.docx》由会员分享,可在线阅读,更多相关《线性表及多项式操作.docx(18页珍藏版)》请在冰点文库上搜索。
线性表及多项式操作
实验报告
实验名称
线性表及多项式的运算
指导教师
邹志强
实验类型
验证
实验学时
2+2
实验时间
2016.9.16
一、实验目的和要求
1.掌握线性表的两种基本存储结构及其应用场合:
顺序存储和链接存储。
2.掌握顺序表和链表的各种基本操作算法。
3.理解线性表应用于多项式的实现算法。
二、实验环境(实验设备)
Dev-C++
三、实验原理及内容
内容:
1.参照程序2.1~程序2.7,编写程序,完成顺序表的初始化、查找、插入、删除、输出、撤销等操作。
2.已知代表头节点的单链表的类型定义,参照程序2.8~程序2.14,编写程序,完成带表头节点的单链表的初始化、查找、插入、删除、输出、撤销等操作。
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)//判断顺序表是否申请成功
returnERROR;
returnOK;
}
顺序表的查找
StatusFind(SeqListL,inti,int*x)
{
if(i<0||i>L.n-1)//越界判断
returnERROR;
*x=L.element[i];
returnOK;
}
顺序表的插入:
StatusInsert(SeqList*L,inti,intx)
{
intj;
if(i<-1||i>L->n-1)
returnERROR;
if(L->n==L->maxLength)
returnERROR;
for(j=L->n-1;j>i;j--)
L->element[j+1]=L->element[j];
L->element[i+1]=x;
L->n++;
returnOK;
}
顺序表的删除:
StatusDelete(SeqList*L,inti)
{
intj;
if(i<0||i>L->n-1)
returnERROR;
if(!
L->n)
returnERROR;
for(j=i+1;j
L->element[j-1]=L->element[j];
L->n--;
returnOK;
}
顺序表的输出:
StatusOutput(SeqListL)//输出
{
inti;
if(!
L.n)
returnERROR;
for(i=0;i printf("%d",L.element[i]); returnOK; } 顺序表的析构: voidDestroy(SeqList*L) { L->n=0; L->maxLength=0; free(L->element); } 用主函数进行测试: #include #include #defineERROR0 #defineOK1 intmain() { inti; SeqListlist; Init(&list,10); for(i=0;i<10;i++) Insert(&list,i-1,i); Output(list); printf("\n"); Delete(&list,0); Output(list); Destroy(&list); } 调用结果: 实验报告 2.带表头节点单链表的基本运算 单链表的类型定义(struct.h): typedefstructNode { intelement;//结点的数据域 structNode*link;//结点的指针域 }Node; typedefstruct { structNode*head; intn; }headerList; typedefintstatus; 单链表的初始化(Init.c): statusInit(headerList*L) { L->head=(Node*)malloc(sizeof(Node)); if(! L->head) returnERROR; L->head->link=NULL; L->n=0; returnOK; } 单链表的查找(Find.c): statusFind(headerListL,inti,int*x) { Node*p; intj; if(i<0||i>L.n-1)//对i进行越界检查 returnERROR; p=L.head; for(j=0;j p=p->link;//从头结点开始查找ai *x=p->element;//通过x返回ai的值 returnOK; } 单链表的插入(Insert.c): statusInsert(headerList*L,inti,intx) { Node*p,*q; intj; if(i<-1||i>L->n-1) returnERROR; p=L->head; for(j=0;j<=i;j++) p=p->link; q=malloc(sizeof(Node)); q->element=x; q->link=p->link; p->link=q; L->n++; returnOK; } 单链表的删除(Delate.c): statusDelete(headerList*L,inti) { intj; Node*p,*q; if(! L->n) returnERROR; if(i<0||i>L->n-1) returnERROR; q=L->head; for(j=0;jlink; p=q->link;//p指向ai q->link=p->link;//从单链表中删除p所指向的结点 free(p);//释放p所指结点的存储空间 L->n--; returnOK; } 单链表的输出(Output.c): statusOutput(headerListL) { Node*p; if(! L.n)//判断顺序表是否为空 returnERROR; p=L.head->link; while(p) { printf("%d",p->element); p=p->link; } returnOK; } 单链表的析构(Destroy.c): voidDestroy(headerList*L) { Node*p; while(L->head) { p=L->head->link; free(L->head); L->head=p; } } 测试所用主函数(main.c): voidmain() { inti; intx; headerListlist; Init(&list);//对线性表初始化 for(i=0;i<9;i++) Insert(&list,i-1,i);//线性表中插入新元素 printf("thelinklistis: "); Output(list); Delete(&list,0); printf("\nthelinklistis: "); Output(list); Nizhi(&list); printf("\n逆置后: \n"); Output(list); Find(list,0,&x); //printf("\nthevalueis: "); //printf("%d",1); Destroy(&list); }调用结果: 单链表的基本操作和逆置是在一篇代码中,所以主函数中已包括逆置函数的调用,调用结果如图也包括了逆置结果。 3.单链表逆置操作 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.多项式操作 多项式的类型定义(struct.h): typedefstructPNode { intcoef; intexp; structPNode*link; }PNode; typedefstruct { structPNode*head; }polynominal; 多项式的创建(Create.c): 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; } } 多项式的输出(Output.c): voidOutput(polynominalL) { PNode*p; p=L.head->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); } 多项式的析构(Destroy.h): voidDestroy(polynominal*L) { PNode*p; while(L->head) { p=L->head->link; free(L->head); L->head=p; } } 两个多项式的加法(Add.c): 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; } } } 两个多项式的乘法(Mult.c): 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文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性 多项式 操作