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

2024-07-28 19:47:10

循环链表设计与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;
}

关于双向链表的增删改查和排序的C++实现

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 由于双向链表可以方便地实现正序和逆序两个方向的插入.查找等功能,在很多算法中经常被使用, 这里用C++构造了一个双向链表,提供了对双向链表的插入.查找.删除节点.排序等功能,其中排序提供了插入排序和冒泡排序两种方式 #include<iostream> using namespace std;
C++将二叉树转为双向链表及判断两个链表是否相交

把二叉查找树转变成排序的双向链表例如: 转换成双向链表 4=6=8=10=12=14=16 struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; 首先阐述下二叉排序树: 它首先要是一棵二元树,在这基础上它或者是一棵空树:或者是具有下列性质的二元树: (1)若左子树不空
c++双向链表操作示例(创建双向链、双向链表中查找数据、插入数据等)

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. (1)定义双向链表的基本结构复制代码代码如下: typedef struct _DOUBLE_LINK_NODE { int data; struct _DOUBLE_LINK_NODE* prev; struct _DOUBLE_LINK_NODE* nex
C/C++ 双链表之逆序的实例详解

C/C++ 双链表之逆序的实例详解一.结点结构双向链表的数据结构定义如下: typedef struct node { ElemType data; struct node *prior struct node *next; }list; 其中,ElemType可以是任意数据类型如int.float或者char等,在算法中,规定其默认为int类型. 二.带头结点本文描述的是双向链表逆序,链表逆序需要维护3个指针,分别指向前一个节点.当前节点和下一个节点,具体代码如下: list *reve
利用C++实现双链表基本接口示例代码

链表链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域. 相比于线性表顺序结构,链表比较方便插入和删除操作. 本文主要给大家介绍了关于C++实现双链表基本接口的相关内容,分享出来供大家参考学习,话不多说,来一起看看详细的介绍吧. 首先先简单通过图示区分单链表和双链表的结构差异: 单链表
C++ 模版双向链表的实现详解

代码如下所示: 复制代码代码如下: #include <iostream>template <typename T>class double_linked{ struct node { T data; node* prev; node* next; node(T t, node* p, node* n) : data(t), prev(p), next(n) {} }; node* head;
C++ 实现双向链表的实例

双向链表C++ 的实现本文是通过C++ 的知识实现数据结构中的双向链表,这里不多说了,代码注释很清楚, 实现代码: //double LinkList implement with C++ template #include<iostream> using namespace std; /*template<typename Type> class DBListADT { public: virtual void Append(const Type &)=0; virt
如何用C++实现双向循环链表

双向循环链表,即每个节点都拥有一前一后两个指针且头尾互链的链表.各种链表的简单区别如下:单向链表:基本链表:单向循环链表:不同于单向链表以 NULL 判断链表的尾部,单向循环链表的尾部链接到表头,因此当迭代操作到表头前即是尾部:双向链表:比单向链表多出指向前一个节点的指针,但实际上使用双向链表时很少使用不循环的:双向循环链表:相对于单向循环链表,双向循环链表可从头部反向迭代,这在链表长度很大且需要获取.插入或删除靠近链表尾部元素的时候十分高效.单向循环列表只能从表头正向迭代,执行的时间大于从反向
C++ 双链表的基本操作(详解)

1.概念双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 结构图如下所示: 2.基本操作实例 DoubleList.cpp #include "stdafx.h" #include "DoubleList.h" #include <stdio.h> #include <malloc.h>
C++ 构造双向链表的实现代码

构造双向链表,不足之处,还望指正! 复制代码代码如下: // DoubleLinkedList.cpp : 定义控制台应用程序的入口点.//构造双向链表,实现从控制台输入,插入,删除,求大小size等操作#include "stdafx.h"#include <iostream>using namespace std;//定义双向链表的节点template<class T>struct NODE{ NODE<T>* pre; T data; NO

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

相关推荐

随机推荐