线性表及多项式操作.pdf

《线性表及多项式操作.pdf》由会员分享，可在线阅读，更多相关《线性表及多项式操作.pdf（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

2、节点的单链表的初始化、查找、插入、删除、输出、撤销等操作。3.以第 2 题所示带表头节点的单链表为例， 编写程序实现单链表的逆置操作(原单链表为(a0,a1,.an-1)，逆置后为(an-1,an-2,.,a0)，要求不引入新的存储空间。).z.-4.以第 2 题所示带表头节点的单链表为存储构造， 编写程序实现将单链表排序成为有序单链表的操作。5.带表头节点一元多项式的类型定义，编写程序实现一元多项式的创立、输出、撤销以及两个一元多项式相加和相乘的操作。实验报告实验报告.z.-三、实验过程及代码等三、实验过程及代码等1. 1.顺序表的根本运算顺序表的根本运算顺序表的类型定义：typedef s

3、tructint n;int ma*Length;int *element;SeqList;顺序表的初始化：typedef int Status;Status Init(SeqList *L,int mSize)顺序表的查找Status Find(SeqList L,int i,int *)if(iL.n-1)/越界判断return ERROR;.z.L-ma*Length=mSize;L-n=0;L-element=(int*)malloc(sizeof(Status)*mSize);if(!L-element)/ 判断顺序表是否申请成功return ERROR;return OK;-*=L

4、.elementi;return OK;顺序表的插入：Status Insert(SeqList *L,int i,int *)顺序表的删除：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;int j;if(iL-n-1)return ERROR;if(L-n=L-ma*Length)return ERROR;for(j=L-n-1;ji;j-)L-elementj+1=L-elementj;L-el

