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