數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)課件章節(jié)2

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

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

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

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

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

2．按索引刪除操作

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

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

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

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

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

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

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

按值查找表結(jié)點的算法如下：

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

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