算法与数据结构实验一元多项式求和

《算法与数据结构》实验报告

姓名：***

班级：计科01

学号：**********

实验题目：链表的应用

实验内容：一元多项式求和

把任意给定的两个一元多项式P(x) ,Q(x) 输入计算机，计算它们的和并输出计算结果。

设计分析：

一元多项式可以用单链表表示，结点结构图示如下：

coef exp next

一元多项式链表的结点结构

一元多项式算法伪代码如下：

1. 工作指针p、q初始化；

2. while（p存在且q存在）执行下列三种情形之一

2.1 如果p->expexp，则指针p后移; 2.2 如果p->exp>q->exp，则 2.2.1 将结点q插入到结点p之前； 2.2.2 指针q指向原指结点的下一个结点；

2.3 如果p->exp=q->exp，则

2.3.1 p->coef =p->coef+q->coef； 2.3.2 如果p->coef ==0，则执行下列操作，否则，指针p后移; 2.3.2.1 删除结点p； 2.3.2.2 使指针p指向它原指结点的下一个结点； 2.3.3 删除结点q； 2.3.4 使指针q指向它原指结点的下一个结点； 3. 如果q不为空，将结点q链接在第一个单链表的后面； 源程序代码：

#include \"StdAfx.h\" #include typedef struct LNode {

int x,z;

struct LNode *next;

}LinkList;

void OutLinkList(LinkList *L); void PutLinkList(LinkList *&L,int n);

LinkList *AddLinkList(LinkList *a,LinkList *b);

void OutXLinkList(LinkList *L); void OutZLinkList(LinkList *L); void main() { }

void PutLinkList(LinkList *&L,int n) {

LinkList *s,*r;

L=(LinkList *)malloc(sizeof(LinkList)); r=L;

for(int i=0;ir->next=NULL;

s=(LinkList *)malloc(sizeof(LinkList));

printf(\"请?输º?入¨?第̨²%d项?的Ì?系¦Ì数ºy：êo\",i+1); scanf(\"%d\",&s->x);

printf(\"请?输º?入¨?第̨²%d项?的Ì?指?数ºy：êo\",i+1); scanf(\"%d\",&s->z); r->next=s; r=s; int n,m;

LinkList *a,*b,*c;

printf(\"\\\本À?程¨¬序¨°可¨¦以°?完ª¨º成¨¦两¢?个?一°?元a多¨¤项?式º?的printf(\"请?输º?入¨?一°?元a多¨¤项?式º?a的Ì?项?数ºym：êo\"); scanf(\"%d\",&m);

printf(\"请?按ã¡ä照?从䨮低̨ª次ä?到Ì?高?次ä?的Ì?顺3序¨°依°¨¤此ä?输º?入¨?PutLinkList(a,m); printf(\"a=\"); OutLinkList(a);

printf(\"请?输º?入¨?一°?元a多¨¤项?式º?b的Ì?项?数ºyn：êo\"); scanf(\"%d\",&n);

printf(\"请?按ã¡ä照?从䨮低̨ª次ä?到Ì?高?次ä?的Ì?顺3序¨°依°¨¤此ä?输º?入¨?PutLinkList(b,n); printf(\"b=\"); OutLinkList(b); c=AddLinkList(a,b);

printf(\"两¢?个?多¨¤项?式º?的Ì?和¨ª为a：êo\\na+b=\"); OutLinkList(c);

Ì?加¨®法¤¡§运?算?。¡ê\\n\");

一°?元a多¨¤项?式º?a的Ì?系¦Ì数ºy和¨ª指?数ºy：êo\\n\");

一°?元a多¨¤项?式º?b的Ì?系¦Ì数ºy和¨ª指?数ºy：êo\\n\");

}

void OutLinkList(LinkList *L) { }

void OutXLinkList(LinkList *L) { }

void OutZLinkList(LinkList *L) {

if(L->z==0)

;

int xi=L->x>0? L->x:-L->x; if(L->x==1||L->x==-1)

;

printf(\"%d\",xi); else char FuHao;

LinkList *p=L->next; FuHao=p->x>0? '+':'-'; if(FuHao=='-') { }

OutXLinkList(p); OutZLinkList(p); p=p->next; while(p!=NULL) { }

printf(\"\\n\");

FuHao=p->x>0? '+':'-'; printf(\"%c\",FuHao); OutXLinkList(p); OutZLinkList(p); p=p->next;

printf(\"%c\",FuHao); if(p->x==-1)

printf(\"1\");

}

else if(L->z==1||L->z==-1) { } else { }

if(L->z<0)

printf(\"/\");

int zhi=L->z>0? L->z:-L->z; printf(\"X^%d\",zhi); if(L->z<0) { }

printf(\"X\");

if(L->x==1||L->x==-1)

printf(\"1\"); printf(\"/\");

LinkList *AddLinkList(LinkList *a,LinkList *b) {

a=a->next; b=b->next;

LinkList *c,*d,*s;

c=(LinkList *)malloc(sizeof(LinkList)); d=c;

while(a!=NULL&&b!=NULL) {

if(a->zz) { }

else if(a->z>b->z) {

s=(LinkList *)malloc(sizeof(LinkList)); s->x=a->x;

s=(LinkList *)malloc(sizeof(LinkList)); s->x=b->x; s->z=b->z; d->next=s; d=s; b=b->next;

}

}

}

s->z=a->z; d->next=s; d=s; a=a->next;

else { }

s=(LinkList *)malloc(sizeof(LinkList)); s->x=a->x+b->x; s->z=a->z; if(s->x==0) { }

a=a->next; b=b->next; d->next=s; d=s; ; else

if(a!=NULL)

d->next=a; d->next=b; d->next=NULL; else if(b!=NULL) else return c;

测试用例：

当a=3x^8-x^5+2x^3+7x^2+5x,b=5x^5+3x^4-7x^2-3x^(-3)时，运行结果如下：

试验总结：

通过本次试验，学会了链表的应用，加深了对链表的理解，知道了链表是把线性表中的元素按照链式储存方式到计算机中的一片连续的储存空间中。储存时用到了动态内存申请的知识。本次试验让我更好的把书本上的知识运用到具体的例子中来，学会了通过vc6.0来建立链表，链表的基本运算输出顺序表等等。同时也了解到了多项式求和问题可以通过链表的知识来解决，也体会其中算法的奥妙。