閱讀以下說明和 C 函數(shù),填補代碼中的空缺,將解答填入答題紙的對應(yīng)欄內(nèi)。
【說明】
函數(shù) Combine(LinkList La,LinkList Lb)的功能是:將元素呈遞減排列的兩個含頭結(jié) 點單鏈表合并為元素值呈遞增(或非遞減)方式排列的單鏈表,并返回合并所得單鏈表 的頭指針。例如,元素遞減排列的單鏈表 La 和 Lb 如圖 4-1 所示,合并所得的單鏈表如圖 4-2 所示。
圖 4-1 合并前的兩個鏈表示意圖
圖 4-2 合并后所得鏈表示意圖
設(shè)鏈表結(jié)點類型定義如下:
typedef struct Node{
int data;
struct Node *next;
}Node ,*LinkList;
【C 函數(shù)】
LinkList Combine(LinkList La ,LinkList Lb)
{ //La 和 Lb 為含頭結(jié)點且元素呈遞減排列的單鏈表的頭指針
//函數(shù)返回值是將 La 和 Lb 合并所得單鏈表的頭指針
//且合并所得鏈表的元素值呈遞增(或非遞減)方式排列
(1) Lc ,tp ,pa ,pb;; //Lc 為結(jié)果鏈表的頭指針 ,其他為臨時指針
if (!La) return NULL;
pa = La->next; //pa 指向 La 鏈表的第一個元素結(jié)點
if (!Lb) return NULL;
pb = Lb->next; //pb 指向 Lb 鏈表的第一個元素結(jié)點
Lc = La; //取 La 鏈表的頭結(jié)點為合并所得鏈表的頭結(jié)點
Lc->next = NULL;
while ( (2) ){ //pa 和 pb 所指結(jié)點均存在(即兩個鏈表都沒有到達(dá)表尾)
//令tp指向 pa 和 pb 所指結(jié)點中的較大者
if (pa->data > pb->data) {
tp = pa; pa = pa->next;
}
else{
tp = pb; pb = pb->next;
}
(3) = Lc->next; //tp 所指結(jié)點插入 Lc 鏈表的頭結(jié)點之后
Lc->next = (4) ;
}
tp = (pa)? pa : pb; //設(shè)置 tp 為剩余結(jié)點所形成鏈表的頭指針
//將剩余的結(jié)點合并入結(jié)果鏈表中, pa 作為臨時指針使用
while (tp) {
pa = tp->next;
tp->next = Lc->next;
Lc->next = tp;
(5) ;
}
return Lc;
}