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

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

循环链表设计与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,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,ret);     }   }    // 遍历链表   // 这里遍历打印两边，可以证明这是一个循环链表   for (int i = 0; i < 2 * CircleList_Length(List); ++i) {     Student *tmp = (Student *)CircleList_Get(List,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,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; } 

总结

以上是内存溢出为你收集整理的深入解析C++的循环链表与双向链表设计的API实现全部内容，希望文章能够帮你解决深入解析C++的循环链表与双向链表设计的API实现所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。