北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表順序表.ppt

1 第二章線性表 2 本章內(nèi)容 2 1線性表的類型定義2 2線性表類型的實(shí)現(xiàn) 順序映象2 3線性表類型的實(shí)現(xiàn) 鏈?zhǔn)接诚?3 2 2 1順序表示及其特點(diǎn) 2 2 2數(shù)據(jù)結(jié)構(gòu)定義2 2 3順序表的初始化操作2 2 4順序表的插入操作2 2 5順序表的刪除操作2 2 6用順序表實(shí)現(xiàn)合并操作LC LA LB 4 2 2 1順序表示及其特點(diǎn) 順序映象 以x的存儲位置和y的存儲位置之間某種關(guān)系表示邏輯關(guān)系 最簡單的一種順序映象方法是 用一組地址連續(xù)的存儲單元依次存放線性表中的數(shù)據(jù)元素 5 2 2 1順序表示及其特點(diǎn) 以 存儲位置相鄰 表示有序?qū)?LOC ai LOC ai 1 CC是一個數(shù)據(jù)元素所占存儲量所有數(shù)據(jù)元素的存儲位置均取決于第一個數(shù)據(jù)元素的存儲位置LOC ai LOC a1 i 1 C 小結(jié) 順序表的特點(diǎn) 用連續(xù)的存儲單元存放線性表的元素 采用一維數(shù)組存放 元素存儲順序與元素的邏輯順序一致 讀寫元素方便 通過下標(biāo)即可指定位置 6 7 2 2 2順序表數(shù)據(jù)結(jié)構(gòu)定義 defineLIST INIT SIZE80 線性表存儲空間的初始分配量 defineLISTINCREMENT10 線性表存儲空間的分配增量 typedefstruct ElemType elem 存儲空間基址intlength 當(dāng)前長度intlistsize 當(dāng)前分配的存儲容量 以sizeof ElemType 為單位 SqList 俗稱順序表 8 01 i 2i 1 n 1 順序表 L 注意 由于數(shù)組的下標(biāo)從 0 開始 表中第i個元素是L elem i 1 typedefstruct ElemType elem intlength intlistsize SqList 順序表 SqListL 9 2 2 3順序表的初始化操作 StatusInitList Sq SqList InitList Sq typedefstruct ElemType elem intlength intlistsize SqList 順序表 10 2 2 4順序表的插入操作 ListInsert L i e 插入元素在順序表L的第i個元素之前插入新的元素e 把e插入到第i個元素的位置i的合法范圍為1 i L length 1 01 i 2i 1 n 1 e 11 操作的過程 ListInsert L 6 30 12 操作的過程 ListInsert L 6 30 q p 1 p p p 1 p q e p q 插入操作 13 操作步驟判斷插入位置是否合法 1 i L length 1初始化指針循環(huán) 從表尾開始 依次將第i 1個元素之后的元素順序后移一位將新元素e寫入到第i個位置將表的長度加1 14 StatusListInsert Sq SqList ListInsert Sq 算法時(shí)間復(fù)雜度取決于 移動元素的次數(shù) 15 插入操作的算法復(fù)雜度 考慮移動元素的平均情況 假設(shè)在第i個元素之前插入的概率為pi 則在長度為n的線性表中插入一個元素所需移動元素次數(shù)的期望值為 若假定在線性表中任何一個位置上進(jìn)行插入的概率都是相等的 則移動元素的期望值為 算法時(shí)間復(fù)雜度為 O n 16 if L length L listsize 當(dāng)前存儲空間已滿 增加分配newbase ElemType realloc L elem L listsize LISTINCREMENT sizeof ElemType if newbase exit OVERFLOW 存儲分配失敗L elem newbase 新基址L listsize LISTINCREMENT 增加存儲容量 如果存儲空間已滿怎么辦 17 程序設(shè)計(jì)方法的兩點(diǎn)說明 先考慮一般情況 后考慮特殊情況一般不用基本操作實(shí)現(xiàn)其他基本操作 18 兩個實(shí)際問題 錯誤的類型 正常處理的錯誤 是一些常見 合理的錯誤 如 用戶輸入的錯誤 通過錯誤代碼返回 意外錯誤 拋出Exception 通過try catch撲捉 初始化問題 數(shù)據(jù)結(jié)構(gòu)沒有初始化就使用往往也是錯誤 但無法判定 在C 和Java中通過構(gòu)造函數(shù)解決 19 2 2 5順序表的刪除操作 ListDelete L i e 刪除元素刪除線性表中第i個元素 并將刪除的元素方在e中i的合法范圍為1 i L length 刪除操作 20 操作的過程 ListDelete L 5 e p e p p p 1 p p L elem L length 1 p p 1 p 21 操作步驟判斷插入位置是否合法 1 i L length初始化指針將第i個元素的值賦給變量e循環(huán) 從第i 1個元素開始 依次將后面的元素順序前移一位將表的長度減1 22 StatusListDelete Sq SqList ListDelete Sq 算法時(shí)間復(fù)雜度取決于 移動元素的次數(shù) 23 刪除操作的算法復(fù)雜度 考慮移動元素的平均情況 假設(shè)在刪除第i個元素的概率為pi 則在長度為n的線性表中刪除一個元素所需移動元素次數(shù)的期望值為 若假定在線性表中任何一個位置上進(jìn)行刪除的概率都是相等的 則移動元素的期望值為 算法時(shí)間復(fù)雜度為 O n 24 LocateElem Sq SqListL ElemTypee Status compare ElemType ElemType e 38 i 1 2 3 4 1 8 50 基本操作 將順序表中的元素逐個和給定值e相比較 2 2 6定位操作 循環(huán)結(jié)束標(biāo)志 找到e或者p超過表尾的地址 25 2 2 6定位操作 請大家寫出順序表的定位操作的操作步驟和程序要求 在順序表中查詢第一個滿足判定條件的數(shù)據(jù)元素 若存在 則返回它的位序 否則返回0 算法時(shí)間復(fù)雜度為 O n 小結(jié) 順序表的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)不需要附加空間隨機(jī)存取任一個元素 根據(jù)下標(biāo) 缺點(diǎn)很難估計(jì)所需空間的大小開始就要分配足夠大的一片連續(xù)的內(nèi)存空間更新操作代價(jià)大 26 27 END