數(shù)據(jù)結(jié)構(gòu)：第二章 線性表

1、二、線性表2.1 線性表的邏輯結(jié)構(gòu)2.1.1 線性表的定義二、線性表線性結(jié)構(gòu)的基本特征為: 集合中必存在唯一的一個(gè)“第一元素” 集合中必存在唯一的一個(gè) “最后元素” 除最后元素之外，均有 唯一的后繼 除第一元素之外，均有 唯一的前驅(qū)n個(gè)數(shù)據(jù)元素的有限序列ABECFGD典型的線性表的應(yīng)用二、線性表二、線性表2.2 線性表的順序表示和實(shí)現(xiàn)2.2.1 順序存儲(chǔ)結(jié)構(gòu)的定義二、線性表 0 i-2 i-1 n-1 a1 ai-1 ai an kLoc(ai)Loc(a1)元素位置線性表的順序存儲(chǔ)的表示二、線性表2.2.2 線性表的順序存儲(chǔ)上的基本操作實(shí)現(xiàn)1.順序線性表的數(shù)據(jù)插入操作二、線性表從最末尾元素開(kāi)

2、始依次將前一個(gè)元素的值存于后一個(gè)空間注意邊界條件時(shí)間復(fù)雜度：O(n)二、線性表2.順序線性表的數(shù)據(jù)刪除操作依次將后一個(gè)元素的值存于前一個(gè)空間二、線性表時(shí)間復(fù)雜度：O(n)二、線性表3.順序線性表的定位操作時(shí)間復(fù)雜度：O(n)二、線性表5.順序線性表的取元素操作時(shí)間復(fù)雜度：O(1)二、線性表6.順序線性表的輸出操作時(shí)間復(fù)雜度：O(n)二、線性表線性表的順序存儲(chǔ)上的基本運(yùn)算的測(cè)試二、線性表7. 兩線性表的歸并操作(算法2.2)二、線性表7. 兩線性表的歸并操作(算法2.2)二、線性表時(shí)間復(fù)雜度：O(n+m)二、線性表LA中剩余的元素放入LC中LB中剩余的元素放入LC中二、線性表算法2.1 編寫(xiě)函數(shù)

3、實(shí)現(xiàn)求兩線性表的并集 void Union(SeqList &La, SeqList &Lb);二、線性表2.2.3 線性表順序存儲(chǔ)的特點(diǎn)二、線性表練習(xí)：1.編寫(xiě)函數(shù)實(shí)現(xiàn)求兩線性表的交集 SeqList InterSection(SeqList &La, SeqList &Lb);二、線性表2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1 單鏈表用任意的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，每個(gè)元素由結(jié)點(diǎn)(Node)構(gòu)成。data存儲(chǔ)節(jié)點(diǎn)值（數(shù)據(jù)域），next存儲(chǔ)元素的后繼節(jié)點(diǎn)的地址（指針域）結(jié)點(diǎn)可以連續(xù)，可以不連續(xù)存儲(chǔ)鏈表可擴(kuò)充鏈表的頭指針head指向鏈表的第一個(gè)節(jié)點(diǎn)（可能是頭結(jié)點(diǎn)）data nexta0a1a2a

4、3a4head二、線性表free(a) 可利用存儲(chǔ)空間a0a2a1a3freehead(b) 經(jīng)過(guò)一段運(yùn)行后的單鏈表結(jié)構(gòu)單鏈表的存儲(chǔ)映像:借助指針域，可以使得邏輯上相鄰的元素在物理位置上不用相連。二、線性表帶頭節(jié)點(diǎn)的單鏈表頭結(jié)點(diǎn)數(shù)據(jù)域不存儲(chǔ)任何信息，也可以存儲(chǔ)表長(zhǎng)等信息，頭節(jié)點(diǎn)的指針域指向第一個(gè)元素節(jié)點(diǎn)。二、線性表帶頭結(jié)點(diǎn)的單鏈表的存儲(chǔ)結(jié)構(gòu)二、線性表單鏈表上的基本運(yùn)算帶頭節(jié)點(diǎn)的空單鏈表的構(gòu)造函數(shù)頭指針二、線性表4.建立單鏈表(1)頭插法建表二、線性表二、線性表注意(1)語(yǔ)句必須在(2)語(yǔ)句之前，因?yàn)槿粽{(diào)換了兩者的位置，(2)語(yǔ)句改后的head-next已經(jīng)不是之前的指向值了。二、線性表(2) 尾插法建表二、線性表表收尾二、線性表1.取元素二、線性表2.插入元素二、線性表二、線性表3.刪除元素二、線性表二、線性表練習(xí)：1.實(shí)現(xiàn)單鏈表求表長(zhǎng)的成員函數(shù)；2.實(shí)現(xiàn)單鏈表清空的成員函數(shù)；headqheadheadqqheada0a1a1a2a2a2二、線性表練習(xí)：3.實(shí)現(xiàn)兩個(gè)非遞增的單鏈表的合并，合并后的單鏈表是個(gè)遞增鏈表。LinkList Merge(LinkList &L1,LinkList &L2);4.實(shí)現(xiàn)某帶頭節(jié)點(diǎn)的單鏈表的逆序操作。二、線性表2.3.2 雙向鏈表雙向鏈表是一種對(duì)稱結(jié)構(gòu)，顯然有:p-next-prior=p-pr