線性表

數(shù)據(jù)結(jié)構(gòu)里我們時?？吹绞裁词裁幢?，線性表是最基本、最簡單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)，其他各種表的萬惡之源就是這個線性表，他是個啥其實顧名思義：

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

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

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

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

順序表

線性表主要由順序表示或鏈式表示。在實際應用中，常以棧、隊列、字符串等特殊形式使用。

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

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

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

typedef int type;//便于隨時修改類型
#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);
……
//后面這些為尾插，尾刪等接口來處理他們之間的關(guān)系

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

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

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

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

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

最新評論