当前位置：首页 > news >正文

链表的分类以及双向链表的实现

news 2024/12/4 12:45:51

1.链表的分类

在这里插入图片描述

1.1单向链表与双向链表的区别

单向链表只能从头结点遍历到尾结点。
双向链表不仅能从头结点遍历到尾结点，还能从尾结点遍历到头结点。
在这里插入图片描述

1.2带头链表与不带头链表的区别

在这里插入图片描述

1.3循环链表与不循环链表的区别（也称为带环链表与不带环链表）

不循环链表中，尾结点的next指针的值为NULL
循环链表中，尾结点的next指针可以指向该链表中的任意一个结点，包括尾结点。
在这里插入图片描述

2.双向链表中需要注意的点

2.1：双向链表的全称为双向带头循环的链表，单向链表的全称为单向不带头不循环的链表。

在这里插入图片描述

2.2双向链表中结点的结构

typedef int DataType;
typedef struct ListNode
{DataType data;//存储DataType类型的数据struct ListNode* next;//存储后一个结点的地址struct ListNode* prev;//存储前一个结点的地址
}LN;

2.3区分单链表（单向不带头不循环链表）与双向链表（双向带头循环链表）为空表的情况

2.3.1：若单链表为空表，表示单链表中没有结点（即没有存储有效数据），即指向第一个结点的指针为空指针

2.3.2：若双向链表为空表，并不是表示双向链表中没有结点，而是只有一个头结点，且头结点中存储一个无效数据，并且头结点中的两个指针均指向头结点（要满足循环）。故双向链表为空表时，并不是指链表中一个结点也没有，而是指链表中没有存储有效数据。

在这里插入图片描述

2.4常使用的两种链表

虽然链表的分类有很多，但是最常用的只有单链表(单向不带头不循环链表)与双向链表(双向带头循环链表)。

1.单链表：结构简单，一般不会用来存数据，实际中更多的是作为其他数据结构的子结构，如哈希桶、图的邻接表等等，另外单链表在笔试面试中考察的较多。

2.双向链表：结构复杂，一般用于单独存储数据，实际中使用的链表数据结构，通常都是双向链表。虽然双向链表的结构复杂，但是该结构的优势明显，另外该结构也容易实现。

2.5顺序表与单链表的比较

在这里插入图片描述

3.双向链表的实现

a.List.h文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int DataType;
//定义双向链表结点的结构
typedef struct ListNode
{DataType data;struct ListNode* next;//存储下一个结点的地址struct ListNode* prev;//存储上一个结点的地址
}ListNode;//申请新结点的空间,并返回该空间的地址
ListNode* ListBuyNode(DataType x);//双向链表的初始化(初始情况下，双向链表中只有一个头结点，不存储任何有效的数据)
void ListInit(ListNode** pphead);//打印双向链表(打印存储的有效数据)
void ListPrint(ListNode* phead);//向双向链表尾部插入结点
void ListPushBack(ListNode *phead, DataType x);//向双向链表尾部插入结点时，不会改变头结点的地址，因此传头结点的地址即可//向双向链表头部插结点(注意:不是插在头结点之前，而是插在头结点后面。)
//因为头结点中存储的是无效数据，第一个存储有效数据的结点是头结点后面的结点
void ListPushFront(ListNode* phead, DataType x);//向双向链表的头部插入结点时，不会改变头结点的地址，因此传头结点的地址即可//判断双向链表是否为空表
//若双向链表中只有一个头结点，头结点中没有存储有效数据，且头结点中的两个指针均指向头结点(要满足循环))，则双向链表为空表bool ListEmpty(ListNode* phead);//删除尾部的结点(删除尾部的结点时，头结点的地址不会发生变化，因此传头结点的地址即可)
void ListPopBack(ListNode* phead);//删除第一个存储有效数据的结点(删除该结点时，头结点的地址不会变化，因此传头结点的地址即可)
//为什么不是删头结点呢？因为如果把头结点删除了，双向循环链表就不带头了，就不是双向循环链表了
void ListPopFront(ListNode* phead);//查找存储数据为x的结点，返回该结点的地址
ListNode* ListFind(ListNode* phead, DataType x);//删除指定的结点(pos指向的结点)
//头结点是不能删的，不然就不是双向链表了
void ListErase(ListNode * pos);//在指定的结点(pos指向的结点)后插入结点
void ListInsert(ListNode* pos, DataType x);//双向链表的销毁(包括头结点也要销毁)
void ListDestory(ListNode** pphead);//链表销毁后，头结点的地址就变成了NULL，因此要传指向头结点的指针的地址/*
容易发现除了双向链表的初始化与销毁的形参是二级指针外，其余的函数的形参都是一级指针
那么能不能将初始化与销毁这两个函数的形参做一些修改呢？答案是可以的，看下面修改后的函数
*///双向链表的初始化(直接申请一个头结点的空间，然后返回空间的地址)
ListNode* ListInit2();//双向链表的销毁的第二种方法
void ListDestory2(ListNode* phead);

