數(shù)據(jù)結(jié)構(gòu)-第2章-線性表

2.1線性表的基本概念第2章線性表線性表（linear-list）是一組具有相同特征的數(shù)據(jù)元素的有限序列。如，某校十個教學(xué)班級的學(xué)生人數(shù)（50，53，55，52，56，59，60，55，57，51）構(gòu)成一個線性表。線性表可用一個標示符來命名。如用List來命名上述線性表，則可表示為：List=（50，53，55，52，56，59，60，55，57，51）線性表中所包含的數(shù)據(jù)元素的個數(shù)稱為線性表的長度，可用n表示。n=0表示線性表為空，稱為空表。線性表中的數(shù)據(jù)元素可分別用a1，a2，a3，……ai，……an表示。其中a1是第一個數(shù)據(jù)元素，an是最后一個數(shù)據(jù)元素，每個數(shù)據(jù)元素在表中都有一個唯一確定的位置，可用下標i表示第i個數(shù)據(jù)元素在表中的位置。2.1線性表的基本概念第2章線性表2.1.1線性表的定義線性表（linear-list）是一組具有相同特征的數(shù)據(jù)元素的有限序列。如，某校十個教學(xué)班級的學(xué)生人數(shù)（50，53，55，52，56，59，60，55，57，51）構(gòu)成一個線性表。線性表可用一個標示符來命名。如用List來命名上述線性表，則可表示為：List=（50，53，55，52，56，59，60，55，57，51）線性表中所包含的數(shù)據(jù)元素的個數(shù)稱為線性表的長度，可用n表示。n=0表示線性表為空，稱為空表。2.1線性表的基本概念第2章線性表2.1.2線性表的特點線性表是一種線性結(jié)構(gòu)，其中的數(shù)據(jù)元素有序且有限。一個非空的線性表具有如下特點：有且僅有一個開始數(shù)據(jù)元素，該元素沒有前驅(qū)；有且僅有一個終端數(shù)據(jù)元素，該元素沒有后繼；

除開始數(shù)據(jù)元素外，其它的數(shù)據(jù)元素有且僅有一個直接前驅(qū)；

除終端數(shù)據(jù)元素外，其它的數(shù)據(jù)元素有且僅有一個直接后繼。2.1線性表的基本概念第2章線性表2.1.3線性表的抽象數(shù)據(jù)類型

線性表的抽象數(shù)據(jù)類型定義如下：ADTList

