2022年浙江自考數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)筆記第二章：線性表

時間：2022-09-21 17:54:55 作者：儲老師

　　以下自考復(fù)習(xí)資料均由浙江自考網(wǎng)整理并發(fā)布，考生想要了解更多關(guān)于浙江自考報(bào)名、考試、成績查詢、畢業(yè)、歷年真題、常見問答等相關(guān)信息請關(guān)注浙江自考網(wǎng)，獲取浙江自考更多信息。
　線性表是由n≥0個數(shù)據(jù)元素組成的有限序列。n=0是空表；非空表，只能有一個開始結(jié)點(diǎn)，有且只能有一個終端結(jié)點(diǎn)。

　線性表上定義的基本運(yùn)算：·構(gòu)造空表：Initlist(L)
·求表長：Listlength(L)
·取結(jié)點(diǎn)：GetNode(L,i)
·查找：LocateNode(L,x)·插入：InsertList(L,x,i)
·刪除：Delete(L,i)

　　順序表是按線性表的邏輯結(jié)構(gòu)次序依次存放在一組地址連續(xù)的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結(jié)構(gòu)中各結(jié)點(diǎn)相鄰關(guān)系是一致的。地址計(jì)算：LOCa(i)=LOCa(1)+(i-1)*d；（首地址為1）
　　在順序表中實(shí)現(xiàn)的基本運(yùn)算： ·插入：平均移動結(jié)點(diǎn)次數(shù)為n/2；平均時間復(fù)雜度均為O(n)。
　　·刪除：平均移動結(jié)點(diǎn)次數(shù)為（n-1）/2；平均時間復(fù)雜度均為O(n)。
線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同，為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲每個結(jié)點(diǎn)值的同時，還存儲了其后繼結(jié)點(diǎn)的地址信息(即指針或鏈)。這兩部分信息組成鏈表中的結(jié)點(diǎn)結(jié)構(gòu)。一個單鏈表由頭指針的名字來命名。

　　單鏈表運(yùn)算：·建立單鏈表·頭插法：s->next=head；head=s；生成的順序與輸入順序相反。平均時間復(fù)雜度均為O(n)。
·尾插法：head=rear=null；if(head=null) head=s;else r->next=s;r=s; 平均時間復(fù)雜度均為O(n)
·加頭結(jié)點(diǎn)的算法：對開始結(jié)點(diǎn)的操作無需特殊處理，統(tǒng)一了空表和非空表。
·查找·按序號：與查找位置有關(guān)，平均時間復(fù)雜度均為O(n)。
·按值：與輸入實(shí)例有關(guān)，平均時間復(fù)雜度均為O(n)。
·插入運(yùn)算：p=GetNode(L,i-1)；s->next=p->next；p->next=s；平均時間復(fù)雜度均為O(n)
·刪除運(yùn)算：p=GetNode(L,i-1)；r=p->next；p->next=r->next；free(r)；平均時間復(fù)雜度均為O(n)

　　單循環(huán)鏈表是一種首尾相接的單鏈表，終端結(jié)點(diǎn)的指針域指向開始結(jié)點(diǎn)或頭結(jié)點(diǎn)。鏈表終止條件是以指針等于頭指針或尾指針。采用單循環(huán)鏈表在實(shí)用中多采用尾指針表示單循環(huán)鏈表。優(yōu)點(diǎn)是查找頭指針和尾指針的時間都是O(1)，不用遍歷整個鏈表。

雙鏈表就是雙向鏈表，就是在單鏈表的每個結(jié)點(diǎn)里再增加一個指向其直接前趨的指針域prior,形成兩條不同方向的鏈。由頭指針head惟一確定。
雙鏈表也可以頭尾相鏈接構(gòu)成雙(向)循環(huán)鏈表。
雙鏈表上的插入和刪除時間復(fù)雜度均為O (1)。

　　順序表和鏈表的比較：·基于空間： ·順序表的存儲空間是靜態(tài)分配，存儲密度為1；適于線性表事先確定其大小時采用。
·鏈表的存儲空間是動態(tài)分配，存儲密度＜1；適于線性表長度變化大時采用。
·基于時間： ·順序表是隨機(jī)存儲結(jié)構(gòu)，當(dāng)線性表的操作主要是查找時，宜采用。
·以插入和刪除操作為主的線性表宜采用鏈表做存儲結(jié)構(gòu)。
·若插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。

聲明：

（一）由于考試政策等各方面情況的不斷調(diào)整與變化，本網(wǎng)站所提供的考試信息僅供參考，請以權(quán)威部門公布的正式信息為準(zhǔn)。

（二）本網(wǎng)站在文章內(nèi)容來源出處標(biāo)注為其他平臺的稿件均為轉(zhuǎn)載稿，免費(fèi)轉(zhuǎn)載出于非商業(yè)性學(xué)習(xí)目的，版權(quán)歸原作者所有。如您對內(nèi)容、版權(quán)等問題存在異議請與本站聯(lián)系，我們會及時進(jìn)行處理解決。