b.List.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//申请新结点的空间
ListNode* ListBuyNode(DataType x)
{ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));assert(NewNode);NewNode->data = x;NewNode->next = NewNode->prev = NewNode;/*这种写法便于创建头结点，当双向链表为空表时，头结点中的两个指针均指向自己(链表满足循环)如果是下面这种写法，创建头结点时，链表无法循环，就不是双向链表了NewNode->next = NewNode->prev =NULL,*/return NewNode;
}//双向链表的初始化(初始情况下，双向链表中只有一个头结点，不存储任何有效的数据)
void ListInit(ListNode** pphead)
{assert(pphead);//双向链表未初始化之前，链表中没有头结点，因此指向头结点的指针的值为NULL，但指向头结点的指针的地址不是NULL//pphead:指向头结点的指针的地址//*pphead:头结点的地址*pphead = ListBuyNode(INT_MAX);//用INT_MAX表示头结点中存储的是无效数据
}//打印双向链表(打印存储的有效数据)
void ListPrint(ListNode* phead)
{assert(phead);//双向链表中，头结点的地址不可能是NULLif (phead->next == phead)//若双向链表为空表(只有一个头结点，头结点中存储的是无效数据，且头结点中的两个指针均指向头结点){printf("双向链表为空表\n");return;}ListNode* pcur = phead->next;//pcur指向第一个存储有效数据的结点while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}//向双向链表尾部插入结点
void ListPushBack(ListNode* phead, DataType x)
{assert(phead);//双向链表中，头结点的地址不可能是NULL//申请新结点的空间ListNode* NewNode = ListBuyNode(x);//先修改新结点中指针的指向NewNode->prev = phead->prev;NewNode->next = phead;//再修改原链表的尾结点中next指针的指向phead->prev->next = NewNode;//最后修改头结点中的prev指针的指向phead->prev = NewNode;
}//向双向链表头部插结点(注意:不是插在头结点之前，而是插在头结点后面。)
void ListPushFront(ListNode* phead, DataType x)
{assert(phead);//双向链表中，头结点的地址不可能是NULL//申请新结点的空间ListNode* NewNode = ListBuyNode(x);//先修改新结点中指针的指向NewNode->next = phead->next;NewNode->prev = phead;//再改变原链表中第一个存储有效数据的结点中prev指针的指向phead->next->prev = NewNode;//最后改变头结点中next指针的指向phead->next = NewNode;
}//判断双向链表是否为空表(若双向链表中只有一个头结点，头结点中没有存储有效数据，且头结点中的两个指针均指向头结点(要满足循环))
bool ListEmpty(ListNode* phead)
{assert(phead);//双向链表中，头结点的地址不可能是NULLreturn phead->next == phead;//若表达式为真(即双向链表是空表)，返回true,否则返回false
}//删除尾部的结点
void ListPopBack(ListNode* phead)
{assert(phead);//双向链表中，头结点的地址不可能是NULLassert(!ListEmpty(phead));//若双向链表为空表则不能删除结点//删除结点时，会影响头结点的prev指针，以及尾结点的前一个结点的next指针ListNode* ptail = phead->prev;//ptail指向的是尾结点ListNode* prev = ptail->prev;//定义prev指针,指向尾结点的前一个结点//等号的左边的prev是该函数中是定义的变量，它的作用域是该函数；而右边的prev是结构体中成员变量（只有访问这个结构体时，才会用到prev），它的作用域是这个结构体。两个prev的作用域不同，因此两者不冲突。//先修改原链表中，尾结点的前一个结点的next指针prev->next = phead;//再修改头结点的prev指针phead->prev = prev;//最后释放原链表中尾结点的空间free(ptail);ptail = NULL;
}//删除第一个存储有效数据的结点
void ListPopFront(ListNode* phead)
{assert(phead);//双向链表中，头结点的地址不可能是NULLassert(!ListEmpty(phead));//若双向链表为空表则不能删除结点//删除结点时，会影响头结点中的next指针，以及存储第一个有效数据的结点的后一个结点中的prev指针ListNode* first = phead->next;//first指向第一个存储有效数据的结点ListNode* Next = first->next;//Next指向存储第一个有效数据的结点的后一个结点//先修改存储第一个有效数据的结点的后一个结点中prev指针的指向Next->prev = phead;//再修改头结点中的next指针phead->next = Next;//最后释放原链表中存储第一个有效数据的结点的空间free(first);first = NULL;
}//查找存储数据为x的结点，返回该结点的地址
ListNode* ListFind(ListNode* phead, DataType x)
{assert(phead);//双向链表中，头结点的地址不可能是NULL//从第一个存储有效数据的结点开始往后找ListNode* pcur = phead->next;//pcur指向第一个存储有效数据的结点while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//若将所有存储有效数据的结点都遍历了一遍后，依旧找不到存储x的结点，则返回NULLreturn NULL;
}//删除指定的结点(pos指向的结点)
void ListErase(ListNode* pos)
{assert(pos);//pos指向的结点的地址不可能是NULL//删除结点时，会影响pos指向的结点的前一个结点中的next指针,//                  以及pos指向的后一个结点的prev指针//先修改pos指向的结点的前一个结点中的next指针pos->prev->next = pos->next;//再修改pos指向的后一个结点的prev指针pos->next->prev = pos->prev;//最后释放pos指向的结点的空间free(pos);pos = NULL;
}//在指定的结点(pos指向的结点)后插入结点
void ListInsert(ListNode* pos, DataType x)
{assert(pos);//pos指向的结点的地址不可能是NULL//申请新结点的空间ListNode* NewNode = ListBuyNode(x);//插入结点时，会影响pos指向的结点的next指针，以及原链表中pos指向的结点的后一个结点的prev指针ListNode* Next = pos->next;//Next指向原链表中，pos指向的结点的下一个结点//先修改新结点中指针的指向NewNode->prev = pos;NewNode->next = Next;//再修改pos指向的结点的next指针pos->next = NewNode;//再修改原链表中pos指向的结点的后一个结点的prev指针Next->prev = NewNode;
}//双向链表的销毁(包括头结点也要销毁)
void ListDestory(ListNode** pphead)
{//pphead表示指向头结点的指针的地址//*pphead表示头结点的地址//若pphead==NULL，则*pphead就无法找到头结点的地址了//双向链表中，头结点的地址不可能为NULLassert(pphead && *pphead);ListNode* pcur = (*pphead)->next;//pcur指向第一个存储有效数据的结点//先回收存储有效数据的结点的空间while (pcur != *pphead){ListNode* Next = pcur->next;//Next指向pcur指向的结点的下一个结点free(pcur);pcur = Next;}//再回收头结点的空间free(*pphead);*pphead = pcur = NULL;
}//双向链表的初始化(直接申请一个头结点的空间，然后返回空间的地址)
ListNode* ListInit2()
{ListNode* phead = ListBuyNode(INT_MAX);//INT_MAX表示头结点中存储的是无效数据assert(phead);return phead;
}//双向链表的销毁的第二种方法
void ListDestory2(ListNode* phead)
{assert(phead);//双向链表中，头结点的地址不可能为NULLListNode* pcur = phead->next;//pcur指向第一个存储有效数据的结点//先回收存储有效数据的结点的空间while (pcur != phead){ListNode* Next = pcur->next;free(pcur);pcur = Next;}//再回收头结点的空间free(phead);/*头结点的空间虽然被回收了，但由于形参接收的是实参的值，不是实参的地址，形参的改变无法影响实参因此实参(plist)依然是指向头结点，plist变成了野指针，需要手动将plist置为NULL*/pcur = phead = NULL;
}

test.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//测试双向链表的初始化
void test1(ListNode **pplist)
{ListInit(pplist);
}//测试向双向链表中尾插结点
void test2(ListNode *phead)
{ListPushBack(phead, 1);ListPushBack(phead, 2);ListPushBack(phead, 3);ListPushBack(phead, 4);ListPrint(phead);
}//测试向双向链表中头插结点
void test3(ListNode *phead)
{ListPushFront(phead, 4);ListPushFront(phead, 3);ListPushFront(phead, 2);ListPushFront(phead, 1);ListPrint(phead);
}//测试删除尾结点
void test4(ListNode* phead)
{ListPushBack(phead, 1);ListPushBack(phead, 2);ListPrint(phead);//1->2->ListPopBack(phead);ListPrint(phead);//1->ListPopBack(phead);ListPrint(phead);//空表//ListPopBack(phead);空表不能删除结点，会报错
}//测试删除第一个存储有效数据的结点
void test5(ListNode* phead)
{ListPushBack(phead, 1);ListPushBack(phead, 2);ListPrint(phead);//1->2->ListPopFront(phead);ListPrint(phead);//2->ListPopFront(phead);ListPrint(phead);//此时双向链表为空表
}//测试查找存储数据为x的结点
void test6(ListNode *phead)
{ListPushBack(phead, 1);ListPushBack(phead, 2);ListPushBack(phead, 3);ListPushBack(phead, 4);ListPrint(phead);//1->2->3->4->ListNode* find = ListFind(phead, 2);if (find != NULL){printf("找到了\n");}else{printf("找不到\n");}}//测试删除指定的结点(pos指向的结点)
void test7(ListNode* phead)
{ListPushBack(phead, 1);ListPushBack(phead, 2);ListPushBack(phead, 3);ListPushBack(phead, 4);ListPrint(phead);//1->2->3->4->ListNode* find = ListFind(phead, 1);ListErase(find);ListPrint(phead);//2->3->4->}//测试在指定的结点(pos指向的结点)后插入结点
void test8(ListNode* phead)
{ListPushBack(phead, 1);ListPushBack(phead, 2);ListPushBack(phead, 3);ListPushBack(phead, 4);ListPrint(phead);//1->2->3->4->ListNode* find = ListFind(phead, 4);ListInsert(find, 5);//1->2->3->4->5->ListPrint(phead);
}//测试摧毁双向链表
void test9(ListNode** pphead)
{ListPushBack(*pphead, 1);ListPushBack(*pphead, 2);ListPrint(*pphead);//1->2->ListDestory(pphead);}int main()
{ListNode * plist = NULL;//plist表示指向头结点的指针//测试双向链表的初始化test1(&plist);//测试向双向链表中尾插结点//test2(plist);//测试向双向链表中头插结点//test3(plist);//测试删除尾结点//test4(plist);//测试删除第一个存储有效数据的结点//test5(plist);//测试查找存储数据为x的结点//test6(plist);//测试删除指定的结点(pos指向的结点)//test7(plist);//测试在指定的结点(pos指向的结点)后插入结点//test8(plist);//测试销毁双向链表//test9(&plist);//测试销毁双向链表的第二种方法ListDestory2(plist);//虽然链表被销毁了，但是plist依然是指向原来链表中的头结点，变成了野指针，需要手动将plist置为NULLplist = NULL;return 0;
}