第2章線性表2.1線性表的定義

線性表（linearlist）是數據結構的一種，一個線性表是n個具有相同特性的數據元素的有限序列，線性表中數據元素之間的關系是一對一的關系。數據元素是一個抽象的符號，其具體含義在不同的情況下一般不同。

在稍復雜的線性表中，一個數據元素可由多個數據項（item）組成，此種情況下常把數據元素稱為記錄（record），含有大量記錄的線性表又稱文件（file）。

線性表中的個數n定義為線性表的長度，n=0時稱為空表。在非空表中每個數據元素都有一個確定的位置，如用ai表示數據元素，則i稱為數據元素ai在線性表中的位序。

線性表的相鄰元素之間存在著序偶關系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一個順序表，則表中ai-1領先于ai，ai領先于ai+1，稱ai-1是ai的直接前驅元素，ai+1是ai的直接后繼元素。當i=1,2，…，n-1時，ai有且僅有一個直接后繼，當i=2，3，…，n時，ai有且僅有一個直接前驅。我們可以根據定義得出線性表有以下的特點：表中元素的個數有限。表中元素具有邏輯上的順序性，表中元素有其先后次序。表中元素都是數據元素，每個元素都是單個元素。表中元素的數據類型都相同，這意味著每個元素占有相同大小的存儲空間。2.2順序表的定義和基本操作的實現2.2.1順序表的定義采用順序存儲結構的線性表通常稱為順序表。順序表是在計算機內存中以數組的形式保存的線性表，線性表的順序存儲是指用一組地址連續的存儲單元依次存儲線性表中的各個元素、使得線性表中在邏輯結構上相鄰的數據元素存儲在相鄰的物理存儲單元中，即通過數據元素物理存儲的相鄰關系來反映數據元素之間邏輯上的相鄰關系，故順序表表中元素的邏輯順序和其物理順序相同。順序表是將表中的結點依次存放在計算機內存中一組地址連續的存儲單元中。第1個元素存儲在線性表的起始位置，第i個元素的存儲位置后面緊接著存儲的是第i+1個元素。假設順序表L存儲的起始位置為LOC(A)，SIZE為每個數據元素所占用存儲空間的大小，則順序表L所對應的順序存儲如圖所示。順序表最主要的特點是隨機訪問，即通過元素序號可在時間O(1)內找到指定的元素。順序表的存儲密度高，每個結點只存儲數據元素。順序表邏輯上相鄰的元素物理上也相鄰，所以插入和刪除操作需要移動大量元素，故順序表的插入或刪除元素時效率會比較低。2.2.2順序表上基本操作的實現順序表有插入、刪除、查找等基本操作。1．按索引位置插入操作要在順序表L的第i（1≤i≤L.length+1）個位置插入新元素e，需要輸入的參數分別為待插入的索引位置（0≤pos≤L.length，索引是從0開始）和待插入的元素。若pos的輸入不合法，則拋出異常，表示插入失敗；否則將順序表的第pos個元素及其后的所有元素后移一個位置，騰出一個空位置插入新元素e，如圖所示。此時順序表的長度會增加1，該插入操作成功。

2．按索引刪除操作

要在順序表L的第i（1≤i

≤L.length）個位置刪除一個元素e，需要輸入的參數為待刪除的元素索引位置（0≤pos＜L.length）。若pos的輸入不合法，則拋出異常，表示插入失敗；否則將順序表中的該元素其后的所有元素前移一個位置，刪除原先的元素，如圖所示。此時順序表的長度減1，該刪除操作成功。

2.3鏈表的定義和基本操作的實現2.3.1鏈表的定義鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。相比于線性表順序結構，操作復雜。使用鏈表結構可以克服數組鏈表需要預先知道數據大小的缺點，鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。但是鏈表失去了數組隨機讀取的優點，同時鏈表由于增加了結點的指針域，空間開銷比較大。鏈表允許插入和移除表上任意位置上的結點，但是不允許隨機存取。鏈表查找某個特定結點時，必須要從頭開始找起，十分麻煩。鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環鏈表。單鏈表結構如圖所示，其中data為數據域，存放數據元素；next為指針域，存放其后繼結點的地址。

通常用頭指針來標識一個單鏈表，比如有一個單鏈表L，頭指針為NULL時即表示L是一個空表。除此之外，為了便于對鏈表的操作，會在單鏈表第一個結點之前附加一個結點，稱為頭結點。頭結點的數據域可以不設任何信息，也可以記錄表長信息等信息。頭結點的指針域指向線性表的第一個元素結點，如圖所示。引入頭結點，有以下兩個優點：

1）第一個數據結點會被存放在頭結點的指針域中，所以在處理鏈表第一個結點時，其操作和在表中其他位置的操作一致，無需特殊處理。比如在第一個位置插入新結點，沒有頭結點的鏈表需要先將原鏈表第一個結點作為新結點的指向結點，并且將新結點作為新的表頭指針；而有頭結點的鏈表只需將該新結點插入到頭結點之后即可，不需要更新表頭指針，與基本的插入操作無異。

