文章目錄

• 線性表、順序表
• • 線性表概念
  • • 線性結構特點
  • 線性表概念
  • 兩種分類
  • 順序表代碼
  • 遍歷
  • 查找
  • 插入
  • 刪除
  • 逆置
  • 鏈表（用指針實現變長的先行存儲結構）
  • 特點
  • 習題

線性表、順序表

線性表概念

線性結構特點

存在唯一一個被稱為“第一個”的數據元素

存在唯一一個被稱為“最后一個”的數據元素

除“第一個”元素無前驅外，集合中每個元素均有且只有一個“直接”前驅；除“最后一個”元素無后繼外，集合中每個數據元素均有且只有一個“直接”后繼

線性表概念

線性表：是具有相同數據類型的n（n>=0)個數據元素的有限序列，通常記為：

前驅，后繼，表長，空表，首結點，尾結點

位序：ai（0<=i<=n-1)是線性表中元素，則稱i為數據元素ai在線性表中的位序（位置）

兩種分類

順序表（用一維數組實現定長的線性存儲結構 ）
按索引值從小到大存放在一片相鄰的連續區域，緊湊結構，存儲密度為1
順序表需要一塊連續的存儲空間，可以用一個數組實現。保存一個動態數組，需要三個變量：
data：指向線性表元素類型的指針
curlength：數組中元素個數（表長）
maxSize：數組規模（容量）

順序表代碼

遍歷

查找

插入

考慮情況：
1.位置
2插入情況

最好情況：i=curLength表末插入O(1)
最壞情況：i=0表頭插入O(n)

刪除

1.表為空
2.刪除是否合法

逆置

9個四次

鏈表（用指針實現變長的先行存儲結構）

單鏈表：

雙鏈表：

循環鏈表：

特點

順序表需要預先分配存儲空間，很難恰當預留空間

邏輯次序核物理次序的一致性，能夠按序號（下標）直接存取元素，具有隨機存取的特點

順序表在插入刪除時需要移動大量數據，因此其插入和刪除效率低

難于改變順序表的大小，需要重新船艦一個新的順序表，把原表里的數據復制到新表，然后釋放原表空間

順序表比較適合靜態的、經常做定位訪問的線性表

習題

總結

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

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