29 循环链表的实现

循环链表的实现

什么是循环链表？
- 概念上
  - 任意数据元素都有一个前驱和一个后继
  - 所有的数据元素的关系构成一个逻辑上的环
- 实现上
  - 循环链表是一种特殊的单链表
  - 尾结点的指针域保存了首结点的地址
循环链表的逻辑构成

循环链表的继承层次结构

循环链表的实现思路
- 通过模板定义CircleList类，继承自LinkList类
- 定义内部函数last_to_first()，用于将单链表首尾相连
- 特殊处理:首元素的插入操作和删除操作
- 重新实现:清空操作和遍历操作
循环链表的实现要点
- 插入位置为0时:
  - 头结点和尾结点均指向新结点
  - 新结点成为首结点插入链表
- 删除位置为0时:
  - 头结点和尾结点指向位置为1的结点
  - 安全销毁首结点

编程实验(一)

循环链表的实现

#ifndef CIRCULARLIST_H
#define CIRCULARLIST_H

#include "LinkedList.h"

namespace KylinLib {
template<typename T>
class CircularList : public LinkedList<T>{
    using Node = typename LinkedList<T>::Node;
public:
    virtual bool insert(size_t index,const T &value){
        auto i = index%(this->m_size+1);
        bool ret = LinkedList<T>::insert(i,value);
        if(ret&&(i==0)) lastToFirst();
        return ret;
    }

    virtual bool append(const T &value){
        return insert(this->m_size,value);
    }

    virtual bool set(size_t index,const T &value){
        auto i = mod(index);
        return LinkedList<T>::set(i,value);
    }

    virtual bool get(size_t index,T &value) const {
        auto i = mod(index);
        return LinkedList<T>::get(i,value);
    }

    virtual const T& at(size_t index) const{
        auto i = mod(index);
        return this->position(i)->next->value;
    }

    virtual bool remove(size_t index){
        auto i = mod(index);
        if(i==0){
            auto toDel = this->m_header.next;
            if(toDel==nullptr) return false;
            this->m_header.next = toDel->next;
            this->m_size--;
            if(this->m_size==0){
                this->m_header.next = nullptr;
                this->m_current = nullptr;
            } else {
                lastToFirst();
                if(this->m_current==toDel)
                    this->m_current = toDel->next;
            }
            this->destroy(toDel);
            return true;
        } else {
            return LinkedList<T>::remove(i);
        }
    }

    virtual void clear(){
        while (this->m_size>1) {
            remove(1);
        }
        if(this->m_size==1){
            auto del = this->m_header.next;
            this->m_header.next = nullptr;
            this->m_size = 0;
            this->m_current = nullptr;
            this->destroy(del);
        }
    }

    virtual void begin(size_t index,size_t step) const{
        LinkedList<T>::begin(mod(index),step);
    }

    virtual bool end() const{
        return (this->m_size==0)||(this->m_current==nullptr);
    }

    virtual ~CircularList(){
        clear();
    }

protected:
    size_t mod(size_t index) const{
        return (this->m_size==0)?0:(index%this->m_size);
    }

    Node* last() const {
        if(this->m_size==0) return nullptr;
        return this->position(this->m_size-1)->next;
    }

    void lastToFirst(){
        last()->next = this->m_header.next;
    }
};
}
#endif // CIRCULARLIST_H

循环链表的应用
- 约瑟夫环问题
  - 已知n个人(以编号0,1,2,3,...,n-1分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列；依次规律重复下去，直到圆桌周围的人全部出列。
小故事在罗马人占领桥塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第一个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从。那么，一开始要站在什么地方才能避免被处决?

编程实验(二)

约瑟夫问题

void JosephCircle(size_t num,size_t begin,size_t step){
    KylinLib::CircularList<size_t> list;
    for (size_t i=1;i<=num;i++) {
        list.append(i);
    }

    for (list.begin(begin+step-2,step-1);!list.end();list.next()) {
        std::cout<<list.current()<<std::endl;
        list.remove(static_cast<size_t>(list.find(list.current())));
    }
}

小结

循环链表是一种特殊的单链表
尾节点的指针域保存了首节点的地址
特殊处理首元素的插入操作和删除操作
重新实现清空操作和遍历操作

30 双向链表的实现

双向链表的实现

A:学习完循环链表后，我有一个新的想法

B:什么新的想法?

A:单链表的每个结点增加一个指针域，用于指向结点的前驱。

B:有意思，这样的话......

单链表的另一个缺陷
- 单向性
  - 只能从头结点开始高效访问链表中的数据元素
- 缺陷
  - 如果需要逆向访问单链表中的数据元素将极其低效
```
int main()
{
    LinkList<int> l;
    for(int i=0;i<5;i++)    //O(n)
    {
        l.insert(0,i);
    }
    for(int i=l.length()-1;i>=0;i++)    //O(n2)
    {
        cout<<l.get(i)<<endl;
    }
    return 0;
}
```
新的线性表设计思路:在"单链表"的结点中增加一个指针pre，用于指向当前结点的前驱结点。
双向链表的继承层次结构

DuaLinkList的定义

template<typename T>
class DuaLinkList : public List<T>
{
protectd:
    struct Node : public Object
    {    
        T value;
        Node *next;
        Node *pre;
    };
    mutable struct : public Object
    {
        char reserved[sizeof(T)];
        Node *next;
        Node *pre;
    }m_header;
    //... ...
};

编程实验

双向链表的实现

小结

双向链表是为了弥补单链表的缺陷而重新设计的
在概念上，双向链表不是单链表，没有继承关系
双向链表中的游标能够直接访问当前结点的前驱和后继
双向链表是线性表概念的最终实现(更贴近理论上的线性表)

深度思考

开放性问题

DuaLinkList和LinkList中存在很多完全一样的代码，如何进行重构降低代码的冗余性？冗余代码的出现是否意味着DuaLinkList和LinkList之间应该是继承关系？

循环链表的实现​

编程实验(一)​

编程实验(二)​

小结​

30 双向链表的实现

双向链表的实现​

编程实验​

小结​

深度思考​

扩展练习​

循环链表的实现

编程实验(一)

编程实验(二)

小结

双向链表的实现

编程实验

小结

深度思考

扩展练习