数据结构之细说链表
1.1顺序表的问题以及思考
经过上一篇顺序表的学习，我们知道顺序表还是有很多缺点
顺序表的缺点：
1.中间/头部的插入删除，实际复杂度为O(N)
2.增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗
3.扩容一般是呈两倍增长，势必会有一定的空间浪费。
例如当前空间的容量是100，满了之后扩容到200，我们在继续插入了5个数据，后面就没有继续插入了，这样就会浪费95个空间。
如何解决这些问题了？下面我们给出链表的构成，看看链表是如何解决这些问题的
1.2链表的概念以及结构
概念：链表是一种物理储存结构上非连续，非顺序的存储结构，数据元素的逻辑结构是通过链表中的指针连接次序实现的。像一个小火车一样一节连接这一节
链式结构在逻辑上是连续的，但是在物理结构上不一定连续，它们的空间都是在堆上动态申请的，两次申请空间可能连续，则也可能不连续
1.3链表的分类
实际中的链表结构非常多样，以下情况结合起来就有8种链表结构：
1.单向或者双向
2.带头或者不带头
3.循环或者非循环
看着有这么多链表组合起来其实更多
将它们组合起来一共有8种结构
虽然有这么多链表的结构，但是我们实际中最常用的还是两种结构：
我们只要将这两种结构熟练掌握了其他的结构就差不多了
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
1.4单向链表（于顺序表一样：实现增删查改）
需要实现的功能和要用到的头文件
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct SListNode
{
SLTDataType data;
struct SListNode * next;
}SLTNode;
typedef int SLTDataType;
//打印数据
void SLTPrint(SLTNode* phead);
//查找数据
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//增加节点
SLTNode* BuySLTNode(SLTDataType x);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//任意位置插入节点
void SLTinsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//任意位置删除节点
void SLTerase(SLTNode** phead, SLTDataType x);
//pos位置之后删除
void SLTPoppushAfter(SLTNode* pos);
//pos位置之后插入
void SLTPopFrontAfter(SLTNode* pos, SLTDataType x);
//删除链表
void SLTDestroy(SLTNode** pphead);->1.打印数据
//打印数据
void SLTPrint(SLTNode* phead)
{
SLTNode* newnode = phead;
while (newnode != NULL)
{
printf("%d -> ", newnode->data);
newnode = newnode->next;
}
printf("NULL");
printf("\n");
}打印数据是不需要用assert来检查的，因为就算没有数据也可以打印，顺序表也是这样，如果phead传进来的是一个空指针被assert断言就会强制终止程序，就不会打印了，因为打印数据只需要使用结构体就行了，不需要改变结构体指针
->2.查找数据
//查找数据
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
assert(phead);
SLTNode* cur = phead;
while (cur->next != NULL)
{
cur = cur->next;
if (cur->data == x)
{
return cur;
}
}
return NULL;
}查找数据需要一个有效的地址，如果你传进来的空指针，那你找它有什么意义了cur->next还会对空指针越界访问，所以这里需要assert断言一下
->3.增加节点
//增加节点
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (NULL == newnode)
{
perror("BuySLTNode::malloc");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}在堆上申请空间，创建一个新节点，然后返回指针
->4.尾插
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
if (NULL == *pphead)
{
*pphead = newnode;
}
else
{
//找尾
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}因为这里形参为一级指针的地址是绝对不可能为空指针的所以这里需要断言一下pphead是否为空先判断该链表是否有节点，如果没有就将需要尾插的节点直接给pphead，就行了。如果该链表本来就有地址那就先找尾，然后把节点连接到最后一共节点后面
->5.尾删
//尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
尾删，如果链表没有节点的话肯定是删不了的，所以*pphead需要断言一下，然后phead也断言一下。这里while循环的条件判断必须是tail->next->next，因为我们需要释放最后一个节点的地址，所以需要利用它前面一共节点来释放它，然后将tail->next置空，如果我们直接找最后一个地址然后将它释放前面一个节点就会指向被释放的地址变成一个野指针，因为我们已经找不到前面一个节点的位置了
->6.头插
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}头插就比较简单了，将该节点连接在第一个节点和第二个节点之间就可以了，但是我们需要先连接第二个和新节点，如果先连接第一个节点和新节点就会找不到第二个节点的地址。也可以用一个指针变量先存放第二个节点的位置。这里pphead也需要断言
->7.头删
//头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead); //暴力检查
assert(*pphead);
SLTNode* first = *pphead;
*pphead = first->next;
free(first);
first = NULL;
}头删需要断言pphead还有*pphead删节点，链表不能为空吧，为空你还需要删除就没有意义了
->8.查找数据
//查找数据
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
assert(phead);
SLTNode* cur = phead;
while (cur->next != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}断言phead，这个if条件判断语句应该放到cur->next的上面，因为可能第一个节点就是我们需要找到的x
->9.pos位置之前插入节点
//任意插入节点
void SLTinsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pos);
assert(pphead);
if (*pphead == pos)
{
SLTPushFront(&pos, x);
}
SLTNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
SLTNode* newnode = BuySLTNode(x);
newnode->next = cur->next;
cur->next = newnode;
}断言phead和pos，断言pos是因为如果pos为空的话，那该在那个位置插入都不清楚了
->10.pos位置之前删除节点
//任意位置删除节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(*pphead);
assert(pos);
assert(pphead);
if (*pphead == pos)
{
SLTPopFront(&pos);
}
else
{
SLTNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = pos->next;
free(pos);
}
}两个个要注意的地方：1.当*pphead 等于 pos时直接头删就可以了 2.需要断言*pphead，因为*pphead为空，没有可删除的节点
->11.pos位置之后插入节点
//pos位置之后插入
void SLTPopFrontAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next->next;
pos->next = newnode;
}->12.pos位置之后删除节点
//pos位置之后删除
void SLTPoppushAfter(SLTNode* pos)
{
assert(pos);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}->13.清空所有节点
//删除所有节点
void SLTDestroy(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* del = cur->next;
free(cur);
cur = del;
}
*pphead = NULL;
}1.5单向链表的实现
SList.h
#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* SLTFind(SLTNode* phead, SLTDataType x);
//增加链表
SLTNode* BuySLTNode(SLTDataType x);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//插入
void SLTinsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除数据
void SLTerase(SLTNode** phead, SLTDataType x);
//pos位置之后删除
void SLTPoppushAfter(SLTNode* pos);
//pos位置之后插入
void SLTPopFrontAfter(SLTNode* pos, SLTDataType x);
//清空所有节点
void SLTDestroy(SLTNode** pphead);
SList.c
#include "SList.h"
//打印链表
void SLTPrint(SLTNode* phead)
{
SLTNode* newnode = phead;
while (newnode != NULL)
{
printf("%d -> ", newnode->data);
newnode = newnode->next;
}
printf("NULL");
printf("\n");
}
//增加链表
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (NULL == newnode)
{
perror("BuySLTNode::malloc");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//找尾
SLTNode* newnode = BuySLTNode(x);
if (NULL == *pphead)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
//SLTinsert(pphead, newnode, x);
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
//头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead); //暴力检查
assert(*pphead);
SLTNode* first = *pphead;
*pphead = first->next;
free(first);
first = NULL;
}
//查找节点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
assert(phead);
SLTNode* cur = phead;
while (cur->next != NULL)
{
cur = cur->next;
if (cur->data == x)
{
return cur;
}
}
return NULL;
}
//pos位置之前插入节点
void SLTinsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pos);
assert(pphead);
if (*pphead == pos)
{
SLTPushFront(&pos, x);
}
SLTNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
SLTNode* newnode = BuySLTNode(x);
newnode->next = cur->next;
cur->next = newnode;
}
//pos位置之前删除节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(*pphead);
assert(pos);
assert(pphead);
if (*pphead == pos)
{
SLTPopFront(&pos);
}
else
{
SLTNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = pos->next;
free(pos);
}
}
//pos位置之后删除
void SLTPoppushAfter(SLTNode* pos)
{
assert(pos);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
//pos位置之后插入
void SLTPopFrontAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next->next;
pos->next = newnode;
}
//清空所有节点
void SLTDestroy(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* del = cur->next;
free(cur);
cur = del;
}
*pphead = NULL;
}test.c
#include "SList.h"
int main()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
SLTNode* pos = SLTFind(plist, 3);
SLTinsert(&plist, pos, 8);
SLTPrint(plist);
pos = SLTFind(plist, 4);
SLTErase(&plist, pos);
pos = NULL;
SLTPrint(plist);
SLTDestroy(&plist);
SLTPrint(plist);
/*free(plist);
plist = NULL;*/
return 0;
}
测试结果：
1.6带头双向循环链表
需要实现的功能和要用到的头文件
因为是带头双向循环链表所有得有两个接点一个prev，一个next
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* prev;
LTDataType data;
struct ListNode* next;
}LTNode;
//链表初始化
LTNode* LTInIt();
//清空所有节点
void LTDestroy(LTNode* phead);
//判断链表中是否有其他节点(除了带哨兵位的头节点)
bool LTEmpty(LTNode* phead);
//增加一个节点
LTNode* BuyListNode(LTDataType x);
//打印链表
void Print(LTNode* phead);
//尾插
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);
//pos位置前插入节点
void LTInsert(LTNode* pos, LTDataType x);
//pos位置删除节点
void LTErase(LTNode* pos);->1.链表初始化
//链表初始化
LTNode* LTInIt()
{
LTNode* phead = BuyListNode(-1);
phead->prev = phead;
phead->next = phead;
return phead;
}
因为这是带头双向循环链表，一开始我们得让哨兵位的头节点自己指向自己，这样就体现了带头双向循环的特性
如图：
->2.清空所有节点
//清空所有节点
//因为是一级指针的缘故所以在外面还得手动置空phead
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}这里需要注意一点因为我们用的是一级指针所以出去之后我们还得手动指置空哨兵位的头节点（phead），这里有人就会问为什么不使用二级指针，因为大部分形参都是一级指针，我们就没必要去破坏整个代码的美观，非要在这里使用二级指针，除非必须要使用二级指针不可。这里断言一下phead，因为是带头的链表，所以传的头指针肯定不会为空，链表只要带头就不会出现空指针的情况
->3.判断链表中是否有其他节点(除了带哨兵位的头节点)
//判断链表中是否有其他节点(除了带哨兵位的头节点)
bool LTEmpty(LTNode* phead)
{
assert(phead);
/*if (phead->next == phead)
{
return ture;
}
return false;*/
return phead->next == phead;
}因为在删除节点的时候，我们需要判断该链表中是否有节点可以删除，所以在这里我们单独做一个模块来判断。
->4.增加一个节点
//增加节点
LTNode* BuyListNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (NULL == newnode)
{
perror("BuyListNode::malloc");
exit(-1);
}
newnode->prev = NULL;
newnode->data = x;
newnode->next = NULL;
return newnode;
}->5.打印链表
//打印链表
void Print(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur->next != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
注意：这里需要将phead->next赋给cur，不然打印会将哨兵位中的值打印出来
->6.尾插
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
phead->prev = newnode;
newnode->next = phead;
}->7.尾删
//尾删
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* tail = phead->prev;
phead->prev = tail->prev;
tail->prev->next = phead;
}
->8.头插
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* frist = phead->next; //将第一个元素的地址保存下来就不用考虑顺序了
newnode->next = frist;
frist->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
->9.头删
//头删
void PopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* frist = phead->next;
phead->next = frist->next;
frist->next->prev = phead;
free(frist);
frist = NULL;
}->10.查找节点地址
//查找节点地址
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead;
while (cur->next != phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
->11.pos位置前插入节点
//pos位置前插入节点
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = BuyListNode(x);
LTNode* posprev = pos->prev;
posprev->next = newnode;
newnode->prev = posprev;
newnode->next = pos;
pos->prev = newnode;
}->12.pos位置删除节点
//pos位置删除节点
void LTErase(LTNode* pos)
{
LTNode* posprev = pos->prev;
LTNode* posnext = pos->next;
posprev->next = posnext;
posnext->prev = posprev;
free(pos);
pos = NULL;
}1.7 带头双向循环链表的实现
List.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* prev;
LTDataType data;
struct ListNode* next;
}LTNode;
//链表初始化
LTNode* LTInIt();
//清空链表
void LTDestroy(LTNode* phead);
//判断链表中是否有其他节点(除了带哨兵位的头节点)
bool LTEmpty(LTNode* phead);
//增加一个节点
LTNode* BuyListNode(LTDataType x);
//打印链表
void Print(LTNode* phead);
//尾插
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 LTInsert(LTNode* pos, LTDataType x);
//任意位置删除节点
void LTErase(LTNode* pos);List.c
#include "List.h"
//增加节点
LTNode* BuyListNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (NULL == newnode)
{
perror("BuyListNode::malloc");
exit(-1);
}
newnode->prev = NULL;
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//链表初始化
LTNode* LTInIt()
{
LTNode* phead = BuyListNode(-1);
phead->prev = phead;
phead->next = phead;
return phead;
}
//打印链表
void Print(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur->next != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
//判断链表中是否有其他节点(除了带哨兵位的头节点)
bool LTEmpty(LTNode* phead)
{
assert(phead);
/*if (phead->next == phead)
{
return ture;
}
return false;*/
return phead->next == phead;
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
phead->prev = newnode;
newnode->next = phead;
}
//尾删
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* tail = phead->prev;
phead->prev = tail->prev;
tail->prev->next = phead;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* frist = phead->next; //将第一个元素的地址保存下来就不用考虑顺序了
newnode->next = frist;
frist->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
//头删
void PopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* frist = phead->next;
phead->next = frist->next;
frist->next->prev = phead;
free(frist);
frist = NULL;
}
//清空所有节点
//因为是一级指针的缘故所以在外面还得手动置空phead
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
//查找节点地址
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead;
while (cur->next != phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
//pos位置前插入节点
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = BuyListNode(x);
LTNode* posprev = pos->prev;
posprev->next = newnode;
newnode->prev = posprev;
newnode->next = pos;
pos->prev = newnode;
}
//pos位置删除节点
void LTErase(LTNode* pos)
{
LTNode* posprev = pos->prev;
LTNode* posnext = pos->next;
posprev->next = posnext;
posnext->prev = posprev;
free(pos);
pos = NULL;
}test.c
#include "List.h"
int main()
{
LTNode* plist = LTInIt();
//尾插
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPushBack(plist, 5);
Print(plist);
//头插
LTPushFront(plist, 6);
Print(plist);
//4前面插入
LTNode* pos = LTFind(plist, 4);
LTInsert(pos, 9);
Print(plist);
//删除2
pos = LTFind(plist, 2);
LTErase(pos);
Print(plist);
//尾删
LTPopBack(plist);
Print(plist);
return 0;
}测试结果：
原文地址：https://blog.csdn.net/m0_73634434/article/details/140360001
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！