資訊專欄INFORMATION COLUMN
摘要：應(yīng)直接使用原序列中的結(jié)點(diǎn)，返回歸并后的帶頭結(jié)點(diǎn)的鏈表頭指針。要求分別計(jì)算兩個多項(xiàng)式的乘積與和，輸出第一項(xiàng)為乘積的系數(shù)和指數(shù)，第二行為和的系數(shù)和指數(shù)。選定了表示方法后，考慮數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。選擇鏈表在設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)的時候有系數(shù)指數(shù)和指針結(jié)構(gòu)指針。
函數(shù)題給出編譯器為 C(gcc) 的解答，編程題給出編譯器 C++(g++) 或 Python(python3) 的解答。
函數(shù)接口定義：
List Merge( List L1, List L2 );
其中List結(jié)構(gòu)定義如下：
typedef struct Node *PtrToNode;
struct Node {
ElementType Data; /* 存儲結(jié)點(diǎn)數(shù)據(jù) */
PtrToNode Next; /* 指向下一個結(jié)點(diǎn)的指針 */
};
typedef PtrToNode List; /* 定義單鏈表類型 */
L1和L2是給定的帶頭結(jié)點(diǎn)的單鏈表，其結(jié)點(diǎn)存儲的數(shù)據(jù)是遞增有序的；函數(shù)Merge要將L1和L2合并為一個非遞減的整數(shù)序列。應(yīng)直接使用原序列中的結(jié)點(diǎn)，返回歸并后的帶頭結(jié)點(diǎn)的鏈表頭指針。
裁判測試程序樣例：
#include#include typedef int ElementType; typedef struct Node *PtrToNode; struct Node { ElementType Data; PtrToNode Next; }; typedef PtrToNode List; List Read(); /* 細(xì)節(jié)在此不表 */ void Print( List L ); /* 細(xì)節(jié)在此不表；空鏈表將輸出NULL */ List Merge( List L1, List L2 ); int main() { List L1, L2, L; L1 = Read(); L2 = Read(); L = Merge(L1, L2); Print(L); Print(L1); Print(L2); return 0; } /* 你的代碼將被嵌在這里 */
輸入樣例：
3 1 3 5 5 2 4 6 8 10
輸出樣例：
1 2 3 4 5 6 8 10 NULL NULL解讀題目
題目中有兩句話：
1、L1和L2是給定的帶頭結(jié)點(diǎn)的單鏈表，其結(jié)點(diǎn)存儲的數(shù)據(jù)是遞增有序的；函數(shù)Merge要將L1和L2合并為一個非遞減的整數(shù)序列。
這里也說明了我們只需要寫一個函數(shù)Merge。實(shí)現(xiàn)思路為比較鏈表 L1 和 L2，然后以非遞減的形式輸出到一個新鏈表 L 上，最后返回鏈表 L。
2、應(yīng)直接使用原序列中的結(jié)點(diǎn)，返回歸并后的帶頭結(jié)點(diǎn)的鏈表頭指針。
第二句話中的“直接使用原序列中的結(jié)點(diǎn)”其實(shí)是要求我們把原鏈表上的結(jié)點(diǎn)一個一個摘下來，掛到新鏈表上。實(shí)現(xiàn)代碼
List Merge( List L1, List L2 ){
List p1, p2, p3, L;
// 用malloc函數(shù)申請結(jié)構(gòu)
L = (List)malloc(sizeof(struct Node));
p1 = L1->Next;
p2 = L2->Next;
p3 = L;
// 通過循環(huán)來遍歷一遍，比較L1和L2，將值小的依次加到p3
// 循環(huán)條件為 P1!=NULL && p2!=NULL
while(p1 && p2){
if(p1->Data <= p2->Data){
//把結(jié)果拷貝過去
p3->Next = p1;
p3 = p1;
// p1指針向后移一位
p1 = p1->Next;
}else{
p3->Next = p2;
p3 = p2;
p2 = p2->Next;
}
}
//將未處理完的另一個鏈表的結(jié)點(diǎn)復(fù)制過去
p3->Next = p1? p1 : p2;
L1->Next = NULL;
L2->Next = NULL;
return L;
}
提交結(jié)果
編程題
一元多項(xiàng)式的乘法與加法運(yùn)算
題目
設(shè)計(jì)函數(shù)分別求兩個一元多項(xiàng)式的乘積與和。
輸入格式:
輸入分2行，每行分別先給出多項(xiàng)式非零項(xiàng)的個數(shù)，再以指數(shù)遞降方式輸入一個多項(xiàng)式非零項(xiàng)系數(shù)和指數(shù)（絕對值均為不超過1000的整數(shù)）。數(shù)字間以空格分隔。
輸出格式:
輸出分2行，分別以指數(shù)遞降方式輸出乘積多項(xiàng)式以及和多項(xiàng)式非零項(xiàng)的系數(shù)和指數(shù)。數(shù)字間以空格分隔，但結(jié)尾不能有多余空格。零多項(xiàng)式應(yīng)輸出0 0。
輸入樣例:
4 3 4 -5 2 6 1 -2 0 3 5 20 -7 4 3 1
輸出樣例:
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1 5 20 -4 4 -5 2 9 1 -2 0解讀題目
首先我們看輸入樣例，其實(shí)表示了兩個多項(xiàng)式。第一個多項(xiàng)式非零項(xiàng)有 4 項(xiàng)：$3x^4-5x^2+6x-2$，第二哥多項(xiàng)式非零項(xiàng)有 3 項(xiàng)：$5x^{20}-7x^4+3x$。
要求分別計(jì)算兩個多項(xiàng)式的乘積與和，輸出第一項(xiàng)為乘積的系數(shù)和指數(shù)，第二行為和的系數(shù)和指數(shù)。
求解思路從以下幾個方面考慮：
多項(xiàng)式表示
表示多項(xiàng)式的關(guān)鍵信息，即非零項(xiàng)。有兩種表示方法：數(shù)組和鏈表。根據(jù)它們二者的特點(diǎn)，在這道題里項(xiàng)數(shù)是已知的，有一種比較好的實(shí)現(xiàn)方法叫動態(tài)數(shù)組。
選定了表示方法后，考慮數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。
選擇鏈表在設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)的時候有系數(shù)、指數(shù)、和指針（結(jié)構(gòu)指針）。
程序框架
程序框架搭建的大致流程如下：
int main(){
讀入多項(xiàng)式1
讀入多項(xiàng)式2
乘法運(yùn)算并輸出
加法運(yùn)算并輸出
return 0;
}
實(shí)現(xiàn)以下四步：
讀一個多項(xiàng)式
兩個多項(xiàng)式相乘
兩個多項(xiàng)式相加
多項(xiàng)式輸出
實(shí)現(xiàn)代碼C++ 版本
