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(n²)

---

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(n²)）。

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(n²)

   • 每次都必须扫描未排序区，无法提前退出

4. 交换次数少

   • 每轮只交换一次（选最小值），相比冒泡排序可能减少交换次数

---

4. 冒泡排序 vs 选择排序对比

特性	冒泡排序	选择排序
思路	相邻元素两两比较、交换	每次找到最小值放到已排序区
稳定性	稳定	不稳定
时间复杂度	O(n²)，可优化最好情况 O(n)	O(n²)，最好最坏情况相同
交换次数	多，可能每次比较都交换	少，每轮只交换一次
适合数据量	小规模、部分有序	小规模、无序或大数据交换少需求

---

✅ 总结：

• 冒泡排序：直观、稳定，但交换次数多

• 选择排序：交换次数少，但不稳定，比较次数不变

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博客