杜金庭 唐海川

一元多項(xiàng)式的表示在計(jì)算機(jī)內(nèi)可以用鏈表來(lái)表示，為了節(jié)省存儲(chǔ)空間，只存儲(chǔ)多項(xiàng)式中系數(shù)非零的項(xiàng)。 鏈表中的每一個(gè)結(jié)點(diǎn)存放多項(xiàng)式的一個(gè)系數(shù)非零項(xiàng)，它包含三個(gè)域，分別存放該項(xiàng)的系數(shù)、指數(shù)以及指向下一個(gè)多項(xiàng)式項(xiàng)結(jié)點(diǎn)的指針。對(duì)于如何利用鏈表將兩個(gè)一元多項(xiàng)式分別存入兩個(gè)鏈表中，通過(guò)相加將鏈表合并后并輸出合成后的新的一元多項(xiàng)式。在運(yùn)行的過(guò)程中主要所運(yùn)用的就是利用鏈表的data域相加完成鏈表的加法運(yùn)算，輸出相加之后的新一元多項(xiàng)式。

數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)有兩種：順序儲(chǔ)存結(jié)構(gòu)和鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)，而我們所做的一元多項(xiàng)式的相加及其表示，就是我們要把算法想象成是一種抽象的運(yùn)行算法，將一元多項(xiàng)式抽象的想象成一個(gè)新的線性表。

程序流程如下：

使用typedef 和 struct 定義的新類型名稱，其用途與內(nèi)建類型的名稱相同，可以用來(lái)：聲明和初始化結(jié)構(gòu)體變量;創(chuàng)建并根據(jù)自己的意愿初始化結(jié)構(gòu)數(shù)組，用鏈表表示多項(xiàng)式時(shí)，每個(gè)鏈表結(jié)點(diǎn)儲(chǔ)存多項(xiàng)式中的一個(gè)非零項(xiàng)，包括系數(shù)（data1）和指數(shù)（data2）兩個(gè)數(shù)據(jù)域及一個(gè)指針域（next）。對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)定義為：

typedef struct LNode

{

int data1;//系數(shù)

int data2;//指數(shù)

struct LNode *next;//指向下一節(jié)點(diǎn)的指針

}LNode， *LinkList;

之后需要初始化鏈表：因?yàn)閷?shí)現(xiàn)目的過(guò)程需要使用鏈表進(jìn)行算法的實(shí)現(xiàn)，所以開始時(shí)需要先創(chuàng)建兩個(gè)有頭結(jié)點(diǎn)的空鏈表，因?yàn)槌跏蓟逆湵頁(yè)碛袃蓚€(gè)data域（data1，data2）和一個(gè)指針域（next），我們要利用后插法建立單鏈表，將“X”的系數(shù)放入data1中，冪放入data2中，這樣指針域next就可以存放下一個(gè)節(jié)點(diǎn)的地址，初始化函數(shù)void Init（LinkList *L）是一個(gè)無(wú)參函數(shù)，這樣就能成功實(shí)現(xiàn)鏈表的初始化。

在接下來(lái)的過(guò)程中，所用到的輸入函數(shù)LinkList Creat（int n）是一個(gè)無(wú)返回值的有參函數(shù)，用于輸入系數(shù)和指數(shù)。然后通過(guò)為“s”申請(qǐng)一塊大小為（sizeof（LinkList））的內(nèi)存，生成一個(gè)新的節(jié)點(diǎn)“*s”，之后就可以輸入多項(xiàng)式當(dāng)前項(xiàng)的系數(shù)和指數(shù)然后付給新結(jié)點(diǎn)*s的數(shù)據(jù)域。

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

當(dāng)p1的指數(shù)大于p2的指數(shù)時(shí)，函數(shù)返回1，當(dāng)p1的指數(shù)小于p2的指數(shù)時(shí)，返回-1，當(dāng)p1的指數(shù)等于p2的指數(shù)時(shí)，返回0.

連接函數(shù)void Attach（int c， int d， LinkList *pRear）

該連接函數(shù)用于把得到的結(jié)果多項(xiàng)式一項(xiàng)一項(xiàng)的接到用front記錄結(jié)果多項(xiàng)式鏈表的頭結(jié)點(diǎn)的后面，為“p”申請(qǐng)一個(gè)新的節(jié)點(diǎn)，“p->date1/date2=c/d”表示對(duì)“p”這一鏈表?yè)碛袃蓚€(gè)data域（data1，data2）進(jìn)行賦值，將其當(dāng)前所指向的新結(jié)點(diǎn)插入到這一時(shí)刻多項(xiàng)式所表達(dá)的尾部。

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;

}

多項(xiàng)式相加函數(shù)LinkList PolyAdd（LinkList p1， LinkList p2）

