資料結構與演算法----數學應用之一元多項式
摘要：
PS：上一篇說了線性表的順序表和鏈式表表達，該片就寫一下應用到現實數學中去，一元多項式的加減。
一元多項式我們在本子上可以說是手到拈來，但是在電腦上用語言敲出來，估計這會讓很多人頭疼，比如下面的多項式
y1 = 9x^1 + 4x^3 + 6x^4
y2 = 2x^3 + 4x^...
PS：上一篇說了線性表的順序表和鏈式表表達，該片就寫一下應用到現實數學中去，一元多項式的加減。
一元多項式我們在本子上可以說是手到拈來，但是在電腦上用語言敲出來，估計這會讓很多人頭疼，比如下面的多項式
y1 = 9x^1 + 4x^3 + 6x^4
y2 = 2x^3 + 4x^4 + 3x^7 + 3x^8
yz = y1 + y2 ；
效果圖
思路：
- 建立一個結構體，裡面只存連個數，一個是係數data，一個是次冪，至於x就不用存了，只在列印的時候寫上就OK了，
- 然後寫插入操作，注意一定要是有序的，方便在後期相加
- 兩個多項式相加就是合併，我們可以按照順序兩兩比較，先拿y1的第一個數和y2第一個比較，如果y1>y2,則把y2新增到yz，相反之，如果y1=y2則相加係數，按照y1（也可y2）加入yz，等全都比較過後，如果y1（y2）還有項的話，就把剩下的全都載入到yz中，其實就是直接把next指向y1（y2）即可。
1：結構體
定義一個結構體型別
在SlinkOnez呼叫變數是，都是
L->data;L->next;的形式
typedef struct SlinkOne {
int data;
int cimi;
struct SlinkOne *next;
} SlinkOne, *SlinkOnez;
2：初始化
/**c
* 初始化
* */
SlinkOnez initLink() {
SlinkOnez L = (SlinkOnez) malloc(sizeof(SlinkOne));
if (!L) {
exit(-1);
}
L->next = NULL;
return L;
}
3：插入操作
/**
* 插入
* */
int insertLink(SlinkOnez &L, int pos, int e, int cimi) {
SlinkOnez p = L;
int i = 0;
while (p && i < pos-1) {
p = p->next;
i++;
}
if (!p || i > pos-1) {
printf("單鏈表未被建立\n");
return -1;
}
//建立一個新的結點，並賦值
SlinkOnez s = (SlinkOnez) malloc(sizeof(SlinkOne));
s->data = e;
s->cimi = cimi;
s->next = p->next;
p->next = s;
printf("插入成功\n");
return 0;
}
4：列印全部資料
注意：我在這裡面加入了幾個判斷，一個是當p->next ==NULL時，後面的加號就不要了，如果次冪==0的話那就只打印係數，當然如果係數==0，那就不列印，下方並未給出。
/**
* 列印全部資料
* */
void printL(SlinkOnez L) {
SlinkOnez p = L->next;
if (!p) {
printf("單鏈表不成立或者為NULL");
return;
}
while (p) {
if (p->next == NULL) {
printf("%dX^%d", p->data, p->cimi);
} else {
if (p->cimi == 0) {
printf("%d + ", p->data);
} else {
printf("%dX^%d + ", p->data, p->cimi);
}
}
p = p->next;
}
printf("\n");
}
5：合併（重點）
注意：pz = p1;//往下走一個，這句話其實就相當於 pz = pz->next;
下面的全部程式碼實現都是在我上面說的思路上一一對應的，只要有思路，問題就已經解決了一半了，
/**
* 合併
* */
SlinkOnez mergeLink(SlinkOnez &Lz, SlinkOnez &L1, SlinkOnez &L2) {
Lz->next=NULL;
SlinkOnez pz = Lz;
SlinkOnez p1 = L1->next;
SlinkOnez p2 = L2->next;
while (p1 && p2) {
if (p1->cimi < p2->cimi) {
pz->next = p1;
pz = p1;//往下走一個
p1 = p1->next;
} else if (p1->cimi > p2->cimi) {
pz->next = p2;
pz = p2;//往下走一個
p2 = p2->next;
}else{
if(0 !=(p1->data + p2->data)){
p1->data = (p1->data+p2->data);//注意此處，重點，不能寫成pz->data，否則會把當前p的值給替換掉，而不是賦值給下一個指標的值
pz->next = p1;
pz = p1;//往下走一個
}
p1=p1->next;
p2=p2->next;
}
}
if (p1!=NULL){
pz->next=p1;
}
if (p2!=NULL){
pz->next=p2;
}
return Lz;
}
6：使用
int main() {
//第一個多項式
SlinkOnez L;
L = initLink();
insertLink(L, 1, 9, 1);
insertLink(L, 2, 4, 3);
insertLink(L, 3, 6, 4);
printL(L);
//第二個多項式
SlinkOnez L2;
L2 = initLink();
insertLink(L2, 1, 2, 3);
insertLink(L2, 2, 4, 4);
insertLink(L2, 3, 3, 7);
insertLink(L2, 4, 3, 8);
printL(L2);
//合併後多項式
SlinkOnez L3;
L3=initLink();
L3=mergeLink(L3,L,L2);
printL(L3);
return 0;
}
完