线性表及多项式操作.docx

实 验 报 告实验名称线性表及多项式的运算指导教师邹志强实验类型验证实验学时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.顺序表的基本运算顺序表的类型定义：typedef structint n;int maxLength;int *element;SeqList;顺序表的初始化：typedef int Status;Status Init(SeqList *L,int mSize)L-maxLength=mSize;L-n=0;L-element=(int*)malloc(sizeof(Status)*mSize);if(!L-element) / 判断顺序表是否申请成功return ERROR;return OK;顺序表的查找Status Find(SeqList L,int i,int *x)if(iL.n-1) /越界判断return ERROR;*x=L.elementi;return OK;顺序表的插入：Status Insert(SeqList *L,int i,int x)int j;if(iL-n-1)return ERROR;if(L-n=L-maxLength)return ERROR;for(j=L-n-1;ji;j-)L-elementj+1=L-elementj;L-elementi+1=x;L-n+;return OK;顺序表的删除：Status Delete(SeqList *L,int i)int j;if (iL-n-1)return ERROR;if(!L-n)return ERROR;for(j=i+1;jn;j+)L-elementj-1=L-elementj;L-n-;return OK;顺序表的输出：Status Output(SeqList L)/输出 int i; if(!L.n) return ERROR; for(i=0;in=0;L-maxLength=0;free(L-element);用主函数进行测试：#include #include #define ERROR 0#define OK 1int main()int i;SeqList list;Init(&list,10);for(i=0;ihead=(Node*)malloc(sizeof(Node);if(!L-head)return ERROR;L-head-link=NULL;L-n=0;return OK;单链表的查找（Find.c）:status Find(headerList L, int i,int *x)Node *p;int j;if (iL.n-1) /对i 进行越界检查return ERROR;p=L.head;for ( j=0; jlink; /从头结点开始查找ai*x=p-element; /通过x 返回ai 的值return OK;单链表的插入（Insert.c）:status Insert(headerList *L,int i,int x)Node *p,*q;int j;if (iL-n-1)return ERROR;p=L-head;for(j=0;jlink;q=malloc(sizeof(Node);q-element=x;q-link=p-link;p-link=q; L-n+;return OK;单链表的删除（Delate.c）:status Delete(headerList *L,int i)int j;Node *p,*q;if (!L-n)return ERROR;if (iL-n-1)return ERROR;q=L-head;for (j=0; jlink;p=q-link; /p 指向aiq-link=p-link; /从单链表中删除p 所指向的结点free(p); /释放p 所指结点的存储空间L-n-;return OK;单链表的输出（Output.c）:status Output(headerList L)Node *p;if (!L.n) /判断顺序表是否为空return ERROR;p=L.head-link;while(p)printf(%d ,p-element);p=p-link;return OK;单链表的析构（Destroy.c）:void Destroy (headerList *L) Node *p;while(L- head ) p= L- head-link;free(L-head);L- head=p;测试所用主函数(main.c)： void main()int i;int x;headerList list;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-head-link=p;return 0;调用结果：4. 单链表排序操作（冒泡）#include#includetypedef struct nodeint element;struct node *next;Node,*LinkList;LinkList Creat(void) /*创建链表，输入数据，结束标志为当输入的数据为0*/LinkList H,p,q;int n;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);LinkList Paixu(LinkList l) /*排序*/LinkList p,q;int temp;for(p=l;p!=NULL;p=p-next)for(q=p-next;q!=NULL;q=q-next)if(p-elementq-element)temp=q-element;q-element=p-element;p-element=temp;return l;int main()LinkList L,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);return 0;调用结果：5. 多项式操作多项式的类型定义（struct.h）:typedef struct PNodeint coef;int exp;struct PNode* link; PNode;typedef structstruct PNode *head;polynominal;多项式的创建（Create.c）:void Create(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-exphead;q=p-head-link;while(q&q-exppn-exp)pre=q;q=q-link;pn-link=q;pre-link=pn;多项式的输出（Output.c）:void Output(polynominal L)PNode *p;p=L.head-link; while(p-link!=NULL) printf(%d*X%d+,p-coef,p-exp); p=p-link; printf(%d*X%dn,p-coef,p-exp); 多项式的析构（Destroy.h）:void Destroy (polynominal *L) PNode *p; while(L- head ) p= L- head-link; free(L-head); L- head=p; 两个多项式的加法（Add.c）:void Add(polynominal *px,polynominal *qx)PNode *q,*q1=qx-head,*p,*temp;p=px-head-link;q=q1-link;while(p&q)while(p-expexp)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;elseq1=q;q=q-link;p=p-link;elsetemp=(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; polynominal temp; printf(初始化temp，输入0 0 0 -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;调用主函数测试：void main()polynominal listA,listB,listC,listD,temp;int choose=0;printf(请选择操作： 1.多项式相加 2.多项式相乘 n);scanf(%d,&choose); switch(choose) case 1: 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;case 2: 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（int i=