欢迎来到尧图网

客户服务 关于我们

您的位置：首页 > 财经 > 金融 > 从零开始学链表:数据结构的基础与应用

从零开始学链表:数据结构的基础与应用

2025/5/30 3:46:39 来源：https://blog.csdn.net/ABWSO/article/details/142992693  浏览:  次   关键词：从零开始学链表:数据结构的基础与应用

嘿嘿,家人们,今天咱们来详细剖析数据结构中的链表,好啦,废话不多讲,开干!

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:链表的概念以及结构

链表是一种 物理存储结构上非连续 、 非顺序的存储结构，数据元素的 逻辑顺序 是通过链表
中的 指针链接 次序实现的.

 

  • 链表的结构跟火车车厢相似, 淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉或者加上,不会影响其他⻋厢，每节⻋厢都是独立存在的.
  • ⻋厢是独立存在的,且每节⻋厢都有车门.可以想象⼀下介样滴的场景，假设每节⻋厢的车门都是锁上的状态,需要不同的钥匙才能解锁,每次只能携带⼀把钥匙的情况下如何从⻋头走到车尾？
最简单的做法：每节车厢里都放一把下⼀节车厢的钥匙.
  1. 从上图我们可以看到,链式结构在逻辑上是连续的,但是在物理上不一定连续.
  2. 现实中的节点一般都是从堆上申请出来的.
  3. 从堆上申请的空间,是按照一定的策略来进行分配的,两次申请的空间可能连续,也可能不连续.
  4. 与顺序表不同的是,链表里的每节"车厢"都是独立申请下来的空间,我们称之为"结点/结点",结点有以下两个组成部分:
  • 图中指针变量 plist保存的是第⼀个节点的地址,我们称plist此时"指向"第⼀个节点,如果我们想要plist“指向”第二个节点时，只需要修改plist保存的内容为0x0012FFB0.  
那么为什么还要指针变量来保存下一个节点的位置呢?
  • 链表中每个节点都是 独立申请 的( 即需要插⼊数据时才去申请⼀块节点的空间 ),我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点.
结合前⾯学到的结构体知识,我们可以给出每个节点对应的结构体代码:
假设当前保存的节点为整型. 
#include <stdio.h>struct ListNode
{int Value;struct ListNode* Next;
};
当我们想要保存⼀个整型数据时,实际是向操作系统申请了⼀块内存,这个内存不仅要保存整型数据,也需要保存下⼀个节点的地址(当下⼀个节点为空时保存的地址为空).
当我们想要从第⼀个节点⾛到最后⼀个节点时,只需要在前⼀个节点拿上下⼀个节点的地址下⼀个节点的钥匙)就可以了.
假设在32位系统上,结点中值域为int类型, 则一个节点的大小为8个字节,则也有可能下面的链表.

1.2:链表的分类

实际中的链表的结构十分多样,组合起来有8种链表结构:

1.单向或双向

2.带头或不带头

3.循环或非循环

虽然链表的结构有如此之多,但实践中最常用的还是两种结构:无头单向非循环链表与带头双向循环链表. 

  1.  无头单向非循环链表:结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等.
  2. 带头双向循环链表:结构最复杂,一般用在单独存储数据.实际中使用的链表数据结构,都是带头双向循环链表.

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指向的地址是NULLif (*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指针指向NewNodePrevious->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指向的地址是NULLif (*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指针指向NewNodePrevious->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指针指向NewNodephead->next = NewNode;//新节点的前驱指向哨兵位NewNode->previos = phead;//新节点的后驱指向旧的头节点NewNode->next = OldHead;//旧的头结点的前驱指向NewNodeOldHead->previos = NewNode;
}//头删数据
void CircularListPopfront(CircularList* phead)
{assert(phead);//保存旧的头节点CircularList* OldHead = phead->next;//哨兵位头节点的next指针指向旧的头节点的nextphead->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位置的节点的前驱指向NewNodepostion->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的下一个节点的前驱指向tempposition->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指针指向NewNodephead->next = NewNode;//新节点的前驱指向哨兵位NewNode->previos = phead;//新节点的后驱指向旧的头节点NewNode->next = OldHead;//旧的头结点的前驱指向NewNodeOldHead->previos = NewNode;
}//头删数据
void CircularListPopfront(CircularList* phead)
{assert(phead);//保存旧的头节点CircularList* OldHead = phead->next;//哨兵位头节点的next指针指向旧的头节点的nextphead->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位置的节点的前驱指向NewNodepostion->previos = NewNode;
}//删除postion位置的节点
void  CircularListErase(CircularList* phead, CircularList* position)
{assert(phead);CircularList* temp = position->previos;//temp的next指针指向position的下一个节点temp->next = position->next;//position的下一个节点的前驱指向tempposition->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们觉得博主讲的不错的话,请动动你们滴小手给博主点点赞,你们滴鼓励将成为博主源源不断滴动力,同时也欢迎大家来指正博主滴错误~

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

相关资讯

热文排行

最新新闻

推荐新闻

热搜词