深入解析C++的循环链表与双向链表设计的API实现

循环链表设计与API实现
基本概念
循环链表的定义：将单链表中最后一个数据元素的next指针指向第一个元素

循环链表拥有单链表的所有操作

• 创建链表
• 销毁链表
• 获取链表长度
• 清空链表
• 获取第pos个元素操作
• 插入元素到位置pos
• 删除位置pos处的元素

新增功能：游标的定义

在循环链表中可以定义一个“当前”指针，这个指针通常称为游标，可以通过这个游标来遍历链表中的所有元素。

循环链表新操作
将游标重置指向链表中的第一个数据元素

CircleListNode* CircleList_Reset(CircleList* list);

获取当前游标指向的数据元素

CircleListNode* CircleList_Current(CircleList* list);

将游标移动指向到链表中的下一个数据元素

CircleListNode* CircleList_Next(CircleList* list);

直接指定删除链表中的某个数据元素

CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);
// 根据元素的值 删除 元素 pk根据元素的位置 删除 元素

最后加了一个循环链表的应用：求解约瑟夫问题
约瑟夫问题-循环链表典型应用
n 个人围成一个圆圈，首先第 1 个人从 1 开始一个人一个人顺时针报数，报到第 m 个人，令其出列。然后再从下一 个人开始从 1 顺时针报数，报到第 m 个人，再令其出列，…，如此下去，求出列顺序。

代码：

// circlelist.h
// 循环链表API声明

#ifndef _CIRCLELIST_H_
#define _CIRCLELIST_H_

typedef void CircleList;

typedef struct _tag_CircleListNode
{
  struct _tag_CircleListNode *next;
}CircleListNode;

// 创建链表
CircleList* CircleList_Create();

// 销毁链表
void CircleList_Destroy(CircleList* list);

// 清空链表
void CircleList_Clear(CircleList* list);

// 获取链表的长度
int CircleList_Length(CircleList* list);

// 在pos位置插入结点node
int CircleList_Insert(CircleList* list,CircleListNode* node, int pos);

// 获取pos位置的结点
CircleListNode* CircleList_Get(CircleList* list, int pos);

// 删除pos位置的结点
CircleListNode* CircleList_Delete(CircleList* list, int pos);

// 根据结点的值进行数据删除
CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);

// 重置游标
CircleListNode* CircleList_Reset(CircleList* list);

// 获取当前游标所指结点
CircleListNode* CircleList_Current(CircleList* list);

// 将原始游标所指结点返回给上层，然后让游标移到下一个结点
CircleListNode* CircleList_Next(CircleList* list);

#endif

// circlelist.cpp
// 循环链表API实现

#include <iostream>
#include <cstdio>
#include "circlelist.h"

typedef struct _tag_CircleList
{
  CircleListNode header;
  CircleListNode *silder;
  int length;
}TCircleList;

// 创建链表
CircleList* CircleList_Create()
{
  TCircleList *ret = (TCircleList *)malloc(sizeof(TCircleList));
  if (ret == NULL) {
    return NULL;
  }

  // 初始化
  ret->header.next = NULL;
  ret->silder = NULL;
  ret->length = 0;

  return ret;
}

// 销毁链表
void CircleList_Destroy(CircleList* list)
{
  if (list == NULL) {
    return;
  }
  free(list);
  return;
}

// 清空链表
void CircleList_Clear(CircleList* list)
{
  if (list == NULL) {
    return;
  }
  TCircleList *tList = (TCircleList *)list;
  tList->header.next = NULL;
  tList->silder = NULL;
  tList->length = 0;

  return;
}

// 获取链表的长度
int CircleList_Length(CircleList* list)
{
  if (list == NULL) {
    return -1;
  }
  TCircleList *tList = (TCircleList *)list;
  return tList->length;
}

// 在pos位置插入结点node
int CircleList_Insert(CircleList* list, CircleListNode* node, int pos)
{
  if (list == NULL || node == NULL || pos < 0) {
    return -1;
  }

  TCircleList *tList = (TCircleList *)list;

  CircleListNode *cur = (CircleListNode *)tList;

  for (int i = 0; i < pos; ++i) {
    cur = cur->next;
  }

  node->next = cur->next;
  cur->next = node;

  // 如果是第一次插入
  if (tList->length == 0) {
    tList->silder = node;
  }

  ++tList->length; // 记得长度加1

  // 如果是头插法
  if (cur == (CircleListNode *)tList) {
    // 获取最后一个元素
    CircleListNode *last = CircleList_Get(tList, tList->length - 1);
    last->next = cur->next;
  }

  return 0;
}

