（三）線性表 -- 上

1. 線性表的定義

• 線性表（List）

  零個或多個資料元素的有限序列。

首先它是一個序列。也就是說，元素之間是有順序的，若元素存在多個，則第一個元素無前驅，最後一個元素無後繼，其他每個元素都有且隻有一個前驅和後繼。

然後，線性表強調是有限的。

如果用數學語言來進行定義，如下：

若将線性表記為（ a 1 a_1 a1​, …, a i − 1 a_{i-1} ai−1​, a i a_i ai​, a i + 1 a_{i+1} ai+1​, …, a n a_n an​），則表中 a i − 1 a_{i-1} ai−1​,領先于 a i a_i ai​， a i a_i ai​領先于 a i + 1 a_{i+1} ai+1​，稱 a i − 1 a_{i-1} ai−1​是 a i a_i ai​的直接前驅元素， a i + 1 a_{i+1} ai+1​是 a i a_i ai​的直接後繼元素。

當i=1, 2, …, n-1時， a i a_i ai​有且僅有一個直接後繼，當i=2, 3, …, n時， a i a_i ai​有且僅有一個直接前驅。如下圖所示。

是以，線性表元素的個數n(n>=0)定義為線性表的長度，當n=0時，稱為空表。

在非空表中的每個資料元素都有一個确定的位置。 a i a_i ai​時第i個資料元素，稱i為資料元素 a i a_i ai​線上性表中的位序。

班級同學的點名冊，是線性表。

每一個元素除學生的學号外，還可以有同學的姓名、性别等，這其實就是資料項。

在較複雜的線性表中，一個資料元素可以由若幹個資料項組成。

2. 線性表的抽象資料類型

線性表的抽象資料類型定義如下：

要實作兩個線性表集合A和B的并集操作，隻要循環集合B中的每個元素，判斷目前元素是否存在A中，若不存在，則插入到A中即可。

假設La表示集合A，Lb表示集合B，則實作的代碼如下：

void union (List *La, List Lb) {
	int La_len, Lb_len, i;
	ElemType e;
	La_len = ListLength(La);
	Lb_len = ListLength(Lb);
	for (i=1; i<=Lb_len; i++) {
		GetElem(Lb, i, e);
		if (!LocateElem(La, e, equal)) {
			ListInsert(La, ++La_len, e);
		}
	}
}
           

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

3.1 順序存儲定義

線性表的兩種實體結構的第一種——順序存儲結構。

• 線性表的順序存儲結構

  指的是用一段位址連續的存儲單元依次存儲線性表的資料元素。

線性表( a 1 a_1 a1​, a 2 a_2 a2​,…, a n a_n an​) 的順序存儲示意圖如下：

3.2 順序存儲方式

既然線性表的每個資料元素的類型都相同，是以可以用C語言的一維數組來實作順序存儲結構，即把第一個資料元素存到數組下

标為0的位置中，接着把線性表相鄰的元素存儲在數組中相鄰的位置。

存儲空間的起始位置非常關鍵。

線性表中，估算這個線性表的最大存儲容量，建立一個數組，數組的長度就是這個最大存儲容量。

線性表的目前長度不能超過存儲容量，即數組的長度。

線性表的順序存儲的結構代碼：

#define MAXSIZE 20

typedef int ElemType;

typedef struct {
	ElemType data[MAXSIZE];
	int length;
} SqList;
           

描述順序存儲結構需要三個屬性：

(1) 存儲空間的起始位置。數組data，它的存儲位置就是存儲空間的存儲位置。

(2) 線性表的最大存儲容量，數組長度MaxSize。

(3) 線性表的目前長度，length。

3.3 資料長度與線性表長度差別

數組的長度是存放線性表的存儲空間的長度，存儲配置設定後這個量是一般是不變的。

線性表的長度是線性表中資料元素的個數，随着線性表插入和删除操作的進行，這個量是變化的。

在任意時刻，線性表的長度應該小于等于數組的長度。

3.4 位址計算方法

線性表的第i個元素是要存儲在數組下标為i-1的位置，即資料元素的序号和存放它的數組下标之間存在對應關系(如圖3-4-3所示)：

存儲器中的每個存儲單元都有自己的編号，這個編号稱為位址。

假設占用的是c個存儲單元，那麼線性表中第i+1個資料元素的存儲位置和第i個資料元素的存儲位置滿足下列關系(LOC表示獲得存儲位置的函數)：

LOC( a i + 1 a_{i+1} ai+1​)=LOC( a i a_{i} ai​)+c

是以對于第i個資料元素 a i a_i ai​的存儲位置可以由 a 1 a_1 a1​推算得出：

LOC( a i a_{i} ai​)=LOC( a 1 a_{1} a1​)+(i-1)*c

從下圖來了解：

對每個線性表位置的存入或者取出資料，對于計算機來說都是相等的時間，也就是一個常數，是以用時間複雜度的概念來說，它的存取時間性能為O[1]。通常把具有這一特點的存儲結構稱為随機存取結構。

4. 順序存儲結構的插入與删除

4.1 獲得元素操作

實作GetElem操作，即将線性表L中的第1個位置元素值傳回，隻要i的數值在數組下标範圍内，就是把數組第1-1下标的值傳回即可。代碼如下：

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;

Status GetElem(SqList L, int i, ElemType *e) {
	if (L.length==0 || i<1 || i>L.length) {
		return ERROR
	}
	*e = L.data[i-1];
	return OK;
}
           

4.2 插入操作

如果要實作ListInsert(*L,i,e)，即線上性表L中的第1個位置插入新元素e。

插入算法的思路如下：

• 如果插入位置不合理，抛出異常；
• 如果線性表長度大于等于數組長度，則抛出異常或動态增加容量；
• 從最後一個元素開始向前周遊到第i個位置，分别将它們都向後移動一個位置；
• 将要插入元素填入位置i處；
• 表長加1

實作代碼如下：

Status ListInsert(SqList *L, int i, ElemType e) {
 	int k;
 	if (L->length==MAXSIZE)
 		return ERROR
 	if (i<1 || i>L->length+1)
 		return ERROR
 	if (i<=L->length) {
 		for (k<=L->length-1;k>=i-1;k--) {
 			L->data[k+1]=L->data[k];
 		}
 	}
 	L->data[i-1]=e;
 	L->length++;
 	return OK;
}
           

4.3 删除操作

删除算法的思路：

• 如果删除位置不合理，抛出異常；
• 取出删除元素；
• 從删除元素位置開始周遊到最後一個元素位置，分别将它們都向前移動一個位置；
• 表長減1。

實作代碼如下：

Status ListDelete(SqList *L, int i, ElemType *e) {
	int k;
	if (L->length==0)
		return ERROR
	if (i<1 || i>L->length)
		return ERROR
	*e=L->data[i-1];
	if (i<L->length) {
		for (k=i; k<L->length; k++) {
			L->data[k-1]=L->data[k];
		}
	}
	L->length--;
	return OK;
}
           

分析一下插入和删除的時間複雜度：

線性表的順序存儲結構，在存、讀資料時，不管是哪個位置，時間複雜度都是O(1)；

而插入或删除時，時間複雜度都是O(n)。

4.4 線性表順序存儲結構的優缺點

參考

《大話資料結構》 —— 3 線性表