一:概念

數(shù)據(jù)元素的有限序列.
它需要是序列,有列且有序,第一個(gè)元素沒有前驅(qū),最后一個(gè)元素沒有后繼,除此之外每個(gè)元素都只有一個(gè)前驅(qū)一個(gè)后繼.

線性表

線性表

線性表的抽象定義和基本操作

線性表的抽象定義和基本操作

對(duì)于線性表,復(fù)雜的問題也都是用上面這些基本操作組合來解決的,比如去重合并兩個(gè)線性表A和B,獲得B的長度,遍歷,獲取每一個(gè)元素,然后在A中對(duì)比,如果沒有則插入到A的最后.

二:存儲(chǔ)結(jié)構(gòu)

1.順序存儲(chǔ)
線性表的順序存儲(chǔ),前面提到過,就是申請(qǐng)一段地址連續(xù)的內(nèi)存空間,也就是一個(gè)數(shù)組,需要預(yù)定好長度,而真實(shí)的數(shù)據(jù)長度,或者說線性表長度,只能小于等于數(shù)組長度.

• 查找
  順序存儲(chǔ)一開始就要申請(qǐng)一段連續(xù)內(nèi)存空間,而且長度是預(yù)定的,那么顯然每個(gè)元素需要的空間是一樣的,比如整形數(shù)組,不管是多大的數(shù)字,每個(gè)元素占的內(nèi)存空間是一樣大的.
  因此,在獲取某個(gè)位置的元素時(shí),只要根據(jù)下標(biāo)計(jì)算內(nèi)存地址就行了,它是時(shí)間復(fù)雜度是O(1).

• 插入
  順序存儲(chǔ)結(jié)構(gòu),如果要再i處插入一個(gè)新元素, 首先要判斷是否會(huì)溢出,之后要把i后面的元素都后移一位.時(shí)間復(fù)雜度是O(n).

• 刪除
  同樣的,刪除i處的元素,后面的也都要向前移動(dòng),時(shí)間復(fù)雜度是O(n).

  
  
  image.png

2.鏈?zhǔn)酱鎯?chǔ)
鏈?zhǔn)酱鎯?chǔ)把數(shù)據(jù)和指針包裝在一起,叫做節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)分為兩個(gè)部分,一個(gè)是數(shù)據(jù)域,一個(gè)是指針域,指針域存的是下個(gè)節(jié)點(diǎn)的地址;
對(duì)于頭部的節(jié)點(diǎn),數(shù)據(jù)域可能是空的,也可能會(huì)存儲(chǔ)一些信息,比如長度,命名,或者其他業(yè)務(wù)場(chǎng)景實(shí)際需要的信息,而尾部的節(jié)點(diǎn)是真實(shí)的數(shù)據(jù),指針域?yàn)榭誑ULL.
因此鏈?zhǔn)酱鎯?chǔ)的每個(gè)元素不相互挨著,由鏈表來映射數(shù)據(jù)結(jié)構(gòu),也就是線性表的特征.
這種每個(gè)節(jié)點(diǎn)存著下一個(gè)節(jié)點(diǎn)地址的鏈表叫做單鏈表.

image.png

• 頭結(jié)點(diǎn)
  并非是第一個(gè)節(jié)點(diǎn),是一個(gè)擴(kuò)展節(jié)點(diǎn),放在第一節(jié)點(diǎn)之前,存儲(chǔ)一些擴(kuò)展信息,有了頭結(jié)點(diǎn),鏈表真正的數(shù)據(jù)節(jié)點(diǎn)就全部統(tǒng)一了,不必考慮第一個(gè)節(jié)點(diǎn)前面沒東西.另外頭結(jié)點(diǎn)是可選的.

• 頭指針
  指向鏈表第一個(gè)節(jié)點(diǎn)的指針,如果有頭結(jié)點(diǎn),那么指向頭結(jié)點(diǎn),頭指針創(chuàng)建鏈表就存在,即使鏈表是空的.

  
  
  image.png
  
  
  定義單鏈表

• 查找
  單鏈表元素不挨著,查詢需要一個(gè)個(gè)往下訪問,時(shí)間復(fù)雜度是O(n)

• 插入
  當(dāng)向i插入元素時(shí),需要修改i-1的的指針和i的指針,并且這里還有個(gè)順序問題.

  
  
  image.png
  
  

  如果先把p指向s,那么p->next直接就丟失了,所以應(yīng)該先把s指向p->next,再把p指向s.

  
  
  插入節(jié)點(diǎn)的實(shí)現(xiàn)

• 刪除
  刪除單鏈表節(jié)點(diǎn)就是跳過被刪除的節(jié)點(diǎn),直接指向后面的節(jié)點(diǎn).

  
  
  image.png
  
  
  刪除節(jié)點(diǎn)的實(shí)現(xiàn)

