全國計算機等級考試四級復習綱要二

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

　　線性表是n≥0個元素的一個有限序列:（a 1 ，a 2 ，a 3 ，…，a n- 1 ，a n ，）表中元素的個數(shù)n稱為表的長度，長度n=0的表稱為空表。表元素又稱為結(jié)點，線性表的一個重要特性是可以按照諸元素在表中的位置確定它們在表中的先后次序。若n≥1，則a 1 ，為第一個元素，a n 為最后一個元素。元素a i-1 先于a i ，我們稱a i-1 為a i 的前驅(qū);a i 在a i-1 之后，a 1 為a i-1 的后繼。除第一個元素外，每個元素都有一個且僅有一個直接前驅(qū);除最后一個元素外，每個元素都有一個且僅有一個直接后繼，下面所列的是其中一些常用的運算。
　　
　　①查找運算
　　
　　查找線性表的第i（0≤i≤n-1）個表元;

　　在線性表中查找具有給定鍵值的表元;

　�、诓迦脒\算
　　
　　把新表元插在線性表的第i（0≤i≤n）個位置上;

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

　�、蹌h除運算

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

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

　　④其他運算

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

　　線性表分析;

　　線性表合并;

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

　�。�2）線性表的存儲

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

　　①線性表的順序存儲

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

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

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

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

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

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

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

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

　�、躳ush（x，s） 將元素x插入棧s的棧頂。

　�、輙op（s） 取棧頂元素。
　　
　�、辮op（s） 刪除棧頂元素。

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

　　作實際上是線性表的操作的特殊情形，所以表示線性表的方法同樣可以用來表示棧。

　�。�6）隊列
　　
　　隊列可看作是插入在一端進行，刪除在另一端進行的線性表，允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。在隊列中，只能刪除隊頭元素。隊列的最后一個元素一定是最新入隊的元素。因此隊列又稱先進先出表（First-In-First-Out）。

　　日常生活中排隊購物就是隊列應用的例子:新來的顧客排在隊尾等待，排在隊頭的顧客購物后離開隊伍。隊列的基本操作有:

　�、賑reate（Q）建立一個空隊列。

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

　　④front（Q）取隊頭元素。

　　⑤enq（X，Q）向隊列中插入一個元素X。⑥enq（Q）刪除隊頭元素。

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

更多信息請訪問：考試吧計算機等級考試欄目