1. 冒泡排序（Bubble Sort）

1. 原理

冒泡排序是一種 簡單的排序算法，通過 兩兩比較相鄰元素，把較大的元素逐漸 “冒泡” 到數組末尾。

• 思路：

  1. 從數組頭開始，比較相鄰兩個元素。

  2. 如果前一個比后一個大，則交換它們。

  3. 一次完整遍歷后，最大值會移動到數組末尾。

  4. 對剩下未排序的部分重復以上步驟，直到全部排序完成。

• 舉例：

數組：[5, 3, 8, 4]

1. 第一次遍歷：

   • 5 vs 3 → 交換 → [3,5,8,4]

   • 5 vs 8 → 不交換 → [3,5,8,4]

   • 8 vs 4 → 交換 → [3,5,4,8]

   • 最大值 8 已經到最后

2. 第二次遍歷：

   • 3 vs 5 → 不交換 → [3,5,4,8]

   • 5 vs 4 → 交換 → [3,4,5,8]

   • 第二大值 5 到位

3. 第三次遍歷：

   • 3 vs 4 → 不交換 → [3,4,5,8]

   • 排序完成

---

2. C語言實現

#include <stdio.h>
void bubbleSort(int arr[], int n);int main(int argc,const char * argv[]) {int arr[] = {5, 3, 8, 4};int n = sizeof(arr) / sizeof(arr[0]);bubbleSort(arr, n);printf("排序結果：");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}void bubbleSort(int arr[], int n) 
{int i, j, temp;for (i = 0; i < n - 1; i++) // 外層控制遍歷次數{          for (j = 0; j < n - i - 1; j++) // 內層比較相鄰元素{  if (arr[j] > arr[j + 1])  // 前大于后則交換{    temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}

---

3. 特點

1. 穩定性：穩定排序（相同元素的順序不變）

2. 空間復雜度：O(1)，原地排序

3. 時間復雜度：

   • 最好情況（已排序）：O(n) 可以優化，設置標志位

   • 最壞/平均情況：O(n2)

---

4. 優化小技巧

• 可以加一個 標志位 flag，如果某次遍歷沒有交換元素，則提前退出（數組已經有序）：

for (i = 0; i < n - 1; i++) 
{int swapped = 0;for (j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = 1;}}if (!swapped) // 提前結束{break;} 
}

---

? 總結：冒泡排序思路直觀，適合小規模數據，但對大數據效率低（O(n2)）。

2. 選擇排序（Selection Sort）

1. 原理

選擇排序是一種 簡單直觀的排序算法，每一次從 未排序部分選擇最小（或最大）元素 放到已排序部分的末尾（或開頭）。

• 思路：

  1. 將整個數組分為 已排序區 和 未排序區。

  2. 每次在未排序區找到最小元素。

  3. 將最小元素與未排序區第一個元素交換。

  4. 重復以上步驟，直到數組全部排序。

• 舉例：

數組：[5, 3, 8, 4]

1. 第一次選擇：

   • 未排序區 [5,3,8,4] → 最小值 3

   • 交換 3 和第一個元素 5 → [3,5,8,4]

2. 第二次選擇：

   • 未排序區 [5,8,4] → 最小值 4

   • 交換 4 和第一個未排序元素 5 → [3,4,8,5]

3. 第三次選擇：

   • 未排序區 [8,5] → 最小值 5

   • 交換 5 和第一個未排序元素 8 → [3,4,5,8]

4. 排序完成

2. C語言實現

#include <stdio.h>
void selectionSort(int arr[], int n);int main(int argc,const char * argv[]) {int arr[] = {5, 3, 8, 4};int n = sizeof(arr) / sizeof(arr[0]);selectionSort(arr, n);printf("排序結果：");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}void selectionSort(int arr[], int n) 
{int i, j, minIndex, temp;for (i = 0; i < n - 1; i++) // 外層控制已排序區{          minIndex = i; // 假設未排序區第一個是最小值                     for (j = i + 1; j < n; j++) // 遍歷未排序區{      if (arr[j] < arr[minIndex]) {minIndex = j;  // 更新最小元素索引              }}     // 交換最小值到已排序區末尾if (minIndex != i) {temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}
}

