2023計算機考研初試在即，在最后階段建議各位同學將知識點再系統(tǒng)復習一遍，以免有所遺漏！2022計算機考研數(shù)據(jù)結構第二單元知識點包含順序表、單向鏈表、單向循環(huán)鏈表、雙向循環(huán)鏈表。高頓考研為大家整理了2022計算機考研數(shù)據(jù)結構第二單元知識點的詳細內容，供大家參考復習！
順序表：順序存儲表示的線性表稱為順序表
地址計算公式：loc(ai)=loc(a0)+i*k
只要給定loc(a0)和k，就可以確定線性表中任意一個元素的存儲地址。
順序表是一種隨機存取結構。
相關運算：
Find(i,x):查找下標為i的元素a<i>。在x中返回表中下標為i的元素a<i>(即表中第i+1個元素)。如果不存在，則返回false，否則返回true。
Insert(i,x)：在表中下標為i的元素ai后插入x。若i=-1，則將新元素x插在最前面。若插入成功，返回true。
Delete(i)：刪除元素a<i>。
優(yōu)點：隨機存取;存儲空間利用率高。
缺點：插入、刪除效率低;必須按事先估計的最大元素個數(shù)分配連續(xù)的存儲空間，難以臨時擴大。
單向鏈表
·表頭指針first是指向鏈表的頭結點的指針
相關運算：
Find(i,x):必須從表頭指針開始沿鏈逐個計數(shù)查找，稱為順序查找。搜索運算的平均、最壞的漸近時間復雜度都是O(n)。
Insert(i,x)：生成數(shù)據(jù)域為x的新結點，q指向新結點;從first開始找第i+1個結點，p指向該結點;將q插入p之后，表長加1。
·注意區(qū)分插在頭結點和一般節(jié)點的情況
Delete(i)：從first開始找第i+1個結點，p指向該結點，q指向p之前驅結點;從單鏈表中刪除p;放p之空間(delete p);表長減1。
優(yōu)點:單鏈表插入和刪除只需修改一兩個指針，無需移動元素?？梢詣討B(tài)分配結點空間，線性表的長度只受內存大小限制。
缺點:查找運算費時，只能順序查找，不能隨機查找。
帶表頭結點的單向鏈表
注意區(qū)分“表頭結點”和“頭結點”。
頭結點：線性表中下標為0的元素、第1個元素;
表頭結點：為簡化算法而附加的結點，不是線性表中的元素。
·在算法中無需將頭結點和一般節(jié)點的情況分開討論。
單向循環(huán)鏈表
循環(huán)鏈表是另一種形式的鏈式存儲結構。它的特點是表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環(huán)。
雙向循環(huán)鏈表
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。一般我們都構造雙向循環(huán)鏈表。