[数据结构]无头单向非循环链表的实现与应用
文章目录
一、引言
在踏入编程的奇幻世界时，我们常常会遇到各种奇妙的数据结构，它们如同搭建宏伟城堡的砖石，不可或缺。而要想深入理解无头单向非循环链表这一复杂而强大的数据结构，首先得从它的基石 —— 线性表的基本概念开始。本文将分为两大篇章，第一篇章将带你漫步于线性表的瑰丽花园，探索其本质与奥秘；第二篇章则将引领你穿越无头单向非循环链表的迷雾，领略其实现与应用的壮丽风景。
对于指针和数组还感到迷茫的朋友，这里有一个精心准备的传送门，它将是你探索这些基石概念的得力助手。请放心，一旦你掌握了这些基础知识，无头单向非循环链表的神秘面纱将不再难以揭开。
二、线性表的基本概念
1、线性表是什么
想象一下，你手中握着一串璀璨的珍珠项链，每一颗珍珠都紧紧相连，形成一个有序的整体。这就是线性表的生动写照。线性表，简单来说，就是一系列具有相同特性的数据元素的有限序列，它们之间存在着一对一的相邻关系，如同项链上的珍珠，一个接一个，既独立又紧密相连。
2、链表与顺序表的区别
线性表有两种基本的存储结构：链表和顺序表。顺序表，就像是一个排列整齐的书架，每个位置都预先分配好了，书籍（数据元素）按照顺序摆放。而链表，则更像是那条珍珠项链，每颗珍珠（数据元素）都通过一根无形的线（指针）与下一颗珍珠相连，形成了一条灵活的链条。链表允许在任意位置添加或删除元素，而无需移动其他元素，这正是其独特魅力所在。
3、无头单向非循环链表
在无头单向非循环链表中，我们没有那颗象征起点的 “头珍珠” ，也没有形成一个闭环的链条。每个节点都只知道如何找到它的下一个节点（如果存在的话），但不知道整个链条的起点或终点在哪里。这种结构简洁而灵活，非常适合用于需要频繁添加或删除元素的场景。
三、无头单向非循环链表的实现
1、结构体定义
首先，我们需要定义一个结构体来表示链表中的每一个节点。这个结构体通常包含两个部分：一是存储数据元素的数据域；二是指向下一个节点的指针域。
typedef int DataType;
typedef struct SListNode {
DataType data;//数据域
struct SListNode* next;//指针域
}SL;
2、初始化
创建一个无头单向非循环链表，首先需要初始化这个链表，即创建第一个节点，并让它指向NULL。
void Init(SL** head, DataType data)
{
assert(head != NULL && *head == NULL);
SL* pos = (SL*)malloc(sizeof(SL));
if (pos == NULL)
{
fprintf(stderr, "内存分配失败");
exit(EXIT_FAILURE);
}
pos->data = data;
pos->next = *head;
(*head) = pos;
}
3、销毁
当链表不再需要时，我们应该及时释放它所占用的内存资源。遍历链表，逐一释放每个节点的内存，最后将头指针也置为NULL。
void Destory(SL** head)
{
if (head == NULL)
return;
while (*head != NULL)
{
SL* next = (*head)->next;
free(*head);
*head = next;
}
*head = NULL;
}
4、显示
为了查看链表中的元素，我们需要遍历链表，并依次打印出每个节点的数据域。
void Print(SL** head, void (*Prin) (DataType))
{
assert(head != NULL && Prin != NULL);
for (SL* i = *head; i != NULL; i = i->next)
{
Prin(i->data);
}
printf("NULL\n");
}
5、增删查改
链表的核心操作包括增加、删除、查找和修改节点。这些操作都需要我们灵活运用指针来定位、修改或删除链表中的节点。
void PushFront(SL** head, DataType data)
{
assert(head != NULL);
SL* pos = (SL*)malloc(sizeof(SL));
if (pos == NULL)
{
fprintf(stderr, "内存分配失败");
exit(EXIT_FAILURE);
}
pos->data = data;
pos->next = *head;
*head = pos;
}
void PopFront(SL** head)
{
assert(head != NULL && *head != NULL);
SL* next = (*head)->next;
free(*head);
*head = next;
}
void PushBack(SL** head, DataType data)
{
Insert(head, NULL, data);
}
void PopBack(SL** head)
{
assert(head != NULL && *head != NULL);
for (SL* i = *head; i->next != NULL; i = i->next)
{
if (i->next->next == NULL)
{
free(i->next);
i->next = NULL;
return;
}
}
}
void Insert(SL** head, SL* x, DataType data)
{
assert(head != NULL);
if (*head == x)
{
PushFront(head, data);
}
for (SL* i = *head; i != NULL; i = i->next)
{
if (i->next == x)
{
SL* pos = (SL*)malloc(sizeof(SL));
if (pos == NULL)
{
fprintf(stderr, "内存分配失败");
exit(EXIT_FAILURE);
}
pos->data = data;
pos->next = i->next;
i->next = pos;
return;
}
}
assert(0);
}
void Erase(SL** head, SL* x)
{
assert(head != NULL && *head != NULL && x != NULL);
if (*head == x)
{
PopFront(head);
}
for (SL* i = *head; i != NULL; i = i->next)
{
if (i->next == x)
{
i->next = x->next;
free(x);
return;
}
}
assert(0);
}
SL* Find(SL** head, DataType data)
{
assert(head != NULL && *head != NULL);
for (SL* i = *head; i != NULL; i = i->next)
{
if (i->data == data)
return i;
}
return NULL;
}
void Modify(SL** head, SL* x, DataType data)
{
assert(head != NULL && x != NULL);
for (SL* i = *head; i != NULL; i = i->next)
{
if (i == x)
{
i->data = data;
return;
}
}
assert(0);
}
四、分析无头单向非循环链表
1、存储方式
无头单向非循环链表采用动态分配内存的方式来存储节点，每个节点只保存指向下一个节点的指针。这种存储方式使得链表能够灵活地应对元素数量的变化。
2、优点
- 无需预先分配固定大小的存储空间，能够根据需要动态地增加或减少节点。
- 插入和删除操作的时间复杂度较低，特别是在链表中间或尾部进行操作时。
3、缺点
- 访问链表中任意位置的元素需要从头开始遍历，因此时间复杂度较高。
- 链表的每个节点都需要额外的指针域来存储指向下一个节点的指针，这会增加一定的内存开销。
五、总结
1、练习题
2、源代码
对于无头单向非循环链表的源代码我已经开源在GItee：传送门
原文地址：https://blog.csdn.net/2301_79450966/article/details/142442441
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！