正文

4. 带头双向循环链表的实现

带头双向循环链表看似结构复杂，其实在写代码时你会感到很轻松。其关键就在于它的头结点不一般。此处的头结点不存储有效数据。

4.1结点结构的定义

typedef int LTDataType;
typedef struct ListNode
{
  LTDataType data;
  struct ListNode* prev;//指向前一个结点
  struct ListNode* next;//指向后一个结点
}LTNode;

既然是双向循环链表，那就得要求每个结点既保存下一个结点的地址，又要保存上一个结点的地址。结构中，prev指向前一个结点，next指向后一个结点。

4.2函数接口的实现

//申请一个结点
LTNode* BuyListNode(LTDataType data);
//初始化头结点
LTNode* LTInit();
//释放申请的内存
void LTDestroy(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType data);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType data);
//头删
void LTPopFront(LTNode* phead);
//查找data
LTNode* LTFind(LTNode* phead, LTDataType data);
//在pos位置前插入
void LTInsert(LTNode* phead, LTNode* pos, LTDataType data);
//删除pos位置
void LTErase(LTNode* phead, LTNode* pos);
//判断链表是否为空
bool LTEmpty(LTNode* phead);
//统计链表中数据的个数
size_t LTSize(LTNode* phead);
//打印链表存储的数据
void LTPrint(LTNode* phead);

同样的，由于代码过长，为了避免影响阅读体验，我将完整源码置于文章末尾。带头双向循环链表的各个函数实现都比不带头的单链表简单很多。因此学会了之前单链表的实现，双向链表的实现自然轻松无比。这里就不做赘述。

5.两种链表的差异

①尾插与尾删的时间复杂度

对于单链表而言，尾插与尾删都是它的劣势。因为计算机无法直接访问到链表的尾结点，必须遍历完整个链表才能找到尾结点。所以单链表的尾插与尾删都为O(N)。

对于带头双向循环链表，找尾是极其方便的，因为尾结点就在头结点的前一个，可以一步就访问到。所以，带头双向循环链表的尾插与尾删都为O(1)。

②头插与头删的时间复杂度

两种链表头插与头删都为O(1)。对于链表这种数据结构而言，头插与头删都是其优势。上一章中提到顺序表的尾插与尾删效率极高，但是头插与头删却比较劣势。而链表正好相反，头插与头删效率很高。因此面对不同的场景，要学会使用合适的数据结构。

③函数形参为何一个是二级指针，一个是一级指针？

单链表，我们需要对phead的值做修改。那么就得利用phead的指针。而phead本身就是一个指针，所以函数的形参为pphead的二级指针。

双向循环链表，并不需要对phead做修改，而只是需要访问它prev和next所指向的结点，所以只用一级指针即可。

完整源码

无头单向非循环链表

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
}SLTNode;
//申请一个结点
SLTNode* BuySLTNode(SLTDataType data);
//创建一个链表，包含数据为0~n
SLTNode* CreateSList(int n);
//释放内存
void SLTDestroy(SLTNode** pphead);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType data);
//尾删
void SLTPopBack(SLTNode** pphead);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType data);
//头删
void SLTPopFront(SLTNode** pphead);
//查找data的结点
SLTNode* SLTFind(SLTNode** pphead, SLTDataType data);
//在pos位置前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType data);
//在pos位置后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType data);
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//打印链表内容
void SLTPrint(SLTNode* phead);

SList.c

