引言
符號多項式的操作，已經(jīng)成為表處理的典型用例。用一個長度為m且每個元素有兩個數(shù)據(jù)項（系數(shù)項和指數(shù)項）的線性表((p1,e1), (p2,e2), ···,(pm, em))便可唯一確定多項式Pn(x)。
對應(yīng)于線性表的兩種存儲結(jié)構(gòu)，上述定義的一元多項式也可以有兩種存儲表示方法。由于多項式多進(jìn)行相加、乘法等操作，因此采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，節(jié)約結(jié)點插入、刪除等操作時間。
元素定義
typedef struct{
float coef; // 項的系數(shù)
int exp； // 項的指數(shù)
}ElemType; // 多項式的項
一元多項式定義
typedef struct PNode{
ElemType data; // 數(shù)據(jù)項
struct PNode *next; // 指向后繼元素
}PNode, *Polynomail; // 帶頭結(jié)點的鏈表表示多項式
基本操作
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define SUCCESS 1
#define FAILURE 0
// 定義多項式數(shù)據(jù)元素
typedef struct{
float coef; // 項的系數(shù)
int exp; // 項的指數(shù)
} ElemType;
int compare(ElemType e1, ElemType e2){
// 依e1的指數(shù)值<（或=）（或>）e2的指數(shù)值，分別返回-1,0和1
if(e1.exp < e2.exp){
return -1;
} else if(e1.exp == e2.exp){
return 0;
} else {
return 1;
}
}
typedef struct PNode{
ElemType data;
struct PNode *next;
}PNode, *Polynomail; // 帶頭結(jié)點的有序鏈表表示多項式
// 基本操作
int InitPolyn(Polynomail *P){
// 初始化P
*P = (Polynomail)malloc(sizeof(PNode));
if(!*P) exit(-1);
(*P)->next = NULL;
}
int LocatePolyn(Polynomail P, ElemType e, int(*compare)(ElemType, ElemType)){
// 在P中尋找和e滿足compare結(jié)果為0的元素，成功返回1，否則返回-1
P = P->next;
while(P){
if(compare(P->data, e) == 0) return 1;
P = P->next;
}
return -1; // 沒有找到
}
void CreatPolyn(Polynomail *P, int m){
// 輸入m項系數(shù)和指數(shù)，建立表示一元多項式的有序鏈表P
printf("請輸入%d項系數(shù)和參數(shù), 格式:\ncoef exp\n", m);
Polynomail head = *P;
PNode *s;
head->data.coef = 0.0; head->data.exp = -1; // 頭結(jié)點
int i;
for(i=0;i<m;){
s = (Polynomail)malloc(sizeof(PNode));
if(!s) exit(-1); // 存儲空間不足
scanf("%f %d", &(s->data.coef), &(s->data.exp));
if(LocatePolyn(*P, s->data, compare) < 0) { // 排除相同指數(shù)項
s->next = NULL;
head->next = s;
head = s;
i++;
}
}
}
void DestroyPolyn(Polynomail *P){
// 銷毀一元多項式P
Polynomail s = *P;
Polynomail t;
while(s){
t = s->next;
free(s);
s = t;
}
*P = NULL;
}
void PrintPolyn(Polynomail P){
// 打印輸出一元多項式
P = P->next;
int i = 1;
if(P) printf("%.2fx^%d", P->data.coef, P->data.exp);
P = P->next;
while(P){
printf("%+.2fx^%d", P->data.coef, P->data.exp);
P = P->next;
}
printf("\n");
}
int PolynLength(Polynomail P){
// 返回一元多項式P的項數(shù)
int l = 0;
P = P->next;
while(P){
l++;
P = P->next;
}
return l;
}
void AddPolyn(Polynomail *Pa, Polynomail *Pb,
int(*compare)(ElemType, ElemType)){
// 完成有序多項式相加運算，即Pa = Pa + pb; 并銷毀Pb
Polynomail heada = *Pa, headb = *Pb;
Polynomail headc = heada;
Polynomail temp; // 釋放節(jié)點時使用
heada = heada->next; // 指向首元素
headb = headb->next;
while(heada && headb){
if(compare(heada->data, headb->data) < 0){
// 當(dāng)前heada節(jié)點指數(shù)小于headb
headc->next = heada;
headc = heada;
heada = heada->next;
} else if(compare(heada->data, headb->data) > 0){
// 當(dāng)前heada節(jié)點指數(shù)大于headb
headc->next = headb;
headc = headb;
headb = headb->next;
} else{
// 兩者節(jié)點指數(shù)相同
if(heada->data.coef + headb->data.coef != 0){
heada->data.coef = heada->data.coef +
headb->data.coef;
headc->next = heada;
headc = heada;
heada = heada->next;
} else {
temp = heada;
heada = heada->next;
free(temp);
}
temp = headb;
headb = headb->next;
free(temp);
}
}
if(headb) headc->next = headb; // 鏈接Pb中剩余節(jié)點
free(*Pb); // 釋放Pb頭結(jié)點
}
void MultiplyPolyn(Polynomail Pa, Polynomail Pb, Polynomail *Pc){
// 完成多項式相乘運算，即Pc = Pa * Pb
Polynomail pa, pb, s;
// 臨時鏈表
Polynomail temp, headtemp;
pa = Pa->next;
while(pa){
InitPolyn(&temp);
headtemp = temp;
pb = Pb->next; // 每次需將pb重置
while(pb){ // pa同pb中每項相乘并將結(jié)果存在pc中
s = (Polynomail)malloc(sizeof(PNode));
s->data.coef = pa->data.coef * pb->data.coef;
s->data.exp = pa->data.exp + pb->data.exp;
s->next = NULL;
headtemp->next = s;
headtemp = s;
pb = pb->next;
}
// 將每次乘積結(jié)果相加存儲至Pc中
AddPolyn(Pc,&temp, compare);
pa = pa->next;
}
}
void main(){
Polynomail P;
// 初始化
printf("******** init ********\n");
InitPolyn(&P);
// 賦值
printf("********* create value **************\n");
CreatPolyn(&P, 6);
// 打印
printf("********* console value **********\n");
PrintPolyn(P);
// 長度
printf("*************** length **************\n");
printf("P length is: %d\n", PolynLength(P));
//銷毀
printf("*************** destroy **************\n");
DestroyPolyn(&P);
printf("after destory, P postion is: %p\n", P);
// 多項式相加
printf("********** polyn add ******************\n");
Polynomail P1, P2;
InitPolyn(&P1); InitPolyn(&P2);
CreatPolyn(&P1, 5); CreatPolyn(&P2, 6);
printf("P1: ");
PrintPolyn(P1);
printf("P2: ");
PrintPolyn(P2);
printf("\n");
AddPolyn(&P1, &P2, compare);
printf("After add, P1: ");
PrintPolyn(P1);
printf("\n");
// 多項式相乘
printf("************ polynnomail multi********\n");
Polynomail P3, P4, P5;
InitPolyn(&P3); InitPolyn(&P4), InitPolyn(&P5);
CreatPolyn(&P3, 4); CreatPolyn(&P4, 3);
printf("P3: ");
PrintPolyn(P3);
printf("P4: ");
PrintPolyn(P4);
printf("\n");
MultiplyPolyn(P3, P4, &P5);
printf("After multi, P5: ");
PrintPolyn(P5);
printf("\n");
}
運行結(jié)果
******** init ********
********* create value **************
請輸入6項系數(shù)和參數(shù), 格式:
coef exp
1 0
-2 1
4 3
6.2 5
-10.4 29
16 356
********* console value **********
1.00x^0-2.00x^1+4.00x^3+6.20x^5-10.40x^29+16.00x^356
*************** length **************
P length is: 6
*************** destroy **************
after destory, P postion is: (nil)
********** polyn add ******************
請輸入5項系數(shù)和參數(shù), 格式:
coef exp
1 0
-9 5
3 7
5 8
10 10
請輸入6項系數(shù)和參數(shù), 格式:
coef exp
3 0
9 2
9 5
-4.2 7
1 8
-15 12
P1: 1.00x^0-9.00x^5+3.00x^7+5.00x^8+10.00x^10
P2: 3.00x^0+9.00x^2+9.00x^5-4.20x^7+1.00x^8-15.00x^12
After add, P1: 4.00x^0+9.00x^2-1.20x^7+6.00x^8+10.00x^10-15.00x^12
*********** polynnomail multi********
請輸入4項系數(shù)和參數(shù), 格式:
coef exp
9 0
-10 1
7 2
6 3
請輸入3項系數(shù)和參數(shù), 格式:
coef exp
-5 0
4 1
-2 3
P3: 9.00x^0-10.00x^1+7.00x^2+6.00x^3
P4: -5.00x^0+4.00x^1-2.00x^3
After multi, P5: -45.00x^0+86.00x^1-75.00x^2-20.00x^3+44.00x^4-14.00x^5-12.00x^6
