第2章 線(xiàn)性表_1

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)2015-2016-2渭南師范學(xué)院渭南師范學(xué)院 2015級(jí)級(jí)第第2章章 線(xiàn)性表線(xiàn)性表n2.1 線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義 n2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)n小結(jié)小結(jié)2.1 線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義n2.1.1 線(xiàn)性表的邏輯結(jié)構(gòu)線(xiàn)性表的邏輯結(jié)構(gòu)圖圖2.1 線(xiàn)性表的邏輯結(jié)構(gòu)線(xiàn)性表的邏輯結(jié)構(gòu) 2.1 線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義n2.1.1 線(xiàn)性表的邏輯結(jié)構(gòu)線(xiàn)性表的邏輯結(jié)構(gòu) 線(xiàn)性表(Linear List)是由n (n0)個(gè)類(lèi)型相同的數(shù)據(jù)元素a1, a2, ，

2、an組成的有限序列，記作（a1, a2, ，ai-1，ai，ai+1， ，an）。2.1 線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義n2.1.1 線(xiàn)性表的邏輯結(jié)構(gòu)線(xiàn)性表的邏輯結(jié)構(gòu) 線(xiàn)性表中相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系，即對(duì)于非空的線(xiàn)性表（a1, a2, ，ai-1, ai, ai+1, , an）， 表中ai-1 領(lǐng)先于ai，稱(chēng)ai-1 是ai的直接前驅(qū)直接前驅(qū)，而稱(chēng)ai是 ai-1的直接后繼直接后繼。2.1 線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義n2.1.1 線(xiàn)性表的邏輯結(jié)構(gòu)線(xiàn)性表的邏輯結(jié)構(gòu)第一個(gè)元素a1無(wú)直接前驅(qū)，最后一個(gè)元素an無(wú)直接后繼

3、，其余元素有且僅有一個(gè)直接前驅(qū)和直接后繼。 線(xiàn)性表中元素的個(gè)數(shù)n被定義為線(xiàn)性表的長(zhǎng)度，被定義為線(xiàn)性表的長(zhǎng)度，n=0時(shí)稱(chēng)為空表時(shí)稱(chēng)為空表。2.1 線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義n2.1.1 線(xiàn)性表的邏輯結(jié)構(gòu)線(xiàn)性表的邏輯結(jié)構(gòu)例如： 英文字母表(A, B, , Z)就是一個(gè)簡(jiǎn)單的線(xiàn)性表。在較為復(fù)雜的線(xiàn)性表中，數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成。如學(xué)生成績(jī)表中，每個(gè)學(xué)生及其各科成績(jī)是一個(gè)數(shù)據(jù)元素，它由學(xué)號(hào)、姓名、各科成績(jī)及平均成績(jī)等數(shù)據(jù)項(xiàng)(item) 組成。2.1 線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義n2.1.1 線(xiàn)性表的邏輯結(jié)構(gòu)線(xiàn)性表的邏輯結(jié)構(gòu)線(xiàn)

4、性表的特點(diǎn)：數(shù)據(jù)元素同類(lèi)型。：數(shù)據(jù)元素有限，表長(zhǎng)即數(shù)據(jù)元素個(gè)數(shù)。：線(xiàn)性表中相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系。 矩陣、數(shù)組、字符串、堆棧、 隊(duì)列等都符合線(xiàn)性條件。2.1 線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義n2.1.2 線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型定義ADT LinearList 數(shù)據(jù)元素?cái)?shù)據(jù)元素：D=ai| aiD0, i=1, 2, ，n, n0 ， D0為某一數(shù)據(jù)對(duì)象 關(guān)系：關(guān)系： | ai, ai+1D0，i=1, 2, , n-1 基本操作：基本操作：2.1 線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義n2.1.2 線(xiàn)性表的

5、抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型定義InitList(L)操作前提：L為未初始化線(xiàn)性表。 操作結(jié)果：將L初始化為空表。ListLength(L)操作前提：線(xiàn)性表L已存在。 操作結(jié)果：如果L為空表則返回0，否則返回表中的元素個(gè)數(shù)。2.1 線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義n2.1.2 線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型定義GetData(L, i)操作前提：表L存在，且i值合法，即1iListLength(L)。操作結(jié)果：返回線(xiàn)性表L中第i個(gè)元素的值。2.1 線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義n2.1.2 線(xiàn)性表的抽象數(shù)據(jù)

