數據結構------C語言經典題目（6）

1.數據結構都學了些什么？

1.基本數據類型

算數類型：

? ? ? ? char（字符）、int（整數）、float（單精度浮點數）、double（雙精度浮點數）等。

枚舉類型：

? ? ? ? enum，自定義一組命名的整形常量。例如顏色：enum Color {RED ，GREEN ，BLUE}：

2.構造數據類型

數組（Array）：

? ? ? ? 固定大小、連續存儲的同類型元素集合；

? ? ? ? 支持通過下標快速訪問元素，但插入/刪除操作效率低。

結構體（Struct）：

? ? ? ? 自定義的復合數據類型，可以包含不同類型的成員（如學生信息）；

struct Student {char name[20];int age;float score;
};

聯合體（Union）：

? ? ? ? 多個不同類型的變量共享同一段內存空間，同一時刻只能存儲其中一個成員的值（節省內存）。

3.動態數據結構

通過指針動態分配內存，結構靈活。

鏈表：

? ? ? ? 由節點組成，每個節點包含數據和指向下一個節點的指針。

? ? ? ? 有單向鏈表、雙向鏈表、循環鏈表等，插入/刪除操作高效（無需移動大量元素），但訪問效率低（需遍歷）。

棧：

? ? ? ? 遵循? ?后進先出? 原則，可以通過數組或鏈表實現。

? ? ? ? 常見操作：入棧、出棧、取棧頂元素。

隊列：

? ? ? ? 遵循? ?先進先出? ?原則，有入隊、出隊。

樹：

????????分層結構，由節點和邊組成，根節點無父節點，子節點有唯一父節點。

? ? ? ? 常見類型：二叉樹（每個節點最多兩個子節點）、二叉搜索樹（左根右）、堆（用于優先隊列）等。

圖：? ??

? ? ? ? 由頂點（節點）和邊組成，用于表示復雜關系（社交網絡、地圖路徑）。

? ? ? ? 分為有向圖、無向圖、帶權圖。

4.數據結構的核心操作

查找：

? ? ? ? 如順序查找、二分查找（僅適用于有序數組）。

插入：

? ? ? ? 在指定位置添加元素。

刪除：

? ? ? ? 移動指定元素。

排序：

? ? ? ? 冒泡排序、快速排序、希爾排序。

遍歷：

? ? ? ? 按一定順序訪問元素。

5.指針與數據結構

? ? ? ? 通過malloc（）、calloc（）等函數動態分配內存（如創建鏈表節點）。

? ? ? ? 指針操作需注意內存泄漏（分配的內存未釋放）和野指針（指向已釋放的內存）問題。

6.應用場景

數組：

? ? ? ? 適合需要快速隨機訪問、數據大小固定的場景（存儲學生成績）。

鏈表：

? ? ? ? 適合頻繁插入/刪除、數據大小動態變化的場景。

棧：

? ? ? ? 用于函數調用棧、表達式求值、括號匹配等。

隊列：

? ? ? ? 用于任務調度等。

樹和圖：

? ? ? ? 用于文件系統目錄結構等。

2.數據結構中的順序表和鏈表有什么區別？

存儲結構：

順序表：

????????1.存儲方式：數據元素在內存中連續存儲，邏輯上相鄰的元素在物理地址上也相鄰。

? ? ? ? 2.實現方式：通常由數組實現，通過數組下標訪問元素。

? ? ? ? 3.內存分配：需要預先分配固定大小的內存空間，若數量動態變化會導致空間浪費或溢出。

鏈表：

? ? ? ? 1.存儲方式：數據元素分散存儲，每個元素（節點）包含數據域和指針域，指針指向下一個節點的地址。

? ? ? ? 2.實現方式：通過結構體和指針動態創建節點，節點之間通過指針鏈接。

? ? ? ? 3.內存分配：按需動態分配內存，無需預先指定最大容量，比較靈活。

訪問方式：

順序表：

? ? ? ? 隨機訪問：可以通過下標直接訪問任意元素，時間復雜度為O（1）。

