數(shù)據(jù)結(jié)構(gòu)與算法 課件 第2章 線性表

2.1線性表的邏輯結(jié)構(gòu)

2.2線性表的順序存儲(chǔ)結(jié)構(gòu)

2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

2.4順序表與鏈表的比較2.1線性表的邏輯結(jié)構(gòu)2.1.1線性表的定義線性表(LinearList)是由n(n≥0)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))組成的有限序列，其中元素的個(gè)數(shù)n為線性表的長度。當(dāng)n?=?0時(shí)稱為空表，通常將非空線性表(n?>?0)記為線性表中各元素具有相同的特性，i是數(shù)據(jù)元素ai在線性表中的位序，即位置序號(hào)。從線性表的定義可以看出它的邏輯特征：對(duì)于一個(gè)非空線性表，有且僅有一個(gè)開始結(jié)點(diǎn)a1，有且僅有一個(gè)終端結(jié)點(diǎn)an；除第一個(gè)結(jié)點(diǎn)外，其余結(jié)點(diǎn)ai(2≤i≤n)均有且僅有一個(gè)直接前驅(qū)ai-1；除最后一個(gè)結(jié)點(diǎn)外，其余結(jié)點(diǎn)ai(1≤i≤n-1)均有且僅有一個(gè)直接后繼ai+1。2.1.2線性表的基本運(yùn)算每一種數(shù)據(jù)的邏輯結(jié)構(gòu)都對(duì)應(yīng)一組基本運(yùn)算。這里只是給出抽象的運(yùn)算，而運(yùn)算的具體實(shí)現(xiàn)只有在確定了數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)之后才能考慮。對(duì)線性表實(shí)施的基本運(yùn)算主要有以下幾種：1)?InitList(&L)線性表初始化初始條件：線性表L不存在。運(yùn)算結(jié)果：構(gòu)造一個(gè)空的線性表。2)?SetNull(L)置空表初始條件：線性表L已存在。運(yùn)算結(jié)果：將表L置為空表。3)?Length(L)求表長度初始條件：線性表L已存在。運(yùn)算結(jié)果：返回表L中的數(shù)據(jù)元素個(gè)數(shù)。4)?Get(L,i)取元素值初始條件：線性表L已存在。運(yùn)算結(jié)果：返回表L中第i個(gè)數(shù)據(jù)元素ai的值或元素的位置信息。5)?Locate(L,x)定位，按值查找初始條件：線性表L已存在。運(yùn)算結(jié)果：若表L中存在一個(gè)或多個(gè)值為x的元素，返回第一個(gè)查找到的數(shù)據(jù)元素的位序；否則返回一個(gè)特殊值。6)?Insert(L,x,i)插入初始條件：線性表L已存在。運(yùn)算結(jié)果：在表L中第i個(gè)位置上插入值為x的元素。若插入成功，表長加1。7)?Delete(L,i)刪除初始條件：線性表L已存在。運(yùn)算結(jié)果：刪除表L中第i個(gè)數(shù)據(jù)元素。若刪除成功，表長減1。需要說明的是每種基本運(yùn)算用一個(gè)函數(shù)來表示，函數(shù)的參數(shù)L是指向線性表結(jié)構(gòu)體的指針。其中線性表初始化運(yùn)算使線性表從不存在到存在，顯然指針L的指向發(fā)生了變化；置空表、插入和刪除運(yùn)算使線性表的內(nèi)容發(fā)生了變化，但指針的指向并不會(huì)發(fā)生變化；求表長度、取元素值和定位運(yùn)算，指針L和表的內(nèi)容都沒有發(fā)生變化。上述運(yùn)算并不是線性表的全部運(yùn)算。因?yàn)閷?duì)于不同應(yīng)用問題中所使用的線性表，所需執(zhí)行的運(yùn)算可能不同，所以我們不可能也沒有必要事先定義一組適合各種需要的運(yùn)算。因此，通常的做法是只給出一組最基本的運(yùn)算，對(duì)于實(shí)際問題中涉及的其他更為復(fù)雜的運(yùn)算，可以用基本運(yùn)算的組合(調(diào)用基本運(yùn)算)來實(shí)現(xiàn)。例2.1將線性表A按元素值奇、偶數(shù)拆分成兩個(gè)表，A表存放奇數(shù)，B表存放偶數(shù)。算法如下：2.2線性表的順序存儲(chǔ)結(jié)構(gòu)2.2.1線性表的順序存儲(chǔ)——順序表將一個(gè)線性表存儲(chǔ)到計(jì)算機(jī)中，可以采用許多不同的方法，其中既簡單又自然的是順序存儲(chǔ)方法，即把線性表的元素按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。用這種方法存儲(chǔ)的線性表簡稱為順序表(SequentialList)。由于線性表中所有元素類型都是相同的，因此每個(gè)元素所占用存儲(chǔ)空間的大小亦是相同的。假設(shè)順序表中每個(gè)元素占用c個(gè)存儲(chǔ)單元，那么第一個(gè)單元的存儲(chǔ)地址是該元素的存儲(chǔ)地址，順序表中開始元素a1的存儲(chǔ)地址是Loc(a1)，那么元素ai的存儲(chǔ)地址Loc(ai)可通過式(2-2)計(jì)算。其中Loc(a1)是順序表的第一個(gè)元素a1的存儲(chǔ)地址，通常稱作順序表的起始地址或基地址。在順序表中，每個(gè)結(jié)點(diǎn)ai的存儲(chǔ)地址是該結(jié)點(diǎn)在表中位置i的線性函數(shù)。只要知道順序表的起始地址，順序表中任一數(shù)據(jù)元素都可隨機(jī)存取。因此順序表是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，可以對(duì)順序表順序存取(SequentialAccess)或隨機(jī)存取(RandomAccess)。由于程序設(shè)計(jì)語言中的數(shù)組也采用順序存儲(chǔ)結(jié)構(gòu)，故可用一維數(shù)組存放線性表的元素。又因?yàn)閿?shù)組的長度往往大于線性表的實(shí)際長度，所以順序表還應(yīng)該用一個(gè)變量來表示表的當(dāng)前長度，我們用結(jié)構(gòu)類型來定義順序表的類型。在上述定義中，存放線性表結(jié)點(diǎn)的數(shù)組長度maxsize應(yīng)當(dāng)選擇適當(dāng)，使得它既能夠滿足表結(jié)點(diǎn)數(shù)目動(dòng)態(tài)增加的需要，又不至于預(yù)先定義得過大而浪費(fèi)存儲(chǔ)空間。圖2.1是線性表順序存儲(chǔ)示意圖，我們可以看出順序表的特點(diǎn)是邏輯上相鄰的結(jié)點(diǎn)其物理位置上亦相鄰。由于線性表結(jié)點(diǎn)的位序從1開始，而C語言中數(shù)組的下標(biāo)從0開始，因此關(guān)于線性表中數(shù)據(jù)元素的位序(邏輯位置)和存放它的數(shù)組下標(biāo)(物理位置)之間的關(guān)系通常有兩種處理方式：第一種方式是從下標(biāo)為0的數(shù)組元素開始存放，則結(jié)點(diǎn)的位序等于數(shù)組元素的下標(biāo)加一；第二種方式是從下標(biāo)為1的數(shù)組元素開始使用，這樣結(jié)點(diǎn)的位序和數(shù)組的下標(biāo)是相等的，使用起來會(huì)更簡單自然一些，下標(biāo)為0的元素不用或用作其他用途。若L是指向順序表的指針，則a1～an分別存儲(chǔ)在L->data[0]～L->data[L->last-1]中，L->last表示線性表當(dāng)前的長度。2.2.2線性表的基本運(yùn)算在順序表上的實(shí)現(xiàn)在順序表中，線性表的有些基本運(yùn)算很容易實(shí)現(xiàn)。例如，設(shè)L是指向某一順序表的指針，則置空表的操作是將表的長度置0，即L->last=0；求表的長度和取表中第i個(gè)元素值的操作只需分別返回L->last和L->data[i-1]即可。下面重點(diǎn)討論表初始化、插入和刪除運(yùn)算。1．順序表的初始化在函數(shù)中建立一個(gè)空順序表L，指針L從沒有指向順序表變?yōu)橹赶蛞粋€(gè)空表，顯然指針L的指向發(fā)生了變化。如何將這一變化的結(jié)果帶回到主調(diào)函數(shù)，我們給出以下三種方式，并進(jìn)行比較。算法2.1通過函數(shù)返回值將結(jié)果帶回到主調(diào)函數(shù)。在函數(shù)中定義的指針指向順序表，指針作為函數(shù)的返回值。算法2.2采用指向指針的指針作為函數(shù)參數(shù)，通過函數(shù)的參數(shù)將結(jié)果帶回到主調(diào)函數(shù)。第一級(jí)指針L指向第二級(jí)指針?*L，L的指向沒有改變，而?*L的指向發(fā)生了變化。函數(shù)運(yùn)行結(jié)束，將?*L的指向帶回到主調(diào)函數(shù)。算法2.3采用指針的引用作為函數(shù)參數(shù)，通過函數(shù)的參數(shù)將結(jié)果帶回到主調(diào)函數(shù)。參數(shù)的類型使用了C++?語言中的指針類型的引用，可以將指針?biāo)赶虻慕Y(jié)構(gòu)體動(dòng)態(tài)存儲(chǔ)帶回到主調(diào)函數(shù)。2．順序表的插入在線性表的第i(1≤i≤n+1)個(gè)位置上插入一個(gè)新結(jié)點(diǎn)x，并且使表的長度加1，即使變?yōu)殚L度是n?+?1的線性表由于順序表存在“上溢”的可能，因此在插入之前需要判斷表的數(shù)組空間是否已滿。若已經(jīng)滿，則返回值為0，表示插入不成功；否則返回值為1，表示插入成功。在順序表中，由于結(jié)點(diǎn)的物理順序必須與結(jié)點(diǎn)的邏輯順序保持一致，因此我們必須按照an到ai的順序依次將an～ai后移一個(gè)位置，為插入的x讓出存儲(chǔ)位置，然后在該位置上插入新結(jié)點(diǎn)x。僅當(dāng)插入位置i?=?n?+?1時(shí)，才無須移動(dòng)結(jié)點(diǎn)，直接將新結(jié)點(diǎn)x添加到表的末尾。插入過程如圖2.2所示，具體算法描述如下所示：算法2.4在順序表的第i個(gè)位置上插入一個(gè)新結(jié)點(diǎn)x?，F(xiàn)在分析順序表插入算法的時(shí)間復(fù)雜度。顯然算法2.4的時(shí)間主要花費(fèi)在結(jié)點(diǎn)的移動(dòng)上，移動(dòng)結(jié)點(diǎn)的個(gè)數(shù)不僅依賴于表的長度n，而且與插入的位置i有關(guān)。for語句的循環(huán)體執(zhí)行了n-i+1次。當(dāng)i?=?n+1時(shí)，由于循環(huán)變量的終值大于初值，結(jié)點(diǎn)后移語句不執(zhí)行；當(dāng)i?=?1時(shí)，結(jié)點(diǎn)后移語句執(zhí)行n次，移動(dòng)表中所有結(jié)點(diǎn)。也就是說，該算法在最好情況下時(shí)間復(fù)雜度是O(1)，最壞情況時(shí)間復(fù)雜度是O(n)。由于插入可能在表中任意位置上進(jìn)行，因此需分析算法的平均性能。在長度為n的順序表中插入一個(gè)結(jié)點(diǎn)，移動(dòng)結(jié)點(diǎn)次數(shù)的期望值(平均移動(dòng)次數(shù))為假設(shè)pi是在第i位置上插入一個(gè)結(jié)點(diǎn)的概率，并且在表中任何合法位置(1≤i≤n+1)插入結(jié)點(diǎn)的概率相等，則因此，在等概率插入的情況下，有也就是說，在順序表上做插入運(yùn)算，平均要移動(dòng)表中的一半結(jié)點(diǎn)。就數(shù)量級(jí)而言，算法的時(shí)間復(fù)雜度仍然是O(n)。3．順序表的刪除線性表的刪除運(yùn)算是指將表的第i(1≤i≤n)個(gè)結(jié)點(diǎn)刪去，并且使表的長度減1，即使變成長度為n-1的線性表順序表還存在“下溢”的可能。如果是空表，返回值為0，表示刪除不成功；否則返回值為1，表示刪除成功。和插入運(yùn)算類似，在順序表中實(shí)現(xiàn)刪除運(yùn)算也必須移動(dòng)結(jié)點(diǎn)，才能反映出結(jié)點(diǎn)間的邏輯關(guān)系的變化。若i?=?n，則無須移動(dòng)；若1≤i≤n-1，則必須將表中位置i+1,i+2,…,n上的結(jié)點(diǎn)依次前移到位置i,i?+?1,…,n-1上。這兩種情況下的時(shí)間復(fù)雜度分別是O(1)和O(n)。順序表中結(jié)點(diǎn)的刪除過程見圖2.3。算法2.5刪除順序表的第i個(gè)結(jié)點(diǎn)。算法2.5的平均性能分析與插入算法類似。在長度為n的順序表中刪除一個(gè)結(jié)點(diǎn)，移動(dòng)結(jié)點(diǎn)次數(shù)的期望值(平均移動(dòng)次數(shù))為式中，pi表示刪除表中第i個(gè)結(jié)點(diǎn)的概率。在等概率的假設(shè)下，有由此可得即在順序表上做刪除運(yùn)算，平均要移動(dòng)表中約一半的結(jié)點(diǎn)，算法的時(shí)間復(fù)雜度為O(n)。2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.3.1單鏈表1．單鏈表概述單鏈表(SingleLinkedList)是指在內(nèi)存中用一組連續(xù)的或不連續(xù)的存儲(chǔ)單元來存儲(chǔ)線性表的數(shù)據(jù)元素，每個(gè)元素含有一個(gè)數(shù)據(jù)域(data)和一個(gè)指針域(next)。這兩部分信息組成了單鏈表中的一個(gè)結(jié)點(diǎn)，如圖2.4所示。單鏈表中每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域用于存放結(jié)點(diǎn)的數(shù)據(jù)，指針域存放結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的地址。由于開始結(jié)點(diǎn)無前驅(qū)結(jié)點(diǎn)，故應(yīng)設(shè)頭指針head指向開始結(jié)點(diǎn)；終端結(jié)點(diǎn)無后繼結(jié)點(diǎn)，它的指針域?yàn)榭?，即NULL(圖示中也可以用^表示)。單鏈表正是通過頭指針以及每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯順序鏈接在一起。下面給出用C語言描述的單鏈表結(jié)點(diǎn)類型定義：指針變量簡稱指針，用于存放結(jié)點(diǎn)的地址，即用于指向結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)就是一個(gè)結(jié)構(gòu)體變量。若指針的值非空，則它指向一個(gè)類型為linklist的結(jié)點(diǎn)；若指針的值為空，則它不指向任何結(jié)點(diǎn)。指針?biāo)赶虻慕Y(jié)點(diǎn)存儲(chǔ)空間是在程序執(zhí)行過程中生成和釋放的，故稱為動(dòng)態(tài)存儲(chǔ)空間。在C語言中，通過下面兩個(gè)標(biāo)準(zhǔn)函數(shù)生成或釋放結(jié)點(diǎn)。生成結(jié)點(diǎn)：p=(linklist*)malloc(sizeof(linklist));

