浙江大學-數據結構-作業-線性結構1 兩個有序鏈表序列的合併(補充）

www.cnblogs.com

看了挺多版本的，要麼不全，要麼不是c語言寫的，大神請無視，書的話，最近發現兩本

c programming a modern approach, writing solid code bug free c program.

02-線性結構1 兩個有序鏈表序列的合併（15 分）

本題要求實現一個函數，將兩個鏈表表示的遞增整數序列合併為一個非遞減的整數序列。

函數介面定義：

List Merge( List L1, List L2 );

其中List結構定義如下：

typedef struct Node *PtrToNode;

struct Node {

L1和L2是給定的帶頭結點的單鏈表，其結點存儲的數據是遞增有序的；函數Merge要將L1和L2合併為一個非遞減的整數序列。應直接使用原序列中的結點，返回歸併後的帶頭結點的鏈表頭指針。

裁判測試程序樣例：

#include <stdio.h>

#include <stdlib.h>

typedef int ElementType;

typedef struct Node *PtrToNode;

struct Node {

ElementType Data;

PtrToNode Next;

};

typedef PtrToNode List;

List Read(); /* 細節在此不表 */

void Print( List L ); /* 細節在此不表；空鏈表將輸出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

c語言中&稱為地址運算符，在c語言中用於使一個指針指向一個對象，因此，如果x是某種特定類型的一個變數，則表達式&x就是指向該變數的指針。

看了一下書上寫的，我先原封不動的寫出來

void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc){ pa = La->next; pb = Lb->next; Lc = pc = pa; while(pa&&pb){ if(pa->data<=pb->data){ pc->next = pa; pc = pa; pa = pa->next; } else{ pc->next = pb; pc = pb; pb = pb->next; } } pc->next = pa?pa:pb; free(pb);}

這段代碼我看到這裡是懵逼的，主要是有幾個細節不對或者我沒看明白，1. pa, pb, pc憑空出現，這個還好解釋，可能課本忘記聲明了 2. 指針指來指去我有點亂。

但後來查了一下書，如果兩個變數都是指針，那麼相互賦值，相當於這兩個指針同時指向一個地方。

這裡說的很清楚，然後函數裡面傳進去指針參數

但說實話，這個指針的指向以及如何將兩個鏈表連接起來，我還是不能完全搞明白。。。哪位大神，能在草稿紙上幫我畫一下鏈表模擬一下嗎？pc->next = pa; pc = pa; pa = pa->next;

特別是這幾句話。。。