線性表的定義

線性表（List）:由零個或多個資料元素組成的有序結構，
若線性表記為（a1,……,ai-1,ai,ai+1,……an）,則表中ai-1領先于ai領先于ai+1，稱ai-1是ai的直接前驅元素，ai+1是ai的后繼元素，

例子：

請問公司的組織架構是否屬于線性關系？
- 分析：一般公司的總經理管理幾個總監，每個總監管理幾個經理，每個經理都有各自的下屬和員工，
- 答：不是，因為線性關系的條件是如果存在多個元素，則第一個元素無前驅，而最后一個元素無后繼，其他元素都有且只有一個前驅和后繼，

抽象資料型別

資料型別

資料型別：是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱，
例如很多編程語言的整型，浮點型，字符型這些指的就是資料型別，
原因：計算機的記憶體不是無限大的，不同的運算需要開辟不同的記憶體空間，于是計算機的研究者們就考慮，要對資料型別進行分類，分出多種資料結構型別來適合各種不同的計算條件差異，
例如在C語言中按照取值的不同，資料結構型別可以分為兩類：
- 原子型別：不可以再分解的基本型別，例如整型、浮點型、字符型等，
- 結構型別：由若干個型別組合而成，是可以再分解的，例如整型陣列是由若干整型資料組成的，
抽象：是指抽取出事物具有的普遍性的本質，它要求抽出問題的特征而忽略非本質的細節，是對具體事物的一個概括，抽象是一種思考問題的方式，它隱藏了繁雜的細節，
抽象資料型別（Abstract Data Type , ADT）是指一個數學模型及定義再該模型上的一組操作，
抽象資料型別的定義僅取決于它的一組邏輯特性，而與其再計算機內部如何表示和現實無關，

為了便于在之后的講解中對抽象資料型別進行規范的描述，我們給出了描述抽象資料型別的標準格式(偽代碼)：

? ADT 抽象資料型別名

? Data

? 資料元素之間邏輯關系的定義

? Operation

? 操作

? endADT

線性表的抽象資料型別

Operation
- InitList(*L):初始化操作，建立一個空的線性表L，
- ListEmpty(L)：判斷線性表是否為空表，若線性表為空，回傳true，否則回傳false，
- ClearList(*L)：將線性表清空，
- GetElem(L,i,*e)：將線性表L中的第i個位置元素值回傳給e，
- LocationElem(L,e)：在線性表中查找與給定值e相等的元素，如果查找成功，回傳該元素在表中序號表示成功；否則，回傳0表示失敗，
- ListInsert(*L,i,e)：在線性表L中第i個位置插入新元素e，
- ListDelete(*L, i *e):洗掉線性表L中第i個位置元素，并用e回傳其值，
- ListLength(L)：回傳線性表L的元素個數，
endADT
對于不同的應用，線性表的基本操作是不同的，上述操作是最基本的，對于實際問題中涉及的關于線性表的更復雜操作，安全可以用這些基本操作的組合實作，

線性表的順序存盤結構

線性表的兩種物理存盤結構：

順序存盤結構和鏈式存盤結構，

線性表的順序存盤結構，指的是用一段地址連續的存盤單元依次存盤線性表的資料元素，
物理上的存盤方式事實上就是在記憶體中找個初始地址，然后通過占位的形式，把一定的記憶體空間給占了，然后把相同資料型別的資料型別的資料元素一次放在這塊空地中，

線性表順序存盤結構代碼：

#define MAXSIZE 20
typedef int ElemType ;
typedef struct
{
    ElemType data[MAXSIZE];
    int langth;	//線性表當前長度
}SqList;

總結下，順序存盤結構封裝需要三個屬性：

存盤空間的起始位置，陣列data，它的存盤位置就是線性表存盤空間的存盤位置，
線性表的最大存盤容量：陣列的長度MAXSIZE，
線性表的當前長度：length，
- 注意，陣列的長度于線性表的當前長度需要區分一下：陣列的長度是存放線性表的存盤空間的總長度，一般初始化后不變，而線性表的當前長度是線性表中的元素的個數，是會變化的，

地址計算方法

線性表的定義充分考慮到很多軍師級別領導的智商指數，所以決定從1開始回歸正常思維，
假設ELemType占用的時c個存盤單元（位元組），那么線性表中第i+1個資料和第i+1個資料元素和第i個資料元素的存盤位置的關系是（LOC表示獲得存盤位置的函式）：LOC(ai+1) = LOC(ai) + c，
所以對于第i個資料元素ai的存盤位置可以有a1推算得出：LOC(ai) = LOC(a1) + (i-1)*c
通過這個公式，我們可以隨時計算出線性表中任意位置的地址，不管它是第一個還是最后一個，都是相同的時間，那么它的存盤時間性能當然就為O(1),我們通常稱為隨機存盤結構，

獲取元素操作

實作GetElem的具體操作，即將線性表L中的第i個位置元素值回傳，就程式而言非常簡單了，我們只需要把陣列第i-1個下標的值回傳即可，

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALST 0

typedef int Status;
//Status 是函式的型別，其值是函式結果狀態代碼，如OK等，
//初始條件：順序表L已存在，1<= i <= ListLength(L)
//操作結果：用e回傳L中第i個陣列元素的值，

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

插入操作

剛才我們也談到，線性表的順序存盤結構具有隨機存盤結構的特點，時間復雜度為O(1)，
要實作的函式名：
ListInsert(*L , i , e)，即在線性表L中的第i個位置插入新元素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 ){	//當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;	//回傳執行狀態碼

}

洗掉操作

洗掉演算法的思路：
- 如果洗掉位置不合理，拋出例外；
- 取出洗掉元素；
- 從洗掉元素位置開始遍歷到最后一個元素位置，分別將它們都向前移動一個位置；
- 表長-1，

代碼實作：

/*
	前提：順序表L已經存在，且1<= i <= L->length-1;
	執行結果：
		經洗掉元素通過ElemType e接收，并回傳執行狀態碼
*/
Status ListDelete(SqList * L, int i , ElemType *e){
	int k;
	
	if(L->length == 0){		//順序表為空
		return ERROR;
	}
	if( i < 1 || i > L->length){	//當i操作不當時
		return ERROR;
	}
	
    e = L->data[i-1];	//把洗掉元素的資料賦值給e
    
    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)，
至于平均情況，就取中間值O((n-1) /2)，
按照前邊游戲秘籍指導，平均情況復雜度簡化后還是O(n)，

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

線性表的順序存盤結構，在存、讀資料時，不管時哪個位置，時間復雜度都是O(1)，而在插入或者洗掉時，時間復雜度都是O(n)，
這就說明，它比較適合元素個數比較穩定，不經常插入和洗掉元素，而更多的操作時存取資料的應用，
線性表順序存盤結構的優點:
- 無須為表示中間元素之間的邏輯關系而增加額外的存盤空間，
- 可以快速地存取表中任意位置的元素，
線性表順序存盤結構的缺點
- 插入和洗掉操作需要移動大量元素，
- 當線性表長度變化時，難以確定存盤空間的容量，
- 容易造成存盤空間的“碎片”，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/158230.html

標籤：其他

上一篇：BAT批處理實作休眠關機重啟

下一篇：通過python完成青書學堂刷課青書視頻青書教材課件學習