(图像由AI生成)
0.前言
在计算机科学中,数据结构是存储和组织数据的一种方式,它不仅影响数据的存储,也影响数据的检索和更新效率。C语言,作为一种经典的编程语言,提供了灵活的方式来处理数据结构,其中链表是最基本且重要的一种。
1.链表的概念及结构
1.1概念
链表(Linked List)是一种在物理上非连续、非顺序的数据结构,由一系列节点(Node)组成。链表的每个节点由两部分构成:一是存储数据元素的数据域,二是存储下一个节点地址的指针域。这种结构允许在不重新整理整个数据结构的情况下,有效地插入和删除节点。
1.2结构特点
- 动态存储管理:链表的大小不是在编译时确定的,而是在运行时通过申请内存来构建的,这意味着它可以根据需要动态地扩展或缩减。
- 节点构成:链表的每个节点通常是一个对象或结构体,包含至少两个元素:
- 数据域:存储数据值。
- 指针域:指向列表中下一个节点的指针。
- 头指针:链表通过一个外部引用(通常是一个指针)来访问,这个引用指向链表的第一个节点,称为头指针。如果链表为空,头指针指向NULL。
- 尾节点:链表的最后一个节点指向NULL,这标志着链表的结束。
1.3链表与数组的比较
- 存储分配:数组在内存中占用连续空间,而链表由一系列非连续的节点组成。
- 大小灵活性:数组的大小在定义时固定,而链表的大小可以动态变化。
- 内存利用:链表可以更有效地管理内存,因为它只需要根据实际需要分配内存。
- 插入和删除效率:在链表中插入或删除节点通常更快,因为不需要移动其他元素(除非是数组实现的链表)。
2.链表的分类
按照单双向性、是否循环、以及是否带头节点,链表可以被分为以下八种主要类型:
-
单向不循环不带头链表
- 特点:最基本的链表形式,每个节点只有一个指向下一个节点的指针,尾节点指向NULL,不含额外的头节点。
- 用途:简单的数据存储和遍历操作。
-
单向不循环带头链表
- 特点:类似于基本的单向链表,但增加了一个不存储实际数据的头节点,头节点的指针指向第一个实际数据节点。
- 用途:简化某些链表操作,特别是插入和删除操作。
-
单向循环不带头链表
- 特点:单向链表的尾节点指向链表的第一个节点,形成一个闭环。
- 用途:适用于需要循环访问数据的场景。
-
单向循环带头链表
- 特点:单向循环链表,但有一个额外的头节点,头节点的指针指向第一个实际数据节点。
- 用途:循环链表操作的简化,尤其在处理循环链表的起始和终止条件时。
-
双向不循环不带头链表
- 特点:每个节点有两个指针,分别指向前一个和后一个节点,尾节点的后向指针指向NULL,没有头节点。
- 用途:方便的双向遍历,易于节点的前后插入和删除。
-
双向不循环带头链表
- 特点:双向链表加上一个头节点,头节点的前向指针通常指向NULL,后向指针指向第一个实际节点。
- 用途:简化插入、删除操作,尤其是在链表头部的操作。
-
双向循环不带头链表
- 特点:双向链表中的尾节点指向第一个节点,第一个节点的前向指针指向尾节点,形成一个双向闭环,不含头节点。
- 用途:复杂的双向循环遍历,常用于需要频繁正反向操作的场景。
-
双向循环带头链表
- 特点:在双向循环链表的基础上增加了头节点,头节点的前向指针指向尾节点,后向指针指向第一个实际节点。
- 用途:在需要循环遍历的同时,简化链表头部和尾部的操作。
在深入探讨链表的不同分类后,我们将先集中讨论单链表的实现与操作。单链表,作为链表家族中最简单的成员,提供了对链表基本概念的清晰理解。我们将详细介绍单链表(单向不带头不循环链表)的实现方法和各种操作函数。
3.单链表(单向不带头不循环链表)
单链表是一种基础的数据结构,由一系列节点(Node)组成。每个节点包含一个数据域和一个指向下一个节点的指针域。
3.1单链表的实现
我们先来看一下单向不带头不循环链表的具体实现,包括3个文件:头文件SList.h、源文件SList.c和test.c.
//SList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode {
SLTDataType data;
struct SListNode* next;
}SLTNode;
//打印
void SLTPrint(SLTNode* phead);
//获取新节点
SLTNode* BuyNewNode(SLTDataType x);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置之后的节点
void SLTEraseAfter(SLTNode* pos);
//删除pos位置的节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在pos位置之前插入x
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//销毁
void SLTDestroy(SLTNode** pphead);
//SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
//打印
void SLTPrint(SLTNode* phead)
{
//assert(phead);
SLTNode* pcur = phead;
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
//获取新节点
SLTNode* BuyNewNode(SLTDataType x)
{
SLTNode* pnewnode = (SLTNode*)malloc(sizeof(SLTNode));
if (pnewnode == NULL)
{
assert(0);
return NULL;
}
pnewnode->data = x;
pnewnode->next = NULL;
return pnewnode;
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* pnewnode = BuyNewNode(x);
if (*pphead == NULL)
{
*pphead = pnewnode;
}
else
{
SLTNode* pcur = *pphead;
while (pcur->next != NULL)
{
pcur = pcur->next;
}
pcur->next = pnewnode;
}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* pnewnode = BuyNewNode(x);
if (*pphead == NULL)
{
*pphead = pnewnode;
}
else
{
pnewnode->next = *pphead;
*pphead = pnewnode;
}
}
//尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
SLTNode* pcur = *pphead;
//链表为空
if (*pphead == NULL)
{
return;
}
//链表只有一个节点
else if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//链表有多个节点
else
{
while (pcur->next->next != NULL)
{
pcur = pcur->next;
}
free(pcur->next);
pcur->next = NULL;
}
}
//头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
SLTNode* pcur = *pphead;
if (pcur == NULL)
{
return;
}
else
{
*pphead = pcur->next;
free(pcur);
}
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
assert(phead);
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
//没找到
return NULL;
}
//在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* pnewnode = BuyNewNode(x);
pnewnode->next = pos->next;
pos->next = pnewnode;
}
//删除pos位置之后的节点
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
SLTNode* pcur = pos->next;
//pos之后没有节点
if (pcur == NULL)
{
return;
}
//pos之后有节点
else
{
pos->next = pcur->next;
free(pcur);
}
}
//删除pos位置的节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(*pphead);
assert(pos);
if(pos==*pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* pcur = *pphead;
while (pcur->next != pos)
{
pcur = pcur->next;
}
pcur->next = pos->next;
free(pos);
}
}
//在pos位置之前插入x
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
assert(*pphead);//链表不为空
SLTNode* pnewnode = BuyNewNode(x);
//pos为头节点
if (*pphead == pos)
{
/* pnewnode->next = *pphead;
*pphead = pnewnode;*/
SLTPushFront(pphead, x);
}
//pos不为头结点
else
{
SLTNode* pcur = *pphead;
while (pcur->next != pos)
{
pcur = pcur->next;
}
pnewnode->next = pos;
pcur->next = pnewnode;
}
}
//销毁
void SLTDestroy(SLTNode** pphead)
{
assert(pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
*pphead = pcur->next;
free(pcur);
pcur = *pphead;
}
}
//test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void SListTest01()
{
printf("SListTest01()\n");
SLTNode* node1 = BuyNewNode(1);
SLTPushBack(&node1, 2);
SLTPushBack(&node1, 3);
SLTPushBack(&node1, 4);
SLTPushBack(&node1, 5);
SLTPrint(node1);
SLTPushFront(&node1, 0);
SLTPrint(node1);
SLTNode* ToFind = SLTFind(node1, 0);
if(ToFind)
{
printf("Find it!\n");
}
else
{
printf("Not Find!\n");
}
SLTInsertAfter(ToFind, 500);
SLTPrint(node1);
SLTInsertBefore(&node1, ToFind, 100);
SLTPrint(node1);
SLTErase(&node1, ToFind);
SLTPrint(node1);
}
void SListTest02()
{
printf("SListTest02()\n");
SLTNode* node1 = BuyNewNode(1);
SLTPushBack(&node1, 2);
SLTPushBack(&node1, 3);
SLTPushBack(&node1, 4);
SLTPushBack(&node1, 5);
SLTPrint(node1);
SLTPopBack(&node1);
SLTPrint(node1);
SLTPopFront(&node1);
SLTPrint(node1);
SLTNode* ToFind = SLTFind(node1, 3);
SLTEraseAfter(ToFind);
SLTPrint(node1);
SLTDestroy(&node1);
SLTPrint(node1);
}
int main()
{
SListTest01();
SListTest02();
return 0;
}
3.2单链表函数详解
在单链表的实现中,以下是关键的数据类型定义和各个函数的实现原理与作用:
3.2.1数据类型定义
-
typedef int SLTDataType;
- 定义
SLTDataType
作为链表节点存储的数据类型,这里设为整型(int
)。
- 定义
-
typedef struct SListNode { SLTDataType data; struct SListNode* next; } SLTNode;
- 定义单链表的节点结构
SLTNode
,包含数据(data
)和指向下一个节点的指针(next
)。
- 定义单链表的节点结构
3.3.2函数详解
-
打印链表(
SLTPrint
)- 参数:头节点指针
phead
。 - 功能:遍历链表,打印每个节点的数据值。
- 实现:使用循环遍历链表,直到遇到
NULL
结束。
- 参数:头节点指针
-
获取新节点(
BuyNewNode
)- 参数:节点数据
x
。 - 功能:创建并返回一个新的链表节点。
- 实现:分配内存,初始化数据和指针。
- 参数:节点数据
-
尾插(
SLTPushBack
)- 参数:头节点指针的指针
pphead
,节点数据x
。 - 功能:在链表尾部插入一个新节点。
- 实现:找到链表的最后一个节点,将其
next
指向新节点。
- 参数:头节点指针的指针
-
头插(
SLTPushFront
)- 参数:头节点指针的指针
pphead
,节点数据x
。 - 功能:在链表头部插入一个新节点。
- 实现:新节点的
next
指向原头节点,然后更新头节点。
- 参数:头节点指针的指针
-
尾删(
SLTPopBack
)- 参数:头节点指针的指针
pphead
。 - 功能:删除链表的最后一个节点。
- 实现:找到倒数第二个节点,将其
next
设置为NULL
。
- 参数:头节点指针的指针
-
头删(
SLTPopFront
)- 参数:头节点指针的指针
pphead
。 - 功能:删除链表的第一个节点。
- 实现:将头节点指针更新为第二个节点。
- 参数:头节点指针的指针
-
查找(
SLTFind
)- 参数:头节点指针
phead
,要查找的数据x
。 - 功能:查找链表中数据为
x
的节点。 - 实现:遍历链表,比较节点数据。
- 参数:头节点指针
-
指定位置后插入(
SLTInsertAfter
)- 参数:目标节点指针
pos
,节点数据x
。 - 功能:在指定节点之后插入新节点。
- 实现:新节点的
next
指向pos
的next
,然后pos
的next
指向新节点。
- 参数:目标节点指针
-
指定位置后删除(
SLTEraseAfter
)- 参数:目标节点指针
pos
。 - 功能:删除指定节点之后的节点。
- 实现:将
pos
的next
指向要删除节点的next
。
- 参数:目标节点指针
-
指定位置删除(
SLTErase
)- 参数:头节点指针的指针
pphead
,要删除的节点指针pos
。 - 功能:删除指定的节点。
- 实现:找到
pos
的前一个节点,更新其next
指针。
- 参数:头节点指针的指针
-
指定位置前插入(
SLTInsertBefore
)- 参数:头节点指针的指针
pphead
,目标节点指针pos
,节点数据x
。 - 功能:在指定节点之前插入新节点。
- 实现:遍历链表找到
pos
的前一个节点,执行插入操作。
- 参数:头节点指针的指针
-
销毁链表(
SLTDestroy
)- 参数:头节点指针的指针
pphead
。 - 功能:销毁整个链表,释放所有节点。
- 实现:遍历链表,释放每个节点的内存。
- 参数:头节点指针的指针
3.2.3test.c运行结果
继单链表之后,我们将转向更为复杂的双向链表。双向链表(双向带头循环链表)不仅在节点结构上比单链表复杂,其操作也更为多样。通过比较这两种链表类型,我们可以更好地理解链表作为一种数据结构的灵活性和多功能性。
4.双向链表(双向带头循环链表)
双向链表是一种常见的线性数据结构,与单链表不同,它每个节点有两个指针域,一个指向前一个节点,一个指向后一个节点,因此可以从前往后或从后往前遍历链表。本文将详细介绍双向带头循环链表的实现以及双向链表的各种常用操作函数。
4.1双向链表的实现
我们先来看一下双向带头循环链表的具体实现,包括3个文件:头文件List.h、源文件List.c和test.c.
//List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;
typedef struct ListNode {
LTDataType data;
struct ListNode* prev;
struct ListNode* next;
}LTNode;
void LTPrint(LTNode* phead);//打印
void LTInit(LTNode** pphead);//初始化(通过传参)
LTNode* LTInit2();//初始化(通过返回值)
void LTDestroy(LTNode** pphead);//销毁
LTNode* BuyLTNode(LTDataType x);//创建新节点
void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPopBack(LTNode* phead);//尾删
void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPopFront(LTNode* phead);//头删
LTNode* LTFind(LTNode* phead, LTDataType x);//查找
void LTInsertBefore(LTNode* pos, LTDataType x);//在pos位置之前插入x
void LTInsertAfter(LTNode* pos, LTDataType x);//在pos位置之后插入x
void LTRemove(LTNode* pos);//删除pos位置的节点
void LTCheckNode(LTNode* phead);//打印有效节点个数
//List.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//打印
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("head->");
while(cur != phead)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
//初始化(通过传参的方式)
void LTInit(LTNode** pphead)
{
*pphead = (LTNode*)malloc(sizeof(LTNode));
if(*pphead == NULL)
{
assert(0);
return;
}
(*pphead)->data = -1;
(*pphead)->next = *pphead;
(*pphead)->prev = *pphead;
}
//初始化(通过返回值的方式)
LTNode* LTInit2()
{
LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
if(phead == NULL)
{
assert(0);
return NULL;
}
phead->data = -1;
phead->next = phead;
phead->prev = phead;
return phead;
}
//销毁
void LTDestroy(LTNode** pphead)
{
LTNode* cur = (*pphead)->next;
while(cur != *pphead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(*pphead);
*pphead = NULL;
}
//创建新节点
LTNode* BuyLTNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if(newnode == NULL)
{
assert(0);
return NULL;
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* ptail = phead->prev;
LTNode* newnode = BuyLTNode(x);
newnode->next = phead;
newnode->prev = ptail;
ptail->next = newnode;
phead->prev = newnode;
}
//尾删
void LTPopBack(LTNode* phead)
{
assert(phead);
LTNode* ptail = phead->prev;
if(ptail == phead)
{
return;
}
LTNode* prev = ptail->prev;
prev->next = phead;
phead->prev = prev;
free(ptail);
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyLTNode(x);
LTNode* next = phead->next;
newnode->next = next;
newnode->prev = phead;
next->prev = newnode;
phead->next = newnode;
}
//头删
void LTPopFront(LTNode* phead)
{
assert(phead);
LTNode* next = phead->next;
if(next == phead)
{
return;
}
LTNode* nextnext = next->next;
phead->next = nextnext;
nextnext->prev = phead;
free(next);
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while(cur != phead)
{
if(cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//在pos位置之前插入x
void LTInsertBefore(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* newnode = BuyLTNode(x);
newnode->next = pos;
newnode->prev = prev;
prev->next = newnode;
pos->prev = newnode;
}
//在pos位置之后插入x
void LTInsertAfter(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* next = pos->next;
LTNode* newnode = BuyLTNode(x);
newnode->next = next;
newnode->prev = pos;
next->prev = newnode;
pos->next = newnode;
}
//删除pos位置的节点
void LTRemove(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
}
//打印有效节点个数
void LTCheckNode(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
int count = 0;
while(cur != phead)
{
count++;
cur = cur->next;
}
printf("有效节点个数为:%d\n", count);
}
//test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void test01()
{
printf("test01()\n");
LTNode* plist = NULL;
LTInit(&plist);
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
LTPopBack(plist);
LTPrint(plist);
}
void test02()
{
printf("test02()\n");
LTNode* plist = LTInit2();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTNode* toFind = LTFind(plist, 2);
if (toFind)
{
printf("找到了\n");
}
else
{
printf("没找到\n");
}
LTInsertAfter(toFind, 5);
LTInsertBefore(toFind, 6);
LTPrint(plist);
LTRemove(toFind);
LTPrint(plist);
LTCheckNode(plist);
}
int main()
{
test01();
test02();
return 0;
}
4.2双向链表函数详解
4.2.1数据类型定义
在双向链表的实现中,我们使用了以下数据类型的定义:
typedef int LTDataType;
typedef struct ListNode {
LTDataType data;
struct ListNode* prev;
struct ListNode* next;
} LTNode;
LTDataType
:链表节点存储的数据类型,这里使用整数作为示例。LTNode
:链表节点的结构体,包含数据域data
,前驱指针prev
和后继指针next
。这三个部分组成了链表节点的基本结构。
4.2.2 函数详解
以下是双向链表实现中的各个函数的详细介绍:
1. 初始化链表
void LTInit(LTNode** pphead);
- 参数:头节点指针的指针
pphead
。 - 功能:初始化链表,创建一个头节点,使其
next
和prev
指向自身,形成循环链表。这个函数用于链表的初始化操作。
2. 创建新节点
LTNode* BuyLTNode(LTDataType x);
- 参数:节点存储的数据
x
。 - 返回值:新节点的指针。
- 功能:创建一个新节点,为其分配内存并设置数据域为
x
,前驱和后继指针为空。这个函数用于创建待插入的新节点。
3. 插入节点到尾部
void LTPushBack(LTNode* phead, LTDataType x);
- 参数:头节点指针
phead
,要插入的数据x
。 - 功能:在双向链表的尾部插入一个新节点,更新尾节点的指针。这个函数用于在链表尾部添加新元素。
4. 删除尾部节点
void LTPopBack(LTNode* phead);
- 参数:头节点指针
phead
。 - 功能:删除双向链表的尾部节点,更新尾节点的指针,并释放内存。这个函数用于删除链表尾部的元素。
5. 插入节点到头部
void LTPushFront(LTNode* phead, LTDataType x);
- 参数:头节点指针
phead
,要插入的数据x
。 - 功能:在双向链表的头部插入一个新节点,更新头节点的指针。这个函数用于在链表头部添加新元素。
6. 删除头部节点
void LTPopFront(LTNode* phead);
- 参数:头节点指针
phead
。 - 功能:删除双向链表的头部节点,更新头节点的指针,并释放内存。这个函数用于删除链表头部的元素。
7. 查找节点
LTNode* LTFind(LTNode* phead, LTDataType x);
- 参数:头节点指针
phead
,要查找的数据x
。 - 返回值:找到的节点的指针,如果未找到则返回
NULL
。 - 功能:在双向链表中查找存储特定数据
x
的节点。这个函数用于查找链表中的元素。
8. 在指定节点之前插入新节点
void LTInsertBefore(LTNode* pos, LTDataType x);
- 参数:要插入的位置节点
pos
,要插入的数据x
。 - 功能:在双向链表中的指定节点
pos
之前插入一个新节点,更新前驱和后继节点的指针。这个函数用于在指定位置之前
9. 在指定节点之后插入新节点
void LTInsertAfter(LTNode* pos, LTDataType x);
- 参数:要插入的位置节点
pos
,要插入的数据x
。 - 功能:在双向链表中的指定节点
pos
之后插入一个新节点,更新前驱和后继节点的指针。这个函数用于在指定位置之后插入新元素。
10. 删除指定节点
void LTRemove(LTNode* pos);
- 参数:要删除的节点
pos
。 - 功能:从双向链表中删除指定节点
pos
,更新前驱和后继节点的指针,并释放内存。这个函数用于删除链表中的特定元素。
4.2.3test.c运行结果
5.结语
在本篇博客中,我们详细介绍了C语言中的链表数据结构,包括单向链表和双向链表。我们从链表的基本概念和结构开始,然后分别讨论了不同类型的链表,包括单向不带头不循环链表和双向带头循环链表。通过学习链表的实现和操作,我们可以更好地理解数据结构和算法的基本原理,为编程和问题解决提供强大的工具。希望本篇博客能够帮助你更深入地理解链表,并在编程中应用它们。