該函數(shù)作為代碼核心函數(shù)，作用是將兩個(gè)一元多項(xiàng)式中指數(shù)相同的每一項(xiàng)加在一起，并返回結(jié)果多項(xiàng)式的首地址。首先利用“front”申請(qǐng)新的節(jié)點(diǎn)，將結(jié)果多項(xiàng)式鏈表的頭節(jié)點(diǎn)用前面的“front”來(lái)進(jìn)行記錄，。在運(yùn)算的過(guò)程中，就會(huì)出現(xiàn)兩個(gè)多項(xiàng)式可能都有非零項(xiàng)需要進(jìn)行處理，如果說(shuō)“p1”的指數(shù)大于“p2”的指數(shù)，那么“p2”的系數(shù)和指數(shù)都將會(huì)存入多項(xiàng)式鏈表中，存儲(chǔ)完成后，“p2”將會(huì)繼續(xù)指向下一節(jié)點(diǎn)，

由此可知，對(duì)于“p1”和“p2”的互相比較，為的就是哪一個(gè)先進(jìn)行存入和指向下一步，同理，如果“p1”的指數(shù)小于“p2”的指數(shù)，那么“p1”的系數(shù)和指數(shù)都將會(huì)存入多項(xiàng)式鏈表中，存儲(chǔ)完成后，“p1”將會(huì)繼續(xù)指向下一節(jié)點(diǎn)，當(dāng)然也不能忘記 “p1”和“p2”的指數(shù)相同這種情況，那么和剛剛的兩種就會(huì)有些不同，他們會(huì)將自身相同的系數(shù)相加，相加完成之后生成的系數(shù)和“p1”的指數(shù)存入多項(xiàng)式鏈表，同時(shí)“p1”和“p2”指向下一個(gè)節(jié)點(diǎn)。

節(jié)點(diǎn)的插入也會(huì)有順序之分，當(dāng)“p1”和“p2”兩者中其中有一方已經(jīng)完全的插入了多項(xiàng)式鏈表，那么緊接其后的就是另一方全部的插入多項(xiàng)式鏈表里，插入完成后讓上一結(jié)構(gòu)內(nèi)的“front”去指向結(jié)果多項(xiàng)式的第一個(gè)非零項(xiàng)，這樣就會(huì)將釋放一個(gè)臨時(shí)空表頭結(jié)點(diǎn)。

void PrintAns（LinkList ans）這部分的結(jié)構(gòu)體，目的是為了將結(jié)果進(jìn)行打印，將鏈表中第一個(gè)節(jié)點(diǎn)輸出并指向下一節(jié)點(diǎn)，輸出后開始對(duì)后續(xù)的節(jié)點(diǎn)依次進(jìn)行輸出，如果鏈表結(jié)束，輸出的就是“0”。大部分的結(jié)構(gòu)的進(jìn)程或者注釋都進(jìn)行了很詳細(xì)的注釋，接下來(lái)就是對(duì)于我們這個(gè)一元多項(xiàng)式的相加進(jìn)行測(cè)驗(yàn)，首先我們要做的就是屬于第一個(gè) 多項(xiàng)式有幾項(xiàng)，第二個(gè)多項(xiàng)式有幾項(xiàng)，輸入的第一個(gè)多項(xiàng)式要按照系數(shù)指數(shù)的順序進(jìn)行輸入，同理，第二個(gè)多項(xiàng)式的順序與第一個(gè)多項(xiàng)式的順序相同，當(dāng)然輸入的項(xiàng)式的多少，取決于你要測(cè)試的項(xiàng)數(shù)，所后進(jìn)行調(diào)式，產(chǎn)生最終的運(yùn)算結(jié)果。

一元多項(xiàng)式的相加是對(duì)創(chuàng)建鏈表使用鏈表最簡(jiǎn)單的一種運(yùn)用，大多數(shù)函數(shù)的使用更需要注重的是函數(shù)與函數(shù)之間的相互配合，下面所表述的是對(duì)實(shí)現(xiàn)一元多項(xiàng)式相加的全部代碼：

代碼主體：

#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（"第一個(gè)多項(xiàng) 式："）;

PrintAns（head1）;

head2 = Creat（n）;

printf（"第二個(gè)多項(xiàng)式："）;

PrintAns（head2）;

printf（"相加結(jié)果："）;

PrintAns（PolyAdd（head1， head2））;

return 0;

}

在運(yùn)算的過(guò)程中 切記注意節(jié)點(diǎn)使用的順序以及位置，g注意與流程圖的配合，搞清楚每個(gè)模塊的需求，根據(jù)功能進(jìn)行函數(shù)調(diào)用，最終達(dá)到代碼的完美實(shí)現(xiàn)。