C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)線性表教程示例詳解

更新時(shí)間：2022年02月15日 09:21:52 作者：?jiǎn)虇碳业凝堼?

這篇文章主要為大家介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)線性表的示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

線性表

數(shù)據(jù)結(jié)構(gòu)里我們時(shí)常看到什么什么表，線性表是最基本、最簡(jiǎn)單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)，其他各種表的萬(wàn)惡之源就是這個(gè)線性表，他是個(gè)啥其實(shí)顧名思義：

一個(gè)線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系，即除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的（注意，這句話只適用大部分線性表，而不是全部。比如，循環(huán)鏈表邏輯層次上也是一種線性表（存儲(chǔ)層次上屬于鏈?zhǔn)酱鎯?chǔ)，但是把最后一個(gè)數(shù)據(jù)元素的尾指針指向了首位結(jié)點(diǎn)）。

說(shuō)的這么復(fù)雜其實(shí)就是下面這個(gè)模型，線性表的邏輯結(jié)構(gòu)簡(jiǎn)單，便于實(shí)現(xiàn)和操作。因此，線性表這種數(shù)據(jù)結(jié)構(gòu)在實(shí)際應(yīng)用中是廣泛采用的一種數(shù)據(jù)結(jié)構(gòu)。

在這里插入圖片描述

而我們說(shuō)的線性是指他的連續(xù)性，并非是內(nèi)存上連續(xù)，而是邏輯上連續(xù)，什么又是邏輯上連續(xù)？我們說(shuō)數(shù)據(jù)結(jié)構(gòu)有兩種結(jié)構(gòu)，一是物理結(jié)構(gòu)即在內(nèi)存中怎么存，二是邏輯結(jié)構(gòu)是我們假想的。物理結(jié)構(gòu)其實(shí)非數(shù)組即鏈表，基本都逃不開這倆，但數(shù)組有個(gè)致命的缺陷就是不知道咱要存多少，我開辟10個(gè)空間，若想存第11個(gè)就是放屁，那直接給他1000個(gè)空間呢？那剩下989個(gè)空間直接浪費(fèi)掉，一句話就是他不能按需所取。

這時(shí)鏈表就應(yīng)運(yùn)而生，我們有幾個(gè)數(shù)據(jù)就開辟幾個(gè)空間，眾所周知數(shù)組我們得到首元素地址，直接遍歷就能得到全部成員，那它怎么去串聯(lián)這些獨(dú)立零散的空間來(lái)建立聯(lián)系？我們按需所取首先就會(huì)選擇去堆區(qū)申請(qǐng)空間，去堆區(qū)不是一定是最好，因?yàn)?malloc 函數(shù)嘛，滿足要就拿不要就釋放。我們對(duì)數(shù)據(jù)尋蹤覓跡是通過(guò)其對(duì)應(yīng)的地址對(duì)吧，不難想到應(yīng)用指針吧，這樣那我們就可以“有備而來(lái)”，在開辟數(shù)據(jù)空間時(shí)多開辟4到8個(gè)字節(jié)來(lái)存放指針，最后一個(gè)數(shù)據(jù)我們不需要指針了，直接放一個(gè)空指針就行。

在這里插入圖片描述

順序表

線性表主要由順序表示或鏈?zhǔn)奖硎?。在?shí)際應(yīng)用中，常以棧、隊(duì)列、字符串等特殊形式使用。

順序表是在計(jì)算機(jī)內(nèi)存中以數(shù)組的形式保存的線性表，線性表的順序存儲(chǔ)是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的各個(gè)元素、使得線性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲(chǔ)在相鄰的物理存儲(chǔ)單元中，即通過(guò)數(shù)據(jù)元素物理存儲(chǔ)的相鄰關(guān)系來(lái)反映數(shù)據(jù)元素之間邏輯上的相鄰關(guān)系，采用順序存儲(chǔ)結(jié)構(gòu)的線性表通常稱為順序表。

我們說(shuō)過(guò)線性表中結(jié)構(gòu)不是物理就是邏輯，我們的順序表其實(shí)就是使用數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)，本質(zhì)上來(lái)說(shuō)順序表就是一個(gè)數(shù)組。

在這里插入圖片描述

拋開實(shí)際的代碼談概念就是耍流氓,我們采用工程化方式來(lái)寫一組代碼，在.h文件中進(jìn)行定義：

typedef int type;//便于隨時(shí)修改類型
#define n 10 //方便定義數(shù)組大小
struct SeqList
{
	type a[n];
	int size;
};
void PushBack(struct SeqList* p, type x);
void PopBack(struct SeqList* p, type x);
……
//后面這些為尾插，尾刪等接口來(lái)處理他們之間的關(guān)系

以上的代碼就是很多教材上的靜態(tài)順序表設(shè)計(jì)結(jié)構(gòu)，咱跳出來(lái)看看就會(huì)秒感很low，他是固定大小不能按需所取，其實(shí)就是封裝了一個(gè)數(shù)組，我們要變成動(dòng)態(tài)順序表很簡(jiǎn)單，增設(shè)一個(gè)capacity成員即可：

typedef int type;
#define n 10 
struct SeqList
{
	type a[n];
	int size;   //有效數(shù)據(jù)的個(gè)數(shù)
	int capacity;   //容量，即空間的大小
};
void PushBack(struct SeqList* p, type x);
void PopBack(struct SeqList* p, type x);
……

擴(kuò)容操作我們手動(dòng)操作，只需引入 realloc 函數(shù)即可，如果是將分配的內(nèi)存擴(kuò)大，則有以下情況：

如果當(dāng)前內(nèi)存段后面有需要的內(nèi)存空間，則直接擴(kuò)展這段內(nèi)存空間，realloc函數(shù)將返回原指針。如果當(dāng)前內(nèi)存段后面的空閑字節(jié)不夠，那么就使用堆中的第一個(gè)能夠滿足這一要求的內(nèi)存塊，將目前的數(shù)據(jù)復(fù)制到新的位置，并將原來(lái)的數(shù)據(jù)塊釋放掉，返回新的內(nèi)存塊位置。如果申請(qǐng)失敗，將返回NULL，此時(shí)，原來(lái)的指針仍然有效。

今天就到這里吧，摸了家人們，更多關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)線性表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: