温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

C++如何实现双向循环链表

发布时间:2020-07-29 14:59:37 来源:亿速云 阅读:255 作者:小猪 栏目:编程语言

这篇文章主要为大家展示了C++如何实现双向循环链表,内容简而易懂,希望大家可以学习一下,学习完之后肯定会有收获的,下面让小编带大家一起来看看吧。

一、概念

1.在双链表中的每个结点应有两个链接指针:

 lLink -> 指向前驱结点  (前驱指针或者左链指针)

rLink->指向后继结点(后驱指针或者右链指针)

2.双链表常采用带附加头结点的循环链表方式:

first:头指针,不存放数据,或者存放特殊要求的数据。它的lLink指向双链表的尾结点(最后一个结点),

它的rLink指向双链表的首结点(第一个有效结点)。链表的首结点的左链指针lLink和尾结点的右链指针

rLink都指向附加头结点。

二、实现程序

1.DblList.h

#ifndef DblList_h
#define DblList_h
#include <iostream>
using namespace std;
 
template <class T>
struct DblNode { // 链表结点定义
 T data;
 DblNode<T> *lLink, *rLink; // 链表前驱(左链)和后继(右链)指针
 DblNode(DblNode<T> *left = NULL, DblNode<T> *right = NULL):lLink(left), rLink(right){} // 构造函数
 DblNode(T value, DblNode<T> *left = NULL, DblNode<T> *right = NULL):data(value), lLink(left), rLink(right){} // 构造函数
};
 
template <class T>
class DblList { // 双链表(双向循环链表)
public:
 DblList(); // 构造函数:建立附加头结点
 ~DblList(); // 析构函数:释放所有存储
 void createDblList(); // 创建双向链表
 int Length()const; // 计算双链表的长度
 bool isEmpty(); // 判双链表空否
 DblNode<T> *getHead()const; // 取附加头结点
 void setHead(DblNode<T> *ptr); // 设置附加头结点地址
 DblNode<T> *Search(const T x); // 在链表中沿后继方向寻找等于给定值x的结点
 DblNode<T> *Locate(int i, int d); // 在链表中定位第i个结点,d=0按前驱方向,否则按后继方向
 bool Insert(int i, const T x, int d); // 在第i个结点后插入x,d=0按前驱方向,否则按后继方向
 bool Remove(int i, T &x, int d); // 删除第i个结点,x带回删除其值,d=0按前驱方向,否则按后继方向
 void Output(); // 输出双链表中的数据
private:
 DblNode<T> *first; // 附加头结点
};
 
template <class T>
DblList<T>::DblList() {
 // 构造函数:建立附加头结点
 first = new DblNode<T>();
 if(NULL == first) {
  cerr << "动态分配内存空间失败!" << endl;
  exit(1);
 }
 first->rLink = first->lLink = first; // 指向自身
}
 
template <class T>
DblList<T>::~DblList() { // 析构函数:释放所有存储
 DblNode<T> *current = first->rLink;
 while(current != first) {
  current->rLink->lLink = current->lLink; // 从lLink链中摘下
  current->lLink->rLink = current->rLink; // 从rLink链中摘下
  delete current; // 释放空间
  current = first->rLink;
 }
 delete first;
 first = NULL;
}
 
template <class T>
void DblList<T>::createDblList() {
 // 创建双向链表
 int n, val;
 DblNode<T> *current = first;
 cout << "请输入要输入的个数n:";
 cin >> n;
 cout << "请输入要输入的数:" << endl;
 for(int i = 0; i < n; i++) {
  cin >> val;
  DblNode<T> *newNode = new DblNode<T>(val);
  if(NULL == newNode) {
   cerr << "动态分配内存空间失败!" << endl;
   exit(1);
  }
  // 尾插入
  while(current->rLink != first)
   current = current->rLink; // 往后继方向移动
  newNode->rLink = current->rLink;
  current->rLink = newNode;
  newNode->rLink->lLink = newNode;
  newNode->lLink = current;
  current = current->rLink; // current往后移
 }
}
 
template <class T>
int DblList<T>::Length()const {
 // 计算双链表的长度
 DblNode<T> *current = first->rLink;
 int count = 0;
 
 while(current != first) {
  current = current->rLink;
  count++;
 }
 return count;
}
 
template <class T>
bool DblList<T>::isEmpty() {
 // 判双链表空否
 return first->rLink == first;
}
 
template <class T>
DblNode<T> *DblList<T>::getHead()const {
 // 取附加头结点
 return first;
}
 
template <class T>
void DblList<T>::setHead(DblNode<T> *ptr) {
 // 设置附加头结点地址
 first = ptr;
}
 
template <class T>
DblNode<T> *DblList<T>::Search(const T x) {
 // 在链表中沿后继方向寻找等于给定值x的结点
 DblNode<T> *current = first->rLink;
 while(current != first && current->data != x)
  current = current->rLink;
 if(current != first)
  return current; // 搜索成功
 else // 搜索失败
  return NULL;
}
 
