数据结构课程设计-一元多项式计算器.doc

(完整word版)数据结构课程设计-一元多项式计算器
实习1、一元稀疏多项式计算器

一、 需求分析
1. 问题描述
设计一个一元稀疏多项式简单计算器。
2. 基本要求
一元稀疏多项式简单计算器的基本功能是：
(1)输入并建立多项式。
(2)输出多项式，输出形式为整数序列：n, c1, e1, c2, e2, ········,cn, en ，其中n是多项式的项数，ci,ei分别是第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.8x15-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 999

typedef 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)
{//销毁多项式p
Linklist D1,D2;
D1=p;
while(D1)
{
D2=D1->next;
free(D1);
D1=D2;
}
}

void PrintLinklist(Linklist P)
{//输出一元多项式p
Linklist q=P->next;
int flag=1; //项数计数器
if(!q)
{ //若多项式为空，输出0
putchar('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');
else
printf("X^%d",q->expn);
}
if(q->coef==-1)
{
if(!q->expn)
printf("-1");
else if(q->expn==1)
printf("-X");
else
printf("-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;
else
return 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;
}
else
free(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);//建立多项式a
break;
}
case'B':
case'b':
{
printf("下面进行多项式b的输入：\n");
printf("请输入b的项数:");
scanf("%d",&n);
pb=CreateLinklist(pb,n);//建立多项式b
break;
}
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("\n a+b=");
PrintLinklist(pc);
break;
}
case'F':
case'f':
{
pc=SubtractionLinklist(pa,pb);
printf("\n a-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。