99热在线精品一区二区三区_国产伦精品一区二区三区女破破_亚洲一区二区三区无码_精品国产欧美日韩另类一区

這篇文章給大家介紹數(shù)據(jù)結(jié)構(gòu)中的單鏈表如何理解，內(nèi)容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

創(chuàng)新互聯(lián)公司-成都網(wǎng)站建設(shè)公司，專注成都網(wǎng)站建設(shè)、網(wǎng)站制作、網(wǎng)站營銷推廣，主機域名，網(wǎng)頁空間，網(wǎng)站運營有關(guān)企業(yè)網(wǎng)站制作方案、改版、費用等問題，請聯(lián)系創(chuàng)新互聯(lián)公司。

數(shù)據(jù)結(jié)構(gòu)——單鏈表

一、單鏈表簡介

1、單鏈表簡介

單鏈表設(shè)計要點：
A、類模板，通過頭結(jié)點訪問后繼結(jié)點。
B、定義內(nèi)部結(jié)點類型，用于描述鏈表中的結(jié)點的數(shù)據(jù)域和指針域。
C、實現(xiàn)線性表的關(guān)鍵操作

2、單鏈表中結(jié)點的定義

struct Node:public Object
    {
      T value;//數(shù)據(jù)域
      Node* next;//指針域
    };

3、單鏈表的內(nèi)部結(jié)構(gòu)

頭結(jié)點不存儲實際的數(shù)據(jù)元素，用于輔助數(shù)據(jù)元素的定位，方便插入和刪除操作。

4、單鏈表中頭結(jié)點的定義

mutable Node m_header;

5、單鏈表類基本結(jié)構(gòu)

template 
class LinkedList:public List
{
protected:
  struct Node:public Object
  {
    T value;//數(shù)據(jù)域
    Node* next;//指針域
  };
  Node m_header;
  int m_length;
public:
  LinkedList();
  virtual ~LinkedList();
  bool insert(int index, const T& value);
  bool remove(int index);
  bool set(int index, const T& value);
  bool get(int index, T& value)const;
  int length()const;
  int find(const T& value)const;
  void clear();
};

二、單鏈表的操作

1、單鏈表的插入操作

在目標位置處插入數(shù)據(jù)元素流程如下：
A、從頭結(jié)點開始，提供current指針定位到目標位置
B、從堆空間申請新的Node結(jié)點
C、將新結(jié)點插入目標位置，并連接相鄰結(jié)點的邏輯關(guān)系。

bool insert(int index, const T& value)
    {
      //判斷目標位置是否合法
      bool ret = (0 <= index) && (index <= m_length);
      if(ret)
      {
          //創(chuàng)建新的結(jié)點
          Node* node = new Node();
          if(node != NULL)
          {
              //初始化當前結(jié)點為頭結(jié)點
              Node* current = &m_header;
              //遍歷到目標位置
              for(int i = 0; i < index; i++)
              {
                  current = current->next;
              }
              //修改插入結(jié)點的值
              node->value = value;
              //將當前位置的下一個結(jié)點作為插入結(jié)點的下一個結(jié)點
              node->next = current->next;
              //將要插入結(jié)點作為當前結(jié)點的下一個結(jié)點
              current->next = node;
              m_length++;//鏈表結(jié)點長度加1
          }
          else
          {
              THROW_EXCEPTION(NoEnoughMemoryException, "No enough memmory...");
          }
      }
      else
      {
          THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter index is invalid...");
      }
      return ret;
    }

2、單鏈表的刪除操作

在目標位置刪除數(shù)據(jù)元素的流程：
A、從頭結(jié)點開始，通過current指針定位到目標位置
B、使用toDel指針指向要被刪除的結(jié)點
C、刪除結(jié)點，并連接相鄰結(jié)點的邏輯關(guān)系

bool remove(int index)
    {
      //判斷目標位置是否合法
      bool ret = (0 <= index) && (index < m_length);
      if(ret)
      {
        //當前結(jié)點指向頭結(jié)點
        Node* current = &m_header;
        //遍歷到目標位置
        for(int i = 0; i < index; i++)
        {
            current = current->next;
        }
        //使用toDel指向要刪除的結(jié)點
        Node* toDel = current->next;
        //將當前結(jié)點的下一個結(jié)點指向要刪除結(jié)點的下一個結(jié)點
        current->next = toDel->next;
        m_length--;//鏈表結(jié)點長度減1
        delete toDel;//釋放要刪除的結(jié)點的堆空間
      }
      else
      {
          THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid...");
      }
      return ret;

    }