{

定義：一組具有相同特征的數(shù)據(jù)元素的有限序列

表示：List=（a1，a2，a3，……ai，……an）

基本操作：

Initiate（List）

操作結(jié)果：初始化操作。置一個空的線性表List。

ClearList（List）

初始條件：線性表List存在。

操作結(jié)果：將線性表List置為空表。

2.1線性表的基本概念第2章線性表ListEmpty（List）

初始條件：線性表List存在。

操作結(jié)果：若線性表List為空，則返回true；否則返回false。Length（List）

初始條件：線性表List存在。

操作結(jié)果：返回線性表List的長度，若為空，則返回0。

Get（List，i，e）

初始條件：線性表List存在，1≤i≤Length（List）。

操作結(jié)果：返回線性表List的第i個數(shù)據(jù)元素，由e返回。

Find（List，i，e）

初始條件：線性表List存在。

操作結(jié)果：返回線性表List中第一個值為e的數(shù)據(jù)元素的位置（第

幾個元素），值由i返回。若沒有找到，則返回-1。2.1線性表的基本概念第2章線性表

Insert（List，i，e）

初始條件：線性表List存在，1≤i≤Length（List）+1。

操作結(jié)果：在線性表List的第i個位置插入元素e，線性表長度加1。

Delete（List，i）

初始條件：線性表List存在，1≤i≤Length（List）。

操作結(jié)果：刪除線性表List第i個位置上的數(shù)據(jù)元素，線性表長度減1。

GetPrior（List，e，pre_e）

初始條件：線性表List存在。

操作結(jié)果：若e是線性表List中的數(shù)據(jù)元素，且不是第一個數(shù)據(jù)元素，

則用&pre_e返回e的前驅(qū)；否則返回NULL。

GetNext（List，e，next_e）

初始條件：線性表List存在。

操作結(jié)果：若e是線性表中List的數(shù)據(jù)元素，且不是最后一個數(shù)據(jù)元素，

則用&next_e返回e的后繼；否則返回NULL。

2.2線性表的順序存儲和操作實現(xiàn)第2章線性表2.2.1線性表為了用計算機處理線性表，必須為它選擇合適的存儲結(jié)構(gòu)。線性表的存儲結(jié)構(gòu)有順序、鏈式、索引、散列等多種方式，其中順序存儲和鏈式存儲是兩種最簡單常用的存儲結(jié)構(gòu)。本小節(jié)主要介紹線性表的順序存儲和相關(guān)操作。線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表中的每一個數(shù)據(jù)元素。2.2線性表的順序存儲和操作實現(xiàn)第2章線性表2.2.1線性表采用順序存儲結(jié)構(gòu)的線性表稱為順序表。其特點是：

線性表的邏輯順序與物理順序一致；線性表的數(shù)據(jù)元素之間的關(guān)系可以通過物理存儲之間的相鄰關(guān)系來體現(xiàn)；

假設(shè)順序表中第一個數(shù)據(jù)元素的存儲位置為LOC(a1)，每一個數(shù)據(jù)元素占用的存儲單元數(shù)為c，則第i個數(shù)據(jù)元素的存儲位置為：LOC(ai)=LOC(a1)+(i-1)*c2.2線性表的順序存儲和操作實現(xiàn)第2章線性表2.2.2線性表的基本操作

1.初始化順序表動態(tài)分配存儲空間，并把順序表置為空。StatusInitiate_Sq(SqList*L){L->list=(ElemType*)malloc(LIST_SIZE*sizeof(ElemType));

/*分配內(nèi)存單元*/if(!L->list){ printf(“Memoryallocatefailed!\n”);

returnERROR;}L->length=0; /*空表長度為0*/L->list_size=LIST_SIZE; /*初始存儲容量*/returnOK;}2.2線性表的順序存儲和操作實現(xiàn)第2章線性表

2.清除順序表中所有元素，并將順序表置為空voidClearList_Sq(SqList*L){if(L->list){

free(L->list); /*釋放順序表空間*/

L->list=NULL;

L->length=0; /*空表長度為0*/

L->list_size=0;}}2.2線性表的順序存儲和操作實現(xiàn)第2章線性表9.遍歷順序表中的元素StatusTranverse_Sq(SqList*L){ intj; if(L->length<1) /*順序表為空*/ returnERROR; printf(“TheListis:\n”); for(j=0;j<=L->length–1;j++) printf(“l(fā)ist[%d]=%d\n”,j,L->list[j]);

/*此處設(shè)元素類型為整型*/ returnOK;}2.2線性表的順序存儲和操作實現(xiàn)第2章線性表【例2-1】已有一手機通訊錄，各聯(lián)系人信息按照姓名字母順序遞增的方式排列?，F(xiàn)需添加一聯(lián)系人信息，希望添加后各聯(lián)系人信息仍按照姓名字母順序遞增的方式排列設(shè)計思路：將手機通訊錄用線性表的結(jié)構(gòu)表示，采用順序存儲方式。即將其視為一個順序表。首先要判斷該順序表中是否還有剩余空間，如已存滿，則利用上述reallocate函數(shù)重新分配空間；然后在該順序表中從后往前尋找插入位置，將姓名字母比待插入聯(lián)系人姓名字母大（靠后）的記錄向后移動，然后插入新的聯(lián)系人信息。2.2線性表的順序存儲和操作實現(xiàn)第2章線性表程序描述如下：StatusInsert_Sq(SqList*L,ElemType*elem){ intj; if(L->length==L->list_size) /*是否還有剩余空間*/ if(reallocate(L)==ERROR) /*重新分配空間是否失敗*/returnERROR; for(j=L->length–1;j>=0;j--)/*元素（聯(lián)系人信息）后移*/ if(strcmp(L->list[j].name,elem->name)>0)memcpy(&L->list[j+1],&L->list[j],sizeof(ElemType)); else break;

/*將新元素放入順序表第i個位置處*/

memcpy(&L->list[j+1],elem,sizeof(ElemType));L->length++; /*順序表長度加1*/ returnOK;}2.3線性表的鏈式存儲和操作實現(xiàn)第2章線性表線性表的順序存儲只存儲數(shù)據(jù)元素本身的信息，數(shù)據(jù)元素之間的關(guān)系通過物理存儲之間的相鄰關(guān)系來體現(xiàn)，可以實現(xiàn)隨機存取，但也存在插入、刪除操作不方便等缺點。而線性表的鏈式存儲通過同時存儲數(shù)據(jù)元素本身的信息和自己的直接后繼（或直接前驅(qū)）的存儲位置，把所有的數(shù)據(jù)元素鏈接起來，克服了順序存儲的缺點。在鏈式存儲中，這兩部分信息組成的數(shù)據(jù)元素ai的存儲映像，稱為結(jié)點（Node）。其中存儲數(shù)據(jù)元素本身信息的部分稱為數(shù)據(jù)域；存儲其直接后繼（或直接前驅(qū)）的存儲位置信息的部分稱為指針域。指針域中存儲的信息可以稱為指針或鏈。如圖所示。2.3線性表的鏈式存儲和操作實現(xiàn)第2章線性表2.3.1單鏈表1.基本概念每個節(jié)點只包含一個指針域的鏈表稱為單鏈表，也稱為線性鏈表。一般所講到的單鏈表，每個結(jié)點的指針域均指向其后繼結(jié)點，最后一個結(jié)點的指針域為空，用“^”表示。一般用圖所示的形式表示。單鏈表2.3線性表的鏈式存儲和操作實現(xiàn)第2章線性表2.存儲結(jié)構(gòu) 單鏈表的結(jié)點主要有數(shù)據(jù)域和指針域兩部分，其存儲結(jié)構(gòu)可定義如下：

typedefstructnode { ElemTypedata; structnode*next; }LNode,*LinkList; ElemType為數(shù)據(jù)的類型，應(yīng)用時要用具體的數(shù)據(jù)類型來代替。LNode可定義元素結(jié)點，LinkList用于定義單鏈表的頭指針。 2.3線性表的鏈式存儲和操作實現(xiàn)第2章線性表3.基本操作（1）初始化單鏈表單鏈表的初始化操作就是創(chuàng)建一個頭結(jié)點，并返回頭指針。如果操作失敗則返回ERROR，否則返回OK。StatusInitiate_List(LNode**head){*head=(LinkList)malloc(sizeof(LNode)); /*分配內(nèi)存單元*/if(!*head){

printf(“Memoryallocatefailed!\n”);returnERROR;}memset(*head,0,sizeof(LNode));returnOK;}2.3線性表的鏈式存儲和操作實現(xiàn)第2章線性表（2）清除單鏈表中所有結(jié)點，并將單鏈表置為空清除單鏈表中結(jié)點時，需要釋放結(jié)點所占的空間。voidClearList_List(LinkListhead){ LNode*p,*q; p=head->next; while(p) /*循環(huán)單鏈表中所有結(jié)點*/ { q=p; p=p->next; free(q); /*釋放結(jié)點所占空間*/ } head->next=NULL;}2.3線性表的鏈式存儲和操作實現(xiàn)第2章線性表（3）判斷單鏈表是否為空，如果為空返回1，否則返回0引入頭結(jié)點之后，即可根據(jù)頭結(jié)點的指針域是否為空來判斷單鏈表是否為空。intListEmpty_List(LinkListhead){if(head->next==NULL) return1; else return0;}2.3線性表的鏈式存儲和操作實現(xiàn)第2章線性表（4）返回單鏈表的長度，空表則返回0遍歷單鏈表，結(jié)點個數(shù)即為鏈表的長度。為了便于查單鏈表的長度，也可以將其長度存入頭結(jié)點中的數(shù)據(jù)域。intLength_List(LinkListhead){ LNode*p; inti=0; p=head->next; while(p) { i++; p=p->next; } returni;}2.3線性表的鏈式存儲和操作實現(xiàn)第2章線性表（5）返回單鏈表的第i個結(jié)點i大于等于1，并且小于等于單鏈表長度；如果i超出范圍，則返回NULL，否則返回第i個結(jié)點的地址。LNode*GetElem_List(LinkListhead,inti){ LNode*p; intn=1; p=head->next; while(p&&n<i) { n++; p=p->next; } returnp;}2.3線性表的鏈式存儲和操作實現(xiàn)第2章線性表（6）查找單鏈表中第一個數(shù)據(jù)域為elem的結(jié)點位置，如果找不到則返回-1intFindElem_List(LinkListhead,ElemTypeelem){ LNode*p; intn=1; p=head->next; while(p&&p->data!=elem){ n++; p=p->next; } if(p==NULL) return-1; else returnn;}2.3線性表的鏈式存儲和操作實現(xiàn)第2章線性表（12）遍歷單鏈表中的元素voidTranverse_List(LinkListhead){ LNode*p; p=head->next; printf(“Thelistis:\n”); while(p) { printf(“%d\t”,p->data); /*此處假設(shè)數(shù)據(jù)域的類型為整型*/ p=p->next; } printf(“\n”);}2.3線性表的鏈式存儲和操作實現(xiàn)第2章線性表【例2-3】已有一手機通訊錄，各聯(lián)系人信息按照姓名字母順序遞增的方式排列?，F(xiàn)希望將各聯(lián)系人信息按照姓名字母順序遞減的方式排列。設(shè)計思路：將手機通訊錄用線性表的結(jié)構(gòu)表示，采用鏈式存儲方式。即將其視為一個單鏈表。循環(huán)該單鏈表，用頭插法將依次將聯(lián)系人信息插入到另一單鏈表中即可實現(xiàn)倒序。2.3線性表的鏈式存儲和操作實現(xiàn)第2章線性表程序描述如下：voidSort_List(RecordListhead){ /*將head所指單鏈表進行排序，并有head返回結(jié)果*/ LRecord*p,*p1,*q,*q1; p1=head->next; /*指向單鏈表的第一個結(jié)點（聯(lián)系人信息）*/ head->next=NULL; /*排序后的單鏈表為空*/ while(p1) /*循環(huán)所有待排序結(jié)點*/ {

p=p1; /*指示要插入到排序后單鏈表的結(jié)點（聯(lián)系人信息）*/

p1=p1->next; /*待排序的下一個結(jié)點（聯(lián)系人信息）*/

p->next=head->next; /*插入到排序后的單鏈表的頭結(jié)點后*/ head->next=p; } }2.3線性表的鏈式存儲和操作實現(xiàn)第2章線性表2.3.2單向循環(huán)鏈表1.基本概念將單鏈表最后一個結(jié)點的指針指向頭結(jié)點或者存儲第一個數(shù)據(jù)元素的結(jié)點，從而使整個鏈表稱為一個環(huán)，則構(gòu)成了單向循環(huán)鏈表。因其環(huán)形結(jié)構(gòu)，所以從循環(huán)鏈表的任意一個結(jié)點出發(fā)，均可以訪問到其它所有結(jié)點。單向循環(huán)鏈表的一個典型應(yīng)用就是用于約瑟夫環(huán)問題。根據(jù)是否有頭結(jié)點，可分為帶頭結(jié)點的單向循環(huán)鏈表和不帶頭結(jié)點的單向循環(huán)鏈表。帶頭結(jié)點的單向循環(huán)鏈表操作方便，如圖所示：（a）非空表

（b）空表2.3線性表的鏈式存儲和操作實現(xiàn)第2章線性表2.基本操作單向循環(huán)鏈表與單鏈表的存儲結(jié)構(gòu)相同，操作基本相同，區(qū)別僅在于建立空表時的初始化上和判斷最后一個結(jié)點的條件上：（1）建立空鏈表時，應(yīng)將頭結(jié)點的指針域指向頭結(jié)點本身；而單鏈表則置為空。（2）單向循環(huán)鏈表中沒有NULL指針。涉及遍歷操作時，其終止條件就不再是判斷指針是否為空，而是判別它們是否等于頭指針。2.3線性表的鏈式存儲和操作實現(xiàn)第2章線性表2.3.3雙向鏈表1.基本概念在單鏈表中，只有一個指向其后繼結(jié)點的指針域。因此，從某一個結(jié)點出發(fā)，很容易找到其后繼結(jié)點，但卻不容易找到其前驅(qū)結(jié)點。雙向鏈表即在每個節(jié)點中有兩個指針域，一個指向后繼結(jié)點。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地找到它的前驅(qū)結(jié)點和后繼結(jié)點。雙向鏈表同樣可以分為帶頭結(jié)點的雙向鏈表和不帶帶頭結(jié)點的雙向鏈表，也可以有雙向循環(huán)鏈表，同樣雙向循環(huán)鏈表也可以有是否帶頭結(jié)點之分。（a）非空表

（b）空表2.3線性表的鏈式存儲和操作實現(xiàn)第2章線性表

2.存儲結(jié)構(gòu) 雙向鏈表的結(jié)點主要有數(shù)據(jù)域和和兩個指針，其存儲結(jié)構(gòu)可定義如下：

typedefstructduNode { ElemTypedata; type