二、線性表
　　
　　（1）線性表及其基本操作

　　線性表是n≥0個(gè)元素的一個(gè)有限序列:（a 1 ，a 2 ，a 3 ，…，a n- 1 ，a n ，）表中元素的個(gè)數(shù)n稱(chēng)為表的長(zhǎng)度，長(zhǎng)度n=0的表稱(chēng)為空表。表元素又稱(chēng)為結(jié)點(diǎn)，線性表的一個(gè)重要特性是可以按照諸元素在表中的位置確定它們?cè)诒碇械南群蟠涡颉Ｈ鬾≥1，則a 1 ，為第一個(gè)元素，a n 為最后一個(gè)元素。元素a i-1 先于a i ，我們稱(chēng)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ǔ)是最簡(jiǎn)單的存儲(chǔ)方式。程序通常用一個(gè)足夠大的數(shù)組，從數(shù)組的第一個(gè)元素開(kāi)始，將線性表的結(jié)點(diǎn)依次存儲(chǔ)在數(shù)組中。即線性表的第i個(gè)結(jié)點(diǎn)存儲(chǔ)在數(shù)組的第i（0≤i≤n-1）個(gè)元素中，用數(shù)組元素的順序存儲(chǔ)來(lái)體現(xiàn)線性表中結(jié)點(diǎn)的先后次序關(guān)系。用數(shù)組存儲(chǔ)線性表的最大優(yōu)點(diǎn)是能直接訪問(wèn)線性表中的任一結(jié)點(diǎn)。

　　用數(shù)組存儲(chǔ)線性表的缺點(diǎn)主要有兩個(gè):一是程序中的數(shù)組通常大小是固定的，可能會(huì)與線性表的結(jié)點(diǎn)可以任意增加和減少的要求相矛盾;二是執(zhí)行線性表的結(jié)點(diǎn)插、刪操作時(shí)要移動(dòng)存于數(shù)組中的其他元素，使插和刪操作不夠簡(jiǎn)便。
　　
　　②線性表的鏈接存儲(chǔ)
　　
　　線性表鏈接存儲(chǔ)是用鏈表存儲(chǔ)線性表，最簡(jiǎn)單的用單鏈表。如從鏈表的第一個(gè)表元開(kāi)始，將線性表的結(jié)點(diǎn)依次存儲(chǔ)在鏈表的各表元中。即線性表的第i個(gè)結(jié)點(diǎn)存儲(chǔ)在鏈表的第i（0≤i≤n-1）個(gè)表元中。鏈表的每個(gè)表元除要存儲(chǔ)線性結(jié)點(diǎn)的信息外，還要有一個(gè)成分用來(lái)存儲(chǔ)其后繼結(jié)點(diǎn)的指針。單鏈表就是通過(guò)鏈接指針來(lái)體現(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ī)地直接訪問(wèn)線性表的任一結(jié)點(diǎn)。

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

　　（4）線性表的新結(jié)點(diǎn)插入順序存儲(chǔ)線性表的插入:
　　
　　設(shè)線性表結(jié)點(diǎn)的類(lèi)型為整型，插入之前有n個(gè)結(jié)點(diǎn)，把值為x的新結(jié)點(diǎ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è)位置上;
　　
　　修正線性表的結(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)。

　　棧是一種特殊的線性表，這種線性表只能在固定的一端進(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） 刪除棧頂元素。

　　由于棧是一種特殊的線性表，棧的各種操

　　作實(shí)際上是線性表的操作的特殊情形，所以表示線性表的方法同樣可以用來(lái)表示棧。

　　（6）隊(duì)列
　　
　　隊(duì)列可看作是插入在一端進(jìn)行，刪除在另一端進(jì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ì)頭元素。

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

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