線性表的定義
結(jié)構(gòu)：
1. 線性結(jié)構(gòu)： 結(jié)構(gòu)中的數(shù)據(jù)元素之間均滿足線性關(guān)系（一對一）。
2. 由若干個數(shù)據(jù)項組成的數(shù)據(jù)元素，稱為記錄；含有大量記錄的線性表稱為文件；同一線性表中的元素必須屬于同一對象。
3. 線性表：n個數(shù)據(jù)元素的有限序列 數(shù)據(jù)元素/結(jié)點：原子類型或結(jié)構(gòu)類型 線性表長度：線性表中元素個數(shù)n 位序：各線性元素都有一個確定的位置，即位序
非空線性表通常記作：（a1,a2,……a i,a i+1,……a n），a1:開始結(jié)點、表頭結(jié)點，a n：終止結(jié)點、表尾節(jié)點
抽象數(shù)據(jù)操作：
1. 線性表的抽象數(shù)據(jù)類型定義-創(chuàng)建刪除：
DestroyList(&L):釋放掉表中的存儲空間；ClearList(&L):將線性表恢復(fù)到空表狀態(tài)，未釋放存儲空間。
2. 線性表的抽象數(shù)據(jù)類型定義-查找：
ps：LocateElem:用指針的目的是提高操作的通用性
3. 組合的復(fù)雜操作：
①兩線性表的合并
當(dāng)找到與e相同的，則返回滿足equal（）關(guān)系的元素的位序，否則返回0。
算法實現(xiàn)：
②歸并有序線性表
算法思路：先比較A、B兩線性表中的第一個元素，將較小的那一個取出放入新線性表C；再比較A、B兩線性表的元素，將較小的那一個取出放入新線性表C；重復(fù)此操作，直至A或者B的元素個數(shù)為0了，將剩下的表里面的元素全部插至C的末尾。
算法實現(xiàn)：
ps：線性表中的元素有序排列，可提高歸并算法的時間效率。
順序表
順序表的存儲結(jié)構(gòu)
1. 線性表的順序表示：把線性表的結(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。
2. 存儲結(jié)構(gòu)：只要知道了線性表中第一個元素的存儲位置（基地址），那么線性表中任意一個元素，如第i個元素即可根據(jù)式子計算。
3. 線性表的動態(tài)分配線性存儲：順序表SqList類型是結(jié)構(gòu)體類型，由三個域組成。Elem指針域用來指示順序表的基地址；length域用來存儲當(dāng)前表長；listsize用來存儲線性表當(dāng)前最大存儲容量。（length域和listsize以元素個數(shù)為單位）
順序表基本操作的實現(xiàn)
1. 創(chuàng)建空線性表
算法思路：先分配一塊存儲空間；讓Elem指針域指向它的基地址；將length域的值置為0
算法實現(xiàn)：
函數(shù)返回值Status類型是Int類型的別名，可以用OVERFLOW、OK等常量來代表函數(shù)執(zhí)行結(jié)果的不同狀態(tài)
2. 順序表的插入
ListInsert將在第i個元素和第i-1個元素之間插入新元素；為防止元素被覆蓋，元素搬動順序應(yīng)為由后往前搬動，如圖。
注意：
算法實現(xiàn)：
realloc：按新的容量分配新的存儲空間，并將原來空間里的數(shù)據(jù)拷貝到新的空間里，釋放掉原來的空間。
若空間分配成功，相應(yīng)地修改基地址指針域L.elem和存儲容量域L.listsize
3. 順序表的刪除
注意：
算法實現(xiàn)：
4. 插入和刪除操作的算法分析
最好和最壞情況下時間復(fù)雜度的分析：
平均情況下移動元素次數(shù)的期望：
總結(jié)：順序表的插入和刪除操作的時間復(fù)雜度都是O(n)；缺點：在平均情況下，需要移動的表中元素為表中元素的一半，當(dāng)順序表長n很大時，耗費較大。
5. 順序表的查找
按位序查找（GetElem）：時間復(fù)雜度O(1)
按內(nèi)容查找（LocateElem）：從順序表的第一個元素逐一比較
ps：*（p++）指先比較p指向的元素和e的大小，再將p++；時間復(fù)雜度為O(n)。
6. 歸并有序的順序表
算法實現(xiàn)：
ps：加入紅色部分則實現(xiàn)并集操作
7. 順序表的優(yōu)缺點
線性鏈表
線性表（鏈表）的鏈?zhǔn)酱鎯?/h4>
1. 鏈表的鏈?zhǔn)酱鎯Y(jié)構(gòu)： 用一組任意的（可連續(xù)、也可不連續(xù)）存儲單元來存儲線性表的數(shù)據(jù)元素。
節(jié)點包含兩種信息域：1）數(shù)據(jù)域：存儲數(shù)據(jù)元素的信息 2）指針域：存儲數(shù)據(jù)間的邏輯鏈接信息
2. 分類
按連接方式分類
- 線性鏈表（單鏈表）
- 循環(huán)鏈表
- 雙向鏈表
按實現(xiàn)方式分類 - 靜態(tài)鏈表
- 動態(tài)鏈表
線性鏈表
線性鏈表的動態(tài)鏈?zhǔn)酱鎯Γ簡捂湵?/h5>
1. 結(jié)構(gòu)特點： 鏈表中每個節(jié)點只包含一個用來指示直接后繼的指針域。（如老鷹捉小雞的小雞）
2. 頭指針： 用來指示鏈表第一個結(jié)點的存儲位置
-
最后一個結(jié)點的指針域為NULL
圖片.png
圖片.png - 假設(shè)L為單鏈表的頭指針，則L應(yīng)為LinkList型變量。當(dāng)L=NULL時，該鏈表為空表
- 頭結(jié)點：在表的第一個結(jié)點之前附設(shè)一個結(jié)點，其next域指向第一個元素結(jié)點，其data域可以不儲存任何信息，也可以用于儲存表長等附加信息。帶頭結(jié)點的單鏈表中，當(dāng)頭結(jié)點的next域為空時，該鏈表為空表
- 帶頭結(jié)點vs不帶頭結(jié)點：
- 不帶頭結(jié)點的單鏈表：執(zhí)行添加操作時，若添加的結(jié)點在第一個節(jié)點之前，則需要修改頭指針；執(zhí)行刪除操作時亦是如此。
-
帶頭結(jié)點的單鏈表
①單鏈表的查找（按位序查找）：在單鏈表中，要讀取第i個數(shù)據(jù)元素，必須從頭指針L出發(fā)，先找到表中的第一個結(jié)點；再順藤摸瓜，依次查找。
具體操作：
該操作的時間復(fù)雜度為O(n)，在順序表中只需要O(1)。圖片.png
②單鏈表的插入：如果要將新元素e插入到第i個元素之前，則首先需要找到表中的第i-1個結(jié)點，然后把輔助指針p指在第i-1個結(jié)點上；若需要插入在第一個結(jié)點之前，則只需把p指在頭結(jié)點上。
具體操作：動態(tài)分配一個新節(jié)點，用s指針指向這個新結(jié)點；將新元素e寫入這個結(jié)點；修改新結(jié)點的next指針域，讓它指向表中第i個結(jié)點；修改p的next指針域，使它指向新插入的那個結(jié)點。
順序不能替換圖片.png
語言描述：
圖片.png
③單鏈表的刪除：如果要刪除第i個元素，則先將輔助指針p定位到第i-1個結(jié)點上，即被刪除結(jié)點的直接前驅(qū)；此外，還需要引入一個輔助指針q用來指向被刪結(jié)點；然后，修改第i-1結(jié)點的next指針，使其指向被刪結(jié)點的直接后繼；再將被刪結(jié)點的值賦值給引用參數(shù)e；最后，釋放掉被刪結(jié)點，即q所指的結(jié)點。
圖片.png
？是否可以不引入輔助指針q：若不引入，則被刪結(jié)點無法被free掉，它將成為系統(tǒng)中的太空垃圾，一直占用著這部分的存儲空間，直到程序運行結(jié)束才會被釋放，可能造成內(nèi)存泄露的隱患。
具體操作：
圖片.png
④單鏈表的創(chuàng)建：鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)的最大區(qū)別在于，它是動態(tài)結(jié)構(gòu)，鏈表所需的空間不必提前估算并分配，只需要按需實時動態(tài)分配或釋放即可。因此，建立單鏈表的過程即是從空鏈表開始，依次生成各個結(jié)點，并逐個插入到鏈表的過程。
具體操作：
（1）該算法建立的是從表尾到表頭逆向建立單鏈表
圖片.png
（2）建立的是從表頭到表尾正向建立單鏈表
首先，增設(shè)一個表尾指針T，初始令其指向頭結(jié)點；其次，將插入的位置改為插入到表尾節(jié)點之后；在每次插入后，修改T指針，使其每次指向新插入的那個結(jié)點。
圖片.png
⑤歸并倆有序單鏈表：拆東墻補西墻，沒有分配任何其他的結(jié)點空間，而是將原來的單鏈表重新分解開，按照數(shù)值大小連接成新的單鏈表。
圖片.png
線性鏈表的靜態(tài)鏈?zhǔn)酱鎯Γ红o態(tài)鏈表
1. 定義： 在實際開發(fā)中，可能會遇到不方便使用指針或動態(tài)分配的情況，比如沒有提供指針類型的編程語言，此時，可以采用一維數(shù)組來描述鏈表，這種實現(xiàn)的方法稱為靜態(tài)鏈表。
2. 結(jié)構(gòu)特點： 預(yù)先分配一個較大的數(shù)組空間，數(shù)組中的元素有倆域，data域用來存儲結(jié)點的數(shù)據(jù)，cur域稱為游標(biāo)或指示器，用來存儲后繼結(jié)點在數(shù)組中的下標(biāo)。
游標(biāo)cur用結(jié)點在數(shù)組中的相對位置來代替結(jié)點在內(nèi)存中的絕對位置（即指針），因此，靜態(tài)鏈表中的元素存儲位置可以是任意的，插入和刪除時不需要移動元素，只需要修改游標(biāo)；但缺點是，它與順序表一樣，需要提前分配一塊存儲空間，閑置的結(jié)點空間會雜亂地分布在數(shù)組中。
為了再利用這些空閑空間，可以利用cur域，將這些空閑的單元鏈接成一條備用鏈。
因此，整個存儲空間中有兩條鏈表，一條是用來存儲線性表的靜態(tài)鏈表，另一條是空閑結(jié)點構(gòu)成的備用鏈表?？梢约s定將數(shù)組下標(biāo)為0的單元用作備用鏈表的頭結(jié)點，另外設(shè)置變量S來存儲鏈表的頭指針?？梢杂胏ur域的值為0來表示該結(jié)點是表尾節(jié)點。
3. 帶頭結(jié)點的靜態(tài)鏈表的操作
①按內(nèi)容查找：根據(jù)cur域在表中順鏈查找
②初始創(chuàng)建靜態(tài)鏈表：以space[0]作為頭結(jié)點
③插入結(jié)點時：若備用鏈表第一個結(jié)點非空，則刪除備用鏈表的第一個結(jié)點，將其下標(biāo)返回給插入算法，并將其作為待插入的新結(jié)點；反之，若備用鏈表已空（space[0].cur==0），則返回的是0，表示分配空間失敗。
④靜態(tài)表中free的實現(xiàn)，即就是將被刪掉的結(jié)點回收入備用鏈表：將被刪結(jié)點插回備用鏈表表頭，即插入在頭結(jié)點space[0]之后。
4. 靜態(tài)鏈表的優(yōu)缺點
兼具順序存儲和鏈?zhǔn)酱鎯Φ牟糠痔攸c，主要為不支持指針類型的編程語言提供了實現(xiàn)線性鏈表的方法。
- 優(yōu)點：插入和刪除操作時，只需要修改游標(biāo)，不需要移動元素。
- 缺點：和順序表一樣，需要提前分配大塊連續(xù)存儲空間，無法解決難以確定合適存儲規(guī)模的問題；失去順序存儲結(jié)構(gòu)隨機(jī)存取的優(yōu)勢，只能順序存取。
實例
1. 集合運算的實現(xiàn)
思路：1）先依次輸入集合A中的各個元素，正序建立表示集合A 的靜態(tài)鏈表S，并且用輔助指針r指向集合A中的最后一個結(jié)點；而后，每輸入一個集合B的元素，b j+1（j的取值從0開始）。 2）在鏈表S中進(jìn)行查找，最多查找到指針為r的結(jié)點即可。 3）如果存在與b j+1相同的結(jié)點，則從S中刪除這個結(jié)點，否則，就把b j+1插入到r所指的結(jié)點之后。（集合B逆序排列在r所指結(jié)點之后）
循環(huán)鏈表和雙向鏈表
循環(huán)鏈表
1. 導(dǎo)言： 在實際生活中，我們往往需要遍歷線性表，即需要逐一對表中的某結(jié)點做一些操作。
若我們需要按一定規(guī)律，逐一對線性表中的各個結(jié)點進(jìn)行某種操作（稱為訪問），使得某個結(jié)點均被且只被訪問一次。而該種操作用單鏈表實現(xiàn)，則只能從頭指針開始。
2. 循環(huán)鏈表定義： 表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。
3. 特點： 從表中的任意一個結(jié)點出發(fā)，都能遍歷所有結(jié)點。與線性鏈表操作基本一致，差別在于算法中的循環(huán)終止條件不是“p或p->next為空”，而是他們是否等于頭指針或起點。
4. 與單鏈表的區(qū)別：
在單鏈表中，如果只設(shè)置頭指針，訪問表頭結(jié)點，僅需要O(1)時間，但訪問表尾結(jié)點，則需要O(n)時間，若要提高表尾結(jié)點的訪問效率，就得增設(shè)尾指針。
而對于循環(huán)鏈表中，設(shè)置尾指針而不設(shè)置頭指針，就可以做到訪問表頭和表尾結(jié)點都只需要O(1)時間。
5. 兩線性鏈表的頭尾相接（合并）： 當(dāng)需要做到兩線性鏈表頭尾相接，合并成一個表時，采用循環(huán)鏈表結(jié)構(gòu)，只需要修改兩個指針值，僅需要O(1)時間。
具體操作：1）先設(shè)置兩個輔助指針p和q，分別指向倆循環(huán)鏈表的頭結(jié)點； 2）修改表A的表尾結(jié)點指針，使其指向表B的表頭結(jié)點； 3）修改表B的表尾結(jié)點指針，使其指向表A的頭結(jié)點； 4）釋放掉表B的頭結(jié)點。
雙向鏈表
1. 導(dǎo)言： 由于單鏈表只有一個指向后繼結(jié)點的指針的特點，若用單鏈表找直接后繼僅需O(1)的時間，但要找直接前驅(qū)，則需O(n)的時間。為解決這個麻煩，誕生了雙向鏈表，在雙向鏈表中，NextElem和PriorElem都僅需O(1)時間。
2. 雙向鏈表定義： 鏈表的每個結(jié)點有兩個指針域，一個指向直接后繼，另一個指向直接前驅(qū)。（即小盆友手牽手排成一列）
3. 類型定義： 在單鏈表的基礎(chǔ)上多了一個用來指向直接前驅(qū)的prior指針域。
4. 存儲結(jié)構(gòu)：
5. 帶頭結(jié)點的雙向循環(huán)鏈表：
這樣，循環(huán)鏈表就同時具有了兩個方向的環(huán)路。當(dāng)雙向循環(huán)鏈表為空時，只有一個頭結(jié)點，且頭結(jié)點的next和prior都指向自己。
6. 帶頭結(jié)點的雙向循環(huán)鏈表的操作
①ListLength、GetElem和LocateElem只需要涉及一個方向的指針，和單鏈表一致。
②插入：將指針s所指的新結(jié)點插入到p指向的結(jié)點之前，無需引入其他的指針。
具體操作：1）令要插入的那個新結(jié)點的s指針的前驅(qū)指向p指向結(jié)點的前驅(qū) 2）令p指向的結(jié)點的前驅(qū)結(jié)點的next指針指向新結(jié)點 3）令新結(jié)點的next指針指向p所指的結(jié)點 4）令p所指向結(jié)點的prior指針指向新結(jié)點
？這四個步驟的順序可以任意調(diào)換嗎？ 答：步驟四不能早于步驟一
具體算法實現(xiàn)：
③刪除：刪除p指向的結(jié)點，也無需引入輔助指針。
具體操作：1）使目標(biāo)結(jié)點的前驅(qū)結(jié)點的next指針指向目標(biāo)結(jié)點的后繼 2）令目標(biāo)結(jié)點的后繼結(jié)點的prior指針指向目標(biāo)結(jié)點的前驅(qū) 3）釋放掉目標(biāo)刪除結(jié)點
順序可對換
具體算法實現(xiàn)：
順序表與鏈表的比較
（圖片為網(wǎng)絡(luò)課程自截，侵刪）
