順序表示的棧和隊列必須預先分配空間并且空... -

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

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

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

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

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

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

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

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

9、 ERROR -1typedef struct /* 線性表定義 */int elementsMAXSIZE;int last; /* last為線性表的長度 */ SqList;定義了線性表的順序存儲結(jié)構(gòu)后，下面我們就在這種結(jié)構(gòu)的基礎(chǔ)之上討論如何實現(xià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ù)組的下標從"0"開始*/int LocateElem(SqList L,int x) /*定位函數(shù)。返回L中第1個與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）個數(shù)據(jù)元素之前插入一個數(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）個數(shù)據(jù)元素*/int k;if( i<0 | i>=L->last ) /* 下標越界 */ return ERROR;else /* 移動后面的元素 */ for(k=i;k<L->last;k+) L->elementsk= L->elementsk+1; L->last-;return true;void Clear(SqList *L) /* 清空線性表L */InitList( L );對于插入和刪除兩個算法，其算法執(zhí)行的時間都主要花費在元素的移動上。

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

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

15、a和lb中i、j所指的數(shù)據(jù)元素進行比較，當la的元素不大于lb的元素時，將la的當前元素放入lc中，同時i，k指針增1，否則將lb的當前元素放入lc中，同時j，k指針增1。對應(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中的當前元素相等時，同時移動指針 */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 清除順序表中的重復數(shù)據(jù)元素。例如，順序表（2，3，3，4，3，5，4）清除后變?yōu)椋?，3，4，5）。清除重復元素是指刪除重復元素，只保留序號最小的一個。具體的算法實現(xiàn)思路是：從順序表中依次取出每一個元素ai，并檢查ai+1到an-1中是否有元素與ai值相等，有就刪除重復元素。void ClearList(SqList *L) /* 清除順序表中的重復數(shù)據(jù)元素 */int i = 0, j;while( i < L->last ) j = i + 1;while(j<=L->last) /* 找重復數(shù)據(jù)元素并刪除 */if

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

44、p(DLinkList *p) /* 將雙向循環(huán)鏈表的已知結(jié)點與其右邊結(jié)點互換 */DLinkList *q; q=p->next;if(q=p) printf("只有一個結(jié)點，不能進行交換！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 線性表的順序和鏈式存儲結(jié)構(gòu)的比較以上介紹了線性表的兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。下面我們從時間性能和空間性

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

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

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

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

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

50、多項式B中當前進行比較的某個結(jié)點，則比較兩個結(jié)點中的exp指數(shù)域，有下列三種情況:p->exp<q->exp，*p應(yīng)為多項式的一項；p->exp=q->exp，則將兩個結(jié)點中的系數(shù)相加，若相加為零，則釋放指針p和q所指結(jié)點，否則修改*p結(jié)點的coef系數(shù)域，并釋放指針q所指結(jié)點；p->exp > q->exp，*q 應(yīng)為多項式的一項，把*q插入到*p之前。操作過程如圖2.15所示。其算法如下：Poly PolyAdd(Poly pa, Poly pb) /* 求兩多項式之和，多項式用帶頭結(jié)點的單鏈表表示，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) /* 指針順鏈向后移動 */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é)點 */else p->coef=x; r=p;p=r->next;s=q->next; /* s為輔助指針，指向q的后繼結(jié)點 */free(q); /* 釋放q所指結(jié)點 */q=s;else /