Num01-->線性表定義及順序表和鏈表
在程序中锭环，經(jīng)常需要將一組（通常是同為某個(gè)類型的）數(shù)據(jù)元素作為整體管理和使用奋刽，需要?jiǎng)?chuàng)建這種元素組，用變量記錄它們，傳進(jìn)傳出函數(shù)等。一組數(shù)據(jù)中包含的元素個(gè)數(shù)可能發(fā)生變化（可以增加或刪除元素）。
對(duì)于這種需求陶缺，最簡(jiǎn)單的解決方案便是將這樣一組元素看成一個(gè)序列，用元素在序列里的位置和順序洁灵，表示實(shí)際應(yīng)用中的某種有意義的信息饱岸，或者表示數(shù)據(jù)之間的某種關(guān)系。
這樣的一組序列元素的組織形式徽千，我們可以將其抽象為線性表苫费。
一個(gè)線性表是某類元素的一個(gè)集合，還記錄著元素之間的一種順序關(guān)系双抽。線性表是最基本的數(shù)據(jù)結(jié)構(gòu)之一百框，在實(shí)際程序中應(yīng)用非常廣泛，它還經(jīng)常被用作更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)基礎(chǔ)牍汹。
根據(jù)線性表的實(shí)際存儲(chǔ)方式铐维，分為兩種實(shí)現(xiàn)模型：
1柬泽、順序表，將元素順序地存放在一塊連續(xù)的存儲(chǔ)區(qū)里方椎，元素間的順序關(guān)系由它們的存儲(chǔ)順序自然表示。
2钧嘶、鏈表棠众，將元素存放在通過鏈接構(gòu)造起來的一系列存儲(chǔ)塊中。
Num02-->順序表的基本形式
這里寫圖片描述
圖a表示的是順序表的基本形式有决，數(shù)據(jù)元素本身連續(xù)存儲(chǔ)闸拿，每個(gè)元素所占的存儲(chǔ)單元大小固定相同，元素的下標(biāo)是其邏輯地址书幕，而元素存儲(chǔ)的物理地址（實(shí)際內(nèi)存地址）可以通過存儲(chǔ)區(qū)的起始地址Loc (e0)加上邏輯地址（第i個(gè)元素）與存儲(chǔ)單元大行禄纭（c）的乘積計(jì)算而得，即：
Loc(ei) = Loc(e0) + c*i
故台汇，訪問指定元素時(shí)無需從頭遍歷苛骨，通過計(jì)算便可獲得對(duì)應(yīng)地址，其時(shí)間復(fù)雜度為O(1)苟呐。
如果元素的大小不統(tǒng)一痒芝，則須采用圖b的元素外置的形式，將實(shí)際數(shù)據(jù)元素另行存儲(chǔ)牵素，而順序表中各單元位置保存對(duì)應(yīng)元素的地址信息（即鏈接）严衬。由于每個(gè)鏈接所需的存儲(chǔ)量相同，通過上述公式笆呆，可以計(jì)算出元素鏈接的存儲(chǔ)位置请琳，而后順著鏈接找到實(shí)際存儲(chǔ)的數(shù)據(jù)元素。注意赠幕，圖b中的c不再是數(shù)據(jù)元素的大小俄精，而是存儲(chǔ)一個(gè)鏈接地址所需的存儲(chǔ)量，這個(gè)量通常很小榕堰。
圖b這樣的順序表也被稱為對(duì)實(shí)際數(shù)據(jù)的索引嘀倒，這是最簡(jiǎn)單的索引結(jié)構(gòu)。
Num03-->順序表的結(jié)構(gòu)與實(shí)現(xiàn)
Test01-->順序表的結(jié)構(gòu)
這里寫圖片描述
一個(gè)順序表的完整信息包括兩部分：
一部分是表中的元素集合局冰；
另一部分是為實(shí)現(xiàn)正確操作而需記錄的信息测蘑，即有關(guān)表的整體情況的信息，這部分信息主要包括元素存儲(chǔ)區(qū)的容量和當(dāng)前表中已有的元素個(gè)數(shù)兩項(xiàng)康二。
Test02-->順序表的兩種基本實(shí)現(xiàn)
這里寫圖片描述
圖a為一體式結(jié)構(gòu)碳胳，存儲(chǔ)表信息的單元與元素存儲(chǔ)區(qū)以連續(xù)的方式安排在一塊存儲(chǔ)區(qū)里，兩部分?jǐn)?shù)據(jù)的整體形成一個(gè)完整的順序表對(duì)象沫勿。
一體式結(jié)構(gòu)整體性強(qiáng)挨约，易于管理味混。但是由于數(shù)據(jù)元素存儲(chǔ)區(qū)域是表對(duì)象的一部分，順序表創(chuàng)建后诫惭，元素存儲(chǔ)區(qū)就固定了翁锡。
圖b為分離式結(jié)構(gòu)，表對(duì)象里只保存與整個(gè)表有關(guān)的信息（即容量和元素個(gè)數(shù)）夕土，實(shí)際數(shù)據(jù)元素存放在另一個(gè)獨(dú)立的元素存儲(chǔ)區(qū)里馆衔，通過鏈接與基本表對(duì)象關(guān)聯(lián)。
Test03-->順序表元素存儲(chǔ)區(qū)替換
一體式結(jié)構(gòu)由于順序表信息區(qū)與數(shù)據(jù)區(qū)連續(xù)存儲(chǔ)在一起怨绣，所以若想更換數(shù)據(jù)區(qū)角溃，則只能整體搬遷，即整個(gè)順序表對(duì)象（指存儲(chǔ)順序表的結(jié)構(gòu)信息的區(qū)域）改變了篮撑。
分離式結(jié)構(gòu)若想更換數(shù)據(jù)區(qū)减细，只需將表信息區(qū)中的數(shù)據(jù)區(qū)鏈接地址更新即可，而該順序表對(duì)象不變赢笨。
Test04-->順序表元素存儲(chǔ)區(qū)擴(kuò)充
采用分離式結(jié)構(gòu)的順序表未蝌，若將數(shù)據(jù)區(qū)更換為存儲(chǔ)空間更大的區(qū)域，則可以在不改變表對(duì)象的前提下對(duì)其數(shù)據(jù)存儲(chǔ)區(qū)進(jìn)行了擴(kuò)充茧妒，所有使用這個(gè)表的地方都不必修改树埠。只要程序的運(yùn)行環(huán)境（計(jì)算機(jī)系統(tǒng)）還有空閑存儲(chǔ)，這種表結(jié)構(gòu)就不會(huì)因?yàn)闈M了而導(dǎo)致操作無法進(jìn)行嘶伟。人們把采用這種技術(shù)實(shí)現(xiàn)的順序表稱為動(dòng)態(tài)順序表怎憋，因?yàn)槠淙萘靠梢栽谑褂弥袆?dòng)態(tài)變化。
擴(kuò)充的兩種策略：
第一種：每次擴(kuò)充增加固定數(shù)目的存儲(chǔ)位置九昧，如每次擴(kuò)充增加10個(gè)元素位置绊袋，這種策略可稱為線性增長(zhǎng)。
特點(diǎn)：節(jié)省空間铸鹰，但是擴(kuò)充操作頻繁癌别，操作次數(shù)多。
第二種：每次擴(kuò)充容量加倍蹋笼，如每次擴(kuò)充增加一倍存儲(chǔ)空間展姐。
特點(diǎn)：減少了擴(kuò)充操作的執(zhí)行次數(shù)，但可能會(huì)浪費(fèi)空間資源剖毯。以空間換時(shí)間圾笨，推薦的方式。
Num04-->順序表的操作
Test01-->增加
如圖所示逊谋，為順序表增加新元素111的三種方式
這里寫圖片描述
a. 尾端加入元素擂达，時(shí)間復(fù)雜度為O(1)
b. 非保序的加入元素（不常見），時(shí)間復(fù)雜度為O(1)
c. 保序的元素加入胶滋，時(shí)間復(fù)雜度為O(n)
Test02-->刪除
這里寫圖片描述
a. 刪除表尾元素板鬓，時(shí)間復(fù)雜度為O(1)
b. 非保序的元素刪除（不常見）悲敷，時(shí)間復(fù)雜度為O(1)
c. 保序的元素刪除，時(shí)間復(fù)雜度為O(n)