3. 特點

1. 穩定性：不穩定（相同元素的順序可能被交換）

2. 空間復雜度：O(1)，原地排序

3. 時間復雜度：

   • 最好/最壞/平均：O(n2)

   • 每次都必須掃描未排序區，無法提前退出

4. 交換次數少

   • 每輪只交換一次（選最小值），相比冒泡排序可能減少交換次數

---

4. 冒泡排序 vs 選擇排序對比

特性	冒泡排序	選擇排序
思路	相鄰元素兩兩比較、交換	每次找到最小值放到已排序區
穩定性	穩定	不穩定
時間復雜度	O(n2)，可優化最好情況 O(n)	O(n2)，最好最壞情況相同
交換次數	多，可能每次比較都交換	少，每輪只交換一次
適合數據量	小規模、部分有序	小規模、無序或大數據交換少需求

---

? 總結：

• 冒泡排序：直觀、穩定，但交換次數多

• 選擇排序：交換次數少，但不穩定，比較次數不變

3.單鏈表（Singly Linked List）

1. 概念

單鏈表是一種 鏈式存儲結構，由一系列 節點（Node） 組成，每個節點包含：

1. 數據域（data）：存放節點數據

2. 指針域（next）：指向下一個節點

特點：

• 節點在內存中 不必連續分配，通過指針鏈接

• 第一個節點稱為 頭節點（head）

• 最后一個節點的 next 指針為 NULL

示意圖：

head → [data|next] → [data|next] → [data|next] → NULL

---

2. C語言節點定義

#include <stdio.h>
#include <stdlib.h>// 定義單鏈表節點結構體
typedef struct Node 
{int data;           // 數據域struct Node* next;  // 指針域，指向下一個節點
} Node;//錯誤寫法
typedef struct Node 
{int data;           // 數據域struct Node* next;  // 指針域，指向下一個節點
} *Node; //有歧義不明白定義的是一個結構體指針還是結構體

---

3. 創建單鏈表（頭插法）

頭插法：新節點插入到鏈表頭部

Node* createListHead(int arr[], int n) 
{Node* head = NULL;for (int i = 0; i < n; i++) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = arr[i];newNode->next = head; // 插入到頭部head = newNode;}return head;
}

---

4. 鏈表遍歷

void printList(Node* head) 
{Node* p = head;while (p != NULL) {printf("%d -> ", p->data);p = p->next;}printf("NULL\n");
}

---

5. 鏈表插入（指定位置）

在第 pos 個位置插入新節點（1表示頭節點之后）：

void insertNode(Node** head, int pos, int value) 
{Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;if (pos == 1) // 頭插{ newNode->next = *head;*head = newNode;return;}Node* p = *head;for (int i = 1; i < pos - 1 && p != NULL; i++) {p = p->next;}if (p == NULL)// 位置非法{ return; }newNode->next = p->next;p->next = newNode;
}

---

6. 鏈表刪除（指定位置）

刪除第 pos 個節點：

void deleteNode(Node** head, int pos) 
{if (*head == NULL) return;Node* temp;if (pos == 1) // 刪除頭節點{ temp = *head;*head = (*head)->next;free(temp);return;}Node* p = *head;for (int i = 1; i < pos - 1 && p->next != NULL; i++) {p = p->next;}if (p->next == NULL) // 位置非法{return; {temp = p->next;p->next = temp->next;free(temp);
}

---

7. 鏈表銷毀

void freeList(Node* head) 
{Node* temp;while (head != NULL) {temp = head;head = head->next;free(temp);}
}

---

8. 示例程序

