線性表
- 開篇前先了解一下什么是
線性表
線性表是最簡單的資料結構，是一些相同特征的元素的
有限序列，在邏輯結構上每個元素就像被一條線串聯起來，物理結構，則是每個元素在計算機中的聯系
疑惑
- 開篇前請帶著一下幾個疑惑看文章
- 順序表的優點與缺點
- 鏈表的優點與缺點
- 他們的區別
順序表
- 順序表他是由多個相同性質的元素組成，通常是用陣列來實作的
- 如圖所示
- 順序表一般有倆種
-
- 靜態
-
- 動態
靜態
靜態就是創建好之后就能
隨意改變大小，開大了會造成浪費，開小了又不夠，改變也只能從源頭改變，非常局限
動態
動態則是
需要的時候申請一塊(由malloc，calloc，realloc動態申請開辟的)，開大減少了浪費，開小不夠的尷尬場面，
舉一個生活中的例子：
- 靜態就好比是你花錢去買一個儲物間一樣，多少錢就買都大空間
- 動態就好比給你一塊地和鐵鏟，你要放多少東西，就造多大的儲物室
實作順序表
- 在這個期間他的優缺的會被無限的放大
- 他們都基于動態基礎上
- 請看我寫的另篇實作順序表
鏈表
- 鏈表是是邏輯上連續存放每個元素就像被
鏈條穿插在一起，但是物理啊結構上非連續，前面的元素存著下一個元素的地中，(我稱他為羈絆表)
邏輯結構
他們就像是被一條鏈條拴在一起
如圖所示
物理結構
上個元素存著下一個元素的地址通過地址可以找到他
鏈表的種類
- 他種類繁多
- 有
八種 - 常用的就是
單鏈表和雙向帶頭鏈表 - 由圖所示
簡單介紹各種鏈表
- 如圖所示
實作單向不回圈鏈表/ 實作帶頭雙向回圈鏈表
單向不回圈鏈表/ 實作帶頭雙向回圈鏈表
- 他們的優勢是啥？
- 劣勢又是啥？
- 帶著疑惑看著篇鏈表曲二，三
鏈表/順序表的優缺點
- 順序表的尾插效率高，銷毀也快，但是
頭插，任意位置效率低，會造成一定空間浪費 - 單鏈表的尾插與頭插效率高，但是他有一個劣勢就是他找不到前一個但是銷毀一般
效率O(N)，需要的時候申請 - 雙向帶頭回圈鏈表，可以說是單鏈表的優化版，但是他實作起來也是
比單鏈表復雜，可以找到前面的節點，但是依然銷毀沒有順序表那樣效率高
| 不同 | 順序表 | 鏈表 |
|---|---|---|
| 存盤空間上 | 物理上聯系 | 邏輯上連續 |
| 隨機訪問 | 支持:O(1) | 不支持 |
| 任意位置插入或者洗掉元素 | 挪動資料，覆寫 | 修改指標指向 |
| 插入 | 插入不夠擴容一塊空間 | 想插入時申請一塊 |
| 應用場景 | 頻繁訪問+元素高效儲存 | 任意位置插入+洗掉 |
| 快取利用率 | 高 | 低 |
鏈表/順序表oj
- 曲四是升華篇，他們都基于增刪查改的基礎上
- 曲四
end
- 相信經過上面的層層洗禮你已經對鏈表順序表又一個深刻的見解了(記得看他們的實作方法,點跳轉鏈接即可實作順序表，鏈表曲二，三，)
- 但是革命的大軍依舊沒有停止，多去leetcode刷題喲，加深記憶不說了leetcode向我招手呢
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/294707.html
標籤：其他