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