柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu) 順序表和鏈表
柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu) 順序表和鏈表
1. 線性表
定義：線性表（ linear list ）是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。線性表是?種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊(duì)列、字符串...
相同特性包括邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。
邏輯結(jié)構(gòu):認(rèn)為想象出來的一種結(jié)構(gòu)。
物理結(jié)構(gòu)：數(shù)據(jù)在內(nèi)存中的存儲(chǔ)形式。
線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的?條直線。但是在物理結(jié)構(gòu)上并不?定是連續(xù)的，線性表在物理上存儲(chǔ)時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)。
2. 順序表(SeqList)/(sequence:順序的,list:列表）
2.1 概念與結(jié)構(gòu)
概念：順序表是用?段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，?般情況下采用數(shù)組存儲(chǔ)。
順序表和數(shù)組的區(qū)別？ 順序表的底層結(jié)構(gòu)是數(shù)組，對(duì)數(shù)組的封裝，實(shí)現(xiàn)了常用的增刪改查等接
對(duì)于線性表來說，邏輯結(jié)構(gòu)都是線性的，物理結(jié)構(gòu)不一定是線性的。
順序表的底層結(jié)構(gòu)就是數(shù)組。
?順序表是對(duì)數(shù)組（增加、刪除、修改、查找數(shù)據(jù)）來實(shí)現(xiàn)的，也就是對(duì)數(shù)組進(jìn)行封裝得到的。
2.2 分類
順序表分為靜態(tài)順序表和動(dòng)態(tài)順序表。
2.2.1靜態(tài)順序表
概念：使用定長(zhǎng)數(shù)組存儲(chǔ)元素。
靜態(tài)順序表缺陷：空間給少了不夠用，給多了造成空間浪費(fèi)
?2.2.2 動(dòng)態(tài)順序表
2.3 動(dòng)態(tài)順序表的實(shí)現(xiàn)?
包括對(duì)順序表的增刪查改。
定義三個(gè)文件，如下：
其中.h結(jié)尾的頭文件起著相當(dāng)于目錄的作用。?
動(dòng)態(tài)順序表實(shí)現(xiàn)的前提：
1.定義順序表的結(jié)構(gòu)
2.順序表的初始化
3.順序表的銷毀
接下來就是對(duì)順序表中數(shù)據(jù)的插入
順序表數(shù)據(jù)的插入包含頭插(SLPushFront)和尾插(SLPushBack)，接下來先介紹尾插。
尾插包含兩種情況：
1.空間充足
2.空間不足
?這時(shí)capacity表示的是空間容量（10），再插入數(shù)據(jù)后插入到size指向的位置（因?yàn)閿?shù)組的下標(biāo)是從0開始的），插入之后size要＋1，因?yàn)閟ize是有效數(shù)據(jù)個(gè)數(shù)。
空間不足的時(shí)候這時(shí)的capacity大小為3，再插入一個(gè)數(shù)據(jù)是肯定插不下的，這時(shí)就要對(duì)空間進(jìn)行增容了（realloc），但要如何增容呢？
其實(shí)增容是成倍數(shù)的增加，比如2、3、4.....
但很多人又有疑問了，為什么不一次增加一個(gè)呢？這樣不就沒有空間浪費(fèi)了嗎？
其實(shí)增容的操作本身就有一定的性能的消耗，若頻繁的增容會(huì)導(dǎo)致程序效率低下。
增容分兩種情況：
1.連續(xù)空間足夠，直接擴(kuò)容
2.連續(xù)空間不夠
? ?1）重新找一塊地址，分配足夠的空間
? ?2）拷貝數(shù)據(jù)到新的地址
? ?3）銷毀舊地址
柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu) 順序表和鏈表
相關(guān)鏈接
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場(chǎng)。
轉(zhuǎn)載請(qǐng)注明，如有侵權(quán)，聯(lián)系刪除。
Wish夢(mèng)想購
