cbd做网站的公司/厦门seo推广优化

循环链表(Circular Linked List)

1. 循环链表的概念

1.1 循环链表的定义

• 循环链表是另一种形式的表示线性表的链表。

1.2 循环链表的结点结构

• 循环链表的结点包括两个部分：数据域和指针域。
  (1)数据域(data)，用于存储该结点的数据元素，数据元素类型由应用问题决定。
  (2)指针域(link)，用于存放一个指针，该指针指向下一个结点的开始存储地址。
• 循环链表的结点结构示意图：
  

1.3 循环链表中各结点的链接方式

• 循环链表与单链表一样，可以有附加头结点，这样能够简化链表操作的实现，统一空表与非空表的运算。
• 循环链表中表尾结点的link域中不是NULL，而是存放了一个指向链表开始结点的指针。因此，涉及遍历操作时，其终止条件不再是像单链表那样判别p或p->next是否为空，而是判别它们是否等于头指针。
• 循环链表只要知道表中任何一个结点的地址，就可以遍历表中其他任一结点。
• 循环链表(带附加头结点的)中各结点的链接方式示意图：
  

2. 循环链表的实现

2.1 链表的结点结构定义

• 文件：LinkNode.h

  
  #ifndef LINK_NODE_H_#define LINK_NODE_H_#include <iostream>#include <string>#include <strstream>using namespace std;template <class T>
  struct LinkNode         //链表结点类的定义
  {T data;             //数据域LinkNode<T> *link;  //指针域——后继指针//仅初始化指针成员的构造函数LinkNode(LinkNode<T>* ptr = NULL){ link = ptr; }//初始化数据与指针成员的构造函数LinkNode(const T& value, LinkNode<T>* ptr = NULL){ data = value; link = ptr; }
  };#endif /* LINK_NODE_H_ */
  

2.2 循环链表的类定义及其操作的实现(带附加头结点)

