数据结构(C语言)一元稀疏多项式计算器.doc

实验报告一

题目：编制一个一元稀疏多项式计算器
班级：1302018 姓名：王雪 学号：13020188030 完成日期：2014.4.5
一、需求分析
1、一元稀疏多项式简单计算器的功能是：
1.1 输入并建立多项式；
1.2 输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,………cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；
1.3多项式a和b相加，建立多项式a+b；
1.4 多项式a和b相减，建立多项式a-b。
2、设计思路:
2.1 定义线性表的动态分配顺序存储结构；
2.2 建立多项式存储结构，定义指针*next
2.3利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构造的一元多项式
2.4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。多项式显示的格式为：c1x^e1+c2x^e2+…+cnx^en
3、设计思路分析
要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为
序数coef
指数expn
指针域next
运用尾插法建立两条单链表，以单链表polyn p和polyn h分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题（将单链表polyn p中的结点插入到单链表polyn h中），因此“和多项式”中的结点无须另生成。
为了实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则：
① 若p->expn<q->expn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。
② 若p->expn=q->expn，则将两个结点中的系数相加，当和不为0时修改结点p的系数。
③ 若p->expn>q->expn，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。

二、概要设计
为实现上述程序的功能，应以带头结点的单链表表示多项式。为此，需要一个抽象数据类型：单链表。
2.1单链表的抽象数据类型定义
ADT LinkList{
数据对象：D={ai|ai∈TermSet,i=1,2,…,m,m≥0
TermSet中的每个元素包含一个表示系数的实数和表示指数的整数}
数据关系：R1={<ai-1,ai>ai-1,ai∈D且ai-1中的指数值<ai中的指数值,i=2,…,n}
基本操作：
CreatLinkList(&p,m)
操作结果：输入m项的系数和指数，建立一元多项式p。
DestoryLinkList(&p)
初始条件：一元多项式p已存在。
操作结果：销毁一元多项式p.
PrintLinkList(p)
初始条件：一元多项式p已存在。
操作结果：打印输出一元多项式p.
AddLinkList（&pa,&pb）
初始条件：一元多项式pa和pb已存在。
操作结果：完成多项式的相加运算，即：pa=pa+pb,并销毁一元多项式pb.
SubtractLinkList(&pa,&pb)
初始条件：一元多项式pa和pb已存在。
操作结果：完成多项式的想减运算，即：pa=pa-pb,并销毁一元多项式pb.
}ADT LinkList
2.2本程序包括个模块：
1）主程序模块：
Void main（）{
初始化；
输出菜单；
While（1）{
接受命令；
处理命令；
}（循环一直为真直至接受退出命令）；
2）单链表单元模块——实现单链表的抽象数据类型；
3）结点结构单元模块——定义单链表的结点结构。
三、详细设计
3.1元素类型、结点类型和指针类型
typedef int Status;
typedef int ElemType;
typedef struct LNode{
    float     coef;                      //系数
    ElemType  expn;                   //指数
    struct    LNode *next;           
}LNode,*LinkList;
Status MakeNode(LinkList &p,LinkList head)
{ //分配由p指向下一个多项式的头结点head、后继为空的结点，并返回TRUE，
//若分配失败，则返回FALSE
p= (LinkList)malloc(sizeof(struct LNode));
if(!p)return false;
p=head;p->next=null;return ture;
void FreeNode(LinkList &p)
{ //释放p所指结点
free(q1);
        q1=q2;
        q2=q2->next;
}
3.2单链表的基本操作设置如下：
void Insert(LinkList p,LinkList h)；
//将节点p插入到多项式链表h
LinkList CreateLinkList(LinkList head,int m);
//建立一个头指针为head、项数为m的一元多项式,并返回该多项式的头结点；
//若分配空间失败，则返回FALSE
void DestroyLinkList(LinkList p);
 //销毁多项式p
void PrintLinkList(LinkList P);
//输出构造的一元多项式P
Status compare(LinkList a,LinkList b)
//节点进行比较: a的指数 >b的指数   return 1; a的指数==b的指数   return 0;
a的指数<b的指数    return -1.
LinkList AddLinkList(LinkList pa,LinkList pb)
//求解并建立多项式a+b，返回其头指针
LinkList SubtractLinkList(LinkList pa,LinkList pb)
//求解并建立多项式a-b，返回其头指针
其中部分操作的伪码如下：
LinkList CreateLinkList(LinkList head,int m)
{
  p=head=(LinkList)malloc(sizeof(struct LNode));
    head->next=NULL;
    for(i=0;i<m;i++)
 {
        p=(LinkList)malloc(sizeof(struct LNode));   //建立新结点以接收数据
        printf("请输入第%d项的系数与指数:",i+1);
        scanf("%f %d",&p->coef,&p->expn);
        Insert(p,head);                             //调用Insert函数插入结点
 }
    return head;
}// CreateLinkList
Status compare(LinkList a,LinkList b){
    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) return -1;//a多项式已空，但b多项式非空
    else return 1;//b多项式已空，但a多项式非空
}// compare
float ValueLinkList(LinkList head,int x){  //输入x值，计算并返回多项式的值
       for(p=head->next;p;p=p->next){
        t=1; for(i=p->expn;i!=0;)       // i 为指数的系数 pow(x,i)
  { if(i<0){t/=x;i++;}       //指数小于0，进行除法
            else{t*=x;i--;}  } //指数大于0，进行乘法        sum+=p->coef*t;
 } return sum;}// ValueLinkList
LinkList MultiplyLinkList(LinkList pa,LinkList pb){//求解并建立多项式a*b，返回其头指针
     LinkList qa=pa->next;
    LinkList qb=pb->next;
    hf=(LinkList)malloc(sizeof(struct LNode));//建立头结点
    hf->next=NULL;
    for(;qa;qa=qa->next) { for(qb=pb->next;qb;qb=qb->next)
  {pf=(LinkList)malloc(sizeof(struct LNode));
            pf->coef=qa->coef*qb->coef;
            pf->expn=qa->expn+qb->expn;
            Insert(pf,hf); }//调用Insert函数以合并指数相同的项
  }return hf;}// MultiplyLinkList
3.3主函数和其他函数的伪码算法
void main(){//主函数
Initiation();  //多项式初始化
     PrintCommand();//输出菜单
     while(1){   //循环一直为真 知道选择j||J即退出命令时，程序退出
        printf("\n请选择操作：");
        scanf("%c",&flag);        Interpter(flag);  //具体的操作命令
 }}  //main
void Initiation()
{
     printf("请输入a的项数:");
    scanf("%d",&m);
    pa=CreateLinkList(pa,m);//建立多项式a
    printf("请输入b的项数:");
    scanf("%d",&n);
    pb=CreateLinkList(pb,n);//建立多项式b
 printf("多项式已创建\n");
}// Initiation
void PrintCommand(){  //输出菜单
显示键入命令的提示信息；
Printf（’A’,’B’,’C’,’D’,’E’）;
}// PrintCommand
 void Interpter(char flag) {   //具体的操作命令
 switch(flag)
  { case 'A': case 'a':{ PrintLinkList(pa); break;}
case 'B':case 'b':{ PrintLinkList(pb); break;}
case'C': case'c':  { AddLinkList(pa,pb); PrintLinkList(pc); break;}
case'D': case'd': { SubtractLinkList(pa,pb));PrintLinkList(pc); break;}
case'E': case'e': { DestroyLinkList(pa); DestroyLinkList(pb);exit(0) ; }
default:printf("\n       您的选择错误，请重新选择!\n");}
} // Interpter
函数说明：
Initiation(); //多项式初始化
PrintCommand(); //输出菜单
Interpter() ; //具体的操作命令
PrintLinkList() ; //打印多项式(降序输出)
AddLinkList() ; //两个多项式相加
SubtractLinkList(); //两个多项式相减
DestroyLinkList(); //销毁多项式
compare() ; //两个节点比较
CreateLinkList(); //创建多项式
Insert() ; //将节点插入已知多项式中

