如何用C语言实现带头双向循环链表来存储长尾词？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1789个文字，预计阅读时间需要8分钟。
链表，种类多样，有带哨兵位的，有循环的，还有双向的。排列组合后，你会发现八种不同的链表。其中，结构最简单的就是单链表了，而结构最复杂的是带头双向循环链表。
链表，种类众多，有带哨兵位的，有循环的，还有双向的，排列组合后，你会发现有8种不同的链表。其中，结构最简单的就是单链表了，结构最复杂的则是带头双向循环链表。
但是，别看他结构最复杂，其实他的实现反而是最简单的。
数据结构的操作，就是操作内存中的数据，也就是增删查改这些操作；那么，就让我们来看看带头双向循环链表的增删查改吧。
1.首先是结构的定义：
很明显，和单链表相比，我们多了一个prev指针。
typedef int SLDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
SLDataType data;
}LTNode;
2.接着就是链表的初始化：
Buy函数就是创建并初始化一个节点，写成函数复用更方便。
LTNode* Buy(int x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("newnode malloc");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
LTNode* LTInit()
{
LTNode* phead = Buy(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
3.尾插
以前我们写单链表的时候尾插先要while循环找到尾前面那个节点，再尾插，时间复杂度很显然是O(N)，但是现在我们实现尾插就很简单了，时间复杂度是O(1)：
void LTPushBack(LTNode* phead, SLDataType x)
{
assert(phead);
LTNode* newnode = Buy(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
而且单链表尾插还要分链表为空和不为空的时候，这里就不用了。
4.尾删
当链表为空的时候再删除很显然就错了，所以我们可以写一个判断链表是否为空的函数，一是可以复用，二来 assert 报错的时候可以很清楚错在了哪里。
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* tail = phead->prev;
LTNode* nexttail = tail->prev;
free(tail);
tail = NULL;
phead->prev = nexttail;
nexttail->next = phead;
}
在尾删的时候，我们可以用一个nextTail指针指向尾巴的前一个节点再写，也可以直接写，都可以，但是直接写的话就要注意好写的顺序，一旦写错顺序就GG了；而用指针的话，顺序就无所谓了，怎么写都行。
单链表在尾删的时候时间复杂度也是O(N)，这里复杂度很明显：O(1）。
5.头插、头删
void LTPushFront(LTNode* phead, SLDataType x)
{
assert(phead);
LTNode* newnode = Buy(x);
LTNode* tail = phead->prev;
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
assert(phead->next != phead);
LTNode* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
free(del);
del = NULL;
}
也没什么好说的，时间复杂仍然是O(1)；
6.打印
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("guard <==> ");
while (cur != phead)
{
printf("%d <==> ", cur->data);
cur = cur->next;
}
printf("guard\n");
}
最后的效果是这样的：
7.查找
这里时间复杂度就是O(N)了，循环一次查找 data == x 的节点，返回该位置的指针：
SLTNode* SLFind(SLTNode* phead, SLDataType x)
{
SLTNode* find = phead;
while (find)
{
if (find->data == x)
{
return find;
}
find = find->next;
}
return NULL;
}
这里要修改节点数据的话就直接在查找函数后面跟上一行就行了，不用再单独写一个修改函数了。
8.在任意位置之前插入 、 任意位置删除
依然是配合着查找函数食用，效果会比较好：
void LTInsert(LTNode* pos, SLDataType x)//在该位置前面插入
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* newnode = Buy(x);
posPrev->next = newnode;
newnode->next = pos;
newnode->prev = posPrev;
pos->prev = newnode;
}
void LTErase(LTNode* pos)//任意位置删除
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
free(pos);
posPrev->next = posNext;
posNext->prev = posPrev;
}
9.销毁
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
LTNode* curNext = cur->next;
while (cur != phead)
{
free(cur);
printf("...\n");
cur = curNext;
curNext = cur->next;
}
printf("已销毁\n");
}
最后的样子：
咱就是说追求一个大道至简。
贷马奉上：
头文件：
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int SLDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
SLDataType data;
}LTNode;
LTNode* LTInit();
void LTPushBack(LTNode* phead, SLDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, SLDataType x);
void LTPopFront(LTNode* phead);
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead);
LTNode* LTFind(LTNode* phead, int x);
void LTInsert(LTNode* pos, SLDataType x);
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);
源文件：
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
LTNode* Buy(int x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("newnode malloc");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
LTNode* LTInit()
{
LTNode* phead = Buy(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
void LTPushBack(LTNode* phead, SLDataType x)
{
assert(phead);
LTNode* newnode = Buy(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* tail = phead->prev;
LTNode* nexttail = tail->prev;
free(tail);
tail = NULL;
phead->prev = nexttail;
nexttail->next = phead;
}
void LTPushFront(LTNode* phead, SLDataType x)
{
assert(phead);
/*if (LTEmpty(phead))
{
LTPushBack(phead, x);
}
else
{
LTNode* newnode = Buy(x);
LTNode* tail = phead->prev;
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}*/
LTNode* newnode = Buy(x);
LTNode* tail = phead->prev;
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
assert(phead->next != phead);
LTNode* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
free(del);
del = NULL;
}
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("guard <==> ");
while (cur != phead)
{
printf("%d <==> ", cur->data);
cur = cur->next;
}
printf("guard\n");
}
LTNode* LTFind(LTNode* phead, int x)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* pos = phead->next;
while (pos != phead)
{
if (pos->data == x)
{
return pos;
}
pos = pos->next;
}
return NULL;
}
void LTInsert(LTNode* pos, SLDataType x)//在该位置前面插入
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* newnode = Buy(x);
posPrev->next = newnode;
newnode->next = pos;
newnode->prev = posPrev;
pos->prev = newnode;
}
void LTErase(LTNode* pos)//任意位置删除
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
free(pos);
posPrev->next = posNext;
posNext->prev = posPrev;
}
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
LTNode* curNext = cur->next;
while (cur != phead)
{
free(cur);
printf("...\n");
cur = curNext;
curNext = cur->next;
}
printf("已销毁\n");
}
别找辣！没有test函数。。。
本文共计1789个文字，预计阅读时间需要8分钟。
链表，种类多样，有带哨兵位的，有循环的，还有双向的。排列组合后，你会发现八种不同的链表。其中，结构最简单的就是单链表了，而结构最复杂的是带头双向循环链表。
链表，种类众多，有带哨兵位的，有循环的，还有双向的，排列组合后，你会发现有8种不同的链表。其中，结构最简单的就是单链表了，结构最复杂的则是带头双向循环链表。
但是，别看他结构最复杂，其实他的实现反而是最简单的。
数据结构的操作，就是操作内存中的数据，也就是增删查改这些操作；那么，就让我们来看看带头双向循环链表的增删查改吧。
1.首先是结构的定义：
很明显，和单链表相比，我们多了一个prev指针。
typedef int SLDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
SLDataType data;
}LTNode;
2.接着就是链表的初始化：
Buy函数就是创建并初始化一个节点，写成函数复用更方便。
LTNode* Buy(int x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("newnode malloc");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
LTNode* LTInit()
{
LTNode* phead = Buy(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
3.尾插
以前我们写单链表的时候尾插先要while循环找到尾前面那个节点，再尾插，时间复杂度很显然是O(N)，但是现在我们实现尾插就很简单了，时间复杂度是O(1)：
void LTPushBack(LTNode* phead, SLDataType x)
{
assert(phead);
LTNode* newnode = Buy(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
而且单链表尾插还要分链表为空和不为空的时候，这里就不用了。
4.尾删
当链表为空的时候再删除很显然就错了，所以我们可以写一个判断链表是否为空的函数，一是可以复用，二来 assert 报错的时候可以很清楚错在了哪里。
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* tail = phead->prev;
LTNode* nexttail = tail->prev;
free(tail);
tail = NULL;
phead->prev = nexttail;
nexttail->next = phead;
}
在尾删的时候，我们可以用一个nextTail指针指向尾巴的前一个节点再写，也可以直接写，都可以，但是直接写的话就要注意好写的顺序，一旦写错顺序就GG了；而用指针的话，顺序就无所谓了，怎么写都行。
单链表在尾删的时候时间复杂度也是O(N)，这里复杂度很明显：O(1）。
5.头插、头删
void LTPushFront(LTNode* phead, SLDataType x)
{
assert(phead);
LTNode* newnode = Buy(x);
LTNode* tail = phead->prev;
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
assert(phead->next != phead);
LTNode* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
free(del);
del = NULL;
}
也没什么好说的，时间复杂仍然是O(1)；
6.打印
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("guard <==> ");
while (cur != phead)
{
printf("%d <==> ", cur->data);
cur = cur->next;
}
printf("guard\n");
}
最后的效果是这样的：
7.查找
这里时间复杂度就是O(N)了，循环一次查找 data == x 的节点，返回该位置的指针：
SLTNode* SLFind(SLTNode* phead, SLDataType x)
{
SLTNode* find = phead;
while (find)
{
if (find->data == x)
{
return find;
}
find = find->next;
}
return NULL;
}
这里要修改节点数据的话就直接在查找函数后面跟上一行就行了，不用再单独写一个修改函数了。
8.在任意位置之前插入 、 任意位置删除
依然是配合着查找函数食用，效果会比较好：
void LTInsert(LTNode* pos, SLDataType x)//在该位置前面插入
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* newnode = Buy(x);
posPrev->next = newnode;
newnode->next = pos;
newnode->prev = posPrev;
pos->prev = newnode;
}
void LTErase(LTNode* pos)//任意位置删除
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
free(pos);
posPrev->next = posNext;
posNext->prev = posPrev;
}
9.销毁
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
LTNode* curNext = cur->next;
while (cur != phead)
{
free(cur);
printf("...\n");
cur = curNext;
curNext = cur->next;
}
printf("已销毁\n");
}
最后的样子：
咱就是说追求一个大道至简。
贷马奉上：
头文件：
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int SLDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
SLDataType data;
}LTNode;
LTNode* LTInit();
void LTPushBack(LTNode* phead, SLDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, SLDataType x);
void LTPopFront(LTNode* phead);
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead);
LTNode* LTFind(LTNode* phead, int x);
void LTInsert(LTNode* pos, SLDataType x);
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);
源文件：
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
LTNode* Buy(int x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("newnode malloc");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
LTNode* LTInit()
{
LTNode* phead = Buy(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
void LTPushBack(LTNode* phead, SLDataType x)
{
assert(phead);
LTNode* newnode = Buy(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* tail = phead->prev;
LTNode* nexttail = tail->prev;
free(tail);
tail = NULL;
phead->prev = nexttail;
nexttail->next = phead;
}
void LTPushFront(LTNode* phead, SLDataType x)
{
assert(phead);
/*if (LTEmpty(phead))
{
LTPushBack(phead, x);
}
else
{
LTNode* newnode = Buy(x);
LTNode* tail = phead->prev;
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}*/
LTNode* newnode = Buy(x);
LTNode* tail = phead->prev;
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
assert(phead->next != phead);
LTNode* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
free(del);
del = NULL;
}
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("guard <==> ");
while (cur != phead)
{
printf("%d <==> ", cur->data);
cur = cur->next;
}
printf("guard\n");
}
LTNode* LTFind(LTNode* phead, int x)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* pos = phead->next;
while (pos != phead)
{
if (pos->data == x)
{
return pos;
}
pos = pos->next;
}
return NULL;
}
void LTInsert(LTNode* pos, SLDataType x)//在该位置前面插入
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* newnode = Buy(x);
posPrev->next = newnode;
newnode->next = pos;
newnode->prev = posPrev;
pos->prev = newnode;
}
void LTErase(LTNode* pos)//任意位置删除
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
free(pos);
posPrev->next = posNext;
posNext->prev = posPrev;
}
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
LTNode* curNext = cur->next;
while (cur != phead)
{
free(cur);
printf("...\n");
cur = curNext;
curNext = cur->next;
}
printf("已销毁\n");
}
别找辣！没有test函数。。。