链表续-8种链表（数据结构）
目录
了解链表
由于之前已经有一篇文章介绍链表，本次直接上八种链表的代码
具体前一篇文章阅读此处：链表介绍
八种链表代码
单向链表
节点当中存放数据以及指向下一个节点的指针
代码：
#define _CRT_SECURE_NO_WARINGS 1 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> typedef int DataType; //创建单链表结构 typedef struct SListNode { DataType data; struct SListNode* next; }SLTNode; //打印 void SLTPrint(SLTNode* phead) { //断言指针 //assert(phead); SLTNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } //开辟空间 SLTNode* SLTSpace(DataType x) { //开辟空间 SLTNode* p = (SLTNode*)malloc(sizeof(SLTNode)); if (p == NULL) { perror("Space malloc fail"); return NULL; } p->data = x; p->next = NULL; return p; } //头插 void SLPushFront(SLTNode** pphead, DataType x) { //断言指针 assert(pphead); //创建节点 SLTNode* newNode = SLTSpace(x); //无节点的情况下直接插入 if (*pphead == NULL) { *pphead = newNode; return; } //节点存在的情况下插入 newNode->next = *pphead; *pphead = newNode; } //头删 void SLPopFront(SLTNode** pphead) { //断言指针 assert(pphead); assert(*pphead); //只有一个节点的情况下 if ((*pphead)->next == NULL) { //直接进行删除释放 (*pphead)->data = 0; free(*pphead); *pphead = NULL; return; } //有多个节点的情况下 SLTNode* cur = *pphead; SLTNode* tail = *pphead; //tail表示头节点的下一个节点 tail = cur->next; //释放头节点 cur->data = 0; free(cur); *pphead = tail; //将tail置NULL 避免野指针 tail = NULL; } //尾插 void SLPushBank(SLTNode** pphead, DataType x) { //断言指针 assert(pphead); //assert(*pphead);无节点的情况不能断言 //开辟新节点 SLTNode* newNode = SLTSpace(x); //没有节点的情况 if (*pphead == NULL) { //直接插入 *pphead = newNode; return; } //存在节点的时候 //循环遍历找尾 //找尾进行尾插 SLTNode* cur = *pphead; while (cur->next) { cur = cur->next; } //尾插链接 cur->next = newNode; } //尾删 void SLPopBank(SLTNode** pphead) { //断言指针 assert(pphead); assert(*pphead); //只有一个节点的情况 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; return; } //进行找尾 SLTNode* cur = *pphead; SLTNode* tail = *pphead; while (tail->next) { //cur表示最后一个节点的前一个节点 cur = tail; tail = tail->next; } free(tail); tail = NULL; cur->next = NULL; } //查找 SLTNode* SLFind(SLTNode* phead, DataType x) { //断言指针 assert(phead); //循环遍历查找 SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } //找不见的时候返回NULL return NULL; } //销毁 void SLDestroy(SLTNode** pphead) { //断言指针 assert(*pphead); //循环遍历销毁节点 SLTNode* cur = *pphead; SLTNode* tail = *pphead; while (cur) { tail = cur; cur = cur->next; tail->data = 0; free(tail); } *pphead = NULL; } //在pos位置前插入 void SLInsert(SLTNode** pphead, SLTNode* pos, DataType x) { //断言指针 assert(pphead); //申请节点 SLTNode* newnode = SLTSpace(x); //pos为NULL if (pos == NULL) { // *pphead也为NULL,直接插入 if ((*pphead) == NULL) { *pphead = newnode; newnode->next = pos; return; } //pos为NULL 且*pphead不为空的情况 //说明最后一个节点的下一个节点就是尾插 SLPushBank(pphead, x); return; } //pos是头节点的情况，直接进行头插 if (pos == (*pphead)) { //头插 SLPushFront(pphead, x); return; } //pos不为空且不是头节点的情况 SLTNode* cur = *pphead; SLTNode* prev = *pphead; while (cur) { if (cur == pos) { prev->next = newnode; newnode->next = pos; return; } prev = cur; cur = cur->next; } perror("pos Does not exist"); } //在pos位置前删除 void SLErase(SLTNode** pphead, SLTNode* pos) { //pos为空其实就是尾删(以上函数已经实现） //pos和为头节点无法删除，头节点前无任何节点 //pos为头节点且都为NULL ,无节点无法删除 //即pos不为头节点，且pos不能为空 //断言指针 assert(pphead); assert(*pphead);//头节点不能为空，无法删除 assert(pos); //若pos为第二个节点，删除pos的前一个节点就是头删 if ((*pphead)->next == pos) { //头删 SLPopFront(pphead); return; } //pos为头节点无法删除，头节点前无任何节点 if (pos == (*pphead)) { perror("pos == phead"); return; } //不是头删以及不是头的情况 SLTNode* cur = *pphead; SLTNode* pevr = *pphead; SLTNode* ppevr = *pphead; while (cur) { if (cur == pos) { free(pevr); pevr = NULL; ppevr->next = cur; return; } ppevr = pevr; pevr = cur; cur = cur->next; } perror("pos Does not exist"); } //在pos位置后插入 void SLInsertAfter(SLTNode* pos, DataType x) { //pos为空的情况下，无法插入 assert(pos); //创建节点 SLTNode* newnode = SLTSpace(x); SLTNode* plast = pos->next; pos->next = newnode; newnode->next = plast; } //在pos位置后删除 void SLEraseAfter(SLTNode* pos) { //pos不能为NULL,为NULL无法删除 assert(pos); //pos后一个节点为NULL的情况，无法删除 assert(pos->next); SLTNode* cur = pos->next; SLTNode* plast = pos->next->next; free(cur); cur = NULL; pos->next = plast; } int main() { //创建变量 SLTNode* sl = NULL; SLPushFront(&sl, 1);//头插 SLTPrint(sl);//打印 SLPushFront(&sl, 2);//头插 SLPushFront(&sl, 3);//头插 SLTPrint(sl);//打印 SLPopFront(&sl);//头删 SLPopFront(&sl);//头删 SLTPrint(sl);//打印 SLPopFront(&sl);//头删 SLTPrint(sl);//打印 SLPushBank(&sl, 6);//尾插 SLPushBank(&sl, 7);//尾插 SLPushBank(&sl, 8);//尾插 SLTPrint(sl);//打印 SLPopBank(&sl);//尾删 SLTPrint(sl);//打印 SLTNode* ret = SLFind(sl, 7);//查找 printf("%d\n", ret->data); SLInsert(&sl, ret, 8);//在pos位置前插入 SLTPrint(sl);//打印 SLErase(&sl, ret);//在pos位置前删除 SLTPrint(sl);//打印 SLInsertAfter(ret, 9);//在pos位置后插入 SLTPrint(sl);//打印 SLEraseAfter(ret);//在pos位置后删除 SLTPrint(sl);//打印 SLDestroy(&sl);//销毁 SLTPrint(sl);//打印 return 0; }
单向带头链表
节点中存放数据以及指向下一个节点的指针，且会单独开一个哨兵位的头节点，该头节点一般不存放有效数据。
代码：
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int DataType; //定义结构 typedef struct HSTNode { DataType data; struct HSTNode* next; }HSTNode; //初始化头节点（创建哨兵位的头节点） void HSTInit(HSTNode** pphead, DataType x) { //开辟空间，带头节点 assert(pphead); HSTNode* cur = (HSTNode*)malloc(sizeof(HSTNode)); if (cur == NULL) { perror("head malloc fail"); return; } cur->data = x; cur->next = NULL; *pphead = cur; } //开空间 HSTNode* HSTSpace(DataType x) { HSTNode* newnode = (HSTNode*)malloc(sizeof(HSTNode)); if (newnode == NULL) { perror("head malloc fail"); return; } newnode->data = x; newnode->next = NULL; return newnode; } //打印 void HSTPrint(HSTNode* phead) { //必须存在哨兵位的头节点 assert(phead); HSTNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } //头插(插到哨兵位头节点的后面） void HSTPushFront(HSTNode** pphead, DataType x) { //必须存在头节点，断言头节点 assert(pphead); assert(*pphead); //开辟空间 HSTNode* newnode = HSTSpace(x); //直接插入 HSTNode* cur = (*pphead)->next; (*pphead)->next = newnode; newnode->next = cur; } //头删 void HSTPopFront(HSTNode** pphead) { //带哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //只有哨兵位头节点一个节点的情况不能删除 if ((*pphead)->next == NULL) { perror("is NULL"); return; } HSTNode* cur = (*pphead)->next->next; HSTNode* pevr = (*pphead)->next; free(pevr); pevr = NULL; (*pphead)->next = cur; } //尾插 void HSTPushBank(HSTNode** pphead, DataType x) { //哨兵位的头节点不能为空 assert(pphead); assert(*pphead); //开辟节点空间 HSTNode* newnode = HSTSpace(x); HSTNode* cur = *pphead; HSTNode* pevr = *pphead; while (cur) { pevr = cur; cur = cur->next; } pevr->next = newnode; } //尾删 void HSTPopBank(HSTNode** pphead) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //没有数据的时候无法删除（仅有哨兵位的头节点） if ((*pphead)->next == NULL) { perror("is NULL"); return; } //存在数据找尾释放 HSTNode* cur = *pphead; HSTNode* pevr = *pphead; while (cur->next) { pevr = cur; cur = cur->next; } free(cur); cur = NULL; pevr->next = NULL; } //查找 HSTNode* HSTFind(HSTNode* phead, DataType x) { //保证哨兵位的头节点存在 assert(phead); //遍历查找 HSTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //在pos位置前插入 void SHTInsert(HSTNode** pphead, HSTNode* pos, DataType x) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //pos不能为哨兵位的头节点 if ((*pphead) == pos) { perror("(*pphead) == pos"); return; } //pos为空，表示pos为最后一个节点的下一个节点 //在pos前插入实际上是尾插 if (pos == NULL) { //尾插 HSTPushBank(pphead, x); return; } //获取节点 HSTNode* newnode = HSTSpace(x); //进行插入 HSTNode* cur = *pphead; HSTNode* pevr = *pphead; while (cur) { if (cur == pos) { pevr->next = newnode; newnode->next = pos; return; } pevr = cur; cur = cur->next; } perror("pos Does not exist"); } //在pos位置前删除 void SHTErase(HSTNode** pphead, HSTNode* pos) { //保证哨兵位的头节点必须存在 assert(*pphead); assert(pphead); //若只有头或pos为哨兵位头节点的下一个节点情况下不能删除 if ((*pphead)->next == pos) { perror("*pphead->next==pos"); return; } //pos为哨兵位的头节点的情况下不能删除 if ((*pphead) == pos) { perror("(*pphead) == pos"); return; } //pos既不为哨兵位头节点，也不是头节点的下一个节点 //若pos为空，则是尾删 //以及pos不为空的情况 HSTNode* cur = *pphead; HSTNode* pevr = *pphead; while (cur) { if (cur->next == pos) { free(cur); pevr->next = pos; cur = NULL; return; } pevr = cur; cur = cur->next; } perror("pos Does not exist"); } //在pos位置后插入 void SHTInsertAfert(HSTNode* pos, DataType x) { //pos为空不能插入 //保证头节点存在 assert(pos); //获取节点 HSTNode* newnode = HSTSpace(x); //直接插入 HSTNode* cur = pos->next; pos->next = newnode; newnode->next = cur; } //在pos位置后删除 void SHTEraseAfert(HSTNode* pos) { //pos为空不能删除 assert(pos); //pos的下一个元素为NULL，不能删除 if (pos->next == NULL) { perror("pos->next == NULL"); return; } //进行删除 HSTNode* perv = pos->next; HSTNode* cur = pos->next->next; free(perv); perv = NULL; pos->next = cur; } //销毁 void HSTDestroy(HSTNode** pphead) { //哨兵位的头节点也进行销毁 //手心断定哨兵位的头节点时存在的 assert(pphead); assert(*pphead); //循环遍历销毁 HSTNode* cur = *pphead; HSTNode* next = *pphead; while (cur) { next = cur->next; free(cur); cur = next; } //销毁后将哨兵位的头节点置空，避免野指针 *pphead = NULL; } int main() { HSTNode* sl = NULL; //初始化头节点（创建哨兵位的头节点） HSTInit(&sl, 0); HSTPrint(sl);//打印 //头插 HSTPushFront(&sl, 1); HSTPushFront(&sl, 2); HSTPushFront(&sl, 3); HSTPushFront(&sl, 4); HSTPrint(sl);//打印 //头删 HSTPopFront(&sl); HSTPopFront(&sl); HSTPopFront(&sl); HSTPopFront(&sl); HSTPrint(sl);//打印 //尾插 HSTPushBank(&sl, 7); HSTPushBank(&sl, 8); HSTPushBank(&sl, 9); HSTPrint(sl);//打印 //尾删 HSTPopBank(&sl); HSTPopBank(&sl); HSTPrint(sl);//打印 //查找 HSTNode* ret = HSTFind(sl, 7); printf("%d\n", ret->data); //在pos位置前插入 SHTInsert(&sl, ret, 1); SHTInsert(&sl, NULL, 3); HSTPrint(sl);//打印 //在pos位置前删除 SHTErase(&sl, ret); SHTErase(&sl, NULL); HSTPrint(sl);//打印 //在pos位置后插入 SHTInsertAfert(ret, 6); SHTInsertAfert(sl, 9); HSTPrint(sl);//打印 //在pos位置后删除 SHTEraseAfert(ret); SHTEraseAfert(sl); HSTPrint(sl);//打印 //销毁 HSTDestroy(&sl); //销毁之后无法打印 //HSTPrint(sl);//打印 return 0; }
单向循环链表
节点中存放数据以及指向下一个节点的指针，且尾节点中存放的指向下一个节点的指针为头节点的地址，形成尾首相连为一个循环。
代码：
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int DataType; //定义结构 typedef struct HSTNode { DataType data; struct HSTNode* next; }HSTNode; //初始化头节点（创建哨兵位的头节点） void HSTInit(HSTNode** pphead, DataType x) { //开辟空间，带头节点 assert(pphead); HSTNode* cur = (HSTNode*)malloc(sizeof(HSTNode)); if (cur == NULL) { perror("head malloc fail"); return; } cur->data = x; cur->next = NULL; *pphead = cur; } //开空间 HSTNode* HSTSpace(DataType x) { HSTNode* newnode = (HSTNode*)malloc(sizeof(HSTNode)); if (newnode == NULL) { perror("head malloc fail"); return; } newnode->data = x; newnode->next = NULL; return newnode; } //打印 void HSTPrint(HSTNode* phead) { //必须存在哨兵位的头节点 assert(phead); HSTNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } //头插(插到哨兵位头节点的后面） void HSTPushFront(HSTNode** pphead, DataType x) { //必须存在头节点，断言头节点 assert(pphead); assert(*pphead); //开辟空间 HSTNode* newnode = HSTSpace(x); //直接插入 HSTNode* cur = (*pphead)->next; (*pphead)->next = newnode; newnode->next = cur; } //头删 void HSTPopFront(HSTNode** pphead) { //带哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //只有哨兵位头节点一个节点的情况不能删除 if ((*pphead)->next == NULL) { perror("is NULL"); return; } HSTNode* cur = (*pphead)->next->next; HSTNode* pevr = (*pphead)->next; free(pevr); pevr = NULL; (*pphead)->next = cur; } //尾插 void HSTPushBank(HSTNode** pphead, DataType x) { //哨兵位的头节点不能为空 assert(pphead); assert(*pphead); //开辟节点空间 HSTNode* newnode = HSTSpace(x); HSTNode* cur = *pphead; HSTNode* pevr = *pphead; while (cur) { pevr = cur; cur = cur->next; } pevr->next = newnode; } //尾删 void HSTPopBank(HSTNode** pphead) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //没有数据的时候无法删除（仅有哨兵位的头节点） if ((*pphead)->next == NULL) { perror("is NULL"); return; } //存在数据找尾释放 HSTNode* cur = *pphead; HSTNode* pevr = *pphead; while (cur->next) { pevr = cur; cur = cur->next; } free(cur); cur = NULL; pevr->next = NULL; } //查找 HSTNode* HSTFind(HSTNode* phead, DataType x) { //保证哨兵位的头节点存在 assert(phead); //遍历查找 HSTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //在pos位置前插入 void SHTInsert(HSTNode** pphead, HSTNode* pos, DataType x) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //pos不能为哨兵位的头节点 if ((*pphead) == pos) { perror("(*pphead) == pos"); return; } //pos为空，表示pos为最后一个节点的下一个节点 //在pos前插入实际上是尾插 if (pos == NULL) { //尾插 HSTPushBank(pphead, x); return; } //获取节点 HSTNode* newnode = HSTSpace(x); //进行插入 HSTNode* cur = *pphead; HSTNode* pevr = *pphead; while (cur) { if (cur == pos) { pevr->next = newnode; newnode->next = pos; return; } pevr = cur; cur = cur->next; } perror("pos Does not exist"); } //在pos位置前删除 void SHTErase(HSTNode** pphead, HSTNode* pos) { //保证哨兵位的头节点必须存在 assert(*pphead); assert(pphead); //若只有头或pos为哨兵位头节点的下一个节点情况下不能删除 if ((*pphead)->next == pos) { perror("*pphead->next==pos"); return; } //pos为哨兵位的头节点的情况下不能删除 if ((*pphead) == pos) { perror("(*pphead) == pos"); return; } //pos既不为哨兵位头节点，也不是头节点的下一个节点 //若pos为空，则是尾删 //以及pos不为空的情况 HSTNode* cur = *pphead; HSTNode* pevr = *pphead; while (cur) { if (cur->next == pos) { free(cur); pevr->next = pos; cur = NULL; return; } pevr = cur; cur = cur->next; } perror("pos Does not exist"); } //在pos位置后插入 void SHTInsertAfert(HSTNode* pos, DataType x) { //pos为空不能插入 //保证头节点存在 assert(pos); //获取节点 HSTNode* newnode = HSTSpace(x); //直接插入 HSTNode* cur = pos->next; pos->next = newnode; newnode->next = cur; } //在pos位置后删除 void SHTEraseAfert(HSTNode* pos) { //pos为空不能删除 assert(pos); //pos的下一个元素为NULL，不能删除 if (pos->next == NULL) { perror("pos->next == NULL"); return; } //进行删除 HSTNode* perv = pos->next; HSTNode* cur = pos->next->next; free(perv); perv = NULL; pos->next = cur; } //销毁 void HSTDestroy(HSTNode** pphead) { //哨兵位的头节点也进行销毁 //手心断定哨兵位的头节点时存在的 assert(pphead); assert(*pphead); //循环遍历销毁 HSTNode* cur = *pphead; HSTNode* next = *pphead; while (cur) { next = cur->next; free(cur); cur = next; } //销毁后将哨兵位的头节点置空，避免野指针 *pphead = NULL; } int main() { HSTNode* sl = NULL; //初始化头节点（创建哨兵位的头节点） HSTInit(&sl, 0); HSTPrint(sl);//打印 //头插 HSTPushFront(&sl, 1); HSTPushFront(&sl, 2); HSTPushFront(&sl, 3); HSTPushFront(&sl, 4); HSTPrint(sl);//打印 //头删 HSTPopFront(&sl); HSTPopFront(&sl); HSTPopFront(&sl); HSTPopFront(&sl); HSTPrint(sl);//打印 //尾插 HSTPushBank(&sl, 7); HSTPushBank(&sl, 8); HSTPushBank(&sl, 9); HSTPrint(sl);//打印 //尾删 HSTPopBank(&sl); HSTPopBank(&sl); HSTPrint(sl);//打印 //查找 HSTNode* ret = HSTFind(sl, 7); printf("%d\n", ret->data); //在pos位置前插入 SHTInsert(&sl, ret, 1); SHTInsert(&sl, NULL, 3); HSTPrint(sl);//打印 //在pos位置前删除 SHTErase(&sl, ret); SHTErase(&sl, NULL); HSTPrint(sl);//打印 //在pos位置后插入 SHTInsertAfert(ret, 6); SHTInsertAfert(sl, 9); HSTPrint(sl);//打印 //在pos位置后删除 SHTEraseAfert(ret); SHTEraseAfert(sl); HSTPrint(sl);//打印 //销毁 HSTDestroy(&sl); //销毁之后无法打印 //HSTPrint(sl);//打印 return 0; }
单向带头循环链表
节点中存放数据以及指向下一个节点的指针，会开辟一个节点空间用来做哨兵位的头节点，一般头节点中不存放有效数据，且尾节点中存放的指向下一个节点的指针为哨兵位头节点的地址，形成尾首相连为一个循环。
代码：
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <assert.h> //创建节点 typedef int DataType; typedef struct HPLSTNode { DataType data; struct HPLST* next; }HPLSTNode; //初始化哨兵位的头节点 void HPLSTInit(HPLSTNode** pphead, DataType x) { //断言指针 assert(pphead); //申请节点 HPLSTNode* cur = (HPLSTNode*)malloc(sizeof(HPLSTNode)); if (cur == NULL) { perror("mallc fail"); return; } //开辟成功 cur->next = cur; cur->data = x; *pphead = cur; } //创建节点 HPLSTNode* HPLSTSpace(DataType x) { //开辟空间 HPLSTNode* newnode = (HPLSTNode*)malloc(sizeof(HPLSTNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->next = NULL; newnode->data = x; return newnode; } //打印 void HPLSTPrint(HPLSTNode* phead) { if (phead == NULL) { printf("NULL\n"); return; } //哨兵位的头节点一定存在 printf("%d->", phead->data); HPLSTNode* cur = phead->next; while (cur != phead) { printf("%d->", cur->data); cur = cur->next; } printf("head\n"); } //头插 void HPLSTPushFront(HPLSTNode** pphead, DataType x) { //带哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //创建节点 HPLSTNode* newnode = HPLSTSpace(x); //直接插入 HPLSTNode* next = (*pphead)->next; (*pphead)->next = newnode; newnode->next = next; } //头删 void HPLSTPopFront(HPLSTNode** pphead) { //带哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //除了哨兵位头节点，不存在其他节点的情况下不可删除 if ((*pphead)->next == (*pphead)) { assert(NULL); } //具有其他节点的情况可以删除 HPLSTNode* cur = (*pphead)->next; HPLSTNode* next = cur->next; cur->next = NULL; free(cur); cur = NULL; (*pphead)->next = next; } //尾插 void HPLSTPushBank(HPLSTNode** pphead, DataType x) { //哨兵位的头节点必须存在(即链表不能为NULL） assert(pphead); assert(*pphead); //创建节点 HPLSTNode* newnode = HPLSTSpace(x); //找尾进行插入 HPLSTNode* cur = *pphead; while (cur->next != (*pphead)) { cur = cur->next; } //插入 HPLSTNode* next = cur->next; cur->next = newnode; newnode->next = next; } //尾删 void HPLSTPopBank(HPLSTNode** pphead) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //仅有哨兵位的头节点一个节点的时候无法删除 if ((*pphead)->next == (*pphead)) { assert(NULL); } //有两个或多个节点的情况 //找尾删除 HPLSTNode* cur = *pphead; HPLSTNode* pevr = *pphead; while (cur->next != (*pphead)) { pevr = cur; cur = cur->next; } //删除 HPLSTNode* next = cur->next; cur->next = NULL; free(cur); cur = NULL; pevr->next = next; } //查找 HPLSTNode* HPLSTFind(HPLSTNode** pphead, DataType x) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //仅有哨兵位头节点一个节点的时候不可查找 //头节点不存有效数据 if ((*pphead)->next == (*pphead)) { assert(NULL); } //循环遍历查找 HPLSTNode* cur = (*pphead)->next; while (cur != (*pphead)) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //在pos位置前插入 void HPLSTInster(HPLSTNode** pphead, HPLSTNode* pos, DataType x) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //pos为NULL无法插入 assert(pos); //获取节点 HPLSTNode* newnode = HPLSTSpace(x); //pos为哨兵位的头节点（就是尾插） if (pos == (*pphead)) { HPLSTPushBank(pphead, x); return; } //pos不为头节点 //找到pos的前一个节点进行插入操作 HPLSTNode* cur = *pphead; HPLSTNode* pevr = *pphead; while (cur != pos) { pevr = cur; cur = cur->next; } pevr->next = newnode; newnode->next = cur; } //在pos位置前删除 void HPLSTErase(HPLSTNode** pphead, HPLSTNode* pos) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //pos为NULL无法删除 assert(pos); //pos为哨兵位的头节点的下一个节点无法删除 //因为哨兵位的头节点必须存在 if ((*pphead)->next == pos) { assert(NULL); return; } //pos为哨兵位的头节点则是尾删 if (pos == (*pphead)) { //尾删 HPLSTPopBank(pphead); return; } //其余情况 HPLSTNode* cur = *pphead; HPLSTNode* pevr = *pphead; while (cur->next != pos) { pevr = cur; cur = cur->next; } cur->next = NULL; free(cur); cur = NULL; pevr->next = pos; } //在pos位置后插入 void HPLSTInsertAfter(HPLSTNode** pphead, HPLSTNode* pos, DataType x) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //pos为NULL不能插入 assert(pos); //判断pos是否为该链表中的节点 //…………………… 省略……………… //存在的情况 //创建节点 HPLSTNode* newnode = HPLSTSpace(x); HPLSTNode* next = pos->next; //进行插入 pos->next = newnode; newnode->next = next; } //在pos位置后删除 void HPLSTEraseAfter(HPLSTNode** pphead, HPLSTNode* pos) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //pos为NULL不能删除 assert(pos); //仅有哨兵位头节点一个节点的情况不能删除 if ((*pphead)->next == (*pphead)) { assert(NULL); } //pos为尾节点的情况不能删除 if (pos->next == (*pphead)) { assert(NULL); } HPLSTNode* cur = pos->next; HPLSTNode* next = cur->next; cur->next = NULL; free(cur); cur = NULL; pos->next = next; } //销毁 void HPLSTDestroy(HPLSTNode** pphead) { //无节点的情况下不用销毁 assert(pphead); assert(*pphead); //开始销毁 HPLSTNode* cur = (*pphead)->next; HPLSTNode* ccur = cur; while (cur != (*pphead)) { ccur = cur->next; cur->next = NULL; free(cur); cur = ccur; } cur->next = NULL; free(cur); cur = NULL; ccur = NULL; *pphead = NULL; } int main() { HPLSTNode* sl = NULL; //初始化哨兵位的头节点 HPLSTInit(&sl, 0); HPLSTPrint(sl);//打印 //头插 HPLSTPushFront(&sl, 1); HPLSTPushFront(&sl, 2); HPLSTPushFront(&sl, 3); HPLSTPrint(sl);//打印 //头删 HPLSTPopFront(&sl); HPLSTPrint(sl);//打印 HPLSTPopFront(&sl); HPLSTPrint(sl);//打印 HPLSTPopFront(&sl); HPLSTPrint(sl);//打印 //尾插 HPLSTPushBank(&sl, 4); HPLSTPushBank(&sl, 5); HPLSTPushBank(&sl, 6); HPLSTPrint(sl);//打印 //尾删 HPLSTPopBank(&sl); HPLSTPrint(sl);//打印 HPLSTPopBank(&sl); HPLSTPrint(sl);//打印 //查找 HPLSTNode* ret = HPLSTFind(&sl, 4); if (ret != NULL) printf("Find: %d\n", ret->data); else printf("Find: NULL\n"); //在pos位置前插入 HPLSTInster(&sl, ret, 9); HPLSTPrint(sl);//打印 HPLSTInster(&sl, sl, 12); HPLSTPrint(sl);//打印 HPLSTInster(&sl, sl->next, 16); HPLSTPrint(sl);//打印 //查找 ret = HPLSTFind(&sl, 4); if (ret != NULL) printf("Find: %d\n", ret->data); else printf("Find: NULL\n"); //在pos位置前删除 //HPLSTErase(&sl, ret->next); //HPLSTPrint(sl);//打印 //HPLSTErase(&sl, NULL); //HPLSTPrint(sl);//打印 //HPLSTErase(NULL, ret); //HPLSTPrint(sl);//打印 HPLSTErase(&sl, ret); HPLSTPrint(sl);//打印 HPLSTErase(&sl, ret); HPLSTPrint(sl);//打印 //HPLSTErase(&sl, ret); //HPLSTPrint(sl);//打印 //查找 ret = HPLSTFind(&sl, 4); if (ret != NULL) printf("Find: %d\n", ret->data); else printf("Find: NULL\n"); //在pos位置后插入 HPLSTInsertAfter(&sl, ret->next, 45); HPLSTPrint(sl);//打印 HPLSTInsertAfter(&sl, ret, 45); HPLSTPrint(sl);//打印 //在pos位置后删除 HPLSTEraseAfter(&sl, ret); HPLSTPrint(sl);//打印 HPLSTEraseAfter(&sl, ret); HPLSTPrint(sl);//打印 HPLSTEraseAfter(&sl, ret); HPLSTPrint(sl);//打印 HPLSTEraseAfter(&sl, sl); HPLSTPrint(sl);//打印 //销毁 HPLSTDestroy(&sl); HPLSTPrint(sl);//打印 return 0; }
双向链表
节点中存放数据以及两个指针，一个是指向前一个节点的指针，另一个是指向下一个节点的指针。
代码：
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <assert.h> //创建结构 typedef int DataType; typedef struct BSTLNode { DataType data; struct BSTLNode* pevr; struct BSTLNode* next; }BSTLNode; //开辟空间（创建节点） BSTLNode* BSTLSpace(DataType x) { BSTLNode* newnode = (BSTLNode*)malloc(sizeof(BSTLNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; newnode->pevr = NULL; } //打印 void BSTLPrint(BSTLNode* phead) { BSTLNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } //头插 void BSTLPushFront(BSTLNode** pphead, DataType x) { //断言指针 assert(pphead); //创建节点 BSTLNode* newnode = BSTLSpace(x); //无节点的情况 if (*pphead == NULL) { *pphead = newnode; return; } //存在节点的情况 newnode->next = (*pphead); (*pphead)->pevr = newnode; *pphead = newnode; } //头删 void BSTLPopFront(BSTLNode** pphead) { //无节点的情况下不能删除 assert(*pphead); assert(pphead); //仅有一个头节点的情况下 if ((*pphead)->next == NULL) { (*pphead)->next = NULL; (*pphead)->pevr = NULL; free(*pphead); *pphead = NULL; return; } //有节点的情况下删除 BSTLNode* cur = (*pphead)->next; free(cur->pevr); cur->pevr = NULL; *pphead = cur; } //尾插 void BSTLPushBank(BSTLNode** pphead, DataType x) { //断言指针 assert(pphead); //创建节点 BSTLNode* newnode = BSTLSpace(x); //无节点的情况下直接插入 if ((*pphead) == NULL) { //直接插入 *pphead = newnode; return; } //有节点的情况下,找尾插入 BSTLNode* cur = *pphead; while (cur->next) { cur = cur->next; } cur->next = newnode; newnode->pevr = cur; } //尾删 void BSTLPopBank(BSTLNode** pphead) { //没有节点不能删除 assert(pphead); assert(*pphead); //只有一个头节点的情况 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; return; } //找尾释放删除 BSTLNode* cur = *pphead; while (cur->next) { cur = cur->next; } BSTLNode* pevr = cur->pevr; cur->pevr = NULL; free(cur); cur = NULL; pevr->next = NULL; } //查找 BSTLNode* BSTLFind(BSTLNode** pphead, DataType x) { //没有节点无法查找 assert(*pphead); BSTLNode* cur = *pphead; while (cur) { if (cur->data == x) { return cur; } } return NULL; } //在pos位置前插入 void BSTLInsert(BSTLNode** pphead, BSTLNode* pos, DataType x) { //断言指针 assert(pphead); assert(*pphead); //pos为空实际上是尾插 if (pos == NULL) { BSTLPushBank(pphead, x); return; } //申请节点 BSTLNode* newnode = BSTLSpace(x); //pos为头节点，前面插入便是头插 if ((*pphead) == pos) { BSTLPushFront(pphead, x); return; } //不为头节点则直接插入 BSTLNode* pevr = pos->pevr; pevr->next = newnode; newnode->pevr = pevr; newnode->next = pos; } //在pos位置前删除 void BSTLErase(BSTLNode** pphead, BSTLNode* pos) { //头节点不能为NULL assert(pphead); assert(*pphead); //若为头节点则不能删除 if ((*pphead) == pos) { perror("pos==phead"); return; } //pos为NULL说明是尾删 if (pos == NULL) { BSTLPopBank(pphead); return; } //pos为第二个节点 if ((*pphead)->next == pos) { (*pphead)->pevr = NULL; (*pphead)->next = NULL; free(*pphead); pos->pevr = NULL; *pphead = pos; return; } //其余情况 BSTLNode* pevr = pos->pevr; BSTLNode* ppevr = pevr->pevr; pevr->pevr = NULL; pevr->next = NULL; free(pevr); pevr = NULL; ppevr->next = pos; pos->pevr = ppevr; } //在pos位置后插入 void BSTLInsertAfter(BSTLNode* pos, DataType x) { //pos不能为空 assert(pos); //申请节点 BSTLNode* newnode = BSTLSpace(x); //插入 BSTLNode* cur = pos->next; pos->next = newnode; newnode->pevr = pos; newnode->next = cur; cur->pevr = newnode; } //在pos位置后删除 void BSTLEraseAfter(BSTLNode* pos) { //pos不能为空，为空则不能删除 assert(pos); //pos后一个为NULL 也不能删除 assert(pos->next); //删除 BSTLNode* cur = pos->next; BSTLNode* next = pos->next->next; cur->next = NULL; cur->pevr = NULL; free(cur); cur = NULL; pos->next = next; //若next不为空则将前一个链接到pos if (next != NULL) { next->pevr = pos; } } int main() { BSTLNode* sl = NULL; BSTLPushFront(&sl, 1); BSTLPushFront(&sl, 2); BSTLPushFront(&sl, 3); BSTLPrint(sl);//打印 BSTLPopFront(&sl); BSTLPopFront(&sl); BSTLPopFront(&sl); BSTLPrint(sl);//打印 BSTLPushBank(&sl, 5); BSTLPushBank(&sl, 6); BSTLPushBank(&sl, 7); BSTLPrint(sl);//打印 BSTLPopBank(&sl); BSTLPopBank(&sl); BSTLPrint(sl);//打印 BSTLNode* ret = BSTLFind(&sl, 5); printf("%d\n", ret->data); BSTLInsert(&sl, ret, 9); BSTLInsert(&sl, NULL, 8); BSTLInsert(&sl, sl, 7); BSTLPrint(sl);//打印 BSTLErase(&sl, ret); BSTLPrint(sl);//打印 //BSTLErase(&sl, NULL); BSTLErase(&sl, sl); BSTLPrint(sl);//打印 BSTLInsertAfter(ret, 89); BSTLPrint(sl);//打印 //BSTLInsertAfter(NULL, 89); BSTLInsertAfter(ret->pevr, 89); BSTLPrint(sl);//打印 BSTLEraseAfter(ret); BSTLPrint(sl);//打印 BSTLEraseAfter(ret->pevr); BSTLPrint(sl);//打印 //BSTLEraseAfter(NULL); BSTLPrint(sl);//打印 BSTLEraseAfter(sl); BSTLPrint(sl);//打印 BSTLEraseAfter(sl); BSTLPrint(sl);//打印 //BSTLEraseAfter(sl); BSTLPrint(sl);//打印 return 0; }
双向带头链表
节点中存放数据以及两个指针，一个是指向前一个节点的指针，另一个是指向下一个节点的指针，且会单独开辟一个节点空间用来做哨兵位的头节点，一般哨兵位的头节点不存放有效数据。
代码：
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int DataType; //创建结构 typedef struct BHSTLNode { DataType data; struct BHSTLNode* pevr; struct BHSTLNode* next; }BHSTLNode; //初始化（创建带哨兵位的头节点） void BHSTLInit(BHSTLNode** pphead, DataType x) { BHSTLNode* cur = (BHSTLNode*)malloc(sizeof(BHSTLNode)); if (cur == NULL) { perror("malloc fail"); return; } //开辟成功，进行赋值 cur->data = x; cur->next = NULL; cur->pevr = NULL; *pphead = cur; } //创建节点（开辟空间） BHSTLNode* BHSTLSpace(DataType x) { BHSTLNode* newnode = (BHSTLNode*)malloc(sizeof(BHSTLNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->data = x; newnode->next = NULL; newnode->pevr = NULL; return newnode; } //打印 void BHSTLPrint(BHSTLNode* phead) { BHSTLNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } //头插 void BHSTLPushFront(BHSTLNode** pphead, DataType x) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //创建节点 BHSTLNode* newnode = BHSTLSpace(x); //进行插入 BHSTLNode* cur = (*pphead)->next; (*pphead)->next = newnode; newnode->pevr = (*pphead); newnode->next = cur; if (cur != NULL) { cur->pevr = newnode; } } //头删 void BHSTLPopFront(BHSTLNode** pphead) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //头节点的下一个节点为NULL不可删除 assert((*pphead)->next); //进行删除 BHSTLNode* head = (*pphead)->next; BHSTLNode* cur = head->next; head->next = NULL; head->pevr = NULL; free(head); head = NULL; (*pphead)->next = cur; if (cur != NULL) { cur->pevr = (*pphead); } } //尾插 void BHSTLPushBank(BHSTLNode** pphead, DataType x) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //创建节点 BHSTLNode* newnode = BHSTLSpace(x); //找尾进行插入 BHSTLNode* cur = *pphead; while (cur->next) { cur = cur->next; } cur->next = newnode; newnode->pevr = cur; newnode->next = NULL; } //尾删 void BHSTLPopBank(BHSTLNode** pphead) { //带哨兵位的头节点不能为空 assert(pphead); assert(*pphead); //只有哨兵位的头节点一个节点的时候不能删除 assert((*pphead)->next); //找尾删除 BHSTLNode* cur = *pphead; while (cur->next) { cur = cur->next; } BHSTLNode* pevr = cur->pevr; cur->pevr = NULL; cur->next = NULL; free(cur); cur = NULL; pevr->next = NULL; } //查找 BHSTLNode* BHSTLFind(BHSTLNode** pphead, DataType x) { //带哨兵位的头节点必须存在 assert(pphead); assert(*pphead); BHSTLNode* cur = (*pphead)->next; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //在pos位置前插入 void BHSTLInsert(BHSTLNode** pphead, BHSTLNode* pos, DataType x) { //哨兵位的头节点必须存在 assert(*pphead); assert(pphead); //pos不能为哨兵位的头节点 if (pos == (*pphead)) { perror("pos == (*pphead)"); return; } //pos为空的情况就是尾插 if (pos == NULL) { BHSTLPushBank(pphead, x); return; } //获取节点 BHSTLNode* newnode = BHSTLSpace(x); //其余情况 BHSTLNode* pevr = pos->pevr; pevr->next = newnode; newnode->pevr = pevr; newnode->next = pos; pos->pevr = newnode; } //在pos位置前删除 void BHSTLErase(BHSTLNode** pphead, BHSTLNode* pos) { //哨兵位的头节点 assert(pphead); assert(*pphead); //仅有哨兵位头节点一个节点时不可删除 assert((*pphead)->next); //pos的前一个节点为头节点则不能删除 if (pos->pevr == (*pphead)) { perror("pos->pevr == (*pphead)"); return; } //pos为哨兵位的头节点则不能删除前面的 if (pos == (*pphead)) { perror("pos == (*pphead)"); exit; } //pos为哨兵位头节点的下一个节点则不能删除前一个节点 if (pos == (*pphead)->next) { perror("pos == (*pphead)->next"); return; } //pos为NULL就是尾删 if (pos == NULL) { BHSTLPopBank(pphead); return; } //其余情况 BHSTLNode* pevr = pos->pevr; BHSTLNode* ppevr = pevr->pevr; pevr->next = NULL; pevr->pevr = NULL; free(pevr); ppevr->next = pos; } //在pos位置后插入 void BHSTLInsertAfter(BHSTLNode* pos, DataType x) { //pos为空不能插入 assert(pos); //创建节点 BHSTLNode* newnode = BHSTLSpace(x); //直接插入 BHSTLNode* cur = pos->next; pos->next = newnode; newnode->next = cur; newnode->pevr = pos; } //在pos位置后删除 void BHSTLEraseAfter(BHSTLNode* pos) { //pos不能为空，为空则不能删除 assert(pos); //pos的下一个为NULL，则不能删除 assert(pos->next); //进行删除 BHSTLNode* cur = pos->next; BHSTLNode* next = pos->next->next; cur->next = NULL; cur->pevr = NULL; free(cur); cur = NULL; pos->next = next; if (next != NULL) { next->pevr = pos; } } //销毁 void BHSTLDestroy(BHSTLNode** pphead) { //哨兵位的头节点不能为NULL assert(pphead); assert(*pphead); //循环遍历销毁 BHSTLNode* cur = *pphead; BHSTLNode* next = *pphead; while (cur) { next = cur - next; cur->next = NULL; cur->pevr = NULL; cur->data = 0; free(cur); cur = next;; } *pphead = NULL; } int main() { BHSTLNode* sl; //头节点 BHSTLInit(&sl, 0); BHSTLPrint(sl);//打印 //头插 BHSTLPushFront(&sl, 1); BHSTLPushFront(&sl, 2); BHSTLPushFront(&sl, 3); BHSTLPrint(sl);//打印 //头删 BHSTLPopFront(&sl); BHSTLPrint(sl);//打印 BHSTLPopFront(&sl); BHSTLPrint(sl);//打印 BHSTLPopFront(&sl); BHSTLPrint(sl);//打印 //尾插 BHSTLPushBank(&sl, 6); BHSTLPushBank(&sl, 7); BHSTLPushBank(&sl, 8); BHSTLPrint(sl);//打印 //尾删 BHSTLPopBank(&sl); BHSTLPrint(sl);//打印 BHSTLPopBank(&sl); BHSTLPrint(sl);//打印 //BHSTLPopBank(&sl); //BHSTLPrint(sl);//打印 //BHSTLPopBank(&sl); //BHSTLPrint(sl);//打印 //查找 BHSTLNode* ret = BHSTLFind(&sl, 6); printf("%d\n", ret->data); //在pos位置前插入 BHSTLInsert(&sl, ret, 9); BHSTLPrint(sl);//打印 BHSTLInsert(&sl, ret->pevr, 10); BHSTLPrint(sl);//打印 //在pos位置前删除 BHSTLErase(&sl, ret); BHSTLPrint(sl);//打印 //BHSTLErase(&sl, ret->pevr); //BHSTLPrint(sl);//打印 return 0; }
双向循环链表
节点中存放数据以及两个指针，一个是指向前一个节点的指针，另一个是指向下一个节点的指针，且尾节点中指向下一个节点的指针存放的是头节点的地址，头节点中的指向前一个节点的指针存放的是尾节点的地址。
代码：
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int DataType; //创建结构 typedef struct BPLSTNode { DataType data; struct BPLSTNode* pevr; struct BPLSTNode* next; }BPLSTNode; //创建节点 BPLSTNode* BPLSTSpace(DataType x) { //开辟空间 BPLSTNode* newnode = (BPLSTNode*)malloc(sizeof(BPLSTNode)); //判断是否开辟成功 if (newnode == NULL) { perror("malloc fail"); return NULL; } //开辟成功进行初始化 newnode->data = x; newnode->next = NULL; newnode->pevr = NULL; return newnode; } //打印 void BPLSTPrint(BPLSTNode* head) { if (head == NULL) { printf("NULL\n"); return; } printf("%d->", head->data); BPLSTNode* cur = head->next; //仅有一个节点的情况 //两个及多个的情况 while (cur != head) { printf("%d->", cur->data); cur = cur->next; } printf("head\n"); } //头插 void BPLSTPushFront(BPLSTNode** pphead, DataType x) { //断言指针 assert(pphead); //获取节点 BPLSTNode* newnode = BPLSTSpace(x); //为空的情况下直接插入 if ((*pphead) == NULL) { newnode->next = newnode; newnode->pevr = newnode; *pphead = newnode; return; } //存在节点的情况下 BPLSTNode* cur = *pphead; BPLSTNode* tail = (*pphead)->pevr; newnode->next = cur; cur->pevr = newnode; newnode->pevr = tail; tail->next = newnode; *pphead = newnode; } //头删 void BPLSTPopFront(BPLSTNode** pphead) { //为空的情况下不能删除 assert(pphead); assert(*pphead); //不为空的情况下进行删除 //仅有头节点一个节点的情况下。 if ((*pphead)->next == (*pphead)) { (*pphead)->next = NULL; (*pphead)->pevr = NULL; free(*pphead); *pphead = NULL; return; } //两个及多个节点的情况 BPLSTNode* tail = (*pphead)->pevr; BPLSTNode* cur = *pphead; BPLSTNode* next = (*pphead)->next; cur->next = NULL; cur->pevr = NULL; free(cur); tail->next = next; next->pevr = tail; *pphead = next; } //尾插 void BPLSTPushBank(BPLSTNode** pphead, DataType x) { //断言指针 assert(pphead); //获取节点 BPLSTNode* newnode = BPLSTSpace(x); //无节点的情况下直接插入 if ((*pphead) == NULL) { newnode->next = newnode; newnode->pevr = newnode; *pphead = newnode; return; } //存在节点的情况 //尾部直接插入 BPLSTNode* tail = (*pphead)->pevr; BPLSTNode* cur = *pphead; tail->next = newnode; newnode->pevr = tail; newnode->next = cur; cur->pevr = newnode; } //尾删 void BPLSTPopBank(BPLSTNode** pphead) { //无节点的情况下不能删除 assert(pphead); assert(*pphead); //只有头节点一个节点的情况下 //直接释放处理 if ((*pphead)->next == (*pphead)) { (*pphead)->next = NULL; (*pphead)->pevr = NULL; free(*pphead); (*pphead) = NULL; return; } //有两个或两个以上节点的情况下进行找尾。 BPLSTNode* cur = *pphead; BPLSTNode* pevr = *pphead; while (cur->next != (*pphead)) { pevr = cur; cur = cur->next; } //进行释放链接 cur->next = NULL; cur->pevr = NULL; free(cur); cur = NULL; pevr->next = (*pphead); (*pphead)->pevr = pevr; } //查找 BPLSTNode* BPLSTFand(BPLSTNode** pphead, DataType x) { //没有节点的情况无法插入 assert(pphead); assert(*pphead); //存在节点的情况下遍历查找 if ((*pphead)->data == x) { return (*pphead); } BPLSTNode* cur = (*pphead)->next; while (cur != (*pphead)) { if (cur->data == x) { return cur; } } return NULL; } //在pos位置前插入 void BPLSTInsert(BPLSTNode** pphead, BPLSTNode* pos, DataType x) { //断言指针 assert(pphead); //获取节点 BPLSTNode* newnode = BPLSTSpace(x); //无节点的情况下且pos为NULL就是头插 if ((*pphead) == NULL) { if (pos == NULL) { //头插 BPLSTPushFront(pphead, x); } else { perror((*pphead) == NULL && pos != NULL); } return; } //存在节点的情况（头不为NULL的情况） if ((*pphead) != NULL && pos == NULL) { perror((*pphead) != NULL && pos == NULL); return; } //正常可以插入的情况 //pos为头节点的情况下 if ((*pphead) == pos) { //就是头插 BPLSTPushFront(pphead, x); return; } //pos不为头的情况 BPLSTNode* cur = *pphead; BPLSTNode* pevr = *pphead; while (cur != pos) { pevr = cur; cur = cur->next; } //插入并链接 pevr->next = newnode; newnode->pevr = pevr; newnode->next = pos; pos->pevr = newnode; } //在pos位置前删除 void BPLSTEaser(BPLSTNode** pphead, BPLSTNode* pos) { //无节点的情况下皆不可删除 assert(pphead); assert(*pphead); //pos为空不能删除 assert(pos); //查找pos是否是该链表中的节点 //……………………省略……………… //若pos为头节点 if ((*pphead) == pos) { //进行尾删 BPLSTPopBank(pphead); return; } //pos不为头节点的情况 //pos是头节点的下一个节点的情况 if ((*pphead)->next == pos) { //直接删除头 BPLSTNode* pevr = (*pphead)->pevr; (*pphead)->next = NULL; (*pphead)->pevr = NULL; free(*pphead); pos->pevr = pevr; pevr->next = pos; *pphead = pos; return; } //pos即不为头节点也不是头节点的下一个节点的情况 BPLSTNode* cur = *pphead; BPLSTNode* pevr = cur->pevr; //循环遍历找pos while (cur->next != pos) { pevr = cur; cur = cur->next; } cur->next = NULL; cur->pevr = NULL; free(cur); cur = NULL; pevr->next = pos; pos->pevr = pevr; } //在pos位置后插入 void BPLSTInsertAfter(BPLSTNode** pphead, BPLSTNode* pos, DataType x) { //断言指针 assert(pphead); //不存在节点的情况 if ((*pphead) == NULL) { //pos为空的情况 if (pos == NULL) { //尾插 BPLSTPushBank(pphead, x); } else //pos不为空的情况 { //无法插入,直接断言 assert(pos); } return; } //存在节点的情况 //pos为NULL 无法插入 if (pos == NULL) { assert(pos); return; } //pos不为NULL的情况 //获取节点 BPLSTNode* newnode = BPLSTSpace(x); //进行插入链接 BPLSTNode* next = pos->next; pos->next = newnode; newnode->pevr = pos; newnode->next = next; next->pevr = newnode; } //在pos位置后删除 void BPLSTEaserAfter(BPLSTNode** pphead, BPLSTNode* pos) { //不存在节点无法删除 assert(pphead); assert(*pphead); //pos为空无法删除 assert(pos); //pos为头节点 if (pos == (*pphead)) { //仅有头节点一个节点的情况 if ((*pphead)->next == (*pphead)) { (*pphead)->next = NULL; (*pphead)->pevr = NULL; free(*pphead); *pphead = NULL; } else { BPLSTNode* cur = pos->next; BPLSTNode* next = cur->next; cur->next = NULL; cur->pevr = NULL; free(cur); cur = NULL; pos->next = next; next->pevr = pos; } return; } //pos为尾节点的情况 if (pos == (*pphead)->pevr) { //仅有pos和头节点两个节点的情况 if ((*pphead)->next == pos) { (*pphead)->next = NULL; (*pphead)->pevr = NULL; free(*pphead); pos->next = pos; pos->pevr = pos; *pphead = pos; } else//具有三个节点的情况，且头节点的下一个节点不是pos { BPLSTNode* cur = pos->next; BPLSTNode* next = cur->next; cur->next = NULL; cur->pevr = NULL; free(cur); cur = NULL; pos->next = next; next->pevr = pos; *pphead = next; } return; } //pos不为尾的情况 BPLSTNode* cur = pos->next; BPLSTNode* next = cur->next; cur->next = NULL; cur->pevr = NULL; free(cur); cur = NULL; pos->next = next; next->pevr = pos; } int main() { BPLSTNode* sl = NULL; //头插 BPLSTPushFront(&sl, 1); BPLSTPushFront(&sl, 2); BPLSTPushFront(&sl, 3); BPLSTPrint(sl);//打印 //头删 BPLSTPopFront(&sl); BPLSTPopFront(&sl); BPLSTPrint(sl);//打印 //尾插 BPLSTPushBank(&sl, 5); BPLSTPushBank(&sl, 6); BPLSTPushBank(&sl, 7); BPLSTPrint(sl);//打印 //尾删 BPLSTPopBank(&sl); BPLSTPopBank(&sl); BPLSTPopBank(&sl); BPLSTPrint(sl);//打印 //查找 BPLSTNode* ret = BPLSTFand(&sl, 1); if (ret != NULL) printf("%d\n", ret->data); else printf("ret==NULL\n"); //在pos位置前插入 BPLSTInsert(&sl, ret, 5); BPLSTInsert(&sl, ret->pevr, 6); BPLSTPrint(sl);//打印 //在pos位置前删除 BPLSTEaser(&sl, ret->next); BPLSTPrint(sl);//打印 ret = BPLSTFand(&sl, 5); if (ret != NULL) printf("%d\n", ret->data); else printf("ret==NULL\n"); //在pos位置后插入 BPLSTInsertAfter(&sl, ret, 7); BPLSTInsertAfter(&sl, ret, 8); BPLSTPrint(sl);//打印 //在pos位置后删除 BPLSTEaserAfter(&sl, ret); BPLSTPrint(sl);//打印 ret = BPLSTFand(&sl, 6); if (ret != NULL) printf("%d\n", ret->data); else printf("ret==NULL\n"); //在pos位置后删除 BPLSTEaserAfter(&sl, ret); BPLSTPrint(sl);//打印 BPLSTEaserAfter(&sl, ret); BPLSTPrint(sl);//打印 BPLSTEaserAfter(&sl, ret); BPLSTPrint(sl);//打印 return 0; }
双向带头循环链表
节点中存放数据以及两个指针，一个是指向前一个节点的指针，另一个是指向下一个节点的指针，会单独开辟一个节点空间用来做哨兵位的头节点，一般哨兵位头节点中不存放有效数据，且尾节点中指向下一个节点的指针存放的是哨兵位头节点的地址，哨兵位头节点中的指向前一个节点的指针存放的是尾节点的地址。
代码：
#define _CRT_DECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <assert.h> //创建结构 typedef int DataType; typedef struct BHPSTLNode { DataType data; struct BHPSTLNode* pevr; struct BHPSTLNode* next; }BHPSTLNode; //初始化哨兵位头节点 void BHPSTLInit(BHPSTLNode** pphead, DataType x) { //申请空间 BHPSTLNode* newnode = (BHPSTLNode*)malloc(sizeof(BHPSTLNode)); if (newnode == NULL) { perror("malloc fail 12link"); return; } //申请成功后进行赋值 newnode->next = newnode; newnode->pevr = newnode; newnode->data = x; *pphead = newnode; } //打印 void BHPSTLPrint(BHPSTLNode* phead) { //空链表直接打印 if (phead == NULL) { printf("NULL\n"); return; } //打印哨兵位的头节点 printf("%d->", phead->data); BHPSTLNode* cur = phead->next; while (cur != phead) { printf("%d->", cur->data); cur = cur->next; } printf("phead\n"); } //创建节点 BHPSTLNode* BHPSTLSpace(DataType x) { //创建节点 BHPSTLNode* newnode = (BHPSTLNode*)malloc(sizeof(BHPSTLNode)); if (newnode == NULL) { perror("malloc fail 51 link"); return NULL; } //创建成功进行链接 newnode->data = x; newnode->next = NULL; newnode->pevr = NULL; return newnode; } //头插 void BHPSTLPushFront(BHPSTLNode** pphead, DataType x) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //创建节点 BHPSTLNode* newnode = BHPSTLSpace(x); //直接进行插入 BHPSTLNode* next = (*pphead)->next; (*pphead)->next = newnode; newnode->pevr = (*pphead); newnode->next = next; next->pevr = newnode; } //头删 void BHPSTLPopFront(BHPSTLNode** pphead) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //仅有哨兵位的头节点一个节点不能删除 if ((*pphead)->pevr == (*pphead)) { assert(NULL); } //具有两个及多个节点的情况 //进行删除 BHPSTLNode* cur = (*pphead)->next; BHPSTLNode* next = cur->next; cur->next = NULL; cur->pevr = NULL; free(cur); cur = NULL; (*pphead)->next = next; next->pevr = (*pphead); } //尾插 void BHPSTLPushBank(BHPSTLNode** pphead, DataType x) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //创建节点 BHPSTLNode* newnode = BHPSTLSpace(x); //找尾 BHPSTLNode* tail = (*pphead)->pevr; //插入 tail->next = newnode; newnode->pevr = tail; newnode->next = (*pphead); (*pphead)->pevr = newnode; } //尾删 void BHPSTLPopBank(BHPSTLNode** pphead) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //仅有哨兵位的头节点一个节点无法删除 if ((*pphead)->next == (*pphead)) { assert(NULL); } //找尾和尾的前一个释放链接 BHPSTLNode* tail = (*pphead)->pevr; BHPSTLNode* pevr = tail->pevr; tail->next = NULL; tail->pevr = NULL; free(tail); tail = NULL; pevr->next = (*pphead); (*pphead)->pevr = pevr; } //查找 BHPSTLNode* BHPSTLFind(BHPSTLNode* phead, DataType x) { //断言指针 assert(phead); //循环遍历查找 BHPSTLNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //在pos位置前插入 void BHPSTLInsert(BHPSTLNode** pphead, BHPSTLNode* pos, DataType x) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //若pos为空无法插入 assert(pos); //判断pos是否存在于该链表中 //………… 省略 ………… //获取节点 BHPSTLNode* newnode = BHPSTLSpace(x); BHPSTLNode* pevr = pos->pevr; pevr->next = newnode; newnode->pevr = pevr; newnode->next = pos; pos->pevr = newnode; } //在pos位置前删除 void BHPSTLErase(BHPSTLNode** pphead, BHPSTLNode* pos) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //pos为空无法删除 assert(pos); //判断pos是否存在于该链表中 //………… 省略 ………… //若pos为哨兵位头节点的下一个节点 //无法删除（即哨兵位的头节点无法删除） //若pos为哨兵位的头节点 //且仅有头节点一个节点的情况无法删除 if ((*pphead)->next == pos) { assert(NULL); return; } //其余情况 BHPSTLNode* cur = pos->pevr; BHPSTLNode* pevr = cur->pevr; cur->next = NULL; cur->pevr = NULL; free(cur); cur = NULL; pevr->next = pos; pos->pevr = pevr; } //在pos位置后插入 void BHPSTLInsertAfter(BHPSTLNode** pphead, BHPSTLNode* pos, DataType x) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //pos为空无法插入 assert(pos); //判断pos是否存在于该链表中 //………… 省略 ………… //创建节点 BHPSTLNode* newnode = BHPSTLSpace(x); BHPSTLNode* next = pos->next; pos->next = newnode; newnode->pevr = pos; newnode->next = next; next->pevr = newnode; } //在pos位置后删除 void BHPSTLEraseAfter(BHPSTLNode** pphead, BHPSTLNode* pos) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //pos为NULL不能删除 assert(pos); //判断pos是否存在于该链表中 //………… 省略 ………… //若pos为尾节点无法删除 //(尾节点的下一个节点是哨兵位的头节点) //若仅有哨兵位头节点一个节点 //且pos为哨兵位头节点的情况无法删除 if (pos->next == (*pphead)) { assert(NULL); } //其余情况 BHPSTLNode* cur = pos->next; BHPSTLNode* next = cur->next; cur->next = NULL; cur->pevr = NULL; free(cur); cur = NULL; pos->next = next; next->pevr = pos; } //销毁 void BHPSTLDestroy(BHPSTLNode** pphead) { //哨兵位的头节点必须存在 assert(pphead); assert(*pphead); //循环遍历销毁 BHPSTLNode* cur = (*pphead)->next; BHPSTLNode* next = (*pphead)->next; while (cur != (*pphead)) { next = cur->next; cur->next = NULL; cur->pevr = NULL; free(cur); cur = next; } cur->pevr = NULL; cur->next = NULL; free(cur); cur = NULL; (*pphead) = NULL; } int main() { BHPSTLNode* sl = NULL; //初始化哨兵位头节点 BHPSTLInit(&sl, 0); BHPSTLPrint(sl);//打印 //头插 BHPSTLPushFront(&sl, 1); BHPSTLPushFront(&sl, 2); BHPSTLPushFront(&sl, 3); BHPSTLPrint(sl);//打印 //头删 BHPSTLPopFront(&sl); BHPSTLPrint(sl);//打印 BHPSTLPopFront(&sl); BHPSTLPrint(sl);//打印 BHPSTLPopFront(&sl); BHPSTLPrint(sl);//打印 //尾插 BHPSTLPushBank(&sl, 5); BHPSTLPushBank(&sl, 6); BHPSTLPushBank(&sl, 7); BHPSTLPrint(sl);//打印 //尾删 BHPSTLPopBank(&sl); BHPSTLPrint(sl);//打印 //BHPSTLPopBank(&sl); //BHPSTLPrint(sl);//打印 //BHPSTLPopBank(&sl); //BHPSTLPrint(sl);//打印 //查找 BHPSTLNode* ret = BHPSTLFind(sl, 6); if (ret == NULL) printf("find: NULL\n"); else printf("Find : %d\n", ret->data); //在pos位置前插入 BHPSTLInsert(&sl, ret, 8); BHPSTLPrint(sl);//打印 BHPSTLInsert(&sl, ret->pevr, 9); BHPSTLPrint(sl);//打印 BHPSTLInsert(&sl, ret->pevr->pevr, 10); BHPSTLPrint(sl);//打印 //在pos位置前删除 BHPSTLErase(&sl, ret); BHPSTLPrint(sl);//打印 BHPSTLErase(&sl, ret); BHPSTLPrint(sl);//打印 BHPSTLErase(&sl, ret); BHPSTLPrint(sl);//打印 BHPSTLErase(&sl, ret); BHPSTLPrint(sl);//打印 //BHPSTLErase(&sl, sl); //BHPSTLPrint(sl);//打印 //BHPSTLErase(&sl, sl); //BHPSTLPrint(sl);//打印 //在pos位置后插入 BHPSTLInsertAfter(&sl, ret, 9); BHPSTLPrint(sl);//打印 BHPSTLInsertAfter(&sl, sl, 7); BHPSTLPrint(sl);//打印 //在pos位置后删除 BHPSTLEraseAfter(&sl, ret); BHPSTLPrint(sl);//打印 //BHPSTLEraseAfter(&sl, ret->pevr); //BHPSTLPrint(sl);//打印 BHPSTLEraseAfter(&sl, sl); BHPSTLPrint(sl);//打印 BHPSTLEraseAfter(&sl, sl); BHPSTLPrint(sl);//打印 //BHPSTLEraseAfter(&sl, sl); //BHPSTLPrint(sl);//打印 //销毁 BHPSTLDestroy(&sl); BHPSTLPrint(sl);//打印 return 0; }
以上为自写8种链表代码，各位铁子欢迎讨论。
原文地址：https://blog.csdn.net/dd811923461/article/details/143866591
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！