如何用鏈表實現一元多項式相加

杜金庭 唐海川

一元多項式的表示在計算機內可以用鏈表來表示，為了節省存儲空間，只存儲多項式中系數非零的項。 鏈表中的每一個結點存放多項式的一個系數非零項，它包含三個域，分別存放該項的系數、指數以及指向下一個多項式項結點的指針。對于如何利用鏈表將兩個一元多項式分別存入兩個鏈表中，通過相加將鏈表合并后并輸出合成后的新的一元多項式。在運行的過程中主要所運用的就是利用鏈表的data域相加完成鏈表的加法運算，輸出相加之后的新一元多項式。

數據結構的存儲結構有兩種：順序儲存結構和鏈式儲存結構，而我們所做的一元多項式的相加及其表示，就是我們要把算法想象成是一種抽象的運行算法，將一元多項式抽象的想象成一個新的線性表。

程序流程如下：

使用typedef 和 struct 定義的新類型名稱，其用途與內建類型的名稱相同，可以用來：聲明和初始化結構體變量;創建并根據自己的意愿初始化結構數組，用鏈表表示多項式時，每個鏈表結點儲存多項式中的一個非零項，包括系數（data1）和指數（data2）兩個數據域及一個指針域（next）。對應的數據結構定義為：

typedef struct LNode

{

int data1;//系數

int data2;//指數

struct LNode *next;//指向下一節點的指針

}LNode， *LinkList;

之后需要初始化鏈表：因為實現目的過程需要使用鏈表進行算法的實現，所以開始時需要先創建兩個有頭結點的空鏈表，因為初始化的鏈表擁有兩個data域（data1，data2）和一個指針域（next），我們要利用后插法建立單鏈表，將“X”的系數放入data1中，冪放入data2中，這樣指針域next就可以存放下一個節點的地址，初始化函數void Init（LinkList *L）是一個無參函數，這樣就能成功實現鏈表的初始化。

在接下來的過程中，所用到的輸入函數LinkList Creat（int n）是一個無返回值的有參函數，用于輸入系數和指數。然后通過為“s”申請一塊大小為（sizeof（LinkList））的內存，生成一個新的節點“*s”，之后就可以輸入多項式當前項的系數和指數然后付給新結點*s的數據域。

根據代碼可以判斷，我們將要進行指數大小判斷，比較函數int Compare（int a， int b）

當p1的指數大于p2的指數時，函數返回1，當p1的指數小于p2的指數時，返回-1，當p1的指數等于p2的指數時，返回0.

連接函數void Attach（int c， int d， LinkList *pRear）

該連接函數用于把得到的結果多項式一項一項的接到用front記錄結果多項式鏈表的頭結點的后面，為“p”申請一個新的節點，“p->date1/date2=c/d”表示對“p”這一鏈表擁有兩個data域（data1，data2）進行賦值，將其當前所指向的新結點插入到這一時刻多項式所表達的尾部。

void Attach（int c， int d， LinkList* pRear） {

LinkList p;

p = （LinkList）malloc（sizeof（LinkList））;

p->data1 = c;

p->data2 = d;

p->next = NULL;

（*pRear）->next = p;

*pRear = p;

}

多項式相加函數LinkList PolyAdd（LinkList p1， LinkList p2）

該函數作為代碼核心函數，作用是將兩個一元多項式中指數相同的每一項加在一起，并返回結果多項式的首地址。首先利用“front”申請新的節點，將結果多項式鏈表的頭節點用前面的“front”來進行記錄，。在運算的過程中，就會出現兩個多項式可能都有非零項需要進行處理，如果說“p1”的指數大于“p2”的指數，那么“p2”的系數和指數都將會存入多項式鏈表中，存儲完成后，“p2”將會繼續指向下一節點，

由此可知，對于“p1”和“p2”的互相比較，為的就是哪一個先進行存入和指向下一步，同理，如果“p1”的指數小于“p2”的指數，那么“p1”的系數和指數都將會存入多項式鏈表中，存儲完成后，“p1”將會繼續指向下一節點，當然也不能忘記 “p1”和“p2”的指數相同這種情況，那么和剛剛的兩種就會有些不同，他們會將自身相同的系數相加，相加完成之后生成的系數和“p1”的指數存入多項式鏈表，同時“p1”和“p2”指向下一個節點。

