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

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

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

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

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

{

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

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

基本操作：

Initiate（List）

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

ClearList（List）

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

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

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

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

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

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

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

Get（List，i，e）

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

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

Find（List，i，e）

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

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

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

Insert（List，i，e）

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

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

Delete（List，i）

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

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

GetPrior（List，e，pre_e）

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

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

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

GetNext（List，e，next_e）

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

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

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

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

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

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

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

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

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

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

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

L->list=NULL;

L->length=0; /*空表長(zhǎng)度為0*/

L->list_size=0;}}2.2線性表的順序存儲(chǔ)和操作實(shí)現(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è)元素類(lèi)型為整型*/ returnOK;}2.2線性表的順序存儲(chǔ)和操作實(shí)現(xiàn)第2章線性表【例2-1】已有一手機(jī)通訊錄，各聯(lián)系人信息按照姓名字母順序遞增的方式排列?，F(xiàn)需添加一聯(lián)系人信息，希望添加后各聯(lián)系人信息仍按照姓名字母順序遞增的方式排列設(shè)計(jì)思路：將手機(jī)通訊錄用線性表的結(jié)構(gòu)表示，采用順序存儲(chǔ)方式。即將其視為一個(gè)順序表。首先要判斷該順序表中是否還有剩余空間，如已存滿，則利用上述reallocate函數(shù)重新分配空間；然后在該順序表中從后往前尋找插入位置，將姓名字母比待插入聯(lián)系人姓名字母大（靠后）的記錄向后移動(dòng)，然后插入新的聯(lián)系人信息。2.2線性表的順序存儲(chǔ)和操作實(shí)現(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個(gè)位置處*/

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

typedefstructnode { ElemTypedata; structnode*next; }LNode,*LinkList; ElemType為數(shù)據(jù)的類(lèi)型，應(yīng)用時(shí)要用具體的數(shù)據(jù)類(lèi)型來(lái)代替。LNode可定義元素結(jié)點(diǎn)，LinkList用于定義單鏈表的頭指針。 2.3線性表的鏈?zhǔn)酱鎯?chǔ)和操作實(shí)現(xiàn)第2章線性表3.基本操作（1）初始化單鏈表單鏈表的初始化操作就是創(chuàng)建一個(gè)頭結(jié)點(diǎn)，并返回頭指針。如果操作失敗則返回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線性表的鏈?zhǔn)酱鎯?chǔ)和操作實(shí)現(xiàn)第2章線性表（2）清除單鏈表中所有結(jié)點(diǎn)，并將單鏈表置為空清除單鏈表中結(jié)點(diǎn)時(shí)，需要釋放結(jié)點(diǎn)所占的空間。voidClearList_List(LinkListhead){ LNode*p,*q; p=head->next; while(p) /*循環(huán)單鏈表中所有結(jié)點(diǎn)*/ { q=p; p=p->next; free(q); /*釋放結(jié)點(diǎn)所占空間*/ } head->next=NULL;}2.3線性表的鏈?zhǔn)酱鎯?chǔ)和操作實(shí)現(xiàn)第2章線性表（3）判斷單鏈表是否為空，如果為空返回1，否則返回0引入頭結(jié)點(diǎn)之后，即可根據(jù)頭結(jié)點(diǎn)的指針域是否為空來(lái)判斷單鏈表是否為空。intListEmpty_List(LinkListhead){if(head->next==NULL) return1; else return0;}2.3線性表的鏈?zhǔn)酱鎯?chǔ)和操作實(shí)現(xiàn)第2章線性表（4）返回單鏈表的長(zhǎng)度，空表則返回0遍歷單鏈表，結(jié)點(diǎn)個(gè)數(shù)即為鏈表的長(zhǎng)度。為了便于查單鏈表的長(zhǎng)度，也可以將其長(zhǎng)度存入頭結(jié)點(diǎn)中的數(shù)據(jù)域。intLength_List(LinkListhead){ LNode*p; inti=0; p=head->next; while(p) { i++; p=p->next; } returni;}2.3線性表的鏈?zhǔn)酱鎯?chǔ)和操作實(shí)現(xiàn)第2章線性表（5）返回單鏈表的第i個(gè)結(jié)點(diǎn)i大于等于1，并且小于等于單鏈表長(zhǎng)度；如果i超出范圍，則返回NULL，否則返回第i個(gè)結(jié)點(diǎn)的地址。LNode*GetElem_List(LinkListhead,inti){ LNode*p; intn=1; p=head->next; while(p&&n<i) { n++; p=p->next; } returnp;}2.3線性表的鏈?zhǔn)酱鎯?chǔ)和操作實(shí)現(xiàn)第2章線性表（6）查找單鏈表中第一個(gè)數(shù)據(jù)域?yàn)閑lem的結(jié)點(diǎn)位置，如果找不到則返回-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線性表的鏈?zhǔn)酱鎯?chǔ)和操作實(shí)現(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ù)域的類(lèi)型為整型*/ p=p->next; } printf(“\n”);}2.3線性表的鏈?zhǔn)酱鎯?chǔ)和操作實(shí)現(xiàn)第2章線性表【例2-3】已有一手機(jī)通訊錄，各聯(lián)系人信息按照姓名字母順序遞增的方式排列?，F(xiàn)希望將各聯(lián)系人信息按照姓名字母順序遞減的方式排列。設(shè)計(jì)思路：將手機(jī)通訊錄用線性表的結(jié)構(gòu)表示，采用鏈?zhǔn)酱鎯?chǔ)方式。即將其視為一個(gè)單鏈表。循環(huán)該單鏈表，用頭插法將依次將聯(lián)系人信息插入到另一單鏈表中即可實(shí)現(xiàn)倒序。2.3線性表的鏈?zhǔn)酱鎯?chǔ)和操作實(shí)現(xiàn)第2章線性表程序描述如下：voidSort_List(RecordListhead){ /*將head所指單鏈表進(jìn)行排序，并有head返回結(jié)果*/ LRecord*p,*p1,*q,*q1; p1=head->next; /*指向單鏈表的第一個(gè)結(jié)點(diǎn)（聯(lián)系人信息）*/ head->next=NULL; /*排序后的單鏈表為空*/ while(p1) /*循環(huán)所有待排序結(jié)點(diǎn)*/ {

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

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

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

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

（b）空表2.3線性表的鏈?zhǔn)酱鎯?chǔ)和操作實(shí)現(xiàn)第2章線性表

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

typedefstructduNode { ElemTypedata; type