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

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

單鏈表

1

2

3

4

5

6

7

datanext

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

typedefstructLNode{ //單鏈表結點類型

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

structLNode*next; //指針域

}LNode,*LinkList;

單鏈表

L

a1

a2

a3

annull

頭指針

頭指針：鏈表中第一個結點的

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

位置，用來標識單鏈表。

若鏈表有頭結點，則頭指針

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

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

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

優(yōu)缺點

優(yōu)點

缺點

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

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

空間。

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

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

空間的缺點。

插入操作

a1

p

q

p

q

（b）中間插入元素

ai-1

X

X

（a）表頭插入元素

ai

創(chuàng)建新結點代碼：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);//查找刪除位置的前驅節(jié)點

q=p->next;

an^

X

^

p

q

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

（c）表尾刪除元素

查找操作

按序號查找結點值的算法如下：

LNode*p=L->next;

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

p=p->next;j++;

}

returnp;

p

a2

a1

ai-1

a3

an

查找操作

按值查找結點的算法如下：

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

溫馨提示

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

評論

0/150

提交評論