【正文】 因此，為了表示存放在計(jì)算機(jī)存儲(chǔ)空間中的各數(shù)據(jù)元素之間的邏輯關(guān)系（即前后件關(guān)系），在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。（2）數(shù)據(jù)結(jié)構(gòu)的圖形表示在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對(duì)于數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點(diǎn)，并簡(jiǎn)稱為結(jié)點(diǎn)；為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對(duì)于關(guān)系R中的每一個(gè)二元組，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。（3）線性結(jié)構(gòu)與非線性結(jié)構(gòu)根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。即線性表或是一個(gè)空表，或可以表示為（a1，a2，…，ai，…，an）其中ai（i=1，2，…，n）是屬于數(shù)據(jù)對(duì)象的元素，通常也稱其為線性表中的一個(gè)結(jié)點(diǎn)。① 有且只有一個(gè)根結(jié)點(diǎn)a1，它無(wú)前件；② 有且只有一個(gè)終端結(jié)點(diǎn)an，它無(wú)后件；③ 除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。① 線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；② 線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。顯然，在線性表采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，如果插入運(yùn)算在線性表的末尾進(jìn)行，即在第n個(gè)元素之后（可以認(rèn)為是在第n+1個(gè)元素之前）插入新元素，則只要在表的末尾增加一個(gè)元素即可，不需要移動(dòng)表中的元素；但如果要在線性表的第1個(gè)元素之前插入一個(gè)新元素，則需要移動(dòng)表中所有的元素。（4）順序表的刪除運(yùn)算設(shè)長(zhǎng)度為n的線性表為……現(xiàn)要?jiǎng)h除第i個(gè)元素，刪除后得到長(zhǎng)度為n–1的線性表為……ajaj+11≤j≤i1i≤j≤n1則刪除前后的兩線性表中的元素滿足如下關(guān)系：在一般情況下，要?jiǎng)h除第i（1≤i≤n）個(gè)元素時(shí)，則要從第i+1個(gè)元素開始，直到第n個(gè)元素之間共n–i個(gè)元素依次向前移動(dòng)一個(gè)位置。在平均情況下，要在線性表中刪除一個(gè)元素，需要移動(dòng)表中一半的元素。即在這種線性表的結(jié)構(gòu)中，一端是封閉的，不允許進(jìn)行插入與刪除元素；另一端是開口的，允許插入與刪除元素。即棧是按照“先進(jìn)后出”（First In Last Out，F(xiàn)ILO）或“后進(jìn)先出”（Last In First Out，LIFO）的原則組織數(shù)據(jù)的，因此，棧也被稱為“先進(jìn)后出”表或“后進(jìn)先出”表。棧頂指針top動(dòng)態(tài)反映了棧中元素的變化情況。top=0表示棧空；top=m表示棧滿。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將棧頂指針進(jìn)一（即top加1），然后將新元素插入到棧頂指針指向的位置。 退棧運(yùn)算退棧運(yùn)算是指取出棧頂元素并賦給一個(gè)指定的變量。（2）隊(duì)列及其基本運(yùn)算① 隊(duì)列的基本概念隊(duì)列（Equeue）是指允許在一端進(jìn)行插入而在另一端進(jìn)行刪除的線性表。在隊(duì)列中，隊(duì)尾指針rear與排頭指針front共同反映了隊(duì)列中元素動(dòng)態(tài)變化的情況。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置，因此，從排頭指針front指向的后一個(gè)位置直到隊(duì)尾指針rear指向的位置之間所有的元素均為隊(duì)列中的元素。當(dāng)隊(duì)尾指針rear=m+1時(shí)，則置rear=1。隊(duì)列空的條件為 s=0；隊(duì)列滿的條件為（s=1）且（front=rear）。 入隊(duì)運(yùn)算入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新元素。這種情況稱為“下溢”。為此目的，將存儲(chǔ)空間中的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部分：一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存放下一個(gè)數(shù)據(jù)元素的存儲(chǔ)序號(hào)（即存儲(chǔ)結(jié)點(diǎn)的地址），即指向后件結(jié)點(diǎn)，稱為指針域。（2）線性鏈表及其基本運(yùn)算① 在線性鏈表中查找指定元素在非空線性鏈表中尋找包含指定元素值x的前一個(gè)結(jié)點(diǎn)p的基本方法如下。為了要在線性鏈表中插入一個(gè)新元素，首先要給該元素分配一個(gè)新結(jié)點(diǎn)，以便用于存儲(chǔ)該元素的值。為了在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)，首先要在線性鏈表中找到這個(gè)結(jié)點(diǎn)，然后將要?jiǎng)h除的結(jié)點(diǎn)放回到可利用棧。② 循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空，而是指向表頭結(jié)點(diǎn)。而線性單鏈表做不到這一點(diǎn)。6．樹與二叉樹（1）樹的基本概念樹（Tree）是一種簡(jiǎn)單的非線性結(jié)構(gòu)。在樹中，沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡(jiǎn)稱為樹的根。在樹中，所有結(jié)點(diǎn)中的最大度稱為樹的度。③ 樹的最大層次稱為樹的深度。而樹結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)的度可以是任意的。② 二叉樹的基本性質(zhì)二叉樹具有以下幾個(gè)性質(zhì)。性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[log2n]+1，其中[log2n]表示取log2n的整數(shù)部分。這就是說，在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹的第k層上有2k–1個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹有2m–1個(gè)結(jié)點(diǎn)。對(duì)于完全二叉樹來說，葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)；對(duì)于任何一個(gè)結(jié)點(diǎn)，若其右分支下的子孫結(jié)點(diǎn)的最大層次為p，則其左分支下的子孫結(jié)點(diǎn)的最大層次或?yàn)閜，或?yàn)閜+1。性質(zhì)6 設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)，如果從根結(jié)點(diǎn)開始，按層序（每一層從左到右）用自然數(shù)1，2，…，n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)于編號(hào)為k（k=1，2，…，n）的結(jié)點(diǎn)有以下結(jié)論。根據(jù)完全二叉樹的這個(gè)性質(zhì)，如果按從上到下、從左到右的順序存儲(chǔ)完全二叉樹的各結(jié)點(diǎn)，則很容易確定每一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)、左子結(jié)點(diǎn)和右子結(jié)點(diǎn)的位置。由于二叉樹的存儲(chǔ)結(jié)構(gòu)中每一個(gè)存儲(chǔ)結(jié)點(diǎn)有兩個(gè)指針域，因此，二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱為二叉鏈表。① 前序遍歷（DLR）前序遍歷是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。③ 后序遍歷（LRD）后序遍歷是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)，并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。從線性表的第一個(gè)元素開始，依次將線性表中的元素與被查找元素進(jìn)行比較，若相等則表示找到（即查找成功）；若線性表中所有的元素都與被查找元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素（即查找失?。?。在此所說的有序表是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）的。在最壞情況下，二分查找只需要比較log2n次，而順序查找需要比較n次。首先，從表頭開始往后掃描線性表，在掃描過程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中，后面的元素小于前面的元素，則將它們互換，這樣就又消去了一個(gè)逆序。但這個(gè)工作量不是必需的，一般情況下要小于這個(gè)工作量。這個(gè)過程稱為線性表的分割。在線性表中，只包含第1個(gè)元素的子表顯然可以看成是有序表。在簡(jiǎn)單插入排序中，每一次比較后最多移掉一個(gè)逆序，因此，這種排序方法的效率與冒泡排