数据结构(05)_链表01（单链表、静态单链表、单向循环链表）

1.线性表的链式存储结构

1.1.链式存储的定义：

为了表示每个数据元素与其直接后继之间的逻辑关系，数据元素除过存储本身的信息之外，还需要存储其后继元素的地址信息。

链式存储结构的逻辑结构：

成都创新互联公司专业提供成都主机托管四川主机托管成都服务器托管四川服务器托管，支持按月付款！我们的承诺：贵族品质、平民价格，机房位于中国电信/网通/移动机房，成都移动云计算中心服务有保障！

• 数据域：存储数据元素本身
• 指针域：存储相邻节点的地址
  
  统一的专业术语：
  — 顺序表：—顺序存储结构的线性表
  — 链表：基于链式存储的线性表
• 单链表：每个节点只包含直接后继的地址信息
• 循环链表：单链表的最后一个节点的后继为第一个节点
• 双向链表：节点中包含其直接前驱和后继的信息
  链表中基本概念：
  — 头节点：链表中的辅助节点，包含指向第一个数据元素的指针，一般不包含数据。
  — 数据节点：链表中代表数据元素的节点，表现为：（数据元素、地址）
  — 尾节点：链表中最后一个节点，包含的地址信息为空

  1.2.单链表

  单链表中的节点定义：
  
  注意：这里的struct是用来定义一个类，与class的访问属性相反，默认为public
  单链表的内部结构：
  头节点在单链表中的意义是：辅助数据元素的定位，方便插入和删除，因此，头节点不存储实际的数据。
  

  1.3.单链表的插入与删除：

  插入：

• 从头节点开始，通过current指针定位到目标位置
• 从堆空间中申请新的Node节点
• 执行插入操作(注意先处理后半部分的挂接，否则会导致链表断开，数据丢失，内存泄漏)

  node->value = e;
  node->next = current->next;
  Current->next = node;

  删除：

• 从头节点开始，通过current指针定位到目标位置
• 使用toDel指针指向需要删除的节点

• 执行操作

  toDel = current->next;
  current->next = toDel->nex;
  delete toDel;

  2.单链表的实现

  2.1.设计要点和实现

  类族结构：
  
  — 类模板，通过头节点访问后继节点
  — 定义内部节点的类型Node，用于描述数据域和指针域
  — 实现线性表的关键操作，增、删、查等。

  template < typename T >
  class LinkList : public List
  {
  protected:
  struct Node : public Object
  {
      Node * next;
      T value;
  };
  int m_length;
  mutable Node m_header;
  // 当前所找到的节点不是要直接操作的节点，要操作的是该节点的next
  Node *position(int i) const
  public:
  LinkList()
  bool insert(const T& e)
  bool insert(int index, const T& e)
  bool remove(int index)
  bool set(int index, const T& e)
  T get(int index)
  bool get(int index, T& e) const
  int length() const
  void clear()
  ~LinkList()
  };

  2.2.隐患和优化

  优化：
  代码中多个函数存在对操作节点的定位逻辑。可以将该段代码实现为一个position函数。

  Node *position(int i) const
  {
      Node *ret = reinterpret_cast(&m_header);
  
      for(int p=0; pnext;
      }
  
      return ret;
  }

  隐患：
  
  LinkList L; // 抛出异常，分析为什么我们没有定义 Test 对象，但确抛出了异常
  原因在于单链表头节点构造时会调用泛指类型的构造函数
  解决方案：
  头节点构造时，避免调用泛指类型的构造函数，也即是说要自定义头节点的类型，并且该类型是一个匿名类型

  mutable struct : public Object
  {
      char reserved[sizeof(T)];
      Node *next;
  }m_header;

  注意：这里我们自定义都头结点类型和Node的内存结构上要一模一样（不要将两个成员变量的位置交换）。

  22.3 单链表的最终实现

template 
class LinkList : public List
{
protected:
    int m_length;
    int m_step;

