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

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

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

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

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

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

2．按索引刪除操作

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

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

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

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

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

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

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

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

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

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