順序表示的棧和隊(duì)列必須預(yù)先分配空間并且空... -

1、第二章 線性表教學(xué)目標(biāo)l 掌握線性表的基本概念，ADT描述方法；l 掌握線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述方法，以及線性表的各種基本操作的實(shí)現(xiàn)；l 能夠從時(shí)間和空間復(fù)雜度的角度，綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場合；l 會(huì)運(yùn)用線性表解決實(shí)際問題。數(shù)據(jù)結(jié)構(gòu)分線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性的數(shù)據(jù)結(jié)構(gòu)有線性表、棧、隊(duì)列、數(shù)組和串。線性結(jié)構(gòu)的特點(diǎn)是數(shù)據(jù)元素存放在非空有限集合中，并且滿足如下幾個(gè)條件：·存在唯一的“第一個(gè)”數(shù)據(jù)元素；·存在唯一的“最后一個(gè)”數(shù)據(jù)元素； ·除第一個(gè)數(shù)據(jù)元素之外，集合中的每一個(gè)數(shù)據(jù)元素都只有一個(gè)前驅(qū)；·除最后一個(gè)數(shù)據(jù)元素之

2、外，集合中的每一個(gè)數(shù)據(jù)元素都只有一個(gè)后繼。2.1 線性表的定義線性表是線性結(jié)構(gòu)中最常用而又最簡單的一種數(shù)據(jù)結(jié)構(gòu)。簡而言之，一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列。線性表中數(shù)據(jù)元素的具體含義在不同情況下各不相同，但同一線性表中的元素類型是相同的，也就是說，同一表中的元素必定具有相同的屬性。例如，英文字母表（A，B，C，Z）是一個(gè)線性表，表中的數(shù)據(jù)元素是單個(gè)字母。又如（1，2，3，50）也是一個(gè)線性表，表中的數(shù)據(jù)元素是整數(shù)。這兩個(gè)線性表的元素都是單個(gè)數(shù)據(jù)項(xiàng)組成。在比較復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。在圖2.1所示的學(xué)生成績表中，每一個(gè)學(xué)生的情況為一個(gè)元素，它由姓名、學(xué)號(hào)、班級(jí)、語文

3、成績、數(shù)學(xué)成績和英語成績等六個(gè)數(shù)據(jù)項(xiàng)組成。表2.1 學(xué)生成績表姓名學(xué)號(hào)班級(jí)離散高數(shù)英語陳強(qiáng)2002000102計(jì)科2929078胡大2002000202計(jì)科2807875周兵2002000302計(jì)科2959085李可2002000402計(jì)科2707065從上面的例子中可以看出，線性表中的數(shù)據(jù)元素可以是各種各樣的，但任何表中的元素必定具有相同特性，即屬同一數(shù)據(jù)類型，數(shù)據(jù)元素之間相對(duì)位置是線性的。通常，我們把非空線性表表示為（a0，a1，ai-1，ai，ai+1，an-1），其中a0是線性表的第一個(gè)元素，ai是第i-1個(gè)元素，an-1是最后一個(gè)元素。元素的個(gè)數(shù)n（n0）定義為線性表的長度，當(dāng)n=0

4、時(shí)稱為空表，空表中沒有元素。線性表具有線性結(jié)構(gòu)的特點(diǎn)，表中ai元素的直接前驅(qū)元素是ai-1，ai元素的直接后繼元素是ai+1。除了a0和an-1之外，每個(gè)ai都有且僅有一個(gè)直接前趨和一個(gè)直接后繼，a0沒有前趨，an-1沒有后繼。線性表是一種非常靈活的數(shù)據(jù)結(jié)構(gòu)，可以根據(jù)需要對(duì)表中的任何數(shù)據(jù)元素進(jìn)行訪問，元素的插入和刪除可以在表中的任何位置進(jìn)行，可以將兩個(gè)表連接成一個(gè)表，還可以把一個(gè)表拆分成兩個(gè)或多個(gè)表等。線性表的ADT描述如下：ADT List；數(shù)據(jù)元素 各種具有相同屬性的數(shù)據(jù)對(duì)象（可以是基本數(shù)據(jù)類型，也可以是構(gòu)造數(shù)據(jù)類型）；操作 InitList(L) 初始化操作，生成一個(gè)空的線性表L。Lis

5、tLength(L) 求表長度函數(shù)。求線性表L中數(shù)據(jù)元素的個(gè)數(shù)。GetElem(L，i) 獲取表中元素的函數(shù)。當(dāng)0iListLength(L)-1時(shí)，函數(shù)值為線性表L中第i個(gè)數(shù)據(jù)元素，否則返回空值null。i是該數(shù)據(jù)元素在線性表中的位置序號(hào)。IsEmpty(S) 判斷空線性表函數(shù)。如果L是空表，返回“true”，否則返回“false”。LocateElem(L，x) 定位函數(shù)。返回L中第1個(gè)與x相等的數(shù)據(jù)元素的位置序號(hào)。若這樣的元素不存在，則返回值為0。Insert(L，x，i) 插入操作。在給定線性表L中第i（0iListLength(L)）個(gè)數(shù)據(jù)元素之前插入一個(gè)新的數(shù)據(jù)元素x，線性表的長度

6、變成n+1。Delete(L，i) 刪除操作。刪除線性表L中第i（0iListLength(L)-1）個(gè)數(shù)據(jù)元素，線性表的長度減1。Clear(L) 表置空操作。無論線性表L是否為空表，操作結(jié)果將L表置空。2.2 線性表的順序存儲(chǔ)2.2.1 順序表順序表是指采用順序存儲(chǔ)結(jié)構(gòu)的線性表，它利用內(nèi)存中的一片起始位置確定的連續(xù)存儲(chǔ)區(qū)域來存放線性表中的所有元素，如圖2.1所示。它的特點(diǎn)是邏輯上相鄰的數(shù)據(jù)元素，其物理存儲(chǔ)位置也是相鄰的，也就是說表中的邏輯關(guān)系和物理關(guān)系是一致的。在圖2.1中，假設(shè)每個(gè)數(shù)據(jù)元素占用c個(gè)存儲(chǔ)單元，表中第一個(gè)元素的存儲(chǔ)地址作為線性表的存儲(chǔ)起始地址LOC（a0），用b來表示。由于同

