1.數據結構基本概念

?????????數據結構是計算機中存儲、組織數據的方式，旨在提高數據的訪問和操作效率。它是實現高效算法和程序設計的基石。???????

????????目標:通過思維導圖了解數據結構的知識點,并掌握。

1.1邏輯結構

????????邏輯結構主要四種類型:

? ? ? ? ?集合：結構中的數據元素之間除了同屬于一個集合的關系外，別無其他關系。
? ? ? ?? 線性結構：結構中的數據元素之間存在一個對一個的關系，如線性表。
? ? ? ?? 樹形結構：結構中的元素之間存在一個對多個的關系，像二叉樹等。
? ? ? ? ?圖狀結構或網狀結構：結構中的數據元素之間存在多個對多個的關系。????????

1.2物理結構

? ? ? ? 物理結構主要兩種類型的特點:

????????順序存儲結構：數據元素在存儲器中是順序存放的，邏輯上相鄰的數據元素在物理位置上也相鄰。
????????鏈式存儲結構：數據元素在存儲器中的位置是任意的，邏輯上相鄰的數據元素在物理位置上不一定相鄰，通過指針來表示元素之間的關系。

1.3抽象數據類型（ADT）

????????抽象數據類型是指一個數學模型以及定義在該模型上的一組操作。它將數據和操作封裝在一起，使用者只需要關心它的功能，而不需要了解其內部實現細節。

????????在數據結構設計中，ADT有助于提高程序的模塊化和可維護性。

? ? ? ? 可以簡單理解成:接口,封裝,模塊化。

1.4數據結構常用的關鍵字及函數

? ? ? ? 數據結構核心必須要掌握常用的關鍵字，常用函數的原型以及內存的資源分配，對內存的操作時需要注意：內存申請，內存使用的狀態，內存的釋放，避免數據溢出而導致的程序異常，這里我們就簡單介紹下struct、union、typedef 。

1.4.1數據結構常用關鍵字及函數定義

1.4.2數據結構體及聯合體解析

1.4.2.1 struct解析

????????struct代碼示例:

//struct原型定義的格式為：struct 結構體名 { 成員列表 };?#include <stdio.h> // 引入標準輸入輸出庫//1. struct Point定義了一個名為 Point 的結構體struct Point {int x; // int x;：結構體成員 x，用于存儲點的 x 坐標int y; // int y;：結構體成員 y，用于存儲點的 y 坐標
};int main() {//2. 聲明結構體變量：    
// struct Point p1;：聲明一個 Point 類型的變量 p1，用于存儲一個點的坐標struct Point p1;  //3. 初始化結構體 p1 的成員變量 p1.x = 10; // p1.x = 10;：將 p1 的 x 坐標設置為 10p1.y = 20; // p1.y = 20;：將 p1 的 y 坐標設置為 20//4. 訪問并打印 p1 的坐標
//p1.x 和 p1.y 分別訪問 p1 的 x 坐標和 y 坐標printf("Point p1: (%d, %d)\n", p1.x, p1.y); // 輸出點 p1 的坐標return 0; // 程序結束
}

1.4.2.2 union解析

????????union代碼示例:

/*
1.union原型:
2.UnionName是union的名稱
3.type1, type2, ..., typen是union中成員的數據類型，member1, member2, ..., membern是union的成員名稱*/union UnionName {type1 member1;type2 member2;// ...typen membern;
};#include <stdio.h>
#include <string.h>//1. 定義一個 union
// union Data 定義了一個名為 Data 的 union，及三個成員：一個整數 i，一個浮點數 f，一個字符數組 str
// union 中的所有成員共享同一塊內存空間，因此 union 的大小等于其最大成員的大小union Data {int i;          // 整數成員float f;        // 浮點數成員char str[20];   // 字符數組成員
};int main() {//2. 定義 union 變量及聲明：
// union Data data;：聲明一個 Data 類型的變量 data，用于存儲不同類型的數據union Data data;//3. 訪問 union 成員：data.i = 10;    // data.i = 10;：將 data 的整數成員 i 設置為 10printf("data.i: %d\n", data.i);  // 使用 printf 函數輸出 data.i 的值//4. 修改 union 成員data.f = 220.5; // 將浮點數成員 f 設置為 220.5printf("data.f: %f\n", data.f);  // 輸出浮點數成員 f 的值//5. 再次訪問 union 成員
由于 union 成員共享同一塊內存空間，初始化 f 會覆蓋之前的 i 的值。printf("data.i: %d\n", data.i);  // 輸出整數成員 i 的值，可以看到它已經被覆蓋//6. 使用 str 成員strcpy(data.str, "hello glang");  // 將字符串 "Hello glang" 復制到字符數組成員 strprintf("data.str: %s\n", data.str);  // 輸出字符數組成員 data.str 的值//7. 再次訪問 union 成員
// 由于 union 成員共享同一塊內存空間，初始化 str 會覆蓋之前的 i 和 f 的值printf("data.i: %d\n", data.i);  return 0;
}

1.4.2.3 typedef 解析

????????代碼示例:

/*
typedef的基本語法existing_type是已存在的數據類型，new_type_name是你為這個數據類型定義的新名稱typedef existing_type new_type_name;
*///1. 為基本數據類型int定義別名Integer
typedef int Integer;//2. 為基本數據類型float定義別名Real
typedef float Real;//3. 為指向int類型的指針定義別名IntPtr
typedef int *IntPtr;//4. 為指向char指針的指針（即char**）定義別名StringArray，可用于表示字符串數組
typedef char **StringArray;//5. 為包含10個int元素的數組定義別名ArrayOfInt
typedef int ArrayOfInt[10];//6. 為匿名結構體定義別名Point，該結構體包含兩個int類型的成員x和y
typedef struct {int x; // x坐標int y; // y坐標
} Point;//7. 為指向函數的指針定義別名Operation，該函數接受兩個int參數并返回一個int值
typedef int (*Operation)(int, int);//8. Integer a = 10; // 等同于 int a = 10;//9. Real b = 20.5f; // 等同于 float b = 20.5f;//10. IntPtr p = &a; // 等同于 int *p = &a;//11. StringArray strings = {"Hello", "World"}; // 等同于 char *strings[] = {"Hello", "World"};//12. ArrayOfInt numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}; // 等同于 int numbers[10] = {1, 2, 
3, 4, 5, 6, 7, 8, 9, 0};//13. Point p1 = {1, 2}; // 等同于 struct {int x; int y;} p1 = {1, 2};//14. 假設有一個函數add，它接受兩個int參數并返回它們的和int add(int x, int y) {return x + y;
}Operation op = add; // 等同于 int (*op)(int, int) = add;int sum = op(5, 3); // 調用add函數，等同于 int sum = add(5, 3);

1.4.2.4?struct、union、typedef 聯合應用

? ? ? ? 代碼示例:

# include <stdio.h>
# include <string.h>// 定義一個結構體，用于表示二維平面上的一個點
struct Point {// 點的 x 坐標int x;// 點的 y 坐標int y;
};// 定義一個聯合體，用于表示不同類型的數據
union Data {// 整數成員int i;// 浮點數成員float f;// 字符數組成員char str[20];
};// 使用 typedef 為結構體和聯合體定義別名，方便后續使用
typedef struct Point Point;
typedef union Data Data;int main() {// 使用別名定義結構體變量Point p1;// 設置 x 坐標為 10p1.x = 10;// 設置 y 坐標為 20p1.y = 20;// 輸出點 p1 的坐標printf("Point p1: (%d, %d)\n", p1.x, p1.y);// 使用別名定義聯合體變量Data data;// 設置整數成員 i 的值為 10data.i = 10;// 輸出整數成員 i 的值printf("data.i: %d\n", data.i);// 設置浮點數成員 f 的值為 220.5data.f = 220.5;// 輸出浮點數成員 f 的值printf("data.f: %f\n", data.f);// 設置字符數組成員 str 的值為 "C Programming"strcpy(data.str,  "C Programming");// 輸出字符數組成員 str 的值printf("data.str:  %s\n", data.str);// 再次訪問聯合體成員 i 和 f，由于聯合體的特性，這些值可能已經被覆蓋printf("data.i after str: %d\n", data.i);printf("data.f after str: %f\n", data.f);return 0; // 返回 0 表示程序成功結束
}

2基礎數據結構

????????目標:通過思維導圖了解數據基礎結構核心的知識點,并掌握。

2.1數組

2.1.1數組的基礎概念及操作

2.1.2數組實現與解析? ? ??

2.1.2.1數組實現操作步驟

(1)插入元素函數?insert：

a.參數：

• arr[]：目標數組。
• size：指向數組當前大小的指針。
• index：插入位置的索引。
• value：要插入的值。

b.功能：

• 檢查數組是否已滿，如果已滿則輸出錯誤信息并返回。
• 檢查索引是否有效，如果無效則輸出錯誤信息并返回。
• 將插入位置之后的元素向后移動一位。
• 在指定位置插入新元素。
• 更新數組大小。

(2)刪除元素函數?delete：

a.參數：

• arr[]：目標數組。
• size：指向數組當前大小的指針。
• index：刪除位置的索引。

b.功能：

• 檢查數組是否為空，如果為空則輸出錯誤信息并返回。
• 檢查索引是否有效，如果無效則輸出錯誤信息并返回。
• 將刪除位置之后的元素向前移動一位。
• 更新數組大小。

(3)通過索引查找元素函數?searchByIndex：

a.參數：

• arr[]：目標數組。
• size：數組當前大小。
• index：要查找的索引。

b.功能：

• 檢查索引是否有效，如果無效則輸出錯誤信息并返回?-1。
• 返回指定索引的元素。

(4)順序查找元素函數?searchByValue：

a.參數：

• arr[]：目標數組。
• size：數組當前大小。
• value：要查找的值。

b.功能：

• 遍歷數組查找指定值。
• 如果找到，返回找到的元素索引。
• 如果未找到，返回?-1。

(5)主函數?main：

a.功能：

• 定義一個大小為100的數組?arr。
• 初始化數組大小?size?為0。
• 插入元素到數組中。
• 查找元素并打印結果。
• 刪除元素并打印數組內容。

(6)運行結果解釋：

• insert(arr, &size, 0, 10); insert(arr, &size, 1, 20); insert(arr, &size, 2, 30);：依次在索引?0,?1,?2?處插入值?10,?20,?30，此時數組內容為?[10, 20, 30]。
• printf("Element at index 1: %d\n", searchByIndex(arr, size, 1));：輸出索引?1?處的元素?20。
• printf("Index of element 20: %d\n", searchByValue(arr, size, 20));：輸出值?20?的索引?1。
• delete(arr, &size, 1);：刪除索引?1?處的元素?20，此時數組內容為?[10, 30]。
• printf("Array after deletion: ");：打印數組內容?[10, 30]。

2.1.2.2數組代碼實現實例

通過下圖代碼了解數據結構中的數組實現原理。

#include <stdio.h>// 插入元素到數組指定位置
void insert(int arr[], int *size, int index, int value) {// 檢查數組是否已滿if (*size >= 100) {printf("Array is full, cannot insert.\n");return;}// 檢查索引是否有效if (index < 0 || index > *size) {printf("Invalid index.\n");return;}// 將插入位置之后的元素向后移動一位for (int i = *size; i > index; i--) {arr[i] = arr[i - 1];}// 在指定位置插入新元素arr[index] = value;// 更新數組大小(*size)++;
}// 從數組指定位置刪除元素
void delete(int arr[], int *size, int index) {// 檢查數組是否為空if (*size == 0) {printf("Array is empty, cannot delete.\n");return;}// 檢查索引是否有效if (index < 0 || index >= *size) {printf("Invalid index.\n");return;}// 將刪除位置之后的元素向前移動一位for (int i = index; i < *size - 1; i++) {arr[i] = arr[i + 1];}// 更新數組大小(*size)--;
}// 通過索引查找元素
int searchByIndex(int arr[], int size, int index) {// 檢查索引是否有效if (index < 0 || index >= size) {printf("Invalid index.\n");return -1;}// 返回指定索引的元素return arr[index];
}// 順序查找元素
int searchByValue(int arr[], int size, int value) {// 遍歷數組查找指定值for (int i = 0; i < size; i++) {if (arr[i] == value) {// 返回找到的元素索引return i;}}// 如果未找到，返回-1return -1;
}int main() {int arr[100]; // 定義一個大小為100的數組int size = 0; // 初始化數組大小為0// 插入元素insert(arr, &size, 0, 10); // 在索引0處插入值10insert(arr, &size, 1, 20); // 在索引1處插入值20insert(arr, &size, 2, 30); // 在索引2處插入值30// 查找元素printf("Element at index 1: %d\n", searchByIndex(arr, size, 1)); // 查找索引1處的元素printf("Index of element 20: %d\n", searchByValue(arr, size, 20)); // 查找值為20的元素索引// 刪除元素delete(arr, &size, 1); // 刪除索引1處的元素// 打印數組printf("Array after deletion: ");for (int i = 0; i < size; i++) {printf("%d ", arr[i]); // 打印數組中的元素}printf("\n");return 0;
}

2.2鏈表

2.2.1鏈表結構特點與操作

????????

2.2.2鏈表實現與解析

2.2.2.1鏈表實現操作步驟

(1)結構體定義：

? Node?結構體表示單鏈表中的節點，包含一個整數?data?和一個指向下一個節點的指針?next。

(2)插入節點函數：

a. insertAtHead：在單鏈表頭部插入節點。

