鏈表
鏈表（Linked List）是一種常見的數(shù)據(jù)結(jié)構(gòu)，用于存儲一系列具有相同類型的元素。鏈表由節(jié)點（Node）組成，每個節(jié)點包含兩部分：數(shù)據(jù)域（存儲元素值）和指針域（指向下一個節(jié)點）。通過節(jié)點之間的指針連接，形成一個鏈式結(jié)構(gòu)。
鏈表可以分為單向鏈表和雙向鏈表兩種類型。在單向鏈表中，每個節(jié)點只有一個指針，指向下一個節(jié)點；而在雙向鏈表中，每個節(jié)點有兩個指針，分別指向前一個節(jié)點和后一個節(jié)點。
鏈表的優(yōu)點是插入和刪除操作的時間復(fù)雜度為O(1)，而不受數(shù)據(jù)規(guī)模的影響。但是，訪問鏈表中的特定元素需要從頭開始遍歷鏈表，時間復(fù)雜度為O(n)，其中n是鏈表的長度。
鏈表在實際應(yīng)用中有廣泛的用途，比如實現(xiàn)棧、隊列、哈希表等數(shù)據(jù)結(jié)構(gòu)，以及解決一些特定的問題，如反轉(zhuǎn)鏈表、合并有序鏈表等。
需要注意的是，在使用鏈表時，我們需要額外的空間來存儲指針，因此鏈表對內(nèi)存的利用率較低。同時，在頻繁插入和刪除操作較多，而對訪問操作要求不高的情況下，鏈表是一個較為合適的選擇。
單鏈表（Singly Linked List）是一種常見的鏈表結(jié)構(gòu)，由一系列節(jié)點按順序連接而成。每個節(jié)點包含兩個部分：數(shù)據(jù)域（存儲元素值）和指針域（指向下一個節(jié)點）。最后一個節(jié)點的指針域指向空（NULL）。
以下是單鏈表的基本結(jié)構(gòu)：
Node:
- 數(shù)據(jù)域（Data）: 存儲元素值
- 指針域（Next）: 指向下一個節(jié)點
LinkedList:
- 頭指針（Head）: 指向鏈表的第一個節(jié)點
單鏈表的頭指針（Head）用于標(biāo)識鏈表的起始位置。通過頭指針，可以遍歷整個鏈表，或者在鏈表中插入、刪除節(jié)點。
單鏈表的特點是每個節(jié)點只有一個指針域，指向下一個節(jié)點，最后一個節(jié)點的指針域為空。這意味著，在單鏈表中，只能從前往后遍歷，無法直接訪問前一個節(jié)點，因此對于某些操作，比如在給定節(jié)點之前插入一個新節(jié)點，需要額外的操作來處理指針。
需要注意的是，單鏈表中的節(jié)點可以動態(tài)地分配內(nèi)存，這意味著可以根據(jù)需求靈活地擴展或縮小鏈表的長度。
下面是一個示例單鏈表的結(jié)構(gòu)：
Head -> Node1 -> Node2 -> Node3 -> ... -> NULL
其中，Head是頭指針，Node1、Node2、Node3等為節(jié)點，箭頭表示指針域的指向關(guān)系，NULL表示鏈表的結(jié)束。
單鏈表的操作包括插入節(jié)點、刪除節(jié)點、查找節(jié)點、遍歷鏈表等，這些操作可以根據(jù)具體需求進行實現(xiàn)。
題1.若線性表采用鏈式存儲，則表中各元素的存儲地址()。
A.必須是連續(xù)的
B.部分地址是連續(xù)的
C.一定是不連續(xù)的
D.不一定是連續(xù)的
答案：D
題2.單鏈表中，增加一個頭結(jié)點的目的是為了()。
A.使單鏈表至少有一個結(jié)點
B.標(biāo)識表結(jié)點中首結(jié)點的位置
C.方便運算的實現(xiàn)
D.說明單鏈表是線性表的鏈式存儲
答案：C
題1的答案是D. 不一定是連續(xù)的。
如果線性表采用鏈式存儲方式，表中各元素的存儲地址不需要連續(xù)。鏈式存儲通過節(jié)點之間的指針連接，每個節(jié)點可以分配在內(nèi)存的任意位置。節(jié)點的指針域存儲著下一個節(jié)點的地址，通過指針的鏈接，實現(xiàn)了元素之間的邏輯關(guān)系。
題2的答案是C. 方便運算的實現(xiàn)。
增加一個頭結(jié)點的目的是為了方便對單鏈表進行操作和實現(xiàn)一些常用的操作，如插入、刪除、查找等。頭結(jié)點不存儲具體的數(shù)據(jù)，它的存在主要是為了簡化操作，使得對鏈表的操作更加統(tǒng)一和方便。頭結(jié)點可以作為操作的起點，避免了對空鏈表的特殊處理，提高了代碼的可讀性和可維護性。
引入頭結(jié)點后，可以帶來兩個優(yōu)點：
①由于第一個數(shù)據(jù)結(jié)點的位置被存放在頭結(jié)點的指針域中，所以在鏈表的第一個位置上的操作和在表的其他位置上的操作一致，無需進行特殊處理。
②無論鏈表是否為空，其頭指針都指向頭結(jié)點的非空指針（空表中頭結(jié)點的指針域為空)。
單鏈表的實現(xiàn)
以下是單鏈表的詳細實現(xiàn)示例（使用C語言）：
- 定義節(jié)點結(jié)構(gòu)（Node）：
struct Node {
int data;
struct Node *next;
};
- 定義鏈表結(jié)構(gòu)（LinkedList）：
struct LinkedList {
struct Node *head;
};
- 實現(xiàn)插入操作：
void insert(struct LinkedList *list, int data) {
struct Node *new_node = (struct Node *)malloc(sizeof(struct Node)); // 創(chuàng)建新節(jié)點
new_node->data = data;
new_node->next = NULL;
if (list->head == NULL) { // 如果鏈表為空，將新節(jié)點設(shè)為頭節(jié)點
list->head = new_node;
} else {
struct Node *current = list->head;
while (current->next != NULL) { // 遍歷到最后一個節(jié)點
current = current->next;
}
current->next = new_node; // 將新節(jié)點插入在最后一個節(jié)點之后
}
}
- 實現(xiàn)刪除操作：
void delete(struct LinkedList *list, int target) {
if (list->head == NULL) { // 如果鏈表為空，無法刪除
return;
}
if (list->head->data == target) { // 如果要刪除的節(jié)點是頭節(jié)點
struct Node *temp = list->head;
list->head = list->head->next;
free(temp);
} else {
struct Node *current = list->head;
while (current->next != NULL && current->next->data != target) { // 查找要刪除節(jié)點的前一個節(jié)點
current = current->next;
}
if (current->next != NULL) { // 找到要刪除的節(jié)點
struct Node *temp = current->next;
current->next = current->next->next;
free(temp);
}
}
}
- 實現(xiàn)查找操作：
int search(struct LinkedList *list, int target) {
struct Node *current = list->head;
while (current != NULL) {
if (current->data == target) { // 找到匹配的節(jié)點
return 1;
}
current = current->next;
}
return 0; // 遍歷完鏈表未找到匹配的節(jié)點
}
- 實現(xiàn)遍歷操作：
void traverse(struct LinkedList *list) {
struct Node *current = list->head;
while (current != NULL) {
printf("%d ", current->data); // 訪問節(jié)點的數(shù)據(jù)域
current = current->next;
}
}
這是一個簡單的單鏈表實現(xiàn)示例。由于C語言需要手動管理內(nèi)存，因此在使用malloc函數(shù)分配內(nèi)存時需要檢查是否分配成功，并在刪除節(jié)點時需要使用free函數(shù)釋放內(nèi)存。您可以根據(jù)這個示例進行自定義擴展和適應(yīng)具體需求。
雙鏈表
雙鏈表（Doubly Linked List）是一種常見的數(shù)據(jù)結(jié)構(gòu)，它與單鏈表相比，在每個節(jié)點中都有兩個指針，分別指向前一個節(jié)點和后一個節(jié)點，因此可以實現(xiàn)雙向遍歷。這使得在雙鏈表中插入、刪除節(jié)點等操作更加高效。
下面是一個更詳細的雙鏈表的 C 代碼實現(xiàn)：
#include <stdio.h>
#include <stdlib.h>
// 雙鏈表節(jié)點結(jié)構(gòu)
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
// 創(chuàng)建新節(jié)點
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("內(nèi)存分配失敗\n");
exit(1);
}
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// 在鏈表頭部插入節(jié)點
void insertFront(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
newNode->next = *head;
(*head)->prev = newNode;
*head = newNode;
}
}
// 在鏈表末尾插入節(jié)點
void insertEnd(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
Node* curr = *head;
while (curr->next != NULL) {
curr = curr->next;
}
curr->next = newNode;
newNode->prev = curr;
}
}
// 在指定位置插入節(jié)點
void insertAt(Node** head, int data, int position) {
if (position < 1) {
printf("無效的位置\n");
return;
}
if (position == 1) {
insertFront(head, data);
return;
}
Node* newNode = createNode(data);
Node* curr = *head;
int count = 1;
while (count < position - 1 && curr != NULL) {
curr = curr->next;
count++;
}
if (curr == NULL) {
printf("無效的位置\n");
return;
}
newNode->next = curr->next;
newNode->prev = curr;
if (curr->next != NULL) {
curr->next->prev = newNode;
}
curr->next = newNode;
}
// 刪除鏈表頭部節(jié)點
void deleteFront(Node** head) {
if (*head == NULL) {
printf("鏈表為空\n");
return;
}
Node* temp = *head;
*head = (*head)->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
free(temp);
}
// 刪除鏈表末尾節(jié)點
void deleteEnd(Node** head) {
if (*head == NULL) {
printf("鏈表為空\n");
return;
}
Node* curr = *head;
while (curr->next != NULL) {
curr = curr->next;
}
if (curr->prev != NULL) {
curr->prev->next = NULL;
} else {
*head = NULL;
}
free(curr);
}
// 刪除指定位置節(jié)點
void deleteAt(Node** head, int position) {
if (*head == NULL || position < 1) {
printf("無效的位置\n");
return;
}
if (position == 1) {
deleteFront(head);
return;
}
Node* curr = *head;
int count = 1;
while (count < position && curr != NULL) {
curr = curr->next;
count++;
}
if (curr == NULL) {
printf("無效的位置\n");
return;
}
if (curr->prev != NULL) {
curr->prev->next = curr->next;
} else {
*head = curr->next;
}
if (curr->next != NULL) {
curr->next->prev = curr->prev;
}
free(curr);
}
// 打印鏈表
void printList(Node* head) {
Node* curr = head;
while (curr != NULL) {
printf("%d ", curr->data);
curr = curr->next;
}
printf("\n");
}
int main() {
Node* head = NULL;
// 插入節(jié)點
insertFront(&head, 1);
insertEnd(&head, 2);
insertEnd(&head, 3);
insertAt(&head, 4, 2);
// 打印鏈表
printf("雙鏈表：");
printList(head);
// 刪除節(jié)點
deleteFront(&head);
deleteEnd(&head);
deleteAt(&head, 1);
// 打印鏈表
printf("刪除節(jié)點后的雙鏈表：");
printList(head);
return 0;
}
這段代碼實現(xiàn)了雙鏈表的創(chuàng)建節(jié)點、在鏈表頭部、末尾和指定位置插入節(jié)點，以及刪除鏈表頭部、末尾和指定位置節(jié)點，并且可以打印鏈表。你可以根據(jù)自己的需求進行擴展和修改。
雙鏈表的插入操作
雙鏈表的插入操作有三種情況：
- 在鏈表頭部插入節(jié)點
- 在鏈表末尾插入節(jié)點
- 在指定位置插入節(jié)點
下面是這三種情況的詳細說明和代碼實現(xiàn)。
- 在鏈表頭部插入節(jié)點
在鏈表頭部插入節(jié)點，只需要將新節(jié)點插入到原頭節(jié)點前面，并更新頭節(jié)點的指針。
void insertFront(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
newNode->next = *head;
(*head)->prev = newNode;
*head = newNode;
}
}
- 在鏈表末尾插入節(jié)點
在鏈表末尾插入節(jié)點，需要遍歷整個鏈表，找到最后一個節(jié)點，并將新節(jié)點插入到最后一個節(jié)點后面。
void insertEnd(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
Node* curr = *head;
while (curr->next != NULL) {
curr = curr->next;
}
curr->next = newNode;
newNode->prev = curr;
}
}
- 在指定位置插入節(jié)點
在指定位置插入節(jié)點，需要遍歷鏈表，找到指定位置的節(jié)點，并將新節(jié)點插入到該節(jié)點的前面，并更新相鄰節(jié)點的指針。
void insertAt(Node** head, int data, int position) {
if (position < 1) {
printf("無效的位置\n");
return;
}
if (position == 1) {
insertFront(head, data);
return;
}
Node* newNode = createNode(data);
Node* curr = *head;
int count = 1;
while (count < position - 1 && curr != NULL) {
curr = curr->next;
count++;
}
if (curr == NULL) {
printf("無效的位置\n");
return;
}
newNode->next = curr->next;
newNode->prev = curr;
if (curr->next != NULL) {
curr->next->prev = newNode;
}
curr->next = newNode;
}
注意，如果指定位置為1，則直接調(diào)用insertFront()函數(shù)插入節(jié)點。如果指定位置大于鏈表長度，則插入失敗，輸出錯誤信息。
上述代碼中，createNode()函數(shù)創(chuàng)建一個新節(jié)點，Node** head表示指向頭節(jié)點指針的指針，因為在插入操作中需要修改頭節(jié)點指針的值，而頭節(jié)點指針本身是一個指針變量，所以需要使用指向指針的指針來實現(xiàn)修改。
雙鏈表的刪除操作
雙鏈表的刪除操作有三種情況：
- 刪除鏈表頭部節(jié)點
- 刪除鏈表末尾節(jié)點
- 刪除指定位置節(jié)點
下面是這三種情況的詳細說明和代碼實現(xiàn)。
- 刪除鏈表頭部節(jié)點
刪除鏈表頭部節(jié)點，只需要將頭節(jié)點的下一個節(jié)點作為新的頭節(jié)點，并釋放原頭節(jié)點的內(nèi)存。
void deleteFront(Node** head) {
if (*head == NULL) {
printf("鏈表為空\n");
return;
}
Node* temp = *head;
*head = (*head)->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
free(temp);
}
- 刪除鏈表末尾節(jié)點
刪除鏈表末尾節(jié)點，需要遍歷整個鏈表，找到最后一個節(jié)點，并將倒數(shù)第二個節(jié)點的next指針置為NULL，并釋放最后一個節(jié)點的內(nèi)存。
void deleteEnd(Node** head) {
if (*head == NULL) {
printf("鏈表為空\n");
return;
}
Node* curr = *head;
while (curr->next != NULL) {
curr = curr->next;
}
if (curr->prev != NULL) {
curr->prev->next = NULL;
} else {
*head = NULL;
}
free(curr);
}
- 刪除指定位置節(jié)點
刪除指定位置節(jié)點，需要遍歷鏈表，找到指定位置的節(jié)點，更新相鄰節(jié)點的指針，并釋放目標(biāo)節(jié)點的內(nèi)存。
void deleteAt(Node** head, int position) {
if (*head == NULL || position < 1) {
printf("無效的位置\n");
return;
}
if (position == 1) {
deleteFront(head);
return;
}
Node* curr = *head;
int count = 1;
while (count < position && curr != NULL) {
curr = curr->next;
count++;
}
if (curr == NULL) {
printf("無效的位置\n");
return;
}
if (curr->prev != NULL) {
curr->prev->next = curr->next;
} else {
*head = curr->next;
}
if (curr->next != NULL) {
curr->next->prev = curr->prev;
}
free(curr);
}
注意，如果指定位置為1，則直接調(diào)用deleteFront()函數(shù)刪除頭部節(jié)點。如果指定位置大于鏈表長度，則刪除失敗，輸出錯誤信息。
上述代碼中，Node** head表示指向頭節(jié)點指針的指針，因為在刪除操作中需要修改頭節(jié)點指針的值，而頭節(jié)點指針本身是一個指針變量，所以需要使用指向指針的指針來實現(xiàn)修改。
循環(huán)鏈表
循環(huán)鏈表是一種特殊的鏈表，它與普通鏈表的區(qū)別在于，最后一個節(jié)點的next指針不是指向NULL，而是指向第一個節(jié)點，從而形成一個環(huán)形結(jié)構(gòu)。
循環(huán)鏈表有兩種基本類型：單向循環(huán)鏈表和雙向循環(huán)鏈表。單向循環(huán)鏈表中每個節(jié)點只有一個指針域，即指向下一個節(jié)點的指針，而雙向循環(huán)鏈表中每個節(jié)點有兩個指針域，即分別指向前一個節(jié)點和后一個節(jié)點的指針。
下面是一個單向循環(huán)鏈表的定義：
typedef struct Node {
int data;
struct Node* next;
} Node;
typedef struct CircularLinkedList {
Node* head;
} CircularLinkedList;
在單向循環(huán)鏈表中，頭節(jié)點的next指針指向第一個節(jié)點，而最后一個節(jié)點的next指針則指向頭節(jié)點。
循環(huán)鏈表的插入和刪除操作與普通鏈表類似，唯一的區(qū)別是在插入和刪除末尾節(jié)點時需要特殊處理，因為末尾節(jié)點的next指針指向頭節(jié)點而非NULL。
下面是一個簡單的單向循環(huán)鏈表的插入和刪除操作的示例代碼：
// 創(chuàng)建新節(jié)點
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 在鏈表末尾插入節(jié)點
void insertEnd(CircularLinkedList* list, int data) {
Node* newNode = createNode(data);
if (list->head == NULL) {
list->head = newNode;
newNode->next = list->head;
} else {
Node* curr = list->head;
while (curr->next != list->head) {
curr = curr->next;
}
curr->next = newNode;
newNode->next = list->head;
}
}
// 刪除指定位置的節(jié)點
void deleteAt(CircularLinkedList* list, int position) {
if (list->head == NULL) {
printf("鏈表為空\n");
return;
}
Node* curr = list->head;
Node* prev = NULL;
int count = 1;
while (count < position && curr->next != list->head) {
prev = curr;
curr = curr->next;
count++;
}
if (count < position) {
printf("無效的位置\n");
return;
}
if (prev == NULL) {
Node* tail = list->head;
while (tail->next != list->head) {
tail = tail->next;
}
list->head = curr->next;
tail->next = list->head;
} else {
prev->next = curr->next;
}
free(curr);
}
注意，上述代碼中，在刪除末尾節(jié)點時需要特判。如果目標(biāo)節(jié)點是頭節(jié)點，則需要更新頭節(jié)點指針的值，并將最后一個節(jié)點的next指針指向新的頭節(jié)點。如果目標(biāo)節(jié)點不是頭節(jié)點，則直接更新相鄰節(jié)點的指針即可。文章來源：http://www.zghlxwxcb.cn/news/detail-776727.html
循環(huán)鏈表的遍歷和其他操作與普通鏈表類似，只需要判斷是否回到了頭節(jié)點即可。文章來源地址http://www.zghlxwxcb.cn/news/detail-776727.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)（2）鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
