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

CircleListNode* CircleList_Reset(CircleList* list);

CircleListNode* CircleList_Current(CircleList* list);

CircleListNode* CircleList_Next(CircleList* list);

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

// 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; } 

// 用循环链表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);  } 

// 循环链表测试程序  #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声明  #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 

// 循环链表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; } 

// 循环线表测试程序  #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; }