柚子快報激活碼778899分享：數(shù)據(jù)結(jié)構(gòu)詳解---順序表

http://yzkb.51969.com/

?個人博客主頁：意疏-CSDN博客

希望文章能夠給到初學(xué)的你一些啟發(fā)～ 如果覺得文章對你有幫助的話，點(diǎn)贊 + 關(guān)注+ 收藏支持一下筆者吧～

閱讀指南：

開篇說明線性表的定義線性表的順序存儲結(jié)構(gòu)（順序表）順序存儲結(jié)構(gòu)的插入與刪除（順序表）插入操作刪除操作線性表順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)

開篇說明

數(shù)據(jù)結(jié)構(gòu)是組織和存儲數(shù)據(jù)的一種方式，它不僅定義了數(shù)據(jù)的類型，還規(guī)定了數(shù)據(jù)之間的關(guān)系以及對數(shù)據(jù)進(jìn)行操作的方法。線性表是一種基本的數(shù)據(jù)結(jié)構(gòu)，用于存儲一組有序的數(shù)據(jù)元素。線性表中的元素具有線性關(guān)系，即每個元素有且只有一個前驅(qū)和一個后繼（除了第一個元素沒有前驅(qū)和最后一個元素沒有后繼）。線性表可以分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)兩種實現(xiàn)方式。

在本篇中，我們將深入探討線性存儲中順序表的實現(xiàn)細(xì)節(jié)、基本操作（如插入、刪除、查找），通過這些內(nèi)容的學(xué)習(xí)，希望我們可以一起進(jìn)步。

線性表的定義

線性表：是具有相同數(shù)據(jù)類型為n(n>=0)個數(shù)據(jù)元素的有限序列，它是典型的線性結(jié)構(gòu)。除第一個元素外，每個元素有且僅有一個直接前驅(qū)，除最后一個元素外，每個元素有且僅有一個直接后繼。 這里首先要強(qiáng)調(diào)的是，首先它是一個序列，也就是說，元素之間是有順序的，若元素存在多個，則第一個元素?zé)o前驅(qū)，最后一個元素?zé)o后繼。元素的個數(shù)是有限的。 如用數(shù)字語言來進(jìn)行定義，若將線性表記為（

a

1

a_1

a1?，…，

a

i

a_i

ai?-1，a，

a

i

a_i

ai?+1，…，

a

n

a_n

an?） 則表中

a

i

a_i

ai?-1領(lǐng)先于

a

i

a_i

ai?，

a

i

a_i

ai?領(lǐng)先于

a

i

a_i

ai?+1，我們稱

a

i

a_i

ai?-1是

a

i

a_i

ai?的直接前驅(qū)，

a

i

a_i

ai?+1是

a

i

a_i

ai?的直接后繼元素。當(dāng)i = 1,2，n-1時，

a

i

a_i

ai?有且僅有一個直接后繼，當(dāng)i = 2,3，n時，

a

i

a_i

ai?有且僅有一個直接前驅(qū)。

這里是示例圖： 所以線性元素的個數(shù) n n(>=0) 定義為線性表的長度，當(dāng)n=0時，稱為空表。

在非空表中的每個數(shù)據(jù)元素都有一個確定的位置，如

a

1

a_1

a1?是第一個數(shù)據(jù)元素，

a

n

a_n

an?是最后一個數(shù)據(jù)元素，

a

i

a_i

ai?是第i個數(shù)據(jù)元素，稱i為數(shù)據(jù)元素

a

i

a_i

ai?在線性表中的位序。

在較復(fù)雜的線性表中，一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成。

線性表的抽象數(shù)據(jù)類型定義如下： 在實際問題中，關(guān)于線性表的更復(fù)雜操作，完全可以用這些基本的操作組合來實現(xiàn)。例如，實現(xiàn)兩個線性表集合A和B的并集操作。即要使得集合A = A

∪

\cup

∪ B 簡單來說就是把存在集合B但不存在A中的數(shù)據(jù)元素插入到A中即可。 我們只要循環(huán)集合B中的每個元素，判斷當(dāng)前元素是否存在A中，若不存在，則插入A即可。 我們假設(shè)

L

a

L_a

La?表示集合A，

L

b

L_b

Lb?表示集合B，則實現(xiàn)的代碼如下：

這里，我們對于union操作，用到了前面線性表基本操作ListLength、GetElem、LocateElem、ListInsert等，其實復(fù)雜的操作，其實就是把基本操作組合起來實現(xiàn)的。

線性表的順序存儲結(jié)構(gòu)（順序表）

我們來看一下線性表的兩種物理結(jié)構(gòu)的第一種：順序存儲結(jié)構(gòu)。 線性表的順序存儲結(jié)構(gòu)是指：用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，從而使邏輯上相鄰的兩個元素在物理位置上也相鄰。

線性表（

a

1

a_1

a1?，

a

2

a_2

a2?，…，

a

n

a_n

an?）的順序存儲示例圖如下： 線性表的順序存儲結(jié)構(gòu)，就是在內(nèi)存中找地方，通過占位的形式，把一定內(nèi)存空間給占掉了，然后把相同數(shù)據(jù)類型的數(shù)據(jù)元素依次存放在這片空地中。線性表的每個數(shù)據(jù)元素的類型都相同，所以可以用C語言的一維數(shù)組來實現(xiàn)順序存儲結(jié)構(gòu)。即把第一個數(shù)據(jù)元素存儲到數(shù)組下標(biāo)為0的位置中，接著把線性表相鄰的元素存儲在數(shù)組中相鄰的位置。

。數(shù)組的分配，在正常情況下是靜態(tài)分配，但我們也可以動態(tài)分配。

