C語言數(shù)據(jù)結(jié)構(gòu)線性表教程示例詳解
線性表
數(shù)據(jù)結(jié)構(gòu)里我們時(shí)??吹绞裁词裁幢?,線性表是最基本、最簡單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu),其他各種表的萬惡之源就是這個(gè)線性表,他是個(gè)啥其實(shí)顧名思義:
一個(gè)線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。數(shù)據(jù)元素之間的關(guān)系是一對一的關(guān)系,即除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外,其它數(shù)據(jù)元素都是首尾相接的(注意,這句話只適用大部分線性表,而不是全部。比如,循環(huán)鏈表邏輯層次上也是一種線性表(存儲(chǔ)層次上屬于鏈?zhǔn)酱鎯?chǔ),但是把最后一個(gè)數(shù)據(jù)元素的尾指針指向了首位結(jié)點(diǎn))。
說的這么復(fù)雜其實(shí)就是下面這個(gè)模型,線性表的邏輯結(jié)構(gòu)簡單,便于實(shí)現(xiàn)和操作。因此,線性表這種數(shù)據(jù)結(jié)構(gòu)在實(shí)際應(yīng)用中是廣泛采用的一種數(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ù)組即鏈表,基本都逃不開這倆,但數(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ú)立零散的空間來建立聯(lián)系?我們按需所取首先就會(huì)選擇去堆區(qū)申請空間,去堆區(qū)不是一定是最好,因?yàn)?malloc 函數(shù)嘛, 滿足要就拿不要就釋放。我們對數(shù)據(jù)尋蹤覓跡是通過其對應(yīng)的地址對吧,不難想到應(yīng)用指針吧,這樣那我們就可以“有備而來”,在開辟數(shù)據(jù)空間時(shí)多開辟4到8個(gè)字節(jié)來存放指針,最后一個(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ǔ)單元中,即通過數(shù)據(jù)元素物理存儲(chǔ)的相鄰關(guān)系來反映數(shù)據(jù)元素之間邏輯上的相鄰關(guān)系,采用順序存儲(chǔ)結(jié)構(gòu)的線性表通常稱為順序表。
我們說過線性表中結(jié)構(gòu)不是物理就是邏輯,我們的順序表其實(shí)就是使用數(shù)組來存儲(chǔ)數(shù)據(jù),本質(zhì)上來說順序表就是一個(gè)數(shù)組。
拋開實(shí)際的代碼談概念就是耍流氓,我們采用工程化方式來寫一組代碼,在.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); …… //后面這些為尾插,尾刪等接口來處理他們之間的關(guān)系
以上的代碼就是很多教材上的靜態(tài)順序表設(shè)計(jì)結(jié)構(gòu),咱跳出來看看就會(huì)秒感很low,他是固定大小不能按需所取,其實(shí)就是封裝了一個(gè)數(shù)組,我們要變成動(dòng)態(tài)順序表很簡單,增設(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ù)制到新的位置,并將原來的數(shù)據(jù)塊釋放掉,返回新的內(nèi)存塊位置。如果申請失敗,將返回NULL,此時(shí),原來的指針仍然有效。
今天就到這里吧,摸了家人們,更多關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)線性表的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
C++中l(wèi)ist的使用與模擬實(shí)現(xiàn)
list相較于vector來說會(huì)顯得復(fù)雜,它的好處是在任意位置插入,刪除都是一個(gè)O(1)的時(shí)間復(fù)雜度,下面這篇文章主要給大家介紹了關(guān)于C++中l(wèi)ist的使用與模擬實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下2022-05-05QT網(wǎng)絡(luò)編程UDP下C/S架構(gòu)廣播通信(實(shí)例講解)
下面小編就為大家?guī)硪黄猀T網(wǎng)絡(luò)編程UDP下C/S架構(gòu)廣播通信(實(shí)例講解)。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-07-07Qt實(shí)現(xiàn)FTP的上傳和下載的實(shí)例代碼
本篇文章主要介紹了Qt實(shí)現(xiàn)FTP的上傳和下載的實(shí)例代碼,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-07-07使用MinGW使Windows通過gcc實(shí)現(xiàn)C或C++程序本地編譯執(zhí)行的方法
這篇文章主要介紹了使用MinGW使Windows通過gcc實(shí)現(xiàn)C或C++程序本地編譯執(zhí)行的方法,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-11-11C++實(shí)踐數(shù)組類運(yùn)算的實(shí)現(xiàn)參考
今天小編就為大家分享一篇關(guān)于C++實(shí)踐數(shù)組類運(yùn)算的實(shí)現(xiàn)參考,小編覺得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來看看吧2019-02-02