線性表

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

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

說的這么復雜其實就是下面這個模型，線性表的邏輯結構簡單，便于實現和操作。因此，線性表這種數據結構在實際應用中是廣泛采用的一種數據結構。

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

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

順序表

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

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

我們說過線性表中結構不是物理就是邏輯，我們的順序表其實就是使用數組來存儲數據，本質上來說順序表就是一個數組。

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

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

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

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

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

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

今天就到這里吧，摸了家人們，更多關于C語言數據結構線性表的資料請關注腳本之家其它相關文章！

最新評論