// 获取pos位置的结点
CircleListNode* CircleList_Get(CircleList* list, int pos)
{
  // 因为是循环链表，所以这里不需要排除pos>length的情况
  if (list == NULL || pos < 0) {
    return NULL;
  }

  TCircleList *tList = (TCircleList *)list;
  CircleListNode *cur = (CircleListNode *)tList;

  for (int i = 0; i < pos; ++i) {
    cur = cur->next;
  }

  return cur->next;
}

// 删除pos位置的结点
CircleListNode* CircleList_Delete(CircleList* list, int pos)
{
  TCircleList *tList = (TCircleList *)list;
  CircleListNode *ret = NULL;

  if (tList != NULL && pos >= 0 && tList->length > 0) {
    CircleListNode *cur = (CircleListNode *)tList;
    for (int i = 0; i < pos; ++i) {
      cur = cur->next;
    }

    // 若删除头结点，需要求出尾结点
    CircleListNode *last = NULL;
    if (cur == (CircleListNode *)tList) {
      last = CircleList_Get(tList, tList->length - 1);
    }

    ret = cur->next;
    cur->next = ret->next;

    --tList->length;

    // 若删除头结点
    if (last != NULL) {
      tList->header.next = ret->next;
      last->next = ret->next;
    }

    // 若删除的元素为游标所指的元素
    if (tList->silder == ret) {
      tList->silder = ret->next;
    }

    // 若删除元素后链表长度为0
    if (tList->length == 0) {
      tList->header.next = NULL;
      tList->silder = NULL;
    }
  }

  return ret;
}

// 根据结点的值进行数据删除
CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node)
{
  TCircleList *tList = (TCircleList *)list;
  CircleListNode *ret = NULL;

  if (list != NULL && node != NULL) {
    CircleListNode *cur = (CircleListNode *)tList;
    int i = 0;
    for (i = 0; i < tList->length; ++i) {
      if (cur->next == node) {
        ret = cur->next;
        break;
      }

      cur = cur->next;
    }

    // 如果找到
    if (ret != NULL) {
      CircleList_Delete(tList, i);
    }
  }

  return ret;
}

// 重置游标
CircleListNode* CircleList_Reset(CircleList* list)
{
  TCircleList *tList = (TCircleList *)list;
  CircleListNode* ret = NULL;

  if (list != NULL) {
    tList->silder = tList->header.next;
    ret = tList->silder;
  }

  return NULL;
}

// 获取当前游标所指结点
CircleListNode* CircleList_Current(CircleList* list)
{
  TCircleList *tList = (TCircleList *)list;
  CircleListNode* ret = NULL;
  if (list != NULL) {
    ret = tList->silder;
  }

  return ret;
}

// 将原始游标所指结点返回给上层，然后让游标移到下一个结点
CircleListNode* CircleList_Next(CircleList* list)
{
  TCircleList *tList = (TCircleList *)list;
  CircleListNode* ret = NULL;
  if (list != NULL && tList->silder != NULL) {
    ret = tList->silder;
    tList->silder = ret->next;
  }
  return ret;
}

joseph.h 

// 用循环链表API求解约瑟夫问题

#include <cstdio>
#include "circlelist.h"

const int maxp = 8;

struct Person
{
  CircleListNode circlenode;
  int id;
};

void joseph()
{
  Person s[maxp];
  for (int i = 0; i < maxp; ++i) {
    s[i].id = i + 1;
  }

  CircleList *list = NULL;
  list = CircleList_Create();

  // 插入元素
  for (int i = 0; i < maxp; ++i) {
    // 尾插法
    int ret = CircleList_Insert(list, (CircleListNode *)&s[i], CircleList_Length(list));
    if (ret < 0) {
      printf("function CircleList_Insert err: %d\n", ret);
    }
  }

  // 遍历链表
  for (int i = 0; i < CircleList_Length(list); ++i) {
    Person *tmp = (Person *)CircleList_Get(list, i);
    if (tmp == NULL) {
      printf("function CircleList_Get err.\n");
    }
    printf("age: %d\n", tmp->id);
  }

  // 求解约瑟夫问题
  while (CircleList_Length(list) > 0)
  {
    Person* pv = NULL;
    for (int i = 1; i < 3; i++)
    {
      CircleList_Next(list);
    }
    pv = (Person*)CircleList_Current(list);
    printf("%d ", pv->id);
    CircleList_DeleteNode(list, (CircleListNode *)pv); //根据结点的值,进行结点元素的删除
  }
  printf("\n");

  CircleList_Destroy(list);

}