3、設(shè)置目標結(jié)點的值

設(shè)置目標結(jié)點的值的流程如下：
A、從頭結(jié)點開始，通過current指針定位到目標位置
B、修改目標結(jié)點的數(shù)據(jù)域的值

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

4、獲取目標結(jié)點的值

 bool get(int index, T& value)const
    {
      //判斷目標位置是否合法
      bool ret = (0 <= index) && (index < m_length);
      if(ret)
      {
          //當前結(jié)點指向頭結(jié)點
          Node* current = &m_header;
          //遍歷到目標位置
          for(int i = 0; i < index; i++)
          {
              current = current->next;
          }
          //獲取目標結(jié)點的數(shù)據(jù)域的值
          value = current->next->value;
      }
      else
      {
          THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid...");
      }
      return ret;
    }
    //重載版本
    T get(int index)const
    {
      T ret;
      get(index, ret);
      return ret;
    }

5、獲取單鏈表的長度

int length()const
    {
      return m_length;
    }

6、單鏈表的清空操作

void clear()
{
    //遍歷刪除結(jié)點
    while(m_header.next)
    {
            //要刪除的結(jié)點為頭結(jié)點的下一個結(jié)點
            Node* toDel = m_header.next;
            //將頭結(jié)點的下一個結(jié)點指向刪除結(jié)點的下一個結(jié)點
            m_header.next = toDel->next;
            delete toDel;//釋放要刪除結(jié)點
    }
    m_length = 0;
}

三、單鏈表的優(yōu)化

1、單鏈表中頭結(jié)點的缺陷

struct Node:public Object
{
    T value;//數(shù)據(jù)域
    Node* next;//指針域
};

    mutable Node m_header;

由于單鏈表在構(gòu)建時必須先創(chuàng)建頭結(jié)點，頭結(jié)點在創(chuàng)建時必須調(diào)用具體類型的構(gòu)造函數(shù)，如果具體類型的構(gòu)造函數(shù)拋出異常，則單鏈表對象將構(gòu)建失敗，并會傳遞具體類型構(gòu)造函數(shù)的異常。

class Test
{
public:
  Test()
  {
    throw 0;
  }
};

int main()
{
  LinkedList l;
  return 0;
}

因此，為了確保模板類的健壯性，需要對頭結(jié)點的創(chuàng)建進行優(yōu)化，即在創(chuàng)建單鏈表對象時不調(diào)用具體類型的構(gòu)造函數(shù)。

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

創(chuàng)建的匿名的頭結(jié)點m_header的內(nèi)存布局與Node對象的內(nèi)存布局完全一樣，并且不會調(diào)用具體類型T的構(gòu)造函數(shù)。

2、目標位置定位的代碼優(yōu)化

單鏈表的操作中經(jīng)常會定位到目標位置，因此可以將此部分代碼獨立構(gòu)建一個函數(shù)。

 Node* position(int index)const
    {
      //指針指向頭結(jié)點
      Node* ret = reinterpret_cast(&m_header);
      //遍歷到目標位置
      for(int i = 0; i < index; i++)
      {
          ret = ret->next;
      }
      return ret;
    }

3、鏈表的元素查找操作

為List模板類增加一個find操作：
virtual int find(const T& value)const = 0;
順序存儲結(jié)構(gòu)的線性表SeqList模板類的find實現(xiàn)如下：

 int find(const T& value)const
    {
        int ret = -1;
        //遍歷線性表
        for(int i = 0; i < m_length; i++)
        {
            //如果找到元素，退出循環(huán)
            if(m_array[i] = value)
            {
               ret = i;
               break;
            }
        }
        return ret;
    }

鏈式存儲結(jié)構(gòu)的線性表的find操作如下：

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;
    }

4、時間復(fù)雜度分析

