線性表就是數據元素的排列像一條線一樣的表。線性表嚴格的定義是具有相同特性的數據元素組成的一個有限序列。其特征有3個：
不同於集合，線性表中可以出現值相同的元素。
線性表的邏輯結構一般表示為 ( a 0 , a 1 , ⋯ , a n − 1 ) (a_0,a_1,\cdots,a_{n-1}) (a0,a1,⋯,an−1)，用 n ( n ≥ 0 ) n(n\geq0) n(n≥0) 表示線性表的長度（即線性表中元素的個數）。當 n = 0 n=0 n=0 時，表示線性表是一個空表，不包含任何數據元素。
線性表的邏輯特征：每個元素最多只有一個前驅元素，也最多只有一個後繼元素。
數 據 對 象 ： D = { a i ∣ 0 ≤ i ≤ n − 1 , n ≥ 0 , a i 為 E 類 型 } 數 據 關 系 ： r = { < a i , a i + 1 > ∣ a i , a i + 1 ∈ D , i = 0 , ⋯ , n − 2 } 基 本 運 算 ： fromlist(a) ： 根 據 數 組 a 的 全 部 元 素 建 立 線 性 表 add(e) ： 將 元 素 e 添 加 到 線 性 表 的 末 尾 insert(i,e) ： 插 入 元 素 e 作 為 序 號 i 的 元 素 delete(i) ： 刪 除 序 號 為 i 的 元 素 getelem(i) ： 獲 取 序 號 為 i 的 元 素 setelem(i,e) ： 設 置 序 號 i 的 元 素 值 為 e getno(e) ： 求 線 性 表 中 第 一 個 值 為 e 的 元 素 的 序 號 getsize() ： 獲 取 線 性 表 的 長 度 display() ： 輸 出 線 性 表 的 所 有 元 素 \begin{aligned} &數據對象：D=\{a_i|0\leq i\leq n-1,n\geq0,a_i為E類型\} \\ &數據關系：r=\{<a_i,a_{i+1}>|a_i,a_{i+1}\in D,i=0,\cdots,n-2\} \\ &基本運算：\\ &\quad \text{fromlist(a)}：根據數組a的全部元素建立線性表 \\ &\quad \text{add(e)}：將元素e添加到線性表的末尾 \\ &\quad \text{insert(i,e)}：插入元素e作為序號i的元素 \\ &\quad \text{delete(i)}：刪除序號為i的元素 \\ &\quad \text{getelem(i)}：獲取序號為i的元素 \\ &\quad \text{setelem(i,e)}：設置序號i的元素值為e \\ &\quad \text{getno(e)}：求線性表中第一個值為e的元素的序號 \\ &\quad \text{getsize()}：獲取線性表的長度 \\ &\quad \text{display()}：輸出線性表的所有元素 \\ \end{aligned} 數據對象：D={ ai∣0≤i≤n−1,n≥0,ai為E類型}數據關系：r={ <ai,ai+1>∣ai,ai+1∈D,i=0,⋯,n−2}基本運算：fromlist(a)：根據數組a的全部元素建立線性表add(e)：將元素e添加到線性表的末尾insert(i,e)：插入元素e作為序號i的元素delete(i)：刪除序號為i的元素getelem(i)：獲取序號為i的元素setelem(i,e)：設置序號i的元素值為egetno(e)：求線性表中第一個值為e的元素的序號getsize()：獲取線性表的長度display()：輸出線性表的所有元素
線性表有兩種存儲結構：順序存儲和鏈式存儲，本文將主要講解順序存儲。
線性表的順序存儲是把線性表中的所有元素按照其邏輯順序依次存儲到存儲器中一塊連續的存儲空間。線性表的順序存儲結構稱為順序表。
接下來我們將采用Python中的列表來實現順序表。順序表通常會有一個最大容量 capacity，當要存儲的元素個數大於 capacity 時，我們可以對順序表進行擴容（例如將 capacity 擴大兩倍）。
class SqList:
def __init__(self, capacity):
self.capacity = capacity # 最大容量
self.data = [None] * self.capacity # 用於存儲數據
self.size = 0 # 順序表的元素個數
我們可以創建一個 resize 函數用來修改線性表的最大容量：
def resize(self, newcapacity):
assert newcapacity >= 0
if newcapacity >= self.capacity:
self.data = self.data + [None] * (newcapacity - self.capacity)
else:
self.data = self.data[:newcapacity]
self.capacity = newcapacity
給定列表 a，我們需要通過該列表來建立相對應的順序表。
def fromlist(self, a):
for i in range(len(a)):
# 出現上溢出時將容量擴大2倍
if self.size == self.capacity:
self.resize(self.size * 2)
# 因為self.size是從0開始遞增的
self.data[self.size] = a[i]
self.size += 1
時間復雜度為 O ( n ) \mathcal{O}(n) O(n)，其中 n n n 表示順序表中的元素個數。
def add(self, e):
# 防止溢出
if self.size == self.capacity:
self.resize(self.size * 2)
self.data[self.size] = e
self.size += 1
要在位置 i i i 處插入元素 e e e，我們需要將 self.data[i, i+1, ..., n-1] 的每個元素均後移一位。
def insert(self, i, e):
assert 0 <= i <= self.size
if self.size == self.capacity:
self.resize(self.size * 2)
for j in range(self.size, i, -1):
self.data[j] = self.data[j - 1]
self.data[i] = e
self.size += 1
平均時間復雜度： O ( n ) \mathcal{O}(n) O(n)。
要刪除位置 i i i 處的元素，我們需要將 self.data[i+1, ..., n-1] 的每個元素均前移一位。
def delete(self, i):
assert 0 <= i < self.size
for j in range(i, self.size - 1):
self.data[j] = self.data[j + 1]
self.size -= 1
# 自適應縮小容量以節省空間
if self.size < self.capacity / 2:
self.resize(self.capacity / 2)
平均時間復雜度： O ( n ) \mathcal{O}(n) O(n)。
def __getitem__(self, i):
assert 0 <= i < self.size
return self.data[i]
def __setitem__(self, i, x):
assert 0 <= i < self.size
self.data[i] = x
def getno(self, e):
for i in range(self.size):
if self.data[i] == e:
return i
# 未找到返回-1
return -1
def getsize(self):
return self.size
def display(self):
print(*self.data[:self.size])
sqlist = SqList(10)
sqlist.fromlist(list(range(10)))
sqlist.display()
# 0 1 2 3 4 5 6 7 8 9
sqlist.add(33)
sqlist.insert(3, 19)
sqlist.delete(0)
sqlist.display()
# 1 2 19 3 4 5 6 7 8 9 33
sqlist[10] = 3
print(sqlist[1])
# 2
print(sqlist.getno(3))
# 3
print(sqlist.getsize())
# 11
sqlist.display()
# 1 2 19 3 4 5 6 7 8 9 3
即若原始順序表為 ( 4 , 3 , 2 , 1 ) (4,3,2,1) (4,3,2,1)，翻轉後的順序表應為 ( 1 , 2 , 3 , 4 ) (1,2,3,4) (1,2,3,4)。
def reverse(sqlist):
i, j = 0, sqlist.getsize() - 1
while i < j:
sqlist[i], sqlist[j] = sqlist[j], sqlist[i]
i += 1
j -= 1
sqlist = SqList(5)
sqlist.fromlist(list(range(5)))
sqlist.display()
# 0 1 2 3 4
reverse(sqlist)
sqlist.display()
# 4 3 2 1 0
時間復雜度 O ( n ) \mathcal{O}(n) O(n)，空間復雜度 O ( 1 ) \mathcal{O}(1) O(1)。
設計一個算法從位置 i i i 開始刪除其後的 k k k 個元素（包括 i i i）。例如設 L = ( 1 , 2 , 3 , 4 , 5 ) , i = 1 , k = 2 L=(1,2,3,4,5),i=1,k=2 L=(1,2,3,4,5),i=1,k=2，則執行操作後 L = ( 1 , 4 , 5 ) L=(1,4,5) L=(1,4,5)。
顯然需要有 i ≥ 0 , k ≥ 1 i\geq0,k\geq1 i≥0,k≥1，刪除的最後一個元素索引為 i + k − 1 i+k-1 i+k−1，需滿足 0 ≤ i + k − 1 ≤ n − 1 0\leq i+k-1\leq n-1 0≤i+k−1≤n−1，即 1 ≤ i + k ≤ n 1\leq i+k\leq n 1≤i+k≤n。
def delete_k(sqlist, i, k):
assert i >= 0 and k >= 1 and 1 <= i + k <= sqlist.getsize()
for j in range(i + k, sqlist.getsize()):
sqlist[j - k] = sqlist[j]
sqlist.size -= k
sqlist = SqList(5)
sqlist.fromlist(list(range(5)))
sqlist.display()
# 0 1 2 3 4
delete_k(sqlist, 1, 2)
sqlist.display()
# 0 3 4
時間復雜度 O ( n ) \mathcal{O}(n) O(n)。
有序表是按元素值或某屬性值遞增或遞減排列的線性表。有序表是線性表的一個子集。有序順序表是有序表的順序存儲結構。對於有序表，可以利用其元素的有序性提高相關算法的效率，二路歸並就是有序表的一個經典算法。
考慮兩個遞增的有序順序表 A A A 和 B B B，設計一個算法將 A A A 和 B B B 合並在一起並構成一個新的遞增有序順序表 C C C。
我們可以設置兩個指針 i , j i,j i,j，用 i i i 遍歷 A A A，用 j j j 遍歷 B B B。初始時， i = j = 0 i=j=0 i=j=0。每次比較 i i i 和 j j j 所指的元素的大小，將較小者添加到 C C C 中，且向右移動指向較小者的指針，不斷重復這個操作。
def merge(A, B):
C = SqList(A.capacity + B.capacity)
i = j = 0
while i < A.getsize() and j < B.getsize():
if A[i] < B[j]:
C.add(A[i])
i += 1
else:
C.add(B[j])
j += 1
# 若i,j並非同時到達終點，則必會有一個順序表還殘留元素，此時只需將這些元素全部加入C中即可
while i < A.getsize():
C.add(A[i])
i += 1
while j < B.getsize():
C.add(B[j])
j += 1
return C
A = SqList(5)
A.fromlist(list(range(1, 11, 2)))
B = SqList(5)
B.fromlist(list(range(2, 11, 2)))
A.display()
# 1 3 5 7 9
B.display()
# 2 4 6 8 10
C = merge(A, B)
C.display()
# 1 2 3 4 5 6 7 8 9 10
class SqList:
def __init__(self, capacity):
self.capacity = capacity
self.data = [None] * self.capacity
self.size = 0
def resize(self, newcapacity):
assert newcapacity >= 0
if newcapacity >= self.capacity:
self.data = self.data + [None] * (newcapacity - self.capacity)
else:
self.data = self.data[:newcapacity]
self.capacity = newcapacity
def fromlist(self, a):
for i in range(len(a)):
if self.size == self.capacity:
self.resize(self.size * 2)
self.data[self.size] = a[i]
self.size += 1
def add(self, e):
if self.size == self.capacity:
self.resize(self.size * 2)
self.data[self.size] = e
self.size += 1
def insert(self, i, e):
assert 0 <= i <= self.size
if self.size == self.capacity:
self.resize(self.size * 2)
for j in range(self.size, i, -1):
self.data[j] = self.data[j - 1]
self.data[i] = e
self.size += 1
def delete(self, i):
assert 0 <= i < self.size
for j in range(i, self.size - 1):
self.data[j] = self.data[j + 1]
self.size -= 1
if self.size < self.capacity / 2:
self.resize(self.capacity / 2)
def __getitem__(self, i):
assert 0 <= i < self.size
return self.data[i]
def __setitem__(self, i, x):
assert 0 <= i < self.size
self.data[i] = x
def getno(self, e):
for i in range(self.size):
if self.data[i] == e:
return i
return -1
def getsize(self):
return self.size
def display(self):
print(*self.data[:self.size])
