第二章線性表_1.ppt

1、1/53,第一章回顧,1、程序設(shè)計(jì)和算法、數(shù)據(jù)結(jié)構(gòu)的關(guān)系 2、數(shù)據(jù)結(jié)構(gòu)討論的內(nèi)容 3、數(shù)據(jù)結(jié)構(gòu)的定義 4、抽象數(shù)據(jù)類型的概念 5、算法及其度量,2/53,練習(xí),設(shè) n 為正整數(shù)。試確定下列各程序段中前置以記號(hào) 的語句的頻度 i=1; k=0;while ( i=n-1) k += 10 * i; i+;,n-1,3/53,i=1; k=0;do k +=10 * i; i+; while(i=n-1);,n-1,但n=1時(shí)特殊,是1次,4/53,x=n; y=0; / n 是不小于1的常數(shù)while (x=(y+1)*(y+1) y+;,5/53,x=91; y=100;while (y0 )

2、 if (x100 ) x -= 10; y- -; else x+;,1100,6/53,數(shù)據(jù)結(jié)構(gòu)部分的起點(diǎn)：,什么是 線性結(jié)構(gòu)？,7/53,第1章 緒論 第2章 線性表 第3章 棧和隊(duì)列 第4章 串 第5章 數(shù)組和廣義表 第6章 樹和二叉樹 第7章 圖 第9章 查找 第10、11章 排序 數(shù)據(jù)庫部分,目 錄,8/53,線性結(jié)構(gòu)的定義：,若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。 可表示為：（a1 , a2 , , an）,簡(jiǎn)言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 的。,特點(diǎn) 只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)； 特點(diǎn) 除首尾結(jié)點(diǎn)外，其他結(jié)

3、點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。,線性結(jié)構(gòu)包括：線性表、堆棧、隊(duì)列、字符串、數(shù)組等，其中最典型、最常用的是-,線性表,一對(duì)一 (1:1),9/53,第2章 線性表,2.1 線性表的類型定義 2.2 線性表的順序表示和實(shí)現(xiàn) 2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 2.4 應(yīng)用舉例,10/53,（a1, a2, ai-1，ai, ai1 ，, an）,2.1 線性表的定義：用數(shù)據(jù)元素的有限序列表示,n=0時(shí)稱為,數(shù)據(jù)元素,線性起點(diǎn),ai的直接前趨,ai的直接后繼,下標(biāo)，是元素的序號(hào)，表示元素在表中的位置,n為元素總個(gè)數(shù)，即表長(zhǎng)。n0,空表,線性終點(diǎn),11/53,（ A, B, C, D, , Z）,例2

4、 分析學(xué)生情況登記表是什么結(jié)構(gòu)。,分析：數(shù)據(jù)元素都是同類型（記錄），元素間關(guān)系是線性的。,分析： 數(shù)據(jù)元素都是同類型（字母）， 元素間關(guān)系是線性的。,注意：同一線性表中的元素必定具有相同特性 ！,例1 分析26 個(gè)英文字母組成的英文表是什么結(jié)構(gòu)。,12/53,“同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性”是指數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)都相等。,是指各元素具有相同的數(shù)據(jù)類型,試判斷下列敘述的正誤：,13/53,線性表的抽象數(shù)據(jù)類型的定義,ADT List 數(shù)據(jù)對(duì)象：Dai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：R1 | ai-1,aiD, i=2,.,n 基本