鏈表：????????

? ? ? ? 順序訪問：必須從表頭開始逐個遍歷節點，直到找到目標元素，時間復雜度為O(n)。

插入和刪除操作：

順序表：

? ? ? ? 插入：在開頭或中間任意位置插入元素，都需要移動后續所有元素。

? ? ? ? 刪除：刪除中間或開頭元素，需移動后續元素填補空缺。

? ? ? ? 尾插尾刪無需移動元素。

鏈表：

? ? ? ? 插入/刪除：只需修改指針指向，無需移動其他元素，但要找到插入位置的前驅節點。

? ? ? ? 示例：在節點p后插入新節點：

? ? ? ? new_node? ->? next? =? p->next;

? ? ? ? p->next = new_node;

適用場景：

順序表：? ? ? ?

? ? ? ? 適合頻繁隨機訪問的場景。

鏈表：

? ? ? ? 適合頻繁插入/刪除的場景。

3.單向鏈表和雙向鏈表有什么區別？

單向鏈表：

? ? ? ? 每個節點包含一個數據域和一個指向下一個節點的指針（next）

Node1 → Node2 → Node3 → ... → NULL

? ? ? ? 節點定義代碼示例：

struct Node {int data;struct Node* next;
};

? ? ? ? 遍歷只能從頭節點開始，沿next指針單向遍歷（向后），無法反向訪問前面的節點。

? ? ? ? 插入節點時，只需修改當前節點的next 指針指向新節點，或新節點的next 指針指向后續節點。

? ? ? ? 刪除節點時，需找到要刪除的節點的前驅節點，修改其next指針跳過要刪除的節點。

? ? ? ? 每個節點包含一個指針，內存占用相對較小。

雙向鏈表：

? ? ? ? 每個節點包含一個數據域、一個指向前一個節點的指針（prev）和一個指向下一個節點的指針（next）

NULL ← Node1 ? Node2 ? Node3 ← ... ← NULL

? ? ? ? 節點定義代碼示例：

struct Node {int data;struct Node* prev;struct Node* next;
};

? ? ? ? 可以從頭節點或尾節點開始，通過prev和next指針雙向遍歷。

? ? ? ? 插入節點后，需同時修改新節點的prev（指向前驅節點）和next（指向后繼節點）。

? ? ? ? 刪除節點時，可通過當前節點的prev指針直接找到前驅節點，通過next指針找到后繼節點，修改兩者的指針即可。

? ? ? ? 每個節點包含兩個指針（prev和next），內存占用比單向鏈表多約一倍。

4.什么是內存泄漏？如何排查和避免內存泄漏？

? ? ? ? 內存泄漏是指程序動態分配的內存空間（如malloc、calloc、realloc等函數申請）在使用完畢后未被正確釋放。即未調用free函數。導致這部分內存無法被系統重新分配利用的現象。

內存泄漏常見場景：

1.直接申請內存后未調用free釋放

例如：

void function() 
{int *p = (int *)malloc(sizeof(int));// 使用 p// 未調用 free(p)
}  // p 離開作用域后，內存泄漏

2.重復釋放或錯誤釋放：

????????釋放已釋放的指針（多次調用free（p）），導致程序崩崩潰。

????????釋放非動態分配的內存（局部變量的地址），導致段錯誤。

3.指針被覆蓋：

? ? ? ? 分配內存后，指針指向其他地址，導致原內存地址丟失，無法釋放：

int *p = (int *)malloc(sizeof(int));
p = (int *)malloc(sizeof(int));  // 新分配覆蓋了 p，原內存未釋放
free(p);  // 僅釋放了最后一次分配的內存

4.循環或條件分支中的分配未釋放

? ? ? ? 當循環或條件判斷中分配內存，但某些分支未執行釋放邏輯。