2）無論鏈表是否為空，其頭指針都是指向頭結點的非空指針，這樣子空表和非空表的處理就得到了統一。2.3.2單鏈表上基本操作的實現1．使用頭插法建立單鏈表該方法從一個空表開始，生產新結點，并將讀取到的數據存放到新結點的數據域中，然后將新結點插入到當前鏈表的表頭，即空白頭結點之后，如圖所示。當采用頭插法來建立單鏈表時，單鏈表中元素的順序和讀入數據的順序是相反的。在鏈表中，每個結點插入的時間為O(1)，設單鏈表的長度為n，則頭插法的總時間復雜度為O(n)。

可以試著思考一下，如果使用頭插法建立沒有頭結點的單鏈表，代碼會有怎樣的變化？與帶頭結點的單鏈表相比，哪一個更易于使用，更易于理解？2．使用尾插法建立單鏈表使用頭插法建立的單鏈表中結點次序和輸入數據的順序不一致，若希望兩者次序一致，可采用尾插法。尾插法是將新結點插入到當前鏈表的表尾，為此必須增加一個尾指針rear，使其始終指向當前鏈表的尾結點。尾插法建立單鏈表的算法如下：與頭插法相比，增加了一個指向表尾結點的指針，故尾插法的時間復雜度與頭插法相同。3．按值查找表結點從單鏈表的第一個結點出發，順著指針next逐個往下比較各結點數據域的值，若某結點數據域的值等于給定值e，則返回該結點的位序，否則返回-1。

按值查找表結點的算法如下：

在查找過程中，最壞需要遍歷整個鏈表，故按值查找操作的時間復雜度為O(n)。4．按位序查找表結點從單鏈表的第一個結點出發，順著指針next逐個往下查找到第i個（0≤i＜n，n為鏈表長度）結點，若輸入i合法，則返回該結點的數據域，否則返回None。按位序查找表結點的算法如下：5．插入結點操作插入結點操作將值為x的新結點插入到單鏈表的第i個位置上。首先檢查插入位置的合法性，然后找到待插入位置的前驅結點，即第i–1個結點，再在其后面插入新結點，如圖所示。假設結點p為待插入的新結點，實現插入結點操作的代碼片段如下：在該算法中，需要注意的是步驟1必須要在步驟2之前，如果先執行步驟2，將前驅結點的指針指向新結點s，那么原來結點p后面的結點都找不到了，無法再獲取到后面的那些結點，故要注意鏈表的執行步驟順序。該算法的主要時間開銷在于去尋找第i-1個元素，故插入結點操作的時間復雜度為O(n)。但如果在給定的結點后面插入一個結點，那么此時的時間復雜度僅為O(1)。6．刪除結點操作刪除結點操作是將單鏈表的第i個結點刪除。先檢查刪除位置的合法性，后查找表中第i–1個結點，即被刪結點的前驅結點，再將其刪除，如圖所示。與插入結點操作類似，刪除結點操作主要耗費在查找上，故時間復雜度為O(n)。7．求表長操作求鏈表的長度就是統計單鏈表中結點的數量，需要從第一個結點開始遍歷，直到遍歷到最后一個結點。該過程需要設置一個計數器，每訪問一個結點，計數器就加1。求表長操作的算法如下：上述方法中，該單鏈表是帶頭結點的，如果是不帶頭結點的單鏈表，在求表長的操作中會有所不同。由于求表長操作需要遍歷整個單鏈表，故該算法的時間復雜度為O(n)。2.3.3雙鏈表單鏈表只有一個指向其后繼的指針，使得單鏈表只能從頭到尾的順序來遍歷，在某些操作中會有一定的局限性。為克服單鏈表的局限性，故引入雙鏈表結構。雙鏈表也叫雙向鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅，如圖所示。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。雙鏈表由于增加了一個指向其前驅的prior指針，在插入和刪除操作的實現上，與單鏈表有較大的不同。1．雙鏈表的插入操作假設在雙鏈表中p所指的結點之后插入結點s，其插入過程如圖所示。上述代碼的語句順序不是唯一但不是任意的，不需要死記硬背。讀者只要加深理解，便能寫出正確的語句順序。如果把題目改成在結點p之前插入結點s，請讀者思考具體的操作步驟。雙鏈表插入操作具體代碼如下：2．雙鏈表的刪除操作假設刪除在雙鏈表中結點p的后繼結點q，雙鏈表的刪除操作如圖所示。刪除操作的代碼片段如下：刪除操作的具體代碼如下：2.3.4循環鏈表循環鏈表是另一種形式的鏈式存儲結構。顧名思義，它的特點是表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環。從循環鏈表的任意一個結點出發都可以找到鏈表中的其它結點，使得表處理更加方便靈活。循環鏈表可分為循環單鏈表和循環雙鏈表。1．循環單鏈表循環單鏈表和單鏈表的區別在于表中最后一個結點的指針不是NULL，而是指向頭結點，從而使整個鏈表形成一個環，如圖所示。

對于循環單鏈表，插入、刪除操作與單鏈表基本一致。不同的是，由于循環單鏈表是一個環，因此在任何一個位置上的插入和刪除操作都是等價的，無須判斷結點是否為表尾。在循環單鏈表L中，若循環單鏈表L為空，則L.next==L；若結點p為尾結點，則p.next=L。2．循環雙鏈表與循環單鏈表類似，在循環雙鏈表中，頭結點的prior指針還要指向表尾結點。在循環雙鏈表L中，若循環雙鏈表L為空，則L.prior==L，L.next==L；若結點p為尾結點，則p.next==L。小結（1）線性表是n個具有相同特性的數據元素的有限序列，線性表中數據元素之間的關系