#define _CRT_SECURE_NO_DEPRECATE 1
#include"SList.h"
SLTNode* BuySLTNode(SLTDataType data)
{
  SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
  //检查是否申请成功
  if (newNode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  //对newNode进行初始化
  newNode->data = data;
  newNode->next = NULL;
  //返回申请成功的结点
  return newNode;
}
SLTNode* CreateSList(int n)
{
  SLTNode* phead = NULL;
  SLTNode* ptail = NULL;
  for (int i = 0; i < n; i++)
  {
    SLTNode* newNode = BuySLTNode(i);
    //若为第一个插入，则分情况处理
    if (phead == NULL)
    {
      phead = ptail = newNode;
    }
    else
    {
      ptail->next = newNode;
      ptail = newNode;
    }
  }
  return phead;
}
void SLTDestroy(SLTNode** pphead)
{
  assert(*pphead);
  SLTNode* cur = *pphead;
  //cur判断何时结束
  while (cur)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}
void SLTPushBack(SLTNode** pphead, SLTDataType data)
{
  SLTNode* newNode = BuySLTNode(data);
  //若为第一次插入，则分情况处理
  if (*pphead==NULL)
  {
    *pphead = newNode;
    return;
  }
  //找尾
  SLTNode* tail = *pphead;
  while(tail->next)
  {
    tail = tail->next;
  }
  //找到了，进行尾插
  tail->next = newNode;
}
void SLTPopBack(SLTNode** pphead)
{
  assert(pphead);
  //分情况处理
  if (*pphead == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  //找尾
  SLTNode* tail = *pphead;
  while (tail->next->next)
  {
    tail = tail->next;
  }
  //找到了，进行尾删
  free(tail->next);
  tail->next = NULL;
}
void SLTPushFront(SLTNode** pphead, SLTDataType data)
{
  SLTNode* newNode = BuySLTNode(data);
  //进行头插
  newNode->next = *pphead;
  *pphead = newNode;
}
void SLTPopFront(SLTNode** pphead)
{
  assert(*pphead);
  //进行头删
  SLTNode* next = (*pphead)->next;
  free(*pphead);
  *pphead = next;
}
SLTNode* SLTFind(SLTNode** pphead, SLTDataType data)
{
  assert(*pphead);
  SLTNode* cur = *pphead;
  while (cur)
  {
    //找到了，返回cur
    if (cur->data == data)
    {
      return cur;
    }
    cur = cur->next;
  }
  //没找到，返回NULL
  return NULL;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType data)
{
  assert(pos);
  SLTNode* newNode = BuySLTNode(data);
  //若pos恰好是phead，相当于进行头插
  if (pos == *pphead)
  {
    SLTPushFront(pphead, data);
    return;
  }
  //找pos前一个指针
  SLTNode* prev = *pphead;
  while (prev->next != pos)
  {
    prev = prev->next;
  }
  //找到了，进行插入
  prev->next = newNode;
  newNode->next = pos;
}
void SLTInsertAfter(SLTNode* pos, SLTDataType data)
{
  assert(pos);
  SLTNode* newNode = BuySLTNode(data);
  SLTNode* next = pos->next;
  pos->next = newNode;
  newNode->next = next;
}
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(pos);
  //若pos恰好就是phead，则相当于头删
  if (pos == *pphead)
  {
    SLTPopFront(pphead);
    return;
  }
  //找pos前一个结点
  SLTNode* prev = *pphead;
  while (prev->next != pos)
  {
    prev = prev->next;
  }
  //找到了，进行删除
  prev->next = pos->next;
  free(pos);
  pos = NULL;
}
void SLTPrint(SLTNode* phead)
{
  assert(phead);
  SLTNode* cur = phead;
  //cur控制何时结束
  while (cur)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}

test.c

#define _CRT_SECURE_NO_DEPRECATE 1
#include"SList.h"
void test()
{
  SLTNode* phead = CreateSList(10);
  SLTPushBack(&phead, 0);
  SLTPushBack(&phead, 0);
  SLTPushBack(&phead, 0);
  SLTPushBack(&phead, 0);
  SLTPushBack(&phead, 0);
  SLTPrint(phead);
  SLTPushFront(&phead, 1);
  SLTPushFront(&phead, 1);
  SLTPushFront(&phead, 1);
  SLTPushFront(&phead, 1);
  SLTPushFront(&phead, 1);
  SLTPrint(phead);
  SLTNode* pos = SLTFind(&phead, 3);
  SLTInsert(&phead, pos, 300);
  SLTInsertAfter(pos, 30);
  SLTPrint(phead);
  SLTPopBack(&phead);
  SLTPopBack(&phead);
  SLTPopBack(&phead);
  SLTPopBack(&phead);
  SLTPopBack(&phead);
  SLTPopFront(&phead);
  SLTPopFront(&phead);
  SLTPopFront(&phead);
  SLTPopFront(&phead);
  SLTPopFront(&phead);
  SLTPrint(phead);
  SLTDestroy(&phead);
}
int main()
{
  test();
  return 0;
}

带头双向循环链表

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
  LTDataType data;
  struct ListNode* prev;//指向前一个结点
  struct ListNode* next;//指向后一个结点
}LTNode;
//申请一个结点
LTNode* BuyListNode(LTDataType data);
//初始化头结点
LTNode* LTInit();
//释放申请的内存
void LTDestroy(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType data);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType data);
//头删
void LTPopFront(LTNode* phead);
//查找data
LTNode* LTFind(LTNode* phead, LTDataType data);
//在pos位置前插入
void LTInsert(LTNode* phead, LTNode* pos, LTDataType data);
//删除pos位置
void LTErase(LTNode* phead, LTNode* pos);
//判断链表是否为空
bool LTEmpty(LTNode* phead);
//统计链表中数据的个数
size_t LTSize(LTNode* phead);
//打印链表存储的数据
void LTPrint(LTNode* phead);