6、類(lèi)型定義線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型定義InsList(L, i, e)操作前提：表L已存在，e為合法元素值且1iListLength(L)+1。 操作結(jié)果：在L中第i個(gè)位置前插入新的數(shù)據(jù)元素e，L的長(zhǎng)度加1。2.1 線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義n2.1.2 線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型定義DelList(L, i, &e)操作前提：表L已存在且非空，1iListLength(L)。 操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，并用e返回其值，L的長(zhǎng)度減1。2.1 線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義n2.1.2 線(xiàn)性表的抽象數(shù)據(jù)類(lèi)

7、型定義線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型定義Locate(L, e)操作前提：表L已存在，e為合法數(shù)據(jù)元素值。操作結(jié)果：如果L中存在元素e，則將“當(dāng)前指針”指向元素e所在位置并返回TRUE，否則返回FALSE。2.1 線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義n2.1.2 線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型定義DestroyList(L)操作前提：線(xiàn)性表L已存在。 操作結(jié)果：將L銷(xiāo)毀。ClearList(L)操作前提：線(xiàn)性表L已存在 。 操作結(jié)果：將表L置為空表。2.1 線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型定義n2.1.2 線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型定義線(xiàn)性

8、表的抽象數(shù)據(jù)類(lèi)型定義EmptyList(L)操作前提：線(xiàn)性表L已存在。 操作結(jié)果：如果L為空表則返回TRUE，否則返回FALSE。 ADT LinearList2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)n2.2.1 線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)線(xiàn)性表的順序存儲(chǔ)是指用一組地址連續(xù)的存儲(chǔ)單指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線(xiàn)性表中的各個(gè)元素，使得線(xiàn)性表中在元依次存儲(chǔ)線(xiàn)性表中的各個(gè)元素，使得線(xiàn)性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲(chǔ)在相鄰的物理存儲(chǔ)邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲(chǔ)在相鄰的物理存儲(chǔ)單元中，單元中，即通過(guò)數(shù)據(jù)元素物理存儲(chǔ)的相鄰關(guān)系來(lái)反映數(shù)據(jù)元素之間邏輯上的相鄰關(guān)系。采用順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)

9、性表通常稱(chēng)為。2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)n2.2.1 線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)假設(shè)線(xiàn)性表中有n個(gè)元素，每個(gè)元素占k個(gè)單元，第一個(gè)元素的地址為L(zhǎng)oc(a1)，則可以通過(guò)如下公式計(jì)算出第i個(gè)元素的地址Loc(ai)： Loc(ai) =Loc(a1)+(i-1)k其中Loc(a1)稱(chēng)為基地址。2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)內(nèi)存空間狀態(tài)a1a2aianLoc(a1)Loc(a1)+k存儲(chǔ)(物理)地址邏輯地址12in空閑Loc(a1)+(i-1)kLoc(a1)+(n-1)k圖圖2.2 順序表存儲(chǔ)示意圖順序表存儲(chǔ)示意圖2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)n2

10、.2.1 線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)可以借助于高級(jí)程序設(shè)計(jì)語(yǔ)言中的一維數(shù)組來(lái)表示，一維數(shù)組的下標(biāo)與元素在線(xiàn)性表中的序號(hào)相對(duì)應(yīng)。2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)n2.2.1 線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言定義：#define MAXSIZE 100typedef struct ElemType elemMAXSIZE; /* 線(xiàn)性表占用的數(shù)組空間線(xiàn)性表占用的數(shù)組空間 */ int last; /* 指向線(xiàn)性表中最后一個(gè)元素指向線(xiàn)性表中最后一個(gè)元素,空表時(shí)置為空表時(shí)置為-1 */SeqList; /* 順序表類(lèi)型名是順序表類(lèi)型名是SeqList,

