第3章順序表的鏈式存盤

一、鏈式存盤
二、單鏈表
- 2.1 單鏈表的基本概念及描述
- 2.2 單鏈表的實作
  - 2.2.1 單鏈表的存盤結構
  - 2.2.2 單鏈表的插入操作（演算法）
  - 2.2.3 單鏈表的洗掉操作（演算法）
三、帶頭結點的單鏈表
- 3.1 帶頭結點的單鏈表的基本概念及描述
- 3.2 帶頭結點的單鏈表的實作
  - 3.2.1 帶頭結點的單鏈表的存盤結構
  - 3.2.2 帶頭結點的單鏈表的插入（演算法）
  - 3.2.3 帶頭結點的單鏈表的洗掉（演算法）
四、回圈單鏈表
- 4.1 回圈單鏈表的基本概念及描述
- 4.2 回圈單鏈表的實作
  - 4.2.1 回圈單鏈表的存盤結構
五、雙鏈表
- 5.1 雙鏈表的基本概念及描述
- 5.2 雙鏈表的實作
  - 5.2.1 雙鏈表的存盤結構
六、鏈式堆疊
- 6.1 鏈式堆疊的基本概念及描述
- 6.2 鏈式堆疊的實作
  - 6.2.1 鏈式堆疊的存盤結構
七、鏈式佇列
- 7.1 鏈式佇列的基本概念及描述
- 7.2 鏈式佇列的實作
  - 7.2.1 鏈式佇列的存盤結構
八、演算法設計題
- 8.1 求單鏈表中結點個數（演算法）
- 8.2 求帶頭結點的單鏈表中的結點個數（演算法）
- 8.3 在單鏈表中的某個結點前插一個新結點（演算法）
- 8.4 判斷單鏈表的各個結點是否有序（演算法）
- 8.5 逆轉一個單鏈表（演算法）
- 8.6 拆分結點值為自然數的單鏈表，原鏈表保留值為偶數的結點，新鏈表存放值為奇數的結點（演算法）
- 8.7 在有序單鏈表中洗掉值大于 x 而小于 y 的結點（演算法）
九、錯題集

一、鏈式存盤

解決問題：對于線性結構，使用順序存盤，需要足夠大的連續存盤區域
鏈式存盤：結點除了存放資訊，并且附設指標，用指標體現結點之間的邏輯關系
注：\(c\)語言的動態分配函式\(malloc()\)和\(free()\)分別實作記憶體空間的動態分配和回收，所以不必知道某個結點的具體地址
注：鏈式存盤中，必須有一個指標指向第一個結點的存盤位置，一般為\(head\)標示
順序存盤和鏈式存盤的區別：順序存盤更適合查詢量大的程式設計；鏈式存盤更適合需要頻繁插入和洗掉的程式

二、單鏈表

2.1 單鏈表的基本概念及描述

單鏈表結點構造：兩個域，一個存放資料資訊的\(info\)域；另一個指向該結點的后繼結點的\(next\)域

2.2 單鏈表的實作

單鏈表的常用操作：
1. 建立一個空的單鏈表
2. 輸出單鏈表中各個結點的值
3. 在單鏈表中查找第\(i\)個結點

2.2.1 單鏈表的存盤結構

typedef int datatype;
typedef struct link_node {
    datatype info;
    struct link_node *next;
} node;

2.2.2 單鏈表的插入操作（演算法）

演算法步驟（插入結點為\(p\)，插入到結點\(q\)后面）：
1. 通過 find(head,i) 查找\(q\)結點，查不到列印報錯資訊
2. 給插入結點\(p\)分配空間，并設定資訊
3. 如果在單鏈表的最前面插入新結點，讓單鏈表的首指標指向新插入的結點
  1. p->next = head;
  2. head = p;
4. 如果在單鏈表中間插入新結點：
  1. p->next = q->next;
  2. q->next=p;

typedef int datatype;
typedef struct link_node {
    datatype info;
    struct link_node *next;
} node;

node *insert(node *head, datatype x, int i) {
    node *p, *q;
    q = find(head, i); // 查找第i個結點
    if (!q && i != 0) {
        printf("\n找不到第%d個結點，不能插入%d！", i, x);
    } else {
        p = (node *) malloc(sizeof(node)); // 分配空間
        p->info = x; // 設定新結點
        if (i == 0) // 插入的結點作為單鏈表的第一個結點
        {
            p->next = head;
            head = p;
        } else {
            p->next = q->next; // 后插
            q->next = p;
        }
    }
    return head;
}

