【10月更文挑战第23天】
• 头部、中间位置的插入删除，时间复杂度变成O(1)
• 减少或者避免增容带来的性能消耗
• 避免空间浪费，要几个空间就给几个空间
链表是否能解决这些问题呢？
链表也是一个统称，链表是线性表的一种
逻辑结构：线性
物理结构不一定是线性的
链表的结构与概念
概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/结点”
我们的理解就是链表是由一个个节点组成的
节点之间的地址不一定是连续的
节点有两个部分组成：数据+指向下一个节点的指针
单链表 ：SList single单身的
//节点的结构
typedef int LTDataType;//数据类型不一定是int类型
//方便我们后面一键替换
struct ListNode
{
LTDataType data;
struct ListNode* next;//下个节点的指针，指向的类型是struct ListNode
};
在链表中没有增容的概念，直接插入新的数据，申请一个节点大小的空间就可以了，用malloc就行了
如果链表为空的话，pilist指向的是第一个结点，因为链表为空，那么plist指向的就是NULL
单链表的实现
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;//pcur指向的是第一个节点的地址
while (pcur)//最后的时候pcur为NULL，我们就跳出了循环
{
printf("%d->", pcur->data);
pcur = pcur->next;//next指针保存的是下个节点的地址
}
printf("NULL\n");
}
//申请新节点
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));//申请一个新节点
//一个节点的大小就是结构体的大小
if (node == NULL)
{
perror("malloc fail!");
exit(1);
}
node->data = x;
node->next = NULL;//该节点指向的下一个指针是NULL
return node;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
//不能传空值
assert(pphead);
//pphead---->&plist
//对pphead进行解引用得到的就是plist
SLTNode* newnode = SLTBuyNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//尾节点-->新节点
//phead指向的是第一个节点，我们创建一个指针pcur,pcur指向的是phead
//我们通过pcur来寻找尾节点
//找尾节点
SLTNode* pcur = *pphead;
while (pcur->next != NULL)
//最后一个节点的next是空指针，我们对于这个循环的
{
pcur = pcur->next;//下一个节点的指针
}
//pcur的下个节点我们不让他指向的是空指针，我们让他指向的是新的节点
pcur->next = newnode;
}
}
//头部增加数据
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//申请一个新节点
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pphead;//让新的节点的指针指向之前的头节点
*pphead = newnode;//原先是*pphead指向的头节点，现在头节点发生变化，我们让头节点变化为我们刚刚创建的新节点
}
//尾部删除数据
void SLTPopBack(SLTNode** pphead)
{
//链表为空：不能进行删除
assert(pphead && *pphead);//pphead就是说传上来的数据不能为空，*pphead就是说明链表不能为空
//处理只有一个节点的情况：要删除的就是头节点,当前指针的next为NULL
if ((*pphead)->next == NULL)//就说明只有一个节点
//因为箭头的优先级高，所以我们要将*pphead进行括起来
{
free(*pphead);//我们直接将这个节点释放
*pphead = NULL;
}
else//不止一个节点
{
SLTNode* ptail = *pphead;//头节点 *pphead就是plist
SLTNode* prev = NULL;//前节点为空
//找尾节点
while (ptail->next != NULL)
{
prev = ptail;//prev指向ptail的前一个节点，在经历下面的代码之后
ptail = ptail->next;
//我们让ptail指向下一个节点的之前，我们将现在的prev赋值为现在的ptail
//等ptail指向下一个节点之后，那么prev就是一直指向的是前一个节点了
}
//假设我们有4个节点，此时的prev指向的是第三个节点，ptail指向的是最后一个节点
//我们现在为了删除尾节点，我们将prev指向的下一个指针变为空指针
prev->next = NULL;
free(ptail);//我们直接将ptail这个指针进行释放，因为这个指针指向的节点就是我们要删除的尾节点
ptail = NULL;
}
}
//头部删除数据
void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);//参数不能传空，链表不能为空
SLTNode* next = (*pphead)->next;//将下一个节点存储起来
free(*pphead);//直接将第一个节点进行释放
*pphead = next;//因为我们之前将下一个节点存储起来了
//现在我们将头节点删除了，那么新的头节点就是之前的下一个节点
//那么我们将头节点的地址赋值上之前存储的下一个节点的地址
//我们还能先改头结点，再进行释放
/*
SLTNode*del=*pphead;
*pphead=(*pphead)->next;//将头结点改变了
*
free(del);//直接将头结点释放掉
dal=NULL;
*/
}
//查抄
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//返回的是一个节点的指针
{
assert(phead);
SLTNode* pcur = phead;//重新定义一个指针
while (pcur!=NULL)
{
if (pcur->data == x)//找到了我们要找的节点了
{
return pcur;
}
pcur = pcur->next;
}
//跳出循环就说明没有我们要找的节点
return NULL;
}
//在指定位置之前插⼊数据（传二级指针，就说明我们要将链表中数据进行改变）
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);//链表是可以为空的，因为我们是插入数据不是删除数据
assert(pos);
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
//申请一个新的节点
SLTNode* newnode = SLTBuyNode(x);
//找prev:pos的前一个节点
SLTNode* prev = *pphead;//初始定义为第一个节点
while (prev->next != pos)//prev的下个节点不是pos我们就一直进行循环
//直到我们的下个节点是pos,那么我们的prev就是pos的前一个节点了
//我们的目的就达到了
{
prev = prev->next;
}
//此时已经是循环之外了，那么我们的prev已经是pos的前一个节点了
//我们在之前已经找到了prev和pos的位置，并且我们已经创建好了新的节点
//现在我们将新节点放到两个节点中间，就实现了指定位置插入了
newnode->next = pos;
prev->next = newnode;
}
}
//在指定位置之后插⼊数据
//我们就不用找pos前面的指针了，
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
//申请一个新的节点
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//删除pos结点 pos前一个节点和后一个节点受到影响
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && *pphead);
assert(pos);
//头删特殊处理
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;//创建一个指针指向头结点
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;//pos前的节点指向pos的下一个节点
free(pos);
pos = NULL;
}
}
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{
//我们需要知道三个节点，pos和pos后面要删除的节点以及删除节点后面的节点
assert(pos&&pos->next);//pos和pos的下个节点都不能为空
//pos pos->next pos->next->nxet
SLTNode* del = pos->next;//将pos下个节点指针保存下来
//我们需要让pos后面结点指向的要删除的节点后面的节点
//我们要让pos节点后面是要删除的节点后面那个节点
pos->next = pos->next->next;
free(del);
del = NULL;
}
//销毁链表
void SListDestroy(SLTNode** pphead)//传址
{
//遍历链表找到每个节点
//我们不能直接将第一个节点释放，我们要先将第二个节点进行保存
//如果提前将第一个节点删除了我们就找不到后面的节点了
assert(pphead && *pphead);//不能传空，不能传空链表
//创建一个指针遍历链表
SLTNode* pcur = *pphead;//先指向第一个节点
while (pcur != NULL)
{
SLTNode* next = pcur->next;//将pcur指向的下个节点进行保存
free(pcur);
pcur = next;
}
//跳出循环的时候,pcur已经指向的是NULL
*pphead = NULL;
}
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义链表（结点）的结构
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;//表示的是单链表节点
//链表的打印
void SLTPrint(SLTNode* phead); //将第一个节点传过去，我们命名为头节点
//尾部增加数据
void SLTPushBack(SLTNode* *pphead, SLTDataType x);
//头部增加数据
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾部删除数据
void SLTPopBack(SLTNode** pphead);
//头部删除数据
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//返回的是一个节点的指针
//在指定位置之前插⼊数据（传二级指针，就说明我们要将链表中数据进行改变）(时间复杂度是O(N))
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插⼊数据(时间复杂度是O(1))
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDestroy(SLTNode** pphead);
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
//创建一个链表，并打印链表
void creatSList()
{
//链表是由一个个节点组成的 SLTNode*是结构体指针
SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));//申请一个节点大小的空间就行了
node1->data = 1;//对节点内的数据进行初始化
SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));//申请一个节点大小的空间就行了
node2->data = 2;
SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));//申请一个节点大小的空间就行了
node3->data = 3;
SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));//申请一个节点大小的空间就行了
node4->data = 4;
/*
我们申请了四个节点，每个节点里面都有一个date和下一个节点的指针
*/
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;//最后一节点的指针指向的是NULL
//打印链表
//将第一个节点的地址作为参数传递过去
SLTPrint(node1);
}
void SListTest01()
{
SLTNode* plist = NULL;
//SLTPushBack(&plist, 1);//因为phead是一级指针，所以我们在接受的时候我们要用二级指针进行接收
//SLTPrint(plist);
//SLTPushBack(&plist, 2);
//SLTPushBack(&plist, 3);
//SLTPrint(plist);
//为什么打印出来的都是NULL
//phead发生改变，但是plist没有发生改变，形参改变，但是实参没有改变，那么我们应该进行传址操作
/*
第一个节点：*plist
指向第一个节点的指针：plist
指向第一个节点的指针的地址：&plist----->pphead*/
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist);//期望结果：4->3->2->1->NULL
//尾删
/*SLTPopBack(&plist);
SLTPrint(plist);*/
/*打印出来的结果就是
4->3->2->1->NULL
4->3->2->NULL
*/
/*SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);*/
/*
当链表还只剩下一个节点的时候我们要进行处理了，因为剩一个节点的时候我们没有前置节点了
*/
//进行处理之后我们得到的结果就是这样的
/*
4->3->2->1->NULL
4->3->2->NULL
4->3->NULL
4->NULL
NULL
*/
//如果我们进行第五次的删除的操作的话，就会报错了Assertion failed: pphead && *pphead, file
/*SLTPopFront(&plist);
SLTPrint(plist);*/
//查找节点
SLTNode* find=SLTFind(plist,2 );
/*if (find == NULL)
{
printf("没有找到\n");
}
else
{`
printf("找到了\n");
}*/
//SLTInsert(&plist, find, 11);//在3之前插入11
////期望结果就是4->11->3->2->1->NULL
//SLTPrint(plist);
/*我们将要查找的数字改为4，我们在4之前插入数据，但是出现了报错
* 那为什么会报错呢？
因为此时的pos是头节点，前面是没有节点的 ，但是我们一开始是将prev定义为第一个节点的，
我们一直满足循环的条件，一直进行循环，那么代码中的while就成了一个死循环
所以我们要对着这种情况进行特殊处理的
我们直接调用头插函数
*/
/*SLTInsertAfter(find, 11);
SLTPrint(plist);*/
//SLTErase(&plist, find);
//SLTPrint(plist);//尾删没问题，但是头删有问题
//对于头删，pos是头节点，那么一开始的prev指向的是头结点，一直满足循环
//就一直循环下去了
//所以我们要进行特殊处理下
/*SLTEraseAfter(find);
SLTPrint(plist);*/
SListDestroy(&plist);
SLTPrint(plist);
}
int main()
{
SListTest01();
//creatSList();
return 0;
}
链表头插的时间复杂度是O(1)
链表头删的时间复杂度是O(1)
链表的分类
虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构：单链表和双向带头循环链表
⽆头单向⾮循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。
带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优势，实现反⽽简单了，后⾯我们代码实现了就知道了。
双向链表我们能从头遍历到尾，我们也能从尾遍历到头
在带头链表中，除了头结点，其他节点都存储有效的数据
头节点的作用是占位子的，叫做“哨兵位”
不带头的链表，从第一个节点开始就是存储的就是有效的数据
带环链表尾节点next不为空
那么单链表的全称是：不带头单向不循环链表
双向链表：带头双向循环链表
双向链表结构相较于单链表来说结构要复杂一些，但是接口的实现要比单链表简单很多
双向链表：带头双向循环链表
双向链表结构相较于单链表来说结构要复杂一些，但是接口的实现要比单链表简单很多
双向链表的节点结构：数据+指向后一个节点的指针+指向前一个节点的指针
尾节点的next指针指向哨兵节点
struct ListNode
{
int data;
struct ListNode* next;//下个节点的指针
struct ListNode* prev;//指向前个节点的指针
};
双向链表为空的情况：只有一个自循环的哨兵位
第一个节点：第一个有效的节点
哨兵位：头节点
新插入的数据的尾节点要指向哨兵位，prev指针要指向前一个节点
我们还要改变新节点之前的节点的next指针的指向，要指向新的节点
我们的哨兵位的prev指针还要指向新的尾节点
那么我们在插入新节点的时候，受到影响的节点有之前的尾节点和哨兵位以及新节点
在存在新的节点的情况下，我们的哨兵位的perv指针指向的是尾节点
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
LTNode* LTBuyNode(LTDataType x)//创建节点
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);//直接退出
}
newnode->data = x;
newnode->next = newnode->prev = newnode;//让这两个指针都指向当前节点的自己，实现循环的效果
return newnode;
}
////初始化
//void LTInit(LTNode** pphead)
//{
// //创建一个头结点（哨兵位）
// *pphead = LTBuyNode(-1);
//}
LTNode* LTInit1()//通过返回值的方法进行初始化，我们要返回一个哨兵位节点的指针
{
LTNode* phead = LTBuyNode(-1);//创建一个指向哨兵位节点的指针
return phead;
}
//销毁 链表的销毁是整个都销毁的
void LTDesTory(LTNode** pphead)
{
//我们需要遍历这个链表，一个个删除
assert(pphead && *pphead);//哨兵位不能为空，参数也不能传一个空链表
LTNode* pcur = (*pphead)->next;//创建一个指针让这个指针指向哨兵位的下个节点,就是第一个有效非节点
//我们从哨兵位的下个节点进行销毁操作
while (pcur != (*pphead))//循环操作一直进行到下个节点不是哨兵位
{
LTNode* Next = pcur->next;//创建一个指针指向pcur的下个节点，进行保存
free(pcur);
pcur = Next;//让pcur这个指针走到Next指向的节点
}
//遇到哨兵位跳出循环了
//销毁哨兵位节点
free(*pphead);
*pphead = NULL;
pcur = NULL;
}
//打印链表
void LTPrint(LTNode* phead)
{
LTNode* pcur = phead->next;//定义一个指针指向哨兵位的next指向的第一个有效的节点
//那么我们就从第一个有效的节点开始打印了
while (pcur != phead)//直到pcur走到哨兵位的位置我们就跳出循环了
{
printf("%d ->", pcur->data);//打印当前节点保存的数据
pcur = pcur->next;//在链表中进行遍历
}
printf("\n");
}
//尾插数据
void LTPushBack(LTNode* phead, LTDataType x)
{
//断言一下，传的参数一定要是有效的参数
assert(phead);
LTNode* newnode = LTBuyNode(x);//创建新的节点
//phead(哨兵位) phead->prev(之前的尾节点) newnode(新插入的节点)
//我们先进行newnode的指针修改，prev指向上个尾节点，next指向哨兵位
newnode->next = phead;
newnode->prev = phead->prev;//之前的尾节点的表示就是phead->prev
//我们再对原先的尾节点进行指针的修改，原先的next指针指向的是哨兵为，那么现在就指向的是新节点了
phead->prev->next = newnode;
//接下来我们对哨兵位进行修改
//哨兵位的prev原本指向的是之前的尾节点，那么我们现在让Prev指新节点
phead->prev = newnode;
//与单链表相比的话，我们不用判断链表是不是空的，我们也不用从头开始遍历来找尾节点
}
//头插数据 哨兵位之后 头插到第一个有效数据的前面
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
//创建新节点
LTNode* newnode = LTBuyNode(x);
//我们先修改插入数据的指针指向，因为newnode的指针指向不会影响原链表
newnode->next = phead->next;//指向原先的第一个节点
newnode->prev = phead;//prev指向哨兵位
//我们头插的节点的next指向的是之前的第一个有效的节点
//prev指向的是哨兵位
//我们还要改变之前的第一个有效节点的Prev指针的指向，让指针指向位头插的新数据
phead->next->prev=newnode;//原先的第一个有效节点的prev指针指向新插入的数据
//还有就是哨兵位的next指针要指向新插入的节点了
phead->next = newnode;
}
//判断链表是否为空
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;//如果哨兵位的next指针指向的是自己，那么就说明这个链表是空链表
}//如果链表为空的话，那么就返回的是true
//尾删数据
void LTPopBack(LTNode* phead)
{
assert(phead);//哨兵位不能为空
assert(!LTEmpty(phead));//判断链表不为空，那么我们就能进行删除节点的操作了
//我们删除节点的话，我们是将哨兵位prev指向的尾节点删掉
//我们将尾节点删掉的话，收到影响的节点有哨兵位和尾删节点的前一个节点
/*
如果将尾节点删掉的话，我们的删掉节点前一个节点的next指针需要指向head'
并且head的prev指针要指向我们的删除节点的前一个节点
我们要创建一个指针指向删除的节点，以便寻找到删除节点的前一个节点
那么我们通过哨兵位就能找到要删除的节点以及他之前的节点
*/
//del是要删除的节点
//del(phead->prev) prev(del->prev) phead
LTNode* del = phead->prev;//创建一个指针指向我们要删除的节点
LTNode* prev = del->prev;//删除节点的前一个节点
//我们先修改prev节点的指针
prev->next = phead;//prev指向了哨兵位
phead->prev = prev;//哨兵位的prev指向了prev，那么现在prev指向的节点就是新的尾节点了
//因为我们之前创建了指针指向我们要删除的节点，那么我们通过这个指针将节点删除
free(del);
del = NULL;
}
//头删数据 删除第一个有效节点
void LTPopFront(LTNode* phead)
{
assert(phead);//哨兵位不能为空
assert(!LTEmpty(phead));//判断链表不为空，那么我们就能进行删除节点的操作了
/*删除第一个节点受到影响的节点有哨兵位以及第二个有效节点
删除第一个节点之后我们哨兵位的next指针要指向第二个节点
第二个节点的prev指针要指向我们的哨兵位*/
LTNode* del = phead->next;//创建一个指针指向我们要删除的节点,就是现在的第一个节点
//我们先改第二个指针的prev指针的指向
del->next->prev = phead;//第二个节点的prev指针要指向哨兵位
phead->next = del->next;//哨兵位的下个节点是第二个节点
free(del);
del = NULL;
}
//查找数据
LTNode* LTFind(LTNode* phead, LTDataType x)//返回值是指向节点的指针
{
//我们需要进行链表的遍历，我们找一圈就行了，再次遇到哨兵位我们直接跳出循环
LTNode* pcur = phead->next;//我们从第一个有效的节点进行遍历
while (pcur != phead)//如果下个节点是哨兵位我们直接跳出循环
{
if (pcur->data == x)
{
return pcur;//找到了我们直接返回这个节点的地址
}
pcur = pcur->next;//没有找到我们继续往后找
}
return NULL;//找不到了，直接返回空
}
//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x)
{
/*
我们先将要插入的节点的next和prev指针进行解决
我们先将newnode 的next和prev处理好
我们是在pos这个位置的后面进行插入节点，那么就会影响到pos和pos->next这两个节点
我们要将pos的next指针进行改变，指向了新的节点以及pos原先后面的节点的prev指向的位置要变为新的节点
*/
//创建一个节点
LTNode* newnode = LTBuyNode(x);
//pos newnode pos->next
//先处理newnode
newnode->next = pos->next;
newnode->prev = pos;
//处理pos后面节点的prev指针的指向
pos->next->prev = newnode;
//改变pos的next指针的指向
pos->next = newnode;
}
//删除指定位置的节点
void LTIErase(LTNode* pos)
{
assert(pos);//传过来的位置不为空
/*删除指定位置的节点
pos前面的节点pos->prev
pos后面的节点pos->next
那么删除pos就出影响到这两个节点了
pos前面指针的节点的next指针就会指向了Pos后面的节点了
pos后面的节点的prev指针就会指向了pos前面的节点了*/
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}
void LTDesTory2(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;//定义一个指针指向哨兵位的下个节点，就是第一个有效节点
while(pcur != phead)//遇到哨兵位就跳出
{
LTNode* Next = pcur->next;//创建一个指针指向当前位置的下个节点
free(pcur);
pcur = Next;
}
free(phead);
phead = NULL;
pcur = NULL;
//我们已经将链表的空间销毁了，但是plist仍然指向原先的那片空间
//所以我们需要进行手动将plist置为NULL
}
#pragma once
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
//定义双向链表节点的结构
typedef int LTDataType;//链表数据类型
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
//为了保持接口的一致性，优化接口都为一级指针
//初始化
//void LTInit(LTNode**pphead);//我们拿着一个空瓶子让老板给我们装饮料
LTNode* LTInit1();//直接让老板给我们一个装好了的饮料
//通过返回值的方法初始化
//销毁 链表的销毁是整个都销毁的
void LTDesTory(LTNode** pphead);
void LTDesTory2(LTNode* phead);//传一级我们需要手动将plist置为NULL
//打印链表
void LTPrint(LTNode* phead);
//尾插数据
//第一个参数传一级还是二级，，要看pphead指向的节点会不会发生改变
//如果发生改变，那么pphead的改变要影响实参，传二级
//如果不发生改变，pphead不会影响实参，传一级
//我们通过传递的一级指针来找到头结点，就可以找到之后的节点了
//那么我们在插入新节点的时候，受到影响的节点有之前的尾节点和哨兵位以及新节点
void LTPushBack(LTNode* phead, LTDataType x);
//头插数据
void LTPushFront(LTNode* phead, LTDataType x);
//尾删数据
void LTPopBack(LTNode* phead);
//头删数据
void LTPopFront(LTNode* phead);
//判断链表是否为空
bool LTEmpty(LTNode* phead);
//查找数据
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x);
//删除指定位置的节点
void LTIErase(LTNode* pos);
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
void ListTest01()
{
//创建双向链表变量
/*LTNode* plist = NULL;
LTInit(&plist);*///这个里面的哨兵位是自循环的
//初始化操作优化
LTNode* plist = LTInit1();//调用这个函数直接给我们一个指向哨兵位的指针
//这种初始化操作之后我们就不用在外面创建指针传过去了
//尾插
LTPushBack(plist,1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
//头插
/*LTPushFront(plist, 1);
LTPrint(plist);
LTPushFront(plist, 2);
LTPrint(plist);
LTPushFront(plist, 3);
LTPrint(plist);
LTPushFront(plist, 4);
LTPrint(plist);*/
//尾删
/*LTPopBack(plist);
LTPrint(plist);
LTPopBack(plist);
LTPrint(plist);
LTPopBack(plist);
LTPrint(plist);*/
//头删
/*LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);*/
//查找数据
LTNode*pos=LTFind(plist, 1);
/*if (pos == NULL)
{
printf("没有找到\n");
}
else
{
printf("找到了\n");
}*/
//删除指定位置之后的节点
/*LTInsert(pos, 11);
LTPrint(plist);*/
//删除pos位置上的节点
LTIErase(pos);
LTPrint(plist);
//销毁操作
LTDesTory(&plist);
}
int main()
{
ListTest01();
return 0;