main.cpp 

// 循环链表测试程序

#include <iostream>
#include <cstdio>
#include "circlelist.h"
#include "joseph.h"

const int maxn = 5;

struct Student
{
  CircleListNode circlenode;
  char name[32];
  int age;
};

void play01()
{
  Student s[maxn];
  for (int i = 0; i < maxn; ++i) {
    s[i].age = i + 1;
  }

  CircleList *list = NULL;

  list = CircleList_Create(); // 创建链表

  // 插入元素
  for (int i = 0; i < maxn; ++i) {
    // 尾插法
    int ret = CircleList_Insert(list, (CircleListNode *)&s[i], CircleList_Length(list));
    if (ret < 0) {
      printf("function CircleList_Insert err: %d\n", ret);
    }
  }

  // 遍历链表
  // 这里遍历打印两边，可以证明这是一个循环链表
  for (int i = 0; i < 2 * CircleList_Length(list); ++i) {
    Student *tmp = (Student *)CircleList_Get(list, i);
    if (tmp == NULL) {
      printf("function CircleList_Get err.\n");
    }
    printf("age: %d\n", tmp->age);
  }

  // 删除结点，通过结点位置
  while (CircleList_Length(list)) {
    Student *tmp = (Student *)CircleList_Delete(list, CircleList_Length(list) - 1);
    if (tmp == NULL) {
      printf("function CircleList_Delete err.\n");
    }
    printf("age: %d\n", tmp->age);
  }

  // 销毁链表
  CircleList_Destroy(list);

}

int main()
{
  play01(); // 为了测试数据的生命周期，所以另写一个函数调用运行
  joseph();

  return 0;
}

双向链表设计与API实现
为什么需要双向链表？

• 单链表的结点都只有一个指向下一个结点的指针
• 单链表的数据元素无法直接访问其前驱元素
• 逆序访问单链表中的元素是极其耗时的操作！

双向链表的定义

在单链表的结点中增加一个指向其前驱的pre指针

双向链表拥有单链表的所有操作

• 创建链表
• 销毁链表
• 获取链表长度
• 清空链表
• 获取第pos个元素操作
• 插入元素到位置pos
• 删除位置pos处的元素

插入操作

插入操作异常处理
插入第一个元素异常处理
在0号位置处插入元素；
删除操作

双向链表的新操作

• 获取当前游标指向的数据元素
• 将游标重置指向链表中的第一个数据元素
• 将游标移动指向到链表中的下一个数据元素
• 将游标移动指向到链表中的上一个数据元素
• 直接指定删除链表中的某个数据元素

双向链表重要技术场景

循环链表插入结点技术场景

循环链表删除结点技术场景

优点：双向链表在单链表的基础上增加了指向前驱的指针
功能上双向链表可以完全取代单链表的使用
双向链表的Next，Pre和Current操作可以高效的遍历链表中的所有元素
缺点：代码复杂

代码示例：
 dlinklist.h 

// 双向链表API声明

#ifndef _DLINKLIST_H_
#define _DLINKLIST_H_

typedef void DLinkList;

typedef struct _tag_DLinkListNode
{
  _tag_DLinkListNode *next;
  _tag_DLinkListNode *pre;
}DLinkListNode;

// 创建链表
DLinkList* DLinkList_Create();

// 销毁链表
void DLinkList_Destroy(DLinkList *list);

// 清空链表
void DLinkList_Clear(DLinkList *list);

// 获取链表长度
int DLinkList_Length(DLinkList *list);

// 在pos位置，插入结点node
int DLinkList_Insert(DLinkList *list, DLinkListNode *node, int pos);

// 获取pos位置的结点，返回给上层
DLinkListNode* DLinkList_Get(DLinkList *list, int pos);

// 删除pos位置的结点
DLinkListNode* DLinkList_Delete(DLinkList *list, int pos);

