線性表的定義
結(jié)構(gòu)：
1. 線性結(jié)構(gòu)： 結(jié)構(gòu)中的數(shù)據(jù)元素之間均滿足線性關(guān)系（一對(duì)一）紫皇。
2. 由若干個(gè)數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)元素底洗，稱為記錄涩澡；含有大量記錄的線性表稱為文件祝懂；同一線性表中的元素必須屬于同一對(duì)象票摇。
3. 線性表：n個(gè)數(shù)據(jù)元素的有限序列 數(shù)據(jù)元素/結(jié)點(diǎn)：原子類型或結(jié)構(gòu)類型 線性表長(zhǎng)度：線性表中元素個(gè)數(shù)n 位序：各線性元素都有一個(gè)確定的位置，即位序
非空線性表通常記作：（a1,a2,……a i,a i+1,……a n）砚蓬，a1:開始結(jié)點(diǎn)矢门、表頭結(jié)點(diǎn)，a n：終止結(jié)點(diǎn)灰蛙、表尾節(jié)點(diǎn)
抽象數(shù)據(jù)操作：
1. 線性表的抽象數(shù)據(jù)類型定義-創(chuàng)建刪除：
DestroyList(&L):釋放掉表中的存儲(chǔ)空間祟剔；ClearList(&L):將線性表恢復(fù)到空表狀態(tài)，未釋放存儲(chǔ)空間摩梧。
2. 線性表的抽象數(shù)據(jù)類型定義-查找：
ps：LocateElem:用指針的目的是提高操作的通用性
3. 組合的復(fù)雜操作：
①兩線性表的合并
當(dāng)找到與e相同的物延，則返回滿足equal（）關(guān)系的元素的位序，否則返回0仅父。
算法實(shí)現(xiàn)：
②歸并有序線性表
算法思路：先比較A叛薯、B兩線性表中的第一個(gè)元素，將較小的那一個(gè)取出放入新線性表C笙纤；再比較A耗溜、B兩線性表的元素，將較小的那一個(gè)取出放入新線性表C省容；重復(fù)此操作抖拴，直至A或者B的元素個(gè)數(shù)為0了，將剩下的表里面的元素全部插至C的末尾蓉冈。
算法實(shí)現(xiàn)：
ps：線性表中的元素有序排列城舞，可提高歸并算法的時(shí)間效率轩触。
順序表
順序表的存儲(chǔ)結(jié)構(gòu)
1. 線性表的順序表示：把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。
2. 存儲(chǔ)結(jié)構(gòu)：只要知道了線性表中第一個(gè)元素的存儲(chǔ)位置（基地址）家夺，那么線性表中任意一個(gè)元素脱柱，如第i個(gè)元素即可根據(jù)式子計(jì)算。
3. 線性表的動(dòng)態(tài)分配線性存儲(chǔ)：順序表SqList類型是結(jié)構(gòu)體類型拉馋，由三個(gè)域組成榨为。Elem指針域用來(lái)指示順序表的基地址；length域用來(lái)存儲(chǔ)當(dāng)前表長(zhǎng)煌茴；listsize用來(lái)存儲(chǔ)線性表當(dāng)前最大存儲(chǔ)容量随闺。（length域和listsize以元素個(gè)數(shù)為單位）
順序表基本操作的實(shí)現(xiàn)
1. 創(chuàng)建空線性表
算法思路：先分配一塊存儲(chǔ)空間；讓Elem指針域指向它的基地址蔓腐；將length域的值置為0
算法實(shí)現(xiàn)：
函數(shù)返回值Status類型是Int類型的別名矩乐，可以用OVERFLOW、OK等常量來(lái)代表函數(shù)執(zhí)行結(jié)果的不同狀態(tài)
2. 順序表的插入
ListInsert將在第i個(gè)元素和第i-1個(gè)元素之間插入新元素回论；為防止元素被覆蓋散罕，元素搬動(dòng)順序應(yīng)為由后往前搬動(dòng)，如圖傀蓉。
注意：
算法實(shí)現(xiàn)：
realloc：按新的容量分配新的存儲(chǔ)空間欧漱，并將原來(lái)空間里的數(shù)據(jù)拷貝到新的空間里摔认，釋放掉原來(lái)的空間毯侦。
若空間分配成功粱快，相應(yīng)地修改基地址指針域L.elem和存儲(chǔ)容量域L.listsize
3. 順序表的刪除
注意：
算法實(shí)現(xiàn)：
4. 插入和刪除操作的算法分析
最好和最壞情況下時(shí)間復(fù)雜度的分析：
平均情況下移動(dòng)元素次數(shù)的期望：
總結(jié)：順序表的插入和刪除操作的時(shí)間復(fù)雜度都是O(n)荧嵌；缺點(diǎn)：在平均情況下，需要移動(dòng)的表中元素為表中元素的一半放闺，當(dāng)順序表長(zhǎng)n很大時(shí)拜英，耗費(fèi)較大幕垦。
5. 順序表的查找
按位序查找（GetElem）：時(shí)間復(fù)雜度O(1)
按內(nèi)容查找（LocateElem）：從順序表的第一個(gè)元素逐一比較
ps：*（p++）指先比較p指向的元素和e的大小岳遥，再將p++奕翔；時(shí)間復(fù)雜度為O(n)裕寨。
6. 歸并有序的順序表
算法實(shí)現(xiàn)：
ps：加入紅色部分則實(shí)現(xiàn)并集操作
7. 順序表的優(yōu)缺點(diǎn)
線性鏈表
線性表（鏈表）的鏈?zhǔn)酱鎯?chǔ)
1. 鏈表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)： 用一組任意的（可連續(xù)浩蓉、也可不連續(xù)）存儲(chǔ)單元來(lái)存儲(chǔ)線性表的數(shù)據(jù)元素。
節(jié)點(diǎn)包含兩種信息域：1）數(shù)據(jù)域：存儲(chǔ)數(shù)據(jù)元素的信息 2）指針域：存儲(chǔ)數(shù)據(jù)間的邏輯鏈接信息
2. 分類
按連接方式分類
- 線性鏈表（單鏈表）
- 循環(huán)鏈表
- 雙向鏈表
按實(shí)現(xiàn)方式分類 - 靜態(tài)鏈表
- 動(dòng)態(tài)鏈表
線性鏈表
線性鏈表的動(dòng)態(tài)鏈?zhǔn)酱鎯?chǔ)：?jiǎn)捂湵?/h5>
1. 結(jié)構(gòu)特點(diǎn)： 鏈表中每個(gè)節(jié)點(diǎn)只包含一個(gè)用來(lái)指示直接后繼的指針域宾袜。（如老鷹捉小雞的小雞）
2. 頭指針： 用來(lái)指示鏈表第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置
-
最后一個(gè)結(jié)點(diǎn)的指針域?yàn)镹ULL
圖片.png
圖片.png - 假設(shè)L為單鏈表的頭指針捻艳，則L應(yīng)為L(zhǎng)inkList型變量。當(dāng)L=NULL時(shí)庆猫，該鏈表為空表
- 頭結(jié)點(diǎn)：在表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)认轨，其next域指向第一個(gè)元素結(jié)點(diǎn)，其data域可以不儲(chǔ)存任何信息月培，也可以用于儲(chǔ)存表長(zhǎng)等附加信息嘁字。帶頭結(jié)點(diǎn)的單鏈表中恩急，當(dāng)頭結(jié)點(diǎn)的next域?yàn)榭諘r(shí)，該鏈表為空表
- 帶頭結(jié)點(diǎn)vs不帶頭結(jié)點(diǎn)：
- 不帶頭結(jié)點(diǎn)的單鏈表：執(zhí)行添加操作時(shí)纪蜒，若添加的結(jié)點(diǎn)在第一個(gè)節(jié)點(diǎn)之前衷恭，則需要修改頭指針；執(zhí)行刪除操作時(shí)亦是如此纯续。
-
帶頭結(jié)點(diǎn)的單鏈表
①單鏈表的查找（按位序查找）：在單鏈表中随珠，要讀取第i個(gè)數(shù)據(jù)元素，必須從頭指針L出發(fā)猬错，先找到表中的第一個(gè)結(jié)點(diǎn)窗看；再順藤摸瓜，依次查找倦炒。
具體操作：
該操作的時(shí)間復(fù)雜度為O(n)显沈，在順序表中只需要O(1)。圖片.png
②單鏈表的插入：如果要將新元素e插入到第i個(gè)元素之前逢唤，則首先需要找到表中的第i-1個(gè)結(jié)點(diǎn)构罗，然后把輔助指針p指在第i-1個(gè)結(jié)點(diǎn)上；若需要插入在第一個(gè)結(jié)點(diǎn)之前智玻，則只需把p指在頭結(jié)點(diǎn)上遂唧。
具體操作：動(dòng)態(tài)分配一個(gè)新節(jié)點(diǎn)，用s指針指向這個(gè)新結(jié)點(diǎn)吊奢；將新元素e寫入這個(gè)結(jié)點(diǎn)盖彭；修改新結(jié)點(diǎn)的next指針域，讓它指向表中第i個(gè)結(jié)點(diǎn)页滚；修改p的next指針域召边，使它指向新插入的那個(gè)結(jié)點(diǎn)。
順序不能替換圖片.png
語(yǔ)言描述：
圖片.png
③單鏈表的刪除：如果要?jiǎng)h除第i個(gè)元素裹驰，則先將輔助指針p定位到第i-1個(gè)結(jié)點(diǎn)上隧熙，即被刪除結(jié)點(diǎn)的直接前驅(qū)；此外幻林，還需要引入一個(gè)輔助指針q用來(lái)指向被刪結(jié)點(diǎn)贞盯；然后，修改第i-1結(jié)點(diǎn)的next指針沪饺，使其指向被刪結(jié)點(diǎn)的直接后繼躏敢；再將被刪結(jié)點(diǎn)的值賦值給引用參數(shù)e；最后整葡，釋放掉被刪結(jié)點(diǎn)件余，即q所指的結(jié)點(diǎn)。
圖片.png
？是否可以不引入輔助指針q：若不引入啼器，則被刪結(jié)點(diǎn)無(wú)法被free掉旬渠，它將成為系統(tǒng)中的太空垃圾，一直占用著這部分的存儲(chǔ)空間端壳，直到程序運(yùn)行結(jié)束才會(huì)被釋放坟漱，可能造成內(nèi)存泄露的隱患。
具體操作：
圖片.png
④單鏈表的創(chuàng)建：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)的最大區(qū)別在于更哄，它是動(dòng)態(tài)結(jié)構(gòu)芋齿，鏈表所需的空間不必提前估算并分配，只需要按需實(shí)時(shí)動(dòng)態(tài)分配或釋放即可成翩。因此觅捆，建立單鏈表的過程即是從空鏈表開始，依次生成各個(gè)結(jié)點(diǎn)麻敌，并逐個(gè)插入到鏈表的過程栅炒。
具體操作：
（1）該算法建立的是從表尾到表頭逆向建立單鏈表
圖片.png
（2）建立的是從表頭到表尾正向建立單鏈表
首先，增設(shè)一個(gè)表尾指針T术羔，初始令其指向頭結(jié)點(diǎn)赢赊；其次，將插入的位置改為插入到表尾節(jié)點(diǎn)之后级历；在每次插入后释移，修改T指針，使其每次指向新插入的那個(gè)結(jié)點(diǎn)寥殖。
圖片.png
⑤歸并倆有序單鏈表：拆東墻補(bǔ)西墻玩讳，沒有分配任何其他的結(jié)點(diǎn)空間，而是將原來(lái)的單鏈表重新分解開嚼贡，按照數(shù)值大小連接成新的單鏈表熏纯。
圖片.png
線性鏈表的靜態(tài)鏈?zhǔn)酱鎯?chǔ)：靜態(tài)鏈表
1. 定義： 在實(shí)際開發(fā)中，可能會(huì)遇到不方便使用指針或動(dòng)態(tài)分配的情況粤策，比如沒有提供指針類型的編程語(yǔ)言樟澜，此時(shí)，可以采用一維數(shù)組來(lái)描述鏈表叮盘，這種實(shí)現(xiàn)的方法稱為靜態(tài)鏈表秩贰。
2. 結(jié)構(gòu)特點(diǎn)： 預(yù)先分配一個(gè)較大的數(shù)組空間，數(shù)組中的元素有倆域熊户，data域用來(lái)存儲(chǔ)結(jié)點(diǎn)的數(shù)據(jù)萍膛，cur域稱為游標(biāo)或指示器，用來(lái)存儲(chǔ)后繼結(jié)點(diǎn)在數(shù)組中的下標(biāo)嚷堡。
游標(biāo)cur用結(jié)點(diǎn)在數(shù)組中的相對(duì)位置來(lái)代替結(jié)點(diǎn)在內(nèi)存中的絕對(duì)位置（即指針），因此，靜態(tài)鏈表中的元素存儲(chǔ)位置可以是任意的蝌戒，插入和刪除時(shí)不需要移動(dòng)元素串塑，只需要修改游標(biāo)；但缺點(diǎn)是北苟，它與順序表一樣桩匪，需要提前分配一塊存儲(chǔ)空間，閑置的結(jié)點(diǎn)空間會(huì)雜亂地分布在數(shù)組中友鼻。
為了再利用這些空閑空間傻昙，可以利用cur域，將這些空閑的單元鏈接成一條備用鏈彩扔。
因此妆档，整個(gè)存儲(chǔ)空間中有兩條鏈表，一條是用來(lái)存儲(chǔ)線性表的靜態(tài)鏈表虫碉，另一條是空閑結(jié)點(diǎn)構(gòu)成的備用鏈表贾惦。可以約定將數(shù)組下標(biāo)為0的單元用作備用鏈表的頭結(jié)點(diǎn)敦捧，另外設(shè)置變量S來(lái)存儲(chǔ)鏈表的頭指針须板。可以用cur域的值為0來(lái)表示該結(jié)點(diǎn)是表尾節(jié)點(diǎn)兢卵。
3. 帶頭結(jié)點(diǎn)的靜態(tài)鏈表的操作
①按內(nèi)容查找：根據(jù)cur域在表中順鏈查找
②初始創(chuàng)建靜態(tài)鏈表：以space[0]作為頭結(jié)點(diǎn)
③插入結(jié)點(diǎn)時(shí)：若備用鏈表第一個(gè)結(jié)點(diǎn)非空习瑰，則刪除備用鏈表的第一個(gè)結(jié)點(diǎn)，將其下標(biāo)返回給插入算法秽荤，并將其作為待插入的新結(jié)點(diǎn)杰刽；反之，若備用鏈表已空（space[0].cur==0）王滤，則返回的是0贺嫂，表示分配空間失敗。
④靜態(tài)表中free的實(shí)現(xiàn)雁乡，即就是將被刪掉的結(jié)點(diǎn)回收入備用鏈表：將被刪結(jié)點(diǎn)插回備用鏈表表頭第喳，即插入在頭結(jié)點(diǎn)space[0]之后。
4. 靜態(tài)鏈表的優(yōu)缺點(diǎn)
兼具順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的部分特點(diǎn)踱稍，主要為不支持指針類型的編程語(yǔ)言提供了實(shí)現(xiàn)線性鏈表的方法曲饱。
- 優(yōu)點(diǎn)：插入和刪除操作時(shí)，只需要修改游標(biāo)珠月，不需要移動(dòng)元素扩淀。
- 缺點(diǎn)：和順序表一樣，需要提前分配大塊連續(xù)存儲(chǔ)空間啤挎，無(wú)法解決難以確定合適存儲(chǔ)規(guī)模的問題驻谆；失去順序存儲(chǔ)結(jié)構(gòu)隨機(jī)存取的優(yōu)勢(shì)卵凑，只能順序存取。
實(shí)例
1. 集合運(yùn)算的實(shí)現(xiàn)
思路：1）先依次輸入集合A中的各個(gè)元素胜臊，正序建立表示集合A 的靜態(tài)鏈表S勺卢，并且用輔助指針r指向集合A中的最后一個(gè)結(jié)點(diǎn)；而后象对，每輸入一個(gè)集合B的元素黑忱，b j+1（j的取值從0開始）。 2）在鏈表S中進(jìn)行查找勒魔，最多查找到指針為r的結(jié)點(diǎn)即可甫煞。 3）如果存在與b j+1相同的結(jié)點(diǎn)，則從S中刪除這個(gè)結(jié)點(diǎn)冠绢，否則抚吠，就把b j+1插入到r所指的結(jié)點(diǎn)之后。（集合B逆序排列在r所指結(jié)點(diǎn)之后）
循環(huán)鏈表和雙向鏈表
循環(huán)鏈表
1. 導(dǎo)言： 在實(shí)際生活中唐全，我們往往需要遍歷線性表埃跷，即需要逐一對(duì)表中的某結(jié)點(diǎn)做一些操作。
若我們需要按一定規(guī)律邮利，逐一對(duì)線性表中的各個(gè)結(jié)點(diǎn)進(jìn)行某種操作（稱為訪問）弥雹，使得某個(gè)結(jié)點(diǎn)均被且只被訪問一次。而該種操作用單鏈表實(shí)現(xiàn)延届，則只能從頭指針開始剪勿。
2. 循環(huán)鏈表定義： 表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)方庭。
3. 特點(diǎn)： 從表中的任意一個(gè)結(jié)點(diǎn)出發(fā)厕吉，都能遍歷所有結(jié)點(diǎn)。與線性鏈表操作基本一致械念，差別在于算法中的循環(huán)終止條件不是“p或p->next為空”头朱，而是他們是否等于頭指針或起點(diǎn)。
4. 與單鏈表的區(qū)別：
在單鏈表中龄减，如果只設(shè)置頭指針项钮，訪問表頭結(jié)點(diǎn)，僅需要O(1)時(shí)間希停，但訪問表尾結(jié)點(diǎn)烁巫，則需要O(n)時(shí)間，若要提高表尾結(jié)點(diǎn)的訪問效率宠能，就得增設(shè)尾指針亚隙。
而對(duì)于循環(huán)鏈表中，設(shè)置尾指針而不設(shè)置頭指針违崇，就可以做到訪問表頭和表尾結(jié)點(diǎn)都只需要O(1)時(shí)間阿弃。
5. 兩線性鏈表的頭尾相接（合并）： 當(dāng)需要做到兩線性鏈表頭尾相接诊霹，合并成一個(gè)表時(shí)，采用循環(huán)鏈表結(jié)構(gòu)恤浪，只需要修改兩個(gè)指針值畅哑，僅需要O(1)時(shí)間肴楷。
具體操作：1）先設(shè)置兩個(gè)輔助指針p和q水由，分別指向倆循環(huán)鏈表的頭結(jié)點(diǎn)； 2）修改表A的表尾結(jié)點(diǎn)指針赛蔫，使其指向表B的表頭結(jié)點(diǎn)砂客； 3）修改表B的表尾結(jié)點(diǎn)指針，使其指向表A的頭結(jié)點(diǎn)呵恢； 4）釋放掉表B的頭結(jié)點(diǎn)鞠值。
雙向鏈表
1. 導(dǎo)言： 由于單鏈表只有一個(gè)指向后繼結(jié)點(diǎn)的指針的特點(diǎn)，若用單鏈表找直接后繼僅需O(1)的時(shí)間渗钉，但要找直接前驅(qū)彤恶，則需O(n)的時(shí)間。為解決這個(gè)麻煩鳄橘，誕生了雙向鏈表声离，在雙向鏈表中，NextElem和PriorElem都僅需O(1)時(shí)間瘫怜。
2. 雙向鏈表定義： 鏈表的每個(gè)結(jié)點(diǎn)有兩個(gè)指針域术徊，一個(gè)指向直接后繼，另一個(gè)指向直接前驅(qū)鲸湃。（即小盆友手牽手排成一列）
3. 類型定義： 在單鏈表的基礎(chǔ)上多了一個(gè)用來(lái)指向直接前驅(qū)的prior指針域赠涮。
4. 存儲(chǔ)結(jié)構(gòu)：
5. 帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表：
這樣，循環(huán)鏈表就同時(shí)具有了兩個(gè)方向的環(huán)路暗挑。當(dāng)雙向循環(huán)鏈表為空時(shí)笋除，只有一個(gè)頭結(jié)點(diǎn)，且頭結(jié)點(diǎn)的next和prior都指向自己炸裆。
6. 帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表的操作
①ListLength垃它、GetElem和LocateElem只需要涉及一個(gè)方向的指針，和單鏈表一致晒衩。
②插入：將指針s所指的新結(jié)點(diǎn)插入到p指向的結(jié)點(diǎn)之前嗤瞎，無(wú)需引入其他的指針。
具體操作：1）令要插入的那個(gè)新結(jié)點(diǎn)的s指針的前驅(qū)指向p指向結(jié)點(diǎn)的前驅(qū) 2）令p指向的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的next指針指向新結(jié)點(diǎn) 3）令新結(jié)點(diǎn)的next指針指向p所指的結(jié)點(diǎn) 4）令p所指向結(jié)點(diǎn)的prior指針指向新結(jié)點(diǎn)
听系？這四個(gè)步驟的順序可以任意調(diào)換嗎贝奇？ 答：步驟四不能早于步驟一
具體算法實(shí)現(xiàn)：
③刪除：刪除p指向的結(jié)點(diǎn)，也無(wú)需引入輔助指針靠胜。
具體操作：1）使目標(biāo)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的next指針指向目標(biāo)結(jié)點(diǎn)的后繼 2）令目標(biāo)結(jié)點(diǎn)的后繼結(jié)點(diǎn)的prior指針指向目標(biāo)結(jié)點(diǎn)的前驅(qū) 3）釋放掉目標(biāo)刪除結(jié)點(diǎn)
順序可對(duì)換
具體算法實(shí)現(xiàn)：
順序表與鏈表的比較
（圖片為網(wǎng)絡(luò)課程自截掉瞳，侵刪）
