搜索
实验三、链表及其多项式相加一、实验目的1.了解线性表的链式存储结构，熟练掌握链表。2.了解作为链表的多项式存贮方式。3.熟悉掌握多项式加法的算法。二、实验原理顺序存储的线性表有一些弱点，其一，插入与删除元素需要大量移动元素；其二，预先分配存储空间时必须按最大的空间来分配。其三，表长难以扩充。所以，必须引入链式存储结构。链式存储结构的特点是用一组任意的存储单元存储线性链表的数据元素，与顺序表的区别在于链式存储的存储单元可以是连续的，也可以是不连续的。为了实现这种结构，链表采取由两部分信息组成数据元素ai的存储映像，称为结点。结点包括两个域，其中存储数据信息的域称为数据域，存储直接后继信息的称为指针域。指针域中存储的信息叫做指针或链。这样，n个结点链接成一个链表，即为线性表（a1,a2,a3,···,an）。1.符号多项式的操作，已经成为表处理的典型用例，在数学上，一个一元多项式pn(x)可以按升幂写成：pn(x)=p0+p1·x+p2·（x的2次幂）+···+pn·（x的n次幂）。它由n+1个系数唯一确定。因此，在计算机里，它可用一个线性表P来表示：P=(p0,p1,p2,···,pn),显然，此种表示仅适于顺序存储结构，在通常的应用中，多项式的次数变化很高且很大，将造成内存的很大浪费。2.实现单链表就地逆置。三、实验要求1．参照书上的原理说明分析程序，深入理解链表的物理存储模式和逻辑模式。2．看懂书上算法，参考实验程序编出程序上机调试。3．参考书上的程序，编写建立链表存储多项式，并实现两多项式相加。四、代码实现：1.#includestdio.h#includestdlib.htypedefstructPolynode{intcoef;intexp;Polynode*next;}Polynode,*Polylist;Polylistpolycreate(){Polynode*head,*rear,*s;intc,e;head=(Polynode*)malloc(sizeof(Polynode));rear=head;scanf(%d,%d,&c,&e);while(c!=0){s=(Polynode*)malloc(sizeof(Polynode));s-coef=c;s-exp=e;rear-next=s;rear=s;scanf(%d,%d,&c,&e);}rear-next=NULL;return(head);}voidpolyadd(Polylistpolya,Polylistpolyb){Polynode*p,*q,*tail,*temp;intsum;p=polya-next;q=polyb-next;tail=polya;while(p!=NULL&&q!=NULL){if(p-expq-exp){tail-next=p;tail=p;p=p-next;}elseif(p-exp==q-exp){sum=p-coef+q-coef;if(sum!=0){p-coef=sum;tail-next=p;tail=p;p=p-next;temp=q;q=q-next;free(temp);}else{temp=p;p=p-next;free(temp);temp=q;q=q-next;free(temp);}}else{tail-next=q;tail=q;q=q-next;}}if(p==NULL)tail-next=p;elsetail-next=q;}voidmain(){Polynode*p;printf(请输入第一个多项式,次数从低到高:\n);PolylistA=polycreate();printf(\n多项式创建完成!\n);printf(\n请输入第二个多项式,次数从低到高:\n);PolylistB=polycreate();printf(\n多项式创建完成!\n\n);polyadd(A,B);p=A-next;while(p!=NULL){printf([%d%d],p-coef,p-exp);p=p-next;}printf(\n\n);}2.#includestdio.h#includestdlib.htypedefstructNode{chardata;structNode*next;}Node,*Linklist;voidInitlist(Linklist*L){*L=(Linklist)malloc(sizeof(Node));(*L)-next=NULL;}voidCreateFromHead(LinklistL){Node*s;charc;intflag=1;while(flag){c=getchar();if(c!='$'){s=(Node*)malloc(sizeof(Node));s-data=c;s-next=L-next;L-next=s;}elseflag=0;}}voidReverselist(LinklistL){Linklistp,q;p=L-next;L-next=NULL;while(p!=NULL){q=p-next;p-next=L-next;L-next=p;p=q;}}voidmain(){Linklistp;LinklistL;Initlist(&L);printf(Pleaseinputdatas:\n);CreateFromHead(L);p=L;while(p-next!=NULL){p=p-next;printf(%c,p-data);}Reverselist(L);printf(\n\n);}五：结果验证：1.2