線性表（Linear List） 具有相同特性的數據元素的一個有限序列。 線性表的順序存儲結構—順序表 線性表的順序存儲結構是指用一塊地址連續的存儲空間依次存儲線性表的數據元素。這種存儲方式好比改革前的銀行，需要在業務窗口前排隊取錢。由此可以看出順序表中邏輯上相鄰的元素在物理上也是相鄰的。 順序表的特點 1.容量固定 存儲順序表的元素需要一整塊內存空間，因而順序表的容量一旦確定，便不能更改。 2.訪問速度快 在順序表使用索引訪問數據元素是非常簡單、快速的。如圖2.3所示，假設順序表中的第一個元素的位置是Loc，每個數據元素所占用的存儲空間為n，那麼可以很快地計算出第i個元素的存儲地址為：Loc + (i – 1) * n。 數組 線性表的順序存儲結構在C#中的最直接表現形式就是數組。在C#語言中，數組是最基礎也是存取速度最快的一種集合類型。數組是引用類型，保存它們所需的內存空間會在托管堆上分配，一旦數組被創建，其中的所有元素將被初始化為它們的默認值。 int[] arrInt = newint[5]; arrInt[2] = 5; arrInt[4] = 3; 以上代碼聲明了一個值類型int的數組，並把它的長度初始化為5，最後分別給第3和第5個元素賦值。 當數組元素為值類型時，數組對象存放的是值類型對象本身。當元素為引用類型時，數組對象存放的則是對象的引用（指針）。 Control[] arrCtrl = new Control[5]; arrCtrl[0] = new Button(); arrCtrl[3] = new Label(); 以上代碼聲明了一個引用類型Control的數組，並把它的長度初始化為5，最後分別給第1和第4個元素賦值。兩個值是分別Button和Label對象，雖然它們都繼承自Control類，但兩者卻是不同類，它們的大小不一樣。 C#與數據結構--ArrayList 2.2.3 ArrayList C#中的ArrayList動態改變數組大小的。ArrayList又被稱為動態數組，它的存儲空間可以被動態改變，同時還擁有添加、刪除元素的功能。 Insert(int index, object value)方法用於在指定索引處插入一個元素。為了保證順序表中的每個元素物理上相鄰，插入點後面的所有元素都將後移一位。 RemoveAt(int index)方法用於刪除指定索引的元素，刪除指定元素後，刪除點後的所有元素將向前移動一位。 二叉樹的存儲結構 二叉樹的存儲可分為兩種：順序存儲結構和鏈式存儲結構。 1.順序存儲結構 把一個滿二叉樹自上而下、從左到右順序編號，依次存放在數組內，可得到圖6.8(a)所示的結果。設滿二叉樹結點在數組中的索引號為i，那麼有如下性質。 （1） 如果i = 0，此結點為根結點，無雙親。 （2） 如果i > 0，則其雙親結點為(i -1) / 2 。（注意，這裡的除法是整除，結果中的小數部分會被捨棄。） （3） 結點i的左孩子為2i + 1，右孩子為2i + 2。 （4） 如果i > 0，當i為奇數時，它是雙親結點的左孩子，它的兄弟為i + 1；當i為偶數時，它是雙新結點的右孩子，它的兄弟結點為i – 1。 （5） 深度為k的滿二叉樹需要長度為2 k-1的數組進行存儲。 通過以上性質可知，使用數組存放滿二叉樹的各結點非常方便，可以根據一個結點的索引號很容易地推算出它的雙親、孩子、兄弟等結點的編號，從而對這些結點進行訪問，這是一種存儲二叉滿二叉樹或完全二叉樹的最簡單、最省空間的做法。 為了用結點在數組中的位置反映出結點之間的邏輯關系，存儲一般二叉樹時，只需要將數組中空結點所對應的位置設為空即可，其效果如圖6.8(b)所示。這會造成一定的空間浪費，但如果空結點的數量不是很多，這些浪費可以忽略。 一個深度為k的二叉樹需要2 k-1個存儲空間，當k值很大並且二叉樹的空結點很多時，最壞的情況是每層只有一個結點，再使用順序存儲結構來存儲顯然會造成極大地浪費，這時就應該使用鏈式存儲結構來存儲二叉樹中的數據。 2.鏈式存儲結構 二叉樹的鏈式存儲結構可分為二叉鏈表和三叉鏈表。二叉鏈表中，每個結點除了存儲本身的數據外，還應該設置兩個指針域left和right，它們分別指向左孩子和右孩子，當需要在二叉樹中經常尋找某結點的雙親，每個結點還可以加一個指向雙親的指針域parent。 3二叉樹的深度優先遍歷 1.先序遍歷 若二叉樹為非空，則過程為： （1） 訪問根節點。 （2） 先序遍歷左子樹。 （3） 先序遍歷右子樹。 圖6.13中，先序遍歷就是把標號為(1)的結點按搜索路徑訪問的先後次序連接起來，得出結果為：ABDECF。 2.中序遍歷 若二叉樹為非空，則過程為： （1） 按中序遍歷左子樹。 （2） 訪問根結點。 （3） 按中序遍歷右子樹。 圖6.13中，先序遍歷就是把標號為(2)的結點按搜索路徑訪問的先後次序連接起來，得出結果為：DBEACF。 3.後序遍歷 若二叉樹為非空，則過程為： （1） 按後序遍歷左子樹。 （2） 按後序遍歷右子樹 （3） 訪問根結點。
