鏈表在c語言中通過結構體和指針實現，每個節(jié)點包含數據和指向下一個節(jié)點的指針；1.定義節(jié)點結構體；2.使用指針連接節(jié)點；3.實現創(chuàng)建、插入、刪除、遍歷等操作；4.鏈表適合頻繁插入刪除且數據大小動態(tài)變化的場景；5.檢測環(huán)使用快慢指針法；6.反轉鏈表可用迭代或遞歸方法。
c語言中，鏈表是通過結構體和指針實現的，它是一種動態(tài)數據結構，允許在運行時添加或刪除元素，無需預先知道數據的大小。核心在于每個節(jié)點包含數據和指向下一個節(jié)點的指針。
解決方案：
C語言實現鏈表的核心在于定義節(jié)點結構體，并使用指針連接這些節(jié)點。以下是一個簡單的單鏈表實現，包括創(chuàng)建、插入、刪除和遍歷等基本操作：
立即學習“C語言免費學習筆記（深入）”；
#include <stdio.h> #include <stdlib.h> // 定義鏈表節(jié)點結構體 typedef struct Node { int data; // 數據域 struct Node* next; // 指針域，指向下一個節(jié)點 } Node; // 創(chuàng)建新節(jié)點 Node* createNode(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); // 動態(tài)分配內存 if (newNode == NULL) { perror("Failed to allocate memory"); exit(EXIT_FAILURE); } newNode->data = data; newNode->next = NULL; // 新節(jié)點是尾節(jié)點，next指向NULL return newNode; } // 在鏈表頭部插入節(jié)點 void insertAtBeginning(Node** head, int data) { Node* newNode = createNode(data); newNode->next = *head; // 新節(jié)點的next指向原來的頭節(jié)點 *head = newNode; // 更新頭節(jié)點為新節(jié)點 } // 在鏈表尾部插入節(jié)點 void insertAtEnd(Node** head, int data) { Node* newNode = createNode(data); if (*head == NULL) { // 如果鏈表為空 *head = newNode; // 新節(jié)點成為頭節(jié)點 return; } Node* current = *head; while (current->next != NULL) { // 找到尾節(jié)點 current = current->next; } current->next = newNode; // 尾節(jié)點的next指向新節(jié)點 } // 在指定位置插入節(jié)點（pos從0開始計數） void insertAtPosition(Node** head, int data, int pos) { if (pos < 0) { printf("Invalid position.n"); return; } if (pos == 0) { // 在頭部插入，等同于insertAtBeginning insertAtBeginning(head, data); return; } Node* newNode = createNode(data); Node* current = *head; Node* previous = NULL; int i = 0; while (current != NULL && i < pos) { previous = current; current = current->next; i++; } if (i != pos) { // 位置超出鏈表長度 printf("Position out of range.n"); free(newNode); // 釋放已分配的內存 return; } newNode->next = current; previous->next = newNode; } // 刪除指定數據的節(jié)點（刪除第一個匹配的節(jié)點） void deleteNode(Node** head, int data) { Node* current = *head; Node* previous = NULL; // 如果鏈表為空 if (*head == NULL) { return; } // 如果頭節(jié)點就是要刪除的節(jié)點 if (current->data == data) { *head = current->next; free(current); return; } // 遍歷鏈表找到要刪除的節(jié)點 while (current != NULL && current->data != data) { previous = current; current = current->next; } // 如果沒找到要刪除的節(jié)點 if (current == NULL) { return; } // 刪除節(jié)點 previous->next = current->next; free(current); } // 遍歷鏈表 void printList(Node* head) { Node* current = head; while (current != NULL) { printf("%d ", current->data); current = current->next; } printf("n"); } // 釋放鏈表內存 void freeList(Node** head) { Node* current = *head; Node* nextNode; while (current != NULL) { nextNode = current->next; free(current); current = nextNode; } *head = NULL; // 將頭指針置空 } int main() { Node* head = NULL; // 初始化頭指針 insertAtEnd(&head, 1); insertAtEnd(&head, 2); insertAtEnd(&head, 3); printf("鏈表內容: "); printList(head); // 輸出：1 2 3 insertAtBeginning(&head, 0); printf("頭部插入后: "); printList(head); // 輸出：0 1 2 3 insertAtPosition(&head, 5, 2); printf("指定位置插入后: "); printList(head); // 輸出：0 1 5 2 3 deleteNode(&head, 2); printf("刪除節(jié)點后: "); printList(head); // 輸出：0 1 5 3 freeList(&head); printf("鏈表釋放后: "); printList(head); // 輸出：（空） return 0; }
鏈表和數組的區(qū)別是什么？什么時候應該使用鏈表？
鏈表和數組是兩種常見的數據結構，它們在內存分配、插入刪除效率和訪問方式上存在顯著差異。數組在內存中是連續(xù)存儲的，因此可以通過索引快速訪問任何元素，但插入和刪除元素（尤其是在數組中間位置）需要移動大量元素，效率較低。鏈表則通過指針連接各個節(jié)點，節(jié)點在內存中可以是不連續(xù)的，插入和刪除節(jié)點只需要修改指針，效率較高，但訪問特定位置的元素需要從頭節(jié)點開始遍歷，效率較低。
使用場景：
- 當你需要頻繁插入和刪除元素，而對元素的訪問順序不敏感時，鏈表是更好的選擇。
- 當你需要快速訪問元素，并且元素的數量在編譯時已知或很少變化時，數組是更好的選擇。
- 當數據量動態(tài)變化且難以預估大小時，鏈表可以避免數組擴容帶來的性能開銷。
如何檢測鏈表中是否存在環(huán)？
檢測鏈表中是否存在環(huán)，可以使用快慢指針（Floyd算法）。定義兩個指針，一個快指針每次移動兩步，一個慢指針每次移動一步。如果鏈表中存在環(huán)，快指針最終會追上慢指針。如果快指針到達鏈表末尾（NULL），則說明鏈表中不存在環(huán)。
#include <stdbool.h> // 引入 bool 類型 bool hasCycle(Node* head) { if (head == NULL || head->next == NULL) { return false; // 空鏈表或只有一個節(jié)點，不可能有環(huán) } Node* slow = head; Node* fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; // 慢指針走一步 fast = fast->next->next; // 快指針走兩步 if (slow == fast) { return true; // 快慢指針相遇，說明有環(huán) } } return false; // 快指針到達鏈表末尾，說明沒有環(huán) }
如何反轉一個鏈表？
反轉鏈表是一個常見的鏈表操作，可以使用迭代或遞歸兩種方法實現。迭代方法通過修改每個節(jié)點的next指針，使其指向前一個節(jié)點。遞歸方法則通過遞歸調用，逐步將鏈表反轉。
迭代方法：
Node* reverseList(Node* head) { Node* prev = NULL; Node* current = head; Node* next = NULL; while (current != NULL) { next = current->next; // 保存下一個節(jié)點 current->next = prev; // 當前節(jié)點的next指向前一個節(jié)點 prev = current; // 前一個節(jié)點更新為當前節(jié)點 current = next; // 當前節(jié)點更新為下一個節(jié)點 } return prev; // prev現在指向新的頭節(jié)點 }
遞歸方法：
Node* reverseListRecursive(Node* head) { if (head == NULL || head->next == NULL) { return head; // 空鏈表或只有一個節(jié)點，直接返回 } Node* newHead = reverseListRecursive(head->next); // 遞歸反轉后面的鏈表 head->next->next = head; // 將當前節(jié)點的下一個節(jié)點的next指向當前節(jié)點 head->next = NULL; // 當前節(jié)點的next置為NULL return newHead; // 返回新的頭節(jié)點 }
選擇哪種方法取決于個人偏好和具體場景。迭代方法通常更容易理解和調試，而遞歸方法則更簡潔，但可能涉及更多的函數調用開銷。
? 版權聲明
文章版權歸作者所有，未經允許請勿轉載。
THE END
