当前位置： 首页 > news >正文

数据结构入门:链表

news 2025/7/5 16:28:11

链式存储结构通过使用指针将分散的存储单元链接起来，每个元素由数据部分和指针部分组成。

链式表的定义和特点

链式表的每个节点包含两个部分：

  1. 数据域：存储数据元素。
  2. 指针域：存储下一个节点的内存地址。

链式表的头指针指向第一个节点，最后一个节点的指针域为NULL，表示链表结束。链式表的特点是插入和删除操作比较方便，不需要移动大量元素，但随机访问效率较低。

示例代码：链式表的实现及取值操作（C语言）

#include <stdio.h>
#include <stdlib.h>// 定义链式表节点结构
typedef struct Node {int data;             // 数据域struct Node *next;    // 指针域，指向下一个节点
} Node;// 创建新节点
Node* create_node(int value) {Node *new_node = (Node*)malloc(sizeof(Node));  // 分配内存if (new_node == NULL) {printf("内存分配失败\n");exit(1);  // 分配失败则退出程序}new_node->data = value;  // 设置节点数据new_node->next = NULL;   // 初始化指针为NULLreturn new_node;  // 返回新节点的指针
}// 在链表尾部插入节点
void append(Node **head, int value) {Node *new_node = create_node(value);  // 创建新节点if (*head == NULL) {  // 如果链表为空*head = new_node;  // 新节点成为头节点return;}Node *current = *head;  // 从头节点开始遍历while (current->next != NULL) {  // 找到链表的最后一个节点current = current->next;}current->next = new_node;  // 将新节点链接到链表末尾
}// 获取指定位置的元素值
int get_value(Node *head, int pos, int *value) {if (head == NULL) {  // 如果链表为空printf("链表为空\n");return 0;  // 返回0表示失败}Node *current = head;int index = 0;while (current != NULL) {  // 遍历链表if (index == pos) {  // 找到指定位置*value = current->data;  // 获取节点数据return 1;  // 返回1表示成功}current = current->next;  // 移动到下一个节点index++;}printf("位置超出范围\n");  // 如果遍历完链表也没找到指定位置return 0;  // 返回0表示失败
}// 打印链表
void print_list(Node *head) {Node *current = head;printf("链表内容：");while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}// 释放链表内存
void free_list(Node *head) {Node *current = head;while (current != NULL) {Node *temp = current;current = current->next;free(temp);}
}int main() {Node *head = NULL;  // 初始化链表为空append(&head, 10);  // 向链表尾部添加元素10append(&head, 20);  // 向链表尾部添加元素20append(&head, 30);  // 向链表尾部添加元素30print_list(head);  // 打印链表内容int value;if (get_value(head, 1, &value)) {  // 获取索引1的元素值printf("索引1的元素值：%d\n", value);}free_list(head);  // 释放链表内存return 0;
}

代码各模块注释

定义链式表节点结构

typedef struct Node {int data;             // 数据域struct Node *next;    // 指针域，指向下一个节点
} Node;
  • 定义了一个名为 Node 的结构体类型，表示链式表的节点。
  • int data; 用于存储节点的数据。
  • struct Node *next; 是一个指向 Node 类型的指针，用于存储下一个节点的内存地址。

创建新节点

Node* create_node(int value) {Node *new_node = (Node*)malloc(sizeof(Node));  // 分配内存if (new_node == NULL) {printf("内存分配失败\n");exit(1);  // 分配失败则退出程序}new_node->data = value;  // 设置节点数据new_node->next = NULL;   // 初始化指针为NULLreturn new_node;  // 返回新节点的指针
}
  • Node *new_node = (Node*)malloc(sizeof(Node)); 使用 malloc 函数动态分配内存，为新节点分配大小为 sizeof(Node) 的内存空间。
  • if (new_node == NULL) { ... } 检查内存分配是否成功。如果失败，打印错误信息并退出程序。
  • new_node->data = value; 将传入的 value 值赋给新节点的数据域。
  • new_node->next = NULL; 将新节点的指针域初始化为 NULL，表示该节点目前没有指向下一个节点。
  • return new_node; 返回新创建的节点的指针。

在链表尾部插入节点

void append(Node **head, int value) {Node *new_node = create_node(value);  // 创建新节点if (*head == NULL) {  // 如果链表为空*head = new_node;  // 新节点成为头节点return;}Node *current = *head;  // 从头节点开始遍历while (current->next != NULL) {  // 找到链表的最后一个节点current = current->next;}current->next = new_node;  // 将新节点链接到链表末尾
}
  • Node *new_node = create_node(value); 调用 create_node 函数创建一个新节点。
  • if (*head == NULL) { ... } 检查链表是否为空。如果链表为空（头指针为 NULL），将新节点设置为头节点。
  • Node *current = *head; 定义一个指针 current，初始化为链表的头节点，用于遍历链表。
  • while (current->next != NULL) { ... } 遍历链表，直到找到最后一个节点（其 next 指针为 NULL）。
  • current->next = new_node; 将最后一个节点的 next 指针指向新节点，将新节点添加到链表末尾。

获取指定位置的元素值

int get_value(Node *head, int pos, int *value) {if (head == NULL) {  // 如果链表为空printf("链表为空\n");return 0;  // 返回0表示失败}Node *current = head;int index = 0;while (current != NULL) {  // 遍历链表if (index == pos) {  // 找到指定位置*value = current->data;  // 获取节点数据return 1;  // 返回1表示成功}current = current->next;  // 移动到下一个节点index++;}printf("位置超出范围\n");  // 如果遍历完链表也没找到指定位置return 0;  // 返回0表示失败
}
  • if (head == NULL) { ... } 检查链表是否为空。如果为空，打印错误信息并返回0表示失败。
  • Node *current = head; 定义一个指针 current，初始化为链表的头节点，用于遍历链表。
  • int index = 0; 用于记录当前遍历到的节点位置。
  • while (current != NULL) { ... } 遍历链表，直到 current 为 NULL（链表结束）。
  • if (index == pos) { ... } 检查当前节点的位置是否为目标位置 pos。如果是，将当前节点的数据赋值给 *value，并返回1表示成功。
  • current = current->next; 移动 current 指针到下一个节点。
  • index++; 增加位置计数器。
  • 如果遍历完整个链表都没有找到目标位置，打印错误信息并返回0表示失败。

打印链表

void print_list(Node *head) {Node *current = head;printf("链表内容：");while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}
  • Node *current = head; 定义一个指针 current，初始化为链表的头节点，用于遍历链表。
  • printf("链表内容："); 打印提示信息。
  • while (current != NULL) { ... } 遍历链表，直到 current 为 NULL。
  • printf("%d ", current->data); 打印当前节点的数据。
  • current = current->next; 移动 current 指针到下一个节点。
  • printf("\n"); 打印换行符，换行。

释放链表内存

void free_list(Node *head) {Node *current = head;while (current != NULL) {Node *temp = current;current = current->next;free(temp);}
}
  • Node *current = head; 定义一个指针 current，初始化为链表的头节点，用于遍历链表。
  • while (current != NULL) { ... } 遍历链表，直到 current 为 NULL。
  • Node *temp = current; 保存当前节点的指针到 temp。
  • current = current->next; 移动 current 指针到下一个节点。
  • free(temp); 释放 temp 指向的节点内存。

主函数

int main() {Node *head = NULL;  // 初始化链表为空append(&head, 10);  // 向链表尾部添加元素10append(&head, 20);  // 向链表尾部添加元素20append(&head, 30);  // 向链表尾部添加元素30print_list(head);  // 打印链表内容int value;if (get_value(head, 1, &value)) {  // 获取索引1的元素值printf("索引1的元素值：%d\n", value);}free_list(head);  // 释放链表内存return 0;
}
  • Node *head = NULL; 声明一个指向 Node 的指针 head，并初始化为 NULL，表示链表为空。
  • append(&head, 10); 调用 append 函数向链表尾部添加元素10。
  • append(&head, 20); 向链表尾部添加元素20。
  • append(&head, 30); 向链表尾部添加元素30。
  • print_list(head); 调用 print_list 函数打印链表的内容。
  • int value; 声明一个整型变量 value，用于存储获取的元素值。
  • if (get_value(head, 1, &value)) { ... } 调用 get_value 函数尝试获取索引1处的元素值。如果成功，打印该值。
  • free_list(head); 调用 free_list 函数释放链表占用的内存。
  • return 0; 返回0，表示程序正常结束。
http://www.lryc.cn/news/580189.html

相关文章：

  • 服务器的IO性能怎么看？
  • 数据库11：MySQL 库的操作、库的说明与表的操作、表的说明
  • 电机转速控制系统算法分析与设计
  • 微信小程序如何实现再多个页面共享数据
  • 达梦数据库DMHS介绍及安装部署
  • vue/微信小程序/h5 实现react的boundary
  • 使用Spring AOP实现@Log注解记录请求参数和执行时间
  • Linux基础 -- NAND Flash UBIFS基础特性及注意点
  • Adobe Illustrator设置的颜色和显示的颜色不对应问题
  • 新手快速入门Luban+Unity使用
  • OneCode 智能化UI布局与定位：注解驱动的视觉编排艺术
  • 打通线上线下会议室联动的综合解决方案及技术选型
  • Echarts3D柱状图-圆柱体-文字在柱体上垂直显示的实现方法
  • D3 面试题100道之（21-40）
  • 如何查看自己电脑的CUDA版本？
  • 服务器间接口安全问题的全面分析
  • 学习者的Python项目灵感
  • 本地区块链服务在物联网中的应用实例
  • Rust+Blender：打造高性能游戏引擎
  • OneCode图生代码技术深度解析：从可视化设计到注解驱动实现的全链路架构
  • golang 中当 JSON 数据缺少结构体（struct）中定义的某些字段，会有异常吗
  • 【HDMI CEC】 设备 OSD 名称功能详解
  • Rust match 控制流结构
  • 从0开始学习R语言--Day38--辛普森多样性指数
  • 重学前端002 --响应式网页设计 CSS
  • 【网络安全基础】第三章---公钥密码和消息认证
  • ＜tauri＞＜rust＞＜GUI＞使用tauri创建一个文件夹扫描程序
  • 【网络】Linux 内核优化实战 - net.core.flow_limit_table_len
  • C++26 下一代C++标准
  • 深度学习笔记29-RNN实现阿尔茨海默病诊断(Pytorch)