/*含頭結點的循環鏈表的多項式*/
# include<stdio.h>
# include<stdlib.h>
struct plist /* 多項式結構聲明*/
{
int coef; /*多項式的系數*/
int exp; /*多項式的指數*/
struct plist *next; /*指向下一結點的指針*/
};
typedef struct plist pnode; /* 多項式新類型*/
typedef pnode *plink; /* 多項式指針新類型*/
/*鏈表輸出*/
void printpoly(plink poly)
{
plink ptr;
ptr=poly->next; /*指向鏈表開始*/
while(poly!=ptr) /*鏈表遍歷循環*/
{
/*輸出結點數據*/
printf("%dX^%d",ptr->coef,ptr->exp);
ptr=ptr->next; /* 指向下一結點*/
if(poly!=ptr) printf("+");
}
printf("\n"); /* 換行*/
}
/*使用數組值創建多項式*/
plink createpoly(int *array,int len)
{
plink head; /*循環鏈表的指針*/
plink before; /*前一結點的指針*/
plink new_node; /*新結點的指針*/
int i;
/*創建頭結點，分配結點內存*/
head=(plink)malloc(sizeof(pnode));
if(!head) return NULL; /*檢查內存指針*/
head->exp=-1; /*創建結點內容*/
before=head; /*指向第一個結點*/
for(i=len-1;i>=0;i--) /*用循環創建其他結點*/
if(array[i]!=0)
{
/*分配結點內存*/
new_node=(plink)malloc(sizeof(pnode));
if(!new_node) return NULL; /*檢查內存指針*/
new_node->coef=array[i]; /*創建系數內容*/
new_node->exp=i; /*創建指數內容*/
new_node->next=NULL; /*設置指針初值*/
before->next=new_node; /*將前結點指向新結點*/
before=new_node; /*新結點成為前結點*/
}
new_node->next=head; /*創建環狀鏈接*/
return head; /*返回鏈表起始指針*/
}
/*多項式相加*/
plink polyadd(plink poly1,plink poly2)
{
plink head1; /*多項式1的開始*/
plink head2; /*多項式2的開始*/
plink result; /*多項式的結果*/
plink before; /*前一結點的指針*/
plink new_node; /*新結點的指針*/
head1=poly1->next; /*指向多項式1的開始*/
head2=poly2->next; /*指向多項式2的開始*/
/*創建頭結點且分配結點內存*/
result=(plink)malloc(sizeof(pnode));
if(!result) return NULL; /*檢查內存指針*/
result->exp=-1; /*創建結點內容*/
before=result; /*指向第一個結點*/
while(poly1!=head1||poly2!=head2)
{
/*分配結點內存*/
new_node=(plink)malloc(sizeof(pnode));
if(!new_node) return NULL; /*檢查內存指針*/
if(head1->exp<head2->exp) /*多項式2的指數大*/
{
new_node->coef=head2->coef; /*設置系數*/
new_node->exp=head2->exp; /*設置指數*/
head2=head2->next; /*指向下一結點*/
}
else if(head1->exp>head2->exp) /*多項式1的指數大*/
{
new_node->coef=head1->coef; /*設置系數*/
new_node->exp=head1->exp; /*設置指數*/
head1=head1->next; /*指向下一結點*/
}
else /*多項式的指數相等*/
{
/*系數相加*/
new_node->coef=head1->coef+head2->coef;
new_node->exp=head1->exp; /*設置指數*/
head1=head1->next; /* 指向下一結點*/
head2=head2->next; /* 指向下一結點*/
}
before->next=new_node; /*將前一結點指向新結點*/
before=new_node; /*新結點成為前結點*/
}
new_node->next=result; /*創建環狀鏈接*/
return result; /*返回多項式的指針*/
}
void main()
{
plink poly1; /*多項式1的指針*/
plink poly2; /*多項式2的指針*/
plink result; /*多項式結果的指針*/
int list1[6]={4,0,3,0,7,0}; /*數組1的內容*/
int list2[6]={9,7,1,0,5,6}; /*數組2的內容*/
poly1=createpoly(list1,6); /*創建多項式1*/
printf("the content1:");
printpoly(poly1); /*輸出多項式1*/
poly2=createpoly(list2,6); /*創建多項式2*/
printf("the content2:");
printpoly(poly2); /*輸出多項式2*/
result=polyadd(poly1,poly2); /*多項式相加*/
printf("the add:");
printpoly(result); /*輸出多項式結果*/
}