（4）線(xiàn)性表的新結(jié)點(diǎn)插入順序存儲(chǔ)線(xiàn)性表的插入:
設(shè)線(xiàn)性表結(jié)點(diǎn)的類(lèi)型為整型，插入之前有n個(gè)結(jié)點(diǎn)，把值為x的新結(jié)點(diǎn)插在線(xiàn)性表的第i（0≤i≤n）個(gè)位置上。完成插入主要有以下幾個(gè)步驟:
檢查插入要求的有關(guān)參數(shù)的合理性;
把原來(lái)第n-1個(gè)結(jié)點(diǎn)至第i個(gè)結(jié)點(diǎn)依次往后移一個(gè)數(shù)組元素位置;
把新結(jié)點(diǎn)放在第i個(gè)位置上;
修正線(xiàn)性表的結(jié)點(diǎn)個(gè)數(shù)。
（5）棧
堆棧的工作原理是采用后進(jìn)先出（LIFO）技術(shù)，棧頂由中央處理器中的堆棧指示器（SP）指出。在執(zhí)行PUSH操作中SP減量，而在POP操作中SP增量。
下面從數(shù)據(jù)結(jié)構(gòu)的角度，進(jìn)一步說(shuō)明堆棧的基本概念與操作。需要說(shuō)明的是，其工作原理與前面所介紹的是一致的，不同的是脫離了硬件背景，例如，棧頂指針不是中央處理器的某個(gè)寄存器的內(nèi)容，而是一個(gè)抽象的數(shù)據(jù)結(jié)構(gòu)。來(lái)源：www.examda.com
棧是一種特殊的線(xiàn)性表，這種線(xiàn)性表只能在固定的一端進(jìn)行插入和刪除操作。允許插入和刪除的一端稱(chēng)為棧頂，另一端稱(chēng)為棧底。一個(gè)新元素只能從棧頂一端進(jìn)入，刪除時(shí)，只能刪除棧頂?shù)脑?，即剛剛被插入的元素。由于元素是按后進(jìn)先出的次序入棧和出棧的，所以棧又稱(chēng)后進(jìn)先出表（Last In First Out），簡(jiǎn)稱(chēng)LIFO表。棧的基本操作有:
①create（s） 建立一個(gè)空棧s。
②empty（s） 測(cè)試棧是否為空棧。
③full（s） 測(cè)試棧是否滿(mǎn)。
④push（x，s） 將元素x插入棧s的棧頂。
⑤top（s） 取棧頂元素。
⑥pop（s） 刪除棧頂元素。
由于棧是一種特殊的線(xiàn)性表，棧的各種操
作實(shí)際上是線(xiàn)性表的操作的特殊情形，所以表示線(xiàn)性表的方法同樣可以用來(lái)表示棧。
（6）隊(duì)列
隊(duì)列可看作是插入在一端進(jìn)行，刪除在另一端進(jìn)行的線(xiàn)性表，允許插入的一端稱(chēng)為隊(duì)尾，允許刪除的一端稱(chēng)為隊(duì)頭。在隊(duì)列中，只能刪除隊(duì)頭元素。隊(duì)列的最后一個(gè)元素一定是最新入隊(duì)的元素。因此隊(duì)列又稱(chēng)先進(jìn)先出表（First-In-First-Out）。
日常生活中排隊(duì)購(gòu)物就是隊(duì)列應(yīng)用的例子:新來(lái)的顧客排在隊(duì)尾等待，排在隊(duì)頭的顧客購(gòu)物后離開(kāi)隊(duì)伍。隊(duì)列的基本操作有:
①create（Q）建立一個(gè)空隊(duì)列。
②empty（Q）測(cè)試隊(duì)列是否為空隊(duì)列。③full（Q）測(cè)試隊(duì)列是否為滿(mǎn)。④front（Q）取隊(duì)頭元素。
⑤enq（X，Q）向隊(duì)列中插入一個(gè)元素X。⑥enq（Q）刪除隊(duì)頭元素。
三、數(shù)組
線(xiàn)性表（包括棧和隊(duì)列）都是線(xiàn)性結(jié)構(gòu)，結(jié)構(gòu)中的每個(gè)元素只是無(wú)結(jié)構(gòu)的數(shù)據(jù)元素。我們對(duì)線(xiàn)性表作進(jìn)一步的推廣，使結(jié)構(gòu)中的元素本身也可以是具有某種結(jié)構(gòu)（如向量）的數(shù)據(jù)，從而引出了數(shù)組這一種新的數(shù)據(jù)結(jié)構(gòu)。
（1）數(shù)組的定義和運(yùn)算
類(lèi)似于線(xiàn)性表，一個(gè)二維數(shù)組（或稱(chēng)矩陣）可以看成是由m個(gè)行向量所組成的向量，也可以看成是由n個(gè)列向量所組成的向量。
對(duì)于數(shù)組的運(yùn)算，主要有檢索或存取數(shù)組中某個(gè)元素。
（2）數(shù)組的順序存儲(chǔ)結(jié)構(gòu)
由于對(duì)數(shù)組一般不作插入或刪除運(yùn)算，因此，一旦數(shù)組被建立，則結(jié)構(gòu)中的元素個(gè)數(shù)和元素之間的關(guān)系就不再發(fā)生變動(dòng)。對(duì)這種情況采用順序存儲(chǔ)結(jié)構(gòu)表示數(shù)組是比較恰當(dāng)?shù)摹?lái)源：www.examda.com
由于計(jì)算機(jī)存儲(chǔ)單元是一維的結(jié)構(gòu)，而數(shù)組是多維的結(jié)構(gòu)，因此就必須把多維結(jié)構(gòu)映射為一維的結(jié)構(gòu)，即把多維結(jié)構(gòu)按一定次序排列成一維的。
四、樹(shù)型結(jié)構(gòu)
線(xiàn)性表、棧和隊(duì)列等數(shù)據(jù)結(jié)構(gòu)所表達(dá)和處理的數(shù)據(jù)以線(xiàn)性結(jié)構(gòu)為組織形式。然而，在計(jì)算機(jī)科學(xué)和計(jì)算機(jī)應(yīng)用的各個(gè)領(lǐng)域中，存在著大量需要用更復(fù)雜的邏輯結(jié)構(gòu)加以表示的問(wèn)題。因此必須研究更復(fù)雜的邏輯結(jié)構(gòu)及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。樹(shù)形結(jié)構(gòu)就是這些更復(fù)雜的結(jié)構(gòu)中最重要的一類(lèi)。
1.樹(shù)的基本概念
樹(shù)是一類(lèi)重要的樹(shù)形結(jié)構(gòu)，其定義如下:樹(shù)是n（n>0）個(gè)結(jié)點(diǎn)的有窮集合，滿(mǎn)足:
（1）有且僅有一個(gè)稱(chēng)為根的結(jié)點(diǎn);
（2）其余結(jié)點(diǎn)分為m（m≥0）個(gè)互不相交的非空集合，T 1 ，T 2 ，…，T m ，這些集合中的每一個(gè)都是一棵樹(shù)，稱(chēng)為根的子樹(shù)。
在樹(shù)上，根結(jié)點(diǎn)沒(méi)有直接前趨。對(duì)樹(shù)上任一結(jié)點(diǎn)X來(lái)說(shuō)，X是它的任一子樹(shù)的根結(jié)點(diǎn)惟一的直接前趨。為了討論方便，我們引入樹(shù)的若干習(xí)慣術(shù)語(yǔ)。樹(shù)上任一結(jié)點(diǎn)所擁有的子樹(shù)的數(shù)目稱(chēng)為該結(jié)點(diǎn)的度。度為0的結(jié)點(diǎn)稱(chēng)為葉子或終端結(jié)點(diǎn)。度大于0的結(jié)點(diǎn)稱(chēng)為非終端結(jié)點(diǎn)或分支點(diǎn)。一棵樹(shù)中所有結(jié)點(diǎn)的度的值稱(chēng)為該樹(shù)的度。若樹(shù)中結(jié)點(diǎn)A是結(jié)點(diǎn)B的直接前趨，則稱(chēng)A為B的雙親或父結(jié)點(diǎn)，稱(chēng)B為A的孩子（即“子女”）或子結(jié)點(diǎn)。易知任何結(jié)點(diǎn)A的孩子B也就是A的一棵子樹(shù)的根結(jié)點(diǎn)，父結(jié)點(diǎn)相同的結(jié)點(diǎn)互稱(chēng)為兄弟。一棵樹(shù)上的任何結(jié)點(diǎn)（不包括根本身）稱(chēng)為根的子孫。反之若B是A的子孫，則稱(chēng)A是B的祖先，結(jié)點(diǎn)的層數(shù)（或深度）從根開(kāi)始算起:根的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)為其雙親的層數(shù)加1。一棵樹(shù)中所有結(jié)點(diǎn)層數(shù)的值稱(chēng)為該樹(shù)的高度或深度。
樹(shù)（及一切樹(shù)形結(jié)構(gòu)）是一種“分支層次”結(jié)構(gòu)。所謂“分支”是指樹(shù)中任一結(jié)點(diǎn)的子孫可以按它們所在的子樹(shù)的不同而劃分成不同的“分支”;所謂“層次”是指樹(shù)上所有結(jié)點(diǎn)可以按它們的層數(shù)劃分不同的“層次”。在實(shí)際應(yīng)用中，樹(shù)中的一個(gè)結(jié)點(diǎn)可用來(lái)存儲(chǔ)實(shí)際問(wèn)題中的一個(gè)數(shù)據(jù)元素，而結(jié)點(diǎn)間的邏輯關(guān)系（即父結(jié)點(diǎn)與子結(jié)點(diǎn)之間的鄰接關(guān)系）往往用來(lái)表示數(shù)據(jù)元素之間的某種重要的、必須加以表達(dá)的關(guān)系。
用圖示法表示任何樹(shù)形結(jié)構(gòu)時(shí)，箭頭的方向總是從上到下，即從父結(jié)點(diǎn)指向子結(jié)點(diǎn)，因此，可以簡(jiǎn)單地用連線(xiàn)代替箭頭。
2.樹(shù)的基本運(yùn)算包括:
①求根ROOT（T），引用型運(yùn)算，其結(jié)果是結(jié)點(diǎn)X在樹(shù)T的根結(jié)點(diǎn)。
②求雙親PARENT（T，X），引用型運(yùn)算，其結(jié)果是結(jié)點(diǎn)X在樹(shù)T上的雙親結(jié)點(diǎn);若X是樹(shù)T的根或X不在T上，則結(jié)果為一特殊標(biāo)志。
③求孩子CHILD（T，X，i），引用型運(yùn)算，其結(jié)果是樹(shù)T上的結(jié)點(diǎn)X的第i個(gè)孩子;若X不在T上或X沒(méi)有第i個(gè)孩子，則結(jié)果為一特殊標(biāo)志。
④建樹(shù)CREATE（X，T 1 ，…，T k ）k≥1，加工型運(yùn)算，其作用是建立一棵以X為根，以T 1 ，…，T k 為第1，…k棵子樹(shù)的樹(shù)。
⑤剪枝DELETE（T，X，i），加工型運(yùn)算，其作用是刪除樹(shù)T上結(jié)點(diǎn)X的第i棵子樹(shù);若T無(wú)第i棵子樹(shù)，則為空操作。
3.二叉樹(shù)
（1）二叉樹(shù)的基本概念
二叉樹(shù)是結(jié)點(diǎn)的有窮集合，它或者是空集，或者同時(shí)滿(mǎn)足下述兩個(gè)條件:（1）有且僅有一個(gè)稱(chēng)為根的結(jié)點(diǎn):
（2）其余結(jié)點(diǎn)分為兩個(gè)互不相交的集合T 1 、T 2 ，T 1 與T 2 都是二叉樹(shù)，并且T 1 與T 2 有順序關(guān)系（T 1 在T 2 之前），它們分別稱(chēng)為根的左子樹(shù)和右子樹(shù)。
二叉樹(shù)是一類(lèi)與樹(shù)不同的樹(shù)形結(jié)構(gòu)。它們的區(qū)別是:第一，二叉樹(shù)可以是空集，這種二叉樹(shù)稱(chēng)為空二叉樹(shù)。第二，二叉樹(shù)的任一結(jié)點(diǎn)都有兩棵子樹(shù)（當(dāng)然，它們中的任何一個(gè)可以是空子樹(shù)），并且這兩棵子樹(shù)之間有次序關(guān)系，也就是說(shuō)，它們的位置不能交換。相應(yīng)地，二叉樹(shù)上任一結(jié)點(diǎn)左、右子樹(shù)的根分別稱(chēng)為該結(jié)點(diǎn)的左孩子和右孩子。另外，二叉樹(shù)上任一結(jié)點(diǎn)的度定義為該結(jié)點(diǎn)的孩子數(shù)（即非空子樹(shù)數(shù)）。除這個(gè)幾個(gè)術(shù)語(yǔ)之外，樹(shù)的其它術(shù)語(yǔ)也適用于二叉樹(shù)。
特別值得注意的是，由于二叉樹(shù)上任一結(jié)點(diǎn)的子樹(shù)有左、右之分，因此即使一結(jié)點(diǎn)只有一棵非空子樹(shù)，仍須區(qū)別它是該結(jié)點(diǎn)的左子樹(shù)還是右子樹(shù)，這是與樹(shù)不同的。
（2）二叉樹(shù)的性質(zhì)
在某些情況下，了解二叉樹(shù)的下列性質(zhì)是有幫助的。
4.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)
二叉樹(shù)通常有兩類(lèi)存儲(chǔ)結(jié)構(gòu)，順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
（1）二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
二叉樹(shù)有不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其中最常用的是二叉樹(shù)鏈表與三叉鏈表。