站长之家seo信息,保定模板建站定制网站,大数据平台的搭建,如何自己做跨境电商文章目录
一、 链表的概念及结构
二、链表的分类
编辑
三、手动实现单链表
1、定义单链表的一个节点
2、打印单链表
3、创建新节点
4、单链表的尾插
5、单链表的头插
6、单链表的尾删
7、单链表的头删
8、单链表的查找 9、在指定位置之前插入一个新节点
10、在指…文章目录
一、 链表的概念及结构
二、链表的分类
编辑
三、手动实现单链表
1、定义单链表的一个节点
2、打印单链表
3、创建新节点
4、单链表的尾插
5、单链表的头插
6、单链表的尾删
7、单链表的头删
8、单链表的查找 9、在指定位置之前插入一个新节点
10、在指定位置之后插入一个新节点
11、删除指定节点
12、删除指定节点之后的节点
13、销毁链表
四、单链表实现完整代码
五、手动实现双向链表
1、定义双向链表的一个节点
2、创建新节点
3、双向链表的初始化
4、打印
5、尾插
6、头插
7、尾删
8、头删
9、查找
10、指定位置之后插入
11、删除指定位置的节点
12、销毁 六、双向链表完整源码 一、 链表的概念及结构
链表是⼀种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。即链表的逻辑结构是线性的物理结构是非线性的。 如上图所示链表的每个节点在内存中都是随机分布着的所以其物理结构存储结构为非连续非顺序的但是链表的每个节点中的指针指向下一个节点所以其逻辑结构是线性的。 如图链表的结构跟火车车厢相似淡季时车次的车厢会相应减少旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上不会影响其他车厢每节车厢都是独立存在的。 车厢是独立存在的且每节车厢都有车门。想象一下这样的场景假设每节车厢的车门都是锁上的状态需要不同的钥匙才能解锁每次只能携带一把钥匙的情况下如何从车头走到车尾 最简单的做法每节车厢里都放一把下一节车厢的钥匙。
再对应到链表火车的车厢就是链表的节点而下一节车厢中放的钥匙就是链表的每个节点中存放的下一个节点的地址。 链表的每个类似于车厢的结构都是独立申请的空间我们称之为节点。每个节点都由两部分组成想要存储的数据和存储下一个节点地址的指针。链表中每个节点都是独立申请的即需要插⼊数据时才去申请⼀块节点的空间我们需要通过指针 变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。
二、链表的分类
链表的结构非常多样以下情况组合起来就有8种2x2x2链表结构 1、带头与不带头
带头即链表有头节点哨兵位头节点不存放实际有意义的数据只是用来占位置。有哨兵位的链表就是带头链表如果带头链表只有一个头节点该链表就为空链表。反之没有哨兵位就是不带头链表这时链表的第一个节点就不能称为头节点。 2、单向与双向
单向即链表的节点只有一个指向下一个节点的next指针。
双向即链表的节点不仅有一个指向下一个节点的next指针还有指向上一个节点的prev指针。 3、循环与不循环
循环链表的尾节点的指针并不指向NULL而是指向第一个有效的节点 。 三、手动实现单链表
根据上面链表的分类单链表为不带头单向不循环链表。
为了方便阅读和查阅我们先将单链表的头文件代码展示出来
SList.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.htypedef int DateType;
//创建单链表的一个节点
typedef struct SList
{DateType val;struct SList* next;//指向下一个节点的指针
}SLT;//打印单链表
void PrintSLT(SLT* phead);
//链表尾插
void SLTpushBack(SLT** pphead, DateType x);
//链表头插
void SLTpushFront(SLT** pphead, DateType x);
//链表尾删
void SLTpopBack(SLT** pphead);
//链表头删
void SLTpopFront(SLT** pphead);
//链表的查找
SLT* SLTFind(SLT* ps, DateType x);
//在链表的指定位置之前插入一个新的节点
void SLTInsert(SLT** pphead, SLT* pos, DateType x);
//在链表的指定位置之后插入一个新的节点
void SLTInsertAfter(SLT* pos, DateType x);
//删除指定节点
void SLTErase(SLT** pphead, SLT* pos);
//删除指定节点之后的节点
void SLTEraseAfter(SLT* pos);
//销毁链表中的所有节点
void SLTDestry(SLT** pphead);
1、定义单链表的一个节点
typedef int DateType;
//创建单链表的一个节点
typedef struct SList
{DateType x;struct SList* next;//指向下一个节点的指针
}SLT;
节点中有两个变量一个用来存储数据一个用来存储下一个节点的地址。由于next指针指向下一个节点所以next为struct SList* 类型的指针变量。用typedef关键字来重定义既方便我们修改也方便我们书写。
2、打印单链表
想要打印单链表只需要将单链表遍历一次。但是有个小细节我们需要创建另一个SLT*类型的指针pcur然后用这个指针来遍历单链表防止指针指向改变而找不到链表的第一个节点。
//打印单链表
void PrintSLT(SLT* phead)
{SLT* pcur phead;while (pcur){printf(%d-, pcur-val);pcur pcur-next;}
}
3、创建新节点
想要实现单链表的尾插头插以及指定位置插入数据就避免不了要创建新的节点。由于链表再存储结构上非连续所以我们用malloc来动态申请内存空间然后将新节点的地址返回。
//创建新节点
SLT* BuyNode(DateType x)
{SLT* newnode (SLT*)malloc(sizeof(SLT));if (newnode NULL){perror(malloc);exit(1);}newnode-val x;newnode-next NULL;return newnode;
}
4、单链表的尾插
1对pphead断言操作因为我们不能对空指针进行解引用操作。但是*pphead可以为空此时链表为空链表。 2创建一个新节点newnode用来存放指定的数据并返回新节点的地址。
3链表是否为空
空链表即*ppheadNULL我们只需要让*ppheadnewnode
非空链表因为要尾插我们先要找到链表的尾节点注意while循环结束的条件是
pcur-next NULL。然后让尾节点的next指针指向新节点。
注意当我们在尾插时如果直接将plist作为实参传递给形参phead那么我们发现形参phead并不会影响实参plist的值。我们想要改变实参plist的值就要传地址而不是传值。由于plist是SLT*类型的指针所以需要用SLT**类型的二级指针来接收实参。 如下图为传值调用经过调试和运行plist中的val值并没有发生改变。 //链表尾插
void SLTpushBack(SLT** pphead, DateType x)
{//断言pphead不能为NULL不能对空指针解引用assert(pphead);//创建新节点SLT* newnode BuyNode(x);//处理空链表if (*pphead NULL){*pphead newnode;}//处理非空链表else{SLT* pcur *pphead;while (pcur-next)//找尾节点{pcur pcur-next;}pcur-next newnode;}
}
5、单链表的头插
首先同样是对pphead断言操作然后创建新节点让新节点的next指针指向原来的第一个节点这时候我们就不需要关注吧是否为空了。
//链表头插
void SLTpushFront(SLT** pphead, DateType x)
{assert(pphead);SLT* newnode BuyNode(x);SLT* pcur *pphead;newnode-next pcur;*pphead newnode;
}
6、单链表的尾删
由于链表的节点的空间都是malloc动态申请的因此删除链表的节点即释放节点所占的空间。
1对pphead断言且对*pphead断言因为如果*pphead NULL则链表为空链表不需要尾删。
2处理不同节点数量的情况
只有一个节点当 *pphead-next NULL时即只有一个节点直接将*pphead释放。
不止一个节点我们需要先找到链表的尾节点遍历然后释放。然后将尾节点的前一个节点的next指针置为空。因此我们需要用创建pcur指针防止找不到第一个节点同时创建prev指针记录尾节点的前一个节点。
//链表尾删
void SLTpopBack(SLT** pphead)
{//断言assert(pphead *pphead);//只有一个节点if ((*pphead)-next NULL){free(*pphead);//释放*pphead NULL;}//不止一个节点else{SLT* pcur *pphead;SLT* prev NULL;while (pcur-next){prev pcur;pcur pcur-next;}free(pcur);//释放pcur NULL;prev-next NULL;}
}
7、单链表的头删
1对pphead断言且对*pphead断言因为如果*pphead NULL则链表为空链表不需要尾删。
2释放第一个节点。但在释放之前需要用一个指针pcur记下第一个节点之后的节点因为释放后*pphead应该为原来的第二个节点。
//链表头删
void SLTpopFront(SLT** pphead)
{//断言assert(pphead *pphead);SLT* pcur (*pphead)-next;free(*pphead);*pphead pcur;}
8、单链表的查找
先断言phead不能为空链表然后创建pcur指针遍历链表防止改变phead指针指向而找不到第一个节点。
//链表的查找
SLT* SLTFind(SLT* phead, DateType x)
{assert(phead);SLT* pcur phead;while (pcur){if (pcur - val x){return pcur;}pcur pcur-next;}return NULL;
} 9、在指定位置之前插入一个新节点
1断言
2创建新节点
3将新节点与链表连接起来。我们需要找到指定位置之前的节点prev然后将prev节点新节点newnode和指定位置的节点pos连接起来。 //在链表的指定位置之前插入一个新的节点
void SLTInsert(SLT** pphead, SLT* pos, DateType x)
{assert(pphead *pphead);assert(pos);SLT* newnode BuyNode(x);//找pos节点之前的节点SLT* prev *pphead;while (prev-next ! pos){prev prev-next;}//连接prev,newnode,posprev-next newnode;newnode-next pos;
}
10、在指定位置之后插入一个新节点
1断言
2创建新节点
3将新节点与链表连接起来。我们需要找到指定位置之后的节点pback然后将指定位置的节点、新节点newnode和pback节点连接起来。 //在链表的指定位置之后插入一个新的节点
void SLTInsertAfter(SLT* pos, DateType x)
{assert(pos);SLT* newnode BuyNode(x);SLT* pback pos-next;//连接pos,newnode,pbackpos-next newnode;newnode-next pback;
}
11、删除指定节点
1断言
2pos为第一个节点释放后首节点改变。
pos不是第一个节点释放指定节点但在此之前需要先将指定节点之前的节点prev和指定节点之后的节点pback记录下来,最后连接prev节点和pback节点。 //删除指定节点
void SLTErase(SLT** pphead, SLT* pos)
{assert(pphead *pphead);assert(pos);//指定节点为第一个节点if (*pphead pos){SLT* pcur (*pphead)-next;free(*pphead);*pphead pcur;}else{SLT* prev *pphead;while (prev-next ! pos){prev prev-next;}//先连接pos节点的前一个节点与pos的后一个节点prev-next pos-next;free(pos);pos NULL;}
}
12、删除指定节点之后的节点
先断言看pos是否为空且pos之后的节点是否为尾节点若断言通过则创建std记录pos之后的节点以及创建later 记录std的后一个节点然后连接pos与later最后释放指定节点之后的节点。 //删除指定节点之后的节点
void SLTEraseAfter(SLT* pos)
{assert(pospos-next);//pos-next:处理当pos是最后一个节点的情况SLT* std pos-next;SLT* later std-next;free(std);std NULL;pos-next later;
}
13、销毁链表
断言是否传了空指针链表是否为空然后遍历链表逐个释放。
//销毁链表中的所有节点
void SLTDestry(SLT** pphead)
{assert(pphead *pphead);SLT* std *pphead;while (std){//记录要销毁节点的下一个节点防止释放而找不到SLT* next std-next;free(std);std next;}*pphead NULL;
}
四、单链表实现完整代码
SList.c
#includeSList.h//打印单链表
void PrintSLT(SLT* phead)
{SLT* pcur phead;while (pcur){printf(%d-, pcur-val);pcur pcur-next;}
}//创建新节点
SLT* BuyNode(DateType x)
{SLT* newnode (SLT*)malloc(sizeof(SLT));if (newnode NULL){perror(malloc);exit(1);}newnode-val x;newnode-next NULL;return newnode;
}//链表尾插
void SLTpushBack(SLT** pphead, DateType x)
{//断言pphead不能为NULL不能对空指针解引用assert(pphead);//创建新节点SLT* newnode BuyNode(x);//处理空链表if (*pphead NULL){*pphead newnode;}//处理非空链表else{SLT* pcur *pphead;while (pcur-next)//找尾节点{pcur pcur-next;}pcur-next newnode;}
}//链表头插
void SLTpushFront(SLT** pphead, DateType x)
{assert(pphead);SLT* newnode BuyNode(x);SLT* pcur *pphead;newnode-next pcur;*pphead newnode;
}//链表尾删
void SLTpopBack(SLT** pphead)
{//断言assert(pphead *pphead);//只有一个节点if ((*pphead)-next NULL){free(*pphead);//释放*pphead NULL;}//不止一个节点else{SLT* pcur *pphead;SLT* prev NULL;while (pcur-next){prev pcur;pcur pcur-next;}free(pcur);//释放pcur NULL;prev-next NULL;}
}//链表头删
void SLTpopFront(SLT** pphead)
{//断言assert(pphead *pphead);SLT* pcur (*pphead)-next;free(*pphead);*pphead pcur;}//链表的查找
SLT* SLTFind(SLT* phead, DateType x)
{assert(phead);SLT* pcur phead;while (pcur){if (pcur - val x){return pcur;}pcur pcur-next;}return NULL;
}//在链表的指定位置之前插入一个新的节点
void SLTInsert(SLT** pphead, SLT* pos, DateType x)
{assert(pphead *pphead);assert(pos);SLT* newnode BuyNode(x);//找pos节点之前的节点SLT* prev *pphead;while (prev-next ! pos){prev prev-next;}//连接prev,newnode,posprev-next newnode;newnode-next pos;
}
//在链表的指定位置之后插入一个新的节点
void SLTInsertAfter(SLT* pos, DateType x)
{assert(pos);SLT* newnode BuyNode(x);SLT* pback pos-next;//连接pos,newnode,pbackpos-next newnode;newnode-next pback;
}//删除指定节点
void SLTErase(SLT** pphead, SLT* pos)
{assert(pphead *pphead);assert(pos);//指定节点为第一个节点if (*pphead pos){SLT* pcur (*pphead)-next;free(*pphead);*pphead pcur;}else{SLT* prev *pphead;while (prev-next ! pos){prev prev-next;}//先连接pos节点的前一个节点与pos的后一个节点prev-next pos-next;free(pos);pos NULL;}
}//删除指定节点之后的节点
void SLTEraseAfter(SLT* pos)
{assert(pos pos-next);//pos-next:处理当pos是最后一个节点的情况SLT* std pos-next;SLT* later std-next;free(std);std NULL;pos-next later;
}//销毁链表中的所有节点
void SLTDestry(SLT** pphead)
{assert(pphead *pphead);SLT* std *pphead;while (std){//记录要销毁节点的下一个节点防止释放而找不到SLT* next std-next;free(std);std next;}*pphead NULL;
}
test.c
#includeSList.hvoid test01()
{SLT* s1 (SLT*)malloc(sizeof(SLT));SLT* s2 (SLT*)malloc(sizeof(SLT));SLT* s3 (SLT*)malloc(sizeof(SLT));s1-val 1;s2-val 2;s3-val 3;s1-next s2;s2-next s3;s3-next NULL;PrintSLT(s1);//打印//SLTpopBack(s1);//尾删//SLTpopFront(s1);//头删//SLTpopFront(s1);//头删printf(\n);//PrintSLT(s1);SLT*ret SLTFind(s1, 2);//查找//printf(%d\n, ret-val);//SLTInsert(s1, ret, 4);//指定位置之前插入//PrintSLT(s1);//SLTInsertAfter(ret, 4);//指定位置之后插入//PrintSLT(s1);//删除指定节点SLTErase(s1, ret);PrintSLT(s1);
}void test02()
{SLT* s1 (SLT*)malloc(sizeof(SLT));SLT* s2 (SLT*)malloc(sizeof(SLT));s1-val 1;s2-val 2;s1-next s2;s2-next NULL;SLT* plist s1;SLTpushFront(plist, 3);//头插PrintSLT(plist);
}void test03()
{SLT* plist NULL;//SLTpushBack(plist, 1);//尾插//SLTpushFront(plist, 1);//头插//SLTpopBack(plist);//尾删PrintSLT(plist);
}
int main()
{test01();//test02();//test03();return 0;
}
五、手动实现双向链表
根据前面的分类双向链表即带头双向循环链表 先展示头文件
LTNode.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h#define DateType int
//创建双向链表带头双向循环链表
typedef struct LTNode
{DateType date;struct LTNode* prev;struct LTNode* next;
}LTNode;//初始化
void LTInit(LTNode**pphead);
//创建双向链表中的节点
LTNode* BuyNode(DateType x);
//打印双向链表
void PrintLT(LTNode* phead);
//双向链表尾插
void LTPushBack(LTNode* phead, DateType x);
//头插
void LTPushFront(LTNode* phead, DateType x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, DateType x);
//指定位置之后插入
void LTInsert(LTNode* pos, DateType x);
//删除指定位置的节点
void LTEarse(LTNode* pos);
//销毁
void LTDestry(LTNode* phead);/*所有传的都是一级指针保证了接口的一致性降低了记忆的成本*/
1、定义双向链表的一个节点
双向链表中有一个存储Dateype类型的数据的变脸一个用来指向下一个节点的指针next还有一个用来指向上一个节点的指针prev。
typedef int DateType;
//定义双向链表带头双向循环链表的一个节点
typedef struct LTNode
{DateType date;struct LTNode* prev;//指向前一个节点struct LTNode* next;//指向后一个节点
}LTNode;
2、创建新节点
想要实现双向链表的初始化尾插头插以及指定位置插入数据就避免不了要创建新的节点。由于链表再存储结构上非连续所以我们用malloc来动态申请内存空间然后赋值改变两个指针的指向使其形成自循环最后将新节点的地址返回。 //创建双向链表中的节点
LTNode* BuyNode(DateType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc);exit(1);}newnode-date x;newnode-prev newnode-next newnode;return newnode;
} 3、双向链表的初始化
双向链表是带头链表所以对双向链表初始化即对头节点哨兵位初始化。由于哨兵位不存储有效数据一般将date初始化为-1然后改变两个指针的指向使其形成自循环即直接调用创建新节点的函数。 //初始化
void LTInit(LTNode** pphead)
{*pphead BuyNode(-1);
}
4、打印
打印则要遍历双向链表同时要打印的是双向链表的有效节点。因此用一个pcur指针指向头节点的下一个节点由于是双向链表遍历时的结束条件就应该是pcur ! phead。
//打印双向链表
void PrintLT(LTNode* phead)
{//pcur指向第一个有效节点LTNode* pcur phead-next;while (pcur ! phead){printf(%d-, pcur-date);pcur pcur-next;}
}
5、尾插
先要找到双向链表的尾节点。即phead-prev。
然后连接新节点与原来的尾节点
phead-prev-nextnewnodenewnode-prevphead-prev
最后连接头节点与新节点
phead-prevnewnodenewnode-nextphead
注意连接的顺序不然会改变phead-prev的指向。 //双向链表尾插
void LTPushBack(LTNode* phead, DateType x)
{LTNode* newnode BuyNode(x);//连接原来的尾节点与新节点phead-prev-next newnode;newnode-prev phead-prev;//连接头节点与新节点phead-prev newnode;newnode-next phead;
}
6、头插
头插是指插入到第一个有效节点之前。找到第一个有效节点然后连接头节点新节点与第一个节点。注意phead-next的连接顺序防止改变这种指向。 //头插
void LTPushFront(LTNode* phead, DateType x)
{LTNode* newnode BuyNode(x);//连接新节点与原来第一个与有效节点newnode-next phead-next;phead-next-prev newnode;//连接头节点与新节点phead-next newnode;newnode-prev phead;
}
7、尾删
1断言排除传过来NULL和空链表只有一个头节点的情况
2找到尾节点phead-prev再顺藤摸瓜找到尾节点的前一个节点phead-prev-prev
3连接头节点与新的尾节点即phead与phead-prev-prev注意连接顺序
4释放尾节点。 //尾删
void LTPopBack(LTNode* phead)
{//排除传过来NULL和空链表只有一个头节点的情况assert(phead phead-next ! phead);LTNode* del phead-prev;//尾节点//尾节点的前一个节点del-prev//连接尾节点的前一个节点与头节点del-prev-next phead;phead-prev del-prev;free(del);del NULL;
}
8、头删
删除第一个有效节点。
1断言排除传过来NULL和空链表只有一个头节点的情况
2找到第一个有效节点phead-next第一个有效节点之后的节点phead-next-next
3连接头节点与第一个有效节点之后的节点即连接phead与phead-next-next注意连接顺序
4释放第一个有效节点。 //头删
void LTPopFront(LTNode* phead)
{assert(phead phead-next ! phead);LTNode* del phead-next;//第一个有效节点//第一个有效节点之后的节点;del-next//连接头节点与第一个有效节点之后的节点del-next-prev phead;phead-next del-next;free(del);del NULL;
}
9、查找 查找则要遍历双向链表且要查找的是双向链表的有效节点。因此断言排除传过来NULL和只有一个头节点然后用一个pcur指针指向头节点的下一个节点由于是双向链表遍历时的结束条件就应该是pcur ! phead。
//查找
LTNode* LTFind(LTNode* phead, DateType x)
{assert(phead phead-next ! phead);LTNode* std phead-next;//让std指针指向第一个有效节点//遍历while (std ! std-next){if (std-date x){return std;}std std-next;}return NULL;
}
10、指定位置之后插入
先找到指定位置之后的节点pos-next然后。连接pos节点新节点newnode与指定位置之后的节点pos-next。注意连接顺序防止改变pos-next的指向。 //指定位置之后插入
void LTInsert(LTNode* pos, DateType x)
{LTNode* newnode BuyNode(x);//指定位置之后的节点pos-next//连接新节点与原来指定位置之后的节点newnode-next pos-next;pos-next-prev newnode;//连接新节点与指定位置的节点pos-next newnode;newnode-prev pos;
}
11、删除指定位置的节点
现在的指定位置节点之前的节点pos-prev指定位置之后的节点pos-next。然后连接pos-prev与pos-next。最后释放指定位置节点。 //删除指定位置的节点
void LTEarse(LTNode* pos)
{//指定位置之后的节点pos-next//指定位置之前的节点pos-prev//连接指定位置之后的节点与指定位置之前的节点pos-prev-next pos-next;pos-next-prev pos-prev;//删除pos节点free(pos);pos NULL;
}
12、销毁
先找到第一个有效节点std然后用std指针遍历链表逐个节点释放但在释放结构之前需要记下该节点的下一个节点防止因为释放而找不到到不到销毁整个链表的效果。最后将头节点释放。
//销毁
void LTDestry(LTNode* phead)
{assert(phead);LTNode* std phead-next;//让std指针指向第一个有效节点while (std ! std-next){LTNode* next std-next;//保证在std被释放后std的下一个节点还能找到free(std);std next;//下一个节点}//释放哨兵位free(phead);phead NULL;
} 六、双向链表完整源码
LTNode.c
#includeLTNode.h
//初始化
void LTInit(LTNode** pphead)
{*pphead BuyNode(-1);
}//创建双向链表中的节点
LTNode* BuyNode(DateType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc);exit(1);}newnode-date x;newnode-prev newnode-next newnode;return newnode;
}//打印双向链表
void PrintLT(LTNode* phead)
{//pcur指向第一个有效节点LTNode* pcur phead-next;while (pcur ! phead){printf(%d-, pcur-date);pcur pcur-next;}
}//双向链表尾插
void LTPushBack(LTNode* phead, DateType x)
{LTNode* newnode BuyNode(x);//连接原来的尾节点与新节点phead-prev-next newnode;newnode-prev phead-prev;//连接头节点与新节点phead-prev newnode;newnode-next phead;
}//头插
void LTPushFront(LTNode* phead, DateType x)
{LTNode* newnode BuyNode(x);//连接新节点与原来第一个与有效节点newnode-next phead-next;phead-next-prev newnode;//连接头节点与新节点phead-next newnode;newnode-prev phead;
} //尾删
void LTPopBack(LTNode* phead)
{//排除传过来NULL和空链表只有一个头节点的情况assert(phead phead-next ! phead);LTNode* del phead-prev;//尾节点//尾节点的前一个节点del-prev//连接尾节点的前一个节点与头节点del-prev-next phead;phead-prev del-prev;free(del);del NULL;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead phead-next ! phead);LTNode* del phead-next;//第一个有效节点//第一个有效节点之后的节点;del-next//连接头节点与第一个有效节点之后的节点del-next-prev phead;phead-next del-next;free(del);del NULL;
}
//查找
LTNode* LTFind(LTNode* phead, DateType x)
{assert(phead phead-next ! phead);LTNode* std phead-next;//让std指针指向第一个有效节点//遍历while (std ! std-next){if (std-date x){return std;}std std-next;}return NULL;
}//指定位置之后插入
void LTInsert(LTNode* pos, DateType x)
{LTNode* newnode BuyNode(x);//指定位置之后的节点pos-next//连接新节点与原来指定位置之后的节点newnode-next pos-next;pos-next-prev newnode;//连接新节点与指定位置的节点pos-next newnode;newnode-prev pos;
}
//删除指定位置的节点
void LTEarse(LTNode* pos)
{//指定位置之后的节点pos-next//指定位置之前的节点pos-prev//连接指定位置之后的节点与指定位置之前的节点pos-prev-next pos-next;pos-next-prev pos-prev;//删除pos节点free(pos);pos NULL;
}
//销毁
void LTDestry(LTNode* phead)
{assert(phead);LTNode* std phead-next;//让std指针指向第一个有效节点while (std ! std-next){LTNode* next std-next;//保证在std被释放后std的下一个节点还能找到free(std);std next;//下一个节点}//释放哨兵位free(phead);phead NULL;
}
test.c
#includeLTNode.h
void test01()
{LTNode* plist NULL;LTInit(plist);//初始化//LTPushBack(plist, 4);//尾插//LTPushFront(plist, 4);//头插//LTPopBack(plist);//尾删LTPopFront(plist);PrintLT(plist);
}
void test02()
{LTNode* s NULL;LTInit(s);LTNode* s1 (LTNode*)malloc(sizeof(LTNode));LTNode* s2 (LTNode*)malloc(sizeof(LTNode));LTNode* s3 (LTNode*)malloc(sizeof(LTNode));s1-date 1;s2-date 2;s3-date 3;//连接s-next s1;s-prev s3;s1-prev s;s1-next s2;s2-prev s1;s2-next s3;s3-prev s2;s3-next s;PrintLT(s);//打印printf(\n);//LTPushBack(s, 4);//尾插//LTPushFront(s,4);//头插//LTPopBack(s);//尾删//LTPopFront(s);//头删LTNode* ret LTFind(s, 2);//查找//printf(%d\n, ret-date);//LTInsert(ret, 4);//指定位置之后插入LTEarse(ret);PrintLT(s);
}
int main()
{//test01();test02();return 0;
}
