前言

我們都知道，數據結構中邏輯結構可以劃分為線性結構(線性表)與非線性結構兩大類。

而存儲結構指的是數據元素在計算機中的存儲及其邏輯關系的表現，也就是在計算機當中對邏輯結構的表示。

線性表的存儲結構主要有順序結構和鏈式結構兩種實現形式。本文主要探討基于線性表的順序結構也就是順序表的四種基本操作：初始化、插入、刪除、查找。

這些知識點既可能出現在選擇題的考察當中又可以出現在編程大題當中，但是考察的側重點不同，選擇題重點關注操作的時間復雜度以及特性(特別是不同結構的順序表，在實現某種操作時候的效率高低)，編程大題只是關注代碼實現能力。

基本知識分析

順序存儲?：

把線性表的結點按邏輯順序依次存放在一組地址連續的存儲單元里。用這種方法存儲的線性表簡稱順序表。(為了便于理解，大家可以近似得把這一段空間理解成一個C語言數組)

由于元素順序排列，順序存儲具有以下性質和特征：

??線性表的邏輯順序與物理順序一致;

??數據元素之間的關系是以元素在計算機內“物理位置相鄰”來體現

a1到an存放情況如圖所示，設每個元素占l個單元長度。(ps：計算機中數組下標實際從0開始)

a_i的地址：Loc(a_i)=Loc(a₁)+(i-1)×1

因此順序表的結構體當中應當包含 一塊連續的地址空間、當前存放元素的長度、當前分配的存儲容量。由此寫出結構體如下：

typedef struct{
ElemType *elem;//存儲空間基址
int length;//當前長度
int listsize;//當前分配的存儲容量
}SqList;

在了解順序表靜態構造的基礎上，我們可以在這個基礎上構建它的幾個基本操作了。

1

初始化

輸入：MAXSIZE，表示要申請MAXSIZE個元素大小的地址單元。

關鍵代碼：

L->elem=(ElemType *)malloc(MAX_SIZE*sizeof( ElemType));//分配空間
L->length=0;//空表長度為0
L->listsize=MAX_SIZE;//初始存儲容量

2

插入

設n個元素存放在elem[0...length-1]內。

輸入：i，e，表示要在下標為i處插入值為e的元素。

分析插入過程導致的結果：元素數量從length變成了length+1，如果只是簡單地將下標為i處的元素替換成e，會導致原先的元素丟失。因此插入操作可以表述為：(1)將該元素以及該元素之后的所有元素都向后移動一個位。(2)元素大小加1。(3)再將e寫入到下標為i處。比如對于[1,2]這個數組來說，將0插入到第一位，事實上是先使得第一位以及第一位之后的所有元素后移一位，數組變成[1,1,2]，然后將0寫入第一位，數組變成[0,1,2]

關鍵代碼：

//elem[i...length-1]向后移動for(j = length-1; j >= i; j--){
L->elem[j+1] = L->elem[j]
}//元素大小加1
length++;//e寫入下標為i處
L->elem[i]=e;

3

刪除

設n個元素存放在elem[0...length-1]內。

輸入：i，表示要刪除下標為i處的元素。

分析刪除過程導致的結果：元素數量從length變成了length-1，如果只是簡單地將下標為i處的元素被刪除，會導致此處出現一個空白單元。因此刪除操作可以表述為：(1)將該元素之后的所有元素都向前移動一個位。(2)元素大小減1。將i+1處的元素移動到i處時完成了覆蓋，事實上等同于刪除了i處的元素。比如對于[0,1,2]這個數組來說，將第二個元素移動到第一個，第三個元素移動到第二個也就是數組變成了[1,2,2]，但是此時length=2說明數組長度為2，取前2個元素，事實上完成了對0的刪除。

關鍵代碼：

//elem[i+1...length-1]向前移動for(j = length-1; j > i; j--){
L->elem[j-1] = L->elem[j]
}//元素大小減1
length--;?

4

查找

設n個元素存放在elem[0...length-1]內。

輸入：e，表示查找值為e的元素。

輸出：i，表示值為e的元素位于下標為i處，若查找不成功，i=-1(或者自己定義其他不屬于0...length-1的值)

分析查找過程：其實是從頭到尾遍歷每一個元素，比較當前元素是否等于查找值e，若等于則返回下標i，當遍歷完畢n個元素還是沒有返回值，說明表中不存在要查詢的元素。

關鍵代碼：

//遍歷比較每一個元素for(i=0; i < length; i++){if(EQ(L->elem[i], e)){?return?i;}
}//遍歷結束沒有返回值，說明不存在return?-1;

