资源简介

(共24张PPT)
与
组
数
链
2.2 链表
表
录
目
链表的概念与特性
01
链表的基本操作
02
链表应用解决实际问题
03
问题提出
问题：
想用python制作一个班级学生的抽奖程序——输入中奖人数，点抽奖显示中奖人姓名。用数组保存中奖人姓名和暂时未中奖人姓名有什么弊端么？
一、链表的概念
链表指将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。
数据区域
指针区域
实际需要处理的数据元素
相邻结点的存储地址
一、链表的概念
data3
null
data1
next
new
next
data2
next
head
前驱节点
后继节点
一、链表的概念
单向链表中各节点在内存中可以非顺序存储
每个节点使用指针指向其后继节点的存储地址
通过head进入链表，其他节点则需经过所有在它之前的节点才能访问
尾节点的指针指向null，表示指向为空
一、链表的概念
问题与讨论：
描述双向链表和循环链表的节点结构及其指针指向
二、链表的特性
同一链表中每个节点的结构均相同
每个链表必定有一个头指针，以实现对链表的引用和边界处理
链表占用的空间不固定
三、链表的基本操作
链表的创建——通过列表模拟实现
链表实际应用可以不带头节点，本章用列表索引来代替地址指针，规定列表索引均为正索引
Head值为-1，表示头指针指向为空，该链表为空链表
三、链表的基本操作
链表节点的访问
data3
null
data1
next
new
next
data2
next
三、链表的基本操作
链表节点的插入
新数据插入位置
data3
null
data1
next
new
next
data2
next
指针指向的修改是否必须有先后？
三、链表的基本操作
链表节点的插入的列表实现
data1
6
data8
-1
new
next
data3
7
data6
5
data5
3
data7
0
data2
1
data4
2
0
1
2
3
4
5
6
7
head
列表索引
数据区域
指针区域
在第3个节点，即data3节点后插入新节点
next
三、链表的基本操作
data1
6
data8
-1
new
data3
7
data6
5
data5
3
data7
0
data2
1
data4
2
0
1
2
3
4
5
6
7
8
7
8
在第3个节点，即data3节点后插入新节点
三、链表的基本操作
在第3个节点，即data3节点后插入新节点
问题与讨论：
尾节点之后插入新节点，节点指针该如何修改？
描述在有8个节点的单向链表中删除第一个节点、中间节点及尾节点的过程。
三、链表的基本操作
链表的插入应用
例1 基于链表实现数据合并功能
与数组合并功能类似，将两个有序链表的数据合并到其中一个链表中。
三、链表的基本操作
链表的插入应用
三、链表的基本操作
链表的插入应用
三、链表的基本操作
链表的访问与遍历
例2 约瑟夫问题
n个人排成一圈，从某个人开始，按顺时针方向从1开始依次编号。从编号为1的人开始顺时针“1,2,3，……，m,1,2,3,……”报数，报到m(m>1)的人退出圈子。这样不断循环下去，圈子里的人数将不断减少。由于人数是有限的（n个），因此最终会只剩下一个人。试问最后剩下的人的初始编号是多少？
三、链表的基本操作
链表的访问与遍历
抽象建模：
★ n个参与人员的初始编号，1至n的序列。
★ 从编号1开始计数，每过一个编号加1，当计数到m时将该编号从数据序列中移除，并从该编号的后一编号从1开始重新计数。
★ 计数到序列中最后一个编号，又从序列的开始编号继续计数，从而将计数序列构成一个环。
三、链表的基本操作
链表的访问与遍历
设计数据结构与算法：
★ 数据规模初始时可以确定（最大为n）。
★ 数据处理过程中需要按照规则不断地移除数据，直至只剩一个为止。
★ 数据规模逐渐变小，具有不稳定特性，符合链表应用。
★ 最大编号报数后会从最小编号继续报数，所以可采用单向循环链表来组织数据。
三、链表的基本操作
链表的访问与遍历
编写程序
五、思考与练习
1.画出双向链表和循环链表在内存中的存储模式图。
2.编程实现双向链表节点的创建、增加、删除及显示等。
3.从应用场景、组织结构、操作特性方面区分数组和链表。
观
谢
谢
看

展开更多......

收起↑