一、什麼是線性表

1、基本概念

線性表是具有相同特性的資料元素的一個有限序列。

所有資料元素型別相同。

線性表是有限個數據元素構成的。

線性表中資料元素與位置相關，即每個資料元素有唯一的序號。

線性表中每個元素ai的唯一位置透過序號或者索引i表示，為了演算法設計方便，將邏輯序號和儲存序號統一，均假設從0開始，這樣含n個元素的線性表的元素序號i滿足0≤i≤n-1。

2、線性表的抽象資料型別描述

3、線性表的順序儲存結構

（1）線性表的順序儲存結構—順序表

data陣列存放線性表元素

data陣列的容量（存放最多的元素個數）為capacity。

線性表中實際資料元素個數size

（2）線性表基本運算演算法在順序表中的實現

整體建立順序表：由含若干個元素的陣列a的全部元素整體建立順序表，即依次將a中的元素新增到data陣列的末尾，當出現上溢位時按實際元素個數size的兩倍擴大容量。

順序表基本運算演算法

將元素e新增的線性表末尾Add(e)

求線性表的長度getsize()

求線性表中序號為i的元素GetElem(i)

設定線性表中序號為i的元素SetElem(i，e)

求線性表中第一個值為e的元素的邏輯序號GetNo(e)

線上性表中插入e作為第i個元素Insert(i，e)

擴容運算resize()在n次插入中僅僅呼叫一次，其平攤時間為O(1)，上述演算法時間分析中可以忽略它。

輸出線性表所有元素display()

4、順序表的應用演算法設計示例

（1）基於順序表基本操作的演算法設計

練習1：對於含有n個整數元素的順序表L，設計一個演算法將其中所有元素逆置。

例如L=(1，2，3，4，5)，逆置後L=(5，4，3，2，1)。並給出演算法的時間複雜度和空間複雜度。

（2）基於整體建立順序表的演算法設計

（3）有序順序表的演算法設計

有序表是指按元素值或者某屬性值遞增或者遞減排列的線性表，有序表是線性表的一個子集。

有序順序表是有序表的順序儲存結構。

對於有序表可以利用其元素的有序性提高相關演算法的效率，二路歸併就是有序表的一種經典演算法。

練習：有兩個按元素值遞增有序的整數順序表A和B，設計一個演算法將順序表A和B的全部元素合併到一個遞增有序順序表C中。並給出演算法的時間複雜度和空間複雜度。

二路歸併：

演算法中儘管有多個while迴圈語句，但恰好對順序表A、B中每個元素均訪問一次，所以時間複雜度為O(n+m) 。

演算法中需要在臨時順序表C中新增n+m個元素，所以演算法的空間複雜度也是O(n+m)。

二路歸併中，若兩個有序表的長度分別為n、m，演算法的主要時間花費在元素比較上，那麼比較次數是多少呢？

最好的情況下，整個歸併中僅僅是較長表的第一個元素與較短表每個元素比較一次，此時元素比較次數為MIN(n，m)（為最少元素比較次數），如A=(1，2，3)，B=(4，5，6，7，8)，只需比較3次。

最壞的情況下，這n+m個元素均兩兩比較一次，比較次數為n+m-1（為最多元素比較次數），如A=(1，3，5，7)，B=(2，4，6)，需要比較6次。