選擇題角度

重點考察 時間復雜度、特性、以及執行相關操作的效率。

根據前面的分析以及關鍵代碼部分可以觀察到：

1

初始化

關鍵代碼只涉及到一次堆分配malloc以及修改listsize和length，頻度為3，時間復雜度為O(1)。

2

插入

關鍵代碼分為三步：(1)修改length，頻度為1，時間復雜度為O(1)；(2)elem[i...n-1]向后移動，移動n-i次，頻度為n-i，時間復雜度為O(n)；(3)向下標為i處寫入元素e，頻度為1，時間復雜度為O(1)。綜上總的時間復雜度為O(n)。

3

刪除

關鍵代碼分為兩步：(1)修改length，頻度為1，時間復雜度為O(1)；(2)elem[i+1...n-1]向前移動，移動n-i-1次，頻度為n-i-1，時間復雜度為O(n)。綜上總的時間復雜度為O(n)。

4

查找

關鍵代碼：遍歷整個序列比較是否有元素的值為e，遍歷結束時查找不成功則返回-1。顯然若第一個元素就是要找的元素時，只比較一次，若最后一個元素是要找的元素則比較n次，若不存在該元素同樣是比較n次，比較次數的取值范圍為1到n，若每個元素出現頻率相等，查找成功的情況下平均比較次數為(n+1)/2次，時間復雜度為O(n)。

綜上，在順序表中，訪問下標為i的元素可以通過 隨機訪問?，如elem[i]獲取，時間復雜度為O(1)，但是對于插入和刪除這樣的動態操作時間復雜度都為O(n)，順序查找時間復雜度也為O(n)。

編程角度

一個完整的操作函數，是由 健壯性保證?以及 關鍵代碼?兩部分組成的。

1

初始化

malloc可能會有分配失敗的可能，因此要對此進行判斷。

bool InitList(SqList *L){
L->elem=(ElemType *)malloc(MAX_SIZE*sizeof( ElemType));//分配空間if(!L->elem){ return?false;}//基址指針為空時分配失敗
L->length=0;//空表長度為0
L->listsize=MAX_SIZE;//初始存儲容量return?true;
}

2

插入

??對于elem[0...length-1]來說合法的插入范圍應該是0~length，要對輸入的i進行判斷。

??插入會使得表長加1，可能會發生上溢，也就是分配空間不夠，所以要對此進行判斷。

bool ListInsert(SqList *L, int?i, ElemType e){int?j;if(i < 0?|| i > L->length) { return?false;}//i輸入是否合法if(L->length >= L->listsize){
?newbase = (ElemType *)realloc(L->elem, (L->listsize + INCREMENT)*sizeof( ElemType));//分配空間if(!newbase){return?false;}//分配失敗
?L->elem = newbase;
?L->listsize += INCREMENT;
}//是否上溢//elem[i...n-1]向后移動for(j = L->length-1; j >= i; j--){
?L->elem[j+1] = L->elem[j]
}//元素大小加1
L->length++;//e寫入下標為i處
L->elem[i]=e;return?true;
}

3

刪除

??對于elem[0...length-1]來說合法的刪除范圍應該是0~length-1，要對輸入的i進行判斷。

bool ListDelete(SqList *L, int?i, ElemType &e){if(i < 0?|| i > L->length - 1){ retrun false;}//i輸入是否合法
e = *(&L->elem[i]);//elem[i+1...length-1]向前移動for(j = L->length-1; j > i; j--){
?L->elem[j-1] = L->elem[j]
}//元素大小減1
L->length--;return?true;
}

4

查找

int?Locate(SqList* L, ElemType e){int?i;//遍歷比較每一個元素for(i=0; i < L.length; i++){if(EQ(L->elem[i], e)){ return?i;}
}//遍歷結束沒有返回值，說明不存在return?-1;
}

以上就是學長給大家歸納的關于線性表的相關基本操作了。

這里大牛學長幫大家最后總結一下。

??對于增、刪、查、改幾個基本操作，由于順序表元素存在于一片連續空間。每一次做遍歷相關操作的時候，都需要用一個全局的for循環去近似遍歷整個表，因此這幾個操作的時間復雜度都是O(n)，即線性的。

? 對于增、刪操作，一定要做好合法性判斷，在編程大題中，合法性判斷是判卷老師對于學生編程素質的重點考察點，你不能說老師一定會關注合法性判斷，但是寫上合法性判斷相關的代碼一定會為你加上一點“印象分”！

今天是2020年8月18日

距離2021考研還有?122?天??

全力以赴，才有資格說盡力。

大牛學長一直在~