c语言 链表学习笔记
·
1：基础知识点
a：链表是由一系列独立的节点串联组成的线性数据结构，每个节点固定包含两个核心域：数据域与指针域。
数据域：专门用来存放节点要存储的实际数据
指针域：一个和节点同类型的指针变量，专门存放下一个节点的内存地址
在内存中是非连续存储的。和数组完全不同，数组的所有元素在内存中是一块连续、相邻的地址空间；而链表的每个节点可以分散在内存的不同位置，节点之间没有地址上的相邻要求，全靠指针域的地址来维系关联。
b：链表在指定位置插入、删除元素，不需要移动其他元素，仅需修改对应节点的指针指向即可。如果在数组中间插入 / 删除元素，需要移动插入位置之后的所有元素，数据量越大效率越低。
c：链表随机查找，访问速度远低于数组
d：没头结点的链表：头指针直接指向第一个存数据的节点。
头指针 -> 第1个数据节点 -> 第2个数据节点 -> ... -> NULL
当你插入新节点时，由于它是新的“第一名”，你必须强制修改头指针的指向，否则你找不到新的链表开头。
第一步：新节点的 next 指向当前的第一个节点。
第二步：头指针指向新节点。
有头结点链表：头指针指向头结点。
头指针 -> 头结点 -> 第1个数据节点 -> 第2个数据节点 -> ... -> NULL
这是最推荐的做法。此时，头指针永远指向那个不动的“头结点”。在第一个位置插入，其实就是在头结点后面加塞。
插入数据10演示：
具体例子：静态链表
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct linknode
{
int data;
struct linknode* next;
};
void test()
{
//创建结构体
struct linknode node1 = { 10,NULL };
struct linknode node2 = { 20,NULL };
struct linknode node3 = { 30,NULL };
struct linknode node4 = { 40,NULL };
struct linknode node5 = { 50,NULL };
//链表连接
node1.next = &node2;
node2.next = &node3;
node3.next = &node4;
node4.next = &node5;
node5.next = NULL;
struct linknode* pcurrent = &node1;
while (pcurrent != NULL)
{
printf("%d\n", pcurrent->data);
pcurrent = pcurrent->next;
}
}
int main()
{
test();
std::cout << "Hello World!\n";
}
2：动态链表
初始化
- 尾指针
plast避免了每次插入都遍历到尾部，效率极高； - 头结点是链表入口，永远不移动；
- 所有节点都用
malloc分配在堆区，不会自动释放。
// 初始化链表：用户循环输入数据，自动创建链表
struct LinkNode* int_link()
{
// 1. 创建头结点（堆区分配内存）
struct LinkNode* header = (struct LinkNode*)malloc(sizeof(struct LinkNode));
header->data = 0; // 头结点数据域无意义，赋0即可
header->next = NULL; // 初始链表为空，头结点指向NULL
// 2. 尾指针：始终指向链表最后一个节点（核心！）
struct LinkNode* plast = header;
int val = 0;
// 3. 循环输入数据，创建节点
while (1)
{
printf("请输入插入数据\n");
scanf_s("%d", &val);
if (val == 0) break; // 输入0退出循环
// 4. 为新节点分配堆内存
struct LinkNode* newnode = (struct LinkNode*)malloc(sizeof(struct LinkNode));
newnode->data = val; // 赋值用户输入的数据
newnode->next = NULL; // 新节点默认是尾节点，指向NULL
// 5. 尾插核心：把新节点挂到链表尾部
plast->next = newnode;
// 6. 更新尾指针，让它永远指向最后一个节点
plast = newnode;
}
return header; // 返回头结点（链表唯一入口）
}
插入函数：在指定节点前插入，如果没找到，直接在尾部插入
// 功能：在找到的 oldval 节点 前面 插入新节点 newval
void insert_value(struct LinkNode* header, int oldval, int newval)
{
if (NULL == header) return; // 健壮性判断：头结点为空直接退出
// 双指针：pre 指向当前节点的前驱，cru指向当前节点
struct LinkNode* pre = header;
struct LinkNode* cru = pre->next;
// 1. 查找目标值 oldval 的节点
while (cru != NULL)
{
if (cru->data == oldval) break; // 找到目标，退出循环
// 双指针同步向后移动
pre = cru;
cru = pre->next;
}
// 2. 创建新节点
struct LinkNode* newnode = (struct LinkNode*)malloc(sizeof(struct LinkNode));
newnode->data = newval;
newnode->next = NULL;
// 3. 插入核心（先连后断，防止断链）
newnode->next = cru; // 新节点先指向原节点
pre->next = newnode; // 前驱节点指向新节点，完成插入
}
删除函数
// 功能：删除第一个值为 delval 的节点
void delect_value(struct LinkNode* header, int delval)
{
if (NULL == header) return;
// 双指针：前驱+当前节点
struct LinkNode* pre = header;
struct LinkNode* pcu = pre->next;
// 1. 查找要删除的节点
while (pcu != NULL)
{
if (pcu->data == delval) break;
pre = pcu;
pcu = pcu->next;
}
if (pcu == NULL) return; // 没找到，直接退出
// 2. 删除核心：前驱跳过待删除节点，指向后继
pre->next = pcu->next;
free(pcu); // 必须释放malloc申请的内存！
pcu = NULL; // 置空指针，避免野指针
}
遍历函数
// 功能：打印链表所有数据
void for_read_value(struct LinkNode* header)
{
if (NULL == header) return;
// 临时指针：从头结点的下一个节点开始（头结点无数据）
struct LinkNode* pcurrent = header->next;
// 循环遍历到尾节点（NULL为止）
while (pcurrent != NULL)
{
printf("%d\n", pcurrent->data);
pcurrent = pcurrent->next; // 指针向后移动
}
}
销毁函数：整个链表销毁
// 功能：销毁整个链表，释放所有内存（包括头结点）
void destroy_link(struct LinkNode* header)
{
if (NULL == header) return;
struct LinkNode* pcur = header;
while (pcur != NULL)
{
struct LinkNode* Pnex = pcur->next; // 关键：先保存下一个节点地址
free(pcur); // 释放当前节点
pcur = Pnex; // 指针后移
}
}
清空函数：
清空：释放数据节点，保留头结点，链表可以继续使用
// 功能：清空所有数据节点，头结点保留（链表可重新使用）
void delect_all_value(struct LinkNode* header)
{
if (NULL == header) return;
// 从头结点的下一个节点开始释放
struct LinkNode* pcur = header->next;
while (pcur != NULL)
{
struct LinkNode* Pnex = pcur->next;
free(pcur);
pcur = Pnex;
}
header->next = NULL; // 头结点指向NULL，链表变回空链表
}
完整的c文件
#include "link.h"
//初始化
struct LinkNode* int_link()
{
//创建头结点
struct LinkNode* header = (struct LinkNode*)malloc(sizeof(struct LinkNode));
header->data = 0;//头节点不需要存数据
header->next = NULL;//起始为空，后面开始填入第一个节点的地址
//尾部指针
struct LinkNode* plast = header;//指针变量存入头结点的地址
int val = 0;
while (1)
{
printf("请输入插入数据\n");
scanf_s("%d", &val);
if (val == 0)
{
break;
}
struct LinkNode* newnode = (struct LinkNode*)malloc(sizeof(struct LinkNode));
newnode->data = val;
newnode->next = NULL;//最后的节点为空
plast->next = newnode;//节点插入到链表中
plast = newnode;//更新指针 最后指向的位置
}
return header;
}
//插入
void insert_value(struct LinkNode* header, int oldval, int newval)
{
if (NULL == header)
{
return;
}
struct LinkNode* pre = header;
struct LinkNode* cru = pre->next;
while (cru !=NULL )//查找旧值是否存在
{
if (cru->data == oldval)
{
break;
}
pre = cru;
cru = pre->next;
}
//if (cru == NULL)//如果cru存放的地址是空，说明找不到旧的value值
//{
// return;
//}
//创建新节点
struct LinkNode* newnode =(struct LinkNode*) malloc(sizeof(struct LinkNode));
newnode->data = newval;
newnode->next = NULL;
//新节点插入
newnode->next = cru;
pre->next = newnode;
}
//删除单个节点
void delect_value(struct LinkNode* header, int delval)
{
if (NULL == header)
{
return;
}
struct LinkNode* pre = header;
struct LinkNode* pcu = pre->next;
while (pcu != NULL)
{
if (pcu->data == delval)
{
break;
}
pre = pcu;
pcu = pcu->next;
}
if (pcu == NULL)//找不到要删除的节点
{
return;
}
//找到了要删除的节点
pre->next = pcu->next;
free(pcu);
pcu = NULL;
}
//遍历
void for_read_value(struct LinkNode* header)
{
if (NULL == header)
{
return;
}
struct LinkNode* pcurrent = header->next;//不需要打印头，直接打印头里面存放下一个数据地址的信息
while (pcurrent != NULL)
{
printf("%d\n", pcurrent->data);
pcurrent = pcurrent->next;
}
}
//销毁整个链表
void destroy_link(struct LinkNode* header)
{
if (NULL == header)
{
return;
}
struct LinkNode* pcur = header;
while (pcur != NULL)
{
struct LinkNode* Pnex = pcur->next;//先保存当前节点的 下一个节点地址
free(pcur);//释放当前节点内存
pcur = Pnex;
}
}
//清空
void delect_all_value(struct LinkNode* header)
{
if (NULL == header)
{
return;
}
struct LinkNode* pcur = header->next;//清空头结点之后的数据
while (pcur != NULL)
{
struct LinkNode* Pnex = pcur->next;//先保存当前节点的 下一个节点地址
free(pcur);
pcur = Pnex;
}
header->next = NULL;
}
.h文件
#pragma once
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#ifdef __cplusplus
extern "C" {
#endif
// 定义节点数据类型
struct LinkNode
{
int data;
struct LinkNode* next;
};
//初始化
struct LinkNode* int_link();
//插入
void insert_value(struct LinkNode* header, int old, int newval);
//删除
void delect_value(struct LinkNode* header, int delval);
//遍历
void for_read_value(struct LinkNode* header);
//销毁
void destroy_link(struct LinkNode* header);
//清空
void delect_all_value(struct LinkNode* header);
#ifdef __cplusplus
}
#endif#pragma once
main
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "link.h"
int main()
{
struct LinkNode* header = int_link();
for_read_value(header);//遍历打印
std::cout << "-------------\n";
insert_value(header, 100, 6666);//如果有100，在一百前面插入666
for_read_value(header);//遍历打印
delect_value(header,20);
std::cout << "-------------\n";
for_read_value(header);//遍历打印
std::cout << "Hello World!\n";
delect_all_value(header);
for_read_value(header);//遍历打印
destroy_link(header);
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
0
0- 0
已为社区贡献3条内容
所有评论(0)