小甲魚筆記：資料結構——線性表（一）線性表的順序存盤結構，線性表順序存盤結構的增，刪，插入元素操作

一、線性表的定義

線性表（List）：由零個或多個資料元素組成的有限序列，

TIPS:
1.線性表是一個序列，也就是說元素之間是有先來后到的，
2.若元素存在多個，則第一個元素無前驅，最后一個元素無后繼，其他元素只有一個前驅和后繼，
3.線性表是有限的，

用數學語言定義：
若將線性表記為（a1,a2,…ai-1,ai,ai+1,…an）則ai-1領先于ai，ai領先于ai+1,稱ai-1為ai的前驅元素，ai+1是ai的直接后繼元素，

所以線性表元素的個數n（n>0）定義為線性表長度，當n=0成為空表，

二、抽象資料型別

1. 定義：

一組性質相同的值的集合及定義在此集合上的一些操作總稱，
例：很多編程語言的整型，浮點型，字符型這些即為資料型別，
在計算機中，內容并非無限大，若計算1+1=2整型數字的加減乘除，不需要開辟很大空間，
若計算1.23456+2.78946這樣帶小數的就需要比較大的空間存放，故要對資料型別進行分類，分出多種型別來適合各種不同的計算條件差異，

例如：
C語言中資料型別分為兩類：
原子型別：不可以再分解的基本型別，例如：整型，浮點型，字符型…

結構型別：由若干個型別組合而成，是可以再分解的，例如：整形陣列是由若干個整形資料組成的

何為抽象：是指抽取出事物具有普遍性的本質，它要求抽出問題的特征而忽略非本質的細節，是對具體事物的一個概括，抽象是一種思考問題的方式，

2. 抽象資料型別

是指一個數學模型及定義在該模型上的一組操作，它的定義取決于它的一組邏輯特性，而與其他計算機內部如何表示和實作無關，

3. 為了方便江杰對抽象資料型別進行規范描述，我們給出了描述抽象資料型別進行規范描述，我們給出了描述抽象資料型別的標準格式，

 ADT: 資料型別
 DATA:資料元素之間的邏輯關系定義
 OPERATION:操作

二、線性表的抽象資料型別

1. 定義：
   ADT：線性表（List）

   Data：線性表的資料物件集合為（a1,a2…an），每個元素的型別均為DataType，其中，除第一個元素a1外，每一個元素有且只有一個前驅元素，除了最后一個元素an外，每個元素有且只有一個后繼元素，資料元素之間的關系是一對一的關系

   Operation：
   InitList(*L)：初始化操作，建立一個空的線性表L
   ListEmpty(L)：判讀線性表是否為空表，若線性表為空，回傳true，否則回傳false；
   ClearList(*L)：將線性表清空，
   GetElem(L,i,*e)：將線性表L中第i個位置元素值回傳給e；
   LocateElem(L,e)：在線性表L中查找與給定值e相等的元素，如果查找成功，回傳該元素在表中序號表示成功，否則，回傳0表示失敗，
   ListInsert(*L,i,e)：在線性表L中第i個元素位置插入新元素e；
   ListDelete(*L,I,*e)：用洗掉線性表L中第i個位置元素，并用e回傳其值，
   ListLength(L)：回傳線性表L的元素個數，

對于不同的應用，線性表的基本操作是不同的，上述為基礎Operation，對于實際問題中涉及的關于線性表的更多復雜操作，完全可以用這些基本操作的組合來實作，
例題：
若實作兩個線性表A，B的并集操作，即要是的集合A=AUB；
分析：
只要遍歷集合B中的每個元素，判斷當前元素是否存在A中，若不存在，則插入A中；所以我們需要用到上述的基本Operation，
ListLength(L);GetElem(L,i,*e)；LocateElem(L,e);ListInsert(*L,i,e);

偽代碼實踐：
void UnionL(List *La,list Lb){
	int La_len,Lb_len,i;
		ElemType e;
		La_len = ListLength(*La);
		Lb_len = ListLength(Lb);
		for(int i = 1;i<La_len;i++){
			//遍歷獲得Lb中的所有元素
			GetElem(Lb,i,&e);
			//判斷La中的中的元素是否與取出的e相同，若沒有則插入元素
		if(!LocateElem(*La,e)){
			ListInsert(La,++La_len,e);
		}
		}
}