在實際工程開發(fā)中，時間復(fù)雜度只是效率的一個參考指標。對于內(nèi)置基礎(chǔ)類型，順序存儲結(jié)構(gòu)實現(xiàn)的線性表與鏈式存儲結(jié)構(gòu)實現(xiàn)的線性表的效率基本相同。對于自定義類類型，順序存儲結(jié)構(gòu)實現(xiàn)的線性表比鏈式存儲結(jié)構(gòu)實現(xiàn)的線性表效率要低，原因在于順序存儲結(jié)構(gòu)實現(xiàn)的線性表要設(shè)計大量的數(shù)據(jù)元素的復(fù)制，如果自定義類型的拷貝耗時嚴重，則效率會很低。
順序存儲結(jié)構(gòu)實現(xiàn)的線性表的插入和刪除操作涉及大量對象的復(fù)制操作，鏈式存儲結(jié)構(gòu)實現(xiàn)的線性表的插入和刪除操作只涉及指針的操作，不會涉及數(shù)據(jù)對象的復(fù)制。
順序存儲結(jié)構(gòu)實現(xiàn)的線性表的數(shù)據(jù)訪問支持隨機訪問，可直接定位數(shù)據(jù)對象。鏈式存儲結(jié)構(gòu)實現(xiàn)的線性表的數(shù)據(jù)訪問必須順序訪問，必須從頭開始訪問數(shù)據(jù)對象，無法直接定位。
因此，順序存儲結(jié)構(gòu)實現(xiàn)的線性表適合數(shù)據(jù)類型的類型相對簡單，不涉及深拷貝，數(shù)據(jù)元素相對固定，訪問操作遠多于插入和刪除的場合。鏈式存儲結(jié)構(gòu)實現(xiàn)的線性表適合數(shù)據(jù)元素的類型復(fù)雜，復(fù)制操作耗時，數(shù)據(jù)元素不穩(wěn)定，需要經(jīng)常插入和刪除操作，訪問操作較少的場合。

5、單鏈表的遍歷

通常遍歷鏈表的方法時間復(fù)雜度為O（n^2）

for(int i = 0; i < ll.length(); i++)
{
    ll.get(i);
 }

通過使用游標的方法將遍歷鏈表的時間復(fù)雜度優(yōu)化為O（n）：
A、在單鏈表的內(nèi)部定義一個游標（Node* m_current）
B、遍歷開始前將游標指向位置為0的數(shù)據(jù)元素
C、獲取游標指向的數(shù)據(jù)元素
D、通過結(jié)點中的next指針移動游標
提供一組遍歷相關(guān)成員函數(shù)，以線性時間復(fù)雜度遍歷鏈表：

bool move(int pos, int step = 1)
    {
      bool ret = (0 <= pos) && (pos < m_length) && (0 < step);
      if(ret)
      {
           m_current = position(pos);
           m_step = step;
          }
      return ret;
    }
    bool end()
    {
        return m_current == NULL;
    }
    T current()
    {
        if(!end())
        {
            return m_current->value;
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "Invalid Operation...");
        }
    }
    bool next()
    {
        int i = 0;
        while((i < m_step) && (!end()))
        {
            m_current = m_current->next;
            i++;
        }
        return (i == m_step);
    }

使用游標遍歷鏈表的方法：

for(ll.move(0); !ll.end(); ll.next())
{
    cout << ll.current() << endl;
 }

6、單鏈表的翻轉(zhuǎn)

單鏈表反轉(zhuǎn)有遞歸和非遞歸兩種算法。
單鏈表翻轉(zhuǎn)的遞歸實現(xiàn)：

 Node* reverse(Node* list)
    {
        Node* ret = NULL;
        //如果單鏈表為空
        if(list == NULL || list->next == NULL)
        {
            ret = list;
        }
        else
        {
            Node* guard = list->next;
            ret = reverse(list->next);
            guard->next = list;
            list->next = NULL;
        }
        return ret;
    }

單鏈表翻轉(zhuǎn)的非遞歸實現(xiàn)：

 Node* reverse(Node *header)
    {
        Node* guard = NULL;//鏈表翻轉(zhuǎn)后的頭結(jié)點
        Node* current = reinterpret_cast(header);//當前結(jié)點
        Node* prev = NULL;//前一結(jié)點
        while(current != NULL)
        {
            Node* pNext = current->next;//下一結(jié)點
            if(NULL == pNext)//如果是單結(jié)點鏈表
            {
                guard = current;
            }
            current->next = prev;//當前結(jié)點的下一個結(jié)點指向前一結(jié)點,實現(xiàn)翻轉(zhuǎn)
            prev = current;//將前一結(jié)點移到當前結(jié)點位置
            current = pNext;//將當前結(jié)點后移
        }
        return guard;
    }

