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

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

2、線性表形式La=（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; /作者名稱.;2.1.2 線性表的抽象數(shù)據(jù)類型描述ADT List數(shù)據(jù)對象：Dai| 1=i=0, ai屬ElemType類型數(shù)據(jù)關系：R1=| ai,ai+1D,i=1,n-1基本運算：（略介紹

3、）（1）初始化線性表L InitList(L) （2）銷毀線性表L DestoryList(L) （3）清空線性表L ClearList(L) （4）求線性表L的長度 ListLength(L)（5）判斷線性表L是否為空 IsEmpty(L) （6）獲取線性表L中的某個數(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中插入一個數(shù)據(jù)元素 ListInsert(L,i,e)（11）刪除線性表L

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

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

6、法實現(xiàn)：（1）初始化線性表Lvoid InitList(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) /*判斷表是

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

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

9、L-elementsi=x; L-last=L-last+1;return true;（9）將線性表L中第i個數(shù)據(jù)元素刪除int Dlete(SqList *L,int i) /*刪除線性表L中第i（0IL.last）個數(shù)據(jù)元素*/int k;if( i=L-last ) /* 下標越界 */ return ERROR;else /* 移動后面的元素 */ for(k=i;klast;k+) L-elementsk= L-elementsk+1; L-last-;return true;插入算法的分析：設Pi是在第i個元素之前插入一個元素的概率，假定在順序表中任何位置插入元素的機會相等，即設P

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

11、素，只保留序號最小的一個。解：具體的算法實現(xiàn)思路是：從順序表中依次取出每一個元素ai，并檢查ai+1到an-1中是否有元素與ai值相等，有就刪除重復元素。void ClearList(SqList *L) /* 清除順序表中的重復數(shù)據(jù)元素 */int i = 0, j;while( i last ) j = i + 1;while(jlast) /* 找重復數(shù)據(jù)元素并刪除 */if( L-elementsi = L-elementsj ) Dlete(L,j); /* 下一個元素自動向前移動過來 */else j+; /* 指針向下移動一個位置 */ i+; 2.3 線性表的鏈式存儲結(jié)構(gòu)2.3

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

13、的信息。假設有一個線性表（a,b,c,d），可用下圖所示的形式存儲：可以形象地描述為：abcdhead鏈式存儲結(jié)構(gòu)的特點：（1）線性表中的數(shù)據(jù)元素在存儲單元中的存放順序與邏輯順序不一定一致；（2）在對線性表操作時，只能通過頭指針進入鏈表，并通過每個結(jié)點的指針域向后掃描其余結(jié)點，這樣就會造成尋找第一個結(jié)點和尋找最后一個結(jié)點所花費的時間不等，具有這種特點的存取方式被稱為順序存取方式。用C語言描述單鏈表的結(jié)點結(jié)構(gòu)如下：typedef struct node /* 單鏈表結(jié)點結(jié)構(gòu) */DataType data; /*DataType可以是任何相應的數(shù)據(jù)類型如int,char等*/struct nod

14、e *next; LinkList;2.3.2 典型操作的算法實現(xiàn)（1）初始化鏈表Lvoid InitList1( LinkList *head ) /* 初始化不帶頭結(jié)點的鏈表頭指針 */*head = NULL;（2）銷毀鏈表L void DestoryList(LINK_LIST *L)LINKLIST *p;while (L-head) /依次刪除鏈表中的所有結(jié)點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

15、-next; /p指向鏈表中頭結(jié)點后面的第一個結(jié)點L-head-next=p-next; /刪除p結(jié)點free(p); /釋放p結(jié)點占據(jù)的存儲空間（4）求鏈表L的長度int Length(LinkList *head)/* 在帶頭結(jié)點的單鏈表中求表的長度 */LinkList *p=head; int j=0;while (p-next!=NULL) j+;p=p-next; /* p右移一個結(jié)點 */return j;（5）判鏈表L空否。int IsEmpty(LINK_LIST L) if (L.head-next=NULL) return TRUE;else return FALSE;（

16、6）通過e返回鏈表L中第i個數(shù)據(jù)元素的內(nèi)容void GetElem(LINK_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個結(jié)點*e=p-elem; /將第i個結(jié)點的內(nèi)容賦給e指針所指向的存儲單元中（7）在鏈表L中檢索值為e的數(shù)據(jù)元素LinkList *LocateNode(LinkList *head, int x)/* 在帶頭結(jié)點的單鏈表中查找值為x的結(jié)點，找到返回結(jié)點指針，否則返回

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

18、*NextElem(LINK_LIST L,LINKLIST* e)LINKLIST *p;for(p=L.head-next;p&p!=e;p=p-next);if (p) p=p-next; return p;（10）在鏈表L中第i個數(shù)據(jù)元素之前插入數(shù)據(jù)元素e void AddHead1(LinkList *head, int x )/* 向頭指針為head的鏈表中插入一個結(jié)點，其值為x */LinkList *p;p=( LinkList *)malloc(sizeof(LinkList);p-data = x;p-next = *head;*head = p; /* 調(diào)整鏈表頭指針he

19、ad */（11）將鏈表L中第i個數(shù)據(jù)元素刪除，并將其內(nèi)容保存在e中。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; /*對應圖2.8 */p-next=q-next; /*對應圖2.8 */ free(q); /*對應圖2.8 */else printf(“結(jié)點未找到！n”);2.3.3 循環(huán)鏈表若將單鏈表中最后一個結(jié)點的指針指向鏈表的第一個

20、結(jié)點，那么整個鏈表就形成了一個環(huán)形結(jié)構(gòu)，故稱為單鏈形式的循環(huán)鏈表，并簡稱為單循環(huán)鏈表。（a） 非空循環(huán)鏈表heada1a2anhead頭結(jié)點(b) 空循環(huán)鏈表頭結(jié)點循環(huán)鏈表的特點：從表中任一結(jié)點出發(fā)均可訪問其他所有結(jié)點。實現(xiàn)循環(huán)鏈表的類型定義與單鏈表完全相同，它的所有操作也都與單鏈表類似。只是判斷鏈表結(jié)束的條件有所不同。2.3.4 雙向鏈表可以在單鏈表的每個結(jié)點內(nèi)再增加一個指向其直接前驅(qū)的鏈域，這樣形成的鏈表中就有兩條方向不同的鏈，故稱為雙向鏈表（Double linked list）。雙向鏈表的結(jié)點結(jié)構(gòu)C語言描述：typedef struct dnode /* 雙向鏈表結(jié)點結(jié)構(gòu) */Data

21、Type data; /*DataType可以是任何相應的數(shù)據(jù)類型如int,char等*/struct dnode *prior,*next; DLinkList;雙鏈表的*p結(jié)點之前插入值為x的結(jié)點插入的過程：pq對應算法如下：void InsertDNode(DLinkList *p, int x)/* 在雙鏈表的*p結(jié)點之前插入值為x的結(jié)點 */DLinkList *q; q=( DLinkList *)malloc(sizeof(DLinkList);q-data=x;q-prior=p-prior; /*對應圖2.11 */q-next=p; /*對應圖2.11 */p-prior-

22、next=q; /*對應圖2.11 */p-prior=q; /*對應圖2.11 */在雙鏈表中刪除p指針指向的結(jié)點的過程：p對應算法如下：void DeleteDNode(DLinkList *p)/* 在雙鏈表中刪除p指針指向的結(jié)點 */p-prior-next=p-next; /*對應圖2.12 */p-next-prior=p-prior; /*對應圖2.12 */free(p);2.3.4 線性表的應用舉例例22 有一個不帶頭結(jié)點的單鏈表L（至少有1個結(jié)點），第一個結(jié)點指針為head，編寫算法將L逆置，即最后一個結(jié)點變成第一個結(jié)點，倒數(shù)第二個結(jié)點變成第二個結(jié)點，如此等等。解：逆置的方

23、法是：從頭到尾掃描單鏈表L，將第一個結(jié)點的next域設置為NULL，將第二個結(jié)點的next域指向第一個結(jié)點，將第三個結(jié)點的next域指向第二個結(jié)點，如此進行直到最后一個結(jié)點，用head指向它。其算法如下：void Invert1( LinkList *head ) /* 將不帶頭指針的單鏈表倒置 */LinkList *p = *head, *r;LinkList *q = NULL;/* q始終指向當前插入點 */while( p ) /* 還有剩余元素時 */r = p-next; /* r緩存下一個待插入元素指針 */p-next = q; /* 插入當前的待插元素到新表中 */q =

24、p; p = r; /* 調(diào)整 */*head = q;/* 更新頭指針 */例23 有兩個帶頭結(jié)點的單循環(huán)鏈表L1和L2，編寫算法將鏈表L2鏈接到鏈表L1之后成為一個單循環(huán)鏈表。解決本題的具體方法是：如果在用頭指針指向的單循環(huán)鏈表上做這個操作，都需要先找到兩鏈表的尾指針，要找尾指針就必須遍歷整個鏈表，找到后將第二個鏈表的尾指針與第一個鏈表的頭結(jié)點鏈接起來，使之成為循環(huán)的鏈表。若在用尾指針指向的單循環(huán)鏈表上做這個操作，則只需修改指針，操作過程如下圖所示。其算法如下：a1a2anrear1a1a2anrear2pqLinkList *InsertOrder(LinkList *rear1, No

25、de *rear2) /* 在有序單鏈表L中插入值為x的結(jié)點，插入后仍然有序 */LinkList *p = rear1-next; /*對應圖2.13中的*/LinkList *q = rear2-next; /*對應圖2.13中的*/rear1-next = q-next; /*對應圖2.13中的*/rear2-next = p; /*對應圖2.13中的*/free(q);return( rear2 );2.5 線性表的應用約瑟夫（Joseph）問題：編號為1，2，n的n個人按順時針方向圍坐在一張圓桌旁，每個人手中持有一個密碼（正整數(shù)）。首先輸入一個正整數(shù)作為報數(shù)上限值m，然后，從第一個人

26、開始按順時針方向自1開始順序報數(shù)，報到m的人離開桌旁，并將他手中的密碼作為新的m值，從順時針方向的下一個就坐在桌旁的人人開始重新從1報數(shù)，如此下去，直至所有人全部離開桌旁為止。 解： 假設有7個人，編號從1到7，他們手中的密碼分別是3，1，7，2，4，8，4，最初的m=2，通過報數(shù)，這7個人離開桌旁的順序應該是：2，3，5，4，7，6，1。數(shù)據(jù)結(jié)構(gòu)的分析：這個問題的主角是n個人，每個人需要描述的信息有：編號、密碼和是否在桌旁的狀態(tài)。假設有7個人，他們的信息可以表示成下面的形式。算法描述：讓n個人圍坐在一張圓桌旁；for (i=1;i=n;i+)從1開始報數(shù)，報到m停止；報到m的人離開桌子；代碼實現(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個人手中的密碼，n是開始就坐在桌旁的人數(shù) SqList pe