文档内容
~ 2025年教师资格证·《信息技术》~
数 据 结 构 与 算 法 2 / 5
主讲老师 孙珍珍
粉笔教师教育 粉笔教师第二节 数据结构基础P262
一、相关术语
（一）数据
Ø描述客观事物的符号，即计算机可以操作的对象
（二）数据元素
Ø数据元素：基本单位，一个整体，一个记录
Ø数据项：数据元素的组成部分
（三）数据结构
Ø相互之间存在关系的元素集合P263
二、数据结构三要素
（一）数据的逻辑结构【4】
Ø元素间固有关系，与在计算机中存储位置无关
（二）数据的物理结构【2】
Ø数据在计算机中存储方式
（三）数据的运算
Ø运算的定义和实现书上无
试题巩固
以下关于数据结构的说法中，正确的是（ ）。
A.数据的逻辑结构独立于其存储结构
B.数据的存储结构独立于其逻辑结构
C.数据的逻辑结构与其存储结构一定相同
D.数据的逻辑结构与其存储结构一定不相同P263
（一）数据逻辑结构
1.线性结构
004 005 006 007
①一对一的关系
②只有一个开始节点和终端节点
③每个节点最多一个直接前驱和直接后继P263
（一）数据逻辑结构
2.树形结构
D盘
学习资料 工作娱乐 其它
数学类 …类 电影
课件
一对多的关系P263
（一）数据逻辑结构
3.图形结构
多对多的关系P263
（一）数据逻辑结构
4.集合
属于关系总结下
（一）数据逻辑结构
元素间固有关系，与在计算机中存储位置无关
u
1.线性结构 2.树形结构 3.图形结构 4.集合
一对一 一对多 多对多 属于关系P264
（二）数据物理结构
1.顺序存储结构
A B C D
内存
A
B
C
D
①数据存放在地址连续的空间
②借助相邻位置找下一个数据P264
（二）数据物理结构
2.链式存储结构
A B C D
内存
C
B
D
A
①数据存放在任意的空间
②借助指针查找下一个数据总结下
（二）数据物理结构
数据在计算机中的存储方式
u
内存 内存
A C
B 2.链式存储结构：
1.顺序存储结构：
①数据存放在任意的空间
C ①数据存放在地址连续的空间 B
②借助指针查找下一个数据
②借助相邻位置找下一个数据
D D
A书上无
试题巩固
（2023 下·初中）数据在计算机存储器中表示时，逻辑上相邻的两个元素对应的物理地址也是相邻
的，这种存储结构称为（ ）。
A. 顺序存储结构
B. 链式存储结构
C. 索引存储结构
D. 散列存储结构第三节 线性表P265
一、初识线性表
（一）定义
Ø具有相同数据类型的 n 个数据元素的有限序列，可表示为为L=（a ，a ，…，a ）
1 2 n
a a … … a
1 2 n
特点1：元素个数有限，可以为0
特点2：元素具有顺序性，即有先后次序
特点3：每个元素占相同大小的存储空间
特点4：除a1外，其它元素有且仅有一个直接前驱
特点5：除an外，其它元素有且仅有一个直接后继P265
二、线性表的顺序存储
（一）顺序表的定义
Ø线性表的顺序存储又称顺序表
①公式：
②特点：【随机访问/存取】
Ø根据序号可方便找到该元素的位置P266
（二）顺序表的基本操作
操作 说明
1.初始化 构造空表，分配预设大小的空间
2.获取表长 元素的总个数
3.取值（按位查找） 找指定序号位置上的元素
4.插入 在指定位置插入新元素
5.删除 将指定位置的元素删除
1 2 3 4 5 6 7 8 9 10P267
（二）顺序表的基本操作
4.插入 （第 i 位置插入新元素）
（1）核心操作
F
前： A B C D E 空闲空间
后： A B F C D E 空闲空间
结论：从最后一个元素到第 i 个元素依次向 后 移动一个位置，共移动 n-i+1 个元素P267
（二）顺序表的基本操作
4.插入 （第 i 位置插入新元素）
（2）算法分析
A B C D E 空闲空间
Ø最好情况：在表尾插入，移动次数为0
Ø最坏情况：在表头插入，移动次数为n
Ø平均情况：设p 是在第i个位置上插入元素的概率，则平均移动次数为：
i
$%# $%#
1 𝑛
! 𝑝 (𝑛 − 𝑖 + 1) = ! (𝑛 − 𝑖 + 1) =
!
𝑛 + 1 2
!"# !"#P268
（二）顺序表的基本操作
5.删除 （删除第 i 位置元素）
（1）核心操作
前： A B F C D E 空闲空间
后： A B C D E 空闲空间
结论：从第 i+1 个到最后一个元素依次向 前 移动一个位置，共移动 n-i 个元素P268
（二）顺序表的基本操作
5.删除 （删除第 i 位置元素）
（2）算法分析
A B C D E 空闲空间
Ø最好情况：在表尾删除，移动次数为0
Ø最坏情况：在表头删除，移动次数为n-1
Ø平均情况：设p 是在第i个位置上删除元素的概率，则平均移动次数为：
i
$ $
1 𝑛 − 1
! 𝑝 (𝑛 − 𝑖) = ! (𝑛 − 𝑖) =
!
𝑛 2
!"# !"#P269
三、线性表的链式存储
（一）单链表的定义
Ø线性表的链式存储又称单链表
内存
C
B
D
①组成：数据域和指针域
A ②本节点的数据：P→data，下一个节点：P→next
③术语：头指针、头节点、第1个节点P269
（二）单链表的操作
操作 说明
1.初始化 构造空表，只有头节点
2.建立单链表 分头插法和尾插法
3.获取表长 节点的总个数（不含头节点）
4.取值（按位查找） 找指定序号位置上的节点
5.插入 在指定位置插入新节点
6.删除 将指定位置的节点删除P270
（二）单链表的操作
4.取值（查找第 i 位置的数值）
（1）核心操作
P
a a a a
1 2 3 … n
1 2 3 … n
结论：从第一个节点开始，依次向后查找【顺序存取/访问】书上无
试题巩固
（2022 下·高中）线性表的链式存储是一种（ ）存储结构。
A.顺序存取
B.随机存取
C.索引存取
D.散列存取P270
（二）单链表的操作
4.取值（查找第 i 位置的数值）
（2）算法分析
P
a a a a
1 2 3 … n
Ø最好情况：查找第1个位置的节点，比较次数为1
Ø最坏情况：查找最后位置的节点，比较次数为n
Ø平均情况：设p 是在查找第i个位置上节点的概率，Ci是所需要比较的次数，则平均查找长度为：
i
$ $
1 𝑛 + 1
! 𝑝 𝐶 = ! ×𝑖 =
! &
𝑛 2
!"# !"#P270
（二）单链表的操作
5.插入 （若在p节点后面插入一个新节点s）
【补充】
核心步骤（不引入q节点）
核心步骤（引入q节点）
①s → next = p → next
①s → next = q
②p → next = s
②p → next = s
①②顺序不可颠倒P271
（二）单链表的操作
6.删除 （若删除p节点后面的节点）
【补充】
核心步骤（引入q节点）： 核心步骤（不引入q节点）：
p → next = q → next p → next = p → next → next总结下
顺序表和单链表
顺序表【顺序存储】 单链表【链式存储】
存储分配 一段连续的空间 一组任意的空间
空间性能 预先分配，容易浪费 不需提前分配
查找 查找方便（随机存取） 查找麻烦（顺序存取）
插入和删除 移动大量元素 只需移动指针P271
（三）双链表
1.双链表的定义
Ø在单链表的结点中增加了一个指向其前驱的prior 指针P271
（三）双链表
2.插入操作
核心操作：
①s→next = p→next ②p→next→prior=s
③s→prior=p ④p→next=s
①和②一定要在④前完成P272
（三）双链表
3.删除操作
核心步骤（引入p节点）
①p→next = q→next
②q→next→prior = pP272
（四）循环链表
1.循环单链表【首尾相连】
2.循环双链表【首尾相连】下
节
内
容在 粉 笔
遇 见 不 一 样 的 自 己
粉笔教师教育 粉笔教师