7、一線性表中數(shù)據(jù)元素的類型相同，則線性表中任意相鄰的兩個(gè)數(shù)據(jù)元素ai與ai+1的存儲(chǔ)首址LOC（ai）與LOC（ai+1）將滿足下面的關(guān)系:MAXSIZE元素序號(hào)012in-1存儲(chǔ)首址012in-1MAXSIZE-1bb+cb+2cb+i*cb+(n-1)*c線性表空閑圖2.1 線性表的順序存儲(chǔ)結(jié)構(gòu)。an-1a0a1a2。aiLOC（ai+1）= LOC（ai）+c一般來說，線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)首址為LOC（ai）= b+ i*c（0in-1）也就是說，只要知道線性表的起始地址LOC（a0）b和一個(gè)元素所占用的存儲(chǔ)單元c，表中的任意一個(gè)元素的存儲(chǔ)地址均可由上面的公式求得，且計(jì)算所花費(fèi)

8、的時(shí)間是一樣的，所以，訪問表中任意元素的時(shí)間相等，并且可以隨機(jī)存取。由于高級(jí)程序設(shè)計(jì)語言中一維數(shù)組（即向量）也是采用順序存儲(chǔ)表示，因此可用一維數(shù)組elementsMAXSIZE來描述順序表，其中MAXSIZE是一個(gè)預(yù)先設(shè)定的常數(shù)，表示線性表存儲(chǔ)空間的大小，預(yù)設(shè)為100，實(shí)際使用時(shí)其值應(yīng)有所選擇，使得它既能滿足線性表中的元素個(gè)數(shù)動(dòng)態(tài)增加的需求，又不至于因預(yù)先定義得過大而浪費(fèi)存儲(chǔ)空間。至于順序表的長度（即線性表中元素的數(shù)目）可用一個(gè)整型變量last來表示，所以我們可用結(jié)構(gòu)類型來定義順序表的類型。#define MAXSIZE 100 /* MAXSIZE 為線性表可能的最大長度 */#define

9、 ERROR -1typedef struct /* 線性表定義 */int elementsMAXSIZE;int last; /* last為線性表的長度 */ SqList;定義了線性表的順序存儲(chǔ)結(jié)構(gòu)后，下面我們就在這種結(jié)構(gòu)的基礎(chǔ)之上討論如何實(shí)現(xiàn)線性表的基本運(yùn)算。void InitList(SqList *L) /*初始化操作，將線性表L置空*/L->last = 0;bool IsEmpty( SqList L) /*判斷表是否為空。如果L是空表，返回true，否則返回false*/if( L.last = 0 ) return true;else return false;in

10、t GetElem(SqList L,int i) /* 取表中第i元素。*/if(i<0 | i>=L.last) return ERROR;else return L.elementsi; /*C語言中數(shù)組的下標(biāo)從"0"開始*/int LocateElem(SqList L,int x) /*定位函數(shù)。返回L中第1個(gè)與x相等的數(shù)據(jù)元素的位置（從0算起）。*/ /*否則返回值為0。*/int k; k=0; while (k<L.last && L.elementsk!=x) k+; if(k<L.last) return k; e

11、lse return ERROR;int Insert(SqList *L,int x,int i) /*在線性表L中第i（0iL.last）個(gè)數(shù)據(jù)元素之前插入一個(gè)數(shù)據(jù)元素x*/int k; if(i<0 | i>L->last | L->last = MAXSIZE) return ERROR; else for( k=L->last; k>=i; k- ) L->elementsk= L->elementsk-1; L->elementsi=x; L->last=L->last+1;return true;int Dlete

12、(SqList *L,int i) /*刪除線性表L中第i（0I<L.last）個(gè)數(shù)據(jù)元素*/int k;if( i<0 | i>=L->last ) /* 下標(biāo)越界 */ return ERROR;else /* 移動(dòng)后面的元素 */ for(k=i;k<L->last;k+) L->elementsk= L->elementsk+1; L->last-;return true;void Clear(SqList *L) /* 清空線性表L */InitList( L );對(duì)于插入和刪除兩個(gè)算法，其算法執(zhí)行的時(shí)間都主要花費(fèi)在元素的移動(dòng)上。

13、而移動(dòng)元素的次數(shù)不僅與具體位置上插入或刪除的概率有關(guān)，而且還與插入或刪除的位置本身有關(guān)。在表頭附近進(jìn)行插入或刪除比在表尾附近進(jìn)行插入或刪除元素的移動(dòng)數(shù)要多一些。所以，我們要討論的是進(jìn)行這些操作時(shí)元素的平均移動(dòng)次數(shù)。設(shè)Pi是在第i個(gè)元素之前插入一個(gè)元素的概率，假定在順序表中任何位置插入元素的機(jī)會(huì)相等，即設(shè)Pi，則在長度為n的線性表中插入一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為E（n）=設(shè)qi是刪除第i個(gè)元素的概率，假定在順序表中刪除元素的機(jī)會(huì)相等，即設(shè)qi，則在長度為n的線性表中刪除一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為E（n）=通過上述討論可知，在順序表中插入或刪除一個(gè)數(shù)據(jù)元素，大約移動(dòng)表中一半元素。當(dāng)

