从零开始学链表:数据结构的基础与应用
嘿嘿,家人们,今天咱们来详细剖析数据结构中的链表,好啦,废话不多讲,开干!
1:链表
1.1:链表的概念以及结构
1.2:链表的分类
2:无头单向非循环链表的实现
2.1:Single_Linked_List.h
2.2:Single_Linked_List.c
2.2.1:打印链表与创建链表节点
2.2.2:头插与尾插节点
2.2.3:头删节点与尾删节点
2.2.4:查找节点与在position位置的前面插入节点
2.2.5:删除position位置的节点与删除position位置后面的节点以及在position位置后面添加节点
2.2.6:链表的销毁
2.3:Test.c
2.3.1:测试打印链表与创建链表节点
2.3.2:测试头插与尾插
2.3.3:测试头删与尾删
2.3.4:测试查找与在position位置的前面添加节点
2.3.6:测试删除position位置的节点与删除position位置后面的节点以及在position位置后面添加节点
2.3.7:测试链表的销毁
3:无头单向非循环链表的总代码
3.1:Single_Linked_List.h
3.2:Single_Linked_List.c
3.3:Test.c
4:带头双向循环链表的实现
4.1:Doubly_Circular_Linked_List.h
4.2:Doubly_Circular_Linked_List.c
4.2.1:初始化与创建节点与尾插
4.2.2:尾删与头插与头删数据
4.2.3:查找节点与在position位置的前面插入节点
4.2.4:删除position位置的节点与销毁链表
4.3:Test.c
4.3.1:测试初始化与创建节点与尾插
4.3.2:测试尾删与头插与头删数据
4.3.3:测试查找节点与在position位置的前面插入节点
4.3.4:测试删除position位置的节点与销毁链表
5:带头双向循环链表的总代码
5.1:Doubly_Circular_Linked_List.h
5.2:Doubly_Circular_Linked_List.c
5.3:Test.c
6:顺序表与链表的区别
1:链表
1.1:链表的概念以及结构
链表是一种 物理存储结构上非连续 、 非顺序的存储结构，数据元素的 逻辑顺序 是通过链表中的 指针链接 次序实现的.
- 链表的结构跟火车车厢相似, 淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉或者加上,不会影响其他⻋厢，每节⻋厢都是独立存在的.
- 从上图我们可以看到,链式结构在逻辑上是连续的,但是在物理上不一定连续.
- 现实中的节点一般都是从堆上申请出来的.
- 从堆上申请的空间,是按照一定的策略来进行分配的,两次申请的空间可能连续,也可能不连续.
- 与顺序表不同的是,链表里的每节"车厢"都是独立申请下来的空间,我们称之为"结点/结点",结点有以下两个组成部分:
结合前⾯学到的结构体知识,我们可以给出每个节点对应的结构体代码:假设当前保存的节点为整型.
#include <stdio.h>
struct ListNode
{
int Value;
struct ListNode* Next;
};当我们想要保存⼀个整型数据时,实际是向操作系统申请了⼀块内存,这个内存不仅要保存整型数据,也需要保存下⼀个节点的地址(当下⼀个节点为空时保存的地址为空).当我们想要从第⼀个节点⾛到最后⼀个节点时,只需要在前⼀个节点拿上下⼀个节点的地址下⼀个节点的钥匙)就可以了.
假设在32位系统上,结点中值域为int类型,
则一个节点的大小为8个字节,则也有可能下面的链表.
1.2:链表的分类
实际中的链表的结构十分多样,组合起来有8种链表结构:
1.单向或双向
2.带头或不带头
3.循环或非循环
虽然链表的结构有如此之多,但实践中最常用的还是两种结构:无头单向非循环链表与带头双向循环链表.
- 无头单向非循环链表:结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等.
- 带头双向循环链表:结构最复杂,一般用在单独存储数据.实际中使用的链表数据结构,都是带头双向循环链表.
2:无头单向非循环链表的实现
2.1:Single_Linked_List.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//结构声明与函数声明
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.c
2.2.1:打印链表与创建链表节点
#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:头插与尾插节点
//头插数据
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:头删节点与尾删节点
//头删数据
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位置的前面插入节点
//查找节点
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位置后面添加节点
// 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:链表的销毁
//销毁链表
void SlistDestory(Slist** pphead)
{
assert(pphead);
Slist* Current = *pphead;
while(Current)
{
Slist* temp = Current->next;
free(Current);
Current = temp;
}
*pphead = NULL;
}2.3:Test.c
2.3.1:测试打印链表与创建链表节点
#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:测试头插与尾插
#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:测试头删与尾删
#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位置的前面添加节点
#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位置后面添加节点
#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:测试链表的销毁
#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
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//结构声明与函数声明
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
#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
#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
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
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.c
4.2.1:初始化与创建节点与尾插
#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:尾删与头插与头删数据
//尾删数据
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位置的前面插入节点
//查找节点
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位置的节点与销毁链表
//删除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.c
4.3.1:测试初始化与创建节点与尾插
#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:测试尾删与头插与头删数据
#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位置的前面插入节点
#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位置的节点与销毁链表
#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
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
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
#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
#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们觉得博主讲的不错的话,请动动你们滴小手给博主点点赞,你们滴鼓励将成为博主源源不断滴动力,同时也欢迎大家来指正博主滴错误~