數據結構整理(一) 線性結構

一、前言

　　自己挖的坑還是得自己來填，當年學數據結構（C++版本）天天打醬油，課程結業的時候還以為->是一個字元，自己還納悶這東西是怎麼鍵入的，直到做結業設計的時候看團支書的代碼才突然醒悟，特此感謝下團支書MM，我想如果老師知道了應該不會打我...，後來嘗試看過兩次數據結構，都沒堅持看完。現找了一本C#版本的數據結構，預計在月底前看完並針對五個模塊（線性結構、樹、圖、排序、查找）各出一篇博客，也算是對自己的一種督促。在此吐槽一下雖然書上的思路很清晰但是示例代碼坑好深。

　　實踐源碼：https://github.com/Nik364/DataStructure.git

　　聲明：文中信息大量摘自數據結構圖書（暫不知作者，因為沒有編者，網上搜索關鍵字【C#數據結構】即可找到），後續就不做其他說明瞭

二、相關概念

1. 線性結構作為最常用的數據結構，其特點是數據元素之間存在一對一的線性關係。
2. 線性結構擁有兩種不同的存儲結構，即順序存儲結構和鏈式存儲結構。順序存儲的線性表稱為順序表，順序表中的存儲元素是連續的，鏈式存儲的線性表稱為鏈表，鏈表中的存儲元素不一定是連續的，元素節點中存放數據元素以及相鄰元素的地址信息。
3. 線性結構中存在兩種操作受限的使用場景，即隊列和棧。棧的操作只能線上性表的一端進行，就是我們常說的先進後出（FILO），隊列的插入操作線上性表的一端進行而其他操作線上性表的另一端進行，先進先出（FIFO），由於線性結構存在兩種存儲結構，因 此隊列和棧各存在兩個實現方式。
   
   

三、部分實現

1. 順序表（順序存儲）
   　　按照我們的習慣，存放東西時，一般是找一塊空間，然後將需要存放的東西依次擺放，這就是順序存儲。電腦中的順序存儲是指在記憶體中用一塊地址連續的空間依次存放數據元素，用這種方式存儲的線性表叫順序表其特點是表中相鄰的數據元素在記憶體中存儲位置也相鄰，如下圖：
   

    1 // 倒置線性表
    2 public void Reverse()
    3 {
    4     T tmp = default(T);
    5 
    6     int len = GetLength() - 1;
    7     for (int i = 0; i <= len / 2; i++)
    8     {
    9         if (i.Equals(len - i))
   10         {
   11             break;
   12         }
   13 
   14         tmp = data[i];
   15         data[i] = data[len - i];
   16         data[len - i] = tmp;
   17     }
   18 }

2. 鏈表（鏈式存儲）
   　　假如我們現在要存放一些物品，但是沒有足夠大的空間將所有的物品一次性放下（電腦中使用鏈式存儲不是因為記憶體不夠先事先說明一下...，具體原因後續會說到），同時設定我們因為腦容量很小，為了節省空間，只能記住一件物品位置。此時我們很機智的找到瞭解決方案：存放物品時每放置一件物品就在物品上貼一個小紙條，標明下一件物品放在那裡，只記住第一件物品的位置，尋找的時候從第一件物品開始尋找，通過小紙條我們可以找到所有的物品，這就是鏈式存儲。鏈表實現的時候不再像線性表一樣只存儲數據即可，還有下一個數據元素的地址，因此先定義一個節點類(Node)，記錄物品信息和下一件物品的位置，我們把物品本身叫做數據域，存儲下一件物品地址信息的小紙條稱為引用域。鏈表結構示意圖如下：
   　　尋找物品的時候發現了一個問題，我們從一件物品找下一件物品的時候很容易，但是如果要找上一件物品就得從頭開始找，真的很麻煩。為瞭解決這個問題我們又機智了一把，模仿之前的做法，在存放物品的時候多放置一個小紙條記錄上一件物品的位置，這樣就可以很快的找到上一件物品了。我們把這種方式我們稱為雙向鏈表，前面只放置一張小紙條的方式稱為單向鏈表。
   

    1 // 倒置單鏈表
    2 public void Reverse()
    3 {
    4     Node<T> oldHead = Head;
    5     Node<T> tmp ;
    6     Head = null;    //清空鏈表，解除Head跟oldHead之間的相同引用
    7 
    8     while (oldHead != null)
    9     {
   10         tmp = Head;
   11         Head = oldHead;
   12         //解除Head跟oldHead之間的相同引用
   13         oldHead = oldHead.Next;
   14         Head.Next = tmp;
   15     }
   16 }

   　　由於數據存儲結構不同導致使用場景上的巨大差異，順序表由於元素連續具有隨機存儲的特點，所以查找數據很方便效率很高，但是插入、刪除操作為了確保數據元素連續，需要移動大量的數據導致效率很低。而鏈表由於存儲空間不要求連續，插入、刪除只需修改相鄰元素的引用域地址即可，所以效率很高，但查詢需要從頭引用開始遍歷鏈表，效率很低。因此，如果只是進行查找操作而不經常插入、刪除線性表中的數據元素，則使用順序存儲結構，反之，使用鏈式存儲結構。

3. 棧
   　　其實成功完成順序表和鏈表之後，棧已經沒太多可說的了，主要是邏輯上的不同，畢竟棧也是一種特殊的線性結構。棧是一種操作限定在表尾部進行的線性表，表尾稱為棧頂（Top），另一端固定不動，稱為棧底（Bottom）。進棧、出棧示意圖如下：
   
   
   

    1 //鏈棧入駐
    2 public void Push(T item)
    3 {
    4     Node<T> tmp = new Node<T>(item);
    5     if (Top == null)
    6     {
    7         Top = tmp;
    8     }
    9     else
   10     {
   11         tmp.Next = Top;
   12         Top = tmp;
   13     }
   14     Num++;
   15 }
   16 
   17 //順序棧入棧
   18 public void Push(T item)
   19 {
   20     if (IsFull())
   21     {
   22         throw new Exception("Stack is full");
   23     }
   24 
   25     data[++Top] = item;
   26 }

4. 隊列
   　　隊列與棧類似，僅僅是邏輯有一丟丟不同。隊列是一種插入操作限定在表尾其他操作限定在表頭的線性表。把進行插入操作的表尾稱為隊尾（Rear）,把進行其它操作的頭部稱為隊首（Front）。入隊、出隊示意圖如下：
   

    1 //鏈隊入隊
    2 public void In(T item)
    3 {
    4     Node<T> node = new Node<T>(item);
    5     if (Rear == null)
    6     {
    7         Rear = node;
    8         Front = Rear;
    9     }
   10     else
   11     {
   12         Rear.Next = node;
   13         Rear = Rear.Next;
   14     }
   15     ++num;
   16 }
   17 
   18 //迴圈隊列入隊
   19 public void In(T item)
   20 {
   21     if (IsFull())
   22     {
   23         throw new Exception("Queue is full");
   24     }
   25     data[++Rear] = item;
   26 }

　　最後說一句，臨淵羡魚不如退而結網，只有自己動手實踐才知道是不是真的理解了，實現鏈式結構的時候才發現原來自己對於對象地址的理解並沒有那麼的透徹...