[数据结构]无头单向非循环链表的实现与应用

一、引言

在踏入编程的奇幻世界时，我们常常会遇到各种奇妙的数据结构，它们如同搭建宏伟城堡的砖石，不可或缺。而要想深入理解无头单向非循环链表这一复杂而强大的数据结构，首先得从它的基石 —— 线性表的基本概念开始。本文将分为两大篇章，第一篇章将带你漫步于线性表的瑰丽花园，探索其本质与奥秘；第二篇章则将引领你穿越无头单向非循环链表的迷雾，领略其实现与应用的壮丽风景。

对于指针和数组还感到迷茫的朋友，这里有一个精心准备的传送门，它将是你探索这些基石概念的得力助手。请放心，一旦你掌握了这些基础知识，无头单向非循环链表的神秘面纱将不再难以揭开。

---

二、线性表的基本概念

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：传送门

---