• 線性表的定義

零個或多個數(shù)據(jù)元素的有限序列小作。

• a(i-1)是ai的直接前驅(qū)元素衷咽，a（i+1）是ai的直接后繼元素
• 當(dāng)線性表元素的個數(shù)為0時悬嗓，稱為空表

• 線性表的順序存儲結(jié)構(gòu)

  • 順序存儲定義
    線性表的順序存儲結(jié)構(gòu)狞换，指的是用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素避咆。
  • 數(shù)據(jù)長度和線性表長度的區(qū)別
    • 數(shù)組的長度是存放線性表的存儲空間的長度，存儲分配后這個量一般是不會變的修噪。
    • 任意時刻查库，線性表的長度應(yīng)該小于等于數(shù)組的長度。
  • 地址計算方法
    公式 ai= a1 + (i-1)*c
    c是規(guī)定的存儲單元黄琼。

• 順序存儲結(jié)構(gòu)的插入和刪除

  • 獲得元素操作

圖片.png

圖片.png

• 插入操作

圖片.png

• 刪除操作

圖片.png

圖片.png

• 線性表順序存儲結(jié)構(gòu)的優(yōu)缺點
  • 優(yōu)點
    無須為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間樊销。
    可以快速地存取表中任一位置的元素
  • 缺點
    插入和刪除操作需要移動大量元素
    當(dāng)線性表長度變化較大時，難以確定存儲空間的容量
    造成存儲空間的碎片

• 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

  • 順序存儲結(jié)構(gòu)不足的解決辦法
    鏈表
  • 線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義
    為了表示每個數(shù)據(jù)元素ai與其直接后繼元素a（i+1）之間的邏輯關(guān)系脏款，對數(shù)據(jù)元素ai來說围苫，除了存儲其本身的信息之外，還需存儲一個指示其直接后繼的信息撤师，我們把存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域剂府，把存儲直接后繼位置的域稱為指針域，指針域中存儲的信息稱做指針或鏈剃盾。這兩部分信息組成數(shù)據(jù)元素ai的存儲映像腺占，稱為結(jié)點（Node）
    n個結(jié)點鏈結(jié)成一個鏈表淤袜，即線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，因為此鏈表的每個結(jié)點中包含一個指針域衰伯，所以叫做單鏈表铡羡。
    • 我們把鏈表第一個結(jié)點的存儲位置叫做頭指針。
    • 最后一直指針是NULL
    • 第一結(jié)點是頭結(jié)點嚎研。
  • 頭指針與頭結(jié)點的異同
    • 頭指針
      頭指針是指鏈表指向第一個結(jié)點（實際上是第二個蓖墅，因為還有頭結(jié)點）的指針，若鏈表有頭結(jié)點临扮，則是指向頭結(jié)點的指針论矾。
      頭指針具有標(biāo)識作用，所以常用頭指針冠以鏈表的名字
      無論鏈表是否為空杆勇，頭指針均不為空贪壳。頭指針是鏈表的必要元素
    • 頭結(jié)點
      頭結(jié)點是為了操作的統(tǒng)一和方便而設(shè)立的，放在第一元素的結(jié)點之前蚜退，其數(shù)據(jù)域一般無意義闰靴。
      有了頭結(jié)點，對在第一元素結(jié)點前插入結(jié)點和刪除第一結(jié)點钻注，其操作與其它結(jié)點的操作就統(tǒng)一了
      頭結(jié)點不一定是鏈表必須要素

• 單鏈表的讀取

圖片.png

圖片.png

圖片.png

• 單鏈表的插入和刪除

  • 單鏈表的插入

圖片.png

圖片.png

• 單鏈表的刪除

圖片.png

圖片.png

圖片.png

• 對于插入或刪除數(shù)據(jù)越頻繁的操作蚂且，單鏈表的效率優(yōu)勢就越明顯。

• 單鏈表的整表創(chuàng)建

  • 頭插入

圖片.png

圖片.png

圖片.png

• 尾插法

圖片.png

圖片.png

• 單鏈表的整表刪除

圖片.png

圖片.png

• 單鏈表結(jié)構(gòu)與順序結(jié)構(gòu)優(yōu)缺點

  • 存儲分配方式
    • 順序結(jié)構(gòu)用一段連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素
    • 單鏈表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)幅恋，用一組任意的存儲單元存放線性表的元素
  • 時間性能
    • 查找
      • 順存儲結(jié)構(gòu)O(1)
      • 單鏈表O(n)
    • 插入和刪除
      • 順序存儲結(jié)構(gòu)需要平均移動表長一半的元素杏死，時間為O(n)
      • 單鏈表在線出某位置指針后，插入和刪除時間為O(1)
    • 空間性能
      • 順序存儲結(jié)構(gòu)需要預(yù)分配存儲空間捆交，分大了淑翼，浪費，分小易溢出品追。
      • 單鏈表不需要分配存儲空間玄括，只要有就可以分配，元素個數(shù)也不受限制肉瓦。

• 靜態(tài)鏈表

由兩個數(shù)據(jù)域組成遭京，data和cur。也就是說泞莉，數(shù)組的每一個下標(biāo)都對應(yīng)一個data和一個cur哪雕。數(shù)據(jù)域data，用來存放數(shù)據(jù)元素戒财，也就是通常外面處理的數(shù)據(jù)热监；而游標(biāo)cur相當(dāng)于單鏈表中的next指針。存放該元素
用數(shù)組描述的鏈表叫做靜態(tài)鏈表饮寞。這種描述方法還有起名叫做游標(biāo)實現(xiàn)法孝扛。
插入

圖片.png

刪除

• 靜態(tài)鏈表的插入操作

圖片.png

圖片.png

圖片.png

• 靜態(tài)鏈表的刪除操作

圖片.png

圖片.png

圖片.png

圖片.png

• 靜態(tài)鏈表的優(yōu)缺點

  • 優(yōu)點
    在插入和刪除操作時列吼，只需要修改游標(biāo)，不需要移動元素苦始，從而改進(jìn)了在順序存儲結(jié)構(gòu)中的插入和刪除操作需要移動大量元素的缺點寞钥。
  • 缺點
    • 沒用解決連續(xù)存儲分配帶來的表長難以確定的問題。
    • 失去了順序存儲結(jié)構(gòu)隨機存取的特性陌选。

• 循環(huán)鏈表

將單鏈表中終端結(jié)點的指針端由空指針改為指向頭結(jié)點理郑，就使整個單鏈表形成一個環(huán)，這種頭尾相接的單鏈表稱為單循環(huán)鏈表咨油，簡稱循環(huán)鏈表您炉。
兩個循環(huán)鏈表的合并

圖片.png

• 雙向鏈表

雙向鏈表是在單鏈表的每個結(jié)點中，再設(shè)置一個指向其前驅(qū)結(jié)點的指針域役电。

插入

圖片.png

刪除

圖片.png