深入解析C++的循環鏈表與雙向鏈表設計的API實現

循環鏈表設計與API實現
基本概念
循環鏈表的定義：將單鏈表中最后一個數據元素的next指針指向第一個元素

C++,循環鏈表,雙向鏈表

循環鏈表擁有單鏈表的所有操作

創建鏈表
銷毀鏈表
獲取鏈表長度
清空鏈表
獲取第pos個元素操作
插入元素到位置pos
刪除位置pos處的元素

新增功能：游標的定義

在循環鏈表中可以定義一個“當前”指針，這個指針通常稱為游標，可以通過這個游標來遍歷鏈表中的所有元素。

C++,循環鏈表,雙向鏈表

循環鏈表新操作
將游標重置指向鏈表中的第一個數據元素

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 個人，再令其出列，…，如此下去，求出列順序。

C++,循環鏈表,雙向鏈表

代碼：

// 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指針

C++,循環鏈表,雙向鏈表

雙向鏈表擁有單鏈表的所有操作

創建鏈表
銷毀鏈表
獲取鏈表長度
清空鏈表
獲取第pos個元素操作
插入元素到位置pos
刪除位置pos處的元素

插入操作

C++,循環鏈表,雙向鏈表

插入操作異常處理
插入第一個元素異常處理
在0號位置處插入元素；
刪除操作

C++,循環鏈表,雙向鏈表

雙向鏈表的新操作

獲取當前游標指向的數據元素
將游標重置指向鏈表中的第一個數據元素
將游標移動指向到鏈表中的下一個數據元素
將游標移動指向到鏈表中的上一個數據元素
直接指定刪除鏈表中的某個數據元素

雙向鏈表重要技術場景

C++,循環鏈表,雙向鏈表

循環鏈表插入結點技術場景

C++,循環鏈表,雙向鏈表

循環鏈表刪除結點技術場景

C++,循環鏈表,雙向鏈表

優點：雙向鏈表在單鏈表的基礎上增加了指向前驅的指針
功能上雙向鏈表可以完全取代單鏈表的使用
雙向鏈表的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; }