• 文件：CircLinkedList.h

  
  #ifndef CIRC_LINKED_LIST_H_#define CIRC_LINKED_LIST_H_#include "LinkNode.h"template <class T>
  class CircLinkedList//带附加头结点
  {
  public:CircLinkedList();                               //构造函数CircLinkedList(const CircLinkedList<T>& L);     //拷贝构造函数~CircLinkedList();                              //析构函数
  public:int Length()const;                          //计算链表的结点总数(除附加头结点)LinkNode<T>* Search(const T& x)const;       //搜索数据值为x的结点并返回LinkNode<T>* Locate(int i)const;            //获取第i个结点并返回bool GetData(int i, T& x)const;             //获取第i个结点的数据值保存至x，并返回获取成功与否bool SetData(int i, const T& x);            //修改第i个结点的数据值为xbool Insert(int i, const T& x);             //在第i个结点后插入数据值为x的新结点bool Remove(int i, T& x);                   //删除第i个结点，并将被删结点的数据值保存至xbool IsEmpty()const;                        //判断表是否为空bool IsFull()const;                         //判断表是否为满void Sort();                                //表排序——冒泡排序void InputFront(const T& endTag);           //前插法建立链表void InputRear(const T& endTag);            //后插法建立链表void Output()const;                         //输出所有结点的数据值void Reverse();                             //链表逆置void MakeEmpty();                           //清空链表(保留附加头结点)CircLinkedList<T>& operator=(const CircLinkedList<T>& L);   //链表间赋值操作——重载等号运算符
  public:LinkNode<T>* GetHead()const;                //返回附加头结点的地址T get_value(string& s_value);               //返回输入的结点数据值                
  public:static bool IsNumber(const string& s_num);  //判断输入的字符串每个字符是否都是数值0~9static T StrToTtype(const string& s_num);   //类型转换——将string型转为模板类型T
  private:LinkNode<T> *first; //链表的头结点
  };//构造函数
  template<class T>
  CircLinkedList<T>::CircLinkedList()
  : first(new LinkNode<T>)
  {first->link = first;cout << "$ 执行构造函数" << endl;
  }//拷贝构造函数
  template<class T>
  CircLinkedList<T>::CircLinkedList(const CircLinkedList<T>& L)
  {cout << "$ 执行拷贝构造函数" << endl;LinkNode<T> *srcptr = L.GetHead();LinkNode<T> *destptr = first = new LinkNode<T>;while (L.GetHead() != srcptr->link){srcptr = srcptr->link;destptr->link = new LinkNode<T>(srcptr->data);destptr = destptr->link;}destptr->link = first;
  }//析构函数
  template<class T>
  CircLinkedList<T>::~CircLinkedList()
  {cout << "$ 执行析构函数" << endl;MakeEmpty();
  }//计算链表的结点总数(除附加头结点)
  template<class T>
  int CircLinkedList<T>::Length()const
  {int count = 0;LinkNode<T> *curNode = first->link;while (first != curNode){curNode = curNode->link;count++;}return count;
  }//搜索数据值为x的结点并返回
  template<class T>
  LinkNode<T>* CircLinkedList<T>::Search(const T& x)const
  {LinkNode<T> *curNode = first->link;while ((first != curNode) && (x != curNode->data)){curNode = curNode->link;}if (first == curNode){curNode = NULL;}return curNode;
  }//获取第i个结点并返回
  template<class T>
  LinkNode<T>* CircLinkedList<T>::Locate(int i)const
  {if (i < 0){return NULL;}if ((first == first->link) || (0 == i)){return first;}int location = 1;LinkNode<T> *curNode = first->link;while ((location < i) && (first != curNode)){curNode = curNode->link;location++;}if (first == curNode){curNode = NULL;}return curNode;
  }//获取第i个结点的数据值保存至x，并返回获取成功与否
  template<class T>
  bool CircLinkedList<T>::GetData(int i, T& x)const
  {LinkNode<T> *curNode = Locate(i);if ((NULL == curNode) || (first == curNode)){return false;}x = curNode->data;return true;
  }//修改第i个结点的数据值为x
  template<class T>
  bool CircLinkedList<T>::SetData(int i, const T& x)
  {LinkNode<T> *curNode = Locate(i);if ((NULL == curNode) || (first == curNode)){return false;}curNode->data = x;return true;
  }//在第i个结点后插入数据值为x的新结点
  template<class T>
  bool CircLinkedList<T>::Insert(int i, const T& x)
  {LinkNode<T> *curNode = Locate(i);if (NULL == curNode){return false;}LinkNode<T> *newNode = new LinkNode<T>(x);if (NULL == newNode){cerr << "* 存储分配错误" << endl;exit(1);}newNode->link = curNode->link;curNode->link = newNode;return true;
  }//删除第i个结点，并将被删结点的数据值保存至x
  template<class T>
  bool CircLinkedList<T>::Remove(int i, T& x)
  {LinkNode<T> *preNode = Locate(i - 1);if (NULL == preNode){return false;}LinkNode<T> *delNode = preNode->link;if ((NULL == delNode) || (first == delNode)){return false;}preNode->link = delNode->link;x = delNode->data;delete delNode;return true;
  }//判断表是否为空
  template<class T>
  bool CircLinkedList<T>::IsEmpty()const
  {return (first == first->link) ? true : false;
  }//判断表是否为满
  template<class T>
  bool CircLinkedList<T>::IsFull()const
  {return false;
  }//表排序——冒泡排序
  template<class T>
  void CircLinkedList<T>::Sort()
  {LinkNode<T> *curNode = first->link;while (first != curNode){LinkNode<T> *nextNode = curNode->link;while (first != nextNode){if (curNode->data < nextNode->data){T temp = curNode->data;curNode->data = nextNode->data;nextNode->data = temp;}nextNode = nextNode->link;}curNode = curNode->link;}
  }//前插法建立链表
  //endTag是约定的输入序列结束的标志。如果输入序列是正整数，endTag可以是0或负数；
  //如果输入序列是字符，endTag可以是字符集中不会出现的字符，如“\0”。
  template<class T>
  void CircLinkedList<T>::InputFront(const T& endTag)
  {MakeEmpty();LinkNode<T> *lastNode = NULL;string s_value;T value = get_value(s_value);while (endTag != value){LinkNode<T> *newNode = new LinkNode<T>(value);  //创建新结点if (NULL == newNode){cerr << "* 存储分配错误" << endl;exit(1);}if (first->link == first){lastNode = newNode;}newNode->link = first->link;                    //新结点中指针域的指针指向链表的第一个结点first->link = newNode;                          //附加头结点中指针域的指针指向新结点value = get_value(s_value);}lastNode->link = first;
  }//后插法建立链表
  //endTag是约定的输入序列结束的标志。如果输入序列是正整数，endTag可以是0或负数；
  //如果输入序列是字符，endTag可以是字符集中不会出现的字符，如“\0”。
  template<class T>
  void CircLinkedList<T>::InputRear(const T& endTag)
  {MakeEmpty();LinkNode<T> *lastNode = first;                      //设置链表的最后一个结点为附加头结点string s_value;T value = get_value(s_value);while (endTag != value){LinkNode<T> *newNode = new LinkNode<T>(value);  //创建新结点if (NULL == newNode){cerr << "* 存储分配错误" << endl;exit(1);}lastNode->link = newNode;                       //最后一个结点中指针域的指针指向新结点lastNode = newNode;                             //设置最后一个结点为新结点value = get_value(s_value);}lastNode->link = first;
  }//输出所有结点的数据值
  template<class T>
  void CircLinkedList<T>::Output()const
  {LinkNode<T> *curNode = first->link;while (first != curNode){cout << "curNode->data = " << curNode->data << endl;curNode = curNode->link;}
  }//链表逆置
  template<class T>
  void CircLinkedList<T>::Reverse()
  {LinkNode<T> *prevNode = first;LinkNode<T> *curNode = first->link;LinkNode<T> *nextNode = curNode->link;while (first != curNode) {curNode->link = prevNode;prevNode = curNode;curNode = nextNode;nextNode = curNode->link;}first->link = prevNode;
  }//清空链表(保留附加头结点)
  template<class T>
  void CircLinkedList<T>::MakeEmpty()
  {LinkNode<T> *curNode = NULL;while (first != first->link)        //当链表不为空时，删去链表中所有结点{curNode = first->link;          //保存被删结点first->link = curNode->link;    //将链表附加头结点中指针域的指针指向被删结点的下一个结点delete curNode;                 //从链表上摘下被删结点}
  }//链表间赋值操作——重载等号运算符
  template<class T>
  CircLinkedList<T>& CircLinkedList<T>::operator=(const CircLinkedList<T>& L)
  {cout << "$ 执行赋值操作函数" << endl;LinkNode<T> *srcptr = L.GetHead();LinkNode<T> *destptr = first = new LinkNode<T>;while (L.GetHead() != srcptr->link){srcptr = srcptr->link;destptr->link = new LinkNode<T>(srcptr->data);destptr = destptr->link;}destptr->link = first;return *this;
  }//返回附加头结点的地址
  template<class T>
  LinkNode<T>* CircLinkedList<T>::GetHead()const
  {return first;
  }//返回输入的结点数据值
  template <class T>
  T CircLinkedList<T>::get_value(string& s_value)
  {cout << "newNode->data = ";cin >> s_value;return StrToTtype(s_value);
  }//判断输入的字符串每个字符是否都是数值0~9
  template <class T>
  bool CircLinkedList<T>::IsNumber(const string& s_num)
  {for (size_t i = 0; i < s_num.size(); i++){if ((s_num[i] < '0') || (s_num[i] > '9')){return false;}}return true;
  }//类型转换——将string型转为模板类型T
  template <class T>
  T CircLinkedList<T>::StrToTtype(const string& s_num)
  {T n_num;strstream ss_num;ss_num << s_num;ss_num >> n_num;return n_num;
  }#endif /* CIRC_LINKED_LIST_H_ */
  

2.3 主函数(main函数)的实现

• 文件：main.cpp

  
  #include "CircLinkedList.h" //带附加头结点#define EXIT 0              //退出#define CONSTRUCT_COPY 1    //拷贝构造链表#define LENGTH 2            //计算链表的结点总数#define SEARCH 3            //搜索数据值为x的结点并返回#define LOCATE 4            //获取第i个结点并返回#define GETDATA 5           //获取第i个结点的数据值保存至x，并返回获取成功与否#define SETDATA 6           //修改第i个结点的数据值为x#define INSERT 7            //在第i个结点后插入数据值为x的新结点#define REMOVE 8            //删除第i个结点，并将被删结点的数据值保存至x#define ISEMPTY 9           //判断表是否为空#define ISFULL 10           //判断表是否为满#define SORT 11             //表排序——冒泡排序#define INPUTFRONT 12       //前插法建立链表#define INPUTREAR 13        //后插法建立链表#define OUTPUT 14           //输出所有结点的数据值#define REVERSE 15          //链表逆置#define MAKEEMPTY 16        //清空链表#define OPERATOR_COPY 17    //链表间赋值操作——重载等号运算符#define GETHEAD 18          //返回头结点的地址void print_description()
  {cout << "------------------------------>循环链表<------------------------------" << endl;cout << "功能选项说明：" << endl;cout << "#0： 退出" << endl;cout << "#1： 拷贝构造链表" << endl;cout << "#2： 计算链表的结点总数" << endl;cout << "#3： 搜索数据值为x的结点并返回" << endl;cout << "#4： 获取第i个结点并返回" << endl;cout << "#5： 获取第i个结点的数据值保存至x，并返回获取成功与否" << endl;cout << "#6： 修改第i个结点的数据值为x" << endl;cout << "#7： 在第i个结点后插入数据值为x的新结点" << endl;cout << "#8： 删除第i个结点，并将被删结点的数据值保存至x" << endl;cout << "#9： 判断表是否为空" << endl;cout << "#10：判断表是否为满" << endl;cout << "#11：表排序——冒泡排序" << endl;cout << "#12：前插法建立链表" << endl;cout << "#13：后插法建立链表" << endl;cout << "#14：输出所有结点的数据值" << endl;cout << "#15：链表逆置" << endl;cout << "#16：清空链表" << endl;cout << "#17：链表间赋值操作——重载等号运算符" << endl;cout << "#18：返回头结点的地址" << endl;cout << "--------------------------------------------------------------------" << endl;
  }//输入结点编号
  template <class T>
  int get_item()
  {cout << "> 请输入结点编号，item = ";string s_item;cin >> s_item;while (false == CircLinkedList<T>::IsNumber(s_item)){cout << "* 输入有误，请重新输入：";cin >> s_item;}return atoi(s_item.c_str());
  }//输入数据值
  template <class T>
  T get_data()
  {cout << "> 请输入数据值，data = ";string s_data;cin >> s_data;return CircLinkedList<T>::StrToTtype(s_data);
  }//输入结束标志位
  template <class T>
  T get_endtag()
  {cout << "请输入结束标志值，endTag = ";string s_endTag;cin >> s_endTag;return CircLinkedList<T>::StrToTtype(s_endTag);
  }//构造循环链表
  template <class T>
  CircLinkedList<T>* construct_circlinkedlist()
  {cout << "\n==> 创建循环链表" << endl;CircLinkedList<T> *circlinkedList = new CircLinkedList<T>;return circlinkedList;
  }//析构循环链表
  template <class T>
  void destory_circlinkedlist(CircLinkedList<T>* circlinkedList)
  {cout << "\n==> 释放循环链表在堆中申请的空间，并将指向该空间的指针变量置为空" << endl;delete circlinkedList;circlinkedList = NULL;
  }//拷贝构造链表
  template <class T>
  void construct_copy(CircLinkedList<T>* circlinkedList)
  {cout << "$ 执行拷贝构造链表函数" << endl;CircLinkedList<T> cpy_linkedlist = *circlinkedList;cpy_linkedlist.Output();
  }//计算链表的结点总数
  template <class T>
  void length(CircLinkedList<T>* circlinkedList)
  {cout << "$ 执行计算链表的结点总数函数，Length = " << circlinkedList->Length() << endl;
  }//搜索数据值为x的结点并返回
  template <class T>
  void search(CircLinkedList<T>* circlinkedList)
  {cout << "$ 执行搜索数据值为x的结点并返回函数" << endl;T data = get_data<T>();LinkNode<T> *node = circlinkedList->Search(data);if (NULL == node){cout << "* 搜索失败" << endl;return;}cout << "* 搜索成功，data = " << node->data << endl;
  }   //获取第i个结点并返回
  template <class T>
  void locate(CircLinkedList<T>* circlinkedList)
  {cout << "$ 执行获取第i个结点并返回函数" << endl;int n_item = get_item<T>();LinkNode<T> *node = circlinkedList->Locate(n_item);if ((NULL == node) || (circlinkedList->GetHead() == node)){cout << "* 获取失败" << endl;return;}cout << "* 获取成功，item = " << n_item << "，data = " << node->data << endl;
  }//获取第i个结点的数据值保存至x，并返回获取成功与否
  template <class T>
  void getdata(CircLinkedList<T>* circlinkedList)
  {cout << "$ 执行获取第i个结点的数据值保存至x并返回获取成功与否函数" << endl;T data;int n_item = get_item<T>();if (false == circlinkedList->GetData(n_item, data)){cout << "* 获取失败" << endl;return;}cout << "* 获取成功，item = " << n_item << "，data = " << data << endl;
  }//修改第i个结点的数据值为x
  template <class T>
  void setdata(CircLinkedList<T>* circlinkedList)
  {cout << "$ 执行修改第i个结点的数据值为x函数" << endl;int n_item = get_item<T>();T data = get_data<T>();if (false == circlinkedList->SetData(n_item, data)){cout << "* 修改失败" << endl;return;}cout << "* 修改成功，item = " << n_item << "，data = " << data << endl;
  }//在第i个结点后插入数据值为x的新结点
  template <class T>
  void insert(CircLinkedList<T>* circlinkedList)
  {cout << "$ 执行在第i个结点后插入数据值为x的新结点函数" << endl;int n_item = get_item<T>();T data = get_data<T>();if (false == circlinkedList->Insert(n_item, data)){cout << "* 插入失败" << endl;return;}cout << "* 插入成功，item+1 = " << n_item+1 << "，data = " << data << endl;
  }//删除第i个结点，并将被删结点的数据值保存至x
  template <class T>
  void remove(CircLinkedList<T>* circlinkedList)
  {cout << "$ 执行删除第i个结点并将被删结点的数据值保存至x函数" << endl;T data;int n_item = get_item<T>();if (false == circlinkedList->Remove(n_item, data)){cout << "* 删除失败" << endl;return;}cout << "* 删除成功，item = " << n_item << "，data = " << data << endl;
  }//判断表是否为空
  template <class T>
  void isempty(CircLinkedList<T>* circlinkedList)
  {cout << "$ 执行判断表是否为空函数，IsEmpty = " << circlinkedList->IsEmpty() << endl;
  }//判断表是否为满
  template <class T>
  void isfull(CircLinkedList<T>* circlinkedList)
  {cout << "$ 执行判断表是否为满函数，IsFull = " << circlinkedList->IsFull() << endl;
  }//表排序——冒泡排序
  template <class T>
  void sort(CircLinkedList<T>* circlinkedList)
  {cout << "$ 执行表排序——冒泡排序函数" << endl;circlinkedList->Sort();
  }//前插法建立链表
  template <class T>
  void inputfront(CircLinkedList<T>* circlinkedList)
  {cout << "$ 执行前插法建立链表函数" << endl;T endTag = get_endtag<T>();circlinkedList->InputFront(endTag);
  }//后插法建立链表
  template <class T>
  void inputrear(CircLinkedList<T>* circlinkedList)
  {cout << "$ 执行后插法建立链表函数" << endl;T endTag = get_endtag<T>();circlinkedList->InputRear(endTag);
  }//输出所有结点的数据值
  template <class T>
  void output(CircLinkedList<T>* circlinkedList)
  {cout << "$ 执行输出所有结点的数据值函数" << endl; circlinkedList->Output();
  }//链表逆置
  template <class T>
  void reverse(CircLinkedList<T>* circlinkedList)
  {cout << "$ 执行链表逆置函数" << endl;circlinkedList->Reverse();
  }//清空链表
  template <class T>
  void make_empty(CircLinkedList<T>* circlinkedList)
  {cout << "$ 执行清空链表函数" << endl; circlinkedList->MakeEmpty();
  }//链表间赋值操作——重载等号运算符
  template <class T>
  void operator_copy(CircLinkedList<T>* circlinkedList)
  {cout << "$ 执行链表间赋值操作——重载等号运算符函数" << endl; CircLinkedList<T> cpy_linkedlist;cpy_linkedlist = *circlinkedList;//或cpy_linkedlist.operator=(*circlinkedList);cpy_linkedlist.Output();
  }//返回头结点的地址
  template <class T>
  void gethead(CircLinkedList<T>* circlinkedList)
  {       LinkNode<T> *head = circlinkedList->GetHead();cout << "$ 执行返回头结点的地址函数，&first = " << &head << endl;
  }//循环链表操作选择
  template <class T>
  void select_operation(CircLinkedList<T>* circlinkedList)
  {if (NULL == circlinkedList){cout << "* 没有构造循环链表，请先构造循环链表。" << endl;return;}string s_operation;while (s_operation != "0"){cout << "\n==> 请输入功能选项编号(按\"0\"退出程序)：";cin >> s_operation;while (false == CircLinkedList<T>::IsNumber(s_operation)){cout << "* 输入有误，请重新输入：";cin >> s_operation;}int n_operation = atoi(s_operation.c_str());switch (n_operation){case EXIT://退出{cout << "$ 退出程序" << endl;break;}case CONSTRUCT_COPY://拷贝构造链表{construct_copy(circlinkedList);break;}case LENGTH://计算链表的结点总数{length(circlinkedList);break;}case SEARCH://搜索数据值为x的结点并返回{search(circlinkedList);break;}case LOCATE://获取第i个结点并返回{locate(circlinkedList);break;}case GETDATA://获取第i个结点的数据值保存至x，并返回获取成功与否{getdata(circlinkedList);break;}case SETDATA://修改第i个结点的数据值为x{setdata(circlinkedList);break;}case INSERT://在第i个结点后插入数据值为x的新结点{insert(circlinkedList);break;}case REMOVE://删除第i个结点，并将被删结点的数据值保存至x{remove(circlinkedList);break;}case ISEMPTY://判断表是否为空{isempty(circlinkedList);break;}case ISFULL://判断表是否为满{isfull(circlinkedList);break;}case SORT://表排序——冒泡排序{sort(circlinkedList);break;}case INPUTFRONT://前插法建立链表{inputfront(circlinkedList);break;}case INPUTREAR://后插法建立链表{inputrear(circlinkedList);break;}case OUTPUT://输出所有结点的数据值{output(circlinkedList);break;}case REVERSE://链表逆置{reverse(circlinkedList);break;}case MAKEEMPTY://清空链表{make_empty(circlinkedList);break;}case OPERATOR_COPY://链表间赋值操作——重载等号运算符{operator_copy(circlinkedList);break;}case GETHEAD://返回头结点的地址{gethead(circlinkedList);break;}default:{cout << "* 请输入正确的功能选项编号" << endl;break;}}}
  }int main(int argc, char* argv[])
  {print_description();CircLinkedList<int> *circlinkedList = construct_circlinkedlist<int>();select_operation(circlinkedList);destory_circlinkedlist(circlinkedList);system("pause");return 0;
  }

3. 循环链表的优缺点

3.1 优点

• 没有空间限制，存储元素的个数无上限，基本只与内存空间大小有关。
• 插入和删除元素速率高。
• 只要知道表中任何一个结点的地址，就可以遍历表中其他任一结点。

3.2 缺点

• 占用额外的空间以存储指针(浪费空间)。
• 随机存取元素速率低。
• 不能直接获取一个结点的前驱结点。

3.3 循环链表的适用情况

• 适用于需要进行大量增添和删除元素操作而对访问元素无要求的，及预先无法确定表的大小的程序。

参考文献：
[1]《数据结构(用面向对象方法与C++语言描述)(第2版)》殷人昆——第二章
[2]《C/C++常用算法手册》秦姣华、向旭宇——第二章
[3] 百度搜索关键字：循环链表的优缺点