用双链表实现多项式相加及输出.doc

#include<stdio.h>
#include<stdlib.h>
const int NUM = 10;

/*定义多项式的节点*/
struct node
{
int ratio;//多项式的系数
int exp; //多项式的指数
struct node *next;
};

typedef struct node polynode;
typedef polynode *PolyLink;

void printpoly(PolyLink L);//多项式的输出
PolyLink creatpoly(int a[], int num);//多项式的创建
PolyLink addpoly(PolyLink h1, PolyLink h2);//多项式的相加

#include"head.h"

/*多项式的输出*/
void printpoly(PolyLink L)
{
PolyLink ptr;
ptr = L->next;

while(ptr->exp != -1)
{
printf("%dX^%d", ptr->ratio, ptr->exp);

if(ptr->next->exp != -1)
printf(" + ");

ptr = ptr->next;
}
//printf("\n\n输出完毕！\n\n");
}

/*多项式的创建*/
PolyLink creatpoly(int a[], int num)
{
PolyLink before, newnode;
PolyLink head;
head = (PolyLink)malloc(sizeof(PolyLink));
if(!head)
{
perror("Fail to malloc head_node");
exit(1);
}
head->exp = -1;
head->ratio = 0;
head->next = NULL;
before = head;

for(int i = num - 1; i >= 0; i--)
{
if(a[i] != 0)
{
newnode = (PolyLink)malloc(sizeof(PolyLink));
if(!newnode)
{
perror("Fail to malloc new_node");
exit(1);
}
newnode->ratio = a[i];
newnode->exp = i;
newnode->next = NULL;
before->next = newnode;
before = newnode;
}
}
before->next = head;

return head;
}

/*多项式相加*/
PolyLink addpoly(PolyLink h1, PolyLink h2)
{
PolyLink head, move, new_node;
head = (PolyLink)malloc(sizeof(PolyLink));
if(!head)
{
perror("Fail to malloc head");
exit(1);
}

head->next = NULL;
head->exp = -1;
head->ratio = 0;
move = head;

h1 = h1->next;
h2 = h2->next;

while(h1->exp != -1 || h2->exp != -1)
{
if(h1->exp > h2->exp)
{
move->next = h1;
move = h1;
h1 = h1->next;
}
else if(h1->exp < h2->exp)
{
move->next = h2;
move = h2;
h2 = h2->next;
}
else
{
new_node = (PolyLink)malloc(sizeof(PolyLink));
if(!new_node)
{
perror("Fail to mallo new_node");
exit(1);
}

new_node->ratio = h1->ratio + h2->ratio;
new_node->exp = h1->exp;
move->next = new_node;
move = new_node;
h1 = h1->next;
h2 = h2->next;
}
}

move->next = head;

return head;
}

/*****************************************************
* *
* 软件名称：有头节点的循环单链表处理多项式相加 *
* 软件版本：v001 *
* 写作日期：2012.11.2 *
* 编写要求：1.用有头节点的循环单链表。2.用数组给 *
* 多项式赋值 3.实现多项式相加 *
* *
*****************************************************/

#include"head.h"

int main(void)
{

PolyLink head,head1, head2;
int polyarr1[NUM] = {7, 0, 2, 4, 0, 3, 0, 12, 6, 8};
int polyarr2[NUM] = {4, 7, 0, 6, 3, 8, 0, 21, 0, 6};
head1 = creatpoly(polyarr1, NUM);
head2 = creatpoly(polyarr2, NUM);
printpoly(head1);
printf("\n\n");
printpoly(head2);
printf("\n\n");
printf("多项式相加以后:\n");
head = addpoly(head1, head2);
printpoly(head);
printf("\n\n\n");

return 0;
}