线性表及多项式操作.doc

精品文档，仅供学习与交流，如有侵权请联系网站删除【精品文档】第 24 页实 验 报 告实验名称线性表及多项式的运算指导教师邹志强实验类型验证实验学时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(i<0|i>L.n-1) /越界判断return ERROR;*x=L.elementi;return OK;顺序表的插入：Status Insert(SeqList *L,int i,int x)int j;if(i<-1|i>L->n-1)return ERROR;if(L->n=L->maxLength)return ERROR;for(j=L->n-1;j>i;j-)L->elementj+1=L->elementj;L->elementi+1=x;L->n+;return OK;顺序表的删除：Status Delete(SeqList *L,int i)int j;if (i<0|i>L->n-1)return ERROR;if(!L->n)return ERROR;for(j=i+1;j<L->n;j+)L->elementj-1=L->elementj;L->n-;return OK;顺序表的输出：Status Output(SeqList L)/输出 int i; if(!L.n) return ERROR; for(i=0;i<L.n;i+) printf("%d ",L.elementi); return OK;顺序表的析构：void Destroy(SeqList *L) L->n=0;L->maxLength=0;free(L->element);用主函数进行测试：#include <stdio.h>#include <stdlib.h>#define ERROR 0#define OK 1int main()int i;SeqList list;Init(&list,10);for(i=0;i<10;i+)Insert(&list,i-1,i);Output(list);printf("n");Delete(&list,0);Output(list);Destroy(&list);调用结果：实 验 报 告2. 带表头节点单链表的基本运算单链表的类型定义（struct.h）:typedef struct Node int element; /结点的数据域 struct Node *link; /结点的指针域 Node; typedef struct struct Node * head; int n; headerList; typedef int status;单链表的初始化（Init.c）:status Init(headerList *L)L->head=(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 (i<0 | i>L.n-1) /对i 进行越界检查return ERROR;p=L.head;for ( j=0; j<i; j+) p=p->link; /从头结点开始查找ai*x=p->element; /通过x 返回ai 的值return OK;单链表的插入（Insert.c）:status Insert(headerList *L,int i,int x)Node *p,*q;int j;if (i<-1 | i>L->n-1)return ERROR;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+;return OK;单链表的删除（Delate.c）:status Delete(headerList *L,int i)int j;Node *p,*q;if (!L->n)return ERROR;if (i<0 | i>L->n-1)return ERROR;q=L->head;for (j=0; j<i; j+) q=q->link;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;i<9;i+)Insert(&list,i-1,i); /线性表中插入新元素printf("the linklist is:");Output(list);Delete(&list,0);printf("nthe linklist is:");Output(list);Nizhi(&list);printf("n逆置后：n");Output(list);Find(list,0,&x);/printf("nthe value is:");/printf("%d ",1);Destroy (&list);调用结果:单链表的基本操作和逆置是在一篇代码中，所以主函数中已包括逆置函数的调用，调用结果如图也包括了逆置结果。3.单链表逆置操作status Nizhi(headerList *L)Node *p,*q,*r;p=L->head;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<stdio.h>#include<stdlib.h>typedef 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->element>q->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->exp<0) break;pre=p->head;q=p->head->link;while(q&&q->exp>pn->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->exp<q->exp)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=1,i<n,i+）类似上式，有些编译器不支持for循环类定义变量名。二、刚开始写链表的代码时，总是搞不清一个链表内的成员和关系，后来一直到完成多项式加法时才对链表有了一个较为全面的认识。三、在写多项式乘法时，在网上找了一个乘法的算法，可是改来改去还是会出问题，在输出最终结果时输出的系数和指数是地址而不是数，和舍友讨论了很久也没有解决，我后来在舍友的帮助下完成了多项式的乘法；但是之前的那段没有找出问题的代码还是没有找到答案，而且目前还以注释的形式保留在源代码中。四、希望自己能够在实验和作业中有所收获，使得自己的代码水平有一定的提升。五、指导教师评语 成 绩批阅人日 期欢迎您的光临，Word文档下载后可修改编辑.双击可删除页眉页脚.谢谢！你的意见是我进步的动力，希望您提出您宝贵的意见！让我们共同学习共同进步！学无止境.更上一层楼。