14、線性表的長度較大，且插入和刪除操作的頻度較高時(shí)，則花費(fèi)時(shí)間較多，不宜采用順序存儲(chǔ)結(jié)構(gòu)。但是順序表存儲(chǔ)結(jié)構(gòu)簡單，便于順序存儲(chǔ)，存儲(chǔ)空間的利用率高。2.2.2 順序表的應(yīng)用舉例例1 已知順序表la和lb中的數(shù)據(jù)元素依值非遞減有序排列，現(xiàn)將la和lb歸并為一個(gè)新的的順序表lc，且lc中的數(shù)據(jù)元素也依值非遞減有序排列。例如:la=(2,4,6,8,9)lb=(3,5,7,9,11,13,18)則lc=(2,3,4,5,6,7,8,9,9,11,13,18)具體算法的實(shí)現(xiàn)思路是：設(shè)三個(gè)指針i，j，k初始值均為0，其中i，j分別指向la和lb順序表中第一個(gè)數(shù)據(jù)元素，k指向lc中元素即將存放的序號(hào)。分別取l

15、a和lb中i、j所指的數(shù)據(jù)元素進(jìn)行比較，當(dāng)la的元素不大于lb的元素時(shí)，將la的當(dāng)前元素放入lc中，同時(shí)i，k指針增1，否則將lb的當(dāng)前元素放入lc中，同時(shí)j，k指針增1。對(duì)應(yīng)的算法如下：void MergeList(SqList la, SqList lb, SqList *lc) /* 合并表有序表la和lb到表lc中，使得lc依然有序 */int i,j,k;i = j = k = 0;while(i<la.last && j<lb.last) /* la和lb均不空 */if( la.elementsi < lb.elementsj ) lc->

16、elements k+ = la.elementsi+; else if( la.elementsi > lb.elementsj )lc->elementsk+=lb.elementsj+;else /* la和lb中的當(dāng)前元素相等時(shí)，同時(shí)移動(dòng)指針 */lc->elementsk+=lb.elementsj+; i+;while(i < la.last) /* la非空,lb己空 */lc->elementsk+=la.elementsi+;while(j < lb.last) /* la己空,lb非空 */lc->elementsk+=la.ele

17、mentsj+;lc->last=k;例2 清除順序表中的重復(fù)數(shù)據(jù)元素。例如，順序表（2，3，3，4，3，5，4）清除后變?yōu)椋?，3，4，5）。清除重復(fù)元素是指刪除重復(fù)元素，只保留序號(hào)最小的一個(gè)。具體的算法實(shí)現(xiàn)思路是：從順序表中依次取出每一個(gè)元素ai，并檢查ai+1到an-1中是否有元素與ai值相等，有就刪除重復(fù)元素。void ClearList(SqList *L) /* 清除順序表中的重復(fù)數(shù)據(jù)元素 */int i = 0, j;while( i < L->last ) j = i + 1;while(j<=L->last) /* 找重復(fù)數(shù)據(jù)元素并刪除 */if

18、( L->elementsi = L->elementsj ) Dlete(L,j); /* 下一個(gè)元素自動(dòng)向前移動(dòng)過來 */else j+; /* 指針向下移動(dòng)一個(gè)位置 */ i+; 2.3 線性表的鏈?zhǔn)酱鎯?chǔ)由上節(jié)的討論可知，線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是借助于元素物理位置上的鄰接關(guān)系來表示元素間的邏輯關(guān)系，這一特點(diǎn)使我們可以隨機(jī)地存取表中任何一個(gè)元素，但它的缺點(diǎn)也很明顯。如元素的插入、刪除需要移動(dòng)大量的數(shù)據(jù)元素，操作效率極低,而且由于順序表要求連續(xù)的存儲(chǔ)空間，存儲(chǔ)空間必須預(yù)先分配，表的最大長度卻很難確定。最大長度估計(jì)過小會(huì)出現(xiàn)表滿溢出，估計(jì)過大又會(huì)造成存儲(chǔ)空間的浪費(fèi)。本節(jié)將介紹線

19、性表的另一種存儲(chǔ)方法，稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。該方法可以克服順序表的上述缺點(diǎn)，但隨之而來的卻是隨機(jī)存取性能的消失。我們通常把鏈?zhǔn)酱鎯?chǔ)的線性表簡稱為鏈表。2.3.1 單鏈表2.3.1.1單鏈表的基本概念鏈表是用一組任意的存儲(chǔ)單元來依次存儲(chǔ)線性表中的各個(gè)數(shù)據(jù)元素，這些存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。為了能正確反映數(shù)據(jù)元素之間的邏輯關(guān)系，我們可以用指向直接后繼的指針來表示。用鏈接存儲(chǔ)結(jié)構(gòu)表示線性表的一個(gè)元素時(shí)至少要有兩部分信息:一是這個(gè)數(shù)據(jù)元素的值，二是這個(gè)數(shù)據(jù)元素的直接后繼的存儲(chǔ)地址。這兩部分信息一起組成了鏈表的一個(gè)結(jié)點(diǎn)。鏈表中結(jié)點(diǎn)的結(jié)構(gòu)如下:datanext其中，data域是數(shù)據(jù)域，用來存放數(shù)

20、據(jù)元素的值；next域稱指針域（又稱鏈域）用來存放該數(shù)據(jù)元素的直接后繼結(jié)點(diǎn)的地址。鏈表正是通過每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接成為一個(gè)整體。由于這種鏈表的每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，故稱這種鏈表為單鏈表。由于我們只注重鏈表中結(jié)點(diǎn)的邏輯順序，并不關(guān)心每個(gè)結(jié)點(diǎn)的實(shí)際存儲(chǔ)位置，通常用箭頭表示鏈域中的指針，于是單鏈表就可以直觀地畫成用箭頭鏈接起來的結(jié)點(diǎn)序列，如圖2.2所示。從圖中可見，單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址存放在其直接前驅(qū)的指針域中，因此訪問單鏈表的每一個(gè)結(jié)點(diǎn)必須從表頭指針開始進(jìn)行，這表明單鏈表在邏輯上依然是順序結(jié)構(gòu)的。a0a1a2an-1圖2.2 一般單鏈表圖示head 用C語言描

