问题描述
编程实现一元多项式的加法计算。
基本要求
能用链表实现一元多项式的加法计算，并能打印出计算结果。
所需知识
（1）基本编程方法和程序设计知识。
（2）链表的理解和运算与运用。
所用算法
遍历算法和递归算法。
操作平台
Visual C++
#include<stdio.h>
#include<graphics.h>
#define MAX 100
typedef struct polynode
{ float coef;
int expn;
struct polynode *next;
}node;
node * create(void)
{
node *h,*r,*s;
float c;
int e;
h=(node *)malloc(sizeof(node));
r=h;
printf("coef:");
scanf("%f",&c);
printf("expn: ");
scanf("%d",&e);
while(c!=0.0)
{
s=(node *)malloc(sizeof(node));
s->coef=c;
s->expn=e;
r->next=s;
r=s;
printf("coef:");
scanf("%f",&c);
printf("expn: ");
scanf("%d",&e);
}
r->next=NULL;
return(h);
}
void polyadd(node *pa, node *pb)
{
node *p,*q,*pre,*temp;
int sum;
p=pa->next;
q=pb->next;
pre=pa;
while(p!=NULL&&q!=NULL)
{
if(p->expn<q->expn)
{
pre->next=p;
pre=pre->next;
p=p->next;
}
if(p->expn==q->expn)
{
sum=p->coef+q->coef;
if(sum!=0)
{
p->coef=sum;
pre->next=p;pre=pre->next;p=p->next;
temp=q;q=q->next;free(temp);
}
else
{
temp=p->next;free(p);p=temp;
temp=q->next;free(q);q=temp;
}
}
if (q->expn<p->expn)
{
pre->next=q;
pre=pre->next;
q=q->next;
}
}
if(p!=NULL)
pre->next=p;
else
pre->next=q;
}
void print(node * p)
{
while(p->next!=NULL)
{
p=p->next;
printf(" %f*x^%d",p->coef,p->expn);
}
}
void calculate()
{ float cal=1.0,mid=0.0,las;
int j;
float num, x;
int i=0;
float later=0.0;
int e[MAX];float c[MAX];
printf("Please input num:");
scanf("%f",&num);
printf("Please input x:");
scanf("%f",&x);
printf("Please input e[0]:");
scanf("%d",&e[0]);
printf("Please input c[0]:");
scanf("%f",&c[0]);
while(e[i]!=0 && c[i]!=0.0 )
{ cal=1;
for(j=0;j<e[i];j++)
{
cal=cal*x;
}
i++;
mid=cal*c[i-1];
later+=mid;
printf("Please input e[%d] and c[%d] :",i,i);
scanf("%d%f",&e[i],&c[i]);
}
las=later+num;
printf("The Result is :\n");
printf("%f",las);
sleep(3);
}
void main()
{
node * pa,* pb,*pc,*p,*q,*pre;
int driver=VGA,mode=VGAHI;
initgraph(&driver,&mode,"c:\\tc ");
setbkcolor(BLUE);
setcolor(RED);
printf("Welcome,Let's go!\n");
printf("Next, you will see the process of computing !");
printf("\nPlease input the coef and expn of pa:\n");
pa=create();
print(pa);
printf("\nPlease input the coef and expn of pb:\n");
pb=create();
print(pb);
p=pa->next;
pa->next=NULL;
while(p!=NULL)
{
if(pa->next==NULL)
{
pa->next=p;p=p->next;
pa->next->next=NULL;
}
else
{ pre=pa;q=pre->next;
while(q!=NULL && p->expn>q->expn)
{
pre=q;q=q->next;
}
q=p->next;
p->next=pre->next;
pre->next=p;
p=q;
}
}
printf("\nthe first ordered one:\n");print(pa);
p=pb->next;
pb->next=NULL;
while(p!=NULL)
{
if(pb->next==NULL)
{
pb->next=p;p=p->next;
pb->next->next=NULL;
}
else
{ pre=pb;q=pre->next;
while(q!=NULL && p->expn>q->expn)
{
pre=q;q=q->next;
}
q=p->next;
p->next=pre->next;
pre->next=p;
p=q;
}
}
printf("\nthe second ordered one:\n");print(pb);
printf("\nSum of the polys is:\n");
polyadd(pa,pb);
print(pa);
printf("\n");
setbkcolor(RED);
calculate();
}
编后总结
本程序在逻辑设计，详细设计，程序编码和程序调试阶段时本来都城有设计save()保存函数，和load()下载函数，分别用来保存创建的多项式，和下载其它需计算的多项式数据，这样这个系统才能更加实用，void createadj()原来的函数原型为arcnode *createdj()函数中用链表结构把adjmatrix[][]的数据都保存其中，这样就能实现数据的保存，但随之要把Dijkstra中的adjmatrix[][]转换成用arcnode 指针的形式进行表示，因为只有这样，下载后的数据才能使用。但在最后的调试阶段中，发现dijkstra无法运行，但又苦于无法用save()函数保存adjmatrix[][],最后只放弃save()和load()函数，在 main()主函数中初始化该算式。从这次程序设计中我看到自己的不足之处，今后要更努力的学习和掌握好数据结构程序设计的知识。
我们的数据结构实验也是这题，需要我把我的实验报告给你参考下么！
我这里就只发这部分的代码。
Status PreOrderTraverse(BiTree T)
{
//先序遍历二叉树T的递归算法
if (T)
{
printf("%d ",T->data);
if(T->lchild) PreOrderTraverse(T->lchild);
if(T->rchild) PreOrderTraverse(T->rchild);
return FALSE;
}
else return OK;
}
Status PreOrder(BiTree T)
{
//先序遍历二叉树T的非递归算法
while(!(T==NULL&&top==NULL))
{
if(T)
{
printf("%d ",T->data);
push(T);
T=T->lchild;
}
else
{
T=(BiTree)pop();
T=T->rchild;
}
}
}
Status InOrderTraverse(BiTree T)
{
//中序遍历二叉树T的递归算法
if (T)
{
if (T->lchild) InOrderTraverse(T->lchild);
printf("%d ",T->data);
if (T->rchild) InOrderTraverse(T->rchild);
return FALSE;
}
else return OK;
}
Status InOrder(BiTree T)
{
//中序遍历二叉树T的非递归算法
while(!(T==NULL&&top==NULL))
{
while(T)
{
push(T);
T=T->lchild;
}
T=(BiTree)pop();
printf("%d ",T->data);
T=T->rchild;
}
}
Status PostOrderTraverse(BiTree T)
{
//后序遍历二叉树T的递归算法
if (T)
{
if (T->lchild) PostOrderTraverse(T->lchild);
if (T->rchild) PostOrderTraverse(T->rchild);
printf("%d ",T->data);
return FALSE;
}
else return OK;
}
Status PostOrder(BiTree T)
{
//后序遍历二叉树T的递归算法
unsigned sign;//记录结点从栈中弹出的次数
while(!(T==NULL&&top==NULL))
{
if(T)
{
push(T);//第一次遇到结点T时压入其指针
push(1);//置标志为1
T=T->lchild;
}
else
{
while(top)
{
sign=pop();
T=(BiTree)pop();
if(1==sign)//表示走过T的左子树
{
push(T);
push(2);
T=T->rchild;
break;
}
else
{
if(2==sign)//表示T的左右子树都已走过
{
printf("%d ",T->data);
T=NULL;
}
}
}
}
}
}