中文字幕日韩精品一区二区免费_精品一区二区三区国产精品无卡在_国精品无码专区一区二区三区_国产αv三级中文在线

數(shù)據(jù)結(jié)構(gòu)（七）——雙向鏈表-創(chuàng)新互聯(lián)

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

一、雙向鏈表簡介

1、單鏈表的缺陷

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

10年積累的網(wǎng)站設(shè)計制作、成都網(wǎng)站制作經(jīng)驗，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識你，你也不認(rèn)識我。但先網(wǎng)站設(shè)計后付款的網(wǎng)站建設(shè)流程，更有石拐免費網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

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

雙鏈表是鏈表的一種，由節(jié)點組成，每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(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é)點
          Node* node = createNode();
          if(node != NULL)
          {
              //當(dāng)前結(jié)點定位到目標(biāo)位置
              Node* current = position(index);
              //當(dāng)前結(jié)點的下一個結(jié)點
              Node* next = current->next;
              //修改插入結(jié)點的值
              node->value = value;
              //將當(dāng)前位置的下一個結(jié)點作為插入結(jié)點的下一個結(jié)點
              node->next = next;
              //將要插入結(jié)點作為當(dāng)前結(jié)點的下一個結(jié)點
              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é)點長度加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é)點指向頭結(jié)點
        Node* current = position(index);

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

    }

三、雙向鏈表的實現(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é)點
      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é)點
          Node* node = createNode();
          if(node != NULL)
          {
              //當(dāng)前結(jié)點定位到目標(biāo)位置
              Node* current = position(index);
              //當(dāng)前結(jié)點的下一個結(jié)點
              Node* next = current->next;
              //修改插入結(jié)點的值
              node->value = value;
              //將當(dāng)前位置的下一個結(jié)點作為插入結(jié)點的下一個結(jié)點
              node->next = next;
              //將要插入結(jié)點作為當(dāng)前結(jié)點的下一個結(jié)點
              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é)點長度加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é)點指向頭結(jié)點
        Node* current = position(index);

        //使用toDel指向要刪除的結(jié)點
        Node* toDel = current->next;
        Node* next = toDel->next;
        if(m_current == toDel)
        {
            m_current = next;
        }
        //將當(dāng)前結(jié)點的下一個結(jié)點指向要刪除結(jié)點的下一個結(jié)點
        current->next = next;
        if(next != NULL)
            next->pre = current;
        m_length--;//鏈表結(jié)點長度減1
        destroy(toDel);//釋放要刪除的結(jié)點的堆空間
      }
      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é)點指向頭結(jié)點
          Node* current = position(index);

          //修改目標(biāo)結(jié)點的數(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é)點指向頭結(jié)點
          Node* current = position(index);
          //遍歷到目標(biāo)位置

          //獲取目標(biāo)結(jié)點的數(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é)點
        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é)點
     while(m_header.next)
      {
          //要刪除的結(jié)點為頭結(jié)點的下一個結(jié)點
          Node* toDel = m_header.next;
          //將頭結(jié)點的下一個結(jié)點指向刪除結(jié)點的下一個結(jié)點
          m_header.next = toDel->next;
          m_length--;
          destroy(toDel);//釋放要刪除結(jié)點
      }

    }

    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ù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

當(dāng)前標(biāo)題：數(shù)據(jù)結(jié)構(gòu)（七）——雙向鏈表-創(chuàng)新互聯(lián)
路徑分享：http://www.rwnh.cn/article20/dgsoco.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、小程序開發(fā)、網(wǎng)站維護(hù)、ChatGPT、網(wǎng)站設(shè)計公司、靜態(tài)網(wǎng)站

廣告

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

成都做網(wǎng)站
澄迈县| 邮箱| 塔河县| 雷山县| 铜鼓县| 浑源县| 元谋县| 祥云县| 武陟县| 濮阳市| 长葛市| 三门峡市| 新泰市| 驻马店市| 丁青县| 伊宁市| 环江| 衡南县| 化州市| 固安县| 望江县| 赣州市| 麻栗坡县| 大悟县| 凤山县| 泽普县| 新宾| 孝义市| 泾源县| 孝义市| 来安县| 金平| 杭州市| 江源县| 葵青区| 临泉县| 景谷| 泸溪县| 海宁市| 临邑县| 武冈市|