Question

单链表实现多项式相加 代码

Answer 1

以下源代码应该能够满足你的要求，C语言实现：
#include "stdio.h"

#define MAX 100

/* 链表结点结构 */
typedef struct LNode{
double coef; /* 系数 */
int exp; /* 指数 */
struct LNode *next;
}LNode;

/* 初始化链表 */
LNode *Init()
{
LNode *head = (LNode*)malloc(sizeof(LNode));
head->next = NULL;
return head;
}

/* 将值为data的结点插入到head链表的最后 */
void AddNode(LNode *head, double coef, int exp)
{
LNode *pre = head->next;
LNode *temp;
temp = (LNode*)malloc(sizeof(LNode));
temp->coef = coef;
temp->exp = exp;
temp->next = NULL;

if(pre == NULL)
{
head->next = temp;
return;
}

for(; pre->next!=NULL; pre=pre->next);

pre->next = temp;
}

/* 输出head链表的所有结点的值 */
void List(LNode *head)
{
LNode *curr;
printf("All nodes : ");
for(curr=head->next; curr!=NULL; curr=curr->next)
{
printf("(%lf, %d)\t", curr->coef, curr->exp);
}
printf("\n");
}

/* 返回head链表的所有结点的数量 */
int Size(LNode *head)
{
int len = 0;
LNode *curr;
for(curr=head->next; curr!=NULL; curr=curr->next,len++);

return len;
}

LNode *Add(LNode *headA, LNode *headB)
{
LNode *currA, *currB, *headC;
double sum;
currA = headA->next;
currB = headB->next;
headC = Init();
while(currA!=NULL && currB!=NULL)
{
if(currA->exp > currB->exp)
{
AddNode(headC, currA->coef, currA->exp);
currA = currA->next;
}
else if(currA->exp < currB->exp)
{
AddNode(headC, currB->coef, currB->exp);
currB = currB->next;
}
else
{
sum = currA->coef + currB->coef;
if(sum != 0)
{
AddNode(headC, sum, currA->exp);
}
currA = currA->next;
currB = currB->next;
}
}
while(currA != NULL)
{
AddNode(headC, currA->coef, currA->exp);
currA = currA->next;
}
while(currB != NULL)
{
AddNode(headC, currB->coef, currB->exp);
currB = currB->next;
}

return headC;
}

void main()
{
LNode *headA, *headB, *headC;
headA = Init();
headB = Init();
AddNode(headA, 1.0, 5);
AddNode(headA, -1.0, 3);
AddNode(headA, 1, 0);
AddNode(headB, 0.5, 5);
AddNode(headB, 1.0, 4);
AddNode(headB, 1.0, 3);

List(headA);
List(headB);

headC = Add(headA, headB);

List(headC);

}