2.2.3 單鏈表的洗掉操作（演算法）

演算法步驟（被洗掉結點\(q\)，被洗掉結點前一個結點\(pre\)）
1. 判斷鏈表是否為空
2. 回圈查找被洗掉結點\(q\)，并且設定一個結點\(pre\)標示被洗掉結點的前一個結點
3. 如果洗掉結點為第一個結點
  1. head = head->next;
  2. free(p)
4. 如果洗掉結點為其他結點
  1. pre->next = q->next;
  2. free(p)

typedef int datatype;
typedef struct link_node {
    datatype info;
    struct link_node *next;
} node;

node *dele(node *head, datatype x) {
    node *pre = NULL, *p;
    if (!head) {
        printf("單鏈表是空的");
        return head;
    }
    p = head;
    while (p && p->info != x) // 尋找被洗掉結點p
    {
        pre = p; // pre指向p的前驅結點
        p = p->next;
    }
    if (p) {
        if (!pre) // 被洗掉結點沒有上一個結點，則是要洗掉的是第一個結點
        {
            head = head->next;
        } else {
            pre->next = p->next;
        }
        free(p)
    }
    return head;
}

三、帶頭結點的單鏈表

3.1 帶頭結點的單鏈表的基本概念及描述

頭結點的作用：單鏈表的插入和洗掉需要對空的單鏈表進行特殊處理，因此可以設定 \(head\) 指標指向一個永遠不會被洗掉的結點——頭結點
注：\(head\) 指示的是所謂的頭結點，它不是實際結點，第一個實際結點應該是 head->next 指示的

3.2 帶頭結點的單鏈表的實作

帶頭結點的單鏈表的常用操作：
1. 建立一個空的帶頭結點的單鏈表
2. 輸出帶頭結點的單鏈表中各個結點的值
3. 在帶頭結點的單鏈表中查找第 \(i\) 個結點

3.2.1 帶頭結點的單鏈表的存盤結構

typedef int datatype;
typedef struct link_node {
    datatype info;
    struct link_node *next;
} node;

3.2.2 帶頭結點的單鏈表的插入（演算法）

演算法步驟（ \(p\) 為插入結點，\(q\) 為插入前一個結點）：
1. 通過 find(head,i) 查找帶頭結點的單鏈表中的第 \(i\) 個結點（ \(i=0\) 表示新結點插入在頭結點之后）
2. 如果沒找到結點 \(q\)，列印報錯資訊
3. 如果在非空的帶頭結點的單鏈表最前面插入一個新結點
  1. p->next = q->next;
  2. q->next = p;
4. 如果在非空的帶頭結點的單鏈表的內部插入一個新結點
  1. p->next = q->next;
  2. q->next = p;

typedef int datatype;
typedef struct link_node {
    datatype info;
    struct link_node *next;
} node;

node *insert(node *head, datatype x, int i) {
    node *p, *q;

    q = find(head, i); // 查找帶頭結點的單鏈表中的第 i 個結點，i=0 時表示新結點插入在頭結點之后

    if (!q) // 沒有找到
    {
        printf("\n帶頭結點的單鏈表中不存在第%d個結點！不能插入%d！", i, x);
        return head;
    }

    p = (node *) malloc(sizeof(node)); // 為準備插入的新結點分配空間
    p->info = x; // 為新結點設定值
    p->next = q->next;
    q->next = q; // i=0 時，本陳述句等價于 head->next=p
    return head;
}

3.2.3 帶頭結點的單鏈表的洗掉（演算法）

演算法步驟（被洗掉結點為 \(q\)，被洗掉結點的前一個結點為 \(pre\)）：
1. 設定 \(pre\) 指向頭結點
2. \(q\) 從帶頭結點的單鏈表的第一個實際結點開始回圈尋找值為 \(x\) 的結點
3. 洗掉帶頭結點的單鏈表的第一個實際結點：
  1. pre->next = q->next;
  2. free(q)
4. 洗掉帶頭結點的單鏈表的內部結點：
  1. pre->next = q->next;
  2. free(q)

