課件線性表的鏈式存儲_第1頁
課件線性表的鏈式存儲_第2頁
課件線性表的鏈式存儲_第3頁
課件線性表的鏈式存儲_第4頁
全文預覽已結(jié)束

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

單鏈表

1

2

3

4

5

6

7

datanext

邏輯上相鄰的兩個元素在物理位置上不相鄰單鏈表結(jié)點的定義：

typedefstructLNode{ //單鏈表結(jié)點類型

ElemTypedata; //數(shù)據(jù)域

structLNode*next; //指針域

}LNode,*LinkList;

單鏈表

L

a1

a2

a3

annull

頭指針

頭指針：鏈表中第一個結(jié)點的

頭結(jié)點：在單鏈表第一個結(jié)點之前附加的一個結(jié)點，為了操作上的方便。

位置，用來標識單鏈表。

若鏈表有頭結(jié)點，則頭指針

空，頭指針是鏈表的必須元素，他標識一個鏈表。

頭結(jié)點是為了操作的方便而設立的，其數(shù)據(jù)域一般為空，或者存放鏈表的長度。有頭結(jié)點后，對在第一結(jié)點前插入和刪除第一結(jié)點的操作就統(tǒng)一了，不需要頻繁重置頭指針。但頭結(jié)點不是必須的。

指向頭結(jié)點，不論鏈表是否為空，頭指針均不為

優(yōu)缺點

優(yōu)點

缺點

插入和刪除操作不需要移動元素，只需要修改指針。

不需要大量的連續(xù)

空間。

單鏈表附加指針域，也存在浪費

查找操作時需要從表頭開始遍歷，依次查找，不能隨機存取。

空間的缺點。

插入操作

a1

p

q

p

q

（b）中間插入元素

ai-1

X

X

（a）表頭插入元素

ai

創(chuàng)建新結(jié)點代碼：q=(LNode*)malloc(sizeof(LNode))q->data=x;

(a)(b)操作的代碼：q->next=p->next;p->next=q;

p

an^

(c)操作的代碼：

q

>next=q;

>next=NULL;

//請分別用頭插法和法創(chuàng)建一個單鏈表

（c）表 入元素

刪除操作

a1

a2

p

q

（a）表頭刪除元素

ai-1

ai

ai+1

p

q

（b）中間刪除元素

(a)(b)(c)操作的代碼：

p=Geem(L,i-1);//查找刪除位置的前驅(qū)節(jié)點

q=p->next;

an^

X

^

p

q

p->next=q->next;(q);

（c）表尾刪除元素

查找操作

按序號查找結(jié)點值的算法如下：

LNode*p=L->next;

intj=1;while(p&&j<i){

p=p->next;j++;

}

returnp;

p

a2

a1

ai-1

a3

an

查找操作

按值查找結(jié)點的算法如下：

LNode*p=L->next;while(p!=NULL&&

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論