数据结构实验-一元多项式的加法运算

一、实验目的

通过实现多项式加法，对链表有更深入的了解

二、实验内容

问题描述：

设计一个一元稀疏多项式简单的加法计算器 实现要求：

一元稀疏多项式简单计算器的基本功能是： （1）输入并建立多项式：

A(x)73x9x85x17； B(x)8x22x79x8

（2）输出多项式

（3）多项式A和B相加，建立多项式C＝A＋B，并输出相加的结果多项式C

（4）选作：多项式A和B相减，建立多项式C＝A－B，并输出相减的结果多项式D 方法说明：

（1）多项式的输入与存储

用带表头结点的单链表存储多项式，链表中的每个节点分别存储多项式各项的系数和指数，即每从键盘输入多项式的一对数（系数，指数），可对应建立链表的一个结点。每个节点的结构为： Coef exp next

建立两个链表，其中pa和pb分别为它们的头指针：

4 -1 7 0 3 1 9 8 5 17 ∧ Pa pb 3 -1 -9 8 ∧ 22 7 8 1

结果链表 Pa(或者是Pc)

22 7 5 17 ∧ 7 0 7 -1 11 1 Pc

（2）多项式数据类型的定义 struct tagNode { float coef; int exp; struct tagNode *next; };

typedef struct tagNode Node; typedef struct tagNode* pNode;

（3）主要算法

①创建两个链表，分别存放多项式1和多项式2，这两个链表中的节点是按指数降序或者升序排列的 ②多项式相加，下面给出多项式相加的部分实现 /*

下面的函数实现两个多项式的相加，要相加的链表分别由pa和pb指向（其中，pa，pb都是分配了空间的头结点）。

相加的结果直接由pa指向的链表保存，即是在pa链表中添加或删除（当系数因为相加为0的情况下）一些结点，构成结果。

相加的链表中指数按从小到大的顺序排列好的，是升序链表。 */

void add_poly(Node *pa,Node *pb) { Node *p=pa->pNext;//链表1，将来的结果也放在此 Node *q=pb->pNext;//链表2 Node *pre=pa; Node *u;//临时用 float x; while (p!=NULL && q!=NULL)//当两个链表都不为空 { if (p->expexp)//比较链表1跟链表2当前节点的指数大小，链表1也是存放结果的地方 { pre=p; p=p->pNext;//p指向要比较的下一个结点。pre指向的是结果链表的最后一个结点。 } else if (p->exp==q->exp)//假如链表1和链表2的指数相等，就要系数相加 { x=p->coef+q->coef; if (x!=0)//相加后的系数不为0，有必要保留一个结点就可以了 { p->coef=x; pre=p; } else//如果相加后，系数不是0，不需要保留任何一个结点，在这里删除链表1的结点，下面删除链表2的结点 { pre->pNext=p->pNext;//保持链表1的连续性 free(p); } p=pre->pNext;//p指向要比较的下一个结点 //下面的代码是进行链表2结点的删除工作，因为指数相等，仅仅需要保留一个结点就可以了

//而结果直接保存在链表1中，所以，删除链表2的结点。 u=q; q=q->pNext; free(u); } else//如果链表2的当前节点指数小，那么要把链表2的当前节点加入到结果链表中（即是链表1） {//相当于把结点插入到链表1中，用u作为临时变量，保存链表2的下一个当前节点的位置。 u=q->pNext; q->pNext=p; pre->pNext=q; pre=q; q=u; } } if (q)//如果链表2比链表1长，那么需要把链表2多余的部分加入结果链表中。链表1比链表2长，则什么都不用做。 { pre->pNext=q; } free(pb); }

③输出结果多项式

三、实验代码 PolyAdd_H

#ifndef PolyAdd_H #define PolyAdd_H struct tagNode {

float coef; int exp;

struct tagNode*next; };

typedef struct tagNode Node; typedef struct tagNode* PNode;

void InsertList(PNode head,PNode pnode ); void CreateList(PNode head); void Add_Poly(PNode pa,PNode pb); void printLinkedList(PNode head); void Poly_Deri(PNode head); void Printfpoly(PNode head);

#endif

Main.c

# include # include # include \"PolyAdd.h\" int main(void) { }

PNode head1=(PNode)malloc(sizeof(struct tagNode)); PNode head2=(PNode)malloc(sizeof(struct tagNode)); CreateList(head1); CreateList(head2); printf(\"\\n\");

Add_Poly(head1,head2);

printf(\"多项式相加的结果为：\\n\"); printLinkedList(head1); printf(\"\\n\"); return 0;

PolyAdd.c

# include # include # include \"PolyAdd.h\"

void InsertList(PNode head,PNode pnode) { }

void CreateList(PNode head) {

PNode pPre=head; while(pPre->next!=NULL) { }

if(pPre->next==NULL)

pPre->next=pnode;

if(pPre->next->exp>pnode->exp) { }

pPre=pPre->next;

pnode->next=pPre->next;

pPre->next=pnode; break;

}

int exp; float coef; PNode pTemp=NULL; head->next=NULL;

printf(\"请输入多项式的数据，顺序为系数，指数；多项式结束则以0,0结尾\\n\"); scanf(\"%f,%d\while(coef!=0||exp!=0) { }

pTemp=(PNode)malloc(sizeof(struct tagNode)); pTemp->coef=coef; pTemp->exp=exp; pTemp->next=NULL; InsertList(head,pTemp); scanf(\"%f,%d\

void printLinkedList(PNode head) { }

void Add_Poly(PNode pa,PNode pb) {

PNode p=pa->next; PNode q=pb->next; PNode pre=pa; PNode u; float x;

while(p!=NULL&&q!=NULL) { }

else if(p->exp==q->exp) {

x=p->coef+q->coef; if(x !=0) {

p->coef=x,pre=p; if(p->expexp)

{

pre=p;

PNode temp=head->next; while(temp!=NULL) { }

printf(\"%0.0f \printf(\"%d,emp=temp->next;

p=p->next;

}

}

} else { }

p=pre->next; u=q; q=q->next; free(u);

pre->next=p->next; free(p);

else { } } if(q)

pre->next=q; free(pb); return 0;

u=q->next; q->next=p; pre->next=q; pre=q; q=u;

void Poly_Deri(PNode head) {

PNode prev, cur; cur = prev = head;

if (head->next == NULL && head->exp == 0) { }

while (cur != NULL) {

if (cur->exp == 0) { }

cur->coef = cur->coef * cur->exp; cur->exp = cur->exp - 1; prev = cur; cur = cur->next;

prev->next = NULL; free(cur); break; head->coef = 0; return;

}

} return 0;

实验结果：

四、实验总结