typedef int datatype;
typedef struct link_node {
    datatype info;
    struct link_node *next;
} node;

node *dele(node *head, datatype x) {
    node *pre = head, *q; // pre 指向頭結點

    q = head->next; // q 從帶頭結點的單鏈表的第一個實際結點開始找值為 x 的結點
    while (q && q->info != x) // 回圈查找值為 x 的結點
    {
        pre = q; // pre 指向 q 的前驅
        q = q->next;
    }

    if (q) {
        pre->next = q->next; // 洗掉
        free(q); // 釋放記憶體空間
    }
    return head;
}

四、回圈單鏈表

4.1 回圈單鏈表的基本概念及描述

單鏈表存在的問題：從表中的某個結點開始，只能訪問該結點后面的結點
回圈單鏈表解決的問題：從表中的任意一個結點開始，使其都能訪問到表中的所有的結點
回圈單鏈表：在單鏈表的基礎上，設定表中最后一個結點的指標域指向表中的第一個結點

4.2 回圈單鏈表的實作

回圈單鏈表的常用操作：
1. 建立一個空的回圈單鏈表
2. 獲得回圈單鏈表的最后一個結點的存盤地址
3. 輸出回圈單鏈表中各個結點的值
4. 在回圈單鏈表中查找一個值為 \(x\) 的結點
5. 回圈單鏈表的插入操作
6. 回圈單鏈表的洗掉操作
7. 回圈單鏈表的整體插入與洗掉操作

4.2.1 回圈單鏈表的存盤結構

typedef int datatype;
typedef struct link_node {
    datatype info;
    struct link_node *next;
} node;

五、雙鏈表

5.1 雙鏈表的基本概念及描述

雙鏈表解決的問題：設定一個 \(llink\) 指標域，通過這個指標域直接找到每一個結點的前驅結點

5.2 雙鏈表的實作

雙鏈表的常用操作：
1. 建立一個空的雙鏈表
2. 輸出雙鏈表中各個結點的值
3. 查找雙鏈表中第 \(i\) 個結點
4. 雙鏈表的插入操作
5. 雙鏈表的洗掉操作

5.2.1 雙鏈表的存盤結構

typedef int datatype;
typedef struct dlink_node {
    datatype info;
    struct dlink_node *llink, *rlink;
} dnode;

六、鏈式堆疊

6.1 鏈式堆疊的基本概念及描述

鏈式堆疊：使用鏈式存盤的堆疊
注：鏈式堆疊的堆疊頂指標一般用 \(top\) 表示

6.2 鏈式堆疊的實作

鏈式堆疊的常用操作：
1. 建立一個空的鏈式堆疊
2. 判斷鏈式堆疊是否為空
3. 取得鏈式堆疊的堆疊頂結點值
4. 輸出鏈式堆疊中各個結點的值
5. 向鏈式堆疊中插入一個值為 \(x\) 的結點
6. 洗掉鏈式堆疊的堆疊頂節點

6.2.1 鏈式堆疊的存盤結構

typedef int datatype;
typedef struct link_node {
    datatype info;
    struct link_node *next;
} node;

七、鏈式佇列

7.1 鏈式佇列的基本概念及描述

鏈式佇列：使用鏈式存盤的佇列
注：佇列必須有隊首和隊尾指標，因此增加一個結構型別，其中的兩個指標域分別為隊首和隊尾指標

7.2 鏈式佇列的實作

鏈式佇列的常用操作：
1. 建立一個空的鏈式佇列
2. 判斷鏈式佇列是否為空
3. 輸出鏈式佇列中各個結點的值
4. 取得鏈式佇列的隊首結點值
5. 向鏈式佇列中插入一個值為 \(x\) 的結點
6. 洗掉鏈式佇列中的隊首結點

7.2.1 鏈式佇列的存盤結構

typedef int datatype;
typedef struct link_node {
    datatype info;
    struct link_node *next;
} node;
typedef struct {
    node *front, *rear; // 定義隊首和隊尾指標
} queue;

八、演算法設計題

8.1 求單鏈表中結點個數（演算法）

設計一個演算法，求一個單鏈表中的結點個數

typedef struct node {
    int data;
    struct node *next;
} linknode;
typedef linknode *linklist;