5、操作： 結(jié)構(gòu)初始化 銷毀結(jié)構(gòu) 引用型操作 加工型操作 ADT List,14/53,線性表的抽象數(shù)據(jù)類型的定義,ADT List 數(shù)據(jù)對(duì)象：Dai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：R1 | ai-1,aiD, i=2,.,n 基本操作：結(jié)構(gòu)初始化InitList( 2依值在線性表 LA 中進(jìn)行查詢； LocateElem(LA,e,equal( ) 3若不存在，則將它插入到 LA 中。 ListInsert( LA, n+1,e ) 重復(fù)上述三步直至 LB 遍歷止。,20/53,對(duì)應(yīng)的線性表基本操作： 1. GetElem(Lb,i,e); 2. Locate

6、Elem( LA, e, equal() ); 3. ListInsert( LA, n+1,e ) void union(List / 銷毀線性表 LB / union,21/53,例2有順序表A和B，其元素均按從小到大的升序排列，編寫一個(gè)算法將它們合并成一個(gè)順序表C，要求C的元素也按從小到大的升序排列。,基本思路： 依次掃描A和B的元素，比較當(dāng)前元素ai和bj： if(aibj) ai賦給Ck; i+;k+； else bj賦給Ck; j+;k+； 將未完的那個(gè)順序表中余下部分賦給C;,22/53,void MergeList(SqList La,SqList Lb,SqList *Lc)

7、 /* 算法2.2 */ /* 已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減排列。 */ /* 歸并La和Lb得到新的線性表Lc，Lc的數(shù)據(jù)元素也按值非遞減排列 */ int i=1,j=1,k=0; InitList(Lc); /* 創(chuàng)建空表Lc */ La_len=ListLength(La); Lb_len=ListLength(Lb); /依次掃描A和B的元素，比較當(dāng)前元素ai和bj： while(i=La_len ,23/53,教材例2-1：求兩個(gè)線性表的“并”，即： LA U LB = ?,算法至少有兩種： LA和LB都是無序表，則從LB中取元素逐一與LA中所有元素比較，相同則不插入

8、LA中；O(ListLength(LA)* ListLength(LB) 若LA和LB已經(jīng)是有序表，則“歸并”的時(shí)間效率可以大大提高。 O(ListLength(LA)+ ListLength(LB)。,24/53,2.2.1 順序表的表示,用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的元素。,把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。,線性表的順序表示又稱為順序存儲(chǔ)結(jié)構(gòu)或順序映像。,順序存儲(chǔ)定義：,順序存儲(chǔ)方法：,特點(diǎn)：,邏輯上相鄰的元素，物理上也相鄰,可以利用數(shù)組Vn來實(shí)現(xiàn),注意：在C語言中數(shù)組的下標(biāo)是從0開始，即： Vn的有效范圍是從 V0Vn-1,25/53,1. 邏輯上

9、相鄰的數(shù)據(jù)元素，其物理上也相鄰； 2. 若已知表中首元素在存儲(chǔ)器中的位置，則其他元素存放位置亦可求出（利用數(shù)組Vn的下標(biāo)）。,設(shè)首元素a1的存放地址為L(zhǎng)OC(a1)（稱為首地址）， 設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長(zhǎng)度）為L(zhǎng)字節(jié)， 則表中任一數(shù)據(jù)元素的存放地址為： LOC ( ai+1 ) = LOC( ai ) + L LOC ( ai ) = LOC( a1 ) + L *（i -1）,對(duì)上述公式的解釋如圖所示,線性表順序存儲(chǔ)特點(diǎn)：,26/53,地址 內(nèi)容 元素在表中的位序,1,i,2,n,空閑區(qū),i+1,L,b=LOC(a1),b + L,b +(i-1)L,b +(n-1)L,b +(ma

10、x-1)L,LOC ( ai ) = LOC( a1 ) + L *（i -1）,線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖,下標(biāo)起點(diǎn)是1,27/53,設(shè)有一維數(shù)組，下標(biāo)的范圍是到，每個(gè)數(shù)組元素用相鄰的個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，設(shè)存儲(chǔ)數(shù)組元素的第一個(gè)字節(jié)的地址是98，則的第一個(gè)字節(jié)的地址是多少？,答案：113,但此題要注意下標(biāo)起點(diǎn)是從0開始： LOC( M3 ) = 98 + 5 (4-1) =113,解：已知地址計(jì)算通式為：,LOC(ai) = LOC(a1) + L *（i-1）,例1,或用（3-0）,28/53,char V30; void build() /字母線性表的生成，即建表操作 int i

11、; V0=a; for( i=1; i=n-1; i+ ) Vi=Vi-1+1; ,核心語句： 法1 Vi= Vi-1+1; 法2 Vi=a+i; 法3 Vi=97+i;,例2,用數(shù)組V來存放26個(gè)英文字母組成的線性表（a，b，c，z），寫出在順序結(jié)構(gòu)上生成和顯示該表的C語言程序。,省略了include語句,29/53,void main(void) /主函數(shù)，字母線性表的生成和輸出 n=26; / n是表長(zhǎng)，是數(shù)據(jù)元素的個(gè)數(shù)，而不是V的實(shí)際下標(biāo) build( ); display( ); ,void display( ) /字母線性表的顯示，即讀表操作 int i; for( i=0; i=

12、n-1; i+ ) printf( %c, vi ); printf( n ); ,執(zhí)行結(jié)果： a b c d e f g h i j k l m n o p q r s t u v w x y z,30/53,2.2.2 順序表的實(shí)現(xiàn)（或操作）,數(shù)據(jù)結(jié)構(gòu)的基本運(yùn)算： 修改、插入、刪除、查找、排序,1) 修改 通過數(shù)組的下標(biāo)便可訪問某個(gè)特定元素并修改之。,核心語句: Vi=x;,顯然，順序表修改操作的時(shí)間效率是 O(1),31/53,在線性表的第i個(gè)位置前插入一個(gè)元素,實(shí)現(xiàn)步驟： 將第n至第i 位的元素向后移動(dòng)一個(gè)位置； 將要插入的元素寫到第i個(gè)位置； 表長(zhǎng)加1。,for (j=n; j=i;

13、 j-) aj+1=a j ; a i =x; n+;,/ 元素后移一個(gè)位置,/ 插入x,/ 表長(zhǎng)加1,核心語句：,2)插入,注意：事先應(yīng)判斷: 插入位置i 是否合法?表是否已滿? 應(yīng)當(dāng)符合條件： 1in+1 或 i=1, n+1,32/53,在線性表的第i個(gè)位置前插入一個(gè)元素的示意圖如下：,插入25,33/53,實(shí)現(xiàn)步驟： 將第i+1 至第n 位的元素向前移動(dòng)一個(gè)位置； 表長(zhǎng)減1。,刪除線性表的第i個(gè)位置上的元素,for ( j=i+1; j=n; j+ ) aj-1=aj; n-;,/ 元素前移一個(gè)位置,/ 表長(zhǎng)減1,核心語句：,3)刪除,注意：事先需要判斷，刪除位置i 是否合法? 應(yīng)當(dāng)符

14、合條件：1in 或 i=1, n,34/53,刪除順序表中某個(gè)指定的元素的示意圖如下：,35/53,順序表的運(yùn)算效率分析,算法時(shí)間主要耗費(fèi)在移動(dòng)元素的操作上，因此 計(jì)算時(shí)間復(fù)雜度的基本操作（最深層語句頻度） T(n)= O (移動(dòng)元素次數(shù)) 而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置。,思考：若插入在尾結(jié)點(diǎn)之后，則根本無需移動(dòng)（特別快）； 若插入在首結(jié)點(diǎn)之前，則表中元素全部要后移（特別慢）； 應(yīng)當(dāng)考慮在各種位置插入（共n+1種可能）的平均移動(dòng)次數(shù)才合理。,討論1：若在長(zhǎng)度為 n 的線性表的第 i 位前 插入一個(gè)元素，則向后移動(dòng)元素的次數(shù)f(n)為: f(n) =,n i + 1,時(shí)間效率分析:

15、,36/53,推導(dǎo)：假定在每個(gè)元素位置上插入x的可能性都一樣（即概率P相同），則應(yīng)當(dāng)這樣來計(jì)算平均執(zhí)行時(shí)間： 將所有位置的執(zhí)行時(shí)間相加，然后取平均。 若在首結(jié)點(diǎn)前插入，需要移動(dòng)的元素最多，后移次數(shù)為n； 若在a1后面插入，要后移n-1個(gè)元素，后移次數(shù)為n-1; 若在an-1后面插入，后移次數(shù)為1； 若在尾結(jié)點(diǎn)an之后插入，則后移次數(shù)為0；,故插入時(shí)的平均移動(dòng)次數(shù)為：n(n+1)/2（n+1）n/2O(n),共有多少種插入形式?連頭帶尾有n+1種!,所有可能的元素移動(dòng)次數(shù)合計(jì)： 0+1+n = n(n+1)/2,37/53,同理可證：順序表刪除一元素的時(shí)間效率為: T（n)=(n-1)/2 O(

16、n),想一想： 順序表插入、刪除算法的平均空間復(fù)雜度為多少？,插入效率：,刪除效率：,教材P25算法2.5也是對(duì)執(zhí)行效率的推導(dǎo)：,因?yàn)闆]有占用輔助空間！,含義：對(duì)于順序表，插入、刪除操作平均需要移動(dòng)一半元素( n / 2 ),O(1),即插入、刪除算法的平均時(shí)間復(fù)雜度為 O(n),38/53,#define LIST_MAX_LENGTH 100 /線性表的最大長(zhǎng)度 typedef int ElemType; typedef struct ElemType *elem; /指向存放線性表中數(shù)據(jù)元素的基地址 int length; /線性表的當(dāng)前長(zhǎng)度 SQ_LIST；,39/53,典型操作的算法