11、見(jiàn)教材見(jiàn)教材P40*/若有若有SeqList L;則元素則元素ai在內(nèi)存中為在內(nèi)存中為L(zhǎng).elemi-1若有若有SeqList *L;且且L有指向，則元素有指向，則元素ai在內(nèi)存中為在內(nèi)存中為L(zhǎng)-elemi-12.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)n2.2.2 線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算1. 查找操作查找操作 線(xiàn)性表有兩種基本的查找運(yùn)算。按序號(hào)查找GetData(L, i)：要求查找線(xiàn)性表L中第i個(gè)數(shù)據(jù)元素，其結(jié)果是L.elemi-1。按內(nèi)容查找Locate(L, e)：要求查找線(xiàn)性表L中與給定值e相等的數(shù)據(jù)元素。若在表L中找到與e相等的元素，則返回該元素在

12、表中的序號(hào)；若找不到， 則返回一個(gè)“空序號(hào)”-1。2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)【算法算法2.1 順序表的按內(nèi)容查找運(yùn)算順序表的按內(nèi)容查找運(yùn)算】/* 在順序表在順序表L中查找與中查找與e相等的元素，若相等的元素，若L.elemi=e，則找到該元素，并返回序號(hào)，則找到該元素，并返回序號(hào)i+1，若找不到，則返回，若找不到，則返回-1 */問(wèn)題：該算法的參數(shù)有哪些?類(lèi)型分別是什么？在順序表在順序表L中查找中查找，所以一個(gè)參數(shù)是L，其類(lèi)型是？查找與查找與e相等的元素相等的元素，所以一個(gè)參數(shù)是e，其類(lèi)型是？2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)【算法算法2.1 順序表的按內(nèi)容查找運(yùn)算順序表的

13、按內(nèi)容查找運(yùn)算】/* 在順序表在順序表L中查找與中查找與e相等的元素，若相等的元素，若L.elemi=e，則找到該元素，并返回序號(hào)，則找到該元素，并返回序號(hào)i+1，若找不到，則返回，若找不到，則返回-1 */int Locate(SeqList L,ElemType e) i=0 ; /* i為掃描計(jì)數(shù)器，初值為為掃描計(jì)數(shù)器，初值為0，即從線(xiàn)性表第一個(gè)元素開(kāi)始比較，即從線(xiàn)性表第一個(gè)元素開(kāi)始比較 */while ( (i=L.last)&(L.elemi!=e) ) /* 順序掃描表順序掃描表L,直到找到值為直到找到值為e i+; 的元素的元素,或掃描到表尾而沒(méi)找到或掃描到表尾而沒(méi)找到 */ i

14、f (ilast+1，i的合法取值范圍是的合法取值范圍是 1iL-last+2 */#define OK 1#define ERROR 0int InsList(SeqList *L, int i, ElemType e) /*注意參數(shù)注意參數(shù)*/ int k; if(iL-last+2) /* 首先判斷插入位置是否合法首先判斷插入位置是否合法 */ printf(插入位置i值不合法); return(ERROR); 2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ) if(L-last=MAXSIZE-1) printf(表已滿(mǎn)無(wú)法插入); return(ERROR); for(k=L-last;k=

15、i-1;k-) /* 從從n-1i-1的所有元素順次后移一個(gè)位置的所有元素順次后移一個(gè)位置 */ L-elemk+1=L-elemk; L-elemi-1=e; /* 在表在表L的第的第i個(gè)位置放入個(gè)位置放入e，第，第i個(gè)元素的下標(biāo)為個(gè)元素的下標(biāo)為i-1 */ L-last+; /* last后移一個(gè)元素，即表長(zhǎng)增后移一個(gè)元素，即表長(zhǎng)增1 */ return(OK); /* 算法算法2.2結(jié)束結(jié)束*/2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)n2.2.2 線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算【算法分析算法分析】在順序表中插入一個(gè)數(shù)據(jù)元素時(shí)，其時(shí)間主要耗在順序表中插入一個(gè)數(shù)

