前言

我們都知道，數(shù)據(jù)結(jié)構(gòu)中邏輯結(jié)構(gòu)可以劃分為線性結(jié)構(gòu)(線性表)與非線性結(jié)構(gòu)兩大類。

而存儲結(jié)構(gòu)指的是數(shù)據(jù)元素在計(jì)算機(jī)中的存儲及其邏輯關(guān)系的表現(xiàn)，也就是在計(jì)算機(jī)當(dāng)中對邏輯結(jié)構(gòu)的表示。

線性表的存儲結(jié)構(gòu)主要有順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)兩種實(shí)現(xiàn)形式。本文主要探討基于線性表的順序結(jié)構(gòu)也就是順序表的四種基本操作：初始化、插入、刪除、查找。

這些知識點(diǎn)既可能出現(xiàn)在選擇題的考察當(dāng)中又可以出現(xiàn)在編程大題當(dāng)中，但是考察的側(cè)重點(diǎn)不同，選擇題重點(diǎn)關(guān)注操作的時(shí)間復(fù)雜度以及特性(特別是不同結(jié)構(gòu)的順序表，在實(shí)現(xiàn)某種操作時(shí)候的效率高低)，編程大題只是關(guān)注代碼實(shí)現(xiàn)能力。

基本知識分析

順序存儲?：

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

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

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

??數(shù)據(jù)元素之間的關(guān)系是以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來體現(xiàn)

a1到an存放情況如圖所示，設(shè)每個(gè)元素占l個(gè)單元長度。(ps：計(jì)算機(jī)中數(shù)組下標(biāo)實(shí)際從0開始)

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

因此順序表的結(jié)構(gòu)體當(dāng)中應(yīng)當(dāng)包含 一塊連續(xù)的地址空間、當(dāng)前存放元素的長度、當(dāng)前分配的存儲容量。由此寫出結(jié)構(gòu)體如下：

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

在了解順序表靜態(tài)構(gòu)造的基礎(chǔ)上，我們可以在這個(gè)基礎(chǔ)上構(gòu)建它的幾個(gè)基本操作了。

1

初始化

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

關(guān)鍵代碼：

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

2

插入

設(shè)n個(gè)元素存放在elem[0...length-1]內(nèi)。

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

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

關(guān)鍵代碼：

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

3

刪除

設(shè)n個(gè)元素存放在elem[0...length-1]內(nèi)。

輸入：i，表示要?jiǎng)h除下標(biāo)為i處的元素。

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

關(guān)鍵代碼：

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

4

查找

設(shè)n個(gè)元素存放在elem[0...length-1]內(nèi)。

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

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

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

關(guān)鍵代碼：

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

選擇題角度

重點(diǎn)考察 時(shí)間復(fù)雜度、特性、以及執(zhí)行相關(guān)操作的效率。

根據(jù)前面的分析以及關(guān)鍵代碼部分可以觀察到：

1

初始化

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

2

插入

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

3

刪除

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

4

查找

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

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

編程角度

一個(gè)完整的操作函數(shù)，是由 健壯性保證?以及 關(guān)鍵代碼?兩部分組成的。

1

初始化

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

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

2

插入

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

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

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寫入下標(biāo)為i處
L->elem[i]=e;return?true;
}

3

刪除

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

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

以上就是學(xué)長給大家歸納的關(guān)于線性表的相關(guān)基本操作了。

這里大牛學(xué)長幫大家最后總結(jié)一下。

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

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

今天是2020年8月18日

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

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

大牛學(xué)長一直在~

總結(jié)

以上是生活随笔為你收集整理的数据结构知识点总结_大牛带你学 | 考研数据结构中线性表中顺序结构的知识点总结...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。