本章主要介紹下列內(nèi)容1、線性表及其邏輯結(jié)構(gòu);2、線性表的順序

1、本章主要介紹下列內(nèi)容：1、線性表及其邏輯結(jié)構(gòu)；2、線性表的順序存儲結(jié)構(gòu)；3、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)；4、線性表的應(yīng)用舉例課時(shí)分配：1、2占2學(xué)時(shí)，3占2學(xué)時(shí), 4占2學(xué)時(shí)，上機(jī)2學(xué)時(shí)重點(diǎn)、難點(diǎn)：線性表的順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、循環(huán)鏈表 線性表及其邏輯結(jié)構(gòu) 線性表的定義線性表是由n（n0）個(gè)類型相同的數(shù)據(jù)元素組成的有限序列。通常表示成下列形式：L=( a1, a2,.,ai-1,ai,ai+1,.,an)其中：L為線性表名稱，習(xí)慣用大寫書寫；ai為組成該線性表的數(shù)據(jù)元素，習(xí)慣用小寫書寫；線性表中數(shù)據(jù)元素的個(gè)數(shù)被稱為線性表的長度，當(dāng)n=0時(shí)，線性表為空，又稱為空線性表。例2-1 線性表形式La=

2、（34，89，765，12，90，-34，22） 數(shù)據(jù)元素類型為int。Ls=(“Hello”,“World”, “China”, “Welcome”) 數(shù)據(jù)元素類型為string。Lb=(book1,book2,.,book100) 數(shù)據(jù)元素類型為下列所示的結(jié)構(gòu)類型：struct bookinfoint No; /圖書編號char *name; /圖書名稱char *author; /作者名稱.; 線性表的抽象數(shù)據(jù)類型描述ADT List數(shù)據(jù)對象：Dai| 1=i=0, ai屬ElemType類型數(shù)據(jù)關(guān)系：R1=| ai,ai+1D,i=1,n-1基本運(yùn)算：（略介紹）（1）初始化線性表L I

3、nitList(L) （2）銷毀線性表L DestoryList(L) （3）清空線性表L ClearList(L) （4）求線性表L的長度 ListLength(L)（5）判斷線性表L是否為空 IsEmpty(L) （6）獲取線性表L中的某個(gè)數(shù)據(jù)元素內(nèi)容 GetElem(L,i,e) （7）檢索值為e的數(shù)據(jù)元素 LocateELem(L,e) （8）返回線性表L中e的直接前驅(qū)元素 PriorElem(L,e) （9）返回線性表L中e的直接后繼元素 NextElem(L,e) （10）在線性表L中插入一個(gè)數(shù)據(jù)元素 ListInsert(L,i,e)（11）刪除線性表L中第i個(gè)數(shù)據(jù)元素 List

4、Delete(L,i,e) 線性表的順序存儲結(jié)構(gòu) 線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)是指用一組連續(xù)的存儲單元依次存儲線性表中的每個(gè)數(shù)據(jù)元素，也稱為順序表。如下圖所示： 其中，L為每個(gè)數(shù)據(jù)元素所占據(jù)的存儲單元數(shù)目。相鄰兩個(gè)數(shù)據(jù)元素的存儲位置計(jì)算公式：LOC(ai+1)=LOC(ai)+L線性表中任意一個(gè)數(shù)據(jù)元素的存儲位置的計(jì)算公式為：LOC(ai+1)=LOC(a1)+(i-1)*L順序存儲結(jié)構(gòu)的特點(diǎn)：（1）利用數(shù)據(jù)元素的存儲位置表示線性表中相鄰數(shù)據(jù)元素之間的前后關(guān)系，即線性表的邏輯結(jié)構(gòu)與存儲結(jié) 構(gòu)（物理結(jié)構(gòu)）一致；（2）在訪問線性表時(shí)，可以利用上述給出的數(shù)學(xué)公式，快速地計(jì)算出任何一個(gè)數(shù)據(jù)

5、元素的存儲地址。因此，我們可以粗略地認(rèn)為，訪問每個(gè)數(shù)據(jù)元素所花費(fèi)的時(shí)間相等。這種存取元素的方法被稱為隨機(jī)存取法，使用這種存取方法的存儲結(jié)構(gòu)被稱為隨機(jī)存儲結(jié)構(gòu)。在C語言中，實(shí)現(xiàn)線性表的順序存儲結(jié)構(gòu)的類型定義：#define MAXSIZE 100 /* MAXSIZE 為線性表可能的最大長度 */#define ERROR -1typedef struct /* 線性表定義 */int elementsMAXSIZE;int last; /* last為線性表的長度 */ SqList; 注：為幫助學(xué)生考研，上課講解用指針形式。 典型操作的算法實(shí)現(xiàn)：（1）初始化線性表Lvoid InitList