21、述單鏈表的結(jié)點(diǎn)結(jié)構(gòu)如下：typedef struct node /* 單鏈表結(jié)點(diǎn)結(jié)構(gòu) */DataType data; /*DataType可以是任何相應(yīng)的數(shù)據(jù)類型如int,char等*/struct node *next; LinkList;指針變量和結(jié)點(diǎn)變量是兩個(gè)容易混淆而又必須搞清楚的概念。定義指針變量后，要使它有確定的指向必須給它賦值或者使用標(biāo)準(zhǔn)函數(shù)調(diào)用來完成，如：p=( LinkList *) malloc(sizeof(LinkList)函數(shù)malloc分配一個(gè)類型為LinkList的結(jié)點(diǎn)空間，并將起始地址放入p中。這就是說指針變量所指向的結(jié)點(diǎn)變量的存儲(chǔ)空間只是在程序的執(zhí)行過程中，

22、當(dāng)需要時(shí)才產(chǎn)生的，故稱動(dòng)態(tài)變量。一旦所指向的結(jié)點(diǎn)變量不再需要了，又可通過標(biāo)準(zhǔn)函數(shù)free(p)釋放p所指向的結(jié)點(diǎn)變量占用的空間。結(jié)點(diǎn)變量的訪問是通過指向它的指針p來實(shí)現(xiàn)的，即用*p作為該結(jié)點(diǎn)變量的名字來訪問。在C語言中，對(duì)指針?biāo)赶蚪Y(jié)點(diǎn)的成員進(jìn)行訪問時(shí)，通常用運(yùn)算符“->”來表示。例如取上面結(jié)構(gòu)中的兩個(gè)分量，可以寫成（*p）.data和（*p）.next，也可以寫成p->data和p->next。它們之間的關(guān)系如圖2.3所示。圖2.3 指針變量與結(jié)點(diǎn)變量head*p*(p->next)p->datap->nextp下面我們將討論用單鏈表表示線性表時(shí)，如何實(shí)現(xiàn)

23、它的幾種基本運(yùn)算。2.3.1.2 單鏈表的基本運(yùn)算1建立單鏈表假設(shè)線性表中結(jié)點(diǎn)的數(shù)據(jù)類型為整型，有效值域?yàn)榉秦?fù)整數(shù)，那么我們可以依次輸入這些整數(shù)，并以0作為輸入結(jié)束標(biāo)志符，動(dòng)態(tài)地建立單鏈表。建表的方法通常有兩種：一種是頭插入法，也就是每輸入一個(gè)不為零整數(shù)就建立結(jié)點(diǎn)，把結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭之前；另外一種是尾插入法，它是把新生成的結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾結(jié)點(diǎn)之后。這兩種方法的區(qū)別是生成鏈表的結(jié)點(diǎn)的次序和輸入的順序不一樣。（a） 非空鏈表heada0a1an-1head頭結(jié)點(diǎn)(b) 空鏈表圖2.4 帶頭結(jié)點(diǎn)的單鏈表頭結(jié)點(diǎn)為了使鏈表上有些操作實(shí)現(xiàn)起來簡單、清晰，通常在鏈表的第一個(gè)結(jié)點(diǎn)之前增設(shè)一個(gè)類

