線性表的定義和基本操作

線性表是具有相同數據類型的(n≥0)個數據元素的有限序列，其中n為表長，當n=0時線性表是一個空表。若用L命名線性表，則其中一般表示為：L=(a1,a2,a3,··· ,an)。除第一個元素外，每個元素有且僅有一個直接前驅。除最后一個元素外，每個元素有且僅有一個直接后繼。
注意： 線性表是一種邏輯結構，表示元素之間一對一的相鄰關系。順序表和鏈表是指存儲結構

順序表

順序表的定義
線性表的順序存儲又稱順序表。它是用一組地址連續的存儲單元依次存儲線性表中的數據元素，從而使得邏輯上相鄰的兩個元素在物理位置上也相鄰。順序表的特點是表中元素的邏輯順序與其物理順序相同

• 特點：
  1. 順序表最主要的特點是隨機訪問，即通過首地址和元素序號可在時間O(1)內找到指定的元素
  2. 順序表的 存儲密度高 ，每個結點只存儲數據元素
  3. 順序表邏輯上相鄰的元素物理上也相鄰，所以插入和刪除操作需要移動大量元素

---

順序表的基本操作

• 插入操作
  1. 最好情況：在表尾插入，元素后移語句將不執行，時間復雜度為O(1)
  2. 最壞情況：在表頭插入，元素后移語句將執行n次，時間復雜度為O(n)
  3. 平均情況：在長度為n的線性表中插入一個結點時，所需要移動結點的平均次數為n/2，時間復雜度為O(n)
• 刪除操作：
  1. 最好情況：刪除表尾元素，無須移動元素，時間復雜度為O(1)
  2. 最壞情況：刪除表頭元素，需移動除表頭元素外的所有元素，時間復雜度為O(n)
  3. 平均情況：在長度為n的線性表中刪除一個結點時，所需要移動結點的平均次數為(n-1)/2，線性表刪除算法的平均時間復雜度為O(n)
• 按值查找
  1. 最好情況：查找的元素就在表頭，僅需比較一次，時間復雜度為O(1)
  2. 最壞情況：查找的元素在表尾或不存在時，需要比較n次，時間復雜度為O(n)
  3. 平均情況：在長度為n的線性表中查找e元素的平均比較次數為(n+1)/2，時間復雜度為O(n)

---

線性表的鏈式表示

順序表可以隨時存取表中的任意一個元素，但插入和刪除操作需要移動大量元素。鏈式存儲線性表時，不需要使用地址連續的存儲單元，即不要求邏輯上相鄰的元素在物理位置上也相鄰，他通過“鏈”建立起數據元素之間的邏輯關系因此插入和刪除操作不需要移動元素，而只修改指針，但也會失去順序表可隨機存儲取的有優點

單鏈表的定義
線性表的鏈式存儲又稱為單鏈表，它是指通過一組任意的存儲單元來存儲線性表中的數據元素。為了建立數據元素之間的線性關系，對每個鏈表結點，除存放元素自身的信息外，還需要存放一個指向后繼的指針

• 其中data為數據域，存放數據元素。為指針域，存放其后后繼結點的地址
• 利用單鏈表可以解決順序表需要大量連續存儲單元的缺點，但單鏈表附加指針域，也存在浪費存儲空間的缺點，由于單鏈表的元素離散地分布在存儲空間中，所以 單鏈表是非隨機存取的存儲結構 ，不能直接找到表中某個特點的節點。查找某個特定的結點時，需要從表頭開始遍歷，依次查找
• 通常用頭指針來標識一個單鏈表，單鏈表L，頭指針為NULL時表示一個空表。為了操作上的方便，在單鏈表第一個結點之前附加一個結點，稱為頭結點。頭結點的數據域可以不設任何信息，也可以記錄表長等信息。頭結點的指針域指向線性表的第一個元素結點

判斷單鏈表是否為空的判斷條件：

• 帶頭結點：L—>next==NULL
• 不帶頭結點：L==NULL