6、(SqList *L) /*初始化操作，將線性表L置空*/L-last = 0;（2）銷毀線性表Lvoid DestroyList(SqList *L) if (L-elem) free(L-elem); /釋放線性表占據(jù)的所有存儲空間（3）清空線性表Lvoid Clear(SqList *L) /* 清空線性表L */InitList( L );（4）求線性表L的長度int GetLength(SEQLIST L) return (L.length); （5）判斷線性表L是否為空bool IsEmpty( SqList L) /*判斷表是否為空。如果L是空表，返回true，否則返回false

7、*/if( L.last = 0 ) return true;else return false;（6）獲取線性表L中的某個(gè)數(shù)據(jù)元素的內(nèi)容int GetElem(SqList L,int i) /* 取表中第i元素。*/if(i=L.last) return ERROR;else return L.elementsi; /*C語言中數(shù)組的下標(biāo)從0開始*/（7）在線性表L中檢索值為e的數(shù)據(jù)元素int LocateElem(SqList L,int x) /*定位函數(shù)。返回L中第1個(gè)與x相等的數(shù)據(jù)元素的位置（從0算起）。*/ /*否則返回值為0。*/int k; k=0; while (kL.la

8、st & L.elementsk!=x) k+; if(kL.last) return k; else return ERROR;（8）在線性表L中第i個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素e int Insert(SqList *L,int x,int i) /*在線性表L中第i（0iL.last）個(gè)數(shù)據(jù)元素之前插入一個(gè)數(shù)據(jù)元素x*/int k; if(iL-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-las

9、t+1;return true;（9）將線性表L中第i個(gè)數(shù)據(jù)元素刪除int Dlete(SqList *L,int i) /*刪除線性表L中第i（0IL.last）個(gè)數(shù)據(jù)元素*/int k;if( i=L-last ) /* 下標(biāo)越界 */ return ERROR;else /* 移動(dòng)后面的元素 */ for(k=i;klast;k+) L-elementsk= L-elementsk+1; L-last-;return true;插入算法的分析：設(shè)Pi是在第i個(gè)元素之前插入一個(gè)元素的概率，假定在順序表中任何位置插入元素的機(jī)會相等，即設(shè)Pi，則在長度為n的線性表中插入一個(gè)元素時(shí)所需移動(dòng)元素的

10、平均次數(shù)為E（n）=刪除算法的分析：設(shè)qi是刪除第i個(gè)元素的概率，假定在順序表中刪除元素的機(jī)會相等，即設(shè)qi，則在長度為n的線性表中刪除一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為E（n）=結(jié)論：在順序表中插入或刪除一個(gè)數(shù)據(jù)元素，平均大約移動(dòng)表中一半元素。當(dāng)線性表的長度較大，且插入和刪除操作的頻度較高時(shí)，則花費(fèi)時(shí)間較多，不宜采用順序存儲結(jié)構(gòu)。但是順序表存儲結(jié)構(gòu)簡單，便于順序存儲，存儲空間的利用率高。順序表應(yīng)用舉例：例21 清除順序表中的重復(fù)數(shù)據(jù)元素。例如，順序表（2，3，3，4，3，5，4）清除后變?yōu)椋?，3，4，5）。注：清除重復(fù)元素是指刪除重復(fù)元素，只保留序號最小的一個(gè)。解：具體的算法實(shí)現(xiàn)思路是：從

11、順序表中依次取出每一個(gè)元素ai，并檢查ai+1到an-1中是否有元素與ai值相等，有就刪除重復(fù)元素。void ClearList(SqList *L) /* 清除順序表中的重復(fù)數(shù)據(jù)元素 */int i = 0, j;while( i last ) j = i + 1;while(jlast) /* 找重復(fù)數(shù)據(jù)元素并刪除 */if( L-elementsi = L-elementsj ) Dlete(L,j); /* 下一個(gè)元素自動(dòng)向前移動(dòng)過來 */else j+; /* 指針向下移動(dòng)一個(gè)位置 */ i+; 2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈表線性表順序存儲結(jié)構(gòu)的特點(diǎn)： （1）