• 分配內存給新節點，如果內存分配失敗則輸出錯誤信息并返回。
• 設置新節點的數據。
• 將新節點的?next?指針指向當前頭節點。
• 更新頭節點為新節點。

b. insertAtTail：在單鏈表尾部插入節點。

• 分配內存給新節點，如果內存分配失敗則輸出錯誤信息并返回。
• 設置新節點的數據。
• 將新節點的?next?指針初始化為?NULL。
• 如果鏈表為空，直接將新節點設置為頭節點。
• 否則，從頭節點開始遍歷，找到最后一個節點并將最后一個節點的?next?指針指向新節點。

(3)刪除節點函數：

a. deleteNode：刪除單鏈表中的節點。

• 如果鏈表為空，直接返回。

• 如果要刪除的節點是頭節點，保存頭節點，更新頭節點為下一個節點，并釋放原頭節點的內存。

• 否則，從頭節點開始遍歷，找到要刪除節點的前一個節點。

• 如果找到了要刪除的節點，保存要刪除的節點，將前一個節點的?next?指針指向要刪除節點的下一個節點，并釋放要刪除節點的內存。

(4)查找節點函數：

a. searchNode：查找單鏈表中的節點。

????????從頭節點開始遍歷。

????????如果找到目標節點，返回目標節點。

????????如果未找到目標節點，返回?NULL。

(5)打印鏈表函數：

?a. printList：打印單鏈表。

????????從頭節點開始遍歷。

????????打印當前節點的數據。

????????打印換行符。

(6)主函數：

• 初始化鏈表頭節點為?NULL。
• 在頭部插入節點?10,?20,?30。
• 在尾部插入節點?40,?50。
• 打印鏈表。
• 查找值為?30?的節點并打印結果。
• 刪除值為?20?的節點。
• 打印鏈表。

(7)運行結果解釋：

• 插入節點：

  • insertAtHead(&head, 10); insertAtHead(&head, 20); insertAtHead(&head, 30);：依次在頭部插入值?10,?20,?30，此時鏈表內容為?[30, 20, 10]。

  • insertAtTail(&head, 40); insertAtTail(&head, 50);：依次在尾部插入值?40,?50，此時鏈表內容為?[30, 20, 10, 40, 50]。

• 打印鏈表：

  • printf("Linked list after insertions: "); printList(head);：輸出鏈表內容?[30, 20, 10, 40, 50]。

• 查找節點：

  • Node *foundNode = searchNode(head, 30);：查找值為?30?的節點。

  • if (foundNode != NULL) { printf("Node with value 30 found.\n"); }：輸出?Node with value 30 found.。

• 刪除節點：

  • deleteNode(&head, 20);：刪除值為?20?的節點，此時鏈表內容為?[30, 10, 40, 50]。

• 打印鏈表：

  • printf("Linked list after deletion: "); printList(head);：輸出鏈表內容?[30, 10, 40, 50]。

2.2.2.2鏈表代碼實現示例