int count(linklist head) {
    int c = 0;
    linklist p = head; // head為實際的第一個結點

    while (p) // 計數
    {
        c++;
        p = p->next;
    }
    return c;
}

8.2 求帶頭結點的單鏈表中的結點個數（演算法）

設計一個演算法，求一個帶頭結點單鏈表中的結點個數

typedef struct node {
    int data;
    struct node *next;
} linknode;
typedef linknode *linklist;

int count(linlist head) {
    int c = 0;
    linklist = head->next; // head->next 為實際的第一個結點

    while (p) // 計數
    {
        c++;
        p = p->next;
    }
    return c;
}

8.3 在單鏈表中的某個結點前插一個新結點（演算法）

設計一個演算法，在一個單鏈表中值為 y 的結點前面插入一個值為 x 的結點，即使值為 x 的新結點成為值為 y 的結點的前驅結點

typedef struct node {
    int data;
    struct node *next;
} linknode;
typedef linknode *linklist;

void insert(linklist head, int y, int c) {
    linklist pre, p, s; // 假設單鏈表帶頭結點
    pre = head;
    p = head->next;

    while (p && p->data != y) {
        pre = p;
        p = p->next;
    }

    if (p) // 找到了值為 y 的結點，即 p == y
    {
        s = (linklist) malloc(sizeof(linknode));
        s->data = https://www.cnblogs.com/nickchen121/p/x;
        s->next = p;
        pre->next = s;
    }
}

8.4 判斷單鏈表的各個結點是否有序（演算法）

設計一個演算法，判斷一個單鏈表中各個結點值是否有序

typedef struct node {
    int data;
    struct node *next;
} linknode;
typedef linknode *linklist;

int issorted(linklist head, char c) // c='a' 時為升序，c='d' 時為降序
{
    int flag = 1;
    linklist p = head->next;

    switch (c) {
        case 'a': // 判斷帶頭結點的單鏈表 head 是否為升序
            while (p && p->next && flag) {
                if (p->data <= p->next->data) p = p->next;
                else flag = 0;
            }
            break;
        case 'd': // 判斷帶頭結點的單鏈表 head 是否為降序
            while (p && p->next && flag) {
                if (p->data >= p->next->data) p = p->next;
                else flag = 0
            }
            break;
    }
    return flag;
}

8.5 逆轉一個單鏈表（演算法）

設計一個演算法，利用單鏈表原來的結點空間將一個單鏈表就地轉置

核心思想：通過 head->next 保留上一個 \(q\) 的狀態
演算法步驟：
1. 讓 \(p\) 指向實際的第一個結點
2. 回圈以下步驟：
  1. 讓 \(p\) 一直回圈下去，直到走完整個鏈表，\(p\) 回圈的時候，\(q\) 跟著 \(p\) 一起重繪
  2. \(q\) 的 \(next\) 指標域始終指向 head->next;
  3. head->next; 始終指向上一個 \(q\)

typedef struct node {
    int data;
    struct node *next;
} linknode;
typedef linknode *linklist;

void verge(linklist head) {
    linlist p, q;
    p = head->next;
    head->next = NULL;

    while (p) {
        q = p;
        p = p->next;
        q->next = head->next; // 通過 head->next 保留上一個 q 的狀態
        head->next = q;
    }
}

8.6 拆分結點值為自然數的單鏈表，原鏈表保留值為偶數的結點，新鏈表存放值為奇數的結點（演算法）

設計一個演算法，將一個結點值自然數的單鏈表拆分為兩個單鏈表，原表中保留值為偶數的結點，而值為奇數的結點按它們在原表中的相對次序組成一個新的單鏈表

typedef struct node {
    int data;
    struct node *next;
} linknode;
typedef linknode *linklist;

linklist sprit(linklist head) {
    linklist L, pre, p, r;

    L = r = (linklist) malloc(sizeof(linknode));
    r->next = NULL;
    pre = head;
    p = head->next;

    while (p) {
        if (p->data % 2 == 1) // 洗掉奇數值結點，并用 L 鏈表保存
        {
            pre->next = p->next;
            r->next = p;
            r = p; // 這樣使得 r 變成了 r->next
            p = pre->next; // 這樣使得 p 變成了 head->next->next
        } else // 保留偶數值結點
        {
            pre = p; // 書中的貌似多余操作
            p = p->next;
        }
    }
    r->next = NULL; // 置回傳的奇數鏈表結束標記
    return L;
}