24、型相同的附加結(jié)點(diǎn)，稱之為頭結(jié)點(diǎn)，如圖2.4所示。在單鏈表中引入頭結(jié)點(diǎn)通常有兩個(gè)好處：首先，線性表中的第一個(gè)元素結(jié)點(diǎn)的地址被存放在頭結(jié)點(diǎn)的指針域中，這樣對(duì)第一個(gè)元素結(jié)點(diǎn)的處理與其他結(jié)點(diǎn)處理一致，無需特殊處理，簡化了算法；其次，無論鏈表是否為空，頭指針總指向頭結(jié)點(diǎn)，除初始化外，任何操作都不會(huì)改變頭指針，給算法的處理帶來方便。不帶頭結(jié)點(diǎn)的頭插入算法如下：void InitList1( LinkList *head ) /* 初始化不帶頭結(jié)點(diǎn)的鏈表頭指針 */*head = NULL;void AddHead1(LinkList *head, int x )/* 向頭指針為head的鏈表中插入一個(gè)結(jié)點(diǎn)

25、，其值為x */LinkList *p;p=( LinkList *)malloc(sizeof(LinkList);p->data = x;p->next = *head;*head = p; /* 調(diào)整鏈表頭指針head */帶頭結(jié)點(diǎn)的尾插入算法的執(zhí)行過程如圖2.5所示，其算法如下：頭結(jié)點(diǎn)qhead1232p圖2.5 尾插入法建立單鏈表的插入過程void InitList( LinkList *head ) /* 初始化帶頭結(jié)點(diǎn)的鏈表頭指針 */*head = ( LinkList *)malloc(sizeof(LinkList);(*head)->next=NULL;

26、void AddHead( LinkList *head, int x ) /* 建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表，返回表頭指針 */LinkList *p,*q=head; while( q->next ) q = q->next; /* q指向鏈表的尾結(jié)點(diǎn) */p=( LinkList *)malloc(sizeof(LinkList);p->data = x; /* 填充數(shù)據(jù) */p->next = q->next; /* 調(diào)整指針 */q->next = p; /* 掛到鏈表上 */2按序號(hào)查找單鏈表是一種順序存取結(jié)構(gòu)，如果要訪問表中第i個(gè)結(jié)點(diǎn)必須從頭結(jié)點(diǎn)出

27、發(fā)開始搜索，直到第i個(gè)結(jié)點(diǎn)為止。設(shè)單鏈表的長度為n，從頭結(jié)點(diǎn)開始，頭結(jié)點(diǎn)上指向的結(jié)點(diǎn)看成第0個(gè)結(jié)點(diǎn)，其他結(jié)點(diǎn)編號(hào)依次順序編號(hào)。從頭結(jié)點(diǎn)開始順著鏈搜索，用指針p指向當(dāng)前掃描到的結(jié)點(diǎn)，用j作計(jì)數(shù)器。p的初值指向頭結(jié)點(diǎn)，j的初值為0，當(dāng)p掃描下一個(gè)結(jié)點(diǎn)時(shí)，計(jì)數(shù)器j相應(yīng)地加1。當(dāng)j=i時(shí)，p所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)。算法如下：LinkList *GetNode( LinkList *head, int i )/* 在帶頭結(jié)點(diǎn)的單鏈表中查找第i個(gè)結(jié)點(diǎn)，找到返回該結(jié)點(diǎn)指針，否則返回NULL */LinkList *p = head; int j=0;while( p->next &&a

28、mp; j<i ) j+; p=p->next; /* p右移一個(gè)結(jié)點(diǎn) */if(j=i) return p;else return NULL;3按值查找按值查找是在帶頭結(jié)點(diǎn)的查找單鏈表中查找第一個(gè)和給定值x相等的結(jié)點(diǎn)，若查到則返回指向該結(jié)點(diǎn)的指針，否則返回NULL。查找過程從頭結(jié)點(diǎn)開始，依次將每個(gè)結(jié)點(diǎn)的值與x作比較，直到查找成功或到達(dá)表尾為止。算法如下：LinkList *LocateNode(LinkList *head, int x)/* 在帶頭結(jié)點(diǎn)的單鏈表中查找值為x的結(jié)點(diǎn)，找到返回結(jié)點(diǎn)指針，否則返回NULL */LinkList *p = head->next;wh

29、ile( p && p->data != x ) p=p->next;return p;4插入插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表中第i（0in-1）個(gè)位置上，n為插入前表的長度。具體方法是先找第i-1個(gè)結(jié)點(diǎn)，若找到則把新結(jié)點(diǎn)插入作為該結(jié)點(diǎn)的直接后繼。其插入過程如圖2.6所示。其算法如下：x圖2.6 在*p結(jié)點(diǎn)后插入*q結(jié)點(diǎn)ai-1aiqpvoid InsertNode(LinkList *head, int i, int x)/* 在帶頭結(jié)點(diǎn)的單鏈表中第i個(gè)結(jié)點(diǎn)位置上插入值為x的結(jié)點(diǎn) */LinkList *p, *q; p=GetPrior(head, i); /

30、*找到第i個(gè)結(jié)點(diǎn)的前驅(qū) */if(p!=NULL) q=( LinkList *)malloc(sizeof(LinkList);q->data=x;q->next=p->next; /*對(duì)應(yīng)圖2.6 */p->next=q; /*對(duì)應(yīng)圖2.6 */ else /* 插入到最后一個(gè)結(jié)點(diǎn)之后 */AddHead( head, x );5刪除ai+1圖2.7 刪除*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)ai-1aiqp刪除操作是指刪除單鏈表中第i（0in-1）個(gè)結(jié)點(diǎn)。具體方法是先找第i-1個(gè)結(jié)點(diǎn)，然后刪除該結(jié)點(diǎn)的直接后繼（即第i個(gè)結(jié)點(diǎn)）。另外，由于被刪除結(jié)點(diǎn)已經(jīng)毫無用處，所以要向系統(tǒng)申請(qǐng)釋放該結(jié)

31、點(diǎn)的空間。其刪除過程如圖2.7所示。其算法如下：void DeleteNode（LinkList *head, int i）/* 在帶頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn) */LinkList *p,*q； p=GetNode(head,i-1); /*找到第i-1個(gè)結(jié)點(diǎn) */if（(p!=NULL)&&(p->next!=NULL)） q=p->next; /*對(duì)應(yīng)圖2.8 */p->next=q->next; /*對(duì)應(yīng)圖2.8 */ free(q); /*對(duì)應(yīng)圖2.8 */else printf(“結(jié)點(diǎn)未找到！n”);6求表長求表長就是求表中除頭結(jié)點(diǎn)外的結(jié)

32、點(diǎn)的個(gè)數(shù)。具體方法是從頭結(jié)點(diǎn)開始順著鏈搜索，用指針p指向當(dāng)前掃描到的結(jié)點(diǎn)，用j作計(jì)數(shù)器。p的初值指向頭結(jié)點(diǎn)，j的初值為0，當(dāng)p掃描下一個(gè)結(jié)點(diǎn)時(shí)，計(jì)數(shù)器j相應(yīng)地加1。當(dāng)p到達(dá)尾結(jié)點(diǎn)時(shí)，j的值就是表的長度。其算法如下：int Length(LinkList *head)/* 在帶頭結(jié)點(diǎn)的單鏈表中求表的長度 */LinkList *p=head; int j=0;while (p->next!=NULL) j+;p=p->next; /* p右移一個(gè)結(jié)點(diǎn) */return j;2.3.2 循環(huán)鏈表單鏈表的最后一個(gè)結(jié)點(diǎn)的指針域的值是NULL，如果將這個(gè)域改為指向單鏈表的第一個(gè)結(jié)點(diǎn)，那么整個(gè)

33、鏈表就形成了一個(gè)環(huán)形結(jié)構(gòu)，故稱為單鏈形式的循環(huán)鏈表，并簡稱為單循環(huán)鏈表。類似地還有多重鏈形式的循環(huán)鏈表，如雙向循環(huán)鏈表。單循環(huán)鏈表中所在結(jié)點(diǎn)被鏈在一個(gè)環(huán)上，多重循環(huán)鏈表則是把表中結(jié)點(diǎn)鏈在多個(gè)環(huán)上。為了使空表與非空表的處理一致，循環(huán)鏈表也經(jīng)常設(shè)置頭結(jié)點(diǎn)。空循環(huán)鏈表僅由一個(gè)頭結(jié)點(diǎn)組成，自成循環(huán)。帶頭結(jié)點(diǎn)的單循環(huán)鏈表如圖2.8所示。（a） 非空循環(huán)鏈表heada1a2anhead頭結(jié)點(diǎn)(b) 空循環(huán)鏈表圖2.8 帶頭結(jié)點(diǎn)的單循環(huán)鏈表頭結(jié)點(diǎn)循環(huán)鏈表的特點(diǎn)是從表中任一結(jié)點(diǎn)出發(fā)均可訪問其他所有結(jié)點(diǎn)。用頭指針表示的單循環(huán)鏈表找尾結(jié)點(diǎn)時(shí)同單鏈表一樣要從頭結(jié)點(diǎn)搜索到尾結(jié)點(diǎn)，沒有任何優(yōu)勢。在許多實(shí)際問題中，鏈表的

34、操作經(jīng)常在表的首尾兩端進(jìn)行，此時(shí)用頭指針表示的單循環(huán)鏈表就顯得不夠方便。如果改用尾指針rear來表示單循環(huán)鏈表，則頭結(jié)點(diǎn)的指針為rear->next，第一個(gè)結(jié)點(diǎn)的指針為rear->next->next，訪問第一個(gè)結(jié)點(diǎn)和尾結(jié)點(diǎn)都很方便，有利于在兩端進(jìn)行操作。用尾指針rear表示的單循環(huán)鏈表如圖2.9所示。（a） 非空循環(huán)鏈表a1a2anrear頭結(jié)點(diǎn)(b) 空循環(huán)鏈表圖2.9 用尾指針rear表示的單循環(huán)鏈表頭結(jié)點(diǎn)rear2.3.3 雙向鏈表在單鏈表中，給定一個(gè)p指向的結(jié)點(diǎn)，可以沿著指針方向立即訪問到該結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)*（p->next），卻無法訪問到該結(jié)點(diǎn)的直接前驅(qū)結(jié)

35、點(diǎn)。唯一的辦法是從表頭開始順鏈查找，直到當(dāng)前結(jié)點(diǎn)的指針域（存放的是后繼結(jié)點(diǎn)的指針）與p相等，那么這個(gè)結(jié)點(diǎn)就是p所指結(jié)點(diǎn)的直接前驅(qū)。同樣在單循環(huán)鏈表中，雖然從任一結(jié)點(diǎn)出發(fā)可訪問到表中所有結(jié)點(diǎn)，但要找到某個(gè)結(jié)點(diǎn)的直接前驅(qū)同樣要遍歷整個(gè)表，原因是表中每個(gè)結(jié)點(diǎn)只有指向其直接后繼的指針。若希望快速找到一個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)地址，可以在每個(gè)結(jié)點(diǎn)內(nèi)再增加一個(gè)指向其直接前驅(qū)的鏈域，這樣形成的鏈表中就有兩條方向不同的鏈，故稱為雙向鏈表（Double linked list）。用C語言描述雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)如下：typedef struct dnode /* 雙向鏈表結(jié)點(diǎn)結(jié)構(gòu) */DataType data; /*D

36、ataType可以是任何相應(yīng)的數(shù)據(jù)類型如int,char等*/struct dnode *prior,*next; DLinkList;和單鏈表類似，為了使得某些運(yùn)算方便一些，雙鏈表也可附加頭結(jié)點(diǎn)。同樣也可以把雙鏈表的頭結(jié)點(diǎn)與尾結(jié)點(diǎn)鏈接起來構(gòu)成循環(huán)鏈表，稱之為雙向循環(huán)鏈表。帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表如圖2.10所示。圖2.10帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表a1head頭結(jié)點(diǎn)head（a）非空雙向循環(huán)鏈表（b）空雙向循環(huán)鏈表a0an-1pq圖2.11 在雙鏈表的*p結(jié)點(diǎn)之前插入新結(jié)點(diǎn)*q在雙鏈表中每個(gè)結(jié)點(diǎn)既有指向直接前驅(qū)結(jié)點(diǎn)的指針又有指向直接后繼結(jié)點(diǎn)的指針，這就使得原本在單鏈表上很困難的操作在雙鏈表上很容易

