1、北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表1第二章第二章 線性表線性表123456789BIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表2本章內(nèi)容本章內(nèi)容n2.1 線性表的類型定義線性表的類型定義n2.2 線性表類型的實現(xiàn)線性表類型的實現(xiàn) 順序映象順序映象n2.3 線性表類型的實現(xiàn)線性表類型的實現(xiàn) 鏈?zhǔn)接诚箧準(zhǔn)接诚驜IT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表32.2.1 順序表示及其特點順序表示及其特點n2.2.2 數(shù)據(jù)結(jié)構(gòu)定義數(shù)據(jù)結(jié)構(gòu)定義n2.2.3 順序表的初始化操

2、作順序表的初始化操作n2.2.4 順序表的插入操作順序表的插入操作n2.2.5 順序表的刪除操作順序表的刪除操作n2.2.6 用順序表實現(xiàn)合并操作用順序表實現(xiàn)合并操作LCLA + LBBIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表42.2.1 順序表示及其特點順序表示及其特點n順序映象順序映象 以以 x 的存儲位置和的存儲位置和 y 的存儲位置之間的存儲位置之間某種關(guān)系表示邏輯關(guān)系某種關(guān)系表示邏輯關(guān)系。n最簡單的一種順序映象方法是最簡單的一種順序映象方法是：n用一組用一組地址連續(xù)地址連續(xù)的存儲單元的存儲單元依次存放依次存放線性表

3、中的線性表中的數(shù)據(jù)元素數(shù)據(jù)元素。 a1 a2 ai-1 ai an線性表的線性表的起始地址起始地址稱作線性表的基地稱作線性表的基地址址BIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表52.2.1 順序表示及其特點順序表示及其特點n以以“存儲位置相鄰存儲位置相鄰”表示有序?qū)Ρ硎居行驅(qū)即：即：LOC(ai) = LOC(ai-1) + CnC是一個數(shù)據(jù)元素所占存儲量是一個數(shù)據(jù)元素所占存儲量n所有數(shù)據(jù)元素的存儲位置均取決于第一個數(shù)據(jù)元素所有數(shù)據(jù)元素的存儲位置均取決于第一個數(shù)據(jù)元素的存儲位置的存儲位置 nLOC(ai) = LOC(a1

4、) + (i-1)C n BIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表6小結(jié)：順序表的特點小結(jié)：順序表的特點n用連續(xù)的存儲單元存放線性表的元素用連續(xù)的存儲單元存放線性表的元素(采用一維數(shù)組采用一維數(shù)組存放存放)。n元素存儲順序與元素的邏輯順序一致。元素存儲順序與元素的邏輯順序一致。n讀寫元素方便讀寫元素方便 ，通過下標(biāo)即可指定位置。，通過下標(biāo)即可指定位置。 a1 a2 ai-1 ai an線性表的線性表的起始地址起始地址稱作線性表的基地稱作線性表的基地址址BIT GaoChunXiaoNotes of Data Structu

5、re北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表72.2.2 順序表順序表數(shù)據(jù)結(jié)構(gòu)定義數(shù)據(jù)結(jié)構(gòu)定義#define LIST_INIT_SIZE 80 / 線性表存儲空間的初始分配量線性表存儲空間的初始分配量#define LISTINCREMENT 10 / 線性表存儲空間的分配增量線性表存儲空間的分配增量typedef struct ElemType *elem; / 存儲空間基址存儲空間基址 int length; / 當(dāng)前長度當(dāng)前長度 int listsize; / 當(dāng)前分配的存儲容量當(dāng)前分配的存儲容量 / (以以sizeof(ElemType)為單位為單位) SqList; / 俗稱順序表俗稱

6、順序表BIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表8 0 1 . i-2 i-1 . n-1 順序表順序表a1a2ai-1aian.L.elem+L. length1L.elem+L. listsize1elemlengthlistsizeL注意：由于數(shù)組的下標(biāo)從注意：由于數(shù)組的下標(biāo)從“0”開始，表中第開始，表中第 i 個元素是個元素是 L.elemi - 1.typedef struct ElemType *elem; int length; int listsize; SqList; / 順序表順序表SqList L;BI

