本文系在學習資料結構過程中做的筆記記錄，主要參考書籍為《大話資料結構》《算法導論》，文中如有纰漏歡迎指正。
文章目錄
-
-
- 1-線性表的定義
- 2-線性表的抽象資料類型
- 3- 線性表的順序存儲結構
- 4-順序存儲結構的插入與删除
- 5-優缺點
-
1-線性表的定義
線性表(List):零個或者多個資料元素的有限序列
用數學語言可以表述如下：
若線性表記為 ( a 1 , ⋅ ⋅ ⋅ , a i − 1 , a i , a i + 1 , ⋅ ⋅ ⋅ , a n ) (a_1, ···, a_{i-1}, a_i, a_{i+1}, ··· , a_n) (a1,⋅⋅⋅,ai−1,ai,ai+1,⋅⋅⋅,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 i = 1 ， 2 ，··· ,n-1 i=1，2，⋅⋅⋅,n−1時， a i a_i ai有且僅有一個直接後繼，當 i = 2 ， 3 ， ⋅ ⋅ ⋅ , n i = 2 ， 3 ，··· ,n i=2，3，⋅⋅⋅,n時， a i a_i ai有且僅有一個直接前驅。 如下圖所示：
圖1 線性表圖示
是以線性表元素的個數 n ( n ≥ 0 ) n(n≥0) n(n≥0)定義為線性表的長度，當 n = 0 n=0 n=0時，稱為空表。
2-線性表的抽象資料類型
線性表的抽象資料類型可以定義如下：
ADT 線性表(List)
Data
operation：
InitList(*L) ://初始化操作，建立一個空的線性表L
ListEmpty(L) ://若線性表為空，傳回true，否則傳回false
ClearList(*L) ://将線性表清空
GetElem(L, i, *e) : //将線性表L中的第i個元素傳回給e
LocateElem(L, e) : //線上性表中查找與指定元素e相等的元素，如果查找成功，傳回元素在表中的序号；否則傳回0表示失敗
ListInsert(*L, i, e) : //線上性表L中的第i個位置插入新元素e
ListDelete(*L, i, e) : //删除線性表中第i個位置的元素，并用e傳回其值
ListLeng(L) : //傳回線性表L的元素個數
endADT
對于不同的應用，線性表的基本操作是不同的，上述操作是最基本的，對于實際問題中涉及的關于線性表的更複雜的操作，可以利用這些基本操作的組合來實作。
3- 線性表的順序存儲結構
1-順序存儲的定義
- 線性表的順序存儲結構，指的是用一段位址連續的存儲單元依次存儲線性表的資料元素。
線性表 ( a 1 , ⋅ ⋅ ⋅ , a i − 1 , a i , a i + 1 , ⋅ ⋅ ⋅ , a n ) (a_1, ···, a_{i-1}, a_i, a_{i+1}, ··· , a_n) (a1,⋅⋅⋅,ai−1,ai,ai+1,⋅⋅⋅,an)的順序存儲示意圖如下：
圖1 線性表順序存儲示意
2-順序存儲方式
因為線性表的每個資料元素的類型都相同，是以可以用一維數組來實作順序存儲結構，即把第一個資料元素存儲到數組下标為0的位置中，接着把線性表相鄰的元素存儲在數組中的相鄰的位置。
下面是線性表順序存儲結構代碼:
#define MAXSIZE 20 //存儲空間初始配置設定量
typedef int ElemType; //ElemType類型根據實際情況而定，這裡假設為int
typedef struct
{
ElemType data[MAXSIZE];//數組存儲資料元素，最大值為MAXSIZE
int length;//線性表目前長度
}Sqlist;
這裡需要注意順序存儲結構的3個屬性：
- 存儲空間的起始位置：數組data，它的存儲位置就是存儲空間的存儲位置
- 線性表的最大存儲容量：數組長度
MAXSIZE
- 線性表的目前長度：
length
線性表的長度時線性表中資料元素的個數，随着線性表插入和删除操作的進行，這個量是可以變化的，在任何時刻，線性表的長度應該小于等于數組的長度
3-位址計算方法
用數組存儲順序表意味着要配置設定固定的長度的數組空間，由于線性表中可以進行插入和删除操作，是以配置設定的數組空間要大于目前線性表的長度。
假設一個元素占用 c c c個存儲單元，那麼線性表中第 i + 1 i+1 i+1個資料元素的存儲位置和第 i i i個元素的存儲位置滿足如下關系（ L O C LOC LOC表示獲得存儲位置的函數）: L O C ( a i + 1 ) = L O C ( a i ) + c LOC(a_{i+1}) = LOC(a_i) + c LOC(ai+1)=LOC(ai)+c，是以對第 i i i個資料元素的存儲位置可以用 a 1 a_1 a1推算出來： L O C ( a i + 1 ) = L O C ( a 1 ) + ( i − 1 ) ∗ c LOC(a_{i+1}) = LOC(a_1) + (i-1) * c LOC(ai+1)=LOC(a1)+(i−1)∗c
圖3 線性表順序存儲示意
4-順序存儲結構的插入與删除
1-獲得元素操作
對于線性存儲結構來說，如果我們要實作
GetElem
操作，即将線性表中第
i
個位置的元素值傳回，下面是實作代碼：
#define OK 1
#define ERROE 0
typedef int Status;
//Status是函數的類型，其值是函數結果狀态代碼，如OK等
//初始條件：順序表 L 已經存在，1 ≤ 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;
}
2-插入操作
插入算法的思路：
- 如果插入位置不合理，抛出異常
- 如果線性表長度大于或等于數組長度，則抛出異常或動态增加容量
- 從最後一個元素開始向前周遊到第 i 個位置，分别将它們都向後移動一個位置
- 将要插入元素填入位置 i 處
- 表長加 1
實作代碼如下：
//初始條件：順序表 L 已經存在，1 ≤ i ≤ListLength(L)
//操作結果: 在L中第 i 個位置之前插入新的資料元素e, L的長度加 1
Status ListInsert(Sqlist *L, int i, ElemType e)
{
if(L->length == MAXSIZE) return ERROR;//順序表已填滿
if(i < 1 || i > L->length + 1) return ERROR;//i 不在範圍内
if(i <= L->length){//插入資料不在表尾
for(int k = L->length - 1; k >= i-1; k--){//将要插入位置後的元素向後移動一位
L->data[k+1] = L->data[k];
}
}
L->data[i] = e;//新元素插入
L->length ++;
return OK;
}
3-删除操作
删除算法的思路：
- 如果位置不合理，抛出異常
- 取出删除元素
- 從删除元素位置開始周遊到最後一個元素位置，分别将它們都向前移動一個位置
- 表長加 1
實作代碼如下：
//初始條件：順序表 L 已經存在，1 ≤ i ≤ListLength(L)
//操作結果: 删除L中的第 i 個元素， 并用e傳回其值，L的長度減 1
Status ListDelete(Sqlist *L, int i, ElemType *e)
{
if(L->length == 0) return ERROR;//順序表為空
if(i < 1 || i > L->length) return ERROR;//删除位置不正确
*e = L->data[i - 1];
if(i < L->length){//如果删除不是最後位置
for(int k = i; k < L->length; k++){//将删除位置後繼元素前移
L->data[k-1] = L->data[k];
}
}
L->length --;
return OK;
}
5-優缺點
優點：
- 無須為表示表中的元素之間的邏輯關系增加額外的存儲空間
- 可以快速地存取表中任一位置的元素
缺點：
- 插入和删除操作需要移動大量元素
- 當線性表長度變化較大時，難以确定存儲空間的容量
- 造成存儲空間的“碎片”
PS：公衆号上線啦，技術幹貨分享，歡迎關注。