37、就實(shí)現(xiàn)，如在p指向的結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)，刪除p指向的結(jié)點(diǎn)等。這些操作均要找到該結(jié)點(diǎn)的直接前驅(qū)，在雙鏈表中本身就有一個(gè)指向其直接前驅(qū)的鏈域，所以操作的實(shí)現(xiàn)很簡單，僅僅修改相應(yīng)的指針即可。在雙單鏈表的*p結(jié)點(diǎn)之前插入值為x的結(jié)點(diǎn)插入的過程如圖2.11所示。其算法如下：void InsertDNode(DLinkList *p, int x)/* 在雙鏈表的*p結(jié)點(diǎn)之前插入值為x的結(jié)點(diǎn) */DLinkList *q; q=( DLinkList *)malloc(sizeof(DLinkList);q->data=x;q->prior=p->prior; /*對(duì)應(yīng)圖2.11 *

38、/q->next=p; /*對(duì)應(yīng)圖2.11 */p->prior->next=q; /*對(duì)應(yīng)圖2.11 */p->prior=q; /*對(duì)應(yīng)圖2.11 */在雙鏈表中刪除p指針指向的結(jié)點(diǎn)的過程如圖2.12所示。其算法如下：p圖2.12 在雙鏈表中刪除p指針指向的結(jié)點(diǎn) void DeleteDNode(DLinkList *p)/* 在雙鏈表中刪除p指針指向的結(jié)點(diǎn) */p->prior->next=p->next; /*對(duì)應(yīng)圖2.12 */p->next->prior=p->prior; /*對(duì)應(yīng)圖2.12 */free(p);2.3.

39、4 鏈表的應(yīng)用舉例例1頭結(jié)點(diǎn) 有一個(gè)不帶頭結(jié)點(diǎn)的單鏈表L（至少有1個(gè)結(jié)點(diǎn)），第一個(gè)結(jié)點(diǎn)指針為head，編寫算法將L逆置，即最后一個(gè)結(jié)點(diǎn)變成第一個(gè)結(jié)點(diǎn)，倒數(shù)第二個(gè)結(jié)點(diǎn)變成第二個(gè)結(jié)點(diǎn)，如此等等。逆置的方法是：從頭到尾掃描單鏈表L，將第一個(gè)結(jié)點(diǎn)的next域設(shè)置為NULL，將第二個(gè)結(jié)點(diǎn)的next域指向第一個(gè)結(jié)點(diǎn)，將第三個(gè)結(jié)點(diǎn)的next域指向第二個(gè)結(jié)點(diǎn)，如此進(jìn)行直到最后一個(gè)結(jié)點(diǎn)，用head指向它。其算法如下：void Invert1( LinkList *head ) /* 將不帶頭指針的單鏈表倒置 */LinkList *p = *head, *r;LinkList *q = NULL;/* q始終指

40、向當(dāng)前插入點(diǎn) */while( p ) /* 還有剩余元素時(shí) */r = p->next; /* r緩存下一個(gè)待插入元素指針 */p->next = q; /* 插入當(dāng)前的待插元素到新表中 */q = p; p = r; /* 調(diào)整 */*head = q;/* 更新頭指針 */例2有一個(gè)帶頭結(jié)點(diǎn)的非遞減有序單鏈表L，頭結(jié)點(diǎn)指針為head，編寫算法向L中插入一個(gè)值為x的元素，使插入后仍為非遞減有序。解決本題的具體方法是：先建立一個(gè)待插入的結(jié)點(diǎn)，結(jié)點(diǎn)的data域賦值為x，然后鏈表中各結(jié)點(diǎn)的數(shù)據(jù)域依次與x比較大小，直到找到插入的位置，最后插入該結(jié)點(diǎn)。其算法如下：void InsertO

41、rder(LinkList *head,int x) /* 在有序單鏈表L中插入值為x的結(jié)點(diǎn)，插入后仍然有序 */LinkList *p,*q,*s; s=( LinkList *)malloc(sizeof(LinkList); /* 建立待插入的結(jié)點(diǎn) */s->data=x;p=head;q=p->next; /* q指向p的后繼結(jié)點(diǎn) */while(q!=NULL && q->data<x) p=q; q=q->next;s->next=q; /*將s插入到p和q之間*/p->next=s;例3有兩個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表L1和L2

42、，編寫算法將鏈表L2鏈接到鏈表L1之后成為一個(gè)單循環(huán)鏈表。解決本題的具體方法是：如果在用頭指針指向的單循環(huán)鏈表上做這個(gè)操作，都需要先找到兩鏈表的尾指針，要找尾指針就必須遍歷整個(gè)鏈表，找到后將第二個(gè)鏈表的尾指針與第一個(gè)鏈表的頭結(jié)點(diǎn)鏈接起來，使之成為循環(huán)的鏈表。若在用尾指針指向的單循環(huán)鏈表上做這個(gè)操作，則只需修改指針，操作過程如圖2.13所示。其算法如下：a1a2anrear1a1a2anrear2圖2.13 兩單循環(huán)鏈表鏈接為一個(gè)單循環(huán)鏈表pqLinkList *InsertOrder(LinkList *rear1, Node *rear2) /* 在有序單鏈表L中插入值為x的結(jié)點(diǎn)，插入后仍然

43、有序 */LinkList *p = rear1->next; /*對(duì)應(yīng)圖2.13中的*/LinkList *q = rear2->next; /*對(duì)應(yīng)圖2.13中的*/rear1->next = q->next; /*對(duì)應(yīng)圖2.13中的*/rear2->next = p; /*對(duì)應(yīng)圖2.13中的*/free(q);return( rear2 );例4 有一個(gè)不帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，其中已知一結(jié)點(diǎn)的指針為p，編寫算法將p與其右邊的一個(gè)結(jié)點(diǎn)進(jìn)行交換。解決本題的具體方法是：利用雙向循環(huán)的特點(diǎn)先找到p結(jié)點(diǎn)的右邊結(jié)點(diǎn)q，然后將p與q進(jìn)行交換。其算法如下：void Swa

44、p(DLinkList *p) /* 將雙向循環(huán)鏈表的已知結(jié)點(diǎn)與其右邊結(jié)點(diǎn)互換 */DLinkList *q; q=p->next;if(q=p) printf("只有一個(gè)結(jié)點(diǎn)，不能進(jìn)行交換！n");else p->next=q->next;p->next->prior=p;p->prior->next=q;q->prior=p->prior;p->prior=q;q->next=p;2.4 線性表的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的比較以上介紹了線性表的兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。下面我們從時(shí)間性能和空間性

45、能兩方面對(duì)兩種存儲(chǔ)結(jié)構(gòu)分別進(jìn)行比較。（1）時(shí)間性能的比較順序表是利用內(nèi)存中的一片起始位置確定的連續(xù)存儲(chǔ)區(qū)域來存放線性表中的所有元素，它的特點(diǎn)是邏輯上相鄰的數(shù)據(jù)元素，其物理存儲(chǔ)位置也是相鄰的。它是一種隨機(jī)存取結(jié)構(gòu)，存取速度快，存取表中任一元素都可以通過計(jì)算直接得到地址進(jìn)行存取，與元素的位置和表長n無關(guān)，時(shí)間復(fù)雜度為O(1)。而鏈表是用一組任意的存儲(chǔ)單元來依次存儲(chǔ)線性表中的各個(gè)數(shù)據(jù)元素，這些存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。為了能正確反映數(shù)據(jù)元素之間的邏輯關(guān)系，必須附加指針來表示。存取鏈表中的數(shù)據(jù)元素需要從頭指針起順著鏈掃描才能取得，與數(shù)據(jù)元素在表中所處的位置有關(guān)，時(shí)間復(fù)雜度為O(n)。因此

46、，若線性表上的操作主要是查找、求表長、讀取而很少做插入和刪除操作時(shí)，采用順序表結(jié)構(gòu)為宜。在順序表中進(jìn)行元素的插入和刪除時(shí)，平均要移動(dòng)近一半的元素，而在鏈表中插入和刪除元素只需要修改指針。因此，線性表上若頻繁進(jìn)行插入和刪除操作時(shí)，采用鏈表結(jié)構(gòu)為宜。（2）空間性能的比較順序表的存儲(chǔ)空間是靜態(tài)分配的，即在編譯時(shí)分配其存儲(chǔ)空間。順序表的最大長度很難確定，最大長度估計(jì)過小會(huì)出現(xiàn)表滿溢出，估計(jì)過大又會(huì)造成存儲(chǔ)空間的浪費(fèi)。而鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的，即在運(yùn)行時(shí)分配，只要內(nèi)存空間有空閑，操作系統(tǒng)就會(huì)給它分配。因此，在線性表的長度變化較大，頻繁進(jìn)行插入和刪除操作，在表長難以確定的情況下，最好采用鏈表作為存儲(chǔ)結(jié)

47、構(gòu)。鏈表的存儲(chǔ)空間利用率不高。線性表的存儲(chǔ)空間利用率可以用存儲(chǔ)密度來衡量。存儲(chǔ)密度定義為線性表中的數(shù)據(jù)元素本身所占的存儲(chǔ)量和整個(gè)線性表結(jié)構(gòu)所占的存儲(chǔ)量之比。顯然，順序表的存儲(chǔ)密度為1，由于鏈表中的結(jié)點(diǎn)除了數(shù)據(jù)域外還要有存放后繼結(jié)點(diǎn)地址的鏈域，所以鏈表的存儲(chǔ)密度小于1。因此，當(dāng)線性表的長度變化不大，順序表的最大長度很容易確定時(shí)，采用順序存儲(chǔ)結(jié)構(gòu)比較節(jié)省存儲(chǔ)空間?？傊?，實(shí)際應(yīng)用中選用哪種存儲(chǔ)結(jié)構(gòu)要根據(jù)具體問題的要求綜合平衡來選擇。2.5 線性表的應(yīng)用本節(jié)以一元多項(xiàng)式相加作為線性表應(yīng)用的一個(gè)例子。數(shù)學(xué)上，一個(gè)一元多項(xiàng)式Pn（x）可按升冪寫成:Pn（x）=p0p1xp2x2Pnxn它由n+1個(gè)系數(shù)唯一

48、確定。因此，它可以用一個(gè)線性表P表示:P=（p0，p1，p2，Pn）每一項(xiàng)的指數(shù)i隱含在其系數(shù)Pi的序號(hào)里。一般情況下，多項(xiàng)式的次數(shù)很高且變化很大，例如多項(xiàng)式A（x）=12x1003x10004x10000如果用上述方法表示則線性表有10001個(gè)元素，但是卻只有四個(gè)非零元素，浪費(fèi)了大量的存儲(chǔ)空間。在這種情況下，可用系數(shù)和指數(shù)的組合表示多項(xiàng)式的一個(gè)項(xiàng)，則多項(xiàng)式A（x）可表示成如下線性表的形式：A（1，0），（2，100），（3，1000），（4，10000）至于線性表的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)還是鏈接存儲(chǔ)結(jié)構(gòu)，要視其作何種運(yùn)算以及是否有利于這種運(yùn)算的實(shí)現(xiàn)而定。如只對(duì)多項(xiàng)式求值，由于不會(huì)改變多項(xiàng)式的

49、系數(shù)和指數(shù)，用順序表即可。如需對(duì)多項(xiàng)式作求和運(yùn)算，則插入、刪除操作不可避免，而且線性表的長度變化比較大，故宜用鏈表結(jié)構(gòu)。多項(xiàng)式A（x）用帶頭結(jié)點(diǎn)的單鏈表表示如圖2.14所示。2100head頭結(jié)點(diǎn)1031000410000圖2.14 多項(xiàng)式的單鏈表表示多項(xiàng)式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)描述如下：typedef struct pnode /* 多項(xiàng)式結(jié)點(diǎn)結(jié)構(gòu) */float coef; /*表示多項(xiàng)式的系數(shù)*/int exp; /*表示多項(xiàng)式的指數(shù)*/struct pnode *next; *Poly;對(duì)兩個(gè)多項(xiàng)式A和B相加，按照多項(xiàng)式相加的原則，我們可以這樣實(shí)現(xiàn)多項(xiàng)式加法運(yùn)算：設(shè)指針p,q分別指向多項(xiàng)式A和

