九九热这里直有精品,1区二区三区在线播放,玖玖爱在线观看资源,国产aⅴ综合网,午夜福利男女,日本亚洲欧美三级,日韩无码黄色导航,内射少妇13区,中文字幕高清网

線性表（Linear List）

         具有相同特性的數(shù)據(jù)元素的一個有限序列。

線性表的順序存儲結(jié)構(gòu)—順序表

         線性表的順序存儲結(jié)構(gòu)是指用一塊地址連續(xù)的存儲空間依次存儲線性表的數(shù)據(jù)元素。這種存儲方式好比改革前的銀行，需要在業(yè)務(wù)窗口前排隊(duì)取錢。由此可以看出順序表中邏輯上相鄰的元素在物理上也是相鄰的。

順序表的特點(diǎn)

    1.容量固定

         存儲順序表的元素需要一整塊內(nèi)存空間，因而順序表的容量一旦確定，便不能更改。

    2.訪問速度快

         在順序表使用索引訪問數(shù)據(jù)元素是非常簡單、快速的。如圖2.3所示，假設(shè)順序表中的第一個元素的位置是Loc，每個數(shù)據(jù)元素所占用的存儲空間為n，那么可以很快地計(jì)算出第i個元素的存儲地址為：Loc + (i – 1) * n。

數(shù)組

         線性表的順序存儲結(jié)構(gòu)在C#中的最直接表現(xiàn)形式就是數(shù)組。在C#語言中，數(shù)組是最基礎(chǔ)也是存取速度最快的一種集合類型。數(shù)組是引用類型，保存它們所需的內(nèi)存空間會在托管堆上分配，一旦數(shù)組被創(chuàng)建，其中的所有元素將被初始化為它們的默認(rèn)值。

int[] arrInt = newint[5];

arrInt[2] = 5;

arrInt[4] = 3;

         以上代碼聲明了一個值類型int的數(shù)組，并把它的長度初始化為5，最后分別給第3和第5個元素賦值。

         當(dāng)數(shù)組元素為值類型時，數(shù)組對象存放的是值類型對象本身。當(dāng)元素為引用類型時，數(shù)組對象存放的則是對象的引用（指針）。

Control[] arrCtrl = new Control[5];

arrCtrl[0] = new Button();

arrCtrl[3] = new Label();

         以上代碼聲明了一個引用類型Control的數(shù)組，并把它的長度初始化為5，最后分別給第1和第4個元素賦值。兩個值是分別Button和Label對象，雖然它們都繼承自Control類，但兩者卻是不同類，它們的大小不一樣。

C#與數(shù)據(jù)結(jié)構(gòu)--ArrayList

2.2.3 ArrayList

C#中的ArrayList動態(tài)改變數(shù)組大小的。ArrayList又被稱為動態(tài)數(shù)組，它的存儲空間可以被動態(tài)改變，同時還擁有添加、刪除元素的功能。

Insert(int index, object value)方法用于在指定索引處插入一個元素。為了保證順序表中的每個元素物理上相鄰，插入點(diǎn)后面的所有元素都將后移一位。

RemoveAt(int index)方法用于刪除指定索引的元素，刪除指定元素后，刪除點(diǎn)后的所有元素將向前移動一位。

　二叉樹的存儲結(jié)構(gòu)

二叉樹的存儲可分為兩種：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。

1.順序存儲結(jié)構(gòu)

把一個滿二叉樹自上而下、從左到右順序編號，依次存放在數(shù)組內(nèi)，可得到圖6.8(a)所示的結(jié)果。設(shè)滿二叉樹結(jié)點(diǎn)在數(shù)組中的索引號為i，那么有如下性質(zhì)。

（1） 如果i = 0，此結(jié)點(diǎn)為根結(jié)點(diǎn)，無雙親。

（2） 如果i > 0，則其雙親結(jié)點(diǎn)為(i -1) / 2 。（注意，這里的除法是整除，結(jié)果中的小數(shù)部分會被舍棄。）

（3） 結(jié)點(diǎn)i的左孩子為2i + 1，右孩子為2i + 2。

（4） 如果i > 0，當(dāng)i為奇數(shù)時，它是雙親結(jié)點(diǎn)的左孩子，它的兄弟為i + 1；當(dāng)i為偶數(shù)時，它是雙新結(jié)點(diǎn)的右孩子，它的兄弟結(jié)點(diǎn)為i – 1。

（5） 深度為k的滿二叉樹需要長度為2 k-1的數(shù)組進(jìn)行存儲。

通過以上性質(zhì)可知，使用數(shù)組存放滿二叉樹的各結(jié)點(diǎn)非常方便，可以根據(jù)一個結(jié)點(diǎn)的索引號很容易地推算出它的雙親、孩子、兄弟等結(jié)點(diǎn)的編號，從而對這些結(jié)點(diǎn)進(jìn)行訪問，這是一種存儲二叉滿二叉樹或完全二叉樹的最簡單、最省空間的做法。

為了用結(jié)點(diǎn)在數(shù)組中的位置反映出結(jié)點(diǎn)之間的邏輯關(guān)系，存儲一般二叉樹時，只需要將數(shù)組中空結(jié)點(diǎn)所對應(yīng)的位置設(shè)為空即可，其效果如圖6.8(b)所示。這會造成一定的空間浪費(fèi)，但如果空結(jié)點(diǎn)的數(shù)量不是很多，這些浪費(fèi)可以忽略。

一個深度為k的二叉樹需要2 k-1個存儲空間，當(dāng)k值很大并且二叉樹的空結(jié)點(diǎn)很多時，最壞的情況是每層只有一個結(jié)點(diǎn)，再使用順序存儲結(jié)構(gòu)來存儲顯然會造成極大地浪費(fèi)，這時就應(yīng)該使用鏈?zhǔn)酱鎯Y(jié)構(gòu)來存儲二叉樹中的數(shù)據(jù)。

2.鏈?zhǔn)酱鎯Y(jié)構(gòu)

　　二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)可分為二叉鏈表和三叉鏈表。二叉鏈表中，每個結(jié)點(diǎn)除了存儲本身的數(shù)據(jù)外，還應(yīng)該設(shè)置兩個指針域left和right，它們分別指向左孩子和右孩子，當(dāng)需要在二叉樹中經(jīng)常尋找某結(jié)點(diǎn)的雙親，每個結(jié)點(diǎn)還可以加一個指向雙親的指針域parent。

3二叉樹的深度優(yōu)先遍歷

　　1.先序遍歷

　　若二叉樹為非空，則過程為：

（1） 訪問根節(jié)點(diǎn)。

（2） 先序遍歷左子樹。

（3） 先序遍歷右子樹。

圖6.13中，先序遍歷就是把標(biāo)號為(1)的結(jié)點(diǎn)按搜索路徑訪問的先后次序連接起來，得出結(jié)果為：ABDECF。

　　2.中序遍歷

　　若二叉樹為非空，則過程為：

（1） 按中序遍歷左子樹。

（2） 訪問根結(jié)點(diǎn)。

（3） 按中序遍歷右子樹。

圖6.13中，先序遍歷就是把標(biāo)號為(2)的結(jié)點(diǎn)按搜索路徑訪問的先后次序連接起來，得出結(jié)果為：DBEACF。

　　3.后序遍歷

　　若二叉樹為非空，則過程為：

（1） 按后序遍歷左子樹。

（2） 按后序遍歷右子樹

（3） 訪問根結(jié)點(diǎn)。