資源簡介

(共15張PPT)
初識鏈表
冊 別：選擇性必修1
學 科：高中信息技術（浙教版）
“老鷹抓小雞”游戲：“小雞”隊伍中，后面的人拉住前面人的衣服，形成一條鏈。把每個人想象成一個點，如何存儲數據？當有人進隊伍，或者有人退出時，數據中這些點的前后關系如何表示？
A
B
C
D
E
F
G
H
I
A
B
C
D
F
G
H
I
A
B
C
D
F
G
J
H
I
鏈表的概念
鏈表是將需要處理的數據對象以節點的形式，通過指針串聯在一起的一種數據結構。鏈表中每個節點一般由“數據區域”和“指針區域”兩部分構成。數據區域用于保存實際需要處理的數據元素，指針區域用來保存該節點相鄰節點的存儲地址，并通過該地址指針來實現從當前節點按順序走到其相鄰的節點。
A
B
C
D
E
F
G
H
I
列表索引 數據區域 指針區域
0 A 1
1 B 2
2 C 3
3 D 4
4 E 5
5 F 6
6 G 7
7 H 8
8 I -1
列表a,頭指針head=0
A
B
C
D
E
F
G
H
I
列表索引 數據區域 指針區域
0 A 1
1 B 2
2 C 3
3 D 4
4 E 5
5 F 6
6 G 7
7 H 8
8 I -1
列表a,頭指針head=0
A 1
a[0]
B 2
a[1]
head=0
C 3
a[2]
A
B
C
D
E
F
G
H
I
列表索引 數據區域 指針區域
0 A 1
1 B 2
2 C 3
3 D 4
4 E 5
5 F 6
6 G 7
7 H 8
8 I -1
A
B
C
D
F
G
H
I
列表索引 數據區域 指針區域
0 A 1
1 B 2
2 C 3
3 D 5
4 E 5
5 F 6
6 G 7
7 H 8
8 I -1
頭指針head=0
刪除元素字母“E”
A
B
C
D
F
G
H
I
A
B
C
D
F
G
J
H
I
列表索引 數據區域 指針區域
0 A 1
1 B 2
2 C 3
3 D 5
4 E 5
5 F 6
6 G 9
7 H 8
8 I -1
9 J 7
列表索引 數據區域 指針區域
0 A 1
1 B 2
2 C 3
3 D 5
4 E 5
5 F 6
6 G 7
7 H 8
8 I -1
頭指針head=0
在“G”后面插入元素字母“J”
鏈表的特性
1.同一鏈表中每個節點的結構均相同
2.每個鏈表必定有一個頭指針，對實現對鏈表的引用和邊界處理
3.鏈表占用的空間不固定
鏈表與數組
比較項目 數組 鏈表
邏輯結構 數據相鄰的元素存儲在地址連續的單元中；數據元素之間的鄰接關系由存儲單元的鄰接關系來確定。 把數據元素放在任意的存儲單元中（可連續，可不連續），用指針來反映數元素之間的相鄰關系統。
元素的訪問 可以隨機訪問，直接提取 要從頭指針開始查找
元素的插入與刪除 移動量較大，由元素的位置決定 任何位置上的刪除，只需修改指針值，不需要移動
1.鏈表的創建
A
B
C
D
E
F
G
H
I
列表索引 數據區域 指針區域
0 A 1
1 B 2
2 C 3
3 D 4
4 E 5
5 F 6
6 G 7
7 H 8
8 I -1
列表a,頭指針head=0
head=0
a=[]
n=int(input("請輸入人數："))
for i in range(n-1):
a.append([chr(65+i),i+1])
a.append([chr(65+n-1),-1])
鏈表的基本操作
2.鏈表的訪問
A
B
C
D
E
F
G
H
I
列表索引 數據區域 指針區域
0 A 1
1 B 2
2 C 3
3 D 4
4 E 5
5 F 6
6 G 7
7 H 8
8 I -1
列表a,頭指針head=0
head=0
a=[]
n=int(input("請輸入人數："))
for i in range(n-1):
a.append([chr(65+i),i+1])
a.append(['I',-1])
k=head
while(a[k][0]!='E'):
k=a[k][1]
print(k)
輸出字母“E”在隊伍中的位置
鏈表的基本操作
鏈表的基本操作
3.鏈表元素的刪除
head=0
a=[]
n=int(input("請輸入人數："))
for i in range(n-1):
a.append([chr(65+i),i+1])
a.append(['I',-1])
k=head
prev=0
while(a[k][0]!='E'):
prev=k
k=a[k][1]
a[prev][1]=a[k][1]
print(a)
隊伍中刪除字母“E”
A
B
C
D
F
G
H
I
列表索引 數據區域 指針區域
0 A 1
1 B 2
2 C 3
3 D 5
4 E 5
5 F 6
6 G 7
7 H 8
8 I -1
鏈表的基本操作
4.鏈表元素的插入
head=0
a=[]
n=int(input("請輸入人數："))
for i in range(n-1):
a.append([chr(65+i),i+1])
a.append(['I',-1])
#刪除字母“E”（此處省略）
#在“G”后面插入“J”
alen=len(a)
a.append(["J",alen])
k=head
while(a[k][0]!='G'):
k=a[k][1]
a[alen][1]=a[k][1]
a[k][1]=alen
print(a)
在“G”后面插入元素“J”
A
B
C
D
F
G
J
H
I
列表索引 數據區域 指針區域
0 A 1
1 B 2
2 C 3
3 D 5
4 E 5
5 F 6
6 G 9
7 H 8
8 I -1
9 J 7
鏈表的基本操作
2.鏈表的特性
3.鏈表與數組：相同點與不同點
4.鏈表的操作：新建鏈表，訪問鏈表，刪除節點，插入節點
1.鏈表的概念
（圖片來源于網絡，如有侵權請聯系刪除）
同學們，再見

展開更多......

收起↑