资源简介

(共35张PPT)
2.2 链表
导入
小华规划自驾游路线，出发地为杭州，目的地为北京，在规划过程中经过了多次更改。原计划的途径地为上海、苏州、南京、济南、石家庄.第一次在南京和济南之间加入了途径地青岛，第二次取消了途径地南京.用数组来实现其更改过程。
杭州
苏州
南京
济南
石家庄
北京
青岛
数组a
0 1 2 3 4 5 6 7
a=["杭州","上海","苏州","南京","济南","石家庄","北京",""]
n=len(a)
p=4
for i in range（n-2,p-1,-1）:
_________________
____________
n+=1
print(a)
a[i+1]=a[i]
a[p]=”青岛”
第一次：
上海
导入
小华规划自驾游路线，出发地为杭州，目的地为北京，在规划过程中经过了多次更改。原计划的途径地为上海、苏州、南京、济南、石家庄.第一次在南京和济南之间加入了途径地青岛，第二次取消了途径地南京.用数组来实现其更改过程。
杭州
上海
苏州
南京
济南
石家庄
北京
青岛
第二次：
a=["杭州","上海","苏州","南京","青岛","济南","石家庄","北京"]
n=len(a)
q=3
for i in range(__________):
a[i]=a[i+1]
a.pop()
n-=1
print(a)
q,n-1
数组a
0 1 2 3 4 5 6 7
导入
小华规划自驾游路线，出发地为杭州，目的地为北京，在规划过程中经过了多次更改。第一次依次加入的途径地为上海、苏州、南京、济南、石家庄；第二次在南京和济南之间加入了途径地青岛，取消了途径地南京；用数组来实现其更改过程。
杭州
苏州
济南
石家庄
北京
青岛
数组的缺点：
插入和删除元素操作需要移动大量的元素
频繁增、删数据导致数据规模不稳，形成存储空间“碎片”
需要限定最大空间，造成资源浪费
链表适用于当数据规模不确定或初始时确定但在处理过程中由于频繁增、删数据导致数据规模不稳定的问题。
数组a
0 1 2 3 4 5 6 7
上海
链表基本概念
链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。
链表基本概念：
链表节点结构
保存数据元素
保存相邻节点的存储地址
头指针（head）作用：
一是链表的入口，只有通过头指针才能进入链表
二是为循环链表设立一个边界，便于数据处理时的边界判断和处理
吴坚
黄刚
王林
李丰
head
next
next
next
链表基本概念
根据每个节点中指针的数量分为：
单向链表：
循环链表：
第一个节点和最后一个节点使用指针链接，这样就形成了循环链表。
next
prev
data next
双向链表：
prev data next
prev
prev
next：指向其后继节点
prev：指向其前驱节点
链表基本概念
单向链表中各个节点在内存中可以随意存储，每个节点使用指针指向其后继节点的存储地址。进入链表只能通过头指针head，其他节点则需要经过所有在它之前的节点才可以访问，尾结点的指针指向为null，表示指向为空。
链表的特性
（1）同一链表中每个节点的结构均相同
数据类型相同
指针数量和功能相同
（2）每个链表必定有一个头指针，以实现对链表的引用和边界处理
链表的头指针使用变量head表示，用来进入链表。当访问链表中某一节点，
只能从头指针开始，通过指针链接依次访问，不能使用下标直接引用。
对于循环链表，一轮访问的开始和结束都可以用借助头指针指向位置来进行判断，
即边界处理。
head
（3）链表占用的空间不固定
链表的节点间是通过指针链接，相邻节点存储时不需要连续的空间。
所以链表的存储空间由节点数决定，改变节点数就能改变链表的存储空间。
链表的基本操作
Python中没有直接定义链表结构，可以使用其提供的列表来模拟实现。
实现单向链表时，列表中的每个数据项作为链表中的一个节点，包含两个数据，一个作为数据域存储具体数据，另一个作为指针域存储后继节点在列表中的指针。
用列表的索引来代替地址指针，并规定列表索引均为正索引，当某个指针区域值为-1时表示指向为空，该节点为尾节点。
b=[[165,2],[160,-1],[162,1],[172,0]]
head=3
165 2
160 -1
162 1
172 0
0
1
2
3
head→
172
165
162
160
0
1
2
3
数组存储
顺序存储
链表存储
非顺序存储
data next
头节点
尾节点
数据区域 指针区域
空链表的创建
其中head值为–1，表示头指针指向为空，该链表为空链表。
创建链表时，首先要根据问题特点规划节点的数据域和指针域，然后根据规划创建一个空表和头节点。接下来就可以根据输入的实际数据形成节点并逐步插入到已有的链表中。
item=[]
head=-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
②a[1][1]的含义是什么？
D
china后面指向的下一个节点是[“winter”,2]
链表的访问
链表只能通过头指针（head）进行访问，其他节点通过节点间的指针依次访问。如图，当想访问单向链表中data3所在的节点时，需通过头指针进入链表，再分别按照各个节点的指针指向经过data1和data2所在节点，最后通过data2所在节点的指针才能访问
data3所在的节点。
链表的插入
3 new data
data1
data2 2
data3 -1
head
在单向链表data1和data2所处节点的中间位置插入一个新节点
3
1
0
1
2
思想：当需要在链表中某个位置中插入一个新元素时，只需将元素添加在尾部，并改动指针值
data.append([newdata,0])
1.将元素添加在尾部：
列表名data
data[3][1]=data[0][1]
2.修改指针值：
data[0][1]=3
链表的插入
data[8][1]=data[1][1]
data[1][1]=8
2.修改指针值：
思想：当需要在链表中某个位置中插入一个新元素时，只需将元素添加在尾部，并改动指针值
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
8 new
0 data8 -1
1 data3 8
2 data1 6
3 data6 5
4 data5 3
5 data7 0
6 data2 1
7 data4 4
8 new 7
head
head
data.append([new,7])
1.将元素添加在尾部：
链表的插入
现有链表b=[[165,2],[160,-1],[162,1],[172,0]]，要实现分别在链表头部插入数据175，请思考插入过程，并尝试用代码实现。
165 2
160 -1
162 1
172 0
175
0
1
2
3
4
head→
在链表头部插入元素
→ → →
172 0
165 2
162 1
160 -1
175
3
head
b=[[165,2],[160,-1],[162,1],[172,0]]
head=3
_____________________#插入新节点
head=________#修改头指针
print(b)
3
b.append([175,3])
4
链表的插入
现有链表b=[[165,2],[160,-1],[162,1],[172,0]]，要实现分别在链表中间插入数据163，请思考插入过程，并尝试用代码实现。
165 2
160 -1
162 1
172 0
163
0
1
2
3
4
head→
在链表中间插入元素
→ → →
172 0
165 2
162 1
160 -1
163
2
head
b=[[165,2],[160,-1],[162,1],[172,0]]
head=3
#插入新节点
pre=head
cur=head
while cur!=-1:
if b[cur][0]>=163:
pre=cur
cur=b[cur][1]
else:
_____________________
_____________________
break
2
b.insert(4,[163,b[pre][1])
b[pre][1]=4
4
4
cur
pre
链表的插入
现有链表b=[[165,2],[160,-1],[162,1],[172,0]]，要实现分别在链表头部插入数据159，请思考插入过程，并尝试用代码实现。
165 2
160 -1
162 1
172 0
159
0
1
2
3
4
head→
在链表尾部插入元素
→ → →
172 0
165 2
162 1
160 -1
159
-1
head
b=[[165,2],[160,-1],[162,1],[172,0]]
head=3
#插入新节点
cur=head#当前访问节点的索引值
while cur!=-1:#查找尾节点
pre=cur
cur=b[cur][1]
________________________
______________________
-1
b.append([159,-1])
b[pre][1]=4
4
4
cur
pre
练习
①从头部插入
②从中间插入
③从尾部插入
a=[["t",2],["y",0],[“o",-1],["p",1]]
head=1
new_data="x"
a.append([new_data,head])
head=len(a)-1
print(head,a)
a=[["t",2],["y",0],["o",-1],["p",1]]
head=3
new_data="x"
p=0
a.append([new_data,a[p][1]])
a[p][1]=len(a)-1
print(head,a)
a=[["t",4],["y",0],["o",-1],["p",1]]
head=3
new_data="x"
p=head
while a[p][1]!=-1:
p=a[p][1]
a.append([new_data,a[p][1]])
a[p][1]=len(a)-1
print(head,a)
数据合并
（1）算法设计
①初始化两个空链表data_a和data_b，并使用head_a和head_b作为两个链表的头指针，其中data_a作为存储结果的链表。
②使用随机函数randint(start,end)模拟生成两个降序序列数据，生成新的结点在尾部插入。
数据合并
（1）算法设计
③使用变量k_a与k_b指向两个链表中未合并的数据序列中最前面（值最大）的结点，初始化k_a=head_a，k_b=head_b，由于在链表data_a中需要进行插入结点的操作，必须记录插入位置的前驱结点，使用变量q_a，初始化q_a=head。重复以下操作，直到k_a或k_b指向空（即某个链表元素全部处理完）：比较data_a[k_a][0]和data_b[k_b][0]的大小。若data_a[k_a][0]≥data_b[k_b][0]，则修改q_a与k_a相等，再将k_a指向下一个结点；否则将链表data_b中k_b指向的结点插入到链表data_a中，作为q_a指向结点的后继结点，再将k_b指向链表data_b中的下一个结点。
④若k_b未指向空，则将链表data_b剩余结点按顺序插入链表data_a的尾部。
⑤输出链表data_a中每个结点的数据区域的值。
数据合并程序实现
程序 测试结果
from random import randint data_a=[] head_a=-1 data_b=[] head_b=-1 tmp=randint(95,100) data_a.append([tmp,head_a]) head_a=0 for i in range(1,20): tmp=data_a[i-1][0]-randint(1,5) data_a.append([tmp,data_a[i-1][1]]) data_a[i-1][1]=i print(" 链表结构的原始数据序列一 ") print(data_a) 链表结构的原始数据序列一
[[99, 1], [98, 2], [94, 3], [93, 4],[91, 5], [89, 6], [85, 7], [84, 8],[79, 9], [75, 10], [72, 11], [71,12], [66, 13], [64, 14], [59, 15],[54, 16], [52, 17], [48, 18], [44,19], [43,-1]]
数据合并程序实现
程序 测试结果
tmp=randint(95,100) data_b.append([tmp,head_b]) head_b=0 for i in range(1,25): tmp=data_b[i-1][0]-randint(1,5) data_b.append([tmp,data_b[i-1][1]]) data_b[i-1][1]=i print(" 链表结构的原始数据序列二 ") print(data_b) #初始化列表索引 k_a=head_a q_a=head_a k_b=head_b 链表结构的原始数据序列二
[[98, 1], [95, 2], [93, 3], [91, 4],
[90, 5], [89, 6], [84, 7], [80, 8],
[79, 9], [75, 10], [71, 11], [69,
12], [68, 13], [63, 14], [58, 15],
[56, 16], [52, 17], [47, 18], [42,
19], [41, 20], [38, 21], [34, 22],
[32, 23], [29, 24], [24, –1]]
数据合并程序实现
程序 测试结果
while(k_a!=-1 and k_b!=-1): if data_a[k_a][0]>=data_b[k_b][0]: q_a=k_a k_a=data_a[k_a][1] else: if k_a==head_a: # 在链表 data_a 的头部插入结点 data_a.append([data_b[k_b][0],head_a]) head_a=len(data_a)-1 q_a=head_a k_b=data_b[k_b][1] else: data_a.append([data_b[k_b][0],k_a]) data_a[q_a][1]=len(data_a)-1 q_a=data_a[q_a][1] k_b=data_b[k_b][1]
99 1
98 2
94 3
93 4
91 -1
0
1
2
3
4
5
6
7
head→
98 1
95 2
93 3
90 -1
0
1
2
3
head→
数据合并程序实现
程序 测试结果
while k_b!=-1: data_a.append([data_b[k_b][0],-1]) data_a[q_a][1]=len(data_a)-1 q_a=data_a[q_a][1] k_b=data_b[k_b][1] print(" 链表结构的合并后数据序列 ") print(data_a) print(" 按链表链接顺序输出数据序列 ") tmp=head_a while data_a[tmp][1]!=-1: print(data_a[tmp][0],end=" ") tmp=data_a[tmp][1] print(data_a[tmp][0]) 链表结构的合并后数据序列
[[99,1],[98,20],[94,3],[93,22],[91,23],[89,25],[85,7],[84,26],[79,28],[75,29],[72,11],[71,30],[66, 13],[64,33],[59,34],[54,16],[52,36],[48,37],[44,19],[43,38],[98,21],[95,2],[93,4],[91,24],[90,5],[89,6],[84,27],[80,8],[79,9],[75,10],[71,31],[69,32],[68,12],[63,14],[58,35],[56,15],[52,17],[47,18],[42,39],[41,40], [38,41],[34,42],[32,43],[29, 44], [24, –1]]
按链表链接顺序输出数据序列
99 98 98 95 94 93 93 91 91 90 89 89 85 84 84 80 79 79 75 75 72 71 71 69 68 66 64 63 59 58 56 54 52 52 48 47 44 43 42 41 38 34 32 29 24
链表的删除
data1
data2 2
data3 -1
head
将单向链表data1和data3中间的节点删除掉
1
0
1
2
2
7 3
9 -1
5 0
8 1
3 2
0
1
2
3
4
head→
7 3
9 -1
5 0
8 1
3 2
0
1
2
3
4
head→
7 3
9 -1
5 0
8 1
3 2
0
1
2
3
4
head→
删除第一个节点
删除第3个节点
删除最后一个节点
链表的删除
参考链表的插入，描述出在单向链表中删除第一个节点、中间节点及尾节点的过程。
a=[[7,3],[9,-1],[5,0],[8,1],[3,2]]
head=4
wz=int(input())
k_a=head
q_a=head
c=0
while k_a!=-1:
c=c+1
if c==wz:
if q_a==head:
____________________
else:
____________________
break
else:
________________________
________________________
print(a)
k_a=head
for i in range(len(a)):
if k_a!=-1:
print(a[k_a][0])
k_a=a[k_a][1]
head=a[q_a][1]
a[q_a][1]=a[k_a][1]
q_a=k_a
k_a=a[q_a][1]
7 3
9 -1
5 0
8 1
3 2
head→
练习
1.有如下python程序段：
a=[[7,1],[8,2],[9,-1],[6,0]]
head=3
head=a[head][1]
则程序执行后，链表a有几个节点（ ）
A.1 B.2 C.3 D.4
程序实现了什么功能？
程序执行后链表a变为 ：
C
删除了头部节点[6,0]
a=[[7,1],[8,2],[9,-1],[6,0]]
练习
下列程序的运行结果为：
lista = [["c", 3], ["e", -1], ["a", 4], ["d", 1], ["b", 0]]
head = 2
p = head
while lista[p][1] != -1:
print(lista[p][0], end="->")
p = lista[p][1]
print(lista[p][0])
输出结果：
a->b->c->d->e
链表节点的访问与遍历
（1）抽象与建模
该问题中的关键数据是n个参与人员的初始编号，1至n的序列。从编号1开始计数，每过一个编号加1，当计数到m时将该编号从数据序列中移除，并从该编号的后一编号从1开始重新计数。而当计数到序列中最后一个编号，又从序列的开始编号继续计数，从而将计数序列构成一个环。重复这个过程，直到序列中只剩一个编号，该编号即为最后剩下人员的初始编号。
链表节点的访问与遍历
（2）设计数据结构与算法
该问题中数据规模在初始时可以确定（最大为n），但是在数据处理过程中需要按照规则不断地移除数据，直至只剩一个为止。也就是说，数据规模在处理过程中逐渐变小，呈现不稳定的特性，符合链表的应用。
由于最终需要输出初始编号信息，所以链表每个结点中数据区域用来保存初始编号，指针区域需要一个用来保存指向后继结点的指针。同时由于序列中最大编号报数后会从序列中最小编号继续报数，所以可以采用单向循环链表来组织数据。基于链表这种数据结构的设计，可以设计出相应的算法如下：
链表节点的访问与遍历
算法如下：
①创建一个由n个结点组成的单向循环链表，并使报数计数器i的初始化值为1，同时当前报数人的指针k指向链表中第一个结点。
②重复执行下列处理，直到链表中只剩下一个结点：随着报数的进行，不断指向下一个结点，报数计数器i也随之增加，当i增加到淘汰数m时，将对应的链表结点删除，若删除的结点为头结点，则需同时修改头指针的指向；在删除结点的同时，需要重置报数计数器i的值为1。
③将链表中唯一结点，也就是头指针指向的结点中的数据（即初始编号）输出。
链表节点的访问与遍历
程序 测试结果
llist=[] n=int(input(" 请输入参与人数（ N ） :")) m=int(input(" 请输入淘汰数（ M ） :")) for i in range(n-1): llist.append([i+1,i+1]) llist.append([n,0]) # 将尾结点的指针指向头结点，构成循环单向链表 初始化约瑟夫环
链表节点的访问与遍历
程序
head=0
long=n
k=head
i=1
while long>1:
i=i+1
if i==m:
t=llist[k][1]
llist[k][1]=llist[t][1]
if t==head:
# 删除结点为头指针指向的结点
head=llist[k][1]
i=1
long=long-1
k=llist[k][1]
print(llist[head][0])

1 1
0
2 2
1
3 3
2
4 4
3
5 5
4
6 6
5
7 7
6
8 0
7
head
课堂小结2.2链表教学设计
一、教学设计
课程标准和教学目标 链表
教材内容： 2.2链表的概念、特性、基本操作
1.3结合生活实际，理解数据结构的概念，认识数据结构在解决问题过程中的重要作用。1.4 通过案例分析，理解链表的概念，并能编程实现其相关操作。
教学目标：●通过案例分析，理解链表的概念、特性。●结合链表的具体应用，在解决问题的过程中理解链表的特性和基本操作。教学重点：链表的概念、组织结构及其特性教学难点：能理解数组、链表的区别，并能选择合理的数据结构编程实现、解决问题。 指向的核心素养： 本节主要内容为介绍链表的概念、特性及其基本操作，并在此基础上结合实例（合并数据项目的链表实现、约瑟夫问题等）学习，体验如何使用链表组织、存储数据并编程解决具体问题，核心素养主要通过以下几方面进行落实：●信息意识方面的指向:使学生能够运用生活中的实例描述数据的内涵与外延，能够将有限制条件的、复杂生活情境中的关系进行抽象，用合理的数据结构表达数据的逻辑关系。●计算思维方面的指向:使学生能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法编程实现、解决问题。
学习环境：机房，预装Python编程环境。
建议课时：1.5课时
教学活动设计 教学环节 教学过程 设计意图
情境导入1 观看“排队与插队”视频，讨“数组”存储结构的应用局限性：插入和删除元素操作需要移动大量的元素频繁增、删数据导致数据规模不稳，形成存储空间“碎片”需要限定最大空间，造成资源浪费 排队与插队的生活案例，引导学生思考“数组”数据结构在特定场景下的应用局限性，为“链表”非顺序存储结构的介绍做好铺垫。同时通过“数组”的过度有利于加深学生对“数组”存储模式和“链表”存储模式的理解。
知识讲解1 通过围绕“体育课整队”的案例展开探讨，回顾单向链表数据结构，学习链表的基本概念。 在1.2.2常见的数据结构中已经有对链表知识的介绍，本课通过“生活中的数据结构”问题探讨展开教学，既起到回顾已有知识的作用，又能自然过度到本课对链表展开深入研究。。
问题与讨论1 参考单向链表的结点结构及其指针指向，讨论并描述双向链表和循环链表的结点结构及其指针指向。 基于单向链表的学习，引导拓展到双向链表和循环链表知识，有助强化学生对链表结构的理解，培养学生知识迁移的能力。
知识讲解2 基于前面链表结构与概念的讲解，引导学生总结归纳链表的三大性质：同一链表中每个结点的结构均相同每个链表必定有一个头指针，以实现对链表的引用和边界处理链表占用的空间不固定明确告诉学生，由于Python没有指针的概念，无法直接定义链表的结构，只能通过列表来模拟，在这里我们通过列表的索引来模拟数据存放的地址。然后，围绕列表模拟来讲解链表创建、链表访问及链表结点的插入与删除方法。 学生通过前面的教学环节学习基本理解链表的结构特征与实现方式。本环节通过交流、反思的形式来进一步梳理链表的特性，既有利于进一步加深学生对链表的理解，同时，又有利于学生分析、总结、归纳能力的提升，也有利于学生与团队成员分享信息意识的形成。利用列表模拟来研究链表的特征与基本操作，既有利于培养学生编程实现的意识与能力，同时又能让学生养成探究计算机领域原理与方法的习惯，培养学生对计算机科学的兴趣。
问题与讨论2 引导学生自主思考以下两个问题：在单向链表中插入新结点时，指针指向的修改是否必须有先后？如果将其顺序逆转，能否完成新结点的插入？为什么？如果在尾结点之后插入新结点，那么结点指针该如何修改？用列表模拟插入新结点的过程，并描述在8个结点的单向链表中删除第一个结点、中间结点及尾结点的过程。 教师不是直接向学生讲解结点插入的步骤，而是通过问题的形式引导学生思考链表结点插入的步骤为什么不能颠倒，有利于加深对链表操作实质的理解，从而实现知识的内化。同时，通过让学生在自学链表插入新结点方法的基础上，自主探究删除结点的方法，有利于学生知识迁移能力的提升。
知识讲解3 通过“基于链表实现数据合并功能”的项目讲解，落实单向链表的基本操作。通过“约瑟夫”项目的分析，让学生体验问题界定、抽象特征、建立结构模型、合理组织数据结构，形成算法、程序实现的过程，同时进一步学会循环链表的操作。 在“合并数据”项目的链表实现与数组实现内容前后呼应，但其并未体现链表的优势，不过在熟悉的项目中，有利于落实单向链表的基本操作；链表教学项目的重点放在了“约瑟夫问题”项目，一方面是“约瑟夫问题”是链表应用的经典项目，另一方面则是其应用需要构造单向循环链表，可以更全面的展示链表的特性与基本操作。
课堂小结 知识梳理：学习评价（附件10：学习评价表） 通过自评引导学生反思本节课所学内容，发现问题与不足，起到查漏及巩固的作用，通过互评与交流加强同伴的交流与合作，实现团队协作中多种能力的培养。
布置作业 ●基础作业（面向所有学生）：基础作业（面向所有学生）：1. 在单向链表在内存中的存储模式图（课本图2.2.2）基础上，请根据双向链表和循环链表的特性，画出它们在内存中的存储模式图。2. 参考课本图2.2.3，描述出在有3个结点的单向链表中删除第1个、第2个及第3个结点的过程。3. 数组与链表作为存储相同类型数据的两种数据结构，拥有各自的应用场景、组织结构和操作特性，请根据教学内容进行简要概括并完善课后思考与练习表格。4. 参考教材中单向链表的列表实现，请思考如何使用列表实现双向链表的结构及其基本操作，思考完善后编程实现双向链表结点的创建、增加、删除及显示等。●提升作业（面向学有余力学生）：设计查找单链表的中间节点的算法，要求只能使用一重循环（只遍历一次）。 课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。根据学生的基础和能力设置不同难度的作业，以满足不同层次的学生需求。
针对核心素养培养的设计考虑 本节教学过程是理论与实践操作相结合的过程，因此可以从以下维度培养学生的核心素养。信息意识：落点在“能够根据解决问题的需要，自觉、主动地寻求恰当方式获取信息与处理信息；在合作解决问题的过程中，愿意与团队成员共享信息，实现信息的更大价值。”在链表的概念及其基本操作讲解中加入数组对比，如链表允许每个结点随机存储，而数组则是按照下标顺序存储；链表的插入、删除操作不需要移动其他结点的位置，而数组则需要进行其它相关数组元素中的数据移动位置，链表不能直接访问结点，必须通过头指针进行访问，其他结点通过结点件的指针依次访问，而数组可以通过下标直接访问等等。通过“数据合并”、“约瑟夫问题”等项目情景引导学生在项目实现过程中自主分析并提取关键数据选择合适的数据结构存储这些数据，体验到数据结构设计与算法效率的相关性，提升学生的关键数据规划意识；以上过程中均在培养或提升学生获取关键信息的能力，即信息意识的培养与提升。计算思维：落点在 “能够采用计算机科学领域的思想方法界定问题、抽象问题特征、建立结构模型、合理组织数据；通过判断、分析与综合各种信息资源，运用合理的算法形成解决问题的方案。”学生在“约瑟夫问题”实现过程中，在教师的引导下体验并参与完整的问题解决过程，学习并明了计算机解决实际问题的步骤及相应算法的设计，在此基础上，学生自主完成班级学生随机抽奖问题（链表实现）的建模及算法设计，在该过程中可以加深及强化学生建模及算法设计的能力，提升自身的计算思维。

展开更多......

收起↑