数据结构中的线性表链式存储介绍及其基本操作
在数据结构中，线性表是一种基本的数据结构。它是一组具有相同类型的元素的有序集合。线性表的存储方式有两种：顺序存储和链式存储。本文将重点介绍线性表的链式存储及其相关的基本操作，并提供相应的C语言代码示例。
线性表的链式存储
链式存储，又称链表，是通过一系列节点来存储数据的。每个节点包含两个部分：数据域和指针域。数据域存储数据元素，指针域存储下一个节点的地址。根据指针域的数量和结构，链表可以分为以下几种类型：
- 单向链表：每个节点只包含一个指针域，指向下一个节点。
- 双向链表：每个节点包含两个指针域，分别指向前一个节点和后一个节点。
- 循环链表：在单向链表或双向链表的基础上，使最后一个节点的指针指向链表的头节点，从而形成一个环。
单向链表
单向链表是最基本的一种链表结构。它的基本操作包括节点的插入、删除、查找和遍历。下面我们以单向链表为例，介绍其基本操作及相应的C语言代码实现。
单向链表的基本操作
节点结构
首先，我们需要定义单向链表节点的结构体：
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {
int data; // 数据域
struct Node* next; // 指针域
} Node;
创建新节点
创建一个新节点并返回其指针：
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("内存分配失败\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
插入节点
在链表的头部插入新节点：
void insertAtHead(Node** head, int data) {
Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}
在链表的尾部插入新节点：
void insertAtTail(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
删除节点
删除链表中指定数据的节点：
void deleteNode(Node** head, int data) {
Node* temp = *head;
Node* prev = NULL;
// 如果头节点就是要删除的节点
if (temp != NULL && temp->data == data) {
*head = temp->next;
free(temp);
return;
}
// 查找要删除的节点
while (temp != NULL && temp->data != data) {
prev = temp;
temp = temp->next;
}
// 如果未找到要删除的节点
if (temp == NULL) return;
// 断开链接并释放内存
prev->next = temp->next;
free(temp);
}
查找节点
在链表中查找指定数据的节点：
Node* searchNode(Node* head, int data) {
Node* current = head;
while (current != NULL) {
if (current->data == data) {
return current;
}
current = current->next;
}
return NULL;
}
遍历链表
遍历并打印链表中的所有节点：
void printList(Node* head) {
Node* current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
示例代码
最后，我们将上述操作结合起来，展示一个简单的示例程序：
int main() {
Node* head = NULL;
// 插入节点
insertAtHead(&head, 1);
insertAtHead(&head, 2);
insertAtTail(&head, 3);
insertAtTail(&head, 4);
// 打印链表
printf("链表内容: ");
printList(head);
// 查找节点
int key = 3;
Node* searchResult = searchNode(head, key);
if (searchResult != NULL) {
printf("找到节点: %d\n", searchResult->data);
} else {
printf("节点 %d 未找到\n", key);
}
// 删除节点
deleteNode(&head, 2);
printf("删除节点 2 后的链表: ");
printList(head);
// 释放链表内存
while (head != NULL) {
Node* temp = head;
head = head->next;
free(temp);
}
return 0;
}
总结
链式存储是线性表的一种重要存储方式，它通过节点和指针的结构，实现了灵活的动态存储管理。本文介绍了单向链表的基本操作，并提供了相应的C语言代码示例。理解和掌握链表的操作对学习和应用数据结构具有重要意义。希望这篇博客能帮助你更好地理解线性表的链式存储。