16、據(jù)元素時(shí)，其時(shí)間主要耗費(fèi)在移動(dòng)數(shù)據(jù)元素上。費(fèi)在移動(dòng)數(shù)據(jù)元素上。對(duì)于插入算法而言，設(shè)對(duì)于插入算法而言，設(shè)Pi為在第為在第i個(gè)元素之前插入個(gè)元素之前插入元素的概率，并元素的概率，并假設(shè)在任何位置上插入的概率相等假設(shè)在任何位置上插入的概率相等，即即Pi=1/(n+1), i=1, 2, ，n+1。2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)211) 1(11) 1(1111nkninninPEnkniniiinsn2.2.2 線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算設(shè)設(shè)Eins為在長(zhǎng)度為為在長(zhǎng)度為n的表中插入一個(gè)元素所需移動(dòng)的表中插入一個(gè)元素所需移動(dòng)元素的平均次數(shù)，則：元素的平均次數(shù)

17、，則：2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)n2.2.2 線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算3. 刪除操作刪除操作 DelList(L, i, &e)線(xiàn)性表的刪除運(yùn)算是指將表的第i(1in)個(gè)元素刪去，使長(zhǎng)度為n的線(xiàn)性表(e1，, ei-1，ei，ei+1，en)變成長(zhǎng)度為n-1的線(xiàn)性表(e1，, ei-1， ei+1，en)，并將所刪除元素帶回。 算法返回刪除成功或失敗的標(biāo)志。 故刪除成功時(shí)，被刪元素由參數(shù)帶回。2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)n2.2.2 線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算例如：線(xiàn)性表(4, 9, 15, 21,

18、 28, 30, 30, 42, 51, 62)刪除第5個(gè)元素28，則先臨時(shí)保存28，再將第6個(gè)元素到第10個(gè)元素依次向前移動(dòng)一個(gè)位置即可。如圖2.4所示。2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)n2.2.2 線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算圖圖2.4 順序表中刪除元素順序表中刪除元素 2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)【算法算法2.3 順序表的刪除運(yùn)算順序表的刪除運(yùn)算】 /*在順序表在順序表L中刪除第中刪除第i個(gè)數(shù)據(jù)元素，函數(shù)返回刪除成功與否的標(biāo)志。個(gè)數(shù)據(jù)元素，函數(shù)返回刪除成功與否的標(biāo)志。并用指針參數(shù)并用指針參數(shù)e返回已刪除元素的值。返回已刪除元素的值。i的

19、合法取值為的合法取值為1iL.last+1*/ 問(wèn)題：該算法的參數(shù)有哪些?類(lèi)型分別是什么？在順序表在順序表L中刪除中刪除，所以一個(gè)參數(shù)是L，其類(lèi)型是？刪除第刪除第i個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素，所以一個(gè)參數(shù)是i，其類(lèi)型是？用參數(shù)用參數(shù)e返回已刪元素返回已刪元素，所以一個(gè)參數(shù)是e，其類(lèi)型是？2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)【算法算法2.3 順序表的刪除運(yùn)算順序表的刪除運(yùn)算】 /*在順序表在順序表L中刪除第中刪除第i個(gè)數(shù)據(jù)元素，函數(shù)返回刪除成功與否的標(biāo)志。個(gè)數(shù)據(jù)元素，函數(shù)返回刪除成功與否的標(biāo)志。并用指針參數(shù)并用指針參數(shù)e返回已刪除元素的值。返回已刪除元素的值。i的合法取值為的合法取值為1iL.la

20、st+1*/ int DelList(SeqList *L, int i, ElemType *e) int k; if(iL-last+1) printf(刪除位置不合法！); return(ERROR); 2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ) *e=L-elemi-1; /* 將待刪的第將待刪的第i個(gè)元素存放到個(gè)元素存放到e所指向的變量中所指向的變量中 */ for(k=i;ilast;k+) /* 第第i+1個(gè)往后個(gè)往后(下標(biāo)下標(biāo)in)的元素順次前移的元素順次前移 */ L-elemk-1=L-elemk; L-last-; return(OK); 2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順