8.7 在有序單鏈表中洗掉值大于 x 而小于 y 的結點（演算法）

設計一個演算法，對一個有序的單鏈表，洗掉所有值大于 x 而不大于 y 的結點

typedef struct node {
    int data;
    struct node *next;
} linknode;
typedef linknode *linklist;

void deletedata(linklist head, datatype x, datatype y) {
    linklist pre = head, p, q;

    p = head->next;

    // 找第 1 處大于 x 的結點位置
    while (p && p->data <= x) {
        pre = p;
        p = p->next;
    }

    // 找第 1 處小于 y 的位置
    while (p && p->data <= y) p = p->next;

    // 洗掉大于 x 而小于 y 的結點
    q = pre->next;
    pre->next = p; // 小于 x 的第一個結點指向大于 y 的第一個結點
    pre = q->next;
  	// 釋放被洗掉結點所占用的空間
    while (pre != p) { // 此時 p 已經指向了大于 y 的第一個結點
        free(q);
        q = pre;
        pre = pre->next;
    }
}

九、錯題集

在頭結點的單鏈表中查找 \(x\) 應選擇的程式體是：node *p = head; while (p && p->info != x) p = p->next; return p;
1. 注：未找到時需要回傳頭結點 \(head\)，而不是回傳一個 \(NULL\)
用不帶頭結點的單鏈表存盤佇列時，其隊頭指標指向隊頭結點，其隊尾指標指向隊尾結點，則在進行洗掉操作時隊頭隊尾指標都可能要修改
1. 注：鏈式佇列中只有一個結點是會出現該情況，插入時同理
若從鍵盤輸入 \(n\) 個元素，則建立一個有序單向鏈表的時間復雜度為 \(O(n^2)\)
1. 注：第 \(1\) 個數：\(0\) 次查找；第 \(2\) 個數：\(1\) 次查找 \(,\cdots,\) 第 \(n\) 個數，\(n-1\) 次查找，總共 \(n(n-1)/2\) 次

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/154494.html

標籤：其他

上一篇：Ubuntu16.04 跨主機系統備份和更新

下一篇：第3章順序表的鏈式存盤

第3章 順序表的鏈式存盤

第3章 順序表的鏈式存盤

一、鏈式存盤

二、單鏈表

2.1 單鏈表的基本概念及描述

2.2 單鏈表的實作

2.2.1 單鏈表的存盤結構

2.2.2 單鏈表的插入操作（演算法）

2.2.3 單鏈表的洗掉操作（演算法）

三、帶頭結點的單鏈表

3.1 帶頭結點的單鏈表的基本概念及描述

3.2 帶頭結點的單鏈表的實作

3.2.1 帶頭結點的單鏈表的存盤結構

3.2.2 帶頭結點的單鏈表的插入（演算法）

3.2.3 帶頭結點的單鏈表的洗掉（演算法）

四、回圈單鏈表

4.1 回圈單鏈表的基本概念及描述

4.2 回圈單鏈表的實作

4.2.1 回圈單鏈表的存盤結構

五、雙鏈表

5.1 雙鏈表的基本概念及描述

5.2 雙鏈表的實作

5.2.1 雙鏈表的存盤結構

六、鏈式堆疊

6.1 鏈式堆疊的基本概念及描述

6.2 鏈式堆疊的實作

6.2.1 鏈式堆疊的存盤結構

七、鏈式佇列

7.1 鏈式佇列的基本概念及描述

7.2 鏈式佇列的實作

7.2.1 鏈式佇列的存盤結構

八、演算法設計題

8.1 求單鏈表中結點個數（演算法）

8.2 求帶頭結點的單鏈表中的結點個數（演算法）

8.3 在單鏈表中的某個結點前插一個新結點（演算法）

8.4 判斷單鏈表的各個結點是否有序（演算法）

8.5 逆轉一個單鏈表（演算法）

8.6 拆分結點值為自然數的單鏈表，原鏈表保留值為偶數的結點，新鏈表存放值為奇數的結點（演算法）

8.7 在有序單鏈表中洗掉值大于 x 而小于 y 的結點（演算法）

九、錯題集

第3章順序表的鏈式存盤

第3章順序表的鏈式存盤