17、實(shí)現(xiàn),1. 初始化線性表L int InitList(SQ_LIST /成功返回OK / sizeof(x)算符的意思是：計(jì)算變量x的長(zhǎng)度(字節(jié)數(shù)) malloc(m)函數(shù)的意思是：新開一片大小為m字節(jié)的連續(xù)空間，并把該區(qū)首址作為函數(shù)值。,40/53,2. 銷毀線性表L void DestroyList(SQ_LIST /釋放線性表占據(jù)的所有存儲(chǔ)空間 ,41/53,3. 清空線性表L void ClearList(SQ_LIST /將線性表的長(zhǎng)度置為0 ,42/53,4. 求線性表L的長(zhǎng)度 int GetLength(SQ_LIST L) return (L.length); ,43/53,5

18、. 判斷線性表L是否為空 int IsEmpty(SQ_LIST L) if (L.length=0) return TRUE; else return FALSE; ,44/53,6. 獲取線性表L中的某個(gè)數(shù)據(jù)元素的內(nèi)容 int GetElem(SQ_LIST L,int i, ElemType ,45/53,7. 在線性表L中檢索值為e的數(shù)據(jù)元素 int LocateELem(SQ_LIST L, int(*compare)(ElemType,ElemType) /* 操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序。若這樣的數(shù)據(jù)元素不存在，則返回值為0。 */ El

19、emType *p; int i=1; /* i的初值為第1個(gè)元素的位序 */ p=L.elem; /* p的初值為第1個(gè)元素的存儲(chǔ)位置 */ while(i=L.length ,int equal (ElemType a,ElemType b) /* 根據(jù)a 或= b，分別返回0或1 */ if(a=b) return 1; else return 0; ,LocateElem(L,j,equal);,46/53,8. 將線性表L中第i個(gè)數(shù)據(jù)元素刪除 int ListDelete(SQ_LIST ,47/53,9. 在線性表L中第i個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素e int ListInsert(

20、SQ_LIST ,48/53,進(jìn)一步討論：,順序表的存儲(chǔ)結(jié)構(gòu)是一維數(shù)組，如果插入的元素個(gè)數(shù)超過數(shù)組定義的長(zhǎng)度怎么辦？ 采用動(dòng)態(tài)分配的一維數(shù)組,49/53,動(dòng)態(tài)數(shù)組簡(jiǎn)介,先為順序表空間設(shè)定一個(gè)初始分配量，一旦因插入元素而空間不足時(shí)，可為順序表增加一個(gè)約定長(zhǎng)度的空間增量。,#define LIST_INIT_SIZE 100 /存儲(chǔ)空間的初始分配量 #define LISTINCREMENT 10/存儲(chǔ)空間的分配增量 Typedef struct ElemType *elem; /表基址(用指針*elem表示） int length; /表長(zhǎng)度（表中有多少個(gè)元素） int listsize; /當(dāng)

21、前分配的表尺寸（字節(jié)單位） SqList;,注：三個(gè)分量可簡(jiǎn)寫為：L.elem L.length L.listsize,存儲(chǔ)結(jié)構(gòu)描述如下（見教材P22）：,50/53,Status InitList_Sq( SqList /InitList_Sq,動(dòng)態(tài)創(chuàng)建一個(gè)空順序表的算法：,51/53,動(dòng)態(tài)順序表的插入算法 Status ListInsert_Sq(SqList / 檢驗(yàn)i 值的合法性,if ( L.length L.listsize ) /若表長(zhǎng)超過表尺寸則要增加尺寸 newbase = ( ElemType* ) realloc ( L.elem , (L.listsize + LISTINCREMENT )* sizeof ( Ele