顯然插入和刪除本身是O(1)的,耗時(shí)的還是查找,由于地址不連續(xù),不能根據(jù)下標(biāo)獲取地址,因此不管是查找具體元素還是訪問指定下標(biāo)的元素,都得一個(gè)個(gè)查找,為O(n).

對(duì)比

三:創(chuàng)建和刪除單鏈表

1.創(chuàng)建單鏈表

頭插法

頭插法

尾插發(fā)-

尾插發(fā)(接上圖)

尾插發(fā)的區(qū)別在于創(chuàng)建一個(gè)標(biāo)記節(jié)點(diǎn)r指向頭結(jié)點(diǎn);
然后創(chuàng)建一個(gè)節(jié)點(diǎn)P,將r的next指向P,此時(shí)r就是頭結(jié)點(diǎn),r->next是P;
接著把r重新指向P,重新標(biāo)記P為最后一個(gè)元素,以此類推.

r本來是ai-1,之后換成ai

2.刪除單鏈表

image.png

四:靜態(tài)鏈表

1.靜態(tài)鏈表
靜態(tài)鏈表是用數(shù)組來實(shí)現(xiàn)的,在沒有指針操作的開發(fā)環(huán)境中,會(huì)用到這種方式來實(shí)現(xiàn)鏈表.

image.png

image.png

2.靜態(tài)鏈表插入
從上面說的cur來看,插入操作就很容易想象了,就和動(dòng)態(tài)鏈表一樣,修改關(guān)鍵的幾個(gè)節(jié)點(diǎn)的cur就可以了,假設(shè)要在2和3直接插入一個(gè)元素;
首先把元素放在第一個(gè)空位上,下標(biāo)為x,也就是數(shù)組第一個(gè)元素的cur(前面說到存的是個(gè)下標(biāo)),并且設(shè)置cur為元素3的cur;
然后修改元素2的cur為x;
和動(dòng)態(tài)鏈表一樣的兩步操作.

過程表示

返回第一個(gè)空閑下標(biāo)

完成插入

3.靜態(tài)鏈表刪除
刪除元素要分兩步;
先前說到,末尾元素是頭結(jié)點(diǎn)的作用,它的sur是第一個(gè)元素的下標(biāo),如果刪除第一個(gè),要修改頭結(jié)點(diǎn)的sur,然后再釋放節(jié)點(diǎn);
第二步,被修改元素的cur修改為第一個(gè)元素的cur,第一個(gè)元素的cur修改為被刪除元素的下標(biāo);這樣第一個(gè)空閑被修改成了被刪除元素,被刪除元素的cur是原先的第一個(gè)空閑,現(xiàn)在是第二個(gè)了;

過程表示

刪除第i個(gè)元素

接上圖

優(yōu)缺點(diǎn)

五:循環(huán)鏈表

當(dāng)單鏈表訪問到末尾節(jié)點(diǎn)的時(shí)候,無法逆向,也無法回到起點(diǎn),將末尾節(jié)點(diǎn)的指針從NULL改成指向頭結(jié)點(diǎn),于是形成了循環(huán)鏈表.

循環(huán)鏈表

單鏈表的循環(huán)訪問,當(dāng)節(jié)點(diǎn)的指針為NULL時(shí),遍歷結(jié)束,而循環(huán)列表是當(dāng)節(jié)點(diǎn)指針指向頭結(jié)點(diǎn)時(shí),遍歷結(jié)束.

尾指針

不管是單鏈表還是循環(huán)鏈表,訪問第一個(gè)節(jié)點(diǎn)是O(1),但是訪問最后一節(jié)點(diǎn)都是O(n),因?yàn)榭傄獜念^開始往下找,那么能不能解決這個(gè)問題呢:
把頭指針改成尾指針就可以了;
用尾指針rear表示一個(gè)鏈表時(shí),訪問第一個(gè)節(jié)點(diǎn),是rear->next(到這里是頭結(jié)點(diǎn))->next,訪問最后一個(gè)節(jié)點(diǎn)就是rear.這樣就都是O(1).

六:雙向鏈表

雙向鏈表就是每個(gè)節(jié)點(diǎn)有兩個(gè)指針,一個(gè)指向前驅(qū)節(jié)點(diǎn),一個(gè)指向后繼節(jié)點(diǎn).

雙向鏈表

雙向循環(huán)空鏈表

雙向循環(huán)非空鏈表

插入

雙向鏈表插入時(shí),首先設(shè)置新元素的prior和next,然后修改前驅(qū)元素,然后修改后繼元素的prior,最后修改前驅(qū)元素的next.

刪除

刪除節(jié)點(diǎn)時(shí),把前驅(qū)節(jié)點(diǎn)的next修改成后繼節(jié)點(diǎn)的prior,然后把后繼節(jié)點(diǎn)的prior修改成前驅(qū)節(jié)點(diǎn)的next.

線性表