List.c

#define _CRT_SECURE_NO_DEPRECATE 1
#include"List.h"
LTNode* BuyListNode(LTDataType data)
{
  LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
  if (newNode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newNode->data = data;
  newNode->prev = NULL;
  newNode->next = NULL;
  return newNode;
}
LTNode* LTInit()
{
  LTNode* phead = BuyListNode(-1);
  phead->prev = phead;
  phead->next = phead;
  return phead;
}
void LTDestroy(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    LTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  free(phead);
}
void LTPushBack(LTNode* phead, LTDataType data)
{
  assert(phead);
  LTNode* newNode = BuyListNode(data);
  LTNode* tail = phead->prev;
  newNode->next = phead;
  newNode->prev = tail;
  tail->next = newNode;
  phead->prev = newNode;
}
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* tail = phead->prev;
  tail->prev->next = phead;
  phead->prev = tail->prev;
  free(tail);
}
void LTPushFront(LTNode* phead, LTDataType data)
{
  assert(phead);
  LTNode* newNode = BuyListNode(data);
  newNode->next = phead->next;
  phead->next->prev = newNode;
  phead->next = newNode;
  newNode->prev = phead;
}
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* cur = phead->next;
  phead->next = cur->next;
  cur->next->prev = phead;
  free(cur);
}
LTNode* LTFind(LTNode* phead, LTDataType data)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data==data)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
void LTInsert(LTNode* phead, LTNode* pos, LTDataType data)
{
  assert(phead);
  LTNode* newNode = BuyListNode(data);
  pos->prev->next = newNode;
  newNode->prev = pos->prev;
  newNode->next = pos;
  pos->prev = newNode;
}
void LTErase(LTNode* phead,LTNode* pos)
{
  assert(phead);
  pos->prev->next = pos->next;
  pos->next->prev = pos->prev;
  free(pos);
}
bool LTEmpty(LTNode* phead)
{
  assert(phead);
  if (phead->next == phead)
  {
    return true;
  }
  return false;
}
size_t LTSize(LTNode* phead)
{
  assert(phead);
  size_t size = 0;
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    size++;
    cur = cur->next;
  }
  return size;
}
void LTPrint(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("\n");
}

test.c

#define _CRT_SECURE_NO_DEPRECATE 1
#include"List.h"
void test()
{
  LTNode* phead = LTInit();
  LTPushBack(phead, 2);
  LTPushBack(phead, 1);
  LTPushBack(phead, 1);
  LTPushBack(phead, 1);
  LTPushBack(phead, 1);
  LTPushBack(phead, 1);
  LTPushFront(phead, 0);
  LTPushFront(phead, 0);
  LTPushFront(phead, 0);
  LTPushFront(phead, 0);
  LTPushFront(phead, 0);
  LTPrint(phead);
  LTPopFront(phead);
  LTPopFront(phead);
  LTPopFront(phead);
  LTPrint(phead);
  LTPopBack(phead);
  LTPopBack(phead);
  LTPopBack(phead);
  LTPrint(phead);
  LTNode* pos = LTFind(phead, 2);
  LTInsert(phead, pos, 200);
  LTInsert(phead, pos, 200);
  LTInsert(phead, pos, 200);
  LTPrint(phead);
  LTErase(phead, pos);
  LTPrint(phead);
  LTDestroy(phead);
}
int main()
{
  test();
  return 0;
}

基于结点的数据结构——链表（单链表&&双向循环链表）| 附完整源码 | C语言版（下）

正文

4. 带头双向循环链表的实现

4.1结点结构的定义

4.2函数接口的实现

5.两种链表的差异

①尾插与尾删的时间复杂度

②头插与头删的时间复杂度

③函数形参为何一个是二级指针，一个是一级指针？

完整源码

无头单向非循环链表

SList.h

SList.c

test.c

带头双向循环链表

List.h

List.c

test.c

热门文章

最新文章

相关课程

相关电子书