线性表及多项式操作

《线性表及多项式操作》由会员分享，可在线阅读，更多相关《线性表及多项式操作（22页珍藏版）》请在装配图网上搜索。

1、实验报告一、实验目的和要求实验名称线性表及多项式的运算指导教师邹志强实验类型验证实验学时2+2实验时间2016.9.161掌握线性表的两种基本存储结构及其应用场合：顺序存储和链接存储。2掌握顺序表和链表的各种基本操作算法。3理解线性表应用于多项式的实现算法。、实验环境（实验设备）Dev-C+三、实验原理及内容内容：1参照程序2.1程序2.7,编写程序，完成顺序表的初始化、查找、插入、删除、输出、撤销等操作。2已知代表头节点的单链表的类型定义，参照程序2.8程序2.14,编写程序，完成带表头节点的单链表的初始化、查找、插入、删除、输出、撤销等操作。3以第2题所示带表头节点的单链表为例，编写程序实

2、现单链表的逆置操作(原单链表为(aO,a1,an1)，逆置后为(anM,a*2,.,aO),要求不引入新的存储.空间。)4以第2题所示带表头节点的单链表为存储结构，编写程序实现将单链表排序成为有序单链表的操作。5已知带表头节点一元多项式的类型定义，编写程序实现一元多项式的创建、输出、撤销以及两个一元多项式相加和相乘的操作。实验报告三、实验过程及代码等1.顺序表的基本运算顺序表的类型定义：typedefstructintn;intmaxLength;int*element;SeqList;顺序表的初始化：typedefintStatus;StatusInit(SeqList*L,intmSize

3、)L-maxLength=mSize;=丄-n=0;L-element=(int*)malloc(sizeof(Status)*mSize);_if(!L-element)/判断顺序表是否申请成功.returnERROR;returnOK;顺序表的查找StatusFind(SeqListL,inti,int*x)=if(iL.n-1)越界判断一-returnERROR;*x=L.elementi;returnOK;顺序表的插入：StatusInsert(SeqList*L,inti,intx)intj;if(iL-n-1)returnERROR;*if(L-n=L-maxLength)M!MV

4、IreturnERROR;_for(j=L-n-1;ji;j-)L-elementj+1=L-elementj;JJ*L-elementi+1=x;_丄-n+;returnOK;顺序表的删除：StatusDelete(SeqList*L,inti)intj;if(iL-n-1)returnERROR;if(!L-n)returnERROR;for(j=i+1;jn;j+)I-elementj-1=l-elementj;L-n-;returnOK;顺序表的输出：StatusOutput(SeqListL)输出inti;if(!L.n)returnERROR;for(i=0;ivLJ/7retur

5、nOK;顺序表的析构：voidDestroy(SeqList*L)L-n=0;L-maxLength=O;free(L-element);用主函数进行测试：#include#include#defineERROR0#defineOK1intmain()inti;SeqListlist;Init(&list,10);for(i=0;ihead=(Node*)malloc(sizeof(Node);if(!L-head)returnERROR;L-head-link=NULL;L-n=0;returnOK;单链表的查找(Find.c):statusFind(headerListL,inti,int

6、*x)Node*p;intj;if(iL.n-1)/对i进行越界检查returnERROR;p=L.head;for(j=0;jlink;/从头结点开始查找ai*x=p-element;/通过x返回ai的值returnOK;单链表的插入(Insert.c):rstatusInsert(headerList*L,inti,intx)iBiBNode*p,*q;intj;if(iL-n-1)returnERROR;p=L-head;for(j=0;jlink;q=malloc(sizeof(Node);q-element=x;q-link=p-link;p-link=q;L-n+;returnOK

7、;单链表的删除(Delate.c):statusDelete(headerList*L,inti)intj;Node*p,*q;if(!L-n)returnERROR;if(iL-n-1)returnERROR;q=L-head;for(j=0;jlink;P=q-link;/p指向aiq-link=p-link;/从单链表中删除p所指向的结点free(p);/释放p所指结点的存储空间L-n-;returnOK;单链表的输出(Output.c):statusOutput(headerListL)Node*p;if(!L.n)/判断顺序表是否为空returnERROR;p=L.head-link

8、;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;ihead;q=p-link;_while(q)r=q-link;q-link=p;p=q;q=r；L-head-link-link=NULL;L-h

9、ead-link=p;return0;调用结果：4单链表排序操作（冒泡）#include#includetypedefstructnodeintelement;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

10、=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)宀ounobug墙yp%=lu_d(lx1H1_l1nNl!.1_lH1)04刁弓IIs)nx&ds-=p%=lu_d(lxusus_l1nNuis_lus)04=lm耳oroaloulM

11、sJlsnunouroUJ-u一宀】unoci曰xcoeo-oasfcp-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-exphead;q=p-head-link;while(q&q_exppn-exp)pre=q;q=q-link;r-fr-*pn-link=q;

12、=link=pn;多项式的输出(Output.c):voidOutput(ponominalL)PNode*p;p=L.head-link;while(p-link!=NULL)Uprintf(%d*XA%d+,p-coef,p-exp);p=p-link;printf(%d*XA%din,p-coef,p-exp);多项式的析构(Destroy.h):voidDestroy(ponominal*L)PNode*p;while(L-head)p=L-head-link;free(L-head);L-head=p;两个多项式的加法(Add.c):voidAdd(ponominal*px,poly

13、nominal*qx)PNode*q,*q1=qx-head,*p,*temp;p=px-head-link;q=q1-link;while(p&q)while(p-expexp)q仁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;elseq仁q；q=q-link;p=p-link;=coef=p-coef;temp-exp=p-exp;temp-link=q1-link;q1-link=temp;p=p-link;两个多项式的乘法(Mult

14、.c):polynominal*Mult(ponominal*a,ponominal*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

15、=b-head;return&temp;调用主函数测试：voidmain()polynominallistA,listB,listC,listD,temp;intchoose=0;printf(请选择操作：1多项式相加2多项式相乘n);scanf(%d,&choose);switch(choose)case1:Create(&listA);printf(”多项式A为：);Output(listA);printf(多项式B为：);Output(listB);Add(&listA,&listB);.printf(n);printf(A与B相加得：);Output(listB);Destroy(&l

16、istA);Destroy(&listB);_-break;case2:Create(&listC);Create(&listD);printf(”多项式C为：);Output(listC);printf(多项式D为：);Mult(&listC，&listD);Output(*Mult(&listC,&listD);Destroy(&listC);Destroy(&listD);break;运行结果：K(1)多项式加法：(2)多项式乘法：实验报告四、实验小结(包括问题和解决方法、心得体会、意见与建议等)一、前面写顺序表的时候没有遇到什么问题，只是有两个地方有点小问题但很快解决了；(1)(void*)malloc(sizeof(PNode)在malloc前面漏掉强制类型转换。(2)for(inti=1,ihi5d;M*3朋j血*scfjsijwffFWorfc)1)f讪fie(q-?lintf!=ML!lL)/JmaLtecf蛮匕獣牢円忙吐)tst-Xiflfc;rco=p亍垃倨尸q*匸3于;t-exp-iP-cxp+qr-cxp;；:q=甲-di电!)J四、希望自己能够在实验和作业中有所收获，使得自己的代码水平有一定的提升。五、指导教师评语成绩批阅人日期