二、線性表
　　
　�。�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è)重要特性是可以按照諸元素在表中的位置確定它們在表中的先后次序。若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è)位置上;

　　把新表元插在具有給定鍵值的表元的前面或后面;

　�、蹌h除運(yùn)算

　　刪除線性表的第i（0≤i≤n-1）個(gè)表元;

　　刪除線性表中具有給定鍵值的表元;

　　④其他運(yùn)算

　　統(tǒng)計(jì)線性表元的個(gè)數(shù);
　　
　　輸出線性表各表元的值;
　　
　　復(fù)制線性表;

　　線性表分析;

　　線性表合并;

　　線性表排序;
　　
　　按某種規(guī)則整理線性表。

　�。�2）線性表的存儲

　　有多種存儲方式能將線性表存儲在計(jì)算機(jī)內(nèi)，其中最常用的是順序存儲和鏈接存儲。

　　①線性表的順序存儲

　　線性表的順序存儲是最簡單的存儲方式。程序通常用一個(gè)足夠大的數(shù)組，從數(shù)組的第一個(gè)元素開始，將線性表的結(jié)點(diǎn)依次存儲在數(shù)組中。即線性表的第i個(gè)結(jié)點(diǎn)存儲在數(shù)組的第i（0≤i≤n-1）個(gè)元素中，用數(shù)組元素的順序存儲來體現(xiàn)線性表中結(jié)點(diǎn)的先后次序關(guān)系。用數(shù)組存儲線性表的最大優(yōu)點(diǎn)是能直接訪問線性表中的任一結(jié)點(diǎn)。

　　用數(shù)組存儲線性表的缺點(diǎn)主要有兩個(gè):一是程序中的數(shù)組通常大小是固定的，可能會與線性表的結(jié)點(diǎn)可以任意增加和減少的要求相矛盾;二是執(zhí)行線性表的結(jié)點(diǎn)插、刪操作時(shí)要移動(dòng)存于數(shù)組中的其他元素，使插和刪操作不夠簡便。
　　
　�、诰�性表的鏈接存儲
　　
　　線性表鏈接存儲是用鏈表存儲線性表，最簡單的用單鏈表。如從鏈表的第一個(gè)表元開始，將線性表的結(jié)點(diǎn)依次存儲在鏈表的各表元中。即線性表的第i個(gè)結(jié)點(diǎn)存儲在鏈表的第i（0≤i≤n-1）個(gè)表元中。鏈表的每個(gè)表元除要存儲線性結(jié)點(diǎn)的信息外，還要有一個(gè)成分用來存儲其后繼結(jié)點(diǎn)的指針。單鏈表就是通過鏈接指針來體現(xiàn)線性表中結(jié)點(diǎn)的先后次序關(guān)系。每個(gè)鏈表還要有一個(gè)指向鏈表的第一個(gè)表元，鏈表的最末一個(gè)表元的后繼指針值為空。用鏈表存儲線性表的優(yōu)點(diǎn)是線性表的每個(gè)表元的后繼指針就能完成插或刪的操作，不需移動(dòng)任何表元。

　　其缺點(diǎn)也主要有兩條:一是每個(gè)表元增加了一個(gè)后繼指針成分，要花費(fèi)更多的存儲空間;二是不便隨機(jī)地直接訪問線性表的任一結(jié)點(diǎn)。

　�。�3）線性表上的查找
　　
　　線性表上的查找運(yùn)算是指在線性表中找某個(gè)鏈值的結(jié)點(diǎn)。根據(jù)線性表的存儲形式和線性表本身的性質(zhì)差異，有多種查找算法，如:順序查找、二分法查找、分塊查找、散列查找等。

　　（4）線性表的新結(jié)點(diǎn)插入順序存儲線性表的插入:
　　
　　設(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)。

　　棧是一種特殊的線性表，這種線性表只能在固定的一端進(jìn)行插入和刪除操作。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。一個(gè)新元素只能從棧頂一端進(jìn)入，刪除時(shí)，只能刪除棧頂?shù)脑�素，即剛剛被插入的元素。由于元素是按后進(jìn)先出的次序入棧和出棧的，所以棧又稱后進(jìn)先出表（Last In First Out），簡稱LIFO表。棧的基本操作有:
　　
　�、賑reate（s） 建立一個(gè)空棧s。

　�、趀mpty（s） 測試棧是否為空棧。

　�、踗ull（s） 測試棧是否滿。

　　④push（x，s） 將元素x插入棧s的棧頂。

　�、輙op（s） 取棧頂元素。
　　
　�、辮op（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ì)列的基本操作有:

　�、賑reate（Q）建立一個(gè)空隊(duì)列。

　�、趀mpty（Q）測試隊(duì)列是否為空隊(duì)列。
　　
　�、踗ull（Q）測試隊(duì)列是否為滿。

　　④front（Q）取隊(duì)頭元素。

　�、輊nq（X，Q）向隊(duì)列中插入一個(gè)元素X。⑥enq（Q）刪除隊(duì)頭元素。

希望與更多計(jì)算機(jī)等級考試的網(wǎng)友交流，請進(jìn)入計(jì)算機(jī)等級考試論壇

更多信息請?jiān)L問：考試吧計(jì)算機(jī)等級考試欄目