節點的插入也會有順序之分，當“p1”和“p2”兩者中其中有一方已經完全的插入了多項式鏈表，那么緊接其后的就是另一方全部的插入多項式鏈表里，插入完成后讓上一結構內的“front”去指向結果多項式的第一個非零項，這樣就會將釋放一個臨時空表頭結點。

void PrintAns（LinkList ans）這部分的結構體，目的是為了將結果進行打印，將鏈表中第一個節點輸出并指向下一節點，輸出后開始對后續的節點依次進行輸出，如果鏈表結束，輸出的就是“0”。大部分的結構的進程或者注釋都進行了很詳細的注釋，接下來就是對于我們這個一元多項式的相加進行測驗，首先我們要做的就是屬于第一個 多項式有幾項，第二個多項式有幾項，輸入的第一個多項式要按照系數指數的順序進行輸入，同理，第二個多項式的順序與第一個多項式的順序相同，當然輸入的項式的多少，取決于你要測試的項數，所后進行調式，產生最終的運算結果。

一元多項式的相加是對創建鏈表使用鏈表最簡單的一種運用，大多數函數的使用更需要注重的是函數與函數之間的相互配合，下面所表述的是對實現一元多項式相加的全部代碼：

代碼主體：

#include

#include

typedef struct LNode

{

int data1;

int data2;

struct LNode* next;

} LNode， * LinkList;

void Init（LinkList* L） {

*L = （LinkList）malloc（sizeof（LinkList））;

（*L）->next = NULL;

}

LinkList Creat（int n） {

LinkList h， s， t;

t = h = （LinkList）malloc（sizeof（LinkList））;

for （int i = 0; i < n; i++） {

s = （LinkList）malloc（sizeof（LinkList））;

h->next = s;

h = s;

scanf（"%d%d"， &s->data1， &s->data2）;

}

h->next = NULL;

t = t->next;

return t;

}

int Compare（int a， int b） {

if （a > b）

return 1;

if （a < b）

return -1;

if （a == b）

return 0;

}

void Attach（int c， int d， LinkList* pRear） {

LinkList p;

p = （LinkList）malloc（sizeof（LinkList））;

p->data1 = c;

p->data2 = d;

p->next = NULL;

（*pRear）->next = p;

*pRear = p;

}

LinkList PolyAdd（LinkList p1， LinkList p2） {

LinkList front， rear， temp;

int sum;

rear = （LinkList）malloc（sizeof（LinkList））;

front = rear;

while （p1 ！= NULL && p2 ！= NULL） {

if （Compare（p1->data2， p2->data2） == 1） {

Attach（p2->data1， p2->data2， &rear）;

p2 = p2->next;

} else if （Compare（p1->data2， p2->data2） == -1） {

Attach（p1->data1， p1->data2， &rear）;

p1 = p1->next;

} else if （Compare（p1->data2， p2->data2） == 0） {

sum = p1->data1 + p2->data1;

if （sum ！= 0）

Attach（ sum， p1->data2， &rear）;

p1 = p1->next;

p2 = p2->next;

}

}

for （; p1 ！= 0; p1 = p1->next）

Attach（p1->data1， p1->data2， &rear）;

for （; p2 ！= 0; p2 = p2->next）

Attach（p2->data1， p2->data2， &rear）;

rear->next = NULL;

temp = front;

front = front->next;

free（temp）;

return front;

}

void PrintAns（LinkList ans） {

if（ans==NULL） {

printf（"0"）;

} else {

printf（"%dX^%d "，ans->data1，ans->data2）;

ans = ans->next;

while（ans！=NULL） {

printf（"+ %dX^%d"，ans->data1，ans->data2）;

ans = ans->next;

}

}

printf（"＼n"）;

}

int main（） {

LinkList head1， head2;

Init（& head1）;

Init（& head2）;

int m， n;

scanf（"%d"， &m）;

scanf（"%d"， &n）;

head1 = Creat（m）;

printf（"第一個多項 式："）;

PrintAns（head1）;

head2 = Creat（n）;

printf（"第二個多項式："）;

PrintAns（head2）;

printf（"相加結果："）;

PrintAns（PolyAdd（head1， head2））;

return 0;

}

在運算的過程中 切記注意節點使用的順序以及位置，g注意與流程圖的配合，搞清楚每個模塊的需求，根據功能進行函數調用，最終達到代碼的完美實現。