在計算機科學中，數據結構是組織和存儲數據的方式，以便能夠高效地訪問和修改數據。單鏈表是一種常見的數據結構，廣泛應用于各種編程場景中。本文將詳細介紹單鏈表的基本概念、存儲結構、基本操作以及應用實例，并通過C語言代碼示例進行深入分析。
單鏈表（Singly Linked List）是一種線性數據結構，由一系列節點組成，每個節點包含兩個部分：數據域和指針域。數據域用于存儲數據，指針域用于指向下一個節點。單鏈表的特點是只能單向遍歷，即從頭節點開始，依次訪問每個節點，直到尾節點。
單鏈表的存儲結構可以用C語言中的結構體來表示。每個節點包含一個數據域和一個指向下一個節點的指針。以下是一個簡單的單鏈表節點結構體定義：
struct Node {
int data; // 數據域
struct Node* next; // 指針域，指向下一個節點
};
創建單鏈表的過程包括初始化頭節點和添加后續節點。以下是一個創建單鏈表的C語言代碼示例：
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// 創建單鏈表
struct Node* createLinkedList(int arr[], int n) {
struct Node *head = NULL, *temp = NULL, *current = NULL;
for (int i = 0; i < n; i++) {
temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = arr[i];
temp->next = NULL;
if (head == NULL) {
head = temp;
} else {
current->next = temp;
}
current = temp;
}
return head;
}
// 打印單鏈表
void printLinkedList(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
struct Node* head = createLinkedList(arr, n);
printLinkedList(head);
return 0;
}
在單鏈表中插入節點可以分為三種情況：在鏈表頭部插入、在鏈表尾部插入和在鏈表中間插入。以下是一個在單鏈表中插入節點的C語言代碼示例：
// 在鏈表頭部插入節點
struct Node* insertAtHead(struct Node* head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = head;
return newNode;
}
// 在鏈表尾部插入節點
struct Node* insertAtTail(struct Node* head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (head == NULL) {
return newNode;
}
struct Node* current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
return head;
}
// 在鏈表中間插入節點
struct Node* insertAtMiddle(struct Node* head, int data, int position) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
if (position == 0) {
newNode->next = head;
return newNode;
}
struct Node* current = head;
for (int i = 0; i < position - 1 && current != NULL; i++) {
current = current->next;
}
if (current == NULL) {
printf("Position out of range\n");
return head;
}
newNode->next = current->next;
current->next = newNode;
return head;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
struct Node* head = createLinkedList(arr, n);
printLinkedList(head);
head = insertAtHead(head, 0);
printLinkedList(head);
head = insertAtTail(head, 6);
printLinkedList(head);
head = insertAtMiddle(head, 7, 3);
printLinkedList(head);
return 0;
}
在單鏈表中刪除節點可以分為三種情況：刪除頭節點、刪除尾節點和刪除中間節點。以下是一個在單鏈表中刪除節點的C語言代碼示例：
// 刪除頭節點
struct Node* deleteAtHead(struct Node* head) {
if (head == NULL) {
printf("List is empty\n");
return NULL;
}
struct Node* temp = head;
head = head->next;
free(temp);
return head;
}
// 刪除尾節點
struct Node* deleteAtTail(struct Node* head) {
if (head == NULL) {
printf("List is empty\n");
return NULL;
}
if (head->next == NULL) {
free(head);
return NULL;
}
struct Node* current = head;
while (current->next->next != NULL) {
current = current->next;
}
free(current->next);
current->next = NULL;
return head;
}
// 刪除中間節點
struct Node* deleteAtMiddle(struct Node* head, int position) {
if (head == NULL) {
printf("List is empty\n");
return NULL;
}
if (position == 0) {
struct Node* temp = head;
head = head->next;
free(temp);
return head;
}
struct Node* current = head;
for (int i = 0; i < position - 1 && current != NULL; i++) {
current = current->next;
}
if (current == NULL || current->next == NULL) {
printf("Position out of range\n");
return head;
}
struct Node* temp = current->next;
current->next = current->next->next;
free(temp);
return head;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
struct Node* head = createLinkedList(arr, n);
printLinkedList(head);
head = deleteAtHead(head);
printLinkedList(head);
head = deleteAtTail(head);
printLinkedList(head);
head = deleteAtMiddle(head, 1);
printLinkedList(head);
return 0;
}
在單鏈表中查找節點可以通過遍歷鏈表來實現。以下是一個在單鏈表中查找節點的C語言代碼示例：
// 查找節點
struct Node* searchNode(struct Node* head, int data) {
struct Node* current = head;
while (current != NULL) {
if (current->data == data) {
return current;
}
current = current->next;
}
return NULL;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
struct Node* head = createLinkedList(arr, n);
printLinkedList(head);
struct Node* result = searchNode(head, 3);
if (result != NULL) {
printf("Node found: %d\n", result->data);
} else {
printf("Node not found\n");
}
return 0;
}
遍歷單鏈表是指依次訪問鏈表中的每個節點，并對其進行操作。以下是一個遍歷單鏈表的C語言代碼示例：
// 遍歷單鏈表
void traverseLinkedList(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
struct Node* head = createLinkedList(arr, n);
traverseLinkedList(head);
return 0;
}
單鏈表可以用于實現學生信息管理系統。以下是一個簡單的學生信息管理系統的C語言代碼示例：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Student {
int id;
char name[50];
float grade;
struct Student* next;
};
// 創建學生信息鏈表
struct Student* createStudentList(int ids[], char names[][50], float grades[], int n) {
struct Student *head = NULL, *temp = NULL, *current = NULL;
for (int i = 0; i < n; i++) {
temp = (struct Student*)malloc(sizeof(struct Student));
temp->id = ids[i];
strcpy(temp->name, names[i]);
temp->grade = grades[i];
temp->next = NULL;
if (head == NULL) {
head = temp;
} else {
current->next = temp;
}
current = temp;
}
return head;
}
// 打印學生信息鏈表
void printStudentList(struct Student* head) {
struct Student* current = head;
while (current != NULL) {
printf("ID: %d, Name: %s, Grade: %.2f\n", current->id, current->name, current->grade);
current = current->next;
}
}
// 插入學生信息
struct Student* insertStudent(struct Student* head, int id, char name[], float grade) {
struct Student* newNode = (struct Student*)malloc(sizeof(struct Student));
newNode->id = id;
strcpy(newNode->name, name);
newNode->grade = grade;
newNode->next = head;
return newNode;
}
// 刪除學生信息
struct Student* deleteStudent(struct Student* head, int id) {
struct Student* current = head;
struct Student* previous = NULL;
while (current != NULL && current->id != id) {
previous = current;
current = current->next;
}
if (current == NULL) {
printf("Student with ID %d not found\n", id);
return head;
}
if (previous == NULL) {
head = current->next;
} else {
previous->next = current->next;
}
free(current);
return head;
}
// 查找學生信息
struct Student* searchStudent(struct Student* head, int id) {
struct Student* current = head;
while (current != NULL) {
if (current->id == id) {
return current;
}
current = current->next;
}
return NULL;
}
int main() {
int ids[] = {1, 2, 3};
char names[][50] = {"Alice", "Bob", "Charlie"};
float grades[] = {85.5, 90.0, 78.5};
int n = sizeof(ids) / sizeof(ids[0]);
struct Student* head = createStudentList(ids, names, grades, n);
printStudentList(head);
head = insertStudent(head, 4, "David", 88.0);
printStudentList(head);
head = deleteStudent(head, 2);
printStudentList(head);
struct Student* result = searchStudent(head, 3);
if (result != NULL) {
printf("Student found: ID: %d, Name: %s, Grade: %.2f\n", result->id, result->name, result->grade);
} else {
printf("Student not found\n");
}
return 0;
}
單鏈表是一種簡單而靈活的數據結構，適用于需要頻繁插入和刪除操作的場景。通過本文的介紹，我們了解了單鏈表的基本概念、存儲結構、基本操作以及應用實例。雖然單鏈表在某些方面存在不足，但其動態內存分配和高效插入刪除操作的優點使其在許多實際應用中仍然具有重要價值。希望本文能夠幫助讀者更好地理解和應用單鏈表這一數據結構。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