7、T GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表92.2.3 順序表的初始化操作順序表的初始化操作Status InitList_Sq( SqList& L ) / 構(gòu)造一個空的線性表構(gòu)造一個空的線性表 L.elem = (ElemType*) malloc (LIST_INIT_SIZE sizeof (ElemType); if (!L.elem) exit(OVERFLOW); L.length = 0; L.listsize = LIST_INIT_SIZE; return OK; / InitList_Sqtyped

8、ef struct ElemType *elem; int length; int listsize; SqList; / 順序表順序表BIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表102.2.4 順序表的插入操作順序表的插入操作nListInsert(&L, i, e) / 插入元素插入元素n在順序表在順序表L的第的第 i 個元素之前插入新的元素個元素之前插入新的元素e,n把把e插入到第插入到第 i 個元素的位置個元素的位置n i 的合法范圍為的合法范圍為 1iL.length+1 0 1 . i-2 i-1 . n-

9、1a1a2ai-1aianeeBIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表11n操作的過程：操作的過程： ListInsert(&L, 6, 30)3416118253134161182531303416118253134161183025313416118302531BIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表12操作的過程：操作的過程： ListInsert(&L, 6, 30)3416118253134161183025313416118

10、2531pqp34161182531pq = &(L.elemi-1);p = &(L.elemL.length-1); *(p+1) = *p;p-; 34161182531p*(p+1) = *p; *q=e;p=q; BIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表13n操作步驟操作步驟n判斷插入位置是否合法：判斷插入位置是否合法： 1iL.length+1n初始化指針初始化指針n循環(huán)：從表尾開始，依次將第循環(huán)：從表尾開始，依次將第i-1個元素之后的個元素之后的元素順序后移一位元素順序后移一位n將新元素將新元

11、素e寫入到第寫入到第i個位置個位置1.將表的長度加將表的長度加1BIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表14Status ListInsert_Sq(SqList &L, int i, ElemType e) if (i L.length+1) return ERROR; / 步驟步驟1：位置不合法：位置不合法 q = &(L.elemi-1); /步驟步驟2：q 指示插入位置指示插入位置 for (p = &(L.elemL.length-1); p = q; p-) *(p+1) = *p; /

12、步驟步驟3：元素依次后移：元素依次后移 *q = e; / 步驟步驟4：插入：插入e +L.length; / 步驟步驟5：表長加：表長加1 return OK; / ListInsert_Sq 算法時間復(fù)雜度取決于算法時間復(fù)雜度取決于: : 移動元素的次數(shù)移動元素的次數(shù)BIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表15插入操作的算法復(fù)雜度插入操作的算法復(fù)雜度n考慮移動元素的平均情況：考慮移動元素的平均情況：n 假設(shè)在第假設(shè)在第 i 個元素之前插入的概率為個元素之前插入的概率為pi，則在長度，則在長度為為n 的線性表中的線性表中

13、插入一個元素所需移動元素次數(shù)的插入一個元素所需移動元素次數(shù)的期望值期望值為：為：11) 1(niiisinpE2) 1(1111ninnEniisn若假定在線性表中任何一個位置上進(jìn)行若假定在線性表中任何一個位置上進(jìn)行插入的概率插入的概率都是都是相等相等的，則的，則移動元素的期望值移動元素的期望值為為：算法時間復(fù)雜度算法時間復(fù)雜度為為: : O(n)BIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表16if (L.length = L.listsize) / 當(dāng)前存儲空間已滿，增加分配當(dāng)前存儲空間已滿，增加分配 newbase = (

14、ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); / 存儲分配失敗存儲分配失敗 L.elem = newbase; / 新基址新基址 L.listsize += LISTINCREMENT; / 增加存儲容量增加存儲容量如果存儲空間已滿怎么辦？如果存儲空間已滿怎么辦？BIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表17程序設(shè)計方法的兩點說明程序設(shè)計方法的兩點說明n先考慮一般情況

15、，后考慮特殊情況n一般不用基本操作實現(xiàn)其他基本操作BIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表18兩個實際問題兩個實際問題n錯誤的類型：錯誤的類型：n正常處理的錯誤正常處理的錯誤：是一些：是一些常見、合理常見、合理的錯誤（如：的錯誤（如：用戶輸入的錯誤），通過用戶輸入的錯誤），通過錯誤代碼錯誤代碼返回。返回。n意外錯誤意外錯誤：拋出：拋出ExceptionException，通過，通過trytrycatchcatch撲捉。撲捉。n初始化問題：數(shù)據(jù)結(jié)構(gòu)初始化問題：數(shù)據(jù)結(jié)構(gòu)沒有初始化就使用沒有初始化就使用往往也是往往也是錯誤，但無

16、法判定。在錯誤，但無法判定。在C+C+和和JavaJava中通過中通過構(gòu)造函數(shù)構(gòu)造函數(shù)解解決。決。BIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表192.2.5 順序表的刪除操作順序表的刪除操作nListDelete(&L, i, &e) / 刪除元素刪除元素n刪除線性表中第刪除線性表中第i個元素，并將刪除的元素方在個元素，并將刪除的元素方在e中中ni 的合法范圍為的合法范圍為 1iL.lengthBIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表20操

17、作的過程：操作的過程： ListDelete (&L, 5, &e)34161253134161253134161182531pp341612531pp = &(L.elemi-1); *e = *p;p+; 341612531p*(p-1) = *p;p=L.elem+L.length-1; pp+; 341612531p*(p-1) = *p;BIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表21n操作步驟操作步驟n判斷插入位置是否合法：判斷插入位置是否合法： 1iL.lengthn初始化指針初始化指針n

18、將第將第i個元素的值賦給變量個元素的值賦給變量en循環(huán)：從第循環(huán)：從第i+1個元素開始，依次將后面的元素個元素開始，依次將后面的元素順序前移一位順序前移一位n將表的長度減將表的長度減1BIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表22Status ListDelete_Sq (SqList &L, int i, ElemType &e) / 步驟步驟1：位置是否合法：位置是否合法 if (i L.length) return ERROR; p = &(L.elemi-1); /步驟步驟2 2：初始化指針：

19、初始化指針 e = *p; /步驟步驟3:賦給賦給 e q = L.elem+L.length-1; / 表尾的位置表尾的位置 for (+p; p = q; +p) *(p-1) = *p; / 步驟步驟4：被刪除元素之后的元素左移：被刪除元素之后的元素左移 -L.length; / 步驟步驟5：表長減：表長減1 return OK; / ListDelete_Sq算法時間復(fù)雜度取決于算法時間復(fù)雜度取決于: : 移動元素的次數(shù)移動元素的次數(shù)BIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表23刪除操作的算法復(fù)雜度刪除操作的算法復(fù)雜

20、度n考慮移動元素的考慮移動元素的平均情況平均情況：n 假設(shè)在刪除第假設(shè)在刪除第 i 個元素的概率為個元素的概率為pi，則在長度為，則在長度為n 的線性表中的線性表中刪除一個元素所需移動元素次數(shù)的期望刪除一個元素所需移動元素次數(shù)的期望值為值為：niidlinpE1)(n若假定在線性表中任何一個位置上進(jìn)行若假定在線性表中任何一個位置上進(jìn)行刪除的概率刪除的概率都是都是相等相等的，則的，則移動元素的期望值移動元素的期望值為為：21)(11ninnEnidl算法時間復(fù)雜度算法時間復(fù)雜度為為: : O(n)BIT GaoChunXiaoNotes of Data Structure北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表24LocateElem_Sq(SqList L, ElemType e, St