四、單鏈表的實現(xiàn)

 template 
  class LinkedList:public List
  {
  protected:
    struct Node:public Object
    {
      T value;//數(shù)據(jù)域
      Node* next;//指針域
    };
    mutable struct:public Object
    {
      char reserved[sizeof(T)];//占位空間
      Node* next;
    }m_header;
    int m_length;
    int m_step;
    Node* m_current;
  protected:
    Node* position(int index)const
    {
      //指針指向頭結(jié)點
      Node* ret = reinterpret_cast(&m_header);
      //遍歷到目標位置
      for(int i = 0; i < index; i++)
      {
          ret = ret->next;
      }
      return ret;
    }
  public:
    LinkedList()
    {
      m_header.next = NULL;
      m_length = 0;
      m_step = 1;
      m_current = NULL;
    }
    virtual ~LinkedList()
    {
      clear();
    }
    bool insert(int index, const T& value)
    {
      //判斷目標位置是否合法
      bool ret = (0 <= index) && (index <= m_length);
      if(ret)
      {
          //創(chuàng)建新的結(jié)點
          Node* node = createNode();
          if(node != NULL)
          {
              //當前結(jié)點定位到目標位置
              Node* current = position(index);
              //修改插入結(jié)點的值
              node->value = value;
              //將當前位置的下一個結(jié)點作為插入結(jié)點的下一個結(jié)點
              node->next = current->next;
              //將要插入結(jié)點作為當前結(jié)點的下一個結(jié)點
              current->next = 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)
    {
      //判斷目標位置是否合法
      bool ret = (0 <= index) && (index < m_length);
      if(ret)
      {
        //當前結(jié)點指向頭結(jié)點
        Node* current = position(index);

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

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

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

          //獲取目標結(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é)點

      }
    }

    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;
    }
    bool end()
    {
        return m_current == NULL;
    }
    T current()
    {
        if(!end())
        {
            return m_current->value;
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "Invalid Operation...");
        }
    }
    bool next()
    {
        int i = 0;
        while((i < m_step) && (!end()))
        {
            m_current = m_current->next;
            i++;
        }
        return (i == m_step);
    }
    virtual Node* createNode()
    {
        return new Node();
    }
    virtual void destroy(Node* node)
    {
        delete node;
    }
  };

五、靜態(tài)單鏈表

1、單鏈表的缺陷

長時間使用單鏈表頻繁增加和刪除數(shù)據(jù)元素時，堆空間會產(chǎn)生大量內(nèi)存碎片，導(dǎo)致系統(tǒng)運行緩慢。

2、靜態(tài)單鏈表的設(shè)計

靜態(tài)單鏈表的實現(xiàn)要點：
A、通過類模板實現(xiàn)靜態(tài)單鏈表
B、在類中定義固定大小的空間
C、重寫create、destroy函數(shù)，改變內(nèi)存的分配和釋放方式
D、在Node類中重載operator new操作符，用于在指定內(nèi)存上創(chuàng)建對象。

3、靜態(tài)單鏈表的實現(xiàn)

 template 
  class StaticLinkedList:public LinkedList
  {
  protected:
    typedef typename LinkedList::Node Node;
      struct SNode:public Node
      {
          //重載new操作符
          void* operator new(unsigned int size, void* loc)
          {
              return loc;
          }
      };
    unsigned char m_space[N*sizeof(Node)];//順序存儲空間
    bool m_used[N];//空間可用標識
 public:
    StaticLinkedList()
    {
        for(int i = 0; i < N; i++)
        {
            m_used[i] = false;
        }
    }
    Node* createNode()
    {
        SNode* ret = NULL;
        for(int i = 0; i < N; i++)
        {
            if(!m_used[i])
            {
                ret = reinterpret_cast(m_space) + i;
                ret = new(ret) SNode();
                m_used[i] = true;
                break;
            }
        }
        return ret;
    }
    void destroy(Node* node)
    {
        SNode* space = reinterpret_cast(m_space);
        SNode* pn = dynamic_cast(node);
        for(int i = 0; i < N; i++)
        {
            if(pn == space + i)
            {
               m_used[i] = false;
               pn->~SNode();
             }
        }

    }
    int capacty()
    {
        return N;
    }
  };

靜態(tài)單鏈表擁有單鏈表的所有操作，在預(yù)留的順序存儲空間中創(chuàng)建結(jié)點對象，適合于大數(shù)據(jù)元素個數(shù)固定需要頻繁增加和刪除數(shù)據(jù)元素的場合。

關(guān)于數(shù)據(jù)結(jié)構(gòu)中的單鏈表如何理解就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。

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

本文題目：數(shù)據(jù)結(jié)構(gòu)中的單鏈表如何理解-創(chuàng)新互聯(lián)
標題來源：http://ef60e0e.cn/article/ehehg.html