線性表（List）：零個或多個數據元素的有限序列。

若將線性表記為（a1, ..., ai-1, ai , ai+1 , ..., an),則表中 ai-1 領先于ai , ai領先于ai+1,稱ai-1是ai的直接前驅元素，ai+1是ai的直接后繼元素。當i=1,2,...,n-1時，ai有且僅有一個直接后繼，當i=2,3,..,n時，ai有且僅有一個直接前驅。 ? 線性表元素的個數n(n>=0)定義為線性表的長度，當n=0時，稱為空表。 ? 在較復雜的線性表中，一個數據元素可以由若干個數組項組成。 ? 線性表的抽象數據類型定義如下： ADT 線性表（List) Data 線性表的數據對象集合為{a1,a2,...,an)，每個元素的類型均為DataType。其中，除第一個元素a1外，每一個元素有且只有一個直接前驅元素，除了最后一個元素an外，每一個元素有且只有一個直接后繼元素。數據元素之間的關系是一對一的關系。 Operation InitList(*L) 初始化操作，建立一個空的線性表L ListEmpty(L) 若線性表為空，返回true,否則返回false ClearList(*L) 將線性表清空 GetElem(L,i,*e) 將線性表L中第i個位置元素返回給e LocateElem（L,e) ? 在線性表L中查找與給定值e相等的元素，如果查找成功，返回該元素在表中序號表示成功，否則，返回0表示失敗 ListInsert(*L,i,e) 在線性表L中第i個位置插入新元素e ListDelete(*L,i,*e) 刪除線性表L中第i個位置元素，并用e返回其值 ListLength(L) ? 返回現象表L的元素個數 endADT ? 線性表的順序存儲結構，指的是用一段地址連續的存儲單元依次存儲線性表的數據元素。 ? 一維數組來實現順序存儲結構 ? 順序存儲結構需要三個屬性 # 存儲空間的起始位置：數組data,它的存儲位置就是存儲空間的存儲位置 # 線性表的最大存儲容量：數組長度MaxSize # 線性表的當前長度：length ? 數據長度與線性表長度的區別 數組的長度是存放線性表的存儲空間的長度，存儲分配后這個量一般是不變的 線性表的長度是線性表中數據元素的個數，隨著線性表插入和刪除操作的進行，這個量是變化的 在任意時刻，線性表的長度應該小于等于數組的長度。 ? 存儲器中的每個存儲單元都有自己的編號，這個編號稱為地址。 Loc(ai）=Loc(a1)+(i-1)*c ? 線性表順序存儲結構的優缺點 優點： #無須為表示表中元素之間的邏輯關系而增加額外的存儲空間 #可以快速得存取表中任一位置的元素 缺點 # 插入和刪除操作需要移動大量元素 #當線性表長度變化較大時，難以確定存儲空間的容量 #造成存儲空間的碎片 順序存儲結構的讀取、插入和刪除 讀取元素操作思路： 實現GetElem操作，即將線性表L中第i個位置元素返回 就程序而言，只要i的數值在數組中下標范圍內，就是把數組第i-1下標的值返回即可 插入算法的思路： # 如果插入位置不合理，拋出異常 # 如果線性表長度大于等于數組長度，則拋出異常或動態增加容量 # 從最后一個元素開始向前遍歷到第i個位置，分別將他們都向后移動一個位置 # 將要插入元素填入位置i處 # 表長+1 刪除算法的思路 # 如果刪除位置不合理，拋出異常 # 取出刪除元素 # 從刪除元素位置開始遍歷到最后一個元素位置，分別將他們向前移動一個位置 # 表長減1 ?

轉載于:https://www.cnblogs.com/yingmo/p/6148397.html

總結

以上是生活随笔為你收集整理的第三章 线性表---顺序存储结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。