釋放結(jié)點(diǎn)：free(p);函數(shù)malloc的返回值類型是void*，然后進(jìn)行強(qiáng)制類型轉(zhuǎn)換得到一個(gè)類型為linklist的結(jié)點(diǎn)空間。p中所存放的是該結(jié)點(diǎn)的首地址，也可以說，p指向該結(jié)點(diǎn)。如果結(jié)點(diǎn)變量不再使用，調(diào)用函數(shù)free刪除結(jié)點(diǎn)所占的存儲(chǔ)空間。我們必須通過指針來訪問結(jié)點(diǎn)，即用?*p表示結(jié)點(diǎn)。用p->data和p->next或者?(*p).data和?(*p).next表示結(jié)點(diǎn)的數(shù)據(jù)域和指針域，前者是比較常用的形式。2．頭結(jié)點(diǎn)特別需要指出的是，單鏈表以及后面所討論的循環(huán)鏈表和雙向鏈表均可以帶頭結(jié)點(diǎn)或者不帶頭結(jié)點(diǎn)，見圖2.7和圖2.8。頭結(jié)點(diǎn)就是在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，頭結(jié)點(diǎn)數(shù)據(jù)域可以存放一些特殊信息。如果數(shù)據(jù)域?yàn)檎停梢源娣沛湵淼拈L度信息。使用頭結(jié)點(diǎn)的好處如下：(1)由于開始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，所以對(duì)鏈表第一個(gè)結(jié)點(diǎn)的操作同其他結(jié)點(diǎn)一樣，無需特殊處理。(2)無論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn)的非空指針，因此對(duì)空表與非空表的處理也就統(tǒng)一了。從上述兩點(diǎn)我們可以看出，使用頭結(jié)點(diǎn)可以降低鏈表操作的復(fù)雜性和出現(xiàn)錯(cuò)誤的機(jī)會(huì)。3．單鏈表的基本運(yùn)算下面我們將以帶頭結(jié)點(diǎn)的單鏈表為例，講述如何實(shí)現(xiàn)線性表的幾種基本運(yùn)算。1)建立單鏈表假設(shè)單鏈表結(jié)點(diǎn)的數(shù)據(jù)域類型是字符型，可逐個(gè)輸入字符，并以換行符“\n”作為輸入結(jié)束標(biāo)志。動(dòng)態(tài)建立單鏈表通常有以下兩種方法：(1)頭插法建表從空表開始，每次將輸入的字符作為新結(jié)點(diǎn)插入到表頭，鏈表中結(jié)點(diǎn)的次序與輸入字符的順序相反。請(qǐng)注意，圖2.9中給出的序號(hào)與算法中的序號(hào)是對(duì)應(yīng)的，表示在建表過程中的操作次序。算法2.6用頭插法建立單鏈表。算法2.6中循環(huán)語句的循環(huán)體執(zhí)行了n次，所以時(shí)間復(fù)雜度為O(n)。(2)尾插法建表如圖2.10所示，將新結(jié)點(diǎn)插入到表尾，鏈表中結(jié)點(diǎn)的次序與輸入字符的順序相同。算法2.7用尾插法建立單鏈表。如果在單鏈表中不設(shè)置頭結(jié)點(diǎn)，采用尾插法建表，需要對(duì)第一個(gè)結(jié)點(diǎn)進(jìn)行特殊處理。請(qǐng)讀者自行分析下面的算法2.8，并體會(huì)不設(shè)置頭結(jié)點(diǎn)的缺點(diǎn)。算法2.8用尾插法建立不帶頭結(jié)點(diǎn)的單鏈表。2)單鏈表的查找(1)按序號(hào)查找由于鏈表不是隨機(jī)存儲(chǔ)結(jié)構(gòu)，因此即使知道被訪問結(jié)點(diǎn)的序號(hào)i，也不能像順序表那樣直接按序號(hào)訪問結(jié)點(diǎn)，只能從頭指針出發(fā)，沿著結(jié)點(diǎn)的指針域進(jìn)行搜索，直至找到第i個(gè)結(jié)點(diǎn)為止。設(shè)單鏈表的長度為n，并且規(guī)定頭結(jié)點(diǎn)的位序?yàn)?，要查找第i個(gè)結(jié)點(diǎn)，僅當(dāng)1≤i≤n時(shí)，才能查找到。在算法2.9中，我們從頭結(jié)點(diǎn)開始沿著鏈表掃描，用指針p指向當(dāng)前掃描到的結(jié)點(diǎn)，用j作計(jì)數(shù)器，累計(jì)當(dāng)前已掃描的結(jié)點(diǎn)數(shù)。p的初值指向頭結(jié)點(diǎn)，j的初值為0，當(dāng)p指向下一個(gè)結(jié)點(diǎn)時(shí)，計(jì)數(shù)器j的值相應(yīng)加1。分析循環(huán)語句中的表達(dá)式，結(jié)束循環(huán)有兩種可能：一種是j等于i，此時(shí)指針p所指向的結(jié)點(diǎn)就是要查找的第i個(gè)結(jié)點(diǎn)；另一種可能是p->next為NULL并且j小于i，則單鏈表中不存在第i個(gè)結(jié)點(diǎn)。(2)按值查找。在單鏈表中查找是否存在給定查找值key的結(jié)點(diǎn)，若存在，則返回該結(jié)點(diǎn)的地址；否則返回NULL。算法2.10按值查找單鏈表。3)單鏈表的插入在單鏈表中插入或刪除元素，只需要修改指針的指向，不需要移動(dòng)結(jié)點(diǎn)。如圖2.11所示，將值為x的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到元素ai-1與ai之間。由于單鏈表只能做“后插”，不能做“前插”，因此必須先使指針p指向第i個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，然后將新結(jié)點(diǎn)插入在指針p所指向的結(jié)點(diǎn)之后。算法2.11插入單鏈表。設(shè)鏈表的長度為n，合法的插入位置是1≤i≤n+1。當(dāng)i=1時(shí)，p指向頭結(jié)點(diǎn)；當(dāng)i=n+1時(shí)，p指向終端結(jié)點(diǎn)。因此，用i-1作為實(shí)參調(diào)用Get時(shí)可完成插入位置的合法性檢查。算法的時(shí)間主要耗費(fèi)在查找操作Get上，所以時(shí)間復(fù)雜度為O(n)。在涉及改變指針指向的操作中，一定要注意操作的次序，否則容易出錯(cuò)。假如上面的③、④號(hào)操作的順序顛倒過來，會(huì)造成鏈表斷開，后面一截鏈表“丟失”了，如圖2.12所示。4)單鏈表的刪除要在單鏈表中刪除第i個(gè)結(jié)點(diǎn)ai，首先應(yīng)找到它的直接前驅(qū)結(jié)點(diǎn)ai-1的存儲(chǔ)位置p，然后使p->next指向ai的直接后繼結(jié)點(diǎn)，即把結(jié)點(diǎn)ai從鏈上摘下。刪除結(jié)點(diǎn)的示意圖如圖2.13所示。算法2.12刪除單鏈表。2.3.2循環(huán)鏈表循環(huán)鏈表(CircularLinkedList)是一種首尾相接的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。循環(huán)鏈表一般是指單循環(huán)鏈表，其特點(diǎn)是單鏈表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)或開始結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)，從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)。帶頭結(jié)點(diǎn)的單循環(huán)鏈表如圖2.14所示。在用頭指針表示的單循環(huán)鏈表中，找開始結(jié)點(diǎn)a1的時(shí)間復(fù)雜度為O(1)。然而要找到終端結(jié)點(diǎn)an，則需要從頭指針開始遍歷整個(gè)鏈表，其時(shí)間復(fù)雜度為O(n)。如果改用尾指針rear表示帶頭結(jié)點(diǎn)的單循環(huán)鏈表(見圖2.15)，則開始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an的存儲(chǔ)位置分別是rear->next->next和rear，查找這兩個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度都是O(1)。因此，在實(shí)際應(yīng)用中采用尾指針表示單循環(huán)鏈表，可以使某些運(yùn)算易于實(shí)現(xiàn)且效率高。2.3.3雙向鏈表在單循環(huán)鏈表中，雖然從任一結(jié)點(diǎn)出發(fā)能找到其直接前驅(qū)結(jié)點(diǎn)，但需要遍歷整個(gè)鏈表，其時(shí)間復(fù)雜度為O(n)。如果在每個(gè)結(jié)點(diǎn)內(nèi)再增加一個(gè)指向其直接前驅(qū)結(jié)點(diǎn)的指針域prior，就可以快速查找直接前驅(qū)結(jié)點(diǎn)。這樣的鏈表稱為雙向鏈表(DoubleLinkedList)，其結(jié)點(diǎn)的結(jié)構(gòu)體類型定義如下：與單向循環(huán)鏈表類似，雙向鏈表也可以采用循環(huán)表，將頭結(jié)點(diǎn)和終端結(jié)點(diǎn)鏈接起來，構(gòu)成順時(shí)針和逆時(shí)針的兩個(gè)環(huán)，如圖2.16所示。設(shè)指針p指向雙向鏈表中的某個(gè)結(jié)點(diǎn)，則p->prior->next讀作p所指結(jié)點(diǎn)的前驅(qū)指針域所指結(jié)點(diǎn)的后繼指針域，與p的指向是相同的。類似地，p->next->prior也與p的指向相同。在雙向鏈表中既可以進(jìn)行“后插”，也可以進(jìn)行“前插”，插入一個(gè)結(jié)點(diǎn)應(yīng)當(dāng)修改四個(gè)指針的指向。1．在結(jié)點(diǎn)?*p之后插入結(jié)點(diǎn)?*s雙向鏈表的后插操作如圖2.17所示，在結(jié)點(diǎn)?*p之后插入結(jié)點(diǎn)?*s需要注意以下兩點(diǎn)：(1)先修改待插入結(jié)點(diǎn)?*s的前驅(qū)和后繼指針域，以免發(fā)生“斷鏈”現(xiàn)象；(2)然后修改結(jié)點(diǎn)?*p的后繼指針域所指結(jié)點(diǎn)的前驅(qū)指針域，最后修改結(jié)點(diǎn)?*p的后繼指針域。算法2.13雙向鏈表的后插。2．在結(jié)點(diǎn)?*p之前插入結(jié)點(diǎn)?*s雙向鏈表的前插操作如圖2.18所示，應(yīng)當(dāng)先修改待插入結(jié)點(diǎn)的前驅(qū)和后繼指針域，然后修改結(jié)點(diǎn)?*p的前驅(qū)指針域所指結(jié)點(diǎn)的后繼指針域，最后修改結(jié)點(diǎn)?*p的前驅(qū)指針域。算法2.14雙向鏈表的前插。這兩種插入方法對(duì)指針操作的順序不是唯一的，但也不是任意的。操作次序不當(dāng)就有可能錯(cuò)誤地插入，還有可能“丟失”一部分鏈表。3．刪除結(jié)點(diǎn)?*p雙向鏈表中刪除結(jié)點(diǎn)?*p的操作如圖2.19所示，刪除一個(gè)結(jié)點(diǎn)需要改變兩個(gè)指針的指向。算法2.15雙向鏈表的刪除。4．建立雙向鏈表與單鏈表的建立類似，建立雙向鏈表也分為頭插法和尾插法。算法2.16采用頭插法建立