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

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

news 来源：原创 2024/9/28 1:50:11

文章目录

一、引言
二、线性表的基本概念
- 1、线性表是什么
- 2、链表与顺序表的区别
- 3、无头单向非循环链表
三、无头单向非循环链表的实现
- 1、结构体定义
- 2、初始化
- 3、销毁
- 4、显示
- 5、增删查改
四、分析无头单向非循环链表
- 1、存储方式
- 2、优点
- 3、缺点
五、总结
- 1、练习题
- 2、源代码

一、引言

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

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

二、线性表的基本概念

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);
}