50、多項(xiàng)式B中當(dāng)前進(jìn)行比較的某個(gè)結(jié)點(diǎn)，則比較兩個(gè)結(jié)點(diǎn)中的exp指數(shù)域，有下列三種情況:p->exp<q->exp，*p應(yīng)為多項(xiàng)式的一項(xiàng)；p->exp=q->exp，則將兩個(gè)結(jié)點(diǎn)中的系數(shù)相加，若相加為零，則釋放指針p和q所指結(jié)點(diǎn)，否則修改*p結(jié)點(diǎn)的coef系數(shù)域，并釋放指針q所指結(jié)點(diǎn)；p->exp > q->exp，*q 應(yīng)為多項(xiàng)式的一項(xiàng)，把*q插入到*p之前。操作過程如圖2.15所示。其算法如下：Poly PolyAdd(Poly pa, Poly pb) /* 求兩多項(xiàng)式之和，多項(xiàng)式用帶頭結(jié)點(diǎn)的單鏈表表示，pa,pb為頭指針 */Poly p,q,

51、r,s;int x;p=pa->next;r=pa; /* r為p的前驅(qū)指針 */q=pb->next; free(pb);while(p!=NULL && q!=NULL)if(p->exp<q->exp) /* 指針順鏈向后移動(dòng) */r=p; p=p->next;else if (p->exp=q->exp) x=p->coef+q->coef;if (x=0) r->next=p->next; free(p); /* 釋放p所指結(jié)點(diǎn) */else p->coef=x; r=p;p=r->next;s=q->next; /* s為輔助指針，指向q的后繼結(jié)點(diǎn) */free(q); /* 釋放q所指結(jié)點(diǎn) */q=s;else /