// 删除值为node的结点
DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);

// 重置游标
DLinkListNode* DLinkList_Reset(DLinkList* list);

// 获取当前游标所指的结点
DLinkListNode* DLinkList_Current(DLinkList* list);

// 获取游标当前所指结点，然后让游标指向下一个结点
DLinkListNode* DLinkList_Next(DLinkList* list);

// 获取游标当前所指结点，然后让游标指向前一个结点
DLinkListNode* DLinkList_Pre(DLinkList* list);


#endif

dlinklist.cpp 

// 循环链表API实现

#include <cstdio>
#include <malloc.h>
#include "dlinklist.h"

typedef struct _tag_DLinkList
{
  DLinkListNode header;
  DLinkListNode *slider;
  int length;
}TDLinkList;

// 创建链表
DLinkList* DLinkList_Create()
{
  TDLinkList *ret = (TDLinkList *)malloc(sizeof(TDLinkList));

  if (ret != NULL) {
    ret->header.next = NULL;
    ret->header.pre = NULL;
    ret->slider = NULL;
    ret->length = 0;
  }

  return ret;
}

// 销毁链表
void DLinkList_Destroy(DLinkList *list)
{
  if (list != NULL) {
    free(list);
  }

  return;
}

// 清空链表
void DLinkList_Clear(DLinkList *list)
{
  TDLinkList *tList = (TDLinkList *)list;

  if (tList != NULL) {
    tList->header.next = NULL;
    tList->header.pre = NULL;
    tList->slider = NULL;
    tList->length = 0;
  }

  return;
}

// 获取链表长度
int DLinkList_Length(DLinkList *list)
{
  TDLinkList *tList = (TDLinkList *)list;
  int ret = -1;

  if (tList != NULL) {
    ret = tList->length;
  }

  return ret;
}

// 在pos位置，插入结点node
int DLinkList_Insert(DLinkList *list, DLinkListNode *node, int pos)
{
  TDLinkList *tList = (TDLinkList *)list;
  int ret = -1, i = 0;

  if (list != NULL && node != NULL && pos >= 0)
  {
    ret = 0;

    DLinkListNode *cur = (DLinkListNode *)tList;
    DLinkListNode *next = NULL;

    for (i = 0; i < pos && cur->next != NULL; ++i) {
      cur = cur->next;
    }

    next = cur->next;

    cur->next = node;
    node->next = next;

    // 当链表插入第一个结点时需要进行特殊处理
    if (next != NULL) {
      next->pre = node;
    }
    node->pre = cur;

    if (tList->length == 0)  {
      tList->slider = node; // 当链表插入第一个元素处理游标
    }

    // 若在0位置插入，需要特殊处理，新来的结点next前pre指向NULL
    if (cur == (DLinkListNode *)tList) {
      node->pre = NULL;
    }
    ++tList->length;
  }

  return ret;
}

// 获取pos位置的结点，返回给上层
DLinkListNode* DLinkList_Get(DLinkList *list, int pos)
{
  TDLinkList *tList = (TDLinkList *)list;
  DLinkListNode* ret = NULL;
  int i = 0;

  if (list != NULL && pos >= 0 && pos < tList->length) {
    DLinkListNode *cur = (DLinkListNode *)tList;

    for (i = 0; i < pos; ++i) {
      cur = cur->next;
    }

    ret = cur->next;
  }

  return ret;
}

// 删除pos位置的结点
DLinkListNode* DLinkList_Delete(DLinkList *list, int pos)
{
  TDLinkList *tList = (TDLinkList *)list;
  DLinkListNode* ret = NULL;
  int i = 0;

  if (tList != NULL && pos >= 0) {
    DLinkListNode *cur = (DLinkListNode *)tList;
    DLinkListNode *next = NULL;

    for (i = 0; i < pos && cur->next != NULL; ++i) {
      cur = cur->next;
    }

    ret = cur->next;
    next = ret->next;

    cur->next = next;

    if (next != NULL) {
      next->pre = cur;

      if (cur == (DLinkListNode *)tList) { // 第0个位置，需要特殊处理
        next->pre = NULL;
      }
    }

    if (tList->slider == ret) {
      tList->slider = next;
    }

    --tList->length;
  }

  return ret;
}