    struct Node : public Object
    {
        Node* next;
        T value;
    };
    // 游标,获取游标指向的数据元素,遍历开始前将游标指向位置为0的数据元素,通过节点中的next指针移动游标
    Node* m_current;

    // 构造头节点时，会调用泛指类型的构造函数，如果泛指类型构造函数中抛出异常，将导致构造失败
    //mutable Node m_header;
    // 为了避免调用泛指类型的构造函数，自定义头节点的类型(内存结构上要一模一样)，并且该类型是一个匿名类型（没有类型名）
    mutable struct : public Object
    {
        Node *next;
        char reserved[sizeof(T)];
    }m_header;

    Node* position(int index) const
    {
        Node* ret = reinterpret_cast(&m_header);

        for(int p=0; pnext;
        }

        return ret;
    }

    virtual Node* create()
    {
        return new Node();
    }

    virtual void destroy(Node* pNode)
    {
        delete pNode;
    }

public:
    LinkList()
    {
        m_header.next = NULL;
        m_length = 0;
        m_step = 0;
        m_current = NULL;
    }

    int find(const T& e) const
    {
        int ret = -1;
        Node* node = m_header.next;

        for(int i=0; ivalue == e)
            {
                ret = i;
                break;
            }

            node = node->next;
        }

        return ret;
    }

    bool insert(const T& e)
    {
        return insert(m_length, e);
    }

    bool insert(int index, const T& e)
    {
        bool ret = (index>=0) && (index<=m_length);

        if(ret)
        {
            Node* node = create();
            if(NULL != node)
            {
                Node* current = position(index);

                node->next = current->next;
                current->next = node;
                node->value =e;
                m_length++;
            }
            else
            {
                THROW_EXCEPTION(NoEnoughMemoryException, "no enough memory to insert node.");
            }
        }

        return ret;
    }

    bool remove(int index)
    {
        bool ret = (index>=0) && (index<=m_length);

        if(ret)
        {
            Node* current = position(index);

            Node* toDel = current->next;
            if( toDel ==  m_current)
            {
                m_current = toDel->next;    // 确保当前元素删除后m_current指向正确的位置
            }
            current->next = toDel->next;
            destroy(toDel);
            m_length--;
        }

        return ret;
    }

    bool set(int index, const T& e)
    {
        bool ret = (index>=0) && (index<=m_length);

        if(ret)
        {
            Node* current = position(index);
            current->next->value = e;
        }

        return ret;
    }

    virtual T get(int index) const
    {
        T ret;

        if(get(index, ret))
        {
            return ret;
        }
        else
        {
            THROW_EXCEPTION(IndexOutOfBoundsException, "index out of range.");
        }
    }

    bool get(int index, T& e) const
    {
        bool ret = (index>=0) && (index<=m_length);

        if(ret)
        {
            Node* current = position(index);
            e = current->next->value;
        }

        return ret;
    }

    void traverse(void)     //O(n^2)
    {
        for(int i=0; i0);

        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,"No value at current position...");
        }
    }

    virtual bool next()
    {
        int i =0;

        while((inext;
            i++;
        }

        return(i == m_step);
    }

    int length() const
    {
        return m_length;
    }

    void clear()
    {
        while(m_header.next)
        {
            Node* toDel = m_header.next;
            m_header.next = toDel->next;
            destroy(toDel);
            m_length--;
        }
    }

    ~LinkList()
    {
        clear();
    }

};

3.顺序表和单链表的对比分析

3.1.代码优化

1.查找操作：
可以为线性表list增加一个查找操作， int find (const T& e) const
参数为待查找的元素，返回值为查找到的元素首次出现的位置，没有找到返回 -1
2.比较操作：
当我们定义的了上述查找函数之后，线性表中的数据为类类型时，查找函数编译出错，原因在于我们没有重载==操作符。
解决的办法，在顶层父类Object中重载==和!=操作符，并且让自定义的类继承自顶层父类Object。

3.2.对比分析

单链表和顺序表的时间复杂度对比：