21、序存儲(chǔ)n2.2.2 線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算在順序表中刪除一個(gè)數(shù)據(jù)元素時(shí)，其時(shí)間主要耗費(fèi)在移動(dòng)數(shù)據(jù)元素上。對(duì)于刪除算法而言，設(shè)Qi為刪除第i個(gè)元素的概率，并假設(shè)在任何位置上刪除的概率相等，即Qi=1/n, i=1, 2, ，n。刪除一個(gè)元素所需移動(dòng)元素的平均次數(shù)Edel為：1011211)(1)(nkniniidelnkninninQE2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)n2.2.2 線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算例例2.3:有兩個(gè)順序表LA和LB，其元素均為非遞減有序排列。編寫(xiě)算法，將它們合并成一個(gè)順序表LC，要求LC也是

22、非遞減有序排列。例如LA=(2, 2, 3), LB=(1, 3, 3, 4), 則LC=(1, 2, 2, 3, 3, 3, 4)。2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)n2.2.2 線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算算法思想算法思想：設(shè)表LC是一個(gè)空表，指針k指向LC當(dāng)前元素設(shè)兩個(gè)指針i、j分別指向表LA和LB中的當(dāng)前元素若LA.elemiLB.elemj，則將LB.elemj插入到表LC中,并將j后移一個(gè)元素; k后移一個(gè)元素;若LA.elemiLB.elemj，則將LA.elemi插入到表LC ,并將i后移一個(gè)元素; k后移一個(gè)元素;重復(fù)該操作，直到其中一個(gè)

23、表被掃描完畢，然后再將未掃描完的表中剩余的所有元素依次放到表LC中。2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)n2.2.2 線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算問(wèn)題問(wèn)題：該算法的參數(shù)是什么？分別是什么類(lèi)型？方法一：參數(shù)：LA，LB；返回值為L(zhǎng)C；此時(shí)參數(shù)LA，LB可為SeqList 型或SeqList *型方法二：參數(shù)：LA，LB，LC；無(wú)返回值此時(shí)參數(shù)LA，LB可為SeqList 型或SeqList *型，LC必須為SeqList *型。2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)【算法算法2.4 線(xiàn)性表的合并運(yùn)算線(xiàn)性表的合并運(yùn)算】 void mergeList(SeqLi

24、st *LA, SeqList *LB, SeqList *LC) int i, j, k; i=0; j=0; k=0; /* i,j,k分別指向分別指向LA，LB，LC的當(dāng)前元素的當(dāng)前元素*/ while(ilast&jlast) if(LA-elemielemj) LC-elemk=LA-elemi; i+; k+; else LC-elemk=LB-elemj; j+; k+; 2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ) while(ilast) /* 表表LA未掃描完，將表未掃描完，將表LA剩余元素賦給表剩余元素賦給表LC */ LC-elemk=LA-elemi; i+; k+; w

25、hile(jlast) /* 表表LB未掃描完，將表未掃描完，將表LB剩余元素賦給表剩余元素賦給表LC */ LC-elemk=LB-elemj; j+; k+; LC-last=LA-last+LB-last+1; /* 更新表更新表LC最后一個(gè)元素指針，也可為最后一個(gè)元素指針，也可為k-1 */ 該算法的時(shí)間復(fù)雜度為該算法的時(shí)間復(fù)雜度為O(LA表長(zhǎng)表長(zhǎng)+LB表長(zhǎng)表長(zhǎng))2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)n2.2.2 線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算線(xiàn)性表順序存儲(chǔ)的優(yōu)點(diǎn)是：線(xiàn)性表順序存儲(chǔ)的優(yōu)點(diǎn)是： 無(wú)需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間（因?yàn)檫壿嬌舷噜?/p>

26、的元素其存儲(chǔ)的物理位置也是相鄰的）； 可方便地隨機(jī)存取表中的任一元素。2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)n2.2.2 線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算其缺點(diǎn)是：其缺點(diǎn)是： 插入或刪除運(yùn)算不方便，除表尾的位置外，在表的其它位置上插入或刪除操作都必須移動(dòng)大量的元素，其效率較低； 順序表的存儲(chǔ)分配只能預(yù)先進(jìn)行靜態(tài)分配，當(dāng)表長(zhǎng)變化較大時(shí)，難以確定合適的存儲(chǔ)規(guī)模。分配空間大，則可能造成一部分空間長(zhǎng)期閑置；分配空間小，則插入操作可能使表長(zhǎng)超過(guò)預(yù)先分配的空間而造成溢出。2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)n有序順序表的合并運(yùn)算的實(shí)現(xiàn)有序順序表的合并運(yùn)算的實(shí)現(xiàn) 算法2.4