我們首先來看靜態(tài)分配：靜態(tài)分配：數(shù)組大小和空間已經(jīng)固定，一旦空間占滿，再加入新的數(shù)據(jù)，就會產(chǎn)生溢出，導(dǎo)致程序崩潰（空間固定）

#define MaxSize 100//存儲空間初始分配量

typedef struct {

ElemType data[MaxSize];//數(shù)組存儲數(shù)據(jù)元素，最大值為MAXSIZE

int length;//線性表當(dāng)前長度

} SeqList;

這里我們可以發(fā)現(xiàn)描述順序存儲結(jié)構(gòu)需要三個屬性： 1. 存儲空間的起始位置：數(shù)組data，它的存儲位置就是存儲空間的存儲位置。 2. 線性表的最大存儲容量：數(shù)組長度MaxSize。 3. 線性表的當(dāng)前長度：length。

這里我們需要注意的是： 數(shù)組的長度與線性表的長度兩者的區(qū)分: 數(shù)組的長度是存放線性表的存儲空間的長度，存儲分配后這個量是一般是不會變的。 線性表的長度是線性表中數(shù)據(jù)元素的個數(shù)，隨著線性表插入和刪除操作的進(jìn)行，這個量是會變化的。 在任何時刻，線性表的長度都需要小于等于數(shù)組的長度。

我們再來看動態(tài)分配：動態(tài)分配：存儲數(shù)據(jù)的空間在程序執(zhí)行中動態(tài)語句分配，一旦空間占滿，可以另外開辟更大空間，用來替換原始空間。（空間不固定）

#define InitS 100

typedef struct {

ElemType *data;//包含的數(shù)組

int length;//當(dāng)前表中有幾個元素

} SeqList;

順序存儲結(jié)構(gòu)的插入與刪除（順序表）

獲得元素操作 對于線性表的順序存儲結(jié)構(gòu)來說，如果我們要實現(xiàn)GetElem操作，即將線性表L中的第i個位置元素值返回。就程序而言，只要i的數(shù)值在數(shù)組下標(biāo)范圍內(nèi)，就是把數(shù)組第i－1下標(biāo)的值返回即可。

例

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

typedef int Status;

//Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等。

//初始條件：順序線性表L已存在，1<=i<=ListLength (L)。

//操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值。

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;

}

注： 這里返回值類型是Status 是一個整型，返回OK代表1，ERROR代表0。

插入操作

我們要實現(xiàn)ListInsert（*L，i，e），就是將線性表L中的第i個位置插入新元素e。 插入算法的思路：

如果插入位置不合理的話，拋出異常。如果線性表長度大于或等于數(shù)組長度，則拋出異?；騽討B(tài)增加容量。從最后一個元素開始向前遍歷到第i個位置，分別將它們都向后移動一個位置。將要插入的元素填到位置 i 處。表長加1。

代碼如下：

//初始條件：順序線性表L已存在，1<=i<=ListLength(L)

//操作結(jié)果：在L中第i個位置之前插入新的數(shù)據(jù)元素e，L的長度加1

Status ListInsert(SqList *L, int i, ElemType e)

{

int k;

if (L-> length == MAXSIZE)//順序線性表已滿

return ERROR;

if (i < 1 || i > L-> length + 1) //當(dāng)i不在范圍內(nèi)時，返回錯誤

return ERROR;

if (i <= L-> length)//若插入位置不在表尾

{

for (k = L-> length; k >= i-1; k--)//將后面的元素后移一位

L-> data[k+1] = L-> data[k];

}

L-> data[i-1] = e; //插入新元素

L-> length++; //表長加1

return OK;

}

刪除操作

刪除算法的思路：

如果刪除位置不合理的話，拋出異常。取出刪除元素從刪除元素位置開始遍歷到最后一個元素位置，分別將它們都向前移動一個位置。表長減1。

代碼如下：

//初始條件：順序線性表L已存在，1<=i<=ListLength(L)

//操作結(jié)果：刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的長度減1

Status ListDelete(SqList *L, int i, ElemType *e)

{

int k;

if (L-> length == 0)//線性表為空時，返回錯誤

return ERROR;

if (i < 1 || i > L-> length) //刪除位置不正確

return ERROR;

*e = L-> data[i-1]; //返回被刪除元素的值

if (i length)//若插入位置不在表尾

{

for (k=i;k = L-> length; k++)//將刪除位置后繼元素前移

L-> data[k-1] = L-> data[k];

}

L-> length--; //表長減1

return OK;

}

線性表順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

無須為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間?？梢钥焖俚卮嫒”碇腥我晃恢玫脑?。

缺點(diǎn)

插入和刪除操作需要移動大量元素當(dāng)線性表長度變化較大時，難以確定存儲空間的容量造成存儲空間的‘碎片’

你好，我是意疏。一起進(jìn)步。

意氣風(fēng)發(fā)，漫卷疏狂 學(xué)習(xí)是成長的階梯，每一次`的積累都將成為未來的助力。我希望通過持續(xù)的學(xué)習(xí)，不斷汲取新知識，來改變自己的命運(yùn)，并將成長的過程記錄在我的博客中。

如果我的博客能給您帶來啟發(fā)，如果您喜歡我的博客內(nèi)容，請不吝點(diǎn)贊、評論和收藏，也歡迎您關(guān)注我的博客。 您的支持是我前行的動力。聽說點(diǎn)贊會增加自己的運(yùn)氣，希望您每一天都能充滿活力！ 愿您每一天都快樂，也歡迎您常來我的博客。我叫意疏，希望我們一起成長，共同進(jìn)步。 我是意疏 下次見！

柚子快報激活碼778899分享：數(shù)據(jù)結(jié)構(gòu)詳解---順序表

http://yzkb.51969.com/

精彩文章