int main(int argc,const char *argv[]) 
{int arr[] = {1, 2, 3};Node* head = createListHead(arr, 3);printf("初始鏈表: ");printList(head);insertNode(&head, 2, 9); // 在第二個位置插入9printf("插入9后: ");printList(head);deleteNode(&head, 1);    // 刪除第一個節點printf("刪除第一個節點后: ");printList(head);freeList(head);           // 釋放鏈表return 0;
}

---

9. 特點

1. 動態存儲：不需要連續內存

2. 插入/刪除方便：時間復雜度 O(1)（若已有指針）

3. 訪問慢：查找元素需從頭開始，時間復雜度 O(n)

4. 節省空間：不需預分配大數組

4. 雙鏈表原理

4.1 結構

每個節點包含三個部分：

域	說明
數據域 (data)	存儲節點數據
前驅指針 (prev)	指向前一個節點
后繼指針 (next)	指向下一個節點

示意圖：

NULL <- [prev|data|next] <-> [prev|data|next] <-> [prev|data|next] -> NULL

---

4.2 特點

1. 雙向遍歷：可以從頭到尾或從尾到頭遍歷。

2. 插入刪除方便：直接訪問前驅節點，操作比單鏈表更高效。

3. 內存占用多：每個節點多一個 prev 指針。

4. 適合場景：

   • 需要雙向遍歷的情況

   • 中間節點頻繁插入/刪除

   • 示例：瀏覽器歷史記錄、LRU緩存

---

4.3 操作實現

假設節點定義如下：

typedef struct Node {int data;           // 數據域struct Node *prev;  // 前驅指針struct Node *next;  // 后繼指針
} Node;

4.3.1 創建節點

Node* createNode(int value) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->prev = NULL;newNode->next = NULL;return newNode;
}

---

4.3.2 遍歷

從頭到尾：

void traverseForward(Node* head) {Node* p = head;while(p) {printf("%d ", p->data);p = p->next;}printf("\n");
}

從尾到頭：

void traverseBackward(Node* tail) {Node* p = tail;while(p) {printf("%d ", p->data);p = p->prev;}printf("\n");
}

---

4.3.3 插入節點

在頭部插入：

void insertAtHead(Node** head, Node* newNode) {newNode->next = *head;newNode->prev = NULL;if (*head) (*head)->prev = newNode;*head = newNode;
}

在尾部插入：

void insertAtTail(Node** head, Node* newNode) {if (*head == NULL) {*head = newNode;return;}Node* tail = *head;while(tail->next) tail = tail->next;tail->next = newNode;newNode->prev = tail;
}

在指定節點后插入：

void insertAfter(Node* node, Node* newNode) {newNode->next = node->next;newNode->prev = node;if (node->next) node->next->prev = newNode;node->next = newNode;
}

---

4.3.4 刪除節點

void deleteNode(Node** head, Node* node) {if (!node) return;if (node->prev) node->prev->next = node->next;else *head = node->next;  // 刪除頭節點if (node->next) node->next->prev = node->prev;free(node);
}

---

4.3.5 查找節點

Node* search(Node* head, int value) {Node* p = head;while (p) {if (p->data == value) return p;p = p->next;}return NULL; // 未找到
}

---

小結

鏈表類型	指針域	遍歷方式	插入/刪除效率	內存占用
單鏈表	next	單向	中間節點操作較慢	少
雙鏈表	prev+next	雙向	中間節點操作方便	多

鏈表 vs 數組

特性	數組	鏈表
內存要求	連續內存	不連續，堆上分配
最大存儲量	受單塊連續內存限制	受總可用內存限制
插入/刪除效率	O(n)	O(1)（已知位置）
訪問效率	O(1)	O(n)

所以鏈表可以存儲比數組更多的元素，尤其是在可用連續內存不足的情況下。

具體示例請看

學生信息管理系統 —— 課程設計報告（C語言有頭雙向鏈表）-CSDN博客