问题：
顺序表的整体时间复杂度比单链表低，那么单链表还有使用的价值吗？实际工程中为什么单链表反而用的比较多？
——实际工程中，时间复杂度只是效率的一个参考指标

• 对于内置基础类型，顺序表和单链表的效率不相上下（或者说顺序表更优）
• 对于自定义类型，顺序表在效率上低于单链表
  效率的深度分析：
  插入和删除
  ——顺序表：涉及大量数据对象的复制操作
  ——单链表只涉及指针操作，效率与对象无关
  数据访问
  ——顺序表：随机访问，可以直接定位数据对象
  ——单链表：顺序访问，必须从头开始访问数据无法直接定位
  工程开发中的选择:
  顺序表
  ——数据元素的类型相对简单，不涉及深拷贝
  ——数据元素相对稳定，访问操作远远多于插入和删除
  单链表：
  ——数据元素相对复杂，复制操作相对耗时
  ——数据元素不稳定，需要经常插入和删除，访问操作较少
  总结：
• 线性表中元素的查找依赖于相等比较操作符（==）
• 顺序表适用于访问需求较大的场合（随机访问）
• 单链表适用于数据元素频繁插入删除的场合（顺序访问）
• 当数据元素类型相对简单时，两者效率不相上下

  4.单链表的遍历与优化

  4.1.遍历

  遍历一个单链表的方法：通过for循环来调用get函数即可实现。

  for(int i=0; i

  这段代码的时间复杂度为O（n^2）,所以我们希望对其优化，得到一个线性阶的遍历函数。

  4.2.设计思路：

• 在单链表的内部定义一个游标（Node *m_current）
• 遍历开始前将游标指向位置为0的数据元素
• 获取游标指向的数据元素
• 通过节点中的next指针移动游标
• 提供一组遍历相关的函数，以线性的时间复杂度遍历链表
  
  函数原型：

  bool move(int i, int step = 1);
  bool end();
  T current();
  bool next();

  4.3.优化

  单链表内部的一次封装：

  virtual Node *create()
  {
      return new Node();
  }
  virtual void destory(Node *pn)
  {
      delete pn;
  }

  进行上述封装得到意义：增加程序的可扩展性

  5.静态单链表的实现

  5.1.单链表的缺陷：

  长时间使用单链表对象频繁的增加和删除数据元素，会导致堆空间产生大量的内存碎片，导致系统运行缓慢。
  新的线性表：
  在单链表的内部增加一片预留的空间，所有的node对象都在这篇空间中动态创建和动态销毁。
  
  层次结构：
  

  5.2.设计思路：

• 类模板，继承自LinkList
• 在类中定义固定大小的空间（unsigned char[N]）
• 重写create和destroy函，改变内存的分配和归还方式
• 在Node类中重载operator new，用于指定在内存上创建对象

template < typename T, int N>
class StaticLinkList : public LinkList
{
protected:
    // (1)注意这里不能直接写为Node，编译报错，原因是Node中涉及泛指类型T，所以要声明 LinkList::Node
    // (2)上面的写法在某些编译情况下依然会报错，原因在于，编译器不知道这里的Node是一个类对象，还是一个静态成员对象，
    //    所以前面还需使用template声明Node是一个类对象。
    typedef typename LinkList::Node Node;
    struct SNode : public Node
    {
      void *operator new (unsigned int size, void *p)
      {
          (void)size;
          return p;
      }
    };

    unsigned char m_space[sizeof(SNode) *N];
unsigned int m_used[N];

   Node *create()
   {
        SNode *ret = NULL;

        for(int i=0; i(m_space) + i;
                ret = new(ret)SNode;    //返回指定内存地址
                m_used[i] = 1;
                break;
            }
        }
        return ret;
   }

   void destroy(Node *pn)
   {
        SNode *space = reinterpret_cast(m_space);
        SNode *spn = dynamic_cast(pn);

        for(int i=0; i~SNode();      //直接调用析构函数
            }
        }
   }

public:
    StaticLinkList()
    {
        for(int i=0; i

上节封装create和destroy的意义：
为了本节实现StaticList 做准备，两者的不同之处在于链表节点内存分配的不同，因此将仅有的不同封装与父类和子类的虚函数中。最终通过多态技术，来实现。

5.3 静态单链表的最终实现

template 
class StaticLinkList : public LinkList
{
protected:
    // typename 表明Node是一个类而非静态成员变量，Node中包含泛指类型，所以使用 LinkList指明
    typedef typename LinkList::Node Node;
    struct SNode : public Node
    {
        // 重载后的结果，返回指定内存空间
        void* operator new(unsigned int size, void* p)
        {
            (void)size;
            return p;
        }
    };

    unsigned int m_space[N];
    unsigned int m_used[N];

    Node* create(void)
    {
        SNode* ret = NULL;

        for(int i=0; i(m_space) + i;
                ret = new(ret) SNode();     //返回指定内存空间
                break;
            }
        }
        return ret;
    }

    void destroy(Node* pn)
    {
        SNode* space = reinterpret_cast(m_space);
        SNode* spn = dynamic_cast(pn);

        for(int i=0; i~SNode();
                break;
            }
        }
    }

public:
    StaticLinkList()
    {
        for(int i=0; iclear();
    }

};

template < typename T >
class CircleList : public LinkList
{
protected:
    Node* last() const
    void last_to_first() const
    int mod(int i) const
public:
    bool insert(const T& e)
    bool insert(int index, const T& e)
    bool remove(int index)
    bool set(int index, const T& e)
    bool get(int index, const T& e) const
    T get(int index) const
    int find (const T& e) const
    void clear()
    bool move(int i, int step)
    bool end()
    ~CircleList()
};

template < typename T >
class CircleLinkList : public LinkList
{
protected:
    typedef typename LinkList::Node Node;
    int mod(int i)
    {
        return ( (this->m_length == 0) ? 0 : (i % this->m_length));
    }

    Node* last()
    {
        return this->position(this->m_length-1)->next;
    }

    void last_to_first()
    {
        last()->next = this->m_header.next;
    }

public:
    bool insert(const T& e)
    {
        return insert(this->m_length, e);
    }

    bool insert(int index, const T& e)
    {
        bool ret = true;
        index = index % (this->m_length + 1);   // 可插入点=length+1

        ret = LinkList::insert(index, e);

        if(index == 0)
        {
            last_to_first();
        }

        return ret;
    }

    bool remove(int index)
    {
        bool ret = true;
        index = mod(index);

        if(index == 0)
        {
            Node* toDel = this->m_header.next;

            if(toDel != NULL)   // 类似于判断index是否合法
            {
                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_current = NULL;
                    this->m_header.next = NULL;
                    this->m_length = 0;
                }
            }
            else
            {
                ret = false;
            }
        }
        else
        {
            ret = LinkList::remove(index);
        }

        return ret;
    }

    T get(int index)
    {
        return LinkList::get(mod(index));
    }

    bool get(int index, T& e)
    {
        return LinkList::get(mod(index), e);
    }

    bool set(int index, const T& e)
    {
        return LinkList::set(mod(index), e);
    }

    int find(const T& e) const
    {
        int ret = -1;
        Node* node = this->m_header.next;

        for(int i=0; im_length; i++)
        {
            if(node->value == e)
            {
                ret = i;
                break;
            }

            node = node->next;
        }

        return ret;
    }

    bool move(int i, int step)
    {
        return LinkList::move(mod(i), step);
    }

    bool end()
    {
        return ( (this->m_current == NULL) || (this->m_length == 0) );
    }

    void clear()
    {
        if(this->m_length > 1)
        {
            remove(1);
        }
        if(this->m_length == 1)
        {
            Node* toDel = this->m_header.next;

            this->m_current = NULL;
            this->m_header.next = NULL;
            this->m_length = 0;

            this->destroy(toDel);
        }
    }

    ~CircleLinkList()
    {
        clear();
    }
};