一. 循环链表
A. 循环链表的介绍
a. 概念上
1. 任意数据元素都有一个前驱和一个后继
2. 所有数据元素的关系构成一个逻辑上的环
b. 实现上
1. 循环链表是一种特殊的单链表
2. 尾节点的指针域保存了首结点的地址
关系图如下
,
循环链表的继承层次结构
二. 循环链表的实现思路
A. 思路
1. 通过模板定义 CircleList 类, 继承自 LinkList 类
2. 定义内部函数 last_to_first(); 用于将单链表首尾相连
- Node* last()const// 尾节点
- {
- return this->position(this->m_length-1)->next;// 返回尾节点 (m_length-1)
- }
- void last_to_first()const// 将链表首尾相连
- {
- last()->next=this->m_header.next;// 尾节点的 next 指针指向首节点
- }
- int mod(int i)const// 取余的实现
- {
- return (this->m_length==0) ? 0 : ( i % this->m_length);
- }
3. 特殊处理: 首元素的插入操作和删除操作
4. 重新实现: 清空操作和遍历操作
B. 实现要点
a. 插入位置为 0 时
1. 头结点和尾结点均指向新结点
2. 新结点成为首节点插入链表
- bool insert(int i,const T& e)
- {
- bool ret=true;
- i=i%(this->m_length+1);//i 值取余
- ret=LinkList<T>::insert(i,e);// 调用父类的 insert 来实现子类的 insert
- if(ret&&(i==0))
- {
- last_to_first();
- }
- return ret;
- }
b. 删除位置为 0 时
1. 头结点和尾结点指向位置为 1 的结点
2. 安全销毁首结点
- bool remove(int i)
- {
- bool ret= true;
- i= mod(i);
- if(i==0)
- {
- Node *toDel=this->m_header.next;
- if(toDel!=NULL)
- {
- this->m_header.next=toDel->next;
- this->m_length--;
- // 链表不为空
- if(this->m_length>0)
- {
- last_to_first();
- if(this->m_current==toDel)
- {
- this->m_current=toDel->next;
- }
- }
- else
- { // 链表为空, 置空
- this->m_header.next=NULL;
- this->m_current=NULL;
- }
- this->destroy(toDel);// 在最后一步删除首节点 避免了异常安全
- }
- else
- {
- ret=false;
- }
- }
- else
- {
- ret=LinkList<T>::remove(i);
- }
- return ret;
- }
循环链表的完整实现代码如下
- #include "LinkList.h"
- namespace MyLib
- {
- template <typename T>
- class CircleList:public LinkList<T>
- {
- protected:
- typedef typename LinkList<T>::Node Node;
- Node* last()const// 尾节点
- {
- return this->position(this->m_length-1)->next;// 返回尾节点 (m_length-1)
- }
- void last_to_first()const// 将链表首尾相连
- {
- last()->next=this->m_header.next;// 尾节点的 next 指针指向首节点
- }
- int mod(int i)const
- {
- return (this->m_length==0) ? 0 : ( i % this->m_length);
- }
- public:
- bool insert(const T& e)// 重载
- {
- return insert(this->m_length,e);// 调用重载的版本
- }
- bool insert(int i,const T& e)
- {
- bool ret=true;
- i=i%(this->m_length+1);//i 值取余
- ret=LinkList<T>::insert(i,e);// 调用父类的 insert 来实现子类的 insert
- if(ret&&(i==0))
- {
- last_to_first();
- }
- return ret;
- }
- bool remove(int i)
- {
- bool ret= true;
- i= mod(i);
- if(i==0)
- {
- Node *toDel=this->m_header.next;
- if(toDel!=NULL)
- {
- this->m_header.next=toDel->next;
- this->m_length--;
- // 链表不为空
- if(this->m_length>0)
- {
- last_to_first();
- if(this->m_current==toDel)
- {
- this->m_current=toDel->next;
- }
- }
- else
- { // 链表为空, 置空
- this->m_header.next=NULL;
- this->m_current=NULL;
- }
- this->destroy(toDel);// 在最后一步删除首节点 避免了异常安全
- }
- else
- {
- ret=false;
- }
- }
- else
- {
- ret=LinkList<T>::remove(i);
- }
- return ret;
- }
- bool set(int i, const T &e)
- {
- i=mod(i);
- return LinkList<T>::set(i,e);// 调用父类函数
- }
- T get(int i)const
- {
- i=mod(i);
- return LinkList<T>::get(i);
- }
- T get(int i,const T&e) const
- {
- i=mod(i);
- return LinkList<T>::get(i,e);
- }
- int find(const T &e)const
- {
- int ret=-1;
- Node* slide=this->m_header.next;// 指针 slide 指向首节点
- for(int i=0;i<this->m_length;i++)//slide 指针遍历每个元素
- {
- if(slide->value==e)
- {
- ret=i;
- break;
- }
- slide=slide->next;
- }
- return ret;
- }
- void clear()
- {
- while(this->m_length>1)
- {
- remove(1);// 这里取 1 的原因是效率更高
- }
- if(this->m_length==1)
- {
- Node* toDel=this->m_header.next;
- this->m_header.next=NULL;
- this->m_current=NULL;
- this->m_length=0;
- this->destroy(toDel);
- }
- }
- bool move(int i, int step)//i 表示位置
- {
- i=mod(i);
- return LinkList<T>::move(i,step);
- }
- bool end()
- {
- return (this->m_length==0)||(this->m_current==NULL);
- }
- ~CircleList()// 析构函数直接调用 clear() 函数
- {
- clear();
- }
- };
- }
三. 小结
1. 循环链表是一种特殊的单链表
2. 尾结点的指针域保存了首结点的地址
3. 特殊处理首元素的插入操作和删除操作
4. 重新实现清空操作和遍历操作
四. 双向链表
由之前的单链表我们可以看到单链表存在的缺陷
1. 单向性 ==> 只能从头结点开始高效访问链表中的数据元素
2. 缺陷 ==> 如果需要逆向访问单链表中的数据元素将极其低效
新的线性表实现
设计思路: 在单链表的结点中增加一个指针 pre, 用于指向当前结点的前驱结点
示意图
双向链表的继承层次结构
简单的图示来说明双向链表的插入和删除操作
插入操作
如图所示四个步骤完成操作
1. 将插入结点的 next 指向 next
2.current 的 next 指向插入的结点
3. 插入结点的 pre 指向 curret
4.next 的 pre 指向 node
实现代码
- bool insert(int i,const T&e)
- {
- bool ret=((0<=i)&&(i<= m_length));
- if(ret)
- {
- Node* node=creat();
- if(node!=NULL)
- {
- Node* current=positon();
- Node* next=current->next;
- node->value=e;
- node->next=next;// 步骤 1
- current->next=node;// 步骤 2
- if(current!=reinterpret_cast<Node*>(&m_header))
- {
- node->pre=current;// 步骤 3
- }
- else
- {
- node->pre=NULL;
- }
- if(next!=NULL)
- {
- next-pre=node;
- }
- m_length++;
- }
- else
- {
- THROW_EXCEPTION(NoEoughMemoryException,"NoEoughMemory");
- }
- }
- return ret;
- }
删除操作
删除部分 3 个步骤
1. 将 current 的 next 指向 next
2. 将 next 的 pre 指向 current
3. 删除 toDel
代码实现如下
- bool remove(int i)
- {
- bool ret=((0<=i)&&(i<m_length));
- if(ret)
- {
- Node* current=position(i);
- Node* toDel=current->next;
- Node* next=toDel->next;
- if(m_current==toDel)
- {
- m_current=next;
- }
- current->next=next;// 步骤 1
- if(next!=NULL)
- {
- next->pre=toDel->pre;// 步骤 2
- }
- m_length--;
- destroy(toDel);// 步骤 3
- //m_length--;
- }
- return ret;
- }
双向链表的具体实现
- #include "List.h"
- #include "Exception.h"
- namespace MyLib
- {
- template <typename T>
- class DuaLinkList:public List<T>
- {
- protected:
- struct Node :public Object
- {
- T value;// 数据域 保存数据的值
- Node* next;// 指针域 指向后继节点的指针
- Node* pre;
- };
- mutable struct:public Object// 没有类型名的结构
- {
- char reserved[sizeof(T)];
- Node* next;
- Node* pre;
- } m_header;// 头节点 辅助定位元素
- int m_length;
- int m_step;
- Node* m_current;
- Node* position(int i) const// 程序优化
- {
- Node* ret=reinterpret_cast<Node*>(&m_header);//reinterpret_cast 强制类型转换
- for(int p=0;p<i;p++)
- {
- ret=ret->next;
- }
- return ret;
- }
- virtual Node* create()
- {
- return new Node();
- }
- virtual void destroy(Node* pn)
- {
- delete pn;
- }
- public:
- DuaLinkList()
- {
- m_header.next=NULL;
- m_header.pre=NULL;
- m_length=0;
- m_step=1;
- m_current=NULL;
- }
- bool insert(const T&e)
- {
- return insert(m_length,e);
- }
- bool insert(int i,const T&e)//i 表示插入的位置, e 表示插入的数据
- {
- bool ret=((0<=i)&&(i<= m_length));//m_length 表示链表的长度
- if(ret)
- {
- Node* node=create();
- if(node!=NULL)
- {
- Node* current=position(i);// 定位位置
- Node* next=current->next;// 表示插入的节点的后继节点
- node->value=e;
- node->next=next;
- current->next=node;
- if(current!=reinterpret_cast<Node*>(&m_header))
- {
- node->pre=current;
- }
- else
- {
- node->pre=NULL;
- }
- if(next!=NULL)
- {
- next->pre=node;
- }
- m_length++;
- }
- else
- {
- THROW_EXCEPTION(NoEoughMemoryException,"No ...");
- }
- }
- return ret;
- }
- bool remove(int i)
- {
- bool ret=((0<=i)&&(i<m_length));
- if(ret)
- {
- Node* current=position(i);
- Node* toDel=current->next;
- Node* next=toDel->next;
- if(m_current==toDel)
- {
- m_current=next;
- }
- current->next=next;
- if(next!=NULL)
- {
- next->pre=toDel->pre;
- }
- m_length--;
- destroy(toDel);
- //m_length--;
- }
- return ret;
- }
- bool set(int i,const T&e)
- {
- bool ret=((0<=i)&&(i<m_length));
- if(ret)
- {
- position(i)->next->value=e;
- }
- return ret;
- }
- int find(const T&e) const
- {
- int ret=-1;
- int i=0;
- Node* node=m_header.next;
- while(node)
- {
- if(node->value==e)
- {
- ret=i;
- break;
- }
- else
- {
- node=node->next;
- i++;
- }
- }
- return ret;
- }
- virtual T get(int i)const
- {
- T ret;
- if(get(i,ret))
- {
- return ret;
- }
- else
- {
- THROW_EXCEPTION(indexOutOfBoundsException,"...");
- }
- return ret;
- }
- bool get(int i,T&e)const
- {
- bool ret=((0<=i)&&(i<m_length));
- if(ret)
- {
- e=position(i)->next->value;
- }
- return ret;
- }
- int length()const
- {
- return m_length;
- }
- void clear()
- {
- while(m_length>0)
- {
- remove(0);
- }
- }
- virtual bool move(int i,int step=-1)
- {
- bool ret= (0<=i)&&(i<m_length)&&(step>0);
- if(ret)
- {
- m_current=position(i)->next;
- m_step=step;
- }
- return ret;
- }
- virtual bool end()
- {
- return (m_current==NULL);
- }
- virtual T current()
- {
- if(!end())
- {
- return m_current->value;
- }
- else
- {
- THROW_EXCEPTION(InvalidOperationException,"...");
- }
- }
- virtual bool next()
- {
- int i=0;
- while((i<m_step)&& !end())
- {
- m_current=m_current->next;
- i++;
- }
- return (i==m_step);
- }
- virtual bool pre()
- {
- int i=0;
- while((i<m_step)&& !end())
- {
- m_current=m_current->pre;
- i++;
- }
- return (i==m_step);
- }
- ~DuaLinkList()
- {
- clear();
- }
- };
- }
小结
1. 双向链表是为了弥补单链表的缺陷而重新设计的
2. 在概念上, 双向链表不是单链表, 没有继承关系
3. 双向链表中的游标能够直接访问当前结点的前驱和后继
4. 双向链表是线性表概念的最终实现
来源: http://www.bubuko.com/infodetail-2929722.html