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