四、源程序
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct LNode{
float coef; //系数
ElemType expn; //指数
struct LNode *next;
}LNode,*LinkList;
/*全局节点 初始化多项式节点为空*/
static LinkList pa=NULL;
static LinkList pb=NULL;
static LinkList pc=NULL;
/*将节点p插入到多项式链表h*/
void Insert(LinkList p,LinkList h){
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 LNode));
head->next=NULL;
for(i=0;i<m;i++)
{
p=(LinkList)malloc(sizeof(struct LNode)); //建立新结点以接收数据
printf("请输入第%d项的系数与指数:",i+1);
scanf("%f %d",&p->coef,&p->expn);
Insert(p,head); //调用Insert函数插入结点
}
return head;
}
void DestroyLinkList(LinkList p){
//销毁多项式p
LinkList q1,q2;
q1=p->next;
q2=q1->next;
while(q1->next)
{free(q1);
q1=q2;
q2=q2->next;
}
}
//输出构造的一元多项式P
void PrintLinkList(LinkList 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");
}
// 节点进行比较
// a的指数 >b的指数 return 1
// a的指数==b的指数 return 0
// a的指数<b的指数 return -1
Status compare(LinkList a,LinkList b){
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) return -1;//a多项式已空，但b多项式非空
else return 1;//b多项式已空，但a多项式非空
}
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 LNode));//建立头结点
hc->next=NULL;
headc=hc;
while(qa||qb){
qc=(LinkList)malloc(sizeof(struct LNode));
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 SubtractLinkList(LinkList pa,LinkList pb){//求解并建立多项式a-b，返回其头指针
LinkList h=pb;
LinkList p=pb->next;
LinkList pd;
while(p) { //将pb的系数取反
p->coef*=-1;
p=p->next;
}
pd=AddLinkList(pa,h);
for(p=h->next;p;p=p->next) //恢复pb的系数
p->coef*=-1;
return pd;
}

//多项式初始化
void Initiation()
{
int m, n ;
printf("请输入a的项数:");
scanf("%d",&m);
pa=CreateLinkList(pa,m);//建立多项式a
printf("请输入b的项数:");
scanf("%d",&n);
pb=CreateLinkList(pb,n);//建立多项式b
printf("多项式已创建\n");
}
//输出菜单
void PrintCommand()
{
printf(" A:输出多项式a B:输出多项式b \n");
printf(" C:输出a+b D:输出a-b \n");
printf("E:退出程序 \n");
}
void Interpter(char flag)
{
int x ;
scanf("%c",&flag);
switch(flag)
{
case 'A':
case 'a':{ printf("\n多项式a=");
PrintLinkList(pa);
break;}

case 'B':
case 'b':{printf("\n多项式b=");
PrintLinkList(pb);
break;
}
case'C':
case'c': {pc=AddLinkList(pa,pb);
printf("\n a+b=");
PrintLinkList(pc);
break;
}

case'D':
case'd':{pc=SubtractLinkList(pa,pb);
printf("\n a-b=");
PrintLinkList(pc);
break;
}

case'E':
case'e':{ printf("\n 感谢使用此程序！\n");
DestroyLinkList(pa);
DestroyLinkList(pb);
exit(0) ;} //强制程序退出
default:printf("\n 您的选择错误，请重新选择!\n");
}
}

void main()
{
char flag;
Initiation(); //多项式初始化
PrintCommand();//输出菜单
while(1){ //循环一直为真 知道选择j||J即退出命令时，程序退出
printf("\n请选择操作：");
scanf("%c",&flag);//空格符号一定要注意
Interpter(flag); //具体的操作命令
}
}
五、运行结果