template <class T>
DblNode<T> *DblList<T>::Locate(int i, int d) {
 // 定位
 if((first->rLink == first) || (i = 0))
  return first;
 DblNode<T> *current;
 if(d == 0)
  current = first->lLink; // 搜索前驱方向
 else
  current = first->rLink;
 for(int j = 1; j < i; j++)
 {
  if(current == first)
   break;
  else if(d == 0)
   current = current->lLink;
  else
   current = current->rLink;
 }
 if(current != first) // 定位成功
  return current;
 else
  return NULL;
}
 
template <class T>
bool DblList<T>::Insert(int i, const T x, int d) {
 // 插入
 DblNode<T> *current = Locate(i, d); // 查找第i个结点
 if(current == NULL) // i不合理,插入失败
  return false;
 DblNode<T> *newNode = new DblNode<T>(x);
 if(newNode == NULL) {
  cerr << "内存空间分配失败!" << endl;
  exit(1);
 }
 if(d == 0) { // 前驱方向插入
  newNode->lLink = current->lLink;
  current->lLink = newNode;
  newNode->lLink->rLink = newNode;
  newNode->rLink = current;
 }
 else { // 后继方向插入
  newNode->rLink = current->rLink;
  current->rLink = newNode;
  newNode->rLink->lLink = newNode;
  newNode->lLink = current;
 }
 return true;
}
 
template <class T>
bool DblList<T>::Remove(int i, T &x, int d) {
 // 删除
 DblNode<T> *current = Locate(i, d); // 查找第i个结点
 if(current == NULL) // i不合理,插入失败
  return false;
 current->rLink->lLink = current->lLink; // 从lLink链中摘下
 current->lLink->rLink = current->rLink; // 从rLink链中摘下
 x = current->data;
 delete current; // 释放空间
 current = NULL; // 指向空
 return true; // 删除成功
}
 
template <class T>
void DblList<T>::Output() {
 // 输出双链表中的数据
 DblNode<T> *current = first->rLink;
 while(current != first) {
  cout << current->data << " ";
  current = current->rLink;
 }
 cout << endl;
}
 
#endif /* DblList_h */

2.main.cpp

#include "DblList.h"
using namespace std;
 
int main(int argc, const char * argv[]) {
 int finished = 0, choice, i, x, d, len; // i存储第i个,d:存储方向 -》0表示前驱方向,否则为后继方向
 DblList<int> L;
 DblNode<int> *head = NULL, *current;
 
 while(!finished) {
  cout << "\n*********菜单*********\n";
  cout << "1:建立双链表\n";
  cout << "2:双链表的长度\n";
  cout << "3:双链表是否为空?\n";
  cout << "4:取附加头结点\n";
  cout << "5:设置附加头结点地址\n";
  cout << "6:在链表中沿后继方向寻找等于给定值x的结点\n";
  cout << "7:在链表中定位第i个结点,d=0按前驱方向,否则按后继方向\n";
  cout << "8:在第i个结点后插入x,d=0按前驱方向,否则按后继方向\n";
  cout << "9:删除第i个结点,x带回删除其值,d=0按前驱方向,否则按后继方向\n";
  cout << "10:输出双链表中的数据:\n";
  cout << "11:退出\n";
  cout << "请输入选择[1-11]:\n";
  cin >> choice;
  switch(choice) {
   case 1:
    L.createDblList(); // 建立双链表
    break;
   case 2:
    len = L.Length(); // 双链表的长度
    cout << "双链表的长度为:" << len << endl;
    break;
   case 3:
    if(L.isEmpty()) // 双链表是否为空
     cout << "双链表为空" << endl;
    else
     cout << "双链表不空" << endl;
    break;
   case 4:
    head = L.getHead();
    break;
   case 5:
    L.setHead(head); // 设置附加头结点地址
    break;
   case 6:
    cout << "请输入要查找的值x:";
    cin >> x;
    if(L.Search(x) != NULL)
     cout << "查找成功!" << endl;
    else
     cout << "查找失败!" << endl;
    break;
   case 7:
    cout << "请输入要定位第i个结点的i和方向d(d=0按前驱方向,否则按后继方向):";
    cin >> i >> d;
    current = L.Locate(i, d);
    if(current == NULL)
     cout << "定位失败!" << endl;
    else
     cout << "定位成功!" << endl;
    break;
   case 8:
    cout << "在第i个结点后插入x,d=0按前驱方向,否则按后继方向。请输入i, x和d:";
    cin >> i >> x >> d;
    if(L.Insert(i, x, d))
     cout << "插入成功!" << endl;
    else
     cout << "插入失败!" << endl;
    break;
   case 9:
    cout << "删除第i个结点,x带回删除其值,d=0按前驱方向,否则按后继方向。请输入i和d:";
    cin >> i >> d;
    if(L.Remove(i, x, d))
     cout << "删除成功,删除的值为:" << x << endl;
    else
     cout << "删除失败!" << endl;
    break;
   case 10:
    cout << "双链表中的数据为:" << endl;
    L.Output();
    break;
   case 11:
    finished = 1;
    break;
   default:
    cout << "输入错误, 请重新输入!" << endl;
  } // switch
 } // while
 return 0;
}

以上就是关于C++如何实现双向循环链表的内容,如果你们有学习到知识或者技能,可以把它分享出去让更多的人看到。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI