數(shù)據(jù)結(jié)構(gòu)（七）——雙向鏈表

一、雙向鏈表簡介

1、單鏈表的缺陷

單鏈表只能從頭結(jié)點(diǎn)開始訪問鏈表中的數(shù)據(jù)元素，如果需要逆序訪問單鏈表中的數(shù)據(jù)元素將極其低效。

創(chuàng)新互聯(lián)公司自2013年創(chuàng)立以來，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元羅湖做網(wǎng)站,已為上家服務(wù),為羅湖各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:13518219792

2、雙向鏈表的結(jié)構(gòu)

雙鏈表是鏈表的一種，由節(jié)點(diǎn)組成，每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。
數(shù)據(jù)結(jié)構(gòu)（七）——雙向鏈表

3、雙向鏈表類的基本結(jié)構(gòu)

template <typename T>
class DualLinkedList:public List<T>
{
protected:
  struct Node:public Object
  {
    T value;//數(shù)據(jù)域
    Node* next;//后繼指針域
    Node* pre;//前驅(qū)
  };
  mutable struct:public Object
  {
    char reserved[sizeof(T)];//占位空間
    Node* next;
    Node* pre;
  }m_header;
  int m_length;
  int m_step;
  Node* m_current;
}

二、雙向鏈表的操作

1、雙向鏈表的插入操作

數(shù)據(jù)結(jié)構(gòu)（七）——雙向鏈表

bool insert(int index, const T& value)
    {
      //判斷目標(biāo)位置是否合法
      bool ret = (0 <= index) && (index <= m_length);
      if(ret)
      {
          //創(chuàng)建新的結(jié)點(diǎn)
          Node* node = createNode();
          if(node != NULL)
          {
              //當(dāng)前結(jié)點(diǎn)定位到目標(biāo)位置
              Node* current = position(index);
              //當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
              Node* next = current->next;
              //修改插入結(jié)點(diǎn)的值
              node->value = value;
              //將當(dāng)前位置的下一個(gè)結(jié)點(diǎn)作為插入結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
              node->next = next;
              //將要插入結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
              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++;//鏈表結(jié)點(diǎn)長度加1
          }
          else
          {
              THROW_EXCEPTION(NoEnoughMemoryException, "No enough memmory...");
          }
      }
      else
      {
          THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter index is invalid...");
      }
      return ret;
    }
    bool insert(const T& value)
    {
      return insert(m_length, value);
    }

2、雙向鏈表的刪除操作

數(shù)據(jù)結(jié)構(gòu)（七）——雙向鏈表

bool remove(int index)
    {
      //判斷目標(biāo)位置是否合法
      bool ret = (0 <= index) && (index < m_length);
      if(ret)
      {
        //當(dāng)前結(jié)點(diǎn)指向頭結(jié)點(diǎn)
        Node* current = position(index);

        //使用toDel指向要?jiǎng)h除的結(jié)點(diǎn)
        Node* toDel = current->next;
        Node* next = toDel->next;
        if(m_current == toDel)
        {
            m_current = next;
        }
        //將當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向要?jiǎng)h除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
        current->next = next;
        if(next != NULL)
            next->pre = current;
        m_length--;//鏈表結(jié)點(diǎn)長度減1
        destroy(toDel);//釋放要?jiǎng)h除的結(jié)點(diǎn)的堆空間
      }
      else
      {
          THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid...");
      }
      return ret;

    }

三、雙向鏈表的實(shí)現(xiàn)

template <typename T>
  class DualLinkedList:public List<T>
  {
  protected:
    struct Node:public Object
    {
      T value;//數(shù)據(jù)域
      Node* next;//后繼指針域
      Node* pre;//前驅(qū)
    };
    mutable struct:public Object
    {
      char reserved[sizeof(T)];//占位空間
      Node* next;
      Node* pre;
    }m_header;
    int m_length;
    int m_step;
    Node* m_current;
  protected:
    Node* position(int index)const
    {
      //指針指向頭結(jié)點(diǎn)
      Node* ret = reinterpret_cast<Node*>(&m_header);
      //遍歷到目標(biāo)位置
      for(int i = 0; i < index; i++)
      {
          ret = ret->next;
      }
      return ret;
    }
  public:
    DualLinkedList()
    {
      m_header.next = NULL;
      m_header.pre = NULL;
      m_length = 0;
      m_step = 1;
      m_current = NULL;
    }
    virtual ~DualLinkedList()
    {
      clear();
    }
    bool insert(int index, const T& value)
    {
      //判斷目標(biāo)位置是否合法
      bool ret = (0 <= index) && (index <= m_length);
      if(ret)
      {
          //創(chuàng)建新的結(jié)點(diǎn)
          Node* node = createNode();
          if(node != NULL)
          {
              //當(dāng)前結(jié)點(diǎn)定位到目標(biāo)位置
              Node* current = position(index);
              //當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
              Node* next = current->next;
              //修改插入結(jié)點(diǎn)的值
              node->value = value;
              //將當(dāng)前位置的下一個(gè)結(jié)點(diǎn)作為插入結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
              node->next = next;
              //將要插入結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
              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++;//鏈表結(jié)點(diǎn)長度加1
          }
          else
          {
              THROW_EXCEPTION(NoEnoughMemoryException, "No enough memmory...");
          }
      }
      else
      {
          THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter index is invalid...");
      }
      return ret;
    }
    bool insert(const T& value)
    {
      return insert(m_length, value);
    }
    bool remove(int index)
    {
      //判斷目標(biāo)位置是否合法
      bool ret = (0 <= index) && (index < m_length);
      if(ret)
      {
        //當(dāng)前結(jié)點(diǎn)指向頭結(jié)點(diǎn)
        Node* current = position(index);

        //使用toDel指向要?jiǎng)h除的結(jié)點(diǎn)
        Node* toDel = current->next;
        Node* next = toDel->next;
        if(m_current == toDel)
        {
            m_current = next;
        }
        //將當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向要?jiǎng)h除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
        current->next = next;
        if(next != NULL)
            next->pre = current;
        m_length--;//鏈表結(jié)點(diǎn)長度減1
        destroy(toDel);//釋放要?jiǎng)h除的結(jié)點(diǎn)的堆空間
      }
      else
      {
          THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid...");
      }
      return ret;

    }
    bool set(int index, const T& value)
    {
      //判斷目標(biāo)位置是否合法
      bool ret = (0 <= index) && (index < m_length);
      if(ret)
      {
          //將當(dāng)前結(jié)點(diǎn)指向頭結(jié)點(diǎn)
          Node* current = position(index);

          //修改目標(biāo)結(jié)點(diǎn)的數(shù)據(jù)域的值
          current->next->value = value;
      }
      else
      {
          THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid...");
      }
      return ret;
    }
    bool get(int index, T& value)const
    {
      //判斷目標(biāo)位置是否合法
      bool ret = (0 <= index) && (index < m_length);
      if(ret)
      {
          //當(dāng)前結(jié)點(diǎn)指向頭結(jié)點(diǎn)
          Node* current = position(index);
          //遍歷到目標(biāo)位置

          //獲取目標(biāo)結(jié)點(diǎn)的數(shù)據(jù)域的值
          value = current->next->value;
      }
      else
      {
          THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid...");
      }
      return ret;
    }
    //重載版本
    T get(int index)const
    {
      T ret;
      if(get(index, ret))
        return ret;
    }
    int length()const
    {
      return m_length;
    }

    int find(const T& value)const
    {
        int ret = -1;
        //指向頭結(jié)點(diǎn)
        Node* node = m_header.next;
        int i = 0;
        while(node)
        {
            //找到元素，退出循環(huán)
            if(node->value == value)
            {
                ret = i;
                break;
            }
            else
            {
                node = node->next;
                 i++;
            }
        }
        return ret;
    }
    void clear()
    {
      //遍歷刪除結(jié)點(diǎn)
      while(m_header.next)
      {
          //要?jiǎng)h除的結(jié)點(diǎn)為頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
          Node* toDel = m_header.next;
          //將頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向刪除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
          m_header.next = toDel->next;
          m_length--;
          destroy(toDel);//釋放要?jiǎng)h除結(jié)點(diǎn)
      }

    }

    virtual bool move(int pos, int step = 1)
    {
      bool ret = (0 <= pos) && (pos < m_length) && (0 < step);
      if(ret)
      {
           m_current = position(pos)->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, "Invalid Operation...");
        }
    }
    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);
    }
    virtual Node* createNode()
    {
        return new Node();
    }
    virtual void destroy(Node* node)
    {
        delete node;
    }
  };

網(wǎng)頁標(biāo)題：數(shù)據(jù)結(jié)構(gòu)（七）——雙向鏈表
地址分享：http://bm7419.com/article36/jcejsg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、云服務(wù)器、全網(wǎng)營銷推廣、企業(yè)建站、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站維護(hù)

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

數(shù)據(jù)結(jié)構(gòu)（七）——雙向鏈表