华北水利水电学院一元稀疏多项式计算器实验报告2010～2011学年第一学期 09 级计算机科学与技术专业班级： 2009119 学号： 200911902 姓名：万婷婷一、实验目的设计一个医院稀疏多项式简单计算器熟练掌握线性表的基本操作在两种存储结构上的实现，其中以各种链表的操作和应用二、实验要求a)输入并建立多项式b)输出多项式，输出形式为整数序列：n，c1，e1，c2，e2……cn，en，其中n是多项式的项数，ci ，ei分别为第i项的系数和指数。

序列按指数降序排列。

c)多项式a和b相加，建立多项式a+b，输出相加的多项式。

d)多项式a和b相减，建立多项式a-b，输出相减的多项式。

用带表头结点的单链表存储多项式。

测试数据：(1) (2x+5x8-3.1x11)+(7-5x8+11x9)(2) (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)(3)（1+x+x2 +x3 +x4 +x5）+( -x3- x4)(4)(x+x2+x3)+0(5)(x+x3)-(-x-x-3)(6) (x+x2 +x3 )+0三、实验内容主要算法设计typedef struct Node{float coef;int index;struct Node *next;}LinkList;本程序涉及到多项式的建立、多项式的输出、两个多项式的相加减。

用带头结点的单链表存储多项式；程序中共定义了5个函数：void Insert(LinkList *p,LinkList *h)//把节点p插入到链表h中LinkList *Creat_L(LinkList *head,int m)//创建一个链表，项数为m void Printf(LinkList *L)LinkList *ADDlist(LinkList *head,LinkList *pb)LinkList *MinusList(LinkList *head,LinkList *pb)四、程序源代码#include<iostream.h>#include<malloc.h>#include<stdio.h>#include<stdlib.h>typedef struct Node{float coef;int index;struct Node *next;}LinkList;void Insert(LinkList *p,LinkList *h)//把节点p插入到链表h中{LinkList *q1,*q2;int flag=0;q1=h;if(p->coef==0)free(p);else{if(q1->next==NULL){q1->next=p;}else{q2=q1->next;while(flag==0){if(p->index<q2->index){if(q2->next==NULL){q2->next=p;flag=1;}else{q1=q2;q2=q2->next;}}elseif(p->index>q2->index){p->next=q2;q1->next=p;flag=1;}else{q2->coef=p->coef+q2->coef;if(q2->coef==0){q1->next=q2->next;free(q2);}flag=1;free(p);}}}}}LinkList *Creat_L(LinkList *head,int m)//创建一个链表，项数为m {int i;LinkList *q;head=(LinkList *)malloc(sizeof(LinkList));head->next=NULL;for(i=1;i<=m;i++){q=(LinkList *)malloc(sizeof(LinkList));q->next=NULL;printf("请输入第%d项的系数和指数：",i);scanf("%f,%d",&q->coef,&q->index);Insert(q,head);}return head;}void Printf(LinkList *L){LinkList *p,*q,*pa;int i=0;p=L->next;q=L->next;if(p==NULL){printf("0\n");return;}while(p){p=p->next;i++;}printf("%d,",i);while(q){printf("%g,",q->coef);printf("%d,",q->index);q=q->next;}}LinkList *ADDlist(LinkList *head,LinkList *pb) {LinkList *pc;int flag=0;while(flag==0){if(pb->next==NULL)flag=1;else{pb=pb->next;pc=(LinkList *)malloc(sizeof(LinkList));pc->coef=pb->coef;pc->index=pb->index;pc->next=NULL;Insert(pc,head);}}return head;}LinkList *MinusList(LinkList *head,LinkList *pb) {LinkList *pc;int flag=0;while(flag==0){if(pb->next==NULL)flag=1;else{pb=pb->next;pc=(LinkList *)malloc(sizeof(LinkList));pc->coef=-pb->coef;pc->index=pb->index;pc->next=NULL;Insert(pc,head);}}return head;}void main(){int i,m,n;LinkList *pa=0,*pb=0,*pc;while(1){system("cls");printf("................欢迎使用一元稀疏多项式计算器..............\n");printf(" 请输入多项式a的项数：");scanf("%d",&m);pa=Creat_L(pa,m);printf(" 请输入多项式b的项数：");scanf("%d",&n);pb=Creat_L(pb,n);printf("................欢迎使用一元稀疏多项式计算器..............\n"); printf(" 0.退出系统 \n");printf(" 1.输出多项式a \n");printf(" 2.输出多项式b \n");printf(" 3.输出多项式a+b \n");printf(" 4.输出多项式a-b \n");while(1){printf("\n 请选择操作：");scanf("%d",&i);switch(i){case 0:return;case 1:{printf(" 输出多项式a的整数序列为：");Printf(pa);break;}case 2 :{printf(" 输出多项式b的整数序列为：");Printf(pb);break;}case 3:{pc=ADDlist(pa,pb);printf(" 输出多项式a+b的整数序列为：");Printf(pc);break;}case 4:{pc=MinusList(pa,pb);printf(" 输出多项式a-b的整数序列为：");Printf(pc);break;}default:printf("\n 输入有误，请重新输入：\n");}}}}五、运行结果六、小结（不少于100字）虽然数据结构是一门公认的比较难的课程，自己学起来也觉得有些吃力，但在本次课程设计之前，我系统地把教科书复习了一遍，大大加深了对各种数据结构的理解，运用起来更加自如。

不断地翻阅各种参考书，以及在老师和同学的帮助下，基本上考虑到了所有的边界情况，反复测试各种类型的数据，强化程序的健壮性，最终顺利完成了本次课程设计。

虽然课程设计做的不够完善，但在设计的过程中受益匪浅，通过查资料等学到了很多以前不知道或不太会应用的知识，对单向链表的使用有了更深刻的了解和掌握，因为多项式的计算要求用单向链表来实现，所以在做课程设计之前通过网上找资料，查参考书及问辅导老师等对单向链表的使用比以前掌握的更加到位，并且能够灵活运用，通篇几乎用的都是单向链表，这是受益的一大重点。