嘿嘿,家人们,今天咱们来详细剖析数据结构中的链表,好啦,废话不多讲,开干!
1:链表1.1:链表的概念以及结构 链表是一种 物理存储结构上非连续 、 非顺序的存储结构，数据元素的 逻辑顺序 是通过链表
中的 指针链接 次序实现的.
链表的结构跟火车车厢相似, 淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉或者加上,不会影响其他⻋厢，每节⻋厢都是独立存在的. ⻋厢是独立存在的,且每节⻋厢都有车门.可以想象⼀下介样滴的场景，假设每节⻋厢的车门都是锁上的状态,需要不同的钥匙才能解锁,每次只能携带⼀把钥匙的情况下如何从⻋头走到车尾？
最简单的做法：每节车厢里都放一把下⼀节车厢的钥匙.
从上图我们可以看到,链式结构在逻辑上是连续的,但是在物理上不一定连续.现实中的节点一般都是从堆上申请出来的.从堆上申请的空间,是按照一定的策略来进行分配的,两次申请的空间可能连续,也可能不连续.与顺序表不同的是,链表里的每节"车厢"都是独立申请下来的空间,我们称之为"结点/结点",结点有以下两个组成部分: 图中指针变量 plist保存的是第⼀个节点的地址,我们称plist此时"指向"第⼀个节点,如果我们想要plist“指向”第二个节点时，只需要修改plist保存的内容为0x0012FFB0.
那么为什么还要指针变量来保存下一个节点的位置呢?
链表中每个节点都是 独立申请 的( 即需要插⼊数据时才去申请⼀块节点的空间 ),我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点.
结合前⾯学到的结构体知识,我们可以给出每个节点对应的结构体代码:
假设当前保存的节点为整型.
代码语言：javascript复制#include
struct ListNode
{
int Value;
struct ListNode* Next;
}; 当我们想要保存⼀个整型数据时,实际是向操作系统申请了⼀块内存,这个内存不仅要保存整型数据,也需要保存下⼀个节点的地址(当下⼀个节点为空时保存的地址为空).
当我们想要从第⼀个节点⾛到最后⼀个节点时,只需要在前⼀个节点拿上下⼀个节点的地址下⼀个节点的钥匙)就可以了.
假设在32位系统上,结点中值域为int类型, 则一个节点的大小为8个字节,则也有可能下面的链表.
1.2:链表的分类 实际中的链表的结构十分多样,组合起来有8种链表结构:
1.单向或双向
2.带头或不带头
3.循环或非循环
虽然链表的结构有如此之多,但实践中最常用的还是两种结构:无头单向非循环链表与带头双向循环链表.
无头单向非循环链表:结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等.带头双向循环链表:结构最复杂,一般用在单独存储数据.实际中使用的链表数据结构,都是带头双向循环链表.2:无头单向非循环链表的实现2.1:Single_Linked_List.h代码语言：javascript复制#pragma once
#include
#include
#include
//结构声明与函数声明
typedef int LKDataType;
typedef struct SingleList
{
//存值
LKDataType data;
//指向下一个节点的地址
struct SingleList* next;
}Slist;
//打印链表
void SlistPrint(Slist* phead);
//创建节点
Slist* SlistCreateNode(LKDataType value);
//尾插数据
void SlistPushback(Slist** pphead, LKDataType value);
//头插数据
void SlistPushfront(Slist** pphead, LKDataType value);
//尾删数据
void SlistPopback(Slist** pphead);
//头删数据
void SlistPopfront(Slist** pphead);
//查找节点
Slist* SlistFindNode(Slist* position, LKDataType value);
//在position位置的前面添加数据
void SlistInsert(Slist** pphead, Slist* position, LKDataType value);
//删除
// position位置的删除数据
void SlistDelete(Slist** pphead, Slist* position);
//postion后面位置的添加数据
void SlistInsertAfter(Slist* position, LKDataType value);
//position后面位置的删除数据
void SlistDeleteAfter(Slist* position);
//销毁链表
void SlistDestory(Slist** pphead);2.2:Single_Linked_List.c2.2.1:打印链表与创建链表节点代码语言：javascript复制#include "Single_Linked_List.h"
//打印链表
void SlistPrint(Slist* phead)
{
assert(phead);
Slist* Current = phead;
while(Current)
{
printf("%d->", Current->data);
Current = Current->next;
}
printf("\n");
}
//创建节点
Slist* SlistCreateNode(LKDataType value)
{
Slist* NewNode = (Slist *)malloc(sizeof(Slist));
if(NewNode == NULL)
{
perror("malloc fail\n");
exit(-1);
}
NewNode->data = value;
NewNode->next = NULL;
return NewNode;
}2.2.2:头插与尾插节点代码语言：javascript复制//头插数据
void SlistPushfront(Slist** pphead, LKDataType value)
{
//确保plist的地址为有效地址
assert(pphead);
Slist* NewNode = SlistCreateNode(value);
//让创建的节点存储最初的头结点的地址;
NewNode->next = *pphead;
//让头节点存储新头结点的地址
*pphead = NewNode;
}
//尾插数据
void SlistPushback(Slist** pphead, LKDataType value)
{
assert(pphead);
Slist* NewNode = SlistCreateNode(value);
//链表为空即phead的地址为NULL
//这里改变的是结构体的指针,一开始plist指向的地址是NULL
if (*pphead == NULL)
{
*pphead = NewNode;
}
else
{
//先找到最后一个节点
Slist* Current = *pphead;
while(Current->next != NULL)
{
//这里改变的是结构体的成员
Current = Current->next;
}
//然后在最后一个节点里存放新节点的地址
Current->next = NewNode;
}
}2.2.3:头删节点与尾删节点
代码语言：javascript复制//头删数据
void SlistPopfront(Slist** pphead)
{
assert(pphead);
//空节点不能删
assert(*pphead);
//记录头节点
Slist* temp = *pphead;
//plist指向head的next
*pphead = (*pphead)->next;
//释放最初的头结点
free(temp);
}
//尾删数据
void SlistPopback(Slist** pphead)
{
assert(pphead);
//空节点不能删
assert(*pphead);
//单独处理一个节点的情况
if((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//找尾节点的前一个节点
else
{
//记录头节点
Slist* tail = *pphead;
Slist* previous = NULL;
while (tail->next)
{
//记录尾节点的前一个节点
previous = tail;
//这里改变的是结构体的成员
tail = tail->next;
}
free(tail);
//找尾之后直接释放(tail可置可不置)
tail = NULL;
//将上一个节点的所存储的地址置为空
previous->next = NULL;
}
}2.2.4:查找节点与在position位置的前面插入节点代码语言：javascript复制//查找节点
Slist* SlistFindNode(Slist* phead, LKDataType value)
{
Slist* current = phead;
while (current != NULL)
{
//根据值来进行查找
if (current->data == value)
{
return current;
}
else
{
current = current->next;
}
}
return NULL;
}
//在position位置的前面添加数据
void SlistInsert(Slist** pphead, Slist * position, LKDataType value)
{
assert(pphead);
//防止一个为空与一个不为空的情况(链表是空的,但是position这一节点不存在)
assert((!position && !(*pphead)) || (position && *pphead));
Slist* NewNode = SlistCreateNode(value);
if (NewNode == NULL)
{
perror("CreateNode Fail");
exit(-1);
}
//等于头结点,则是头插
if (position == *pphead)
{
SlistPushfront(pphead, value);
}
else
{
Slist* Previous = *pphead;
//找到position位置的前一个节点
while(Previous->next != position)
{
Previous = Previous->next;
}
//新节点的next指针指向position位置
NewNode->next = position;
//position位置的前一个节点的next指针指向NewNode
Previous->next = NewNode;
}
} 有的uu会比较好奇,为什么链表的查找不是像顺序表那样子返回下标呢,
本质原因在于:链表是一种物理存储结构上非连续、非顺序的存储结构,而顺序表是物理存储结构上连续的存储结构.
2.2.5:删除position位置的节点与删除position位置后面的节点以及在position位置后面添加节点代码语言：javascript复制// position位置的删除数据
void SlistDelete(Slist** pphead, Slist* position)
{
//防止一个为空与一个不为空的情况(链表是空的,但是position这一节点不存在)
assert((!position && !(*pphead)) || (position && *pphead));
if (*pphead == position)
{
*pphead = position->next;
free(position);
position = NULL;
}
else
{
Slist* Previous = *pphead;
//找到position位置的前一个节点
while(Previous->next != position)
{
Previous = Previous->next;
}
Previous->next = position->next;
free(position);
}
}
//postion后面位置的添加数据
void SlistInsertAfter(Slist* position, LKDataType value)
{
assert(position);
Slist* NewNode = SlistCreateNode(value);
if(NULL == NewNode)
{
perror("malloc fail");
exit(-1);
}
NewNode->next = position->next;
position->next = NewNode;
}
//position后面位置的删除数据
void SlistDeleteAfter(Slist* position)
{
assert(position);
Slist* temp = position->next;
position->next = temp->next;
free(temp);
}2.2.6:链表的销毁 代码语言：javascript复制//销毁链表
void SlistDestory(Slist** pphead)
{
assert(pphead);
Slist* Current = *pphead;
while(Current)
{
Slist* temp = Current->next;
free(Current);
Current = temp;
}
*pphead = NULL;
}2.3:Test.c2.3.1:测试打印链表与创建链表节点代码语言：javascript复制#include "Single_Linked_List.h"
void TestCreateAndPrint(Slist ** pphead)
{
*pphead = SlistCreateNode(1);
(*pphead)->next = SlistCreateNode(2);
(*pphead)->next->next = SlistCreateNode(3);
(*pphead)->next->next->next = SlistCreateNode(4);
(*pphead)->next->next->next->next = SlistCreateNode(5);
SlistPrint(*pphead);
}
int main()
{
Slist* phead = NULL;
TestCreateAndPrint(&phead);
return 0;
}2.3.2:测试头插与尾插代码语言：javascript复制#include "Single_Linked_List.h"
void TestPushFrontAndPushBack(Slist** pphead)
{
SlistPushfront(pphead, 6);
SlistPushfront(pphead, 5);
SlistPushfront(pphead, 4);
SlistPushfront(pphead, 3);
SlistPrint(*pphead);
SlistPushback(pphead, 7);
SlistPushback(pphead, 8);
SlistPushback(pphead, 9);
SlistPrint(*pphead);
}
int main()
{
Slist* phead = NULL;
TestPushFrontAndPushBack(&phead);
return 0;
}2.3.3:测试头删与尾删代码语言：javascript复制#include "Single_Linked_List.h"
void TestPopFrontAndPopBack(Slist** pphead)
{
SlistPushfront(pphead, 6);
SlistPushfront(pphead, 5);
SlistPushfront(pphead, 4);
SlistPushfront(pphead, 3);
SlistPushback(pphead, 7);
SlistPushback(pphead, 8);
SlistPushback(pphead, 9);
SlistPrint(*pphead);
//头删
SlistPopfront(pphead);
SlistPopfront(pphead);
SlistPopfront(pphead);
SlistPopfront(pphead);
SlistPrint(*pphead);
SlistPopback(pphead);
SlistPopback(pphead);
SlistPrint(*pphead);
}
int main()
{
Slist* phead = NULL;
TestPopFrontAndPopBack(&phead);
return 0;
}2.3.4:测试查找与在position位置的前面添加节点 代码语言：javascript复制#include "Single_Linked_List.h"
void TestFindAndInsert(Slist** pphead)
{
SlistPushfront(pphead, 6);
SlistPushfront(pphead, 5);
SlistPushfront(pphead, 4);
SlistPushfront(pphead, 3);
SlistPushback(pphead, 7);
SlistPushback(pphead, 8);
SlistPushback(pphead, 9);
SlistPrint(*pphead);
Slist* postion = SlistFindNode(*pphead, 5);
SlistInsert(pphead,postion,1);
postion = SlistFindNode(*pphead, 3);
SlistInsert(pphead, postion, 0);
SlistPrint(*pphead);
}
int main()
{
Slist* phead = NULL;
TestInsertAndDelete(&phead);
return 0;
}2.3.6:测试删除position位置的节点与删除position位置后面的节点以及在position位置后面添加节点代码语言：javascript复制#include "single_linked_list.h"
void TestDeleteAndInsertAfter(Slist ** pphead)
{
SlistPushfront(pphead, 6);
SlistPushfront(pphead, 5);
SlistPushfront(pphead, 4);
SlistPushfront(pphead, 3);
SlistPushback(pphead, 7);
SlistPushback(pphead, 8);
SlistPushback(pphead, 9);
SlistPrint(*pphead);
Slist* position = SlistFindNode(*pphead, 5);
//删除5这个节点
SlistDelete(pphead, position);
position = SlistFindNode(*pphead, 3);
//删除头节点
SlistDelete(pphead, position);
SlistPrint(*pphead);
printf("-------------------------\n");
position = SlistFindNode(*pphead, 4);
SlistInsertAfter(position, 10);
SlistPrint(*pphead);
printf("-------------------------\n");
SlistDeleteAfter(position);
SlistDeleteAfter(position);
SlistDeleteAfter(position);
SlistDeleteAfter(position);
SlistDeleteAfter(position);
SlistPrint(*pphead);
}
int main()
{
Slist* phead = NULL;
TestDeleteAndInsertAfter(&phead);
return 0;
}2.3.7:测试链表的销毁代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS
#include "single_linked_list.h"
//测试头插和尾插
void test1(Slist** list)
{
printf("头插与尾插:>");
SlistPushfront(&(*list), 0);
SlistPushfront(&(*list), 1);
SlistPushfront(&(*list), 2);
SlistPushfront(&(*list), 3);
SlistPushfront(&(*list), 4);
SlistPushback(&(*list), 5);
SlistPushback(&(*list), 6);
SlistPushback(&(*list), 7);
SlistPrint(*list);
}
int main()
{
Slist* list = NULL;
test1(&list);
SlistDestory(&list);
return 0;
}3:无头单向非循环链表的总代码3.1:Single_Linked_List.h代码语言：javascript复制#pragma once
#include
#include
#include
//结构声明与函数声明
typedef int LKDataType;
typedef struct SingleList
{
//存值
LKDataType data;
//指向下一个节点的地址
struct SingleList* next;
}Slist;
//打印链表
void SlistPrint(Slist* phead);
//创建节点
Slist* SlistCreateNode(LKDataType value);
//尾插数据
void SlistPushback(Slist** pphead, LKDataType value);
//头插数据
void SlistPushfront(Slist** pphead, LKDataType value);
//尾删数据
void SlistPopback(Slist** pphead);
//头删数据
void SlistPopfront(Slist** pphead);
//查找节点
Slist* SlistFindNode(Slist* phead, LKDataType value);
//在position位置的前面添加数据
void SlistInsert(Slist** pphead, Slist* position, LKDataType value);
//删除
// position位置的删除数据
void SlistDelete(Slist** pphead, Slist* position);
//postion后面位置的添加数据
void SlistInsertAfter(Slist* position, LKDataType value);
//position后面位置的删除数据
void SlistDeleteAfter(Slist* position);
//销毁链表
void SlistDestory(Slist** pphead);3.2:Single_Linked_List.c代码语言：javascript复制#include "Single_Linked_List.h"
//打印链表
void SlistPrint(Slist* phead)
{
assert(phead);
Slist* Current = phead;
while(Current)
{
printf("%d->", Current->data);
Current = Current->next;
}
printf("\n");
}
//创建节点
Slist* SlistCreateNode(LKDataType value)
{
Slist* NewNode = (Slist *)malloc(sizeof(Slist));
if(NewNode == NULL)
{
perror("malloc fail\n");
exit(-1);
}
NewNode->data = value;
NewNode->next = NULL;
return NewNode;
}
//头插数据
void SlistPushfront(Slist** pphead, LKDataType value)
{
//确保plist的地址为有效地址
assert(pphead);
Slist* NewNode = SlistCreateNode(value);
//让创建的节点存储最初的头结点的地址;
NewNode->next = *pphead;
//让头节点存储新头结点的地址
*pphead = NewNode;
}
//尾插数据
void SlistPushback(Slist** pphead, LKDataType value)
{
assert(pphead);
Slist* NewNode = SlistCreateNode(value);
//链表为空即phead的地址为NULL
//这里改变的是结构体的指针,一开始plist指向的地址是NULL
if (*pphead == NULL)
{
*pphead = NewNode;
}
else
{
//先找到最后一个节点
Slist* Current = *pphead;
while(Current->next != NULL)
{
//这里改变的是结构体的成员
Current = Current->next;
}
//然后在最后一个节点里存放新节点的地址
Current->next = NewNode;
}
}
//头删数据
void SlistPopfront(Slist** pphead)
{
assert(pphead);
//空节点不能删
assert(*pphead);
//记录头节点
Slist* temp = *pphead;
//plist指向head的next
*pphead = (*pphead)->next;
//释放最初的头结点
free(temp);
}
//尾删数据
void SlistPopback(Slist** pphead)
{
assert(pphead);
//空节点不能删
assert(*pphead);
//单独处理一个节点的情况
if((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//找尾节点的前一个节点
else
{
//记录头节点
Slist* tail = *pphead;
Slist* previous = NULL;
while (tail->next)
{
//记录尾节点的前一个节点
previous = tail;
//这里改变的是结构体的成员
tail = tail->next;
}
free(tail);
//找尾之后直接释放(tail可置可不置)
tail = NULL;
//将上一个节点的所存储的地址置为空
previous->next = NULL;
}
}
//查找节点
Slist* SlistFindNode(Slist* phead, LKDataType value)
{
Slist* current = phead;
while (current != NULL)
{
//根据值来进行查找
if (current->data == value)
{
return current;
}
else
{
current = current->next;
}
}
return NULL;
}
//在position位置的前面添加数据
void SlistInsert(Slist** pphead, Slist * position, LKDataType value)
{
assert(pphead);
//防止一个为空与一个不为空的情况(链表是空的,但是position这一节点不存在)
assert((!position && !(*pphead)) || (position && *pphead));
Slist* NewNode = SlistCreateNode(value);
if (NewNode == NULL)
{
perror("CreateNode Fail");
exit(-1);
}
//等于头结点,则是头插
if (position == *pphead)
{
SlistPushfront(pphead, value);
}
else
{
Slist* Previous = *pphead;
//找到position位置的前一个节点
while(Previous->next != position)
{
Previous = Previous->next;
}
//新节点的next指针指向position位置
NewNode->next = position;
//position位置的前一个节点的next指针指向NewNode
Previous->next = NewNode;
}
}
//删除
// position位置的删除数据
void SlistDelete(Slist** pphead, Slist* position)
{
//防止一个为空与一个不为空的情况(链表是空的,但是position这一节点不存在)
assert((!position && !(*pphead)) || (position && *pphead));
if (*pphead == position)
{
*pphead = position->next;
free(position);
position = NULL;
}
else
{
Slist* Previous = *pphead;
//找到position位置的前一个节点
while(Previous->next != position)
{
Previous = Previous->next;
}
Previous->next = position->next;
free(position);
}
}
//postion后面位置的添加数据
void SlistInsertAfter(Slist* position, LKDataType value)
{
assert(position);
Slist* NewNode = SlistCreateNode(value);
if(NULL == NewNode)
{
perror("malloc fail");
exit(-1);
}
NewNode->next = position->next;
position->next = NewNode;
}
//position后面位置的删除数据
void SlistDeleteAfter(Slist* position)
{
assert(position);
Slist* temp = position->next;
position->next = temp->next;
free(temp);
}
//销毁链表
void SlistDestory(Slist** pphead)
{
assert(pphead);
Slist* Current = *pphead;
while(Current)
{
Slist* temp = Current->next;
free(Current);
Current = temp;
}
*pphead = NULL;
}3.3:Test.c代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS
#include "single_linked_list.h"
//测试头插和尾插
void test1(Slist** list)
{
printf("头插与尾插:>");
SlistPushfront(&(*list), 0);
SlistPushfront(&(*list), 1);
SlistPushfront(&(*list), 2);
SlistPushfront(&(*list), 3);
SlistPushfront(&(*list), 4);
SlistPushback(&(*list), 5);
SlistPushback(&(*list), 6);
SlistPushback(&(*list), 7);
SlistPrint(*list);
}
//测试头删和尾删
void test2(Slist** list)
{
printf("头删与尾删:>");
SlistPopback(&(*list));
SlistPopback(&(*list));
SlistPopback(&(*list));
SlistPopfront(list);
SlistPopfront(list);
SlistPrint(*list);
}
//测试查找与任意位置的增加
void test3(Slist** list)
{
//链表与要插入的位置都为空的情况
Slist* position = SlistFindNode(*list, 2);
SlistInsert(&(*list), position, 5);
SlistPrint(*list);
position = SlistFindNode(*list, 5);
SlistInsert(&(*list), position, 8);
SlistInsert(&(*list), position, 9);
SlistInsert(&(*list), position, 10);
SlistPrint(*list);
}
//测试查找与任意位置的删除
void test4(Slist** list)
{
SlistPushfront(list, 3);
Slist* position = SlistFindNode(*list, 10);
SlistPrint(*list);
SlistDelete(list, position);
SlistPrint(*list);
SlistPushback(list, 5);
SlistPushback(list, 6);
SlistPushback(list, 7);
SlistPushfront(list, 4);
SlistPushfront(list, 3);
position = SlistFindNode(*list, 5);
SlistDelete(list, position);
SlistPrint(*list);
}
//测试在position位置之后的数据添加与删除与链表销毁
void test5(Slist** list)
{
SlistPushback(list, 5);
SlistPushback(list, 6);
SlistPushback(list, 7);
SlistPushfront(list, 4);
SlistPushfront(list, 3);
SlistPrint(*list);
Slist* position = SlistFindNode(*list, 5);
SlistInsertAfter(position, 20);
SlistInsertAfter(position, 30);
SlistPrint(*list);
SlistDeleteAfter(position);
SlistDeleteAfter(position);
SlistDeleteAfter(position);
SlistDeleteAfter(position);
SlistPrint(*list);
SlistDestory(list);
}
int main()
{
Slist* list = NULL;
test1(&list);
test2(&list);
test3(&list);
test4(&list);
test5(&list);
return 0;
}4:带头双向循环链表的实现4.1:Doubly_Circular_Linked_List.h代码语言：javascript复制#pragma once
#include
#include
#include
typedef int CircularDatatype;
typedef struct CircularList
{
struct CircularList* next;
struct CircularList* previos;
CircularDatatype value;
}CircularList;
//创建节点
CircularList* CreateNewnode(CircularDatatype value);
//初始化带头双向循环链表
void CircularListInit(CircularList** phead);
//尾插数据
void CircularListPushback(CircularList* phead, CircularDatatype value);
//尾删数据
void CircularListPopback(CircularList* phead);
//头插数据
void CircularListPushfront(CircularList* phead, CircularDatatype value);
//头删数据
void CircularListPopfront(CircularList* phead);
//查找节点
CircularList* CircularListFind(CircularList* phead, CircularDatatype value);
//在position位置的前面添加数据
void CircularListInsert(CircularList* postion,CircularDatatype value);
//删除postion位置的节点
void CircularListErase(CircularList* phead,CircularList* position);
//销毁链表
void CircularListDestory(CircularList* phead);
//打印带头双向循环链表
void CircularListPrint(CircularList* phead);4.2:Doubly_Circular_Linked_List.c4.2.1:初始化与创建节点与尾插代码语言：javascript复制#include "Doubly_Circular_Linked_List.h"
//创建节点
CircularList* CreateNewnode(CircularDatatype value)
{
CircularList* NewNode = (CircularList *)malloc(sizeof(CircularList));
if (NewNode == NULL)
{
perror("malloc fail\n");
exit(-1);
}
NewNode->value = value;
NewNode->previos = NULL;
NewNode->next = NULL;
return NewNode;
}
//打印带头双向循环链表
void CircularListPrint(CircularList* phead)
{
assert(phead);
CircularList* Current = phead->next;
while(Current != phead)
{
printf("%d->", Current->value);
Current = Current->next;
}
}
//初始化带头双向循环链表
void CircularListInit(CircularList** pphead)
{
//确保传过来的地址是有效地址
assert(pphead);
//创建哨兵位的头结点
*pphead = CreateNewnode(-1);
//指向自己
(*pphead)->previos = *pphead;
(*pphead)->next = *pphead;
}
//尾插数据
void CircularListPushback(CircularList* phead, CircularDatatype value)
{
assert(phead);
//创建节点
CircularList* NewNode = CreateNewnode(value);
if(NewNode == NULL)
{
perror("malloc fail");
exit(-1);
}
CircularList* tail = phead->previos;
//新节点的前驱链接旧链表的尾节点
NewNode->previos = tail;
//旧尾节点存储新尾节点的地址
tail->next = NewNode;
//哨兵位的前驱节点链接新节点
phead->previos = NewNode;
//新节点的next指针指向头结点
NewNode->next = phead;
}4.2.2:尾删与头插与头删数据代码语言：javascript复制//尾删数据
void CircularListPopback(CircularList* phead)
{
assert(phead);
CircularList* tail = phead->previos;
//哨兵位的前驱节点指向尾节点的前驱
phead->previos = tail->previos;
//尾节点的前驱节点的next指向哨兵位
tail->previos->next = phead;
free(tail);
tail = NULL;
}
//头插数据
void CircularListPushfront(CircularList* phead, CircularDatatype value)
{
assert(phead);
CircularList* NewNode = CreateNewnode(value);
if (NewNode == NULL)
{
perror("malloc fail");
exit(-1);
}
//记录旧的头结点
CircularList* OldHead = phead->next;
//哨兵位的next指针指向NewNode
phead->next = NewNode;
//新节点的前驱指向哨兵位
NewNode->previos = phead;
//新节点的后驱指向旧的头节点
NewNode->next = OldHead;
//旧的头结点的前驱指向NewNode
OldHead->previos = NewNode;
}
//头删数据
void CircularListPopfront(CircularList* phead)
{
assert(phead);
//保存旧的头节点
CircularList* OldHead = phead->next;
//哨兵位头节点的next指针指向旧的头节点的next
phead->next = OldHead->next;
//旧的头节点的下一个节点的前驱节点指向哨兵位
OldHead->next->previos = phead;
free(OldHead);
}4.2.3:查找节点与在position位置的前面插入节点代码语言：javascript复制//查找节点
CircularList* CircularListFind(CircularList* phead, CircularDatatype value)
{
assert(phead);
CircularList* Current = phead;
while(Current->next != phead)
{
if (Current->value == value)
return Current;
Current = Current->next;
}
return NULL;
}
//在position位置的前面添加数据
void CircularListInsert(CircularList* postion, CircularDatatype value)
{
assert(postion);
CircularList* NewNode = CreateNewnode(value);
//新节点的前驱指向posituon位置的前一个节点
NewNode->previos = postion->previos;
//新节点的next指向position节点
NewNode->next = postion;
//position位置的前一个节点next指向新节点
postion->previos->next = NewNode;
//position位置的节点的前驱指向NewNode
postion->previos = NewNode;
}4.2.4:删除position位置的节点与销毁链表代码语言：javascript复制//删除postion位置的节点
void CircularListErase(CircularList* phead, CircularList* position)
{
assert(phead);
CircularList* temp = position->previos;
//temp的next指针指向position的下一个节点
temp->next = position->next;
//position的下一个节点的前驱指向temp
position->next->previos = temp;
}
//销毁链表
void CircularListDestory(CircularList* phead)
{
assert(phead);
CircularList* Current = phead->next;
while(Current != phead)
{
CircularList* temp = Current->next;
free(Current);
Current = temp;
}
}4.3:Test.c4.3.1:测试初始化与创建节点与尾插代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS
#include "Doubly_Circular_Linked_List.h"
void TestInitAndPushBack(CircularList ** List)
{
CircularListInit(List);
CircularListPushback(*List,1);
CircularListPushback(*List,2);
CircularListPushback(*List,3);
CircularListPrint(*List);
}
int main()
{
CircularList* List;
TestInitAndPushBack(&List);
return 0;
}4.3.2:测试尾删与头插与头删数据代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS
#include "Doubly_Circular_Linked_List.h"
void TestPushFrontAndPopFrontAndPopBack(CircularList** List)
{
CircularListInit(List);
CircularListPushback(*List, 1);
CircularListPushback(*List, 2);
CircularListPushback(*List, 3);
CircularListPrint(*List);
CircularListPopback(*List);
CircularListPopback(*List);
CircularListPrint(*List);
CircularListPushfront(*List, 5);
CircularListPushfront(*List, 4);
CircularListPushfront(*List, 6);
CircularListPrint(*List);
CircularListPopfront(*List);
CircularListPopfront(*List);
CircularListPrint(*List);
}
int main()
{
CircularList* List;
//TestInitAndPushBack(&List);
TestPushFrontAndPopFrontAndPopBack(&List);
return 0;
}4.3.3:测试查找节点与在position位置的前面插入节点代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS
#include "Doubly_Circular_Linked_List.h"
void TestFindAndInsert(CircularList** List)
{
CircularListInit(List);
CircularListPushback(*List, 1);
CircularListPushback(*List, 2);
CircularListPushback(*List, 3);
CircularListPrint(*List);
CircularList* position = CircularListFind(*List, 2);
CircularListInsert(position, 4);
position = CircularListFind(*List, 1);
CircularListInsert(position, 25);
CircularListPrint(*List);
}
int main()
{
CircularList* List;
TestFindAndInsert(&List);
return 0;
}4.3.4:测试删除position位置的节点与销毁链表代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS
#include "Doubly_Circular_Linked_List.h"
void TestEraseAndDestory(CircularList** List)
{
CircularListInit(List);
CircularListPushback(*List, 1);
CircularListPushback(*List, 2);
CircularListPushback(*List, 3);
CircularListPrint(*List);
CircularList* position = CircularListFind(*List, 2);
CircularListInsert(position, 4);
position = CircularListFind(*List, 1);
CircularListPrint(*List);
printf("\n");
CircularListErase(*List, position);
position = CircularListFind(*List, 2);
CircularListErase(*List, position);
CircularListPrint(*List);
CircularListDestory(*List);
//释放哨兵位的头结点
free(*List);
*List = NULL;
CircularListPrint(*List);
}
int main()
{
CircularList* List;
TestEraseAndDestory(&List);
return 0;
}5:带头双向循环链表的总代码5.1:Doubly_Circular_Linked_List.h代码语言：javascript复制#pragma once
#include
#include
#include
typedef int CircularDatatype;
typedef struct CircularList
{
struct CircularList* next;
struct CircularList* previos;
CircularDatatype value;
}CircularList;
//创建节点
CircularList* CreateNewnode(CircularDatatype value);
//初始化带头双向循环链表
void CircularListInit(CircularList** phead);
//尾插数据
void CircularListPushback(CircularList* phead, CircularDatatype value);
//尾删数据
void CircularListPopback(CircularList* phead);
//头插数据
void CircularListPushfront(CircularList* phead, CircularDatatype value);
//头删数据
void CircularListPopfront(CircularList* phead);
//查找节点
CircularList* CircularListFind(CircularList* phead, CircularDatatype value);
//在position位置的前面添加数据
void CircularListInsert(CircularList* postion, CircularDatatype value);
//删除postion位置的节点
void CircularListErase(CircularList* phead, CircularList* position);
//销毁链表
void CircularListDestory(CircularList* phead);
//打印带头双向循环链表
void CircularListPrint(CircularList* phead);5.2:Doubly_Circular_Linked_List.c代码语言：javascript复制#include "Doubly_Circular_Linked_List.h"
//创建节点
CircularList* CreateNewnode(CircularDatatype value)
{
CircularList* NewNode = (CircularList *)malloc(sizeof(CircularList));
if (NewNode == NULL)
{
perror("malloc fail\n");
exit(-1);
}
NewNode->value = value;
NewNode->previos = NULL;
NewNode->next = NULL;
return NewNode;
}
//打印带头双向循环链表
void CircularListPrint(CircularList* phead)
{
assert(phead);
CircularList* Current = phead->next;
while(Current != phead)
{
printf("%d->", Current->value);
Current = Current->next;
}
printf("\n");
}
//初始化带头双向循环链表
void CircularListInit(CircularList** pphead)
{
//确保传过来的地址是有效地址
assert(pphead);
//创建哨兵位的头结点
*pphead = CreateNewnode(-1);
//指向自己
(*pphead)->previos = *pphead;
(*pphead)->next = *pphead;
}
//尾插数据
void CircularListPushback(CircularList* phead, CircularDatatype value)
{
assert(phead);
//创建节点
CircularList* NewNode = CreateNewnode(value);
if(NewNode == NULL)
{
perror("malloc fail");
exit(-1);
}
CircularList* tail = phead->previos;
//新节点的前驱链接旧链表的尾节点
NewNode->previos = tail;
//旧尾节点存储新尾节点的地址
tail->next = NewNode;
//哨兵位的前驱节点链接新节点
phead->previos = NewNode;
//新节点的next指针指向头结点
NewNode->next = phead;
}
//尾删数据
void CircularListPopback(CircularList* phead)
{
assert(phead);
CircularList* tail = phead->previos;
//哨兵位的前驱节点指向尾节点的前驱
phead->previos = tail->previos;
//尾节点的前驱节点的next指向哨兵位
tail->previos->next = phead;
free(tail);
tail = NULL;
}
//头插数据
void CircularListPushfront(CircularList* phead, CircularDatatype value)
{
assert(phead);
CircularList* NewNode = CreateNewnode(value);
if (NewNode == NULL)
{
perror("malloc fail");
exit(-1);
}
//记录旧的头结点
CircularList* OldHead = phead->next;
//哨兵位的next指针指向NewNode
phead->next = NewNode;
//新节点的前驱指向哨兵位
NewNode->previos = phead;
//新节点的后驱指向旧的头节点
NewNode->next = OldHead;
//旧的头结点的前驱指向NewNode
OldHead->previos = NewNode;
}
//头删数据
void CircularListPopfront(CircularList* phead)
{
assert(phead);
//保存旧的头节点
CircularList* OldHead = phead->next;
//哨兵位头节点的next指针指向旧的头节点的next
phead->next = OldHead->next;
//旧的头节点的下一个节点的前驱节点指向哨兵位
OldHead->next->previos = phead;
free(OldHead);
}
//查找节点
CircularList* CircularListFind(CircularList* phead, CircularDatatype value)
{
assert(phead);
CircularList* Current = phead;
while(Current->next != phead)
{
if (Current->value == value)
return Current;
Current = Current->next;
}
return NULL;
}
//在position位置的前面添加数据
void CircularListInsert(CircularList* postion, CircularDatatype value)
{
assert(postion);
CircularList* NewNode = CreateNewnode(value);
//新节点的前驱指向posituon位置的前一个节点
NewNode->previos = postion->previos;
//新节点的next指向position节点
NewNode->next = postion;
//position位置的前一个节点next指向新节点
postion->previos->next = NewNode;
//position位置的节点的前驱指向NewNode
postion->previos = NewNode;
}
//删除postion位置的节点
void CircularListErase(CircularList* phead, CircularList* position)
{
assert(phead);
CircularList* temp = position->previos;
//temp的next指针指向position的下一个节点
temp->next = position->next;
//position的下一个节点的前驱指向temp
position->next->previos = temp;
}
//销毁链表
void CircularListDestory(CircularList* phead)
{
assert(phead);
CircularList* Current = phead->next;
while(Current != phead)
{
CircularList* temp = Current->next;
free(Current);
Current = temp;
}
}5.3:Test.c代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS
#include "Doubly_Circular_Linked_List.h"
//测试初始化,尾删与尾插
void test1(CircularList* phead)
{
printf("尾插与尾删:>");
CircularListInit(&phead);
CircularListPushback(phead, 1);
CircularListPushback(phead, 2);
CircularListPushback(phead, 3);
CircularListPushback(phead, 4);
CircularListPushback(phead, 5);
CircularListPushback(phead, 6);
CircularListPopback(phead);
CircularListPopback(phead);
CircularListPopback(phead);
CircularListPrint(phead);
}
//测试头插与头删
void test2(CircularList* phead)
{
printf("头插与头删:>");
CircularListInit(&phead);
CircularListPushfront(phead, 0);
CircularListPushfront(phead, 1);
CircularListPushfront(phead, 2);
CircularListPushfront(phead, 3);
CircularListPushfront(phead, 4);
CircularListPushfront(phead, 5);
CircularListPushfront(phead, 6);
CircularListPopfront(phead);
CircularListPopfront(phead);
CircularListPopfront(phead);
CircularListPopfront(phead);
CircularListPrint(phead);
}
//测试查找与在position位置的前面添加数据与删除position位置的数据
void test3(CircularList* phead)
{
CircularListInit(&phead);
CircularListPushfront(phead, 3);
CircularListPushfront(phead, 4);
CircularListPushfront(phead, 5);
CircularListPushfront(phead, 6);
CircularListPushfront(phead, 7);
CircularList* position = CircularListFind(phead, 5);
if (position != NULL)
{
position->value = position->value * 15;
}
CircularListInsert(position, 72);
CircularListInsert(position, 73);
CircularListInsert(position, 74);
CircularListPrint(phead);
if (position != NULL)
{
CircularListErase(phead, position);
position = NULL;
}
CircularListPrint(phead);
}
//测试销毁链表
void test4(CircularList* phead)
{
CircularListInit(&phead);
CircularListPushfront(phead, 3);
CircularListPushfront(phead, 4);
CircularListPushfront(phead, 5);
CircularListPushfront(phead, 6);
CircularListPushfront(phead, 7);
CircularListPrint(phead);
CircularListDestory(phead);
phead = NULL;
}
int main()
{
CircularList* phead = NULL;
test1(phead);
test2(phead);
test3(phead);
test4(phead);
}6:顺序表与链表的区别不同点
顺序表
链表
存储空间上
物理和逻辑上一定连续
逻辑上连续,但是物理上不一定连续.
访问方式
随机访问,O(1)
不支持随机访问,O(N)
任意位置插入与删除
可能需要迁移元素,O(N);
只需要修改指针指向
插入
动态顺序表,空间不够时需要扩容.
没有容量的概念
应用场景
元素高效存储
+
频繁访问
元素高效存储
+
频繁访问
缓存利用率
高
低
好啦,uu们,数据结构链表这部分滴详细内容博主就讲到这里啦,如果uu们觉得博主讲的不错的话,请动动你们滴小手给博主点点赞,你们滴鼓励将成为博主源源不断滴动力,同时也欢迎大家来指正博主滴错误~