資源簡(jiǎn)介

(共33張PPT)
鏈 表
1、鏈表是為了解決什么問(wèn)題而發(fā)明的
為了解決動(dòng)態(tài)數(shù)量的數(shù)據(jù)存儲(chǔ)
2、有沒(méi)有更優(yōu)方案
1
2
1、鏈表是為了解決什么問(wèn)題而發(fā)明的
為了解決動(dòng)態(tài)數(shù)量的數(shù)據(jù)存儲(chǔ)
2、有沒(méi)有更優(yōu)方案
概念
節(jié)點(diǎn)
a
2
c
-1
b
1
head=0
頭指針
p=head 指針
p=a[p][1] 后繼指針
鏈表概念
鏈表是指將需要處理的數(shù)據(jù)對(duì)象以節(jié)點(diǎn)的形式，
通過(guò)指針串聯(lián)在一起的一種數(shù)據(jù)結(jié)構(gòu)。
空間 時(shí)間
鏈表
數(shù)組
如何創(chuàng)建列表
a=[ ] #創(chuàng)建空列表
head=-1
a.append([“a”,1]) #添加元素
a = [ ["c", 3], ["e", -1], ["a", 4], ["d", 1], ["b", 0] ]
p = head
while p != -1:
print(a[p][0], end="->")
p = a[p][1]
鏈表的訪問(wèn)（全部元素的遍歷）
輸出結(jié)果：
a->b->c->d->e->
？
head=2
a = [ ["c", 3], ["e", -1], ["a", 4], ["d", 1], ["b", 0] ]
p = head
while a[p][1] != -1:
print(a[p][0], end="->")
p = a[p][1]
（遍歷）
輸出結(jié)果：
a->b->c->d->e
？
head=2
print(a[p][0])
a[p][1] ! = -1:
a = [ ["c", 3], ["e", -1], ["a", 4], ["d", 1], ["b", 0] ]
在頭結(jié)點(diǎn)插入一個(gè)大寫(xiě)字母A
b= ["A", 5]
a.append(b)
len（a）
5是怎么來(lái)的？
代碼實(shí)現(xiàn)
總結(jié)反思
鏈表的訪問(wèn)（全部元素的遍歷）
鏈表
da = [["c", 3], ["e", -1], ["a", 4], ["d", 1], ["b", 0]]
head = 2
p = head
while da[p][1] != -1:
print(da[p][0], end="->")
p = da[p][1]
print(da[p][0])
輸出結(jié)果：
a->b->c->d->e
單向鏈表節(jié)點(diǎn)的插入
鏈表節(jié)點(diǎn)的插入指的是根據(jù)新輸入的實(shí)際數(shù)據(jù)形成節(jié)點(diǎn)，然后修改
新節(jié)點(diǎn)與其前驅(qū)節(jié)點(diǎn)的指針，將新節(jié)點(diǎn)插入到鏈表的正確位置。
①?gòu)念^部插入新節(jié)點(diǎn)
next
data1
next
data2
next
data3
-1
head
單向鏈表從頭部插入新節(jié)點(diǎn)
new data
next
data1
next
data3
data2
next
-1
head
代碼實(shí)現(xiàn)
a=[["data1",1],["data2",2],["data3",-1]]
head=0
a.append(["new_data",head])
head=len(a)-1
從中間或者尾部插入新節(jié)點(diǎn)該怎么實(shí)現(xiàn)呢？
0 data8 -1
1 data3 7
2 data1 6
3 data6 5
4 data5 3
5 data7 0
6 data2 1
7 data4 4
head
列表名data
列表索引
0 data8 -1
1 data3 7
2 data1 6
3 data6 5
4 data5 3
5 data7 0
6 data2 1
7 data4 4
0 data8 -1
1 data3
2 data1 6
3 data6 5
4 data5 3
5 data7 0
6 data2 1
7 data4 4
8 new
head
head
列表名data
列表索引
列表名data
列表索引
在第3個(gè)節(jié)點(diǎn)，即data3節(jié)點(diǎn)后插入新節(jié)點(diǎn)
7
8
②從中間插入新節(jié)點(diǎn)
a=[["data1",1],["data2",2],["data3",-1]]
head=0
p=0
a.append(["new_data",a[p][1]])
a[p][1]=len(a)-1
③從尾部插入新節(jié)點(diǎn)
a=[["data1",1],["data2",2],["data3",-1]]
head=0
p=head
While a[p][1]!=-1:
p=a[p][1]
a.append(["new_data",-1)
a[p][1]=
len(a)-1
單向鏈表節(jié)點(diǎn)的刪除
刪除單向鏈表的節(jié)點(diǎn)有三種情形：刪除頭節(jié)點(diǎn)、刪除中間節(jié)點(diǎn)和刪除尾節(jié)點(diǎn)。
data1
next
data2
next
data3
-1
head
data1
next
data2
next
head
data3
-1
單向鏈表刪除頭節(jié)點(diǎn)
代碼實(shí)現(xiàn)
a=[["data1",1],["data2",2],["data3",-1]]
head=0
head=a[head][1]
data1
next
data2
next
data3
-1
head
data1
next
data2
next
data3
-1
head
×
×
>
data1
next
data2
next
data3
-1
head
data1
next
next
head
×
>
單向鏈表刪除中間節(jié)點(diǎn)
代碼實(shí)現(xiàn)
a=[["data1",1],["data2",2],["data3",-1]]
head=0
pre=0
p=a[pre][1]
a[pre][1]=a[p][1]
data1
next
data2
next
data3
-1
head
head
data1
next
data2
next
data3
-1
×
單向鏈表刪除尾部節(jié)點(diǎn)
代碼實(shí)現(xiàn)
a=[["data1",1],["data2",2],["data3",-1]]
head=0
pre=head
while a[a[pre][1]][1]!=-1:
pre=a[pre][1]
a[pre][1]=-1
鏈表節(jié)點(diǎn)的刪除，并沒(méi)有將元素從列表中刪除，
而僅僅是修改了節(jié)點(diǎn)指針域的值，通過(guò)將被刪除
節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)和其后繼節(jié)點(diǎn)直接相連的方式實(shí)現(xiàn)。
尾節(jié)點(diǎn)可以直接刪除，若刪除了頭節(jié)點(diǎn)，則需要修
改頭指針。
刪除節(jié)點(diǎn)小結(jié)：
練一練
1.使用python 的二維列表來(lái)模擬單向鏈表，如下代碼創(chuàng)建了
一個(gè)擁有4個(gè)節(jié)點(diǎn)的鏈表a：
a=[[“hello”,1],[“china”,3],[“Olympics”,-1],
[“winter”,2]]
head=0
①a[1][1]的值為：
A.1 B.2 C.0 D.3
②依次輸出各節(jié)點(diǎn)數(shù)據(jù)域的值，則輸出內(nèi)容為_(kāi)_______________
__________________
D
hello
china
winter
Olympics
2.單向鏈表中插入新節(jié)點(diǎn)的過(guò)程如圖所示。使用python的
二維列表來(lái)模擬單向鏈表，已知插入節(jié)點(diǎn)前列表a=[[“紅”,1]
,[“橙”,2],[“綠”,3],[“青”,-1]]，則在刪除節(jié)點(diǎn)“橙”之
后，列表a的值為
[[“紅”,1],[“綠”,3],[“青”,-1]]
[[“紅”,1],[“綠”,2],[“青”,-1]]
[[“紅”,1],[“橙”,2],[“綠”,3],[“青”,-1]]
[[“紅”,2],[“橙”,2],[“綠”,3],[“青”,-1]]
D
3.在下列列表中將新節(jié)點(diǎn)插入到data2和data3中間，則下列步驟
不需要的是：
data1
next
data2
next
data3
next
data4
next
new data
next
A.斷開(kāi)data2與data3的連接
B.斷開(kāi)data3與data4的連接
C.使new data的指針指向data3
D.使data2的指針指向new data
B
4.有如下python程序段，表示一個(gè)鏈表及操作：
a=[[5,-1],[9,4],[7,3],[2,1],[6,0]]
head=2
p=head
b=[ ]
While a[p][1]!=-1:
b.append(a[p][0])
p=a[p][1]
b.append(a[p][0])
print(b)
程序執(zhí)行后，輸出的結(jié)果為：
A.[7,2,9,6,5,5] B.[5,9,7,2,6] C.[7,2,9,6,5] D.[2,9,6]
C

展開(kāi)更多......

收起↑