三、線性表的順序存盤結構

1. 引入：
   線性表由兩種物理存盤結構：順序存盤結構和鏈式存盤結構，在此介紹順序存盤結構，

2. 順序存盤結構
   是指用一段地址連續的存盤單元依次存盤線性表的資料元素，例如：陣列，

   物理上的存盤方式就是在記憶體中找個初始地址，然后通過占位的形式，把一定記憶體空間給占掉，然后把相同資料型別的資料元素一次放在這塊空地上，（可以理解為一個團體共50人，在看電影時，第一位領頭人，去第一排第一個位置占座，剩余的49人依次跟在領頭人的后面，）

3. 線性表順序存盤的結構代碼

	 #define MAXSIZE 20
		typedef int ElemType;
	 	typedef struct{
		ElemType date[MAXSIZE];
		int length;//線性表當前長度
	}SqList;//對陣列進行封裝，增加了當前長度的變數

1. 總結
   順序存盤結構封裝需要三個屬性：
   ——存盤空間的起始位置，陣列data，它的存盤位置就是線性表存盤空間的存盤位置
   ——線性表的最大存盤容量：陣列的長度MaxSize.
   ——線性表的當前長度：length
   ——注意：陣列的長度與線性表的當前長度需要進行區別：陣列的長度時存放線性表的存盤空間的總長度，一般初始化后長度不變（一些編程語言可以將陣列長度變大，但一般情況下認為初始化長度不變），而線性表的當前長度時線性表中的元素的個數，是會變化的，

四、地址計算方法

因為編程語言中我們的陣列是從0開始進行遍歷，但線性表一般從1開始遍歷
假設ElemType占用的是c個存盤單元（位元組），那么線性表中第i+1個資料元素和第i個資料元素的存盤位置的關系是：（Loc表示獲得存盤位置的函式）：Loc(ai+1) = Loc(ai)+c

所以對于第i個資料元素ai的存盤位置可以由a1推算得出：
Loc（ai） = Loc（a1）+（i - 1）* c;

通過公式，可以隨時計算出線性表的任意位置的地址，不管是第一個還是最后一個都是相同的實踐，它的存盤實踐性能為O(1)，我們通常成為隨機存盤結構，

五、線性表順序存盤結構之獲得元素操作

1. 分析：
   實作GetElem的具體操作，即將線性表L中的第i個位置元素值回傳，只需要把陣列第i-1下標的值回傳即可，

2. 代碼實踐

 #define OK 1
 #define ERROR 0
 #define TRUE 1
 #define FALSE 0
 typedef int Status;
 //Status 是函式的型別，它的值是函式結果狀態代碼，如OK等，
 //初始條件：順序線性表L已存在，i<= i<=ListLength(L)
 //操作結果：用e回傳L中第i個資料元素的值
 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;
}

注意這里的Status是一個整型，約定回傳1代表OK，回傳0代表ERROR，其時間復雜度為O（1）

六、線性表順序存盤結構之插入元素操作

1. 分析
   ——如果插入位置不合理，拋出例外
   ——如果線性表長度大于等于陣列長度，則拋出例外或動態增加陣列容量，
   ——從最后一個元素開始向前遍歷到第i個位置，分別將他們都向后移動一個位置；
   ——將要插入元素填入位置i處；
   ——線性表長度+1

2. 代碼實踐

  Status ListInsert(SqList *L,int i,ElemType e){
		int k;
		if(L->length == MAXSIZE) //順序線性表已經滿了
		{
			return ERROR;
		}
		if(i < 1 || i > L->length+1)//i不在范圍內時
		{
			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;
}

注意：ListInsert（*L,i,e）插入元素操作的時間復雜度為O(n);第i個位置插入新元素e

七、線性表順序存盤結構之元素洗掉操作

1. 分析
   ——洗掉位置不合理，拋出例外
   ——取出洗掉元素
   ——從洗掉元素位置開始遍歷，最后一個元素位置，分別將他們都向前移動一個
   ——表長-1
2. 代碼實踐

 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--;
}

插入或洗掉的時間復雜度，最好的情況下為O（1），表示只需在尾部插入一個元素或者在尾部洗掉一個元素，最壞情況下，需要O（n）個時間復雜度，因為需要遍歷回圈線性表，兩者進行平均可得時間復雜度O((n-1)/2）可以推出時間復雜度為O（n）