最近遇到這樣一個(gè)題目,使用鏈表來實(shí)現(xiàn)兩個(gè)多項(xiàng)式的加法，剛開始覺得應(yīng)該比較簡(jiǎn)單房资，也可能是自己基礎(chǔ)不扎實(shí)吧蜕劝，這其中也是踩了很多的坑啊，最終還是成功了志膀，特此寫博客記錄一下熙宇。
一鳖擒、題目要求
使用鏈表來實(shí)現(xiàn)兩個(gè)多項(xiàng)式的加法溉浙，輸出最終相加后的多項(xiàng)式。多項(xiàng)式默認(rèn)是按指數(shù)(冪次)依次遞增的蒋荚，輸入時(shí)會(huì)依次輸入每一項(xiàng)的系數(shù)和指數(shù)戳稽，兩個(gè)多項(xiàng)式之間的數(shù)據(jù)以連續(xù)兩個(gè)0來結(jié)束一個(gè)多項(xiàng)式的輸入，最終輸出兩個(gè)多項(xiàng)式相加的多項(xiàng)式結(jié)果期升。例如：
多項(xiàng)式A: X^1 + 2 * X^2 + 3 * X^3
多項(xiàng)式B: X^1 + 2 * X^2 + 3 * X^3
輸入:
1 1
2 2
3 3
0 0
1 1
2 2
3 3
0 0
輸出:
2 * X^1 + 4 * X^2 + 6 * X^3
上面便是題目的要求,下面我們開始正式分析惊奇。
二、題目分析
我們先要解決的問題是多項(xiàng)式的存儲(chǔ)問題播赁，即它在計(jì)算機(jī)中的表現(xiàn)形式颂郎，很明顯我們只需要存儲(chǔ)了多項(xiàng)式的系數(shù)和指數(shù)即可以開始后面加法計(jì)算。這里我們又兩種存儲(chǔ)方式容为，一種是線性存儲(chǔ)乓序，另一種是鏈?zhǔn)酱鎯?chǔ)。
線性存儲(chǔ)坎背，比如我們采用數(shù)組來存儲(chǔ)這些數(shù)據(jù)替劈，理論來說是可以的，但是由于我們的多項(xiàng)式的項(xiàng)數(shù)是不確定的得滤，但數(shù)組必須在剛開始就必須
先給定一個(gè)初始的大小陨献，這個(gè)初始大小我們不好確定，分配少了懂更，沒法存儲(chǔ)全部多項(xiàng)式眨业，分配多了，會(huì)造成空間浪費(fèi)沮协，所以我們?cè)谶@里采用鏈表來存儲(chǔ)多項(xiàng)式秩霍，每次輸入一個(gè)多項(xiàng)式節(jié)點(diǎn)溯泣，我們就分配一個(gè)鏈表的節(jié)點(diǎn)，這樣便可以合理的節(jié)約空間。
接著我們分析的是具體的實(shí)現(xiàn)步驟减拭，我在這里將其分為三步:
第一步:
接收用戶控制臺(tái)的輸入搭综，并且生成對(duì)應(yīng)的兩個(gè)多項(xiàng)式的鏈表表示。
我們的每個(gè)鏈表節(jié)點(diǎn)有三個(gè)域,前兩個(gè)域是數(shù)據(jù)域,依次表示多項(xiàng)式的系數(shù)和指數(shù),第三個(gè)域是指針域,指向下一個(gè)節(jié)點(diǎn)
這里我們?yōu)榱朔奖愫罄m(xù)處理,給每個(gè)連邊增加一個(gè)頭結(jié)點(diǎn),頭結(jié)點(diǎn)的數(shù)據(jù)域內(nèi)都放-1,沒有實(shí)際意義。如下圖所示:
第二步:
依次對(duì)兩個(gè)鏈表中的數(shù)據(jù)進(jìn)行加法處理
這一步是我們的關(guān)鍵步驟悍募，下面將以圖文結(jié)合的方式來進(jìn)行解釋:
如圖中所示，我們準(zhǔn)備了A洋机、B兩個(gè)鏈表
鏈表A表示的多項(xiàng)式: 7 * X^1 + 2 * X^2 + 8 * X^5
鏈表B表示的多項(xiàng)式: 2 * X^1 + (-2 * X^2) + 2 * X^3
鏈表C是我們最終的和鏈表
這里我們按照這樣的步驟進(jìn)行處理:
1 . 我們規(guī)定三個(gè)頭指針,分別指向三個(gè)鏈表的頭,然后再規(guī)定三個(gè)移動(dòng)指針,分別指向當(dāng)前三個(gè)鏈表中正在處理的那個(gè)節(jié)點(diǎn)
2 . 我們讓A坠宴、B、C的移動(dòng)指針剛開始也處于頭指針的位置,然后,我們拿A第一個(gè)節(jié)點(diǎn)中的指數(shù)和B第一個(gè)節(jié)點(diǎn)中的指數(shù)進(jìn)行比較,這個(gè)時(shí)候有三種情況:
a情況 . A中當(dāng)前的節(jié)點(diǎn)指數(shù) < B中當(dāng)前的節(jié)點(diǎn)指數(shù) ------ 我們將A中的當(dāng)前節(jié)點(diǎn)插入C中,然后向后移動(dòng)A和C的指針(因?yàn)锳中當(dāng)前節(jié)點(diǎn)已經(jīng)處理了)
b情況 . A中當(dāng)前的節(jié)點(diǎn)指數(shù) > B中當(dāng)前的節(jié)點(diǎn)指數(shù) ------ 我們將B中的當(dāng)前節(jié)點(diǎn)插入C中,然后向后移動(dòng)B和C的指針(因?yàn)锽中當(dāng)前節(jié)點(diǎn)已經(jīng)處理了) 即圖中⑧的情況绷旗。
c情況 . A中當(dāng)前的節(jié)點(diǎn)指數(shù) > B中當(dāng)前的節(jié)點(diǎn)指數(shù) ------ 此時(shí)A和B當(dāng)前節(jié)點(diǎn)指數(shù)相同,可以進(jìn)行系數(shù)相加,這時(shí)候也會(huì)出現(xiàn)兩種情況:
情況1 . 系數(shù)之和不為0 ------ 我們此時(shí)將系數(shù)之和放到A中的當(dāng)前節(jié)點(diǎn)的系數(shù)域,然后將A中的該節(jié)點(diǎn)插入C中,然后向后移動(dòng)C的指針(記住,我們這里不是產(chǎn)生一個(gè)新的節(jié)點(diǎn),而是直接更改A的系數(shù)域,然后將A的當(dāng)前節(jié)點(diǎn)插入C中),即圖中的①和②產(chǎn)生③的過程喜鼓。
情況2 . 系數(shù)之和為0 ------ 此時(shí)我們不能將系數(shù)和為0的項(xiàng)放入鏈表C中,理論來說我們什么都不用做,但是這里有一個(gè)小問題,因?yàn)榘凑涨闆r1來看,我們?cè)谙禂?shù)和不為0時(shí)是將A節(jié)點(diǎn)直接插到C中,我們假設(shè)我們?cè)谙禂?shù)和為0后什么都不做,繼續(xù)處理A中后續(xù)節(jié)點(diǎn),后面遇到一個(gè)系數(shù)和不為0的情況,我們將后面遇到的這個(gè)系數(shù)不為0的節(jié)點(diǎn)插入C中,那其實(shí)也將前面那個(gè)系數(shù)為0的項(xiàng)也一并插入C中了,以為前面那個(gè)系數(shù)為0的節(jié)點(diǎn)和其他后面的節(jié)點(diǎn)一直保持聯(lián)系。所以我們此時(shí)必須在系數(shù)和為0時(shí),將A中的當(dāng)前節(jié)點(diǎn)刪除了衔肢。即圖中的④和⑤產(chǎn)生⑥的過程庄岖。
無論上面是情況1還是情況2,總之我們都同時(shí)處理了節(jié)點(diǎn)A和節(jié)點(diǎn)B,所以，我們還需要同時(shí)將節(jié)點(diǎn)A和B的移動(dòng)指針向后移動(dòng)角骤。
這里還有一個(gè)情況,我們的A隅忿、B鏈表可能長(zhǎng)度不是一致的，那么就有可能其中一個(gè)鏈表的移動(dòng)指針已經(jīng)移動(dòng)到了末尾,那么此時(shí),我們就不需要繼續(xù)移動(dòng)了,我們只需要將另一個(gè)鏈表中未處理的數(shù)據(jù)直接接在當(dāng)前已經(jīng)生產(chǎn)的C鏈表的后面即可邦尊。
第三步:
打印輸出最終計(jì)算所得的和鏈表表達(dá)式
三背桐、代碼實(shí)現(xiàn)
經(jīng)過上面的分析,我們這里分別采用C語言和Java來實(shí)現(xiàn)上述思路,代碼中有詳細(xì)的注釋,下面只進(jìn)行簡(jiǎn)單解釋。
C語言實(shí)現(xiàn):
#include<stdio.h>
#include<malloc.h>
typedef struct node{
float coef;
int expn;
node *next;
}Lnode, * Dxs;
Dxs create();
Dxs add_dxs(Dxs firsta, Dxs firstb);
void printDxs(Dxs h);
void deleteNode(Dxs h, Dxs p);
int main(){
Dxs ha, hb, hc;
printf("請(qǐng)依次輸入第一個(gè)多項(xiàng)式的系數(shù)和指數(shù)\n");
ha = create();
printf("請(qǐng)依次輸入第二個(gè)多項(xiàng)式的系數(shù)和指數(shù)\n");
hb = create();
printf("輸入的第一個(gè)多項(xiàng)式是: ");
printDxs(ha->next);
printf("輸入的第二個(gè)多項(xiàng)式是: ");
printDxs(hb->next);
hc = add_dxs(ha, hb);
printf("兩個(gè)多項(xiàng)式的和為: ");
printDxs(hc->next);
return 0;
}
//創(chuàng)建鏈表(讀入數(shù)據(jù)以 0 0 結(jié)束)
Dxs create(){
float coef;
int expn;
Dxs first, qa, s;
first = (Dxs)malloc(sizeof(Lnode));
first->coef = -1;
first->expn = -1;
first->next = NULL;
qa = first;
while(1){
scanf("%f", &coef);
scanf("%d", &expn);
if(coef == 0 && expn == 0){
break;
}
s = (Dxs)malloc(sizeof(Lnode));
s->coef = coef;
s->expn = expn;
s->next = NULL;
qa->next = s;
qa = s;
}
return first;
}
//鏈表相加
Dxs add_dxs(Dxs firsta, Dxs firstb){
Dxs firstc, ha, hb, pc, s;
int a, b;
float sum;
firstc = (Dxs)malloc(sizeof(Lnode));
firstc->coef = -1;
firstc->expn = -1;
firstc->next = NULL;
pc = firstc;
ha = firsta->next;
hb = firstb->next;
while(ha!= NULL && hb != NULL){
a = ha->expn;
b = hb->expn;
if(a < b){
//將a加入c中,移動(dòng)a和c的指針
pc->next = ha;
pc = pc->next;
ha = ha->next;
}else if(a > b){
//將b加入c中,移動(dòng)b和c的指針
pc->next = hb;
pc = pc->next;
hb = hb->next;
}else{
sum = ha->coef + hb->coef;
if(sum != 0.0){
//將和加入a中,再將a加入c中,移動(dòng)c的指針
ha->coef = sum;
pc->next = ha;
pc = pc->next;
}else{
//查找刪除A中系數(shù)之和為0的那個(gè)節(jié)點(diǎn)
s = firsta;
while(s != ha){
s = s->next;
}
s->next = ha->next;
}
//ab已經(jīng)處理完成,同時(shí)后移一位
ha = ha->next;
hb = hb->next;
}
}
//將剩余部分加入c后面
if(ha != NULL){
pc->next = ha;
}
if(hb != NULL){
pc->next = hb;
}
return firstc;
}
//遍歷顯示鏈表
void printDxs(Dxs h){
while(h != NULL){
printf("%0.2f*X^%d + ", h->coef, h->expn);
h=h->next;
}
printf("\n");
}
Java語言描述:
package cn.codekong;
import java.util.Scanner;
/**
* 鏈表類
* @author szh
*
*/
public class MyLink {
/**
* 鏈表節(jié)點(diǎn)類
* @author szh
*
*/
class Node{
//多項(xiàng)式的系數(shù)
private float coef;
//多項(xiàng)式的指數(shù)
private int expn;
//指向下級(jí)節(jié)點(diǎn)
public Node next = null;
public Node(float coef, int expn){
this.coef = coef;
this.expn = expn;
}
}
/**
* 創(chuàng)建鏈表類
* 從從控制臺(tái)不斷讀入數(shù)據(jù)蝉揍，以(0 0)結(jié)束
* @return 創(chuàng)建好鏈表的第一個(gè)節(jié)點(diǎn)
*/
public Node createLink(){
//存取從控制臺(tái)讀到的系數(shù)和指數(shù)
float coef = 0.0f;
int expn = 0;
//頭尾節(jié)點(diǎn)(尾節(jié)點(diǎn)方便插入)
Node head, tail;
head= new Node(-1, -1);
head.next = null;
tail = head;
Scanner scanner = new Scanner(System.in);
while(true){
String res = scanner.nextLine();
//以空格分割一行中的字符串
String[] resArray = res.split("\\s+");
coef = Float.parseFloat(resArray[0]);
expn = Integer.parseInt(resArray[1]);
if(coef == 0 && expn == 0.0f){
break;
}
Node node = new Node(coef, expn);
node.next = null;
tail.next = node;
tail = tail.next;
}
return head;
}
/**
* 打印鏈表
* @param head 鏈表首節(jié)點(diǎn)
*/
public void printLink(Node head){
while(head != null){
System.out.format("%.2f*X^%d + ", head.coef, head.expn);
head = head.next;
}
System.out.println();
}
/**
* 計(jì)算兩個(gè)鏈表的和
* @param nodeA
* @param nodeB
* @return 最終和的鏈表
*/
public Node addLink(Node nodeA, Node nodeB){
Node nodeC = new Node(-1, -1);
nodeC.next = null;
//始終指向鏈表的當(dāng)前需要處理的節(jié)點(diǎn)(剛開始要除去開頭的(-1,-1)節(jié)點(diǎn))
Node pA = nodeA.next, pB = nodeB.next, pC = nodeC;
//當(dāng)前指向的兩個(gè)鏈表的指數(shù)
int valueAExpn = 0, valueBExpn = 0;
while(pA != null && pB != null){
valueAExpn = pA.expn;
valueBExpn = pB.expn;
if(valueAExpn < valueBExpn){
//將A中的該節(jié)點(diǎn)加入C中, 同時(shí)移動(dòng)A和C的指針指向下個(gè)元素
pC.next = pA;
pC = pC.next;
pA = pA.next;
}else if(valueAExpn > valueBExpn){
//將B中的該節(jié)點(diǎn)加入C中,同時(shí)移動(dòng)B和C的指針指向下個(gè)元素
pC.next = pB;
pC = pC.next;
pB = pB.next;
}else{
//兩節(jié)點(diǎn)指數(shù)相同
//現(xiàn)將系數(shù)相加放到A節(jié)點(diǎn)的系數(shù)中,然后將A節(jié)點(diǎn)加入C中
float sum = pA.coef + pB.coef;
if(sum != 0.0f){
//系數(shù)和不為0,將A節(jié)點(diǎn)的系數(shù)改變?yōu)閟um,然后將A節(jié)點(diǎn)加入C中
pA.coef = sum;
pC.next = pA;
pC = pC.next;
}else{
//系數(shù)和為0,必須將A鏈表中的該節(jié)點(diǎn)從鏈表中刪除掉,如果只移動(dòng)指針,會(huì)在輸出時(shí)也輸出該項(xiàng)
//在整個(gè)A鏈表中依次查找,必須找到要?jiǎng)h除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)才能將其刪除
Node s = nodeA;
while(s != pA){
s = s.next;
}
//刪除該節(jié)點(diǎn)
s.next = pA.next;
}
//對(duì)于系數(shù)相同的情況,A和B節(jié)點(diǎn)指針都往后移動(dòng)
pA = pA.next;
pB = pB.next;
}
}
if(pA != null){
pC.next = pA;
}
if(pB != null){
pC.next = pB;
}
return nodeC;
}
}
package cn.codekong;
import cn.codekong.MyLink.Node;
public class MyTest {
public static void main(String[] args) {
MyLink myLink = new MyLink();
System.out.println("請(qǐng)依次輸入第一個(gè)多項(xiàng)式的系數(shù)和指數(shù)");
Node nodea = myLink.createLink();
System.out.println("請(qǐng)依次輸入第二個(gè)多項(xiàng)式的系數(shù)和指數(shù)");
Node nodeb = myLink.createLink();
System.out.println("輸入的第一個(gè)多項(xiàng)式是: ");
myLink.printLink(nodea.next);
System.out.println("輸入的第二個(gè)多項(xiàng)式是: ");
myLink.printLink(nodeb.next);
Node nodec = myLink.addLink(nodea, nodeb);
System.out.println("兩個(gè)多項(xiàng)式的和為: ");
myLink.printLink(nodec.next);
}
}
其實(shí)Java的鏈表實(shí)現(xiàn)和C語言很類似,只是C語言中的節(jié)點(diǎn)是定義結(jié)構(gòu)體,而此處是使用一個(gè)內(nèi)部類來定義鏈表的每個(gè)節(jié)點(diǎn),C語言中的指針其實(shí)就是Java中的引用,我們生命的Java對(duì)象是存儲(chǔ)在堆中,而對(duì)象的引用則是存儲(chǔ)在堆棧中链峭。
上面為了保持Java和C在控制臺(tái)輸入的一致性,我通過使用Scanner讀入一行,然后通過正則表達(dá)式分割出系數(shù)和指數(shù)進(jìn)行后續(xù)處理。
四又沾、代碼運(yùn)行驗(yàn)證
C語言運(yùn)行結(jié)果：
Java運(yùn)行結(jié)果：