#include <stdio.h>
#include <stdlib.h>// 定義單鏈表節點結構體
typedef struct Node {int data;       // 節點數據域struct Node *next;  // 指向下一個節點的指針
} Node;// 在單鏈表頭部插入節點
void insertAtHead(Node **head, int value) {Node *newNode = (Node *)malloc(sizeof(Node));  // 分配新節點的內存newNode->data = value;  // 設置新節點的數據newNode->next = *head;  // 將新節點的next指針指向當前頭節點*head = newNode;  // 更新頭節點為新節點
}// 在單鏈表尾部插入節點
void insertAtTail(Node **head, int value) {Node *newNode = (Node *)malloc(sizeof(Node));  // 分配新節點的內存newNode->data = value;  // 設置新節點的數據newNode->next = NULL;  // 新節點的next指針初始化為NULLif (*head == NULL) {  // 如果鏈表為空*head = newNode;  // 直接將新節點設置為頭節點return;}Node *current = *head;  // 從頭節點開始遍歷while (current->next != NULL) {  // 找到最后一個節點current = current->next;}current->next = newNode;  // 將最后一個節點的next指針指向新節點
}// 刪除單鏈表中的節點
void deleteNode(Node **head, int value) {if (*head == NULL) {  // 如果鏈表為空return;}if ((*head)->data == value) {  // 如果要刪除的節點是頭節點Node *temp = *head;  // 保存頭節點*head = (*head)->next;  // 更新頭節點為下一個節點free(temp);  // 釋放原頭節點的內存return;}Node *current = *head;  // 從頭節點開始遍歷while (current->next != NULL && current->next->data != value) {  // 找到要刪除節點的前一個節點current = current->next;}if (current->next != NULL) {  // 如果找到了要刪除的節點Node *temp = current->next;  // 保存要刪除的節點current->next = current->next->next;  // 將前一個節點的next指針指向要刪除節點的下一個節點free(temp);  // 釋放要刪除節點的內存}
}// 查找單鏈表中的節點
Node *searchNode(Node *head, int value) {Node *current = head;  // 從頭節點開始遍歷while (current != NULL) {  // 遍歷鏈表if (current->data == value) {  // 如果找到目標節點return current;  // 返回目標節點}current = current->next;  // 繼續遍歷下一個節點}return NULL;  // 如果未找到目標節點，返回NULL
}// 打印單鏈表
void printList(Node *head) {Node *current = head;  // 從頭節點開始遍歷while (current != NULL) {  // 遍歷鏈表printf("%d ", current->data);  // 打印當前節點的數據current = current->next;  // 繼續遍歷下一個節點}printf("\n");  // 打印換行符
}int main() {Node *head = NULL;  // 初始化鏈表頭節點為NULL// 在頭部插入節點insertAtHead(&head, 10);  // 在頭部插入值為10的節點insertAtHead(&head, 20);  // 在頭部插入值為20的節點insertAtHead(&head, 30);  // 在頭部插入值為30的節點// 在尾部插入節點insertAtTail(&head, 40);  // 在尾部插入值為40的節點insertAtTail(&head, 50);  // 在尾部插入值為50的節點// 打印鏈表printf("Linked list after insertions: ");printList(head);  // 打印鏈表// 查找節點Node *foundNode = searchNode(head, 30);  // 查找值為30的節點if (foundNode != NULL) {  // 如果找到了節點printf("Node with value 30 found.\n");  // 打印提示信息} else {  // 如果未找到節點printf("Node with value 30 not found.\n");  // 打印提示信息}// 刪除節點deleteNode(&head, 20);  // 刪除值為20的節點// 打印鏈表printf("Linked list after deletion: ");printList(head);  // 打印鏈表return 0;
}

2.3棧與隊列

2.3.1棧與隊列的基本概念

2.3.2棧與隊列實現與解析

2.3.2.1順序棧實現操作步驟

(1)宏定義：MAX_SIZE?定義了棧的最大容量。

(2)結構體定義：Stack?結構體包含一個數組?data?和一個整數?top，用于存儲棧中的元素和指向棧頂的位置。

(3)初始化函數：initStack?將棧頂指針?top?初始化為?-1，表示棧為空。

(4)判斷棧狀態：isEmpty?和?isFull?分別用于判斷棧是否為空或已滿。

(5)棧操作函數：

• push：將元素壓入棧頂，檢查棧是否已滿以避免溢出。

• pop：彈出棧頂元素，檢查棧是否為空以避免下溢。

• peek：查看棧頂元素但不彈出，同樣需要檢查棧是否為空。

(6)主函數：演示了棧的基本操作，包括入棧、查看棧頂元素和出棧。

2.3.2.2順序棧代碼實現示例

#include <stdio.h>
#include <stdlib.h>// 定義棧的最大容量
#define MAX_SIZE 100// 定義棧結構體，包含一個數組和一個指向棧頂的指針
typedef struct {int data[MAX_SIZE]; // 存儲棧中元素的數組int top;            // 棧頂指針，初始值為-1表示空棧
} Stack;// 初始化棧，將棧頂指針設置為-1
void initStack(Stack *s) {s->top = -1;
}// 判斷棧是否為空
int isEmpty(Stack *s) {return s->top == -1;
}// 判斷棧是否已滿
int isFull(Stack *s) {return s->top == MAX_SIZE - 1;
}// 入棧操作：將元素壓入棧頂
void push(Stack *s, int value) {if (isFull(s)) { // 檢查棧是否已滿printf("Stack Overflow\n"); // 棧滿時輸出錯誤信息return;}s->data[++s->top] = value; // 將元素存入棧頂，并更新棧頂指針
}// 出棧操作：彈出棧頂元素
int pop(Stack *s) {if (isEmpty(s)) { // 檢查棧是否為空printf("Stack Underflow\n"); // 棧空時輸出錯誤信息return -1;}return s->data[s->top--]; // 返回棧頂元素，并更新棧頂指針
}// 查看棧頂元素但不出棧
int peek(Stack *s) {if (isEmpty(s)) { // 檢查棧是否為空printf("Stack is empty\n"); // 棧空時輸出錯誤信息return -1;}return s->data[s->top]; // 返回棧頂元素
}// 主函數，用于測試棧的基本操作
int main() {Stack s;initStack(&s); // 初始化棧// 測試入棧操作push(&s, 1);push(&s, 2);push(&s, 3);// 查看棧頂元素printf("Top element: %d\n", peek(&s));// 彈出棧頂元素printf("Popped element: %d\n", pop(&s));// 再次查看棧頂元素printf("Top element after pop: %d\n", peek(&s));return 0;
}

? 2.3.2.3鏈棧實現操作步驟

?(1)結構體定義：

• Node?結構體表示鏈表中的節點，每個節點包含一個整數?data?和一個指向下一個節點的指針?next。
• Stack?結構體表示棧，棧由一個指向鏈表頭節點（即棧頂）的指針?top?組成。

?(2)初始化函數：initStack?將棧頂指針?top?初始化為?NULL，表示棧為空。

?(3)判斷棧狀態：isEmpty?通過檢查棧頂指針是否為?NULL?來判斷棧是否為空。

(4)棧操作函數：

• push：創建新節點并將其插入到棧頂。首先分配內存給新節點，如果內存分配失敗則輸出錯誤信息并返回。然后設置新節點的數據，并將其?next?指針指向當前棧頂，最后更新棧頂指針為新節點。
• pop：移除棧頂元素并返回其值。如果棧為空則輸出錯誤信息并返回?-1。否則，保存當前棧頂節點，獲取其值，更新棧頂指針為下一個節點，并釋放原棧頂節點的內存。
• peek：查看棧頂元素但不彈出。如果棧為空則輸出錯誤信息并返回?-1，否則返回棧頂元素的值。

(5)主函數：演示了棧的基本操作，包括入棧、查看棧頂元素和出棧。

(6)運行結果解釋：

• push(&s, 1); push(&s, 2); push(&s, 3);：依次將?1,?2,?3?壓入棧中，此時棧頂元素為?3。
• printf("Top element: %d\n", peek(&s));：輸出棧頂元素?3。
• printf("Popped element: %d\n", pop(&s));：彈出棧頂元素?3?并輸出。
• printf("Top element after pop: %d\n", peek(&s));：再次查看棧頂元素，此時棧頂元素為?2。

? 2.3.2.4鏈棧代碼實現示例

#include <stdio.h>
#include <stdlib.h>// 定義鏈表節點結構體，每個節點包含一個整數數據和指向下一個節點的指針
typedef struct Node {int data;                // 節點存儲的數據struct Node *next;       // 指向下一個節點的指針
} Node;// 定義棧結構體，棧由一個指向鏈表頭節點（即棧頂）的指針組成
typedef struct {Node *top;               // 指向棧頂元素的指針
} Stack;// 初始化棧，將棧頂指針設置為NULL，表示空棧
void initStack(Stack *s) {s->top = NULL;
}// 判斷棧是否為空，如果棧頂指針為NULL，則棧為空
int isEmpty(Stack *s) {return s->top == NULL;
}// 入棧操作：創建新節點并將其插入到棧頂
void push(Stack *s, int value) {// 分配內存給新節點Node *newNode = (Node *)malloc(sizeof(Node));if (newNode == NULL) { // 如果內存分配失敗，輸出錯誤信息并返回printf("Memory allocation failed\n");return;}newNode->data = value;  // 設置新節點的數據newNode->next = s->top; // 新節點的next指針指向當前棧頂s->top = newNode;       // 更新棧頂指針為新節點
}// 出棧操作：移除棧頂元素并返回其值
int pop(Stack *s) {if (isEmpty(s)) { // 如果棧為空，輸出錯誤信息并返回-1printf("Stack Underflow\n");return -1;}Node *temp = s->top;   // 保存當前棧頂節點int value = temp->data; // 獲取棧頂元素的值s->top = temp->next;   // 更新棧頂指針為下一個節點free(temp);            // 釋放原棧頂節點的內存return value;          // 返回棧頂元素的值
}// 查看棧頂元素但不出棧
int peek(Stack *s) {if (isEmpty(s)) { // 如果棧為空，輸出錯誤信息并返回-1printf("Stack is empty\n");return -1;}return s->top->data; // 返回棧頂元素的值
}// 主函數，用于測試棧的基本操作
int main() {Stack s;initStack(&s); // 初始化棧// 測試入棧操作push(&s, 1);push(&s, 2);push(&s, 3);// 查看棧頂元素printf("Top element: %d\n", peek(&s));// 彈出棧頂元素printf("Popped element: %d\n", pop(&s));// 再次查看棧頂元素printf("Top element after pop: %d\n", peek(&s));return 0;
}

2.3.2.5順序隊列實現操作步驟

(1)宏定義：MAX_SIZE?定義了隊列的最大容量。

(2)結構體定義：Queue?結構體包含一個數組?data?和兩個整數?front?和?rear，用于存儲隊列中的元素和指向隊頭和隊尾的位置。

1. 初始化函數：initQueue?將?front?和?rear?初始化為?-1，表示隊列為空。

2. 判斷隊列狀態：

• isEmpty?通過檢查?front?是否為?-1?來判斷隊列是否為空。
• isFull?通過檢查?(rear + 1) % MAX_SIZE?是否等于?front?來判斷隊列是否已滿。

(3)隊列操作函數：

• enqueue：將元素添加到隊尾。首先檢查隊列是否已滿，如果已滿則輸出錯誤信息并返回。如果隊列為空，則將?front?和?rear?都設置為?0，否則更新?rear?指針并使用模運算實現循環隊列。最后將元素存入隊尾。
• dequeue：移除隊頭元素并返回其值。如果隊列為空則輸出錯誤信息并返回?-1。否則，獲取隊頭元素的值，如果隊列只有一個元素，則重置?front?和?rear?為?-1，否則更新?front?指針并使用模運算實現循環隊列。
• peek：查看隊頭元素但不移除。如果隊列為空則輸出錯誤信息并返回?-1，否則返回隊頭元素的值。

(4)主函數：演示了隊列的基本操作，包括入隊、查看隊頭元素和出隊。

(5)運行結果解釋：

• enqueue(&q, 1); enqueue(&q, 2); enqueue(&q, 3);：依次將?1,?2,?3?入隊，此時隊頭元素為?1。
• printf("Front element: %d\n", peek(&q));：輸出隊頭元素?1。
• printf("Dequeued element: %d\n", dequeue(&q));：出隊隊頭元素?1?并輸出。
• printf("Front element after dequeue: %d\n", peek(&q));：再次查看隊頭元素，此時隊頭元素為?2。

2.3.2.6順序隊列代碼實現示例

#include <stdio.h>
#include <stdlib.h>// 定義隊列的最大容量
#define MAX_SIZE 100// 定義隊列結構體，包含一個數組和兩個指針（front和rear）
typedef struct {int data[MAX_SIZE]; // 存儲隊列中元素的數組int front, rear;    // front指向隊頭，rear指向隊尾
} Queue;// 初始化隊列，將front和rear設置為-1，表示隊列為空
void initQueue(Queue *q) {q->front = q->rear = -1;
}// 判斷隊列是否為空，如果front為-1，則隊列為空
int isEmpty(Queue *q) {return q->front == -1;
}// 判斷隊列是否已滿，如果(rear + 1) % MAX_SIZE等于front，則隊列已滿
int isFull(Queue *q) {return (q->rear + 1) % MAX_SIZE == q->front;
}// 入隊操作：將元素添加到隊尾
void enqueue(Queue *q, int value) {if (isFull(q)) { // 檢查隊列是否已滿printf("Queue Overflow\n"); // 隊列滿時輸出錯誤信息return;}if (isEmpty(q)) { // 如果隊列為空，front和rear都指向0q->front = q->rear = 0;} else {q->rear = (q->rear + 1) % MAX_SIZE; // 更新rear指針，使用模運算實現循環隊列}q->data[q->rear] = value; // 將元素存入隊尾
}// 出隊操作：移除隊頭元素并返回其值
int dequeue(Queue *q) {if (isEmpty(q)) { // 檢查隊列是否為空printf("Queue Underflow\n"); // 隊列空時輸出錯誤信息return -1;}int value = q->data[q->front]; // 獲取隊頭元素的值if (q->front == q->rear) { // 如果隊列只有一個元素，重置front和rear為-1q->front = q->rear = -1;} else {q->front = (q->front + 1) % MAX_SIZE; // 更新front指針，使用模運算實現循環隊列}return value; // 返回隊頭元素的值
}// 查看隊頭元素但不出隊
int peek(Queue *q) {if (isEmpty(q)) { // 檢查隊列是否為空printf("Queue is empty\n"); // 隊列空時輸出錯誤信息return -1;}return q->data[q->front]; // 返回隊頭元素的值
}// 主函數，用于測試隊列的基本操作
int main() {Queue q;initQueue(&q); // 初始化隊列// 測試入隊操作enqueue(&q, 1);enqueue(&q, 2);enqueue(&q, 3);// 查看隊頭元素printf("Front element: %d\n", peek(&q));// 出隊操作printf("Dequeued element: %d\n", dequeue());// 再次查看隊頭元素printf("Front element after dequeue: %d\n", peek(&q));return 0;
}

2.3.2.7鏈式隊列實現操作步驟

(1)結構體定義：

• Node?結構體表示鏈表中的節點，每個節點包含一個整數?data?和一個指向下一個節點的指針?next。
• Queue?結構體表示隊列，隊列由兩個指針?front?和?rear?組成，分別指向隊頭和隊尾。

(2)初始化函數：initQueue?將?front?和?rear?初始化為?NULL，表示隊列為空。

(3)判斷隊列狀態：isEmpty?通過檢查?front?是否為?NULL?來判斷隊列是否為空。

(4)隊列操作函數：

• enqueue：將元素添加到隊尾。首先分配內存給新節點，如果內存分配失敗則輸出錯誤信息并返回。然后設置新節點的數據，并將其?next?指針初始化為?NULL。如果隊列為空，則將?front?和?rear?都指向新節點，否則將當前隊尾節點的?next?指針指向新節點，并更新?rear?指針為新節點。
• dequeue：移除隊頭元素并返回其值。如果隊列為空則輸出錯誤信息并返回?-1。否則，保存當前隊頭節點，獲取其值，更新?front?指針為下一個節點。如果隊列為空，則更新?rear?指針也為?NULL，并釋放原隊頭節點的內存。
• peek：查看隊頭元素但不移除。如果隊列為空則輸出錯誤信息并返回?-1，否則返回隊頭元素的值。

(5)主函數：演示了隊列的基本操作，包括入隊、查看隊頭元素和出隊。

(6)運行結果解釋：

• enqueue(&q, 1); enqueue(&q, 2); enqueue(&q, 3);：依次將?1,?2,?3?入隊，此時隊頭元素為?1。
• printf("Front element: %d\n", peek(&q));：輸出隊頭元素?1。
• printf("Dequeued element: %d\n", dequeue(&q));：出隊隊頭元素?1?并輸出。
• printf("Front element after dequeue: %d\n", peek(&q));：再次查看隊頭元素，此時隊頭元素為?2。

2.3.2.8鏈式隊列代碼實現示例

#include <stdio.h>
#include <stdlib.h>// 定義鏈表節點結構體，每個節點包含一個整數數據和指向下一個節點的指針
typedef struct Node {int data;                // 節點存儲的數據struct Node *next;       // 指向下一個節點的指針
} Node;// 定義隊列結構體，隊列由兩個指針（front和rear）組成
typedef struct {Node *front;             // 指向隊頭元素的指針Node *rear;              // 指向隊尾元素的指針
} Queue;// 初始化隊列，將front和rear設置為NULL，表示隊列為空
void initQueue(Queue *q) {q->front = q->rear = NULL;
}// 判斷隊列是否為空，如果front為NULL，則隊列為空
int isEmpty(Queue *q) {return q->front == NULL;
}// 入隊操作：將元素添加到隊尾
void enqueue(Queue *q, int value) {// 分配內存給新節點Node *newNode = (Node *)malloc(sizeof(Node));if (newNode == NULL) { // 如果內存分配失敗，輸出錯誤信息并返回printf("Memory allocation failed\n");return;}newNode->data = value;  // 設置新節點的數據newNode->next = NULL;   // 新節點的next指針初始化為NULLif (isEmpty(q)) { // 如果隊列為空，front和rear都指向新節點q->front = q->rear = newNode;} else {q->rear->next = newNode; // 將當前隊尾節點的next指針指向新節點q->rear = newNode;       // 更新rear指針為新節點}
}// 出隊操作：移除隊頭元素并返回其值
int dequeue(Queue *q) {if (isEmpty(q)) { // 如果隊列為空，輸出錯誤信息并返回-1printf("Queue Underflow\n");return -1;}Node *temp = q->front;   // 保存當前隊頭節點int value = temp->data; // 獲取隊頭元素的值q->front = q->front->next; // 更新front指針為下一個節點if (q->front == NULL) { // 如果隊列為空，更新rear指針也為NULLq->rear = NULL;}free(temp);            // 釋放原隊頭節點的內存return value;          // 返回隊頭元素的值
}// 查看隊頭元素但不出隊
int peek(Queue *q) {if (isEmpty(q)) { // 如果隊列為空，輸出錯誤信息并返回-1printf("Queue is empty\n");return -1;}return q->front->data; // 返回隊頭元素的值
}// 主函數，用于測試隊列的基本操作
int main() {Queue q;initQueue(&q); // 初始化隊列// 測試入隊操作enqueue(&q, 1);enqueue(&q, 2);enqueue(&q, 3);// 查看隊頭元素printf("Front element: %d\n", peek(&q));// 出隊操作printf("Dequeued element: %d\n", dequeue(&q));// 再次查看隊頭元素printf("Front element after dequeue: %d\n", peek(&q));return 0;
}

3.高級數據結構

???????目標:通過思維導圖了解高級數據基礎結構核心的知識點,并掌握。

3.1樹形結構

? ? ? ? 樹形結構基礎概念與操作。

3.1.1二叉樹的概念

?

3.1.2二叉樹實現與解析

3.1.2.1二叉樹節點結構體定義

// 定義了一個二叉樹節點的結構體 BiNode //通過 typedef 關鍵字定義了一個指向 BiNode 結構體的指針類型 BiTree，方便后續使用//typedef existing_type new_type_name; 關鍵字的原型//existing_type 是已有的數據類型，new_type_name 是你為該數據類型定義的新名稱typedef struct BiNode {int data;             // 定義一個整型節點數據域 datastruct BiNode *lchild; // 指向左子節點的lchild指針struct BiNode *rchild; // 指向右子節點的rchild指針
} BiNode, *BiTree;/*

3.1.2.2二叉樹存儲結構定義

(1)數組表示法

// 定義二叉樹數組的最大容量#define MAX_SIZE 100  // 定義二叉樹數組結構體typedef struct {// 一個整型數組，用于存儲二叉樹的節點數據,數組的大小為 MAX_SIZE，即100int data[MAX_SIZE];  // size：一個整型變量，用于記錄當前二叉樹的節點個數int size;    //定義了一個名為 BinaryTreeArray 的結構體，用于表示一個二叉樹的數組存儲結構
//結構體包含兩個成員：} BinaryTreeArray;

(2)鏈表表示法

// 定義二叉樹節點名為 BiNode 的結構體，用于表示二叉樹的節點,結構體包含三個成員typedef struct BiNode {// 一個整型變量(data)，用于存儲節點的值int data;  // 一個指向 BiNode 結構體的(lchild)指針，用于指向左子節點struct BiNode *lchild;// 一個指向 BiNode 結構體的（rchild)指針，用于指向右子節點struct BiNode *rchild;} BiNode, *BiTree;/*通過這個結構體，可以構建二叉樹的數據結構，并進行相關的操作，如插入、刪除、遍歷等。此外，代碼中還使用了 typedef 關鍵字，為 BiNode 結構體定義了一個別名 BiTree，使得 BiTree 可以作為指向 BiNode 結構體的指針類型使用。這樣，在聲明變量時可以直接使用 BiTree，而不需要每次都寫完整的 struct BiNode **/

3.1.3平衡樹的概念

3.1.4平衡樹實現與解析

3.1.4.1平衡樹節點結構體定義

// 定義平衡樹節點結構體
// 定義了一個名為 AVLNode 的結構體，用于表示平衡樹的節點,結構體包含四個成員typedef struct AVLNode {// 節點數據域,用于存儲節點的值int data;             // 指向左子節點的指針，指向 AVLNode 結構體的指針struct AVLNode *left;      // 指向右子節點的指針,指向 AVLNode 結構體的指針struct AVLNode *right;     // 節點的高度，用于平衡因子的計算，節點的高度是指從該節點到其最遠葉子節點的最長路徑上的節點數int height;      //使用了 typedef 關鍵字，為 AVLNode 結構體定義了一個別名 AVLTree，使得 AVLTree 可以作為指向 AVLNode 結構體的指針類型使用
//這樣，在聲明變量時可以直接使用 AVLTree，而不需要每次都寫完整的 struct AVLNode *} AVLNode, *AVLTree;

3.1.4.2紅黑樹樹節點結構體定義

// 定義紅黑樹節點顏色typedef enum {RED,BLACK//枚舉（Color )定義了紅黑樹節點的顏色，包括 RED 和 BLACK} Color;// 定義紅黑樹節點結構體typedef struct RBNode {int data;                   // 節點數據struct RBNode *left;        // 指向左子節點的指針struct RBNode *right;       // 指向右子節點的指針struct RBNode *parent;      // 指向父節點的指針Color color;                // 節點顏色，可以是 RED 或 BLACK
} RBNode, *RBTree;

3.1.5堆的概念

3.1.6堆實現與解析

#include <stdio.h>
#include <stdlib.h>// 定義最大堆結構體
typedef struct {// 存儲堆元素的數組int* array;     // 堆的最大容量int capacity;   // 當前堆的大小int size;       
} MaxHeap;// 創建一個最大堆
MaxHeap* createMaxHeap(int capacity) {// 分配內存給 MaxHeap 結構體MaxHeap* heap = (MaxHeap*)malloc(sizeof(MaxHeap));// 分配內存給存儲堆元素的數組heap->array = (int*)malloc(capacity * sizeof(int));// 設置堆的最大容量heap->capacity = capacity;// 初始化堆的大小為 0heap->size = 0;// 返回創建的堆return heap;
}// 交換兩個元素的值
void swap(int* a, int* b) {// 臨時變量存儲 a 的值int temp = *a;// 將 b 的值賦給 a*a = *b;// 將臨時變量的值賦給 b*b = temp;
}// 向上調整堆
void heapifyUp(MaxHeap* heap, int index) {// 計算父節點的索引int parent = (index - 1) / 2;// 當索引大于 0 且當前節點的值大于父節點的值時while (index > 0 && heap->array[index] > heap->array[parent]) {// 交換當前節點和父節點的值swap(&heap->array[index], &heap->array[parent]);// 更新當前節點的索引為父節點的索引index = parent;// 重新計算父節點的索引parent = (index - 1) / 2;}
}// 向下調整堆
void heapifyDown(MaxHeap* heap, int index) {// 計算左子節點的索引int leftChild = 2 * index + 1;// 計算右子節點的索引int rightChild = 2 * index + 2;// 初始化最大節點的索引為當前節點的索引int largest = index;// 如果左子節點存在且左子節點的值大于最大節點的值if (leftChild < heap->size && heap->array[leftChild] > heap->array[largest]) {// 更新最大節點的索引為左子節點的索引largest = leftChild;}// 如果右子節點存在且右子節點的值大于最大節點的值if (rightChild < heap->size && heap->array[rightChild] > heap->array[largest]) {// 更新最大節點的索引為右子節點的索引largest = rightChild;}// 如果最大節點的索引不是當前節點的索引if (largest != index) {// 交換當前節點和最大節點的值swap(&heap->array[index], &heap->array[largest]);// 遞歸調用 heapifyDown 函數，繼續向下調整堆heapifyDown(heap, largest);}
}// 插入元素到堆中
void insert(MaxHeap* heap, int value) {// 如果堆已滿if (heap->size == heap->capacity) {// 輸出提示信息printf("Heap is full. Cannot insert more elements.\n");// 返回return;}// 將元素插入到堆的末尾heap->array[heap->size] = value;// 向上調整堆heapifyUp(heap, heap->size);// 增加堆的大小heap->size++;
}// 刪除堆頂元素
int deleteMax(MaxHeap* heap) {// 如果堆為空if (heap->size == 0) {// 輸出提示信息printf("Heap is empty. Cannot delete element.\n");// 返回 -1 表示錯誤return -1;}// 獲取堆頂元素的值int max = heap->array[0];// 將堆的最后一個元素移到堆頂heap->array[0] = heap->array[heap->size - 1];// 減少堆的大小heap->size--;// 向下調整堆heapifyDown(heap, 0);// 返回刪除的堆頂元素的值return max;
}// 獲取堆頂元素
int peek(MaxHeap* heap) {// 如果堆為空if (heap->size == 0) {// 輸出提示信息printf("Heap is empty. No element to peek.\n");// 返回 -1 表示錯誤return -1;}// 返回堆頂元素的值return heap->array[0];
}// 打印堆中的元素
void printHeap(MaxHeap* heap) {// 遍歷堆中的元素for (int i = 0; i < heap->size; i++) {// 輸出元素的值printf("%d ", heap->array[i]);}// 輸出換行符printf("\n");
}// 釋放堆的內存
void destroyHeap(MaxHeap* heap) {// 釋放存儲堆元素的數組的內存free(heap->array);// 釋放 MaxHeap 結構體的內存free(heap);
}int main() {// 創建一個最大堆，容量為 10MaxHeap* heap = createMaxHeap(10);// 插入元素到堆中insert(heap, 3);insert(heap, 4);insert(heap, 9);insert(heap, 5);insert(heap, 2);// 打印堆中的元素printf("Max Heap: ");printHeap(heap);// 獲取堆頂元素并輸出printf("Peek: %d\n", peek(heap));// 刪除堆頂元素并輸出printf("Deleted: %d\n", deleteMax(heap));// 打印刪除堆頂元素后的堆printf("Max Heap after deletion: ");printHeap(heap);// 釋放堆的內存destroyHeap(heap);return 0;
}

3.2圖結構基礎概念

????????圖（Graph）是一種非線性的數據結構，由頂點（Vertex）和邊（Edge）組成。頂點表示圖中的節點，邊表示節點之間的連接關系。圖可以用來表示各種實際問題，如社交網絡、交通網絡、計算機網絡等,常見的有鄰接矩陣和鄰接表。

3.2.1圖結構頂點（Vertex）

? ? ? ? 基本概念如下所示:

3.2.1.1圖結構頂點結構體定義

// 定義一個結構體 Vertex，用于表示圖中的頂點
typedef struct Vertex {int id;        // 頂點的標識符char *name;    // 頂點的名字int visited;   // 標記頂點是否被訪問過，0表示未訪問，1表示已訪問
} Vertex;

3.2.1.2圖結構頂點實現與解析

// 頂點結構體定義
typedef struct Vertex {int id;                // 頂點的唯一標識符char *name;            // 頂點的名稱（可選）int visited;           // 標記頂點是否被訪問過，0表示未訪問，1表示已訪問// 可以添加其他屬性，如權重、顏色等
} Vertex;// 創建一個新的頂點
Vertex *createVertex(int id, char *name) {// 分配內存以存儲新的頂點結構體Vertex *newVertex = (Vertex *)malloc(sizeof(Vertex));// 檢查內存分配是否成功if (newVertex == NULL) {printf("內存分配失敗\n");// 如果內存分配失敗，程序終止exit(1);}// 設置頂點的唯一標識符newVertex->id = id;// 設置頂點的名稱newVertex->name = name;// 初始化頂點的訪問狀態為未訪問newVertex->visited = 0;// 返回新創建的頂點指針return newVertex;
}// 打印頂點信息
void printVertex(Vertex *vertex) {// 打印頂點的唯一標識符printf("頂點ID: %d\n", vertex->id);// 如果頂點有名稱，打印頂點的名稱if (vertex->name != NULL) {printf("頂點名稱: %s\n", vertex->name);}// 打印頂點的訪問狀態printf("是否被訪問: %s\n", vertex->visited ? "是" : "否");
}int main() {// 創建頂點Vertex *v1 = createVertex(1, "頂點1");Vertex *v2 = createVertex(2, "頂點2");Vertex *v3 = createVertex(3, "頂點3");// 打印頂點信息printVertex(v1);printVertex(v2);printVertex(v3);// 釋放內存free(v1);free(v2);free(v3);return 0;
}

3.2.2圖結構邊（Edge）

????????基本概念如下所示:

3.2.2.1圖結構邊定義

????????圖結構的邊可以通過多種方式定義，具體取決于圖的表示方法（如鄰接矩陣或鄰接表）。

//1. 使用結構體定義圖邊// 定義一個結構體 Edge，用于表示圖中的邊
typedef struct Edge {int dest;           // 邊的目標頂點int weight;         // 邊的權重（如果是有權圖）struct Edge* next;  // 指向下一個邊的指針
} Edge;//2. 使用結構體定義帶有源頂點和目標頂點的邊typedef struct Edge {int src;            // 邊的源頂點int dest;           // 邊的目標頂點int weight;         // 邊的權重（如果是有權圖）struct Edge* next;  // 指向下一個邊的指針
} Edge;//3. 使用二維數組定義邊（適用于鄰接矩陣）
#define MAX_VERTICES 100typedef struct {int matrix[MAX_VERTICES][MAX_VERTICES]; // 鄰接矩陣int numVertices;                        // 頂點數量
} GraphMatrix;

3.2.2.2圖結構邊實現與解析

#include <stdio.h>
#include <stdlib.h>// 定義邊結構體
typedef struct Edge {int dest;           // 邊的目標頂點int weight;         // 邊的權重（如果是有權圖）struct Edge* next;  // 指向下一個邊的指針
} Edge;//1. 創建一個新的邊
Edge* createEdge(int dest, int weight) {// 分配內存以存儲新的邊結構體Edge* newEdge = (Edge*)malloc(sizeof(Edge));// 檢查內存分配是否成功if (newEdge == NULL) {printf("內存分配失敗\n");// 如果內存分配失敗，程序終止exit(1);}// 設置邊的目標頂點newEdge->dest = dest;// 設置邊的權重newEdge->weight = weight;// 將下一個邊指針初始化為NULLnewEdge->next = NULL;// 返回新創建的邊指針return newEdge;
}//2. 插入邊到鄰接表中
void insertEdge(Edge** adjList, int src, int dest, int weight) {// 創建一個新的邊Edge* newEdge = createEdge(dest, weight);// 將新邊的下一個邊指針指向當前頂點的鄰接表newEdge->next = adjList[src];// 將新邊插入到當前頂點的鄰接表的頭部adjList[src] = newEdge;
}//3. 刪除邊
void deleteEdge(Edge** adjList, int src, int dest) {// 獲取當前頂點的鄰接表Edge* current = adjList[src];// 初始化前一個邊指針為NULLEdge* prev = NULL;// 遍歷鄰接表，找到目標邊while (current != NULL && current->dest != dest) {prev = current;current = current->next;}// 如果目標邊不存在，打印錯誤信息并返回if (current == NULL) {printf("邊不存在\n");return;}// 如果目標邊是鄰接表的第一個邊if (prev == NULL) {// 將鄰接表的頭指針指向下一個邊adjList[src] = current->next;} else {// 將前一個邊的下一個邊指針指向目標邊的下一個邊prev->next = current->next;}// 釋放目標邊的內存free(current);
}//4. 查找邊
Edge* findEdge(Edge* adjList, int src, int dest) {// 獲取當前頂點的鄰接表Edge* current = adjList;// 遍歷鄰接表，找到目標邊while (current != NULL && current->dest != dest) {current = current->next;}// 返回目標邊指針return current;
}//5. 遍歷邊
void traverseEdges(Edge* adjList) {// 獲取當前頂點的鄰接表Edge* current = adjList;// 遍歷鄰接表，打印每條邊的目標頂點和權重while (current != NULL) {printf("目標頂點: %d, 權重: %d\n", current->dest, current->weight);current = current->next;}
}//6. 更新邊的權重
void updateEdgeWeight(Edge* adjList, int src, int dest, int newWeight) {// 查找目標邊Edge* edge = findEdge(adjList, src, dest);// 如果目標邊存在，更新其權重if (edge != NULL) {edge->weight = newWeight;} else {// 如果目標邊不存在，打印錯誤信息printf("邊不存在\n");}
}//7. 判斷邊是否存在
int edgeExists(Edge* adjList, int src, int dest) {// 查找目標邊return findEdge(adjList, src, dest) != NULL;
}//8. 獲取邊的權重
int getEdgeWeight(Edge* adjList, int src, int dest) {// 查找目標邊Edge* edge = findEdge(adjList, src, dest);// 如果目標邊存在，返回其權重if (edge != NULL) {return edge->weight;} else {// 如果目標邊不存在，打印錯誤信息并返回-1printf("邊不存在\n");return -1;}
}int main() {// 假設圖有5個頂點int numVertices = 5;// 定義一個鄰接表數組，每個元素指向一個頂點的鄰接表Edge* adjList[numVertices];// 初始化鄰接表，將每個頂點的鄰接表指針初始化為NULLfor (int i = 0; i < numVertices; i++) {adjList[i] = NULL;}// 插入邊insertEdge(adjList, 0, 1, 10);insertEdge(adjList, 0, 2, 20);insertEdge(adjList, 1, 3, 30);insertEdge(adjList, 2, 4, 40);// 遍歷邊printf("遍歷邊:\n");traverseEdges(adjList[0]);// 更新邊的權重updateEdgeWeight(adjList[0], 0, 1, 50);// 查找邊Edge* edge = findEdge(adjList[0], 0, 1);if (edge != NULL) {printf("找到邊: 目標頂點: %d, 權重: %d\n", edge->dest, edge->weight);}// 判斷邊是否存在if (edgeExists(adjList[0], 0, 1)) {printf("邊存在\n");} else {printf("邊不存在\n");}// 獲取邊的權重int weight = getEdgeWeight(adjList[0], 0, 1);if (weight != -1) {printf("邊的權重: %d\n", weight);}// 刪除邊deleteEdge(adjList, 0, 1);// 再次遍歷邊printf("再次遍歷邊:\n");traverseEdges(adjList[0]);return 0;
}

3.2.3圖類型解析與實現

????????基本概念如下所示:

3.2.3.1無向圖

#include <stdio.h>
#include <stdlib.h>// 定義最大頂點數
#define MAX_VERTEX_NUM 100// 邊的結構體
typedef struct Edge {int dest;           // 目標頂點struct Edge* next;  // 指向下一個邊的指針
} Edge;// 圖的結構體
typedef struct Graph {int numVertices;    // 頂點數量Edge* adjLists[MAX_VERTEX_NUM]; // 鄰接表數組
} Graph;// 創建一個新的邊
Edge* createEdge(int dest) {// 分配內存以存儲新的邊結構體Edge* newEdge = (Edge*)malloc(sizeof(Edge));// 設置邊的目標頂點newEdge->dest = dest;// 將下一個邊指針初始化為NULLnewEdge->next = NULL;// 返回新創建的邊指針return newEdge;
}// 創建圖
Graph* createGraph(int vertices) {// 分配內存以存儲圖結構體Graph* graph = (Graph*)malloc(sizeof(Graph));// 設置圖的頂點數量graph->numVertices = vertices;// 初始化鄰接表for (int i = 0; i < vertices; i++) {// 將每個頂點的鄰接表指針初始化為NULLgraph->adjLists[i] = NULL;}// 返回新創建的圖指針return graph;
}// 添加邊到圖中（無向圖，所以添加兩次）
void addEdge(Graph* graph, int src, int dest) {// 從src到dest// 創建一個新的邊Edge* newEdge = createEdge(dest);// 將新邊的下一個邊指針指向當前頂點的鄰接表newEdge->next = graph->adjLists[src];// 將新邊插入到當前頂點的鄰接表的頭部graph->adjLists[src] = newEdge;// 從dest到src// 創建一個新的邊newEdge = createEdge(src);// 將新邊的下一個邊指針指向當前頂點的鄰接表newEdge->next = graph->adjLists[dest];// 將新邊插入到當前頂點的鄰接表的頭部graph->adjLists[dest] = newEdge;
}// 打印圖的鄰接表
void printGraph(Graph* graph) {// 遍歷每個頂點for (int i = 0; i < graph->numVertices; i++) {// 獲取當前頂點的鄰接表Edge* edge = graph->adjLists[i];// 打印當前頂點的編號printf("頂點 %d 的鄰接頂點: ", i);// 遍歷當前頂點的鄰接表while (edge != NULL) {// 打印鄰接頂點的編號printf("%d ", edge->dest);// 移動到下一個鄰接頂點edge = edge->next;}// 換行printf("\n");}
}int main() {// 創建一個有5個頂點的圖Graph* graph = createGraph(5);// 添加邊addEdge(graph, 0, 1);addEdge(graph, 0, 4);addEdge(graph, 1, 2);addEdge(graph, 1, 3);addEdge(graph, 1, 4);addEdge(graph, 2, 3);addEdge(graph, 3, 4);// 打印圖printGraph(graph);return 0;
}

3.2.3.2有向圖

#include <stdio.h>
#include <stdlib.h>// 定義最大頂點數
#define MAX_VERTEX_NUM 100// 邊的結構體
typedef struct Edge {int dest;           // 目標頂點struct Edge* next;  // 指向下一個邊的指針
} Edge;// 圖的結構體
typedef struct Graph {int numVertices;    // 頂點數量Edge* adjLists[MAX_VERTEX_NUM]; // 鄰接表數組
} Graph;// 創建一個新的邊
Edge* createEdge(int dest) {// 分配內存以存儲新的邊結構體Edge* newEdge = (Edge*)malloc(sizeof(Edge));// 設置邊的目標頂點newEdge->dest = dest;// 將下一個邊指針初始化為NULLnewEdge->next = NULL;// 返回新創建的邊指針return newEdge;
}// 創建圖
Graph* createGraph(int vertices) {// 分配內存以存儲圖結構體Graph* graph = (Graph*)malloc(sizeof(Graph));// 設置圖的頂點數量graph->numVertices = vertices;// 初始化鄰接表for (int i = 0; i < vertices; i++) {// 將每個頂點的鄰接表指針初始化為NULLgraph->adjLists[i] = NULL;}// 返回新創建的圖指針return graph;
}// 添加邊到圖中（有向圖，只添加一次）
void addEdge(Graph* graph, int src, int dest) {// 從src到dest// 創建一個新的邊Edge* newEdge = createEdge(dest);// 將新邊的下一個邊指針指向當前頂點的鄰接表newEdge->next = graph->adjLists[src];// 將新邊插入到當前頂點的鄰接表的頭部graph->adjLists[src] = newEdge;
}// 打印圖的鄰接表
void printGraph(Graph* graph) {// 遍歷每個頂點for (int i = 0; i < graph->numVertices; i++) {// 獲取當前頂點的鄰接表Edge* edge = graph->adjLists[i];// 打印當前頂點的編號printf("頂點 %d 的鄰接頂點: ", i);// 遍歷當前頂點的鄰接表while (edge != NULL) {// 打印鄰接頂點的編號printf("%d ", edge->dest);// 移動到下一個鄰接頂點edge = edge->next;}// 換行printf("\n");}
}int main() {// 創建一個有5個頂點的圖Graph* graph = createGraph(5);// 添加邊addEdge(graph, 0, 1);addEdge(graph, 0, 4);addEdge(graph, 1, 2);addEdge(graph, 1, 3);addEdge(graph, 2, 3);addEdge(graph, 3, 4);// 打印圖printGraph(graph);return 0;
}

3.2.3.3加權圖

#include <stdio.h>
#include <stdlib.h>// 定義最大頂點數
#define MAX_VERTEX_NUM 100// 邊的結構體，包含目標頂點和權重
typedef struct Edge {int dest;           // 目標頂點int weight;         // 邊的權重struct Edge* next;  // 指向下一個邊的指針
} Edge;// 圖的結構體
typedef struct Graph {int numVertices;    // 頂點數量Edge* adjLists[MAX_VERTEX_NUM]; // 鄰接表數組
} Graph;// 創建一個新的帶權重的邊
Edge* createEdge(int dest, int weight) {// 分配內存以存儲新的邊結構體Edge* newEdge = (Edge*)malloc(sizeof(Edge));// 設置邊的目標頂點newEdge->dest = dest;// 設置邊的權重newEdge->weight = weight;// 將下一個邊指針初始化為NULLnewEdge->next = NULL;// 返回新創建的邊指針return newEdge;
}// 創建圖
Graph* createGraph(int vertices) {// 分配內存以存儲圖結構體Graph* graph = (Graph*)malloc(sizeof(Graph));// 設置圖的頂點數量graph->numVertices = vertices;// 初始化鄰接表for (int i = 0; i < vertices; i++) {// 將每個頂點的鄰接表指針初始化為NULLgraph->adjLists[i] = NULL;}// 返回新創建的圖指針return graph;
}// 添加帶權重的邊到圖中（無向圖，所以添加兩次）
void addEdge(Graph* graph, int src, int dest, int weight) {// 從src到dest// 創建一個新的邊Edge* newEdge = createEdge(dest, weight);// 將新邊的下一個邊指針指向當前頂點的鄰接表newEdge->next = graph->adjLists[src];// 將新邊插入到當前頂點的鄰接表的頭部graph->adjLists[src] = newEdge;// 從dest到src// 創建一個新的邊newEdge = createEdge(src, weight);// 將新邊的下一個邊指針指向當前頂點的鄰接表newEdge->next = graph->adjLists[dest];// 將新邊插入到當前頂點的鄰接表的頭部graph->adjLists[dest] = newEdge;
}// 打印圖的鄰接表
void printGraph(Graph* graph) {// 遍歷每個頂點for (int i = 0; i < graph->numVertices; i++) {// 獲取當前頂點的鄰接表Edge* edge = graph->adjLists[i];// 打印當前頂點的編號printf("頂點 %d 的鄰接頂點及權重: ", i);// 遍歷當前頂點的鄰接表while (edge != NULL) {// 打印鄰接頂點的編號和權重printf("(%d, %d) ", edge->dest, edge->weight);// 移動到下一個鄰接頂點edge = edge->next;}// 換行printf("\n");}
}int main() {// 創建一個有5個頂點的圖Graph* graph = createGraph(5);// 添加帶權重的邊addEdge(graph, 0, 1, 10);addEdge(graph, 0, 4, 20);addEdge(graph, 1, 2, 30);addEdge(graph, 1, 3, 40);addEdge(graph, 1, 4, 50);addEdge(graph, 2, 3, 60);addEdge(graph, 3, 4, 70);// 打印圖printGraph(graph);return 0;
}

3.2.3.4無權圖

#include <stdio.h>
#include <stdlib.h>// 定義最大頂點數
#define MAX_VERTEX_NUM 100// 邊的結構體
typedef struct Edge {int dest;           // 目標頂點struct Edge* next;  // 指向下一個邊的指針
} Edge;// 圖的結構體
typedef struct Graph {int numVertices;    // 頂點數量Edge* adjLists[MAX_VERTEX_NUM]; // 鄰接表數組
} Graph;// 創建一個新的邊
Edge* createEdge(int dest) {// 分配內存以存儲新的邊結構體Edge* newEdge = (Edge*)malloc(sizeof(Edge));// 設置邊的目標頂點newEdge->dest = dest;// 將下一個邊指針初始化為NULLnewEdge->next = NULL;// 返回新創建的邊指針return newEdge;
}// 創建圖
Graph* createGraph(int vertices) {// 分配內存以存儲圖結構體Graph* graph = (Graph*)malloc(sizeof(Graph));// 設置圖的頂點數量graph->numVertices = vertices;// 初始化鄰接表for (int i = 0; i < vertices; i++) {// 將每個頂點的鄰接表指針初始化為NULLgraph->adjLists[i] = NULL;}// 返回新創建的圖指針return graph;
}// 添加邊到圖中（無向圖，所以添加兩次）
void addEdge(Graph* graph, int src, int dest) {// 從src到dest// 創建一個新的邊Edge* newEdge = createEdge(dest);// 將新邊的下一個邊指針指向當前頂點的鄰接表newEdge->next = graph->adjLists[src];// 將新邊插入到當前頂點的鄰接表的頭部graph->adjLists[src] = newEdge;// 從dest到src// 創建一個新的邊newEdge = createEdge(src);// 將新邊的下一個邊指針指向當前頂點的鄰接表newEdge->next = graph->adjLists[dest];// 將新邊插入到當前頂點的鄰接表的頭部graph->adjLists[dest] = newEdge;
}// 打印圖的鄰接表
void printGraph(Graph* graph) {// 遍歷每個頂點for (int i = 0; i < graph->numVertices; i++) {// 獲取當前頂點的鄰接表Edge* edge = graph->adjLists[i];// 打印當前頂點的編號printf("頂點 %d 的鄰接頂點: ", i);// 遍歷當前頂點的鄰接表while (edge != NULL) {// 打印鄰接頂點的編號printf("%d ", edge->dest);// 移動到下一個鄰接頂點edge = edge->next;}// 換行printf("\n");}
}int main() {// 創建一個有5個頂點的圖Graph* graph = createGraph(5);// 添加邊addEdge(graph, 0, 1);addEdge(graph, 0, 4);addEdge(graph, 1, 2);addEdge(graph, 1, 3);addEdge(graph, 2, 3);addEdge(graph, 3, 4);// 打印圖printGraph(graph);return 0;
}

3.2.3.5稠密圖

#include <stdio.h>
#include <stdbool.h>// 定義最大頂點數
#define MAX_VERTEX_NUM 100// 圖的結構體，使用鄰接矩陣表示
typedef struct Graph {int numVertices;    // 頂點數量bool adjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 鄰接矩陣
} Graph;// 創建圖
Graph* createGraph(int vertices) {// 分配內存以存儲圖結構體Graph* graph = (Graph*)malloc(sizeof(Graph));// 設置圖的頂點數量graph->numVertices = vertices;// 初始化鄰接矩陣為false（表示無連接）for (int i = 0; i < vertices; i++) {for (int j = 0; j < vertices; j++) {graph->adjMatrix[i][j] = false;}}// 返回新創建的圖指針return graph;
}// 添加邊到圖中（無向圖）
void addEdge(Graph* graph, int src, int dest) {// 檢查源頂點和目標頂點是否在有效范圍內if (src >= 0 && src < graph->numVertices && dest >= 0 && dest < graph->numVertices) {// 在鄰接矩陣中標記源頂點到目標頂點的邊graph->adjMatrix[src][dest] = true;// 在鄰接矩陣中標記目標頂點到源頂點的邊（因為是無向圖）graph->adjMatrix[dest][src] = true;}
}// 打印圖的鄰接矩陣
void printGraph(Graph* graph) {// 遍歷鄰接矩陣的每一行for (int i = 0; i < graph->numVertices; i++) {// 遍歷鄰接矩陣的每一列for (int j = 0; j < graph->numVertices; j++) {// 打印鄰接矩陣中的元素（0或1）printf("%d ", graph->adjMatrix[i][j]);}// 換行printf("\n");}
}int main() {// 創建一個有5個頂點的圖Graph* graph = createGraph(5);// 添加邊addEdge(graph, 0, 1);addEdge(graph, 0, 4);addEdge(graph, 1, 2);addEdge(graph, 1, 3);addEdge(graph, 1, 4);addEdge(graph, 2, 3);addEdge(graph, 3, 4);// 打印圖的鄰接矩陣printGraph(graph);return 0;
}

3.2.3.6稀疏圖

#include <stdio.h>
#include <stdlib.h>// 定義最大頂點數
#define MAX_VERTEX_NUM 100// 邊的結構體
typedef struct Edge {int dest;           // 目標頂點struct Edge* next;  // 指向下一個邊的指針
} Edge;// 圖的結構體，使用鄰接表表示
typedef struct Graph {int numVertices;    // 頂點數量Edge* adjLists[MAX_VERTEX_NUM]; // 鄰接表數組
} Graph;// 創建一個新的邊
Edge* createEdge(int dest) {// 分配內存以存儲新的邊結構體Edge* newEdge = (Edge*)malloc(sizeof(Edge));// 設置邊的目標頂點newEdge->dest = dest;// 將下一個邊指針初始化為NULLnewEdge->next = NULL;// 返回新創建的邊指針return newEdge;
}// 創建圖
Graph* createGraph(int vertices) {// 分配內存以存儲圖結構體Graph* graph = (Graph*)malloc(sizeof(Graph));// 設置圖的頂點數量graph->numVertices = vertices;// 初始化鄰接表為空for (int i = 0; i < vertices; i++) {// 將每個頂點的鄰接表指針初始化為NULLgraph->adjLists[i] = NULL;}// 返回新創建的圖指針return graph;
}// 添加邊到圖中（無向圖）
void addEdge(Graph* graph, int src, int dest) {// 檢查源頂點和目標頂點是否在有效范圍內if (src >= 0 && src < graph->numVertices && dest >= 0 && dest < graph->numVertices) {// 從src到dest// 創建一個新的邊Edge* newEdge = createEdge(dest);// 將新邊的下一個邊指針指向當前頂點的鄰接表newEdge->next = graph->adjLists[src];// 將新邊插入到當前頂點的鄰接表的頭部graph->adjLists[src] = newEdge;// 如果是無向圖，還需要從dest到src// 創建一個新的邊newEdge = createEdge(src);// 將新邊的下一個邊指針指向當前頂點的鄰接表newEdge->next = graph->adjLists[dest];// 將新邊插入到當前頂點的鄰接表的頭部graph->adjLists[dest] = newEdge;}
}// 打印圖的鄰接表
void printGraph(Graph* graph) {// 遍歷每個頂點for (int i = 0; i < graph->numVertices; i++) {// 獲取當前頂點的鄰接表Edge* edge = graph->adjLists[i];// 打印當前頂點的編號printf("頂點 %d 的鄰接頂點: ", i);// 遍歷當前頂點的鄰接表while (edge != NULL) {// 打印鄰接頂點的編號printf("%d ", edge->dest);// 移動到下一個鄰接頂點edge = edge->next;}// 換行printf("\n");}
}int main() {// 創建一個有5個頂點的圖Graph* graph = createGraph(5);// 添加邊addEdge(graph, 0, 1);addEdge(graph, 0, 4);addEdge(graph, 1, 2);addEdge(graph, 1, 3);addEdge(graph, 2, 3);addEdge(graph, 3, 4);// 打印圖的鄰接表printGraph(graph);return 0;
}

3.2.3.7完全圖

#include <stdio.h>
#include <stdbool.h>// 定義最大頂點數
#define MAX_VERTEX_NUM 100// 圖的結構體，使用鄰接矩陣表示
typedef struct Graph {int numVertices;    // 頂點數量bool adjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 鄰接矩陣
} Graph;// 創建完全圖
Graph* createCompleteGraph(int vertices) {// 分配內存以存儲圖結構體Graph* graph = (Graph*)malloc(sizeof(Graph));// 設置圖的頂點數量graph->numVertices = vertices;// 初始化鄰接矩陣，完全圖中每對頂點間都有邊for (int i = 0; i < vertices; i++) {for (int j = 0; j < vertices; j++) {if (i == j) {// 頂點不與自身相連graph->adjMatrix[i][j] = false;} else {// 其他情況都有邊相連graph->adjMatrix[i][j] = true;}}}// 返回新創建的圖指針return graph;
}// 打印圖的鄰接矩陣
void printGraph(Graph* graph) {// 遍歷鄰接矩陣的每一行for (int i = 0; i < graph->numVertices; i++) {// 遍歷鄰接矩陣的每一列for (int j = 0; j < graph->numVertices; j++) {// 打印鄰接矩陣中的元素（0或1）printf("%d ", graph->adjMatrix[i][j]);}// 換行printf("\n");}
}int main() {// 創建一個有5個頂點的完全圖Graph* graph = createCompleteGraph(5);// 打印圖的鄰接矩陣printGraph(graph);return 0;
}

3.2.3.8強連通圖

#include <stdio.h>
#include <stdlib.h>// 定義最大頂點數
#define MAX_VERTEX_NUM 100// 邊的結構體
typedef struct Edge {int dest;           // 目標頂點struct Edge* next;  // 指向下一個邊的指針
} Edge;// 圖的結構體，使用鄰接表表示
typedef struct Graph {int numVertices;    // 頂點數量Edge* adjLists[MAX_VERTEX_NUM]; // 鄰接表數組
} Graph;// 創建一個新的邊
Edge* createEdge(int dest) {// 分配內存以存儲新的邊結構體Edge* newEdge = (Edge*)malloc(sizeof(Edge));// 設置邊的目標頂點newEdge->dest = dest;// 將下一個邊指針初始化為NULLnewEdge->next = NULL;// 返回新創建的邊指針return newEdge;
}// 創建圖
Graph* createGraph(int vertices) {// 分配內存以存儲圖結構體Graph* graph = (Graph*)malloc(sizeof(Graph));// 設置圖的頂點數量graph->numVertices = vertices;// 初始化鄰接表為空for (int i = 0; i < vertices; i++) {// 將每個頂點的鄰接表指針初始化為NULLgraph->adjLists[i] = NULL;}// 返回新創建的圖指針return graph;
}// 添加邊到圖中（有向圖）
void addEdge(Graph* graph, int src, int dest) {// 檢查源頂點和目標頂點是否在有效范圍內if (src >= 0 && src < graph->numVertices && dest >= 0 && dest < graph->numVertices) {// 從src到dest// 創建一個新的邊Edge* newEdge = createEdge(dest);// 將新邊的下一個邊指針指向當前頂點的鄰接表newEdge->next = graph->adjLists[src];// 將新邊插入到當前頂點的鄰接表的頭部graph->adjLists[src] = newEdge;}
}// 打印圖的鄰接表
void printGraph(Graph* graph) {for (int i = 0; i < graph->numVertices; i++) {Edge* edge = graph->adjLists[i];printf("頂點 %d 的鄰接頂點: ", i);while (edge != NULL) {printf("%d ", edge->dest);edge = edge->next;}printf("\n");}
}int main() {// 創建一個有4個頂點的圖Graph* graph = createGraph(4);// 添加邊以形成強連通圖addEdge(graph, 0, 1);addEdge(graph, 1, 2);addEdge(graph, 2, 3);addEdge(graph, 3, 0);addEdge(graph, 1, 3);addEdge(graph, 3, 1);addEdge(graph, 2, 0);addEdge(graph, 0, 2);// 打印圖的鄰接表printGraph(graph);return 0;
}

3.2.3.9并查集

#include <stdio.h>
#include <stdlib.h>// 定義最大頂點數
#define MAX_VERTEX_NUM 100// 并查集結構體
typedef struct UnionFind {int parent[MAX_VERTEX_NUM]; // 存儲每個頂點的父節點int rank[MAX_VERTEX_NUM];   // 存儲每個頂點的秩（樹的高度）
} UnionFind;// 初始化并查集
void initUnionFind(UnionFind* uf, int vertices) {for (int i = 0; i < vertices; i++) {uf->parent[i] = i; // 初始時，每個頂點的父節點是它自己uf->rank[i] = 0;   // 初始時，每個頂點的秩為0}
}// 查找頂點的根節點
int find(UnionFind* uf, int x) {if (uf->parent[x] != x) {uf->parent[x] = find(uf, uf->parent[x]); // 路徑壓縮}return uf->parent[x];
}// 合并兩個集合
void unionSets(UnionFind* uf, int x, int y) {int rootX = find(uf, x);int rootY = find(uf, y);if (rootX != rootY) {if (uf->rank[rootX] < uf->rank[rootY]) {uf->parent[rootX] = rootY; // 將秩小的樹合并到秩大的樹上} else if (uf->rank[rootX] > uf->rank[rootY]) {uf->parent[rootY] = rootX;} else {uf->parent[rootY] = rootX;uf->rank[rootX]++; // 秩相同，合并后秩加1}}
}// 檢查兩個頂點是否在同一個集合中
int isConnected(UnionFind* uf, int x, int y) {return find(uf, x) == find(uf, y);
}int main() {// 創建一個有4個頂點的圖int vertices = 4;UnionFind uf;initUnionFind(&uf, vertices);// 添加邊以形成強連通圖unionSets(&uf, 0, 1);unionSets(&uf, 1, 2);unionSets(&uf, 2, 3);unionSets(&uf, 3, 0);unionSets(&uf, 1, 3);unionSets(&uf, 3, 1);unionSets(&uf, 2, 0);unionSets(&uf, 0, 2);// 檢查頂點是否連通printf("頂點0和頂點1是否連通: %d\n", isConnected(&uf, 0, 1));printf("頂點0和頂點2是否連通: %d\n", isConnected(&uf, 0, 2));printf("頂點0和頂點3是否連通: %d\n", isConnected(&uf, 0, 3));return 0;
}

3.2.4圖的表示方法

? ? ? ? 圖的表示方法概念如下所示:? ? ? ??

3.2.4.1領接矩陣

#include <stdio.h>
#include <stdbool.h>// 定義最大頂點數
#define MAX_VERTEX_NUM 100// 圖的結構體，使用鄰接矩陣表示
typedef struct Graph {int numVertices;    // 頂點數量bool adjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 鄰接矩陣
} Graph;// 創建圖
Graph* createGraph(int vertices) {// 分配內存以存儲圖結構體Graph* graph = (Graph*)malloc(sizeof(Graph));// 設置圖的頂點數量graph->numVertices = vertices;// 初始化鄰接矩陣，無連接時設為falsefor (int i = 0; i < vertices; i++) {for (int j = 0; j < vertices; j++) {graph->adjMatrix[i][j] = false;}}// 返回新創建的圖指針return graph;
}// 添加邊到圖中（無向圖）
void addEdge(Graph* graph, int src, int dest) {// 檢查源頂點和目標頂點是否在有效范圍內if (src >= 0 && src < graph->numVertices && dest >= 0 && dest < graph->numVertices) {// 設置鄰接矩陣中對應位置為true，表示有邊連接graph->adjMatrix[src][dest] = true;// 如果是無向圖，對稱位置也需要設置為truegraph->adjMatrix[dest][src] = true;}
}// 打印圖的鄰接矩陣
void printGraph(Graph* graph) {for (int i = 0; i < graph->numVertices; i++) {for (int j = 0; j < graph->numVertices; j++) {// 打印鄰接矩陣中的元素（0或1）printf("%d ", graph->adjMatrix[i][j]);}// 換行printf("\n");}
}int main() {// 創建一個有5個頂點的圖Graph* graph = createGraph(5);// 添加邊addEdge(graph, 0, 1);addEdge(graph, 0, 4);addEdge(graph, 1, 2);addEdge(graph, 1, 3);addEdge(graph, 1, 4);addEdge(graph, 2, 3);addEdge(graph, 3, 4);// 打印圖的鄰接矩陣printGraph(graph);return 0;
}

3.2.4.2鄰接表

#include <stdio.h>
#include <stdlib.h>// 定義最大頂點數
#define MAX_VERTEX_NUM 100// 邊的結構體
typedef struct Edge {int dest;           // 目標頂點struct Edge* next;  // 指向下一個邊的指針
} Edge;// 圖的結構體，使用鄰接表表示
typedef struct Graph {int numVertices;    // 頂點數量Edge* adjLists[MAX_VERTEX_NUM]; // 鄰接表數組
} Graph;// 創建一個新的邊
Edge* createEdge(int dest) {// 分配內存以存儲新的邊結構體Edge* newEdge = (Edge*)malloc(sizeof(Edge));// 設置邊的目標頂點newEdge->dest = dest;// 將下一個邊指針初始化為NULLnewEdge->next = NULL;// 返回新創建的邊指針return newEdge;
}// 創建圖
Graph* createGraph(int vertices) {// 分配內存以存儲圖結構體Graph* graph = (Graph*)malloc(sizeof(Graph));// 設置圖的頂點數量graph->numVertices = vertices;// 初始化鄰接表為空for (int i = 0; i < vertices; i++) {// 將每個頂點的鄰接表指針初始化為NULLgraph->adjLists[i] = NULL;}// 返回新創建的圖指針return graph;
}// 添加邊到圖中（有向圖）
void addEdge(Graph* graph, int src, int dest) {// 檢查源頂點和目標頂點是否在有效范圍內if (src >= 0 && src < graph->numVertices && dest >= 0 && dest < graph->numVertices) {// 從src到dest// 創建一個新的邊Edge* newEdge = createEdge(dest);// 將新邊的下一個邊指針指向當前頂點的鄰接表newEdge->next = graph->adjLists[src];// 將新邊插入到當前頂點的鄰接表的頭部graph->adjLists[src] = newEdge;}
}// 打印圖的鄰接表
void printGraph(Graph* graph) {for (int i = 0; i < graph->numVertices; i++) {Edge* edge = graph->adjLists[i];printf("頂點 %d 的鄰接頂點: ", i);while (edge != NULL) {printf("%d ", edge->dest);edge = edge->next;}printf("\n");}
}int main() {// 創建一個有4個頂點的圖Graph* graph = createGraph(4);// 添加邊以形成特定的圖結構addEdge(graph, 0, 1);addEdge(graph, 0, 2);addEdge(graph, 1, 2);addEdge(graph, 2, 0);addEdge(graph, 2, 3);addEdge(graph, 3, 3);// 打印圖的鄰接表printGraph(graph);return 0;
}

3.2..4.3邊緣列表

#include <stdio.h>
#include <stdlib.h>// 定義最大邊數
#define MAX_EDGE_NUM 100// 邊的結構體
typedef struct Edge {int src;    // 邊的起始頂點int dest;   // 邊的目標頂點// 可選：int weight; // 邊的權重（如果是有權圖）struct Edge* next; // 指向下一個邊的指針
} Edge;// 圖的結構體，使用邊緣列表表示
typedef struct Graph {int numVertices;    // 頂點數量int numEdges;       // 邊的數量Edge* edgeList[MAX_EDGE_NUM]; // 邊緣列表數組
} Graph;// 創建一個新的邊
Edge* createEdge(int src, int dest) {// 分配內存以存儲新的邊結構體Edge* newEdge = (Edge*)malloc(sizeof(Edge));// 設置邊的起始頂點newEdge->src = src;// 設置邊的目標頂點newEdge->dest = dest;// 將下一個邊指針初始化為NULLnewEdge->next = NULL;// 返回新創建的邊指針return newEdge;
}// 創建圖
Graph* createGraph(int vertices, int edges) {// 分配內存以存儲圖結構體Graph* graph = (Graph*)malloc(sizeof(Graph));// 設置圖的頂點數量graph->numVertices = vertices;// 設置圖的邊數量graph->numEdges = edges;// 初始化邊緣列表為空for (int i = 0; i < edges; i++) {// 將每個邊緣列表指針初始化為NULLgraph->edgeList[i] = NULL;}// 返回新創建的圖指針return graph;
}// 添加邊到圖中
void addEdge(Graph* graph, int index, int src, int dest) {// 檢查索引是否在有效范圍內if (index >= 0 && index < graph->numEdges) {// 在指定索引處創建一個新的邊graph->edgeList[index] = createEdge(src, dest);}
}// 打印圖的邊緣列表
void printGraph(Graph* graph) {printf("圖的邊緣列表:\n");for (int i = 0; i < graph->numEdges; i++) {Edge* edge = graph->edgeList[i];if (edge != NULL) {// 打印每條邊的起始頂點和目標頂點printf("邊 %d: %d -> %d\n", i, edge->src, edge->dest);}}
}int main() {// 創建一個有4個頂點和5條邊的圖Graph* graph = createGraph(4, 5);// 添加邊以形成特定的圖結構addEdge(graph, 0, 0, 1);addEdge(graph, 1, 0, 2);addEdge(graph, 2, 1, 2);addEdge(graph, 3, 2, 0);addEdge(graph, 4, 2, 3);// 打印圖的邊緣列表printGraph(graph);return 0;
}

3.3散列表（哈希表）

? ? ? ? 基礎概念如下所示:

3.3.1散列表結構定義

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define TABLE_SIZE 10 // 散列表的大小// 鍵值對結構體
typedef struct {char* key;       // 鍵int value;       // 值
} KeyValuePair;// 散列表節點結構體
typedef struct HashNode {KeyValuePair pair; // 存儲鍵值對struct HashNode* next; // 指向下一個節點的指針，用于處理沖突
} HashNode;// 散列表結構體
typedef struct {HashNode* buckets[TABLE_SIZE]; // 哈希表數組，每個元素是一個鏈表的頭節點
} HashTable;

3.3.2哈希函數定義

// 將字符串鍵轉換為整數索引
unsigned int hashFunction(const char* key) {unsigned int hash = 0; // 初始化哈希值為0while (*key) { // 遍歷字符串中的每個字符hash = (hash << 5) + *key++; // 將當前哈希值左移5位，并加上當前字符的ASCII值}return hash % TABLE_SIZE; // 返回哈希值對散列表大小取模的結果，確保索引在散列表范圍內
}

3.3.3創建和初始化散列表

// 創建哈希表
HashTable* createHashTable() {// 分配內存以存儲哈希表結構體HashTable* table = (HashTable*)malloc(sizeof(HashTable));// 初始化哈希表的每個桶為空for (int i = 0; i < TABLE_SIZE; i++) {table->buckets[i] = NULL;}// 返回創建的哈希表指針return table;
}

3.3.4插入或更新鍵值對

// 插入或更新鍵值對
void insertOrUpdate(HashTable* table, const char* key, int value) {unsigned int index = hashFunction(key); // 計算鍵的哈希值，獲取對應的桶索引HashNode* node = table->buckets[index]; // 獲取桶的頭節點// 搜索鍵是否已存在，若存在則更新值while (node != NULL) {if (strcmp(node->pair.key, key) == 0) { // 比較當前節點的鍵與傳入的鍵node->pair.value = value; // 更新值return; // 結束函數}node = node->next; // 移動到下一個節點}// 若鍵不存在，則創建新節點并插入node = (HashNode*)malloc(sizeof(HashNode)); // 分配新節點的內存if (node == NULL) { // 檢查內存分配是否成功fprintf(stderr, "內存分配失敗\n"); // 輸出錯誤信息exit(1); // 終止程序}node->pair.key = strdup(key); // 復制鍵字符串到新節點node->pair.value = value; // 設置新節點的值node->next = table->buckets[index]; // 將新節點的下一個指針指向當前桶的頭節點table->buckets[index] = node; // 將新節點設置為桶的頭節點
}

3.3.5查找鍵對應的值

// 在哈希表中查找鍵對應的值
int find(HashTable* table, const char* key) {unsigned int index = hashFunction(key); // 計算鍵的哈希值，獲取對應的桶索引HashNode* node = table->buckets[index]; // 獲取桶的頭節點while (node != NULL) { // 遍歷桶中的鏈表if (strcmp(node->pair.key, key) == 0) { // 比較當前節點的鍵與傳入的鍵return node->pair.value; // 如果找到匹配的鍵，返回對應的值}node = node->next; // 移動到下一個節點}return -1; // 表示未找到
}

3.3.6散列表代碼匯總

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define TABLE_SIZE 10// 鍵值對結構體
typedef struct {char* key;       // 鍵int value;       // 值
} KeyValuePair;// 散列表節點結構體（鏈地址法處理沖突）
typedef struct HashNode {KeyValuePair pair; // 存儲鍵值對struct HashNode* next; // 指向下一個節點的指針，用于處理沖突
} HashNode;// 散列表結構體
typedef struct {HashNode* buckets[TABLE_SIZE]; // 哈希表數組，每個元素是一個鏈表的頭節點
} HashTable;// 哈希函數
unsigned int hashFunction(const char* key) {unsigned int hash = 0;while (*key) {hash = (hash << 5) + *key++; // 將當前哈希值左移5位，并加上當前字符的ASCII值}return hash % TABLE_SIZE; // 返回哈希值對散列表大小取模的結果，確保索引在散列表范圍內
}// 創建散列表
HashTable* createHashTable() {HashTable* table = (HashTable*)malloc(sizeof(HashTable)); // 分配內存以存儲哈希表結構體if (table == NULL) {fprintf(stderr, "內存分配失敗\n"); // 錯誤處理exit(1);}for (int i = 0; i < TABLE_SIZE; i++) {table->buckets[i] = NULL; // 初始化哈希表的每個桶為空}return table;
}// 插入或更新鍵值對
void insertOrUpdate(HashTable* table, const char* key, int value) {unsigned int index = hashFunction(key); // 計算鍵的哈希值，獲取對應的桶索引HashNode* node = table->buckets[index]; // 獲取桶的頭節點while (node!= NULL) { // 遍歷桶中的鏈表if (strcmp(node->pair.key, key) == 0) { // 比較當前節點的鍵與傳入的鍵node->pair.value = value; // 如果鍵已存在，更新值return;}node = node->next; // 移動到下一個節點}node = (HashNode*)malloc(sizeof(HashNode)); // 分配新節點的內存if (node == NULL) {fprintf(stderr, "內存分配失敗\n");exit(1);}node->pair.key = strdup(key); // 復制鍵字符串到新節點node->pair.value = value; // 設置新節點的值node->next = table->buckets[index]; // 將新節點的下一個指針指向當前桶的頭節點table->buckets[index] = node; // 將新節點設置為桶的頭節點
}// 查找鍵對應的值
int find(HashTable* table, const char* key) {unsigned int index = hashFunction(key); // 計算鍵的哈希值，獲取對應的桶索引HashNode* node = table->buckets[index]; // 獲取桶的頭節點while (node!= NULL) { // 遍歷桶中的鏈表if (strcmp(node->pair.key, key) == 0) { // 比較當前節點的鍵與傳入的鍵return node->pair.value; // 如果找到匹配的鍵，返回對應的值}node = node->next; // 移動到下一個節點}return -1; // 表示未找到
}// 刪除鍵值對
void delete(HashTable* table, const char* key) {unsigned int index = hashFunction(key); // 計算鍵的哈希值，獲取對應的桶索引HashNode* node = table->buckets[index]; // 獲取桶的頭節點HashNode* prev = NULL; // 用于記錄當前節點的前一個節點while (node!= NULL) { // 遍歷桶中的鏈表if (strcmp(node->pair.key, key) == 0) { // 比較當前節點的鍵與傳入的鍵if (prev == NULL) { // 如果當前節點是桶的頭節點table->buckets[index] = node->next; // 將桶的頭節點指向下一個節點} else {prev->next = node->next; // 將前一個節點的下一個指針指向當前節點的下一個節點}free(node->pair.key); // 釋放鍵字符串的內存free(node); // 釋放當前節點的內存return;}prev = node; // 記錄當前節點為前一個節點node = node->next; // 移動到下一個節點}
}// 打印散列表（用于調試）
void printHashTable(HashTable* table) {for (int i = 0; i < TABLE_SIZE; i++) {HashNode* node = table->buckets[i];printf("Bucket %d: ", i);while (node!= NULL) {printf("(%s, %d) -> ", node->pair.key, node->pair.value);node = node->next;}printf("NULL\n");}
}// 釋放散列表內存
void freeHashTable(HashTable* table) {for (int i = 0; i < TABLE_SIZE; i++) {HashNode* node = table->buckets[i];while (node!= NULL) {HashNode* next = node->next;free(node->pair.key); // 釋放鍵字符串的內存free(node); // 釋放當前節點的內存node = next; // 移動到下一個節點}}free(table); // 釋放哈希表結構體的內存
}int main() {HashTable* table = createHashTable(); // 創建哈希表insertOrUpdate(table, "apple", 1); // 插入鍵值對insertOrUpdate(table, "banana", 2);insertOrUpdate(table, "orange", 3);printf("apple: %d\n", find(table, "apple")); // 查找鍵對應的值printf("banana: %d\n", find(table, "banana"));printf("orange: %d\n", find(table, "orange"));delete(table, "banana"); // 刪除鍵值對printf("After deleting banana:\n");printHashTable(table); // 打印哈希表freeHashTable(table); // 釋放哈希表內存return 0;
}

4.特殊數據結構

? ? ? ? 基礎概念如下所示:

4.1Trie樹（又稱前綴樹）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define ALPHABET_SIZE 26 // 字母表大小，假設只處理小寫字母// Trie樹節點結構體
typedef struct TrieNode {struct TrieNode* children[ALPHABET_SIZE]; // 子節點指針數組，每個元素對應一個字母int isEndOfWord; // 標記該節點是否為單詞的結尾
} TrieNode;// 創建新的Trie樹節點
TrieNode* createNode() {TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode)); // 分配內存if (node) {node->isEndOfWord = 0; // 初始化節點，不是單詞結尾for (int i = 0; i < ALPHABET_SIZE; i++) {node->children[i] = NULL; // 初始化子節點指針為空}}return node;
}// 插入字符串到Trie樹
void insert(TrieNode* root, const char* key) {TrieNode* node = root;for (int i = 0; key[i] != '\0'; i++) {int index = key[i] - 'a'; // 計算字符在字母表中的索引if (!node->children[index]) {node->children[index] = createNode(); // 如果子節點不存在，創建新節點}node = node->children[index]; // 移動到下一個節點}node->isEndOfWord = 1; // 標記當前節點為單詞結尾
}// 在Trie樹中搜索字符串
int search(TrieNode* root, const char* key) {TrieNode* node = root;for (int i = 0; key[i] != '\0'; i++) {int index = key[i] - 'a'; // 計算字符在字母表中的索引if (!node->children[index]) {return 0; // 如果子節點不存在，說明字符串不存在}node = node->children[index]; // 移動到下一個節點}return (node != NULL && node->isEndOfWord); // 返回是否找到單詞
}// 釋放Trie樹的內存
void freeTrie(TrieNode* root) {if (root == NULL) {return;}for (int i = 0; i < ALPHABET_SIZE; i++) {if (root->children[i]) {freeTrie(root->children[i]); // 遞歸釋放子節點內存}}free(root); // 釋放當前節點內存
}int main() {TrieNode* root = createNode(); // 創建Trie樹的根節點// 插入一些單詞insert(root, "apple");insert(root, "banana");insert(root, "cherry");// 搜索單詞printf("Search 'apple': %s\n", search(root, "apple") ? "Found" : "Not Found");printf("Search 'banana': %s\n", search(root, "banana") ? "Found" : "Not Found");printf("Search 'cherry': %s\n", search(root, "cherry") ? "Found" : "Not Found");printf("Search 'grape': %s\n", search(root, "grape") ? "Found" : "Not Found");// 釋放Trie樹的內存freeTrie(root);return 0;
}

4.2并查集

????????是一種數據結構，用于處理一些不相交集合的合并及查詢問題。它主要支持以下兩種操作

? ? ? ? ?(1)查找（Find）：確定某個元素屬于哪個集合。

? ? ? ? (2)合并（Union）：將兩個集合合并成一個集合。

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100 // 并查集的最大元素數量// 并查集結構體
typedef struct {int parent[MAX_SIZE]; // 父節點數組，用于存儲每個元素的父節點int rank[MAX_SIZE];   // 秩數組，用于存儲每個集合的秩（樹的高度）
} DisjointSet;// 初始化并查集
void makeSet(DisjointSet* ds, int n) {for (int i = 0; i < n; i++) {ds->parent[i] = i; // 初始時每個元素的父節點是自己ds->rank[i] = 0;   // 初始時秩為0}
}// 查找根節點，并進行路徑壓縮
int find(DisjointSet* ds, int x) {if (ds->parent[x] != x) {ds->parent[x] = find(ds, ds->parent[x]); // 路徑壓縮，將x的父節點直接指向根節點}return ds->parent[x];
}// 合并兩個集合，按秩合并
void unionSets(DisjointSet* ds, int x, int y) {int rootX = find(ds, x);int rootY = find(ds, y);if (rootX != rootY) {if (ds->rank[rootX] < ds->rank[rootY]) {ds->parent[rootX] = rootY; // 將秩小的集合合并到秩大的集合} else if (ds->rank[rootX] > ds->rank[rootY]) {ds->parent[rootY] = rootX;} else {ds->parent[rootY] = rootX; // 秩相等時，任選一個作為根節點，并增加其秩ds->rank[rootX]++;}}
}// 示例使用
int main() {DisjointSet ds;int n = 10; // 假設有10個元素makeSet(&ds, n); // 初始化并查集unionSets(&ds, 1, 2); // 合并元素1和元素2所在的集合unionSets(&ds, 3, 4); // 合并元素3和元素4所在的集合unionSets(&ds, 1, 4); // 合并元素1和元素4所在的集合printf("元素1和元素4是否在同一個集合中？%s\n",find(&ds, 1) == find(&ds, 4) ? "是" : "否"); // 查找元素1和元素4是否在同一個集合中printf("元素1和元素5是否在同一個集合中？%s\n",find(&ds, 1) == find(&ds, 5) ? "是" : "否"); // 查找元素1和元素5是否在同一個集合中return 0;
}

4.3跳表

????????是一種基于鏈表的數據結構，用于高效地實現有序集合的插入、刪除和查找操作。它通過在鏈表中添加多級索引來提高查找效率，類似于二分查找的思想。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>#define MAX_LEVEL 16 // 跳表的最大層數// 跳表節點結構體
typedef struct SkipListNode {int key; // 鍵int value; // 值struct SkipListNode* forward[MAX_LEVEL]; // 指向不同層的下一個節點
} SkipListNode;// 跳表結構體
typedef struct {SkipListNode* header; // 跳表的頭節點int level; // 跳表的當前層數
} SkipList;// 創建新的跳表節點
SkipListNode* createNode(int key, int value, int level) {SkipListNode* node = (SkipListNode*)malloc(sizeof(SkipListNode)); // 分配內存if (node) {node->key = key; // 設置鍵node->value = value; // 設置值for (int i = 0; i < level; i++) {node->forward[i] = NULL; // 初始化指向不同層的下一個節點的指針為NULL}}return node;
}// 創建新的跳表
SkipList* createSkipList() {SkipList* list = (SkipList*)malloc(sizeof(SkipList)); // 分配內存if (list) {list->header = createNode(0, 0, MAX_LEVEL); // 創建頭節點，鍵和值都為0，層數為最大層數list->level = 1; // 初始時跳表的層數為1}return list;
}// 生成隨機層數
int randomLevel() {int level = 1;while (rand() < RAND_MAX / 2 && level < MAX_LEVEL) {level++; // 以一定概率增加層數，直到達到最大層數}return level;
}// 插入鍵值對到跳表
void insert(SkipList* list, int key, int value) {SkipListNode* update[MAX_LEVEL]; // 用于記錄插入位置的前驅節點SkipListNode* current = list->header;for (int i = list->level - 1; i >= 0; i--) {while (current->forward[i] && current->forward[i]->key < key) {current = current->forward[i]; // 在當前層找到插入位置的前驅節點}update[i] = current;}current = current->forward[0];if (current == NULL || current->key != key) {int newLevel = randomLevel(); // 生成新節點的隨機層數if (newLevel > list->level) {for (int i = list->level; i < newLevel; i++) {update[i] = list->header; // 更新新層的前驅節點為頭節點}list->level = newLevel; // 更新跳表的層數}SkipListNode* newNode = createNode(key, value, newLevel); // 創建新節點for (int i = 0; i < newLevel; i++) {newNode->forward[i] = update[i]->forward[i]; // 更新新節點在各層的指針update[i]->forward[i] = newNode;}} else {current->value = value; // 如果鍵已存在，更新值}
}// 在跳表中查找鍵對應的值
int search(SkipList* list, int key) {SkipListNode* current = list->header;for (int i = list->level - 1; i >= 0; i--) {while (current->forward[i] && current->forward[i]->key < key) {current = current->forward[i]; // 在當前層查找鍵}}current = current->forward[0];if (current && current->key == key) {return current->value; // 如果找到鍵，返回對應的值} else {return -1; // 如果未找到鍵，返回-1}
}// 刪除跳表中的鍵值對
void delete(SkipList* list, int key) {SkipListNode* update[MAX_LEVEL]; // 用于記錄刪除位置的前驅節點SkipListNode* current = list->header;for (int i = list->level - 1; i >= 0; i--) {while (current->forward[i] && current->forward[i]->key < key) {current = current->forward[i]; // 在當前層找到刪除位置的前驅節點}update[i] = current;}current = current->forward[0];if (current && current->key == key) {for (int i = 0; i < list->level; i++) {if (update[i]->forward[i] != current) {break; // 如果在某一層沒有找到要刪除的節點，跳出循環}update[i]->forward[i] = current->forward[i]; // 更新前驅節點的指針}free(current); // 釋放被刪除節點的內存while (list->level > 1 && list->header->forward[list->level - 1] == NULL) {list->level--; // 如果某一層沒有節點，減少跳表的層數}}
}// 釋放跳表的內存
void freeSkipList(SkipList* list) {SkipListNode* current = list->header;SkipListNode* next;while (current) {next = current->forward[0]; // 保存下一個節點的指針free(current); // 釋放當前節點的內存current = next; // 移動到下一個節點}free(list); // 釋放跳表結構體的內存
}// 打印跳表（用于調試）
void printSkipList(SkipList* list) {for (int i = list->level - 1; i >= 0; i--) {SkipListNode* current = list->header->forward[i];printf("Level %d: ", i + 1);while (current) {printf("(%d, %d) -> ", current->key, current->value); // 打印當前節點的鍵值對current = current->forward[i]; // 移動到下一個節點}printf("NULL\n"); // 打印當前層的結束標志}
}int main() {srand(time(NULL)); // 初始化隨機數生成器SkipList* list = createSkipList(); // 創建跳表// 插入一些鍵值對insert(list, 1, 10);insert(list, 2, 20);insert(list, 3, 30);insert(list, 4, 40);insert(list, 5, 50);// 打印跳表printSkipList(list);// 查找鍵對應的值printf("Search key 3: %d\n", search(list, 3));printf("Search key 6: %d\n", search(list, 6));// 刪除鍵值對delete(list, 3);// 打印跳表printSkipList(list);// 釋放跳表的內存freeSkipList(list);return 0;
}

5.文件組織和外部存儲數據結構

? ? ? ? 基本概念定義如下所示:

5.1順序文件

5.1.1 順序文件的特點

• 簡單性：順序文件的結構簡單，易于理解和實現。
• 順序訪問效率高：如果數據的訪問模式是順序的，那么順序文件的訪問效率很高。
• 不適合隨機訪問：由于數據是按照順序存儲的，因此隨機訪問（即直接訪問文件中的某個特定位置的數據）效率較低。

5.1.2 順序文件的操作

• 寫入數據：數據按照順序依次寫入文件。
• 讀取數據：數據按照順序依次從文件中讀取。

5.1.3 順序文件的實現解析

#include <stdio.h>  #define MAX_RECORDS 100  // 定義最大記錄數// 定義學生結構體，包含ID、姓名和成績
typedef struct {int id;  // 學生IDchar name[50];  // 學生姓名，最多49個字符加上結束符float score;  // 學生成績
} Student;// 順序寫入文件函數
void writeSequentialFile(const char* filename) {FILE* file = fopen(filename, "wb");  // 以二進制寫模式打開文件if (file == NULL) {  // 如果文件打開失敗perror("無法打開文件");  // 打印錯誤信息return;  // 返回}Student students[MAX_RECORDS];  // 創建學生數組// 循環填充學生數組for (int i = 0; i < MAX_RECORDS; i++) {students[i].id = i + 1;  // 設置IDsprintf(students[i].name, "學生%d", i + 1);  // 設置姓名students[i].score = (float)(i + 1) * 10;  // 設置成績fwrite(&students[i], sizeof(Student), 1, file);  // 寫入文件}fclose(file);  // 關閉文件
}// 順序讀取文件函數
void readSequentialFile(const char* filename) {FILE* file = fopen(filename, "rb");  // 以二進制讀模式打開文件if (file == NULL) {  // 如果文件打開失敗perror("無法打開文件");  // 打印錯誤信息return;  // 返回}Student student;  // 創建學生變量用于存儲讀取的數據// 循環讀取文件直到文件結束while (fread(&student, sizeof(Student), 1, file) == 1) {printf("ID: %d, 姓名: %s, 成績: %.2f\n", student.id, student.name, student.score);  // 打印學生信息}fclose(file);  // 關閉文件
}int main() {const char* filename = "students.dat";  // 定義文件名writeSequentialFile(filename);  // 寫入文件readSequentialFile(filename);  // 讀取文件return 0;  // 程序結束
}

5.2 索引文件

索引文件是一種通過建立索引來提高數據查找速度的文件組織方式。索引指向數據在文件中的位置，使得可以快速定位到特定的數據記錄。

5.2.1 索引文件的特點

• 查找效率高：通過索引可以快速定位到數據記錄，提高了查找效率。
• 增加了存儲空間：需要額外的存儲空間來存儲索引。
• 維護成本：當數據發生變化時，需要更新索引，增加了維護成本。

5.2.2 索引文件的操作

• 寫入數據：數據按照順序依次寫入文件，同時更新索引。
• 讀取數據：通過索引快速定位到數據記錄，然后讀取數據。

5.2.3 索引文件的實現與解析

#include <stdio.h>
#include <stdlib.h>#define MAX_RECORDS 100  // 定義最大記錄數// 定義學生結構體，包含ID、姓名和成績
typedef struct {int id;  // 學生IDchar name[50];  // 學生姓名，最多49個字符加上結束符float score;  // 學生成績
} Student;// 定義索引條目結構體，包含ID和文件偏移量
typedef struct {int id;  // 記錄IDlong offset;  // 文件中的偏移量
} IndexEntry;// 寫入索引文件函數
void writeIndexedFile(const char* filename) {FILE* dataFile = fopen(filename, "wb");  // 以二進制寫模式打開數據文件if (dataFile == NULL) {  // 如果數據文件打開失敗perror("無法打開數據文件");  // 打印錯誤信息return;  // 返回}FILE* indexFile = fopen("index.dat", "wb");  // 以二進制寫模式打開索引文件if (indexFile == NULL) {  // 如果索引文件打開失敗perror("無法打開索引文件");  // 打印錯誤信息fclose(dataFile);  // 關閉已打開的數據文件return;  // 返回}Student students[MAX_RECORDS];  // 創建學生數組IndexEntry index[MAX_RECORDS];  // 創建索引條目數組// 循環填充學生數組和索引數組，并寫入文件for (int i = 0; i < MAX_RECORDS; i++) {students[i].id = i + 1;  // 設置IDsprintf(students[i].name, "學生%d", i + 1);  // 設置姓名students[i].score = (float)(i + 1) * 10;  // 設置成績fwrite(&students[i], sizeof(Student), 1, dataFile);  // 寫入數據文件index[i].id = students[i].id;  // 設置索引IDindex[i].offset = ftell(dataFile) - sizeof(Student);  // 計算并設置文件偏移量fwrite(&index[i], sizeof(IndexEntry), 1, indexFile);  // 寫入索引文件}fclose(dataFile);  // 關閉數據文件fclose(indexFile);  // 關閉索引文件
}// 讀取索引文件函數
void readIndexedFile(const char* filename, int id) {FILE* dataFile = fopen(filename, "rb");  // 以二進制讀模式打開數據文件if (dataFile == NULL) {  // 如果數據文件打開失敗perror("無法打開數據文件");  // 打印錯誤信息return;  // 返回}FILE* indexFile = fopen("index.dat", "rb");  // 以二進制讀模式打開索引文件if (indexFile == NULL) {  // 如果索引文件打開失敗perror("無法打開索引文件");  // 打印錯誤信息fclose(dataFile);  // 關閉已打開的數據文件return;  // 返回}IndexEntry index;  // 創建索引條目變量用于存儲讀取的數據// 循環讀取索引文件直到找到匹配的ID或文件結束while (fread(&index, sizeof(IndexEntry), 1, indexFile) == 1) {if (index.id == id) {  // 如果找到匹配的IDfseek(dataFile, index.offset, SEEK_SET);  // 定位到數據文件中的記錄位置Student student;  // 創建學生變量用于存儲讀取的數據fread(&student, sizeof(Student), 1, dataFile);  // 讀取學生信息printf("ID: %d, 姓名: %s, 成績: %.2f\n", student.id, student.name, student.score);  // 打印學生信息break;  // 結束循環}}fclose(dataFile);  // 關閉數據文件fclose(indexFile);  // 關閉索引文件
}int main() {const char* filename = "students.dat";  // 定義數據文件名writeIndexedFile(filename);  // 寫入索引文件readIndexedFile(filename, 50);  // 讀取ID為50的學生信息return 0;  // 程序結束
}