资源简介

(共33张PPT)
链 表
1、链表是为了解决什么问题而发明的
为了解决动态数量的数据存储
2、有没有更优方案
1
2
1、链表是为了解决什么问题而发明的
为了解决动态数量的数据存储
2、有没有更优方案
概念
节点
a
2
c
-1
b
1
head=0
头指针
p=head 指针
p=a[p][1] 后继指针
链表概念
链表是指将需要处理的数据对象以节点的形式，
通过指针串联在一起的一种数据结构。
空间 时间
链表
数组
如何创建列表
a=[ ] #创建空列表
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]
链表的访问（全部元素的遍历）
输出结果：
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]
（遍历）
输出结果：
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] ]
在头结点插入一个大写字母A
b= ["A", 5]
a.append(b)
len（a）
5是怎么来的？
代码实现
总结反思
链表的访问（全部元素的遍历）
链表
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])
输出结果：
a->b->c->d->e
单向链表节点的插入
链表节点的插入指的是根据新输入的实际数据形成节点，然后修改
新节点与其前驱节点的指针，将新节点插入到链表的正确位置。
①从头部插入新节点
next
data1
next
data2
next
data3
-1
head
单向链表从头部插入新节点
new data
next
data1
next
data3
data2
next
-1
head
代码实现
a=[["data1",1],["data2",2],["data3",-1]]
head=0
a.append(["new_data",head])
head=len(a)-1
从中间或者尾部插入新节点该怎么实现呢？
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个节点，即data3节点后插入新节点
7
8
②从中间插入新节点
a=[["data1",1],["data2",2],["data3",-1]]
head=0
p=0
a.append(["new_data",a[p][1]])
a[p][1]=len(a)-1
③从尾部插入新节点
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
单向链表节点的删除
删除单向链表的节点有三种情形：删除头节点、删除中间节点和删除尾节点。
data1
next
data2
next
data3
-1
head
data1
next
data2
next
head
data3
-1
单向链表删除头节点
代码实现
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
×
>
单向链表删除中间节点
代码实现
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
×
单向链表删除尾部节点
代码实现
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
链表节点的删除，并没有将元素从列表中删除，
而仅仅是修改了节点指针域的值，通过将被删除
节点的前驱节点和其后继节点直接相连的方式实现。
尾节点可以直接删除，若删除了头节点，则需要修
改头指针。
删除节点小结：
练一练
1.使用python 的二维列表来模拟单向链表，如下代码创建了
一个拥有4个节点的链表a：
a=[[“hello”,1],[“china”,3],[“Olympics”,-1],
[“winter”,2]]
head=0
①a[1][1]的值为：
A.1 B.2 C.0 D.3
②依次输出各节点数据域的值，则输出内容为________________
__________________
D
hello
china
winter
Olympics
2.单向链表中插入新节点的过程如图所示。使用python的
二维列表来模拟单向链表，已知插入节点前列表a=[[“红”,1]
,[“橙”,2],[“绿”,3],[“青”,-1]]，则在删除节点“橙”之
后，列表a的值为
[[“红”,1],[“绿”,3],[“青”,-1]]
[[“红”,1],[“绿”,2],[“青”,-1]]
[[“红”,1],[“橙”,2],[“绿”,3],[“青”,-1]]
[[“红”,2],[“橙”,2],[“绿”,3],[“青”,-1]]
D
3.在下列列表中将新节点插入到data2和data3中间，则下列步骤
不需要的是：
data1
next
data2
next
data3
next
data4
next
new data
next
A.断开data2与data3的连接
B.断开data3与data4的连接
C.使new data的指针指向data3
D.使data2的指针指向new data
B
4.有如下python程序段，表示一个链表及操作：
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)
程序执行后，输出的结果为：
A.[7,2,9,6,5,5] B.[5,9,7,2,6] C.[7,2,9,6,5] D.[2,9,6]
C

展开更多......

收起↑