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

《北京理工大學數(shù)據(jù)結構課件線性表順序表.ppt》由會員分享，可在線閱讀，更多相關《北京理工大學數(shù)據(jù)結構課件線性表順序表.ppt（27頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1 第二章線性表 2 本章內容 2 1線性表的類型定義2 2線性表類型的實現(xiàn) 順序映象2 3線性表類型的實現(xiàn) 鏈式映象 3 2 2 1順序表示及其特點 2 2 2數(shù)據(jù)結構定義2 2 3順序表的初始化操作2 2 4順序表的插入操作2 2 5順序表的刪除操作2 2 6用順序表實現(xiàn)合并操作LC LA LB 4 2 2 1順序表示及其特點 順序映象 以x的存儲位置和y的存儲位置之間某種關系表示邏輯關系 最簡單的一種順序映象方法是 用一組地址連續(xù)的存儲單元依次存放線性表中的數(shù)據(jù)元素 5 2 2 1順序表示及其特點 以 存儲位置相鄰 表示有序對即 LOC ai LOC ai 1 CC是一個數(shù)據(jù)元素所占存儲量所有數(shù)據(jù)元素的存儲位置均取決于第一個數(shù)據(jù)元素的存儲位置LOC ai LOC a1 i 1 C 小結 順序表的特點 用連續(xù)的存儲單元存放線性表的元素 采用一維數(shù)組存放 元素存儲順序與元素的邏輯順序一致 讀寫元素方便 通過下標即可指定位置 6 7 2 2 2順序表數(shù)據(jù)結構定義 defineLIST INIT SIZE80 線性表存儲空間的初始分配量 defineLISTINCREMENT10 線性表存儲空間的分配增量 typedefstruct ElemType elem 存儲空間基址intlength 當前長度intlistsize 當前分配的存儲容量 以sizeof ElemType 為單位 SqList 俗稱順序表 8 01 i 2i 1 n 1 順序表 L 注意 由于數(shù)組的下標從 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ù) 15 插入操作的算法復雜度 考慮移動元素的平均情況 假設在第i個元素之前插入的概率為pi 則在長度為n的線性表中插入一個元素所需移動元素次數(shù)的期望值為 若假定在線性表中任何一個位置上進行插入的概率都是相等的 則移動元素的期望值為 算法時間復雜度為 O n 16 if L length L listsize 當前存儲空間已滿 增加分配newbase ElemType realloc L elem L listsize LISTINCREMENT sizeof ElemType if newbase exit OVERFLOW 存儲分配失敗L elem newbase 新基址L listsize LISTINCREMENT 增加存儲容量 如果存儲空間已滿怎么辦 17 程序設計方法的兩點說明 先考慮一般情況 后考慮特殊情況一般不用基本操作實現(xiàn)其他基本操作 18 兩個實際問題 錯誤的類型 正常處理的錯誤 是一些常見 合理的錯誤 如 用戶輸入的錯誤 通過錯誤代碼返回 意外錯誤 拋出Exception 通過try catch撲捉 初始化問題 數(shù)據(jù)結構沒有初始化就使用往往也是錯誤 但無法判定 在C 和Java中通過構造函數(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ù) 23 刪除操作的算法復雜度 考慮移動元素的平均情況 假設在刪除第i個元素的概率為pi 則在長度為n的線性表中刪除一個元素所需移動元素次數(shù)的期望值為 若假定在線性表中任何一個位置上進行刪除的概率都是相等的 則移動元素的期望值為 算法時間復雜度為 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)結束標志 找到e或者p超過表尾的地址 25 2 2 6定位操作 請大家寫出順序表的定位操作的操作步驟和程序要求 在順序表中查詢第一個滿足判定條件的數(shù)據(jù)元素 若存在 則返回它的位序 否則返回0 算法時間復雜度為 O n 小結 順序表的優(yōu)缺點 優(yōu)點不需要附加空間隨機存取任一個元素 根據(jù)下標 缺點很難估計所需空間的大小開始就要分配足夠大的一片連續(xù)的內存空間更新操作代價大 26 27 END