5、ementi+1=*;L-n+;return OK;.z.-L-n-;return OK;顺序表的输出：Status Output(SeqList L)/输出int i;if(!L.n)return ERROR;for(i=0;in=0;用主函数进展测试：*include *include *define ERROR 0*define OK 1int main().z.L-ma*Length=0;free(L-element);-int i;SeqList list;Init(&list,10);for(i=0;ihead=(Node*)malloc(sizeof(Node);if(!L-he

6、ad)return ERROR;L-head-link=NULL;L-n=0;return OK;单链表的查找Find.c:status Find(headerList L, int i,int *).z.-Node *p;int j;if (iL.n-1) /对 i 进展越界检查return ERROR;p=L.head;for ( j=0; jlink; /从头结点开场查找 ai*=p-element; /通过* 返回 ai 的值return OK;单链表的插入Insert.c:status Insert(headerList *L,int i,int *)Node *p,*q;int j

7、;if (iL-n-1)return ERROR;p=L-head;for(j=0;jlink;q=malloc(sizeof(Node);q-element=*;q-link=p-link;p-link=q;L-n+;return OK;单链表的删除Delate.c:status Delete(headerList *L,int i).z.-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; /从单链表中

8、删除 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;.z.-单链表的析构Destroy.c:void Destroy (headerList *L)Node *p;while(L- head )p= L- head-link;free(L-head);L- h

9、ead=p;测试所用主函数(main.c)：void main()int i;int *;headerList list;Init(&list); /对线性表初始化for(i=0;ihead;q=p-link;while(q)r=q-link;q-link=p;.z.-p=q;q=r;L-head-link-link=NULL;L-head-link=p;return 0;调用结果：4. 4.单链表排序操作冒泡单链表排序操作冒泡*include*includetypedef struct nodeint element;struct node *ne*t;Node,*LinkList;Link

10、List Creat(void)/*创立链表，输入数据，完毕标志为当输入的数据为 0*/.z.-LinkList Pai*u(LinkList l)/*排序*/LinkList p,q;int temp;for(p=l;p!=NULL;p=p-ne*t)for(q=p-ne*t;q!=NULL;q=q-ne*t)if(p-elementq-element)LinkList H,p,q;int n;n=0;p=q=(LinkList)malloc(sizeof(Node);printf(输入数据： 输入 0 标志着输入完成n);scanf(%d,&p-element);H=NULL;while(

11、p-element!=0)q-ne*t=NULL;return(H);n=n+1;if(n=1)H=p;elseq-ne*t=p;q=p;p=(LinkList)malloc(sizeof(Node);scanf(%d,&p-element);.z.-temp=q-element;q-element=p-element;p-element=temp;return l;int main()调用结果：return 0;LinkList L,S,K;L=Creat();printf(初始化的单链表为:n);for(S=L;S!=NULL;S=S-ne*t)printf(%d ,S-element);

12、Pai*u(L);printf(n 按递增排序后的链表为:n);for(K=L;K!=NULL;K=K-ne*t)printf(%d,K-element);.z.-5. 5.多项式操作多项式操作多项式的类型定义struct.h:typedef struct PNodeint coef;int e*p;struct PNode* link; PNode;typedef structstruct PNode *head;polynominal;多项式的创立Create.c:void Create(polynominal *p)PNode *pn,*pre,*q;.z.-p-head=(void*)

13、malloc(sizeof(PNode);p-head-e*p=-1;p-head-link=NULL;printf(请输入多项式n);for( ; ; )pn=(void*)malloc(sizeof(PNode);printf(coef:n);scanf(%d,&pn-coef);printf(e*p:n);scanf(%d,&pn-e*p);if(pn-e*phead;q=p-head-link;while(q&q-e*ppn-e*p)pn-link=q;pre-link=pn;pre=q;q=q-link;多项式的输出Output.c:void Output(polynominal L

14、)PNode *p;p=L.head-link;while(p-link!=NULL).z.-printf(%d*%d+,p-coef,p-e*p);p=p-link;printf(%d*%dn,p-coef,p-e*p);多项式的析构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 *p*,polynominal *q*)PNode *q,*q1=q*-head,*p,*

15、temp;p=p*-head-link;q=q1-link;while(p&q)while(p-e*pe*p)q1=q;q=q-link;.z.-if(p-e*p=q-e*p)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-e*p=p-e*p;temp-link=q1-link;q1-link=temp;p=p-link;.

16、z.-两个多项式的乘法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-e*p+=an-e*p;bn-coef*=an-coef;Add(b,&temp);bn=b-head;while(bn-link)bn=bn-link;bn-e*p-=an

17、-e*p;bn-coef/=an-coef;bn=b-head;return &temp;.z.-调用主函数测试：void main()Create(&listA);polynominal listA,listB,listC,listD,temp;int choose=0;printf(请选择操作：1.多项式相加2.多项式相乘 n);scanf(%d,&choose);switch(choose)case 1:Create(&listB);printf(多项式 A 为：);Output(listA);printf(多项式 B 为：);Output(listB);Add(&listA,&list

18、B);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);.z.-/Mult(&listC,&listD);Output(*Mult(&listC,&listD);Destroy(&listC);运行结果：（1）多项式加法：（2）多项式乘法：break;Destroy(&listD);.z.

19、-实验报告实验报告.z.-四、实验小结四、实验小结包括问题和解决方法、心得体会、意见与建议等一、前面写顺序表的时候没有遇到什么问题， 只是有两个地方有点小问题但很快解决了； 1(void*)malloc(sizeof(PNode)在 malloc 前面漏掉强制类型转换。 2forint i=1,in,i+类似上式，有些编译器不支持for 循环类定义变量名。二、刚开场写链表的代码时，总是搞不清一个链表的成员和关系，后来一直到完成多项式加法时才对链表有了一个较为全面的认识。三、在写多项式乘法时， 在网上找了一个乘法的算法，可是改来改去还是会出问题，在输出最终结果时输出的系数和指数是地址而不是数， 和舍友讨论了很久也没有解决，我后来在舍友的帮助下完成了多项式的乘法；但是之前的那段没有找出问题的代码还是没有找到答案， 而且目前还以注释的形式保存在源代码中。四、希望自己能够在实验和作业中有所收获， 使得自己的代码水平有一定的提升。.z.-五、指导教师评语五、指导教师评语成绩成绩批阅人批阅人日期日期.z.