目錄

順序表

鏈表

棧與隊列

樹

圖

查找

排序

順序表

順序表默認結構體

1
2
3
4
5
# define maxsize 50
typedef struct{
  int data[maxsize];
  int length;
}Sqlist;

1. 在順序表 L 的第 k 個位置插入元素 x【增】

1
2
3
4
5
6
7
8
9
10
11
bool insert_L(Sqlist *L, int k, int x) {
    if (k < 1 || k > L->length + 1) {
        printf("插入失败");
        return false;
    }
    for (int i = L->length - 1; i >= k - 1; i--)
        L->data[i + 1] = L->data[i];
    L->data[k - 1] = x;
    L->length++;
    return true;
}

核心思想

  1. 检查参数合法性
  2. 元素后移
  3. 插入元素并更新长度

2. 刪除順序表 L 的第 k 個元素並返回其值【刪一】

3. 將順序表中的元素逆置【改：經典逆置】

4. 查找順序表中第一個值為 x 的元素的位置【查】

5. 順序表遞增有序，插入元素 x，仍保持遞增有序【查+增】

6. 用順序表最後一個元素覆蓋整個順序表中最小元素（若有多個則選取第一個），並返回該最小元素【查+改】

7. 刪除順序表中第一個值為 x 的元素【查+刪一】

8. 刪除順序表中所有值為 x 的元素（拓展：刪除給定值在 s 到 t 之間的所有元素）【查+刪多】

鏈表

單鏈表默認結構體

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

LinkList create() {
    LinkList L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    LinkList r = L;
    int x;
    scanf("%d", &x);
    while (x != 9999) {
        LinkList s = (LinkList)malloc(sizeof(LNode));
        s->data = x;
        s->next = NULL;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    return L;
}

核心思想
初始化头结点
读入数据直到结束标志
尾插法依次插入结点

1. 分別採用頭插法和尾插法建立一個帶頭結點的單鏈表

2. 帶頭結點遞增有序單鏈表插入新結點保持有序

3. 帶頭結點單鏈表就地逆置（O(1) 空間）

4. 刪除帶頭結點單鏈表中第一個值為 x 的結點

5. 刪除帶頭結點單鏈表中所有值為 x 的結點

6. 刪除帶頭結點單鏈表最小值結點

7. 遞增有序輸出單鏈表並釋放結點空間

8. 將最小值結點移動到鏈表最前端

9. 無序單鏈表實現：找最小值、奇偶判斷交換或刪除

10. 頭插法與尾插法建立雙向鏈表

11. 將雙向鏈表最小值移到最前端

12. 循環單鏈表反覆輸出最小值並刪除直到空

棧與隊列

1. 棧的基本操作

2. 判斷單鏈表是否回文

3. 判斷括號匹配

4. 將字元 S 提到 H 之前

5. 共享棧實現 s1、s2 入棧出棧

6. 隊列的基本操作

7. 循環單鏈表實現隊列入隊出隊

8. 兩個棧模擬一個隊列

9. 判斷字串是否回文

10. 子串匹配

11. 判斷鏈表 B 是否為鏈表 A 的連續子序列

樹

1. 先序、中序、後序遞歸遍歷二叉樹

2. 計算二叉樹結點個數

3. 計算葉子結點個數

4. 求值為 x 的層號

5. 計算二叉樹最大深度

6. 找出值最大的結點

7. 查找 data 域等於 key 的結點

8. 輸出先序第 k 個結點

9. 左右子樹交換

10. 判斷是否正則二叉樹

11. 先序非遞歸遍歷

12. 中序非遞歸遍歷

13. 後序非遞歸遍歷

14. 層次遍歷

圖

1. 鄰接表與鄰接矩陣創建圖

2. 鄰接表實現 BFS

3. 鄰接矩陣實現 BFS

4. 求距離頂點 v 最遠的結點

5. 鄰接表實現 DFS

6. 鄰接矩陣實現 DFS

7. 判斷 Vi 到 Vj 是否存在路徑

8. 輸出所有根結點

9. 求無向圖連通分量個數

查找

1. 二分查找

2. 判斷是否二叉排序樹

3. 尋找最大最小結點

4. 求值為 key 的層次

排序

1. 直接插入排序

2. 折半插入排序

3. 選擇排序

4. 冒泡排序

5. 快速排序