线性表及多项式操作

范文范例精心整理word完美格式实验报告实验名称线性表及多项式的运算指导教师邹志强实验类型验证实验学时2+2实验时间2016.9.16一、实验目的和要求1.掌握线性表的两种基本存储结构及其应用场合：顺序存储和链接存储。2.掌握顺序表和链表的各种基本操作算法。3.理解线性表应用于多项式的实现算法。二、实验环境(实验设备)Dev-C++范文范例精心整理word完美格式三、实验原理及内容内容：1.参照程序2.1~程序2.7，编写程序，完成顺序表的初始化、查找、插入、删除、输出、撤销等操作。2.已知代表头节点的单链表的类型定义，参照程序2.8~程序2.14，编写程序，完成带表头节点的单链表的初始化、查找、插入、删除、输出、撤销等操作。3.以第2题所示带表头节点的单链表为例，编写程序实现单链表的逆置操作(原单链表为(a0,a1,...an-1)，逆置后为(an-1,an-2,...,a0)，要求不引入新的存储空间。)4.以第2题所示带表头节点的单链表为存储结构，编写程序实现将单链表排序成为有序单链表的操作。5.已知带表头节点一元多项式的类型定义，编写程序实现一元多项式的创建、输出、撤销以及两个一元多项式相加和相乘的操作。实验报告范文范例精心整理word完美格式三、实验过程及代码等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(i0||iL.n-1)//越界判断returnERROR;范文范例精心整理word完美格式*x=L.element[i];returnOK;}顺序表的插入：StatusInsert(SeqList*L,inti,intx){intj;if(i-1||iL-n-1)returnERROR;if(L-n==L-maxLength)returnERROR;for(j=L-n-1;ji;j--)L-element[j+1]=L-element[j];L-element[i+1]=x;L-n++;returnOK;}顺序表的删除：StatusDelete(SeqList*L,inti){intj;if(i0||iL-n-1)returnERROR;if(!L-n)returnERROR;for(j=i+1;jL-n;j++)L-element[j-1]=L-element[j];范文范例精心整理word完美格式L-n--;returnOK;}顺序表的输出：StatusOutput(SeqListL)//输出{inti;if(!L.n)returnERROR;for(i=0;iL.n;i++)printf(%d,L.element[i]);returnOK;}顺序表的析构：voidDestroy(SeqList*L){L-n=0;L-maxLength=0;free(L-element);}用主函数进行测试：#includestdio.h#includestdlib.h#defineERROR0#defineOK1intmain(){范文范例精心整理word完美格式inti;SeqListlist;Init(&list,10);for(i=0;i10;i++)Insert(&list,i-1,i);Output(list);printf(\n);Delete(&list,0);Output(list);Destroy(&list);}调用结果：范文范例精心整理word完美格式实验报告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)范文范例精心整理word完美格式{Node*p;intj;if(i0||iL.n-1)//对i进行越界检查returnERROR;p=L.head;for(j=0;ji;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||iL-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）:范文范例精心整理word完美格式statusDelete(headerList*L,inti){intj;Node*p,*q;if(!L-n)returnERROR;if(i0||iL-n-1)returnERROR;q=L-head;for(j=0;ji;j++)q=q-link;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;while(p){printf(%d,p-element);p=p-link;}范文范例精心整理word完美格式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;i9;i++)Insert(&list,i-1,i);//线性表中插入新元素printf(thelinklistis:);Output(list);Delete(&list,0);printf(\nthelinklistis:);Output(list);Nizhi(&list);printf(\n逆置后：\n);范文范例精心整理word完美格式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;范文范例精心整理word完美格式q-link=p;p=q;q=r;}L-head-link-link=NULL;L-head-link=p;return0;}调用结果：4.单链表排序操作（冒泡）#includestdio.h#includestdlib.htypedefstructnode{intelement;structnode*next;}Node,*LinkList;范文范例精心整理word完美格式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;elseq-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){范文范例精心整理word完美格式if(p-elementq-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;}调用结果：范文范例精心整理word完美格式5.多项式操作多项式的类型定义（struct.h）:typedefstructPNode{intcoef;intexp;structPNode*link;}PNode;typedefstruct{structPNode*head;}polynominal;多项式的创建（Create.c）:voidCreate(polynominal*p){PNode*pn,*pre,*q;范文范例精心整理word完美格式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-exp0)break;pre=p-head;q=p-head-link;while(q&&q-exppn-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){范文范例精心整理wor