12、 簡單、方便，要求表中數(shù)據(jù)元素依次存放在連續(xù)的存儲單元中，利用數(shù)據(jù)元素的存儲順序表示相應(yīng)的邏輯順序，屬于靜態(tài)存儲形式；（2） 在做插入或刪除元素的操作時(shí)，會產(chǎn)生大量的數(shù)據(jù)元素移動(dòng)；（3） 對于長度變化較大的線性表，要一次性地分配足夠的存儲空間，但這些空間常常又得不到充分的利用；（4） 線性表的容量難以擴(kuò)充。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指用一組任意的存儲單元（可以連續(xù)，也可以不連續(xù)）存儲線性表中的數(shù)據(jù)元素。為了反映數(shù)據(jù)元素之間的邏輯關(guān)系，對于每個(gè)數(shù)據(jù)元素不僅要表示它的具體內(nèi)容，還要附加一個(gè)表示它的直接后繼元素存儲位置的信息。假設(shè)有一個(gè)線性表（a,b,c,d），可用下圖所示的形式存

13、儲：可以形象地描述為：abcdhead鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)：（1）線性表中的數(shù)據(jù)元素在存儲單元中的存放順序與邏輯順序不一定一致；（2）在對線性表操作時(shí)，只能通過頭指針進(jìn)入鏈表，并通過每個(gè)結(jié)點(diǎn)的指針域向后掃描其余結(jié)點(diǎn)，這樣就會造成尋找第一個(gè)結(jié)點(diǎn)和尋找最后一個(gè)結(jié)點(diǎn)所花費(fèi)的時(shí)間不等，具有這種特點(diǎn)的存取方式被稱為順序存取方式。用C語言描述單鏈表的結(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; 典型操作的算法實(shí)現(xiàn)（1）初

14、始化鏈表Lvoid InitList1( LinkList *head ) /* 初始化不帶頭結(jié)點(diǎn)的鏈表頭指針 */*head = NULL;（2）銷毀鏈表L void DestoryList(LINK_LIST *L)LINKLIST *p;while (L-head) /依次刪除鏈表中的所有結(jié)點(diǎn)p=L-head; L-head=L-head-next;free(p);（3）清空鏈表L void ClearList(LINK_LIST *L)LINKLIST *p;while (L-head-next)p=L-head-next; /p指向鏈表中頭結(jié)點(diǎn)后面的第一個(gè)結(jié)點(diǎn)L-head-next=

15、p-next; /刪除p結(jié)點(diǎn)free(p); /釋放p結(jié)點(diǎn)占據(jù)的存儲空間（4）求鏈表L的長度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;（5）判鏈表L空否。int IsEmpty(LINK_LIST L) if (L.head-next=NULL) return TRUE;else return FALSE;（6）通過e返回鏈表L中第i個(gè)數(shù)據(jù)元素的內(nèi)容void GetElem(LIN

16、K_LIST L,int i,Elemtype *e) LINKLIST *p;int j;if (iListLength(L) exit ERROR; /檢測i值的合理性for (p=L.head,j=0; j!=i;p=p-next,j+); /找到第i個(gè)結(jié)點(diǎn)*e=p-elem; /將第i個(gè)結(jié)點(diǎn)的內(nèi)容賦給e指針?biāo)赶虻拇鎯卧校?）在鏈表L中檢索值為e的數(shù)據(jù)元素LinkList *LocateNode(LinkList *head, int x)/* 在帶頭結(jié)點(diǎn)的單鏈表中查找值為x的結(jié)點(diǎn)，找到返回結(jié)點(diǎn)指針，否則返回NULL */LinkList *p = head-next;while(

17、 p & p-data != x ) p=p-next;return p;（8）返回鏈表L中結(jié)點(diǎn)e的直接前驅(qū)結(jié)點(diǎn)LINKLIST *PriorElem(LINK_LIST L,LINKLIST* e)LINKLIST *p;if (L.head-next=e) return NULL; /檢測第一個(gè)結(jié)點(diǎn)for (p=L.head;p-next&p-next!=e;p=p-next); if (p-next=e) return p;esle return NULL; （9）返回鏈表L中結(jié)點(diǎn)e的直接后繼結(jié)點(diǎn)LINKLIST *NextElem(LINK_LIST L,LINKLIST* e)LIN

18、KLIST *p;for(p=L.head-next;p&p!=e;p=p-next);if (p) p=p-next; return p;（10）在鏈表L中第i個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素e void AddHead1(LinkList *head, int x )/* 向頭指針為head的鏈表中插入一個(gè)結(jié)點(diǎn)，其值為x */LinkList *p;p=( LinkList *)malloc(sizeof(LinkList);p-data = x;p-next = *head;*head = p; /* 調(diào)整鏈表頭指針head */（11）將鏈表L中第i個(gè)數(shù)據(jù)元素刪除，并將其內(nèi)容保存在e中。vo

19、id 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; /*對應(yīng)圖2.8 */p-next=q-next; /*對應(yīng)圖2.8 */ free(q); /*對應(yīng)圖2.8 */else printf(“結(jié)點(diǎn)未找到！n”); 循環(huán)鏈表若將單鏈表中最后一個(gè)結(jié)點(diǎn)的指針指向鏈表的第一個(gè)結(jié)點(diǎn)，那么整個(gè)鏈表就形成了一個(gè)環(huán)形結(jié)構(gòu)，故稱為單鏈形式的循環(huán)鏈表，并簡稱為單循環(huán)鏈表

20、。（a） 非空循環(huán)鏈表heada1a2anhead頭結(jié)點(diǎn)(b) 空循環(huán)鏈表頭結(jié)點(diǎn)循環(huán)鏈表的特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可訪問其他所有結(jié)點(diǎn)。實(shí)現(xiàn)循環(huán)鏈表的類型定義與單鏈表完全相同，它的所有操作也都與單鏈表類似。只是判斷鏈表結(jié)束的條件有所不同。 雙向鏈表可以在單鏈表的每個(gè)結(jié)點(diǎn)內(nèi)再增加一個(gè)指向其直接前驅(qū)的鏈域，這樣形成的鏈表中就有兩條方向不同的鏈，故稱為雙向鏈表（Double linked list）。雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)C語言描述：typedef struct dnode /* 雙向鏈表結(jié)點(diǎn)結(jié)構(gòu) */DataType data; /*DataType可以是任何相應(yīng)的數(shù)據(jù)類型如int,char等*/st

21、ruct dnode *prior,*next; DLinkList;雙鏈表的*p結(jié)點(diǎn)之前插入值為x的結(jié)點(diǎn)插入的過程：pq對應(yīng)算法如下：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; /*對應(yīng)圖2.11 */q-next=p; /*對應(yīng)圖2.11 */p-prior-next=q; /*對應(yīng)圖2.11 */p-prior=q; /*對應(yīng)圖2.11 */在雙鏈表

22、中刪除p指針指向的結(jié)點(diǎn)的過程：p對應(yīng)算法如下：void DeleteDNode(DLinkList *p)/* 在雙鏈表中刪除p指針指向的結(jié)點(diǎn) */p-prior-next=p-next; /*對應(yīng)圖2.12 */p-next-prior=p-prior; /*對應(yīng)圖2.12 */free(p); 線性表的應(yīng)用舉例例22 有一個(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é)

23、點(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始終指向當(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;/* 更新頭指針 */例23 有兩個(gè)帶頭結(jié)點(diǎn)的單

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

25、e(q);return( rear2 );2.5 線性表的應(yīng)用約瑟夫（Joseph）問題：編號為1，2，n的n個(gè)人按順時(shí)針方向圍坐在一張圓桌旁，每個(gè)人手中持有一個(gè)密碼（正整數(shù)）。首先輸入一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，然后，從第一個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m的人離開桌旁，并將他手中的密碼作為新的m值，從順時(shí)針方向的下一個(gè)就坐在桌旁的人人開始重新從1報(bào)數(shù)，如此下去，直至所有人全部離開桌旁為止。 解： 假設(shè)有7個(gè)人，編號從1到7，他們手中的密碼分別是3，1，7，2，4，8，4，最初的m=2，通過報(bào)數(shù)，這7個(gè)人離開桌旁的順序應(yīng)該是：2，3，5，4，7，6，1。數(shù)據(jù)結(jié)構(gòu)的分析：這個(gè)問題的主

26、角是n個(gè)人，每個(gè)人需要描述的信息有：編號、密碼和是否在桌旁的狀態(tài)。假設(shè)有7個(gè)人，他們的信息可以表示成下面的形式。算法描述：讓n個(gè)人圍坐在一張圓桌旁；for (i=1;i=n;i+)從1開始報(bào)數(shù)，報(bào)到m停止；報(bào)到m的人離開桌子；代碼實(shí)現(xiàn)一（順序存儲方式）：#define LIST_MAX_LENGTH 7#define n LIST_MAX_LENGTHtypedef int Elemtype; /將Elemtype定義為int類型void Joseph(int code,int n) /通過一維數(shù)組code帶入n個(gè)人手中的密碼，n是開始就坐在桌旁的人數(shù) SqList people; int temp,m;