以下自考復習資料均由浙江自考網整理并發(fā)布，考生想要了解更多關于浙江自考報名、考試、成績查詢、畢業(yè)、歷年真題、常見問答等相關信息請關注浙江自考網，獲取浙江自考更多信息。
線性表是由n≥0個數據元素組成的有限序列。n=0是空表；非空表，只能有一個開始結點，有且只能有一個終端結點。
線性表上定義的基本運算：·構造空表：Initlist(L)
·求表長：Listlength(L)
·取結點：GetNode(L,i)
·查找：LocateNode(L,x)·插入：InsertList(L,x,i)
·刪除：Delete(L,i)
順序表是按線性表的邏輯結構次序依次存放在一組地址連續(xù)的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結構中各結點相鄰關系是一致的。地址計算：LOCa(i)=LOCa(1)+(i-1)*d；（首地址為1）
在順序表中實現的基本運算： ·插入：平均移動結點次數為n/2；平均時間復雜度均為O(n)。
·刪除：平均移動結點次數為（n-1）/2；平均時間復雜度均為O(n)。
線性表的鏈式存儲結構中結點的邏輯次序和物理次序不一定相同，為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還存儲了其后繼結點的地址信息(即指針或鏈)。這兩部分信息組成鏈表中的結點結構。 一個單鏈表由頭指針的名字來命名。
單鏈表運算：·建立單鏈表·頭插法：s->next=head；head=s；生成的順序與輸入順序相反。平均時間復雜度均為O(n)。
·尾插法：head=rear=null；if(head=null) head=s;else r->next=s;r=s; 平均時間復雜度均為O(n)
·加頭結點的算法：對開始結點的操作無需特殊處理，統(tǒng)一了空表和非空表。
·查找·按序號：與查找位置有關，平均時間復雜度均為O(n)。
·按值：與輸入實例有關，平均時間復雜度均為O(n)。
·插入運算：p=GetNode(L,i-1)；s->next=p->next；p->next=s；平均時間復雜度均為O(n)
·刪除運算：p=GetNode(L,i-1)；r=p->next；p->next=r->next；free(r)；平均時間復雜度均為O(n)
單循環(huán)鏈表是一種首尾相接的單鏈表，終端結點的指針域指向開始結點或頭結點。鏈表終止條件是以指針等于頭指針或尾指針。采用單循環(huán)鏈表在實用中多采用尾指針表示單循環(huán)鏈表。優(yōu)點是查找頭指針和尾指針的時間都是O(1)，不用遍歷整個鏈表。
雙鏈表就是雙向鏈表，就是在單鏈表的每個結點里再增加一個指向其直接前趨的指針域prior,形成兩條不同方向的鏈。由頭指針head惟一確定。
雙鏈表也可以頭尾相鏈接構成雙(向)循環(huán)鏈表。
雙鏈表上的插入和刪除時間復雜度均為O (1)。
順序表和鏈表的比較：·基于空間： ·順序表的存儲空間是靜態(tài)分配，存儲密度為1；適于線性表事先確定其大小時采用。
·鏈表的存儲空間是動態(tài)分配，存儲密度＜1；適于線性表長度變化大時采用。
·基于時間： ·順序表是隨機存儲結構，當線性表的操作主要是查找時，宜采用。
·以插入和刪除操作為主的線性表宜采用鏈表做存儲結構。
·若插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。
聲明：
（一）由于考試政策等各方面情況的不斷調整與變化，本網站所提供的考試信息僅供參考，請以權威部門公布的正式信息為準。
（二）本網站在文章內容來源出處標注為其他平臺的稿件均為轉載稿，免費轉載出于非商業(yè)性學習目的，版權歸原作者所有。如您對內容、版權等問題存在異議請與本站聯系，我們會及時進行處理解決。
報名提醒 
