前言
链表是一种物理存储结构上非连续非线性的结构，数据元素的逻辑顺序通过指针次序链接实现。
链表的结构多种多样，通过以下情况组合起来有8种结构：
1.带头、不带头
2.单向、双向
3.循环、非循环
但实际中最常用的只有不带头单向非循环和带头双向循环两种结构。
不带头单向非循环：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶等
带头双向循环链表：结构最复杂，一般用在单独存储数据。虽然结构复杂但实现起来非常简单，后面我们实现代码就知道了
关于带头、不带的问题，就是有无带哨兵位的头节点：
带头就是始终有一个头节点存在，头节点head不存储有效数据，data为随机值不用管。
带哨兵位的头节点需要我们预先开辟，使用完后释放，而不带头的就不需要创建头节点了，但是每次都需要判断链表的头指针释放为空，各有各的优缺点。
下图：假定有一个plist的指针维护链表，头节点head，有效数据存储在头节点之后，如果没有存储数据，头节点的next就指向NULL，这样不管是头插头删还是尾插尾删都不需要像不带头的链表需要判断头节点是否为空
不带头：没有头节点，plsit直接指向有效数据，链表为空时plist就指向NULL;
双向单向问题：节点的结构不同，单向只有一个指针next存储下一节点的地址，双向有两个指针prev和next，分别存储上一节点和下一节点的地址。
循环非循问题：尾节点的next和头节点的prev是否为空
下图就是双向循环链表，尾节点data3的next指向头节点，头节点的prev指向尾节点，就构成循环
如果是非循环的话，data3的next和头节点的prev就为NULL
函数的传参
当然小伙伴还不理解的话也没有关系，相信你了解完下面单链表的实现就懂了。在这之前呢我们再讨论下传参问题，什么时候传一级指针，什么时候传二级指针？
我们通过一个简单的测试来演示
#include <stdio.h>
void Test1(int* ret)
{
++ret;
}
void Test2(int* ret)
{
*ret = 10;
}
void Test3(int** pp)
{
(*pp)++;
}
int main()
{
int arr[5] = { 1,2,3,4,5 };
int* p = arr;
Test1(p);
printf("%d\n", *p);
Test2(p);
printf("%d\n", *p);
Test3(&p);
printf("%d\n", *p);
return 0;
}
有一个数组arr，数组名是首元素的地址，让指针p指向第一个元素
Test1中传指针p，形参实参的一份临时拷贝，所以有一个指针ret也指向数组中的1，然后++ret，让ret指向2，但是指针p仍然指向1.
Test3中传指针p的地址，指针pp指向p，pp通过解引用操作p改变p的指向，所以p指向2
在Test2中，通过指针解引用，将p指向的1改为10.
那我们就可以得出一个结论：要改变一级指针的指向就要传二级指针，当然还可以用接收返回值的方式改变指针的指向，多级指针以此类推,
如果不改变一级指针的指向，就传一级指针，多级指针以此类推。
不带头单向非循环链表
简称单链表Single List，一般很多oj题都会出这种结构的题目，而实际中是作为其他结构的子结构，如哈希桶等。
先看功能函数的声明 SList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DataType;
typedef struct SingleListNode
{
DataType data;
struct SingleListNode* next;
}SListNode;
//打印链表
void SListNodePrint(SListNode* phead);
//链表尾插
void SListNodepushback(SListNode** pphead, DataType x);
//链表头插
void SListNodepushfront(SListNode** pphead, DataType x);
//链表尾删
void SListNodepopback(SListNode** pphead);
//链表头删
void SListNodepopfront(SListNode** pphead);
//寻找链表中数据所在的位置
SListNode* SListNodeFind(SListNode* phead, DataType x);
//链表指定pos位置前插入
void SListNodeInsert(SListNode** pphead, SListNode* pos, DataType x);
//链表指定pos位置后插入
void SListNodeInsertAfter(SListNode* pos, DataType x);
//链表指定pos位置删除数据
void SListNodeErase(SListNode** pphead, SListNode* pos);
//链表销毁
void SListNodeDestroy(SListNode** pphead);
单链表的基本结构:
节点的结构为：data数据保存值，next保存下一节点地址，通过next找到下一节点，且尾节点的next始终指向NULL
typedef int DataType;
typedef struct SingleListNode
{
DataType data;
struct SingleListNode* next;
}SListNode;
我们操作链表传的都是二级指针，因为不管是头删头插，尾删尾插都有可能改变head的指向，只有打印链表不需要改变head的指向，可以传一级指针
首先第一步先创建一个head指针用来指向NULL，此时链表无节点，为NULL
SListNode* head = NULL;
对于每次头插和尾插都需要在堆上开辟新节点，我们就定义一个create函数，只需要传入要data数据值x，就可以创建一个newnode新节点，然后让next置空
//创建新节点
SListNode* Creatnode(DataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
newnode->data = x;
newnode->next = NULL;
return newnode;
}
头插：第一步先断言pphead始终不为空，如果我们参数传错了，传的是head且head为NULL,而不是head的地址就会断言报错
void SListNodepushfront(SListNode** pphead, DataType x)
{
assert(pphead);
SListNode* newnode = Creatnode(x);
newnode->next = *pphead;
*pphead = newnode;
}
头插不用考虑链表是否为NULL，因为始终要将head指向新的节点
我们要将新节点的next指向那个data1在的节点，然后然头指针head指向newnode，即使头指针为空，那newnode的next也是指向NULL的
尾插：第一步仍然是断言，然后是创建节点，尾插需要判断头指针是否为空，如果为空的话就要将头指针指向尾插的节点，不为空就直接在当前链表的尾节点后面插入
void SListNodepushback(SListNode** pphead, DataType x)
{
assert(pphead);
SListNode* newnode = Creatnode(x);
if (*pphead == NULL)
*pphead = newnode;
else
{
SListNode* ret = *pphead;
while (ret->next != NULL)
{
ret = ret->next;
}
ret->next = newnode;
}
}
不为空时，定义一个临时指针ret遍历当前链表找到链表的尾节点，因为尾节点的next为空，所以循环结束的条件就是ret->next == NULL,然后让ret的next指向newnode
头删：链表必须有节点才能删除，所以断言head也就是*pphead不能为空，
void SListNodepopfront(SListNode** pphead)
{
//链表为空不能删除
assert(*pphead != NULL);
SListNode* next = (*pphead)->next;
free(*pphead);
*pphead = NULL;
*pphead = next;
}
如果直接free头节点，那就找不到链表的下一个节点了，所以需要先定义一个next保存头指针的下一个节点，然后在free，这边*pphea置不置空都可以，因为链表也访问不到了，然后然头节点指向next
尾删：同样链表中有节点才能尾删，所以断言，然后就要判断链表中有一个节点还是一个以上的节点了：
1.只有一个节点，free头head，head指向NULL了
2.有一个以上节点就不需要改变头指针的指向，只需要用指针ret遍历链表找到尾节点删除即可，由于链表是单向的，如果我们让ret直接指向尾节点的话，它的前一个节点就找不到了，所以我们只遍历到尾节点的前一个节点，通过next释放尾节点，然后再让ret->next = NULL
void SListNodepopback(SListNode** pphead)
{
//链表为空不能删除
assert(*pphead != NULL);
//只有一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//两个及以上节点
else
{
SListNode* ret = *pphead;
while (ret->next->next != NULL)
{
ret = ret->next;
}
free(ret->next);
ret->next = NULL;
}
}
寻找链表中数据x所在位置：
由于不需要改变head指向，所以传一级指针，仍然要断言链表不能为空，定义一个指针cur遍历链表cur指向节点的data如果为x就返回cur的地址，遍历完链表还未找到就返回NULL，由于链表中可能有多个与x相同的值，这里只取找到的第一个节点的地址
SListNode* SListNodeFind(SListNode* phead, DataType x)
{
assert(phead != NULL);
SListNode* cur = phead;
//只能返回最开始找到的
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}
链表指定pos位置插入：
1、在pos位置之后插入：这种比较方便，通过find函数找到pos位置，然后就可以在pos后插入节点
//从pos后插入
void SListNodeInsertAfter(SListNode* pos, DataType x)
{
assert(pos);
SListNode* newnode = Creatnode(x);
newnode->next = pos->next;
pos->next = newnode;
}
2.在pos位置之前插入，首先断言，然后判断是否是在头节点插入，也就是头插了，其他情况的话，需要先找到pos前一个节点posprev，然后让posprev指向newnode，newnode的next指向pos位置
void ChainListInsert(CListNode** pphead, CListNode* pos, DataType x)
{
assert(pphead && pos);
CListNode* newnode = Creatnode(x);
//直接头插
if (*pphead == pos)
{
newnode->next = *pphead;
*pphead = newnode;
}
else
{
CListNode* posPrev = *pphead;
//找pos的前一个节点
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
newnode->next=posPrev->next;
posPrev->next = newnode;
}
}
pos位置的删除：
首先断言pos不为空且链表不为空，然后判断是否为头删，不为头删的话，那么需要找到pos位置的上一个节点，让posprev的next指向pos的next，然后free调pos完成pos位置删除
void SListNodeErase(SListNode**pphead, SListNode* pos)
{
assert(*pphead && pos);
//判断是否为头删
if (*pphead == pos)
{
*pphead = pos->next;
free(pos);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
最后就是链表的销毁了，要将之前malloc的所有节点都free置空，再将head置空，
定义一个next记录下一节点，释放当前节点后就可以找到下一节点，然后遍历链表全部free
void SListNodeDestroy(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
while (cur)
{
SListNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
还有一个打印函数，打印链表
void SListNodePrint(SListNode* phead)
{
while (phead != NULL)
{
printf("%d->", phead->data);
phead = phead->next;
}
printf("NULL\n");
}
最后我们测试一下 Test.c
#include "SList.h"
void Test1()
{
SListNode* head = NULL;
SListNodepushback(&head, 1);
SListNodepushback(&head, 2);
SListNodepushfront(&head, 4);
SListNodepushfront(&head, 5);
SListNodePrint(head);
}
void Test2()
{
SListNode* head = NULL;
SListNodepushback(&head, 1);
SListNodepushback(&head, 2);
SListNodepushback(&head, 3);
SListNodepopback(&head);
SListNodepopback(&head);
SListNodePrint(head);
}
void Test3()
{
SListNode* head = NULL;
SListNodepushback(&head, 1);
SListNodepushback(&head, 2);
SListNodepushback(&head, 3);
SListNodepushback(&head, 4);
SListNodepushback(&head, 5);
/*SListNode* pos = SListNodeFind(head, 5);
int i = 1;
while (pos != NULL)
{
printf("这是第%d个节点%p->%d\n", i++, pos, pos->data);
if (pos->next == NULL)
return;
pos = SListNodeFind(pos->next, 5);
}*/
SListNode* pos = SListNodeFind(head, 5);
if (pos != NULL)
{
SListNodeInsertAfter(pos, 10);
}
SListNodePrint(head);
}
int main()
{
Test1();
Test2();
Test3();
return 0;
}
带头双向循环链表
介绍完单链表后我们再来了解一下带头双向循环链表,简称双链表Doubel List，双链表的结构看起来复杂，多了一个指针prev存放上一节点的地址，但是实现起来非常简单
先展示功能函数的定义
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DataType;
typedef struct ListNode
{
DataType data;
struct ListNode* next; //存放下一个节点
struct ListNode* prev; //存放前一个节点
}ListNode;
//链表初始化，创建哨兵位头节点
ListNode* ListNodeInit();
//链表打印
void ListNodePrint(ListNode* phead);
//链表尾插
void ListNodePushBack(ListNode* phead, DataType x);
//链表尾删
void ListNodePopBack(ListNode* phead);
//链表头插
void ListNodePushFront(ListNode* phead, DataType x);
//链表头删
void ListNodePopFront(ListNode* phead);
//链表查找
ListNode* ListNodeFind(ListNode* phead, DataType x);
//链表指定pos位置前插入数据
void ListNodeInsert(ListNode* pos, DataType x);
//链表指定pos位置删除数据
void ListNodeErase(ListNode* pos);
//销毁链表
void ListNodeDestroy(ListNode* phead);
双链表的结构
typedef int DataType;
typedef struct ListNode
{
DataType data;
struct ListNode* next; //存放下一个节点
struct ListNode* prev; //存放前一个节点
}ListNode;
链表只有哨兵位的头节点就自己指向自己
plist指向头节点，因为我们不需要改变plist的指向，所以传一级指针即可，但是我们初始化，创建头节点，需要让pist指向头节点，这里我们直接用返回值接收就不用传二级指针了
ListNode* plist = ListNodeInit();
ListNode* ListNodeInit()
{
//创建哨兵位的头节点，方便尾插，对链表操作时也不用传二级指针了
struct ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
phead->next = phead;
phead->prev = phead;
return phead;
}
也就是上图的头节点自己指向自己的情况
由于每次都要创建新节点，所以直接封装成create函数，newnode的prev和next都置空
//创建新节点
ListNode* ListNodeCreate(DataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
头插：首先要创建新节点newnode，我们定义定义next指针记录头节点的后一个有节点，然后让phead的next指向newn，newnode的pre指向phead，建立链接关系，再让newnode的next指向next，next的prev指向newnode
void ListNodePushFront(ListNode* phead, DataType x)
{
assert(phead);
ListNode* newnode = ListNodeCreate(x);
ListNode* next = phead->next;
phead->next = newnode;
newnode->prev = phead;
newnode->next = next;
next->prev = newnode;
}
头删：首先要判断传过来的是节点是否是头节点，不能把头节点删了，然后我们定义一个指针cur记录第一个节点，指针next记录第二个节点
让头节点phead的next指向next，next的prev指向phead，在free释放掉cur指向的节点
void ListNodePopFront(ListNode* phead)
{
assert(phead && phead->next != phead); //不能把头节点删了
ListNode* cur = phead->next;
ListNode* next = cur->next;
phead->next = next;
next->prev = phead;
free(cur);
}
尾插：我们上面的单链表尾插需要遍历链表找到尾节点，而循环链表它的头节点phead的prev指向的就是尾节点，先定义一个tail记录尾节点，先让newnode和头节点phead链接，再让newn和tail链接，完成尾插
void ListNodePushBack(ListNode* phead, DataType x)
{
assert(phead);
//创建新节点
ListNode* newnode = ListNodeCreate(x);
ListNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
尾删：断言传过来的是节点是否是头节点，由于要删除尾节点，那我们定义一个prev记录尾节点的前一个节点 ，然后将prev的next指向头节点phead，phead的prev指向prev所在节点，完成尾删
void ListNodePopBack(ListNode* phead)
{
assert(phead && phead->next != phead);//不能把头节点删了
//找到尾节点
ListNode* tail = phead->prev;
ListNode* prev = tail->prev;
prev->next = phead;
phead->prev = prev;
free(tail);
}
寻找x所在节点位置：
定义指针cur遍历链表，比较data与x是否相等，由于这是循环链表，所以当cur再次指向phead时已经将链表遍历一遍了，跳出循环后就返回NULL
ListNode* ListNodeFind(ListNode* phead, DataType x)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
在pos位置前插入节点
首先断言pos不为空，创建新节点newnode，在定义一个posprev记录pos的前一个节点，然后形成链接关系，这里不在赘述了，当我们定义了这个函数后就可以代替头插尾插了，头插pos的位置为phead->next,尾插pos位置为phead
void ListNodeInsert(ListNode* pos, DataType x)
{
assert(pos);
ListNode* newnode = ListNodeCreate(x);
ListNode* posprev = pos->prev;
posprev->next = newnode;
newnode->prev = posprev;
newnode->next = pos;
pos->prev = newnode;
}
pos位置删除数据
如果pos->next == pos表是此是只有头节点，没有存储其他节点，所以断言一下，不能把头节点删了，定义两个指针记录pos前一个节点和后一个节点，方便删除pos位置节点，同样当我们定义了这个函数就可以代替头删和尾删了
void ListNodeErase(ListNode* pos)
{
assert(pos->next != pos);
ListNode* prev = pos->prev;
ListNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
}
销毁链表
通过cur和next两个指针遍历并删除链表，由于我们传的是一级指针，是plist的形参，形参的改变不会影响实参，所以要在主函数里面将plist头指针置空，避免形成野指针
void ListNodeDestroy(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}
最后测试一下双链表
#include "List.h"
void Test2()
{
ListNode* plist = ListNodeInit();
ListNodePushFront(plist, 1);
ListNodePushFront(plist, 2);
ListNodePushFront(plist, 3);
ListNodePrint(plist);
ListNodePopFront(plist);
ListNodePrint(plist);
ListNode* pos = ListNodeFind(plist, 2);
if (pos != NULL)
ListNodeInsert(pos, 4);
ListNodePrint(plist);
pos = ListNodeFind(plist, 2);
if (pos != NULL)
ListNodeErase(pos);
ListNodePrint(plist);
ListNodeDestroy(plist);
plist = NULL;
}
int main()
{
//Test1();
Test2();
return 0;
}
实现完带头双向循环链表是不是觉得比单链表要简单多了。
顺序表与链表的优缺点
我们上节介绍了线性表中的顺序表，这节介绍了链表，顺序表和链表是相辅相成的两个结构，自己的优点是对方的缺点，我们下面讨论的是顺序表与带头双向循环链表的优缺点
顺序表：
优点：由于是连续的空间，支持随机访问
缺点：1.空间不够时需要扩容的，而扩容是需要付出代价的，为避免频繁扩容，我们一般是扩2倍，这也从一定程度上导致空间浪费，且原空间不够扩容的话，需要将原数据全部迁移再扩容，大大降低了效率。
2.顺序表是从头开始且连续存储数据的，而当我们要在头部或是中间位置插入删除数据时，需要挪动数据，也大大降低了效率。
于是针对顺序表的缺陷设计出了链表
带头双向循环链表：
优点：1、可以任意插入删除数据，不需要挪动数据
2.按需申请空间，再释放空间，不存在空间浪费缺点：1、每存一个数据，都要存前后指针（当然也没太大的问题）
2、每存一个数据就要malloc动态开辟空间 3、不支持随即访问（硬伤），意味着一些排序，二分查找等在这种结构不适用
针对随机访问的问题，顺序表一白遮百丑，链表一黑毁所有。
同时顺序表的连续存储相比于链表的随即存储在读取速度上也占优势，这就涉及硬件方面的知识了，这里就不赘述了。
单链表源码
SList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DataType;
typedef struct SingleListNode
{
DataType data;
struct SingleListNode* next;
}SListNode;
//打印链表
void SListNodePrint(SListNode* phead);
//链表尾插
void SListNodepushback(SListNode** pphead, DataType x);
//链表头插
void SListNodepushfront(SListNode** pphead, DataType x);
//链表尾删
void SListNodepopback(SListNode** pphead);
//链表头删
void SListNodepopfront(SListNode** pphead);
//寻找链表中数据所在的位置
SListNode* SListNodeFind(SListNode* phead, DataType x);
//链表指定pos位置前插入
void SListNodeInsert(SListNode** pphead, SListNode* pos, DataType x);
//链表指定pos位置后插入
void SListNodeInsertAfter(SListNode* pos, DataType x);
//链表指定pos位置删除数据
void SListNodeErase(SListNode** pphead, SListNode* pos);
//链表销毁
void SListNodeDestroy(SListNode** pphead);
SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
//创建新节点
SListNode* Creatnode(DataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SListNodePrint(SListNode* phead)
{
while (phead != NULL)
{
printf("%d->", phead->data);
phead = phead->next;
}
printf("NULL\n");
}
void SListNodepushback(SListNode** pphead, DataType x)
{
assert(pphead);
SListNode* newnode = Creatnode(x);
if (*pphead == NULL)
*pphead = newnode;
else
{
SListNode* ret = *pphead;
while (ret->next != NULL)
{
ret = ret->next;
}
ret->next = newnode;
}
}
void SListNodepushfront(SListNode** pphead, DataType x)
{
assert(pphead);
SListNode* newnode = Creatnode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SListNodepopback(SListNode** pphead)
{
//链表为空不能删除
assert(*pphead != NULL);
//只有一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//两个及以上节点
else
{
SListNode* ret = *pphead;
while (ret->next->next != NULL)
{
ret = ret->next;
}
free(ret->next);
ret->next = NULL;
}
}
void SListNodepopfront(SListNode** pphead)
{
//链表为空不能删除
assert(*pphead != NULL);
SListNode* next = (*pphead)->next;
free(*pphead);
*pphead = NULL;
*pphead = next;
}
SListNode* SListNodeFind(SListNode* phead, DataType x)
{
assert(phead != NULL);
SListNode* cur = phead;
//只能返回最开始找到的
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}
//从pos位置前插入
//void ChainListInsert(CListNode** pphead, CListNode* pos, DataType x)
//{
// assert(pphead && pos);
//
// CListNode* newnode = Creatnode(x);
// //直接头插
// if (*pphead == pos)
// {
// newnode->next = *pphead;
// *pphead = newnode;
// }
// else
// {
// CListNode* posPrev = *pphead;
// //找pos的前一个节点
// while (posPrev->next != pos)
// {
// posPrev = posPrev->next;
// }
// newnode->next=posPrev->next;
// posPrev->next = newnode;
// }
//}
//从pos后插入
void SListNodeInsertAfter(SListNode* pos, DataType x)
{
assert(pos);
SListNode* newnode = Creatnode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SListNodeErase(SListNode**pphead, SListNode* pos)
{
assert(*pphead && pos);
//判断是否为头删
if (*pphead == pos)
{
*pphead = pos->next;
free(pos);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
void SListNodeDestroy(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
while (cur)
{
SListNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void Test1()
{
SListNode* head = NULL;
SListNodepushback(&head, 1);
SListNodepushback(&head, 2);
SListNodepushfront(&head, 4);
SListNodepushfront(&head, 5);
SListNodePrint(head);
}
void Test2()
{
SListNode* head = NULL;
SListNodepushback(&head, 1);
SListNodepushback(&head, 2);
SListNodepushback(&head, 3);
SListNodepopback(&head);
SListNodepopback(&head);
SListNodePrint(head);
}
void Test3()
{
SListNode* head = NULL;
SListNodepushback(&head, 1);
SListNodepushback(&head, 2);
SListNodepushback(&head, 3);
SListNodepushback(&head, 4);
SListNodepushback(&head, 5);
/*SListNode* pos = SListNodeFind(head, 5);
int i = 1;
while (pos != NULL)
{
printf("这是第%d个节点%p->%d\n", i++, pos, pos->data);
if (pos->next == NULL)
return;
pos = SListNodeFind(pos->next, 5);
}*/
SListNode* pos = SListNodeFind(head, 5);
if (pos != NULL)
{
SListNodeInsertAfter(pos, 10);
}
SListNodePrint(head);
}
int main()
{
Test1();
Test2();
Test3();
return 0;
}
带头双向循环链表源码
List.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DataType;
typedef struct ListNode
{
DataType data;
struct ListNode* next; //存放下一个节点
struct ListNode* prev; //存放前一个节点
}ListNode;
//链表初始化，创建哨兵位头节点
ListNode* ListNodeInit();
//链表打印
void ListNodePrint(ListNode* phead);
//链表尾插
void ListNodePushBack(ListNode* phead, DataType x);
//链表尾删
void ListNodePopBack(ListNode* phead);
//链表头插
void ListNodePushFront(ListNode* phead, DataType x);
//链表头删
void ListNodePopFront(ListNode* phead);
//链表查找
ListNode* ListNodeFind(ListNode* phead, DataType x);
//链表指定pos位置前插入数据
void ListNodeInsert(ListNode* pos, DataType x);
//链表指定pos位置删除数据
void ListNodeErase(ListNode* pos);
//销毁链表
void ListNodeDestroy(ListNode* phead);
** List.c**
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
//创建新节点
ListNode* ListNodeCreate(DataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
ListNode* ListNodeInit()
{
//创建哨兵位的头节点，方便尾插，对链表操作时也不用传二级指针了
struct ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
phead->next = phead;
phead->prev = phead;
return phead;
}
void ListNodePrint(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
void ListNodePushBack(ListNode* phead, DataType x)
{
assert(phead);
//创建新节点
ListNode* newnode = ListNodeCreate(x);
ListNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
void ListNodePopBack(ListNode* phead)
{
assert(phead && phead->next != phead);//不能把头节点删了
//找到尾节点
ListNode* tail = phead->prev;
ListNode* prev = tail->prev;
prev->next = phead;
phead->prev = prev;
free(tail);
}
void ListNodePushFront(ListNode* phead, DataType x)
{
assert(phead);
ListNode* newnode = ListNodeCreate(x);
ListNode* next = phead->next;
phead->next = newnode;
newnode->prev = phead;
newnode->next = next;
next->prev = newnode;
}
void ListNodePopFront(ListNode* phead)
{
assert(phead && phead->next != phead); //不能把头节点删了
ListNode* cur = phead->next;
ListNode* next = cur->next;
phead->next = next;
next->prev = phead;
free(cur);
}
ListNode* ListNodeFind(ListNode* phead, DataType x)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
void ListNodeInsert(ListNode* pos, DataType x)
{
assert(pos);
ListNode* newnode = ListNodeCreate(x);
ListNode* posprev = pos->prev;
posprev->next = newnode;
newnode->prev = posprev;
newnode->next = pos;
pos->prev = newnode;
}
void ListNodeErase(ListNode* pos)
{
assert(pos->next != pos);
ListNode* prev = pos->prev;
ListNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
}
void ListNodeDestroy(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}
Test.c
#include "List.h"
void Test1()
{
ListNode* plist = ListNodeInit();
ListNodePushBack(plist, 1);
ListNodePushBack(plist, 2);
ListNodePushBack(plist, 3);
ListNodePushBack(plist, 4);
ListNodePushBack(plist, 5);
ListNodePrint(plist);
ListNodePopBack(plist);
ListNodePopBack(plist);
ListNodePopBack(plist);
ListNodePopBack(plist);
ListNodePrint(plist);
}
void Test2()
{
ListNode* plist = ListNodeInit();
ListNodePushFront(plist, 1);
ListNodePushFront(plist, 2);
ListNodePushFront(plist, 3);
ListNodePushFront(plist, 4);
ListNodePushFront(plist, 5);
ListNodePrint(plist);
ListNodePopFront(plist);
ListNodePopFront(plist);
ListNodePrint(plist);
ListNode* pos = ListNodeFind(plist, 3);
if (pos != NULL)
ListNodeInsert(pos, 4);
ListNodePrint(plist);
pos = ListNodeFind(plist, 2);
if (pos != NULL)
ListNodeErase(pos);
ListNodePrint(plist);
ListNodeDestroy(plist);
plist = NULL;
}
int main()
{
//Test1();
Test2();
return 0;
}
不是看到希望才去坚持，而是坚持了才看到希望，敬每一位努力奋斗的你和学习编程的你。希望我的文章能对你有所帮助。欢迎👍点赞 ，📝评论，🌟关注，⭐️收藏
版权归原作者 想学好编程的小菜鸟 所有， 如有侵权，请联系我们删除。