数据结构课程设计-一元多项式计算器实习1、一元稀疏多项式计算器一、需求分析1. 问题描述设计一个一元稀疏多项式简单计算器。

2. 基本要求一元稀疏多项式简单计算器的基本功能是：(1)输入并建立多项式。

(2)输出多项式，输出形式为整数序列：n, c1, e1, c2, e2, ········,c n, e n ，其中n是多项式的项数，c i,e i分别是第i项的系数和指数，序列按指数降序排列。

(3)多项式a和b想加，建立多项式a+b 。

(4)多项式a和b想减，建立多项式a-b 。

3. 测试数据(1)(2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7 )(2)(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x 15-1.2x9+12x-3-x)(3) (1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5)(4) (x+x3)+(-x-x3)=0(5) (x+x100)+(x100+x200)=(x+2x100+x200)(6) (x+x2+x3)+0=(x+x2+x3)(7) 互换测试数据的前后两个多项式。

4. 实现提示用带表头结点的单链表存储多项式。

二、概要设计为实现上述程序功能，应用带头结点的单链表存储多项式。

为此需要一个抽象数据类型：一元多项式。

1.抽象数据类型一元多项式定义为：ATD Ploynomial{数据对象：D={ai|ai∈Termset, i=1,2,3···，m,m≥0 Termset中的每个元素包含一个表示系数的实数和表示指数的整数}数据关系：R1={<ai-1,ai>ai-1,ai∈D,且ai-1中的指数<ai中的指数的值，i=1,2,3···n} 基本操作：Insert(p,h)初始条件：h已存在。

操作结果：插入p项。

CreateLinklist(head, m)操作结果：建立一个头指针为head、项数为m的一元多项式。

DestroyLinklist( p)初始条件：一元多项式p已存在。

操作结果：销毁一元多项式p。

PrintLinklist( P)初始条件：一元多项式p已存在。

操作结果：输出一元多项式p。

Compare(a,b)初始条件：项a,b已存在。

操作结果：比较a,b中x的指数的大小。

AddLinklist(pa,pb)初始条件：一元多项式pa,pb已存在。

操作结果：完成一元多项式pa,pb的相加运算。

SubtractionLinklist(Sa,Sb)初始条件：一元多项式Sa,Sb已存在。

操作结果：完成一元多项式Sa,Sb的相减运算。

} ATD Ploynomial三、详细设计（源代码）（使用C语言）#include<stdio.h>#include<malloc.h>#define maxlen 10#define large 999typedef struct Linklistomial{float coef;int expn;struct Linklistomial *next;}Linklistomial,*Linklist;//结点类型，指针类型void Insert(Linklist p,Linklist h){// h已存在插入p项if(p->coef==0)free(p);//系数为0的话释放结点else{Linklist q1,q2;q1=h;q2=h->next;while(q2&&p->expn<q2->expn){ //查找插入位置q1=q2;q2=q2->next;}if(q2&&p->expn==q2->expn){ //将指数相同相合并q2->coef+=p->coef;free(p);if(!q2->coef){//系数为0的话释放结点q1->next=q2->next;free(q2);}}else { //指数为新时将结点插入p->next=q2;q1->next=p; }}}Linklist CreateLinklist(Linklist head,int m){//建立一个头指针为head、项数为m的一元多项式int i;Linklist p;p=head=(Linklist)malloc(sizeof(struct Linklistomial));head->next=NULL;for(i=0;i<m;i++){p=(Linklist)malloc(sizeof(struct Linklistomial));//建立新结点以接收数据printf("请输入第%d项的系数与指数:",i+1);scanf("%f %d",&p->coef,&p->expn);Insert(p,head); //调用Insert函数插入结点}return head;}void DestroyLinklist(Linklist p){//销毁多项式pLinklist D1,D2;D1=p;while(D1){D2=D1->next;free(D1);D1=D2;}}void PrintLinklist(Linklist P) {//输出一元多项式pLinklist q=P->next;int flag=1; //项数计数器if(!q){ //若多项式为空，输出0putchar('0');printf("\n");return;}while(q){if(q->coef>0&&flag!=1) putchar('+'); //系数大于0且不是第一项if(q->coef!=1&&q->coef!=-1){ //系数非1或-1的普通情况printf("%g",q->coef);if(q->expn==1) putchar('X');else if(q->expn) printf("X^%d",q->expn);}else{if(q->coef==1){if(!q->expn)putchar('1');else if(q->expn==1)putchar('X');elseprintf("X^%d",q->expn);}if(q->coef==-1){if(!q->expn)printf("-1");else if(q->expn==1)printf("-X");elseprintf("-X^%d",q->expn);}}q=q->next;flag++;}printf("\n");}int Compare(Linklist a,Linklist b) {//比较a,b中x的指数的大小if(a&&b){if(!b||a->expn>b->expn)return 1;else if(!a||a->expn<b->expn)return -1;elsereturn 0;}else if(!a&&b)//a多项式已空，但b多项式非空return -1;else//b多项式已空，但a多项式非空return 1;}Linklist AddLinklist(Linklist pa,Linklist pb) {//求解并建立多项式a+b，返回其头指针Linklist qa=pa->next;Linklist qb=pb->next;Linklist headc,hc,qc;hc=(Linklist)malloc(sizeof(struct Linklistomial));//建立头结点hc->next=NULL;headc=hc;while(qa||qb){qc=(Linklist)malloc(sizeof(struct Linklistomial));switch(Compare(qa,qb)){case 1:{qc->coef=qa->coef;qc->expn=qa->expn;qa=qa->next;break;}case 0:{qc->coef=qa->coef+qb->coef;qc->expn=qa->expn;qa=qa->next;qb=qb->next;break;}case -1:{qc->coef=qb->coef;qc->expn=qb->expn;qb=qb->next;break;}}if(qc->coef!=0){qc->next=hc->next;hc->next=qc;hc=qc;}elsefree(qc);//当相加系数为0时，释放该结点}return headc;}Linklist SubtractionLinklist(Linklist Sa,Linklist Sb){//求解并建立多项式a-b，返回其头指针Linklist Cb=Sb->next;while(Cb){Cb->coef=(-1)*Cb->coef;Cb=Cb->next;}return AddLinklist(Sa,Sb);}int main(){int m,n,a=1;char flag;Linklist pa=0,pb=0,pc;printf(" 欢迎使用一元多项式加法器\n\n");//输出菜单printf("***************************************** **************\n");printf(" * 一元多项式简单运算器*\n");printf(" * *\n");printf(" * A: 输入多项式a B: 输入多项式b *\n");printf(" * *\n");printf(" * C: 输出多项式a D: 输出多项式b *\n");printf(" * *\n");printf(" * E: 输出a+b F: 输出a-b *\n");printf(" * *\n");printf(" * G: 使用完毕！*\n");printf("***************************************** **************\n");while(a){printf("\n 请选择操作：");scanf(" %c",&flag);//空格符号一定要注意switch(flag){case'A':case'a':{printf("下面进行多项式a的输入：\n");printf("请输入a的项数:");scanf("%d",&m);pa=CreateLinklist(pa,m);//建立多项式abreak;}case'B':case'b':{printf("下面进行多项式b的输入：\n");printf("请输入b的项数:");scanf("%d",&n);pb=CreateLinklist(pb,n);//建立多项式bbreak;}case'C':case'c':{printf("\n 多项式a=");PrintLinklist(pa);break;}case'D':case'd':{printf("\n 多项式b=");PrintLinklist(pb);break;}case'E':case'e':{pc=AddLinklist(pa,pb);printf("\na+b=");PrintLinklist(pc);break;}case'F':case'f':{pc=SubtractionLinklist(pa,pb);printf("\na-b=");PrintLinklist(pc);break;}case'G':case'g':{DestroyLinklist(pa);DestroyLinklist(pb);a=0;printf("\n 欢迎下次使用！\n");break;}default:printf("\n 您的选择错误，请重新选择!\n");}}return 0;}四、调试分析编译环境为CodeBlocks。