??本篇及下一篇文章介紹線性表，包括線性表的定義及順序表和鏈表的表示和方法，有關b樹的補充等到之后進行介紹，
一：線性表的定義和基本操作
??線性表是具有相同資料型別資料元素的有限序列集合，當線性表內沒有元素時，是一個空表用a(i)代表第i個資料元素，第一個元素為表頭，最后一個元素為表尾，除第一個元素外，每個元素都有一個直接前驅；除最后一個元素外，每個元素都有一個直接后繼，
??線性表是一個邏輯結構，表示元素之間一一對應的關系；而順序表和鏈式表是指存盤結構，
??線性表的基本操作是最基本的操作，包括：
??InitList(&L)：初始化一個空的線性表，
??Length(L)：求表長，
??LocateElem(L,e)：在表中查找給定關鍵字值的元素，
??GetElem(L,i)：在表中查找第i個位置的元素的值，
??ListInsert(&L,i,e)：在表中的第i個位置插入元素e，
??ListDelete(&L,i,&e)：洗掉表中第i個位置元素，并用e回傳，
??PrintList(L)：輸出線性表中的所有元素值，
??Empty(L)：判斷線性表是否為空，
??DestoryList(&L)：銷毀線性表，并釋放線性表所占用的記憶體空間，
??這里的"&"表示的是c++里面的參考呼叫，傳入指標變數的時候要對傳入的指標進行改變，則會用到指標變數的參考型，在C語言的采用指標的指標也可以達到同樣的效果，
二：線性表的順序存盤
1.定義
??線性表的順序存盤又稱順序表，用一組地址連續的存盤單元依次存盤線性表的資料元素，使邏輯上相鄰的元素物理位置上也相鄰，i為元素a(i)的位序，特點是表中的邏輯順序與其物理順序相同，
??有關順序表的基本模型和結構這里就不詳細介紹了，主要是順序表是依靠陣列實作的，要注意的是：線性表中元素的位序是從1開始的，而陣列中元素的位序是從0開始的，
2.順序存盤資料型別
??由于順序表是由陣列實作的，我們知道一維陣列可以是靜態分配的，也可以是動態分配的，靜態分配因為空間和大小有限，一旦占滿，再加入新的資料將會產生溢位，導致程式崩潰；動態分配，陣列空間是在需要時通過動態存盤陳述句分配，可以不斷開辟新的存盤空間，擴充存盤空間，所以更高效，
??順序存盤資料型別實作的代碼如下：
// 順序表的靜態存盤
#define MaxSize 50 //順序表最大長度
typedef struct{
ElemType data[MaxSize]; //順序表資料元素
int length; //順序表當前長度
}SqList; //順序表結構體型別定義
//順序表的動態存盤
#define InitSize 100 //表長度的初始定義
typedef struct{
ElemType *data; //動態分配陣列指標
int MaxSize;length; //陣列最大容量和當前個數
}SeqList; //順序表結構體型別定義
??C語言初始動態分配陳述句是：
L.data= https://www.cnblogs.com/ITXiaoAng/p/(ElemType)malloc(sizeof(ElemType)InitSize);
??C++的動態分配陳述句是：
L.data = https://www.cnblogs.com/ITXiaoAng/p/new ElemType(InitList);
3.順序表基本操作的實作(代碼寫的是靜態存盤，動態存盤類似)
(1)插入操作
??在順序表L的第i個位置插入新元素e，如果i的輸入不合法，則回傳false，表示插入失敗；否則將原順序表的第i個元素及其后面的所有元素右移一個位置，騰出一個空間插入新元素e，順序表的長度加一，插入成功，回傳true，插入位置范圍從1到L.length+1，代碼如下：
bool ListInsert(SqList &L,int i,ElemType e){
if(i < 1|| i > Length + 1)
return false;
if(L.length >= MaxSize) //當前存盤空間已滿，不能插入
return false;
for(int j = L.length;j >= i;j--){ //將i及之后的元素后移
L.data[j] = L.data[j-1];
}
L.data[i-1] = e; //陣列從0開始
L.length++;
return true;
}
??插入操作的最好情況是在表尾插，后移操作不再進行；最壞情況是在表頭插，后移n次，而平均情況下，插入的平均時間復雜度是O(n)，
(2)洗掉操作
??洗掉表中的第i個位置的元素，成功回傳true，并將被洗掉的元素用參考變數e回傳，否則回傳false，也需要移動元素位置，洗掉位置范圍從1到L.length，代碼如下：
bool ListDelete(SqList &L,int i,ElemType &e){
if(i < 1|| i > Length)
return false;
e = L.data[i-1];
for(int j = i;j < L.length;j++){ //將i及之后的元素前移
L.data[j-1] = L.data[j];
}
L.length--;
return true;
}
??插入操作的最好情況是在表尾插，前移操作不再進行；最壞情況是在表頭插，前移n-1個資料元素，而平均情況下，洗掉的平均時間復雜度是O(n)，
(3)簡單的按值查找
??在順序表中查找第一個元素值等于e的元素，并回傳其位序，代碼如下：
int LocateElem(SqList L,ElemType e){
int i;
for(i = 0;i < L.length;i++)
if(L.data[i] == e)
return i + 1; //位序從一開始
return 0;
}
??最好情況在表頭比較一次，在表尾或不存在比較n次，按值查找的平均時間復雜度為O(n)，
4.順序表的特點
??優點：隨機訪問，在O(1)的時間內找到指定的元素，存盤密度高，每個結點只存盤資料元素，
??缺點：插入和洗掉操作需要移動大量元素，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/144604.html
標籤：其他