// 删除值为node的结点
DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node)
{
  TDLinkList *tList = (TDLinkList *)list;
  DLinkListNode* ret = NULL;
  int i = 0;

  if (tList != NULL) {
    DLinkListNode *cur = (DLinkListNode *)tList;

    for (i = 0; i < DLinkList_Length(tList); ++i) {
      if (cur->next == node) {
        ret = cur->next;
        break;
      }

      cur = cur->next;
    }

    if (!ret) {
      DLinkList_Delete(tList, i);
    }
  }

  return ret;
}

// 重置游标
DLinkListNode* DLinkList_Reset(DLinkList* list)
{
  TDLinkList *tList = (TDLinkList *)list;
  DLinkListNode* ret = NULL;

  if (tList != NULL) {
    tList->slider = tList->header.next;
    ret = tList->slider;
  }

  return ret;
}

// 获取当前游标所指的结点
DLinkListNode* DLinkList_Current(DLinkList* list)
{
  TDLinkList *tList = (TDLinkList *)list;
  DLinkListNode* ret = NULL;

  if (tList != NULL) {
    ret = tList->slider;
  }

  return ret;
}

// 获取游标当前所指结点，然后让游标指向下一个结点
DLinkListNode* DLinkList_Next(DLinkList* list)
{
  TDLinkList *tList = (TDLinkList *)list;
  DLinkListNode* ret = NULL;

  if (tList != NULL && tList->slider != NULL) {
    ret = tList->slider;
    tList->slider = ret->next;
  }

  return ret;
}

// 获取游标当前所指结点，然后让游标指向前一个结点
DLinkListNode* DLinkList_Pre(DLinkList* list)
{
  TDLinkList *tList = (TDLinkList *)list;
  DLinkListNode* ret = NULL;

  if (tList != NULL && tList->slider != NULL) {
    ret = tList->slider;
    tList->slider = ret->pre;
  }

  return ret;
}

main.cpp 

// 循环线表测试程序

#include <cstdio>
#include "dlinklist.h"

const int maxn = 5;

struct Student
{
  DLinkListNode node;
  int age;
};

void play()
{
  Student s[maxn];
  for (int i = 0; i < maxn; ++i) {
    s[i].age = i + 21;
  }

  DLinkList *list = NULL;
  list = DLinkList_Create(); // 创建链表

  // 插入结点
  for (int i = 0; i < maxn; ++i) {
    int ret = DLinkList_Insert(list, (DLinkListNode *)&s[i], DLinkList_Length(list));
    if (ret < 0) {
      return;
      printf("function DLinkList_Insert err.\n");
    }
  }

  // 遍历链表
  for (int i = 0; i < DLinkList_Length(list); ++i) {
    Student *tmp = (Student *)DLinkList_Get(list, i);
    if (tmp == NULL) {
      printf("function DLinkList_Get err.\n");
      return;
    }
    printf("age: %d\n", tmp->age);
  }

  DLinkList_Delete(list, DLinkList_Length(list) - 1); // 删除尾结点
  DLinkList_Delete(list, 0); // 删除头结点

  // 用游标遍历链表
  for (int i = 0; i < DLinkList_Length(list); ++i) {
    Student *tmp = (Student *)DLinkList_Next(list);
    if (tmp == NULL) {
      printf("function DLinkList_Next err.\n");
      return;
    }
    printf("age: %d\n", tmp->age);
  }

  printf("\n");

  DLinkList_Reset(list);
  DLinkList_Next(list);

  Student *tmp = (Student *)DLinkList_Current(list);
  if (tmp == NULL) {
    printf("function DLinkList_Current err.\n");
    return;
  }
  printf("age: %d\n", tmp->age);

  DLinkList_DeleteNode(list, (DLinkListNode*)tmp);
  tmp = (Student *)DLinkList_Current(list);
  if (tmp == NULL) {
    printf("function DLinkList_Current err.\n");
    return;
  }
  printf("age: %d\n", tmp->age);
  printf("length: %d\n", DLinkList_Length(list));

  DLinkList_Pre(list);
  tmp = (Student *)DLinkList_Current(list);
  if (tmp == NULL) {
    printf("function DLinkList_Current err.\n");
    return;
  }
  printf("age: %d\n", tmp->age);

  printf("length: %d\n", DLinkList_Length(list));
  DLinkList_Destroy(list);

  return;
}

int main()
{
  play();

  return 0;
}