2.2 链表 课件（17张PPT）

(共17张PPT)
链表的应用（第四课时）
n个人排成一圈，从某个人开始，按顺时针方向从1开始依次编号。从编号为1的人开始顺时针“1，2，3，…，m，1，2，3，…”报数，报到m（m＞1）的人退出圈子。按原始编号输出最后一个出圈的编号。
1
2
3
4
5
……
n
6
7
8
约瑟夫游戏
1
2
3
4
5
……
n
6
7
8
约瑟夫游戏
任务一：当n=8,m=3时，请每位同学按游戏规则模拟一下，并按顺序输出出圈人员的编号。
约瑟夫游戏
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
8
出圈顺序为：3 6 1 5 2 8 4 7
7
约瑟夫游戏
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
8
任务二：如何用链表存储这n个人的数据？
7
约瑟夫游戏
1 1
数据区域
指针区域
数组下标
2 2
3 3
4 4
5 5
6 6
7 7
8 0
0
1
2
3
4
5
6
7
每个人设置数据区域和指针区域，当n=8,m=3时，数据如下图所示：
约瑟夫游戏
1 1
数据区域
指针区域
数组下标
2 2
3 3
4 4
5 5
6 6
7 7
8 0
0
1
2
3
4
5
6
7
任务三：请模拟游戏过程中的指针区域的变化过程。
约瑟夫问题
1 1
数据区域
指针区域
数组下标
2 2
3 3
4 4
5 5
6 6
7 7
8 0
0
1
2
3
4
5
6
7
编号为3的人出圈
1 1
数据区域
指针区域
数组下标
2 3
3 3
4 4
5 6
6 6
7 7
8 0
0
1
2
3
4
5
6
7
编号为6的人出圈
1 1
数据区域
指针区域
数组下标
2 3
3 3
4 4
5 6
6 6
7 7
8 0
0
1
2
3
4
5
6
7
编号为1的人出圈
约瑟夫游戏
1 1
数据区域
指针区域
数组下标
2 3
3 3
4 4
5 5
6 6
7 7
8 0
0
1
2
3
4
5
6
7
编号为3的人出圈
算法设计：
任务四：请为约瑟夫游戏设计算法？
约瑟夫游戏
1 1
数据域
指针域
数组下标
2 3
3 3
4 4
5 5
6 6
7 7
8 0
0
1
2
3
4
5
6
7
编号为3的人出圈
算法设计：
1.用二维数组a记录约瑟夫环，a[i][0]表示第i+1个人的编号，a[i][1]表示第i+1个人的指针区域。计数器cnt，初始值为0；总人数n,减少1人时，n的值减1；head表示链表头初始值为0；k表示当前位置，初始值为head，prev为k的前一个数的位置，初始值为n-1。
2.计数器cnt每次加1，分两种情况。
①cnt=m时，当前位置k上的数需要出环，则需要修改prev上的指针域，a[prev][1]=a[k][1]，指向位置k上的指针域指向的数；同时，当前位置发生改变了，k=a[k][1]。并把cnt=0，n=n-1。如果当前的位置k恰好是链表头，则需要修改head的值为a[k][1]。
②cnt!=m时，只需一起移动prev和k。
3.输出a[head][0]。
约瑟夫游戏
1 1
数据区域
指针区域
数组下标
2 2
3 3
4 4
5 5
6 6
7 7
8 0
0
1
2
3
4
5
6
7
问题一：如何新建单向环状链表？
n,m=map(int,input().split())
a=[]
for i in range(n-1):
a.append([i+1,i+1])
a.append([n,0])
for i in range(n):
print(a[i])
约瑟夫问题
n,m=map(int,input().split())
a=[]
for i in range(n-1):
a.append([i+1,i+1])
a.append([n,0])
head=0
prev=n-1
k=head
cnt=0
while n>1:
cnt+=1
if cnt==m:
if k==head:
head=a[k][1]
a[prev][1]=a[k][1]
k=a[k][1]
cnt=0
n-=1
else:
prev=k
k=a[k][1]
print(a[head][0])
1 1
数据区域
指针区域
数组下标
2 2
3 3
4 4
5 5
6 6
7 7
8 0
0
1
2
3
4
5
6
7
约瑟夫游戏
思考：用数组存储数据，并设计算法，用程序实现约瑟夫游戏？
约瑟夫游戏
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
算法：用一维数组a存储每个人的编号，用一维数组flag标记是否出列；顺时针记数，
记录在列的人数，到达m时，则输出该编号，并把flag数组对应的值标记为False。
约瑟夫游戏
n,m=map(int,input().split())
flag=[True]*(n+1)
a=[0]*n
for i in range(n):
a[i]=i+1
k=0;cnt=0;num=0
while numif k==n:
k=1
else:
k+=1
if flag[k]:
cnt+=1
if cnt==m:
print(k,end=" ")
flag[k]=False
cnt=0
1
2
3
4
5
6
7
8
总结
当实例中的数据之间存在相邻关系，又有很多数据需要删除、或者插入时，就可以用链表结构来处理。
同学们，再见