27、為有序順序表的合并算法，若實(shí)現(xiàn)該算法，則需要補(bǔ)充一些代碼。對(duì)照算法2.4，分析如下：算法2.4用到了數(shù)據(jù)類(lèi)型SeqList ，所以定義它(P40)； 而定義SeqList時(shí)，用到了ElemType和MAXSIZE，定義它們；算法2.4是針對(duì)非空的順序表的操作，所以，得創(chuàng)建非空的順序表，所以，程序要包含算法2.2，即順序表的插入運(yùn)算，用于建立非空順序表。2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)n有序順序表的合并運(yùn)算的實(shí)現(xiàn)有序順序表的合并運(yùn)算的實(shí)現(xiàn) 算法2.4為有序順序表的合并算法，若實(shí)現(xiàn)該算法，則需要補(bǔ)充一些代碼。對(duì)照算法2.4，分析如下：當(dāng)兩個(gè)有序表合并完成后,為了看到其合并前和合并后的結(jié)果,

28、得輸出有序表,故要增加一個(gè)算法,用于輸出順序表；設(shè)為 out(SeqList L)有輸出，所以加#include2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)n有序順序表的合并運(yùn)算的實(shí)現(xiàn)有序順序表的合并運(yùn)算的實(shí)現(xiàn) 算法2.4為有序順序表的合并算法，若實(shí)現(xiàn)該算法，則需要補(bǔ)充一些代碼。對(duì)照算法2.4，分析如下：編寫(xiě)main()函數(shù):定義三個(gè)順序表:SeqList A,B,C;算法2.2是針對(duì)已經(jīng)存在的順序表的插入，但此時(shí)A，B和C的值是不確定的，故要先將三個(gè)順序表置為空表A.last=-1;通過(guò)多次調(diào)用InsList(&A,i,待插元素)創(chuàng)建非空順序表A，B通過(guò)調(diào)用out(A)輸出表A，B 調(diào)用merg

29、eList(&A,&B,&C)生成表C調(diào)用out(C)輸出表C2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)【線(xiàn)性表的合并運(yùn)算的實(shí)現(xiàn)線(xiàn)性表的合并運(yùn)算的實(shí)現(xiàn)】 #include#define MAXSIZE 100#define OK 1#define ERROR 0typedef int ElemType;typedef structElemType elemMAXSIZE; /* 線(xiàn)性表占用的數(shù)組空間線(xiàn)性表占用的數(shù)組空間 */int last; /* 指向線(xiàn)性表中最后一個(gè)元素，空表時(shí)置為指向線(xiàn)性表中最后一個(gè)元素，空表時(shí)置為-1 */SeqList;2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)int I

30、nsList(SeqList *L,int i,ElemType e) /*算法算法2.2: 順序表插入順序表插入*/int k;if(iL-last+2) /* 首先判斷插入位置是否合法首先判斷插入位置是否合法 */printf(插入位置插入位置i值不合法值不合法);return(ERROR);if(L-last=MAXSIZE-1)printf(表已滿(mǎn)無(wú)法插入表已滿(mǎn)無(wú)法插入);return(ERROR);for(k=L-last;k=i-1;k-) /* 從從n-1i-1順次向后移動(dòng)一個(gè)位置順次向后移動(dòng)一個(gè)位置 */L-elemk+1=L-elemk;L-elemi-1=e; /* 在表在表L的第的第i個(gè)位置放入個(gè)位置放入e， 第第i個(gè)元素的下標(biāo)為個(gè)元素的下標(biāo)為i-1 */L-last+; /* last后移一個(gè)元素，即表長(zhǎng)增后移一個(gè)元素，即表長(zhǎng)增1 */return(OK); /* 算法算法2.2結(jié)束結(jié)束*/2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)void out(SeqList L) /* 輸出函數(shù)輸出函數(shù) */int i;for(i=0;i=L.last;i+)printf(%d ,L.elemi);printf(n);2.2 線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表