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