while (condition) 
{int *p = (int *)malloc(sizeof(int));if (some_case) {continue;  // 直接跳過釋放}free(ptr);
}

如何排查：

1.手動排查：

檢查所有malloc、calloc、realloc是否有對應的free，且釋放次數正確。

? ? ? ? 確保指針在釋放后被置為NULL（避免野指針）。

2.使用內存檢測工具

? ? ? ? 通過memcheck根據動態檢測內存泄漏，能精準定位未釋放的內存及分配位置。

valgrind --leak-check=full ./your_program

3.調試器（GDB）

? ? ? ? 在程序退出前檢查堆內存狀態，結合斷點定位泄漏點。

如何避免：

? ? ? ? 遵循：分配-使用-釋放? 的配對原則

? ? ? ? 在釋放內存后，立即將指針置為NULL，防止后續誤操作（野指針）。

5.什么是內存碎片？如何避免內存碎片？

? ? ? ? 內存碎片是指程序運行過程中，由于頻繁地申請和釋放內存，導致內存中出現大量不連續的小空閑塊，這些空閑塊雖然總容量足夠，但無法滿足較大內存塊的分配請求，從而影響內存使用效率的現象。

如何避免：

1.減少動態內存分配和釋放的次數：

? ? ? ? 盡量復用已分配的內存。

2.使用內存池：

? ? ? ? 預先分配一大塊內存，劃分為多個固定大小的小塊，通過池管理和回收，避免碎片化。

? ? ? ? 分配/釋放速度快（無需系統調用），碎片控制在池內。

// 簡化的內存池結構
typedef struct {char* buffer;       // 池內存起始地址size_t block_size;  // 每個塊大小size_t num_blocks;  // 塊總數int* free_blocks;   // 記錄可用塊索引
} MemoryPool;

6.如何實現雙向鏈表的插入？刪除？

? ? ? ? 示例代碼如下：

// 定義雙向鏈表節點結構
// 每個節點包含數據域(data)、前驅指針(prev)和后繼指針(next)
typedef struct Node {int data;               // 存儲節點數據struct Node* prev;      // 指向前驅節點的指針（NULL表示無前驅）struct Node* next;      // 指向后繼節點的指針（NULL表示無后繼）
} Node;// 創建新節點并初始化數據
// 參數：data - 節點存儲的數據
// 返回：新創建的節點指針（內存分配失敗時返回NULL）
Node* createNode(int data) 
{Node* newNode = (Node*)malloc(sizeof(Node));  // 分配節點內存if (newNode == NULL) {printf("內存分配失敗！\n");exit(1);  // 終止程序防止空指針操作}newNode->data = data;        // 初始化數據域newNode->prev = NULL;        // 新節點初始無前驅newNode->next = NULL;        // 新節點初始無后繼return newNode;              // 返回新節點指針
}// 在鏈表頭部插入新節點
// 參數：head - 指向頭節點指針的指針（用于修改頭節點），data - 插入的數據
// 功能：將新節點插入到鏈表頭部，更新頭指針及前后指針關系
void insertAtHead(Node** head, int data) 
{Node* newNode = createNode(data);  // 創建新節點// 處理空鏈表情況：新節點成為唯一節點if (*head == NULL) {*head = newNode;  // 頭指針指向新節點return;}// 非空鏈表處理：新節點成為新頭節點newNode->next = *head;          // 新節點的后繼指向原頭節點(*head)->prev = newNode;        // 原頭節點的前驅指向新節點*head = newNode;                // 更新頭指針為新節點
}// 在鏈表尾部插入新節點
// 參數：head - 指向頭節點指針的指針，data - 插入的數據
// 功能：遍歷鏈表找到尾節點，將新節點連接到尾部
void insertAtTail(Node** head, int data) 
{Node* newNode = createNode(data);  // 創建新節點// 處理空鏈表情況：新節點成為唯一節點if (*head == NULL) {*head = newNode;  // 頭指針指向新節點return;}// 查找尾節點：從頭部開始遍歷直到next為NULLNode* current = *head;while (current->next != NULL) {current = current->next;  // 移動到下一個節點}// 連接新節點到尾節點之后current->next = newNode;       // 尾節點的后繼指向新節點newNode->prev = current;       // 新節點的前驅指向尾節點
}// 在指定節點之后插入新節點
// 參數：targetNode - 目標節點（新節點將插入到其之后），data - 插入的數據
// 功能：在目標節點之后插入新節點，處理前后節點的指針關系
void insertAfterNode(Node* targetNode, int data) 
{if (targetNode == NULL) {       // 檢查目標節點是否存在printf("目標節點不存在！\n");return;}Node* newNode = createNode(data);  // 創建新節點// 新節點的后繼指向目標節點的后繼（可能為NULL）newNode->next = targetNode->next;// 新節點的前驅指向目標節點newNode->prev = targetNode;// 如果目標節點有后繼節點，更新其后繼的前驅指針if (targetNode->next != NULL) {targetNode->next->prev = newNode;}// 目標節點的后繼指向新節點targetNode->next = newNode;
}// 刪除指定節點
// 參數：head - 指向頭節點指針的指針，targetNode - 待刪除的目標節點
// 功能：從鏈表中移除目標節點，處理前后節點的指針連接并釋放內存
void deleteNode(Node** head, Node* targetNode) 
{if (*head == NULL || targetNode == NULL) {  // 檢查鏈表是否為空或節點是否存在printf("鏈表為空或目標節點不存在！\n");return;}// 處理刪除頭節點的情況：更新頭指針if (*head == targetNode) {*head = targetNode->next;  // 頭指針指向原頭節點的后繼}// 調整前驅節點的后繼指針（如果存在前驅）if (targetNode->prev != NULL) {targetNode->prev->next = targetNode->next;  // 前驅的后繼指向目標節點的后繼}// 調整后繼節點的前驅指針（如果存在后繼）if (targetNode->next != NULL) {targetNode->next->prev = targetNode->prev;  // 后繼的前驅指向目標節點的前驅}// 釋放目標節點內存并置空指針（防止野指針）free(targetNode);targetNode = NULL;
}// 打印鏈表內容（從頭部到尾部）
// 參數：head - 頭節點指針
// 功能：遍歷鏈表并輸出每個節點的數據
void printList(Node* head) 
{Node* current = head;  // 當前節點從頭部開始printf("雙向鏈表內容: ");while (current != NULL) {  // 遍歷直到NULL（鏈表末尾）printf("%d ", current->data);  // 輸出當前節點數據current = current->next;       // 移動到下一個節點}printf("\n");
}// 主函數：演示雙向鏈表操作
int main() 
{Node* head = NULL;  // 初始化空鏈表// 頭部插入操作演示：插入10 → 鏈表：10// 再次頭部插入20 → 鏈表：20 10insertAtHead(&head, 10);insertAtHead(&head, 20);// 尾部插入操作演示：插入30 → 鏈表：20 10 30// 再次尾部插入40 → 鏈表：20 10 30 40insertAtTail(&head, 30);insertAtTail(&head, 40);// 在節點20（頭節點的下一個節點head->next）之后插入50// 插入后鏈表：20 50 10 30 40insertAfterNode(head->next, 50);// 刪除節點50（此時是head->next節點）// 刪除后鏈表恢復：20 10 30 40Node* nodeToDelete = head->next;  // 獲取待刪除節點（值為50的節點）deleteNode(&head, nodeToDelete);printList(head);  // 輸出最終鏈表內容// 釋放鏈表所有節點內存（防止內存泄漏）while (head != NULL) {Node* temp = head;       // 保存當前節點指針head = head->next;       // 頭指針指向下一個節點free(temp);              // 釋放當前節點內存}return 0;
}

7.怎么判斷一個鏈表是否有環？

? ? ? ? 可以使用快慢指針法來判斷鏈表是否有環。

????????快指針每次移動兩步，慢指針每次移動一步。

????????若鏈表存在環，快指針最終會追上慢指針。

? ? ? ? 若快指針到達鏈表末尾（即指向NULL），則鏈表無環。

? ? ? ? 示例代碼如下：

// 定義鏈表節點結構
typedef struct ListNode {int val;                // 節點存儲的整數值struct ListNode *next;  // 指向下一個節點的指針
} ListNode;// --------------------------
// 函數功能：判斷鏈表是否存在環
// 輸入參數：head - 鏈表頭節點指針
// 輸出參數：1 - 存在環；0 - 不存在環
// 算法：快慢指針法（弗洛伊德龜兔賽跑算法）
// 原理：快指針每次移動2步，慢指針每次移動1步。若存在環，快指針必然追上慢指針；若快指針到達鏈表末尾，則無環
// --------------------------
int hasCycle(ListNode *head) 
{// 處理特殊情況：空鏈表或單個節點（無后續節點，不可能形成環）if (head == NULL || head->next == NULL) {return 0;}// 初始化快慢指針：// 慢指針從頭節點開始，每次移動1步// 快指針從頭節點的下一個節點開始（領先1步），避免初始位置相同導致循環不執行（當鏈表有環時，至少需要2個節點才能形成環）ListNode *slow = head;ListNode *fast = head->next;// 循環條件：快慢指針未相遇（相遇則說明有環）while (fast != slow) {// 快指針到達鏈表末尾（無環）：// 快指針每次移動2步，需檢查當前節點和下一個節點是否為NULL，避免越界訪問if (fast == NULL || fast->next == NULL) {return 0;  // 無環}// 慢指針移動1步slow = slow->next;// 快指針移動2步（先移動1步，再移動1步）fast = fast->next->next;}// 循環退出時，快慢指針相遇，說明存在環return 1;
}// --------------------------
// 函數功能：創建一個帶環的鏈表（用于測試）
// 結構：1 -> 2 -> 3 -> 2（形成環，尾節點指向第二個節點）
// 返回值：鏈表頭節點指針
// --------------------------
ListNode* createCycleList() 
{// 分配3個節點的內存空間ListNode *nodes = (ListNode*)malloc(3 * sizeof(ListNode));// 初始化節點值和連接關系nodes[0].val = 1;nodes[1].val = 2;nodes[2].val = 3;// 正常連接：1->2->3nodes[0].next = &nodes[1];nodes[1].next = &nodes[2];// 形成環：3->2（尾節點指向第二個節點，構成環）nodes[2].next = &nodes[1];return nodes;  // 返回頭節點（第一個節點）
}// --------------------------
// 函數功能：創建一個無環的鏈表（用于測試）
// 結構：1 -> 2 -> 3 -> NULL（正常尾節點）
// 返回值：鏈表頭節點指針
// --------------------------
ListNode* createAcyclicList() 
{// 分配3個節點的內存空間ListNode *nodes = (ListNode*)malloc(3 * sizeof(ListNode));// 初始化節點值和連接關系nodes[0].val = 1;nodes[1].val = 2;nodes[2].val = 3;// 正常連接：1->2->3->NULL（尾節點指向NULL，無環）nodes[0].next = &nodes[1];nodes[1].next = &nodes[2];nodes[2].next = NULL;return nodes;  // 返回頭節點（第一個節點）
}int main() 
{// 測試帶環鏈表ListNode *cycleHead = createCycleList();printf("帶環鏈表檢測結果：%s\n", hasCycle(cycleHead) ? "有環" : "無環");  // 預期輸出"有環"// 測試無環鏈表ListNode *acyclicHead = createAcyclicList();printf("無環鏈表檢測結果：%s\n", hasCycle(acyclicHead) ? "有環" : "無環");  // 預期輸出"無環"// 釋放內存（避免內存泄漏）// 注意：實際使用中需確保所有動態分配的內存都被正確釋放free(cycleHead);free(acyclicHead);return 0;
}

主函數的打印邏輯也可以這么寫：

int result = hasCycle(cycleHead); // 獲取返回值（1或0）
if (result)         // 等價于 if (result != 0)
{                    printf("帶環鏈表檢測結果：有環\n");
} 
else 
{printf("帶環鏈表檢測結果：無環\n");
}