二、線性表
（1）線性表及其基本操作
線性表是n≥0個元素的一個有限序列:（a 1 ，a 2 ，a 3 ，…，a n- 1 ，a n ，）表中元素的個數n稱為表的長度，長度n=0的表稱為空表。表元素又稱為結點，線性表的一個重要特性是可以按照諸元素在表中的位置確定它們在表中的先后次序。若n≥1，則a 1 ，為第一個元素，a n 為最后一個元素。元素a i-1 先于a i ，我們稱a i-1 為a i 的前驅;a i 在a i-1 之后，a 1 為a i-1 的后繼。除第一個元素外，每個元素都有一個且僅有一個直接前驅;除最后一個元素外，每個元素都有一個且僅有一個直接后繼，下面所列的是其中一些常用的運算。
①查找運算
查找線性表的第i（0≤i≤n-1）個表元;
在線性表中查找具有給定鍵值的表元;
②插入運算
把新表元插在線性表的第i（0≤i≤n）個位置上;
把新表元插在具有給定鍵值的表元的前面或后面;
③刪除運算
刪除線性表的第i（0≤i≤n-1）個表元;
刪除線性表中具有給定鍵值的表元;
④其他運算
統(tǒng)計線性表元的個數;
輸出線性表各表元的值;
復制線性表;
線性表分析;
線性表合并;
線性表排序;
按某種規(guī)則整理線性表。
（2）線性表的存儲
有多種存儲方式能將線性表存儲在計算機內，其中最常用的是順序存儲和鏈接存儲。
①線性表的順序存儲
線性表的順序存儲是最簡單的存儲方式。程序通常用一個足夠大的數組，從數組的第一個元素開始，將線性表的結點依次存儲在數組中。即線性表的第i個結點存儲在數組的第i（0≤i≤n-1）個元素中，用數組元素的順序存儲來體現(xiàn)線性表中結點的先后次序關系。用數組存儲線性表的優(yōu)點是能直接訪問線性表中的任一結點。
用數組存儲線性表的缺點主要有兩個:一是程序中的數組通常大小是固定的，可能會與線性表的結點可以任意增加和減少的要求相矛盾;二是執(zhí)行線性表的結點插、刪操作時要移動存于數組中的其他元素，使插和刪操作不夠簡便。
②線性表的鏈接存儲
線性表鏈接存儲是用鏈表存儲線性表，最簡單的用單鏈表。如從鏈表的第一個表元開始，將線性表的結點依次存儲在鏈表的各表元中。即線性表的第i個結點存儲在鏈表的第i（0≤i≤n-1）個表元中。鏈表的每個表元除要存儲線性結點的信息外，還要有一個成分用來存儲其后繼結點的指針。單鏈表就是**鏈接指針來體現(xiàn)線性表中結點的先后次序關系。每個鏈表還要有一個指向鏈表的第一個表元，鏈表的最末一個表元的后繼指針值為空。用鏈表存儲線性表的優(yōu)點是線性表的每個表元的后繼指針就能完成插或刪的操作，不需移動任何表元。
其缺點也主要有兩條:一是每個表元增加了一個后繼指針成分，要花費更多的存儲空間;二是不便隨機地直接訪問線性表的任一結點。
（3）線性表上的查找
線性表上的查找運算是指在線性表中找某個鏈值的結點。根據線性表的存儲形式和線性表本身的性質差異，有多種查找算法，如:順序查找、二分法查找、分塊查找、散列查找等。
（4）線性表的新結點插入順序存儲線性表的插入:
設線性表結點的類型為整型，插入之前有n個結點，把值為x的新結點插在線性表的第i（0≤i≤n）個位置上。完成插入主要有以下幾個步驟:
檢查插入要求的有關參數的合理性;
把原來第n-1個結點至第i個結點依次往后移一個數組元素位置;
把新結點放在第i個位置上;
修正線性表的結點個數。
（5）棧
堆棧的工作原理是采用后進先出（LIFO）技術，棧頂由中央處理器中的堆棧指示器（SP）指出。在執(zhí)行PUSH操作中SP減量，而在POP操作中SP增量。
下面從數據結構的角度，進一步說明堆棧的基本概念與操作。需要說明的是，其工作原理與前面所介紹的是一致的，不同的是脫離了硬件背景，例如，棧頂指針不是中央處理器的某個寄存器的內容，而是一個抽象的數據結構。來源：www.examda.com
棧是一種特殊的線性表，這種線性表只能在固定的一端進行插入和刪除操作。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。一個新元素只能從棧頂一端進入，刪除時，只能刪除棧頂的元素，即剛剛被插入的元素。由于元素是按后進先出的次序入棧和出棧的，所以棧又稱后進先出表（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）。
日常生活中排隊購物就是隊列應用的例子:新來的顧客排在隊尾等待，排在隊頭的顧客購物后離開隊伍。隊列的基本操作有:
①create（Q）建立一個空隊列。
②empty（Q）測試隊列是否為空隊列。③full（Q）測試隊列是否為滿。④front（Q）取隊頭元素。
⑤enq（X，Q）向隊列中插入一個元素X。⑥enq（Q）刪除隊頭元素。