文档文本内容
~ 2 0 2 4 年 教 师 资 格 ~
《 信 息技术( 科技) 》
数 据 结 构与算法 2 / 5
讲师：阿彬
更多干货关注 粉笔教师教育 粉笔教师P262
四、算法的分析
（一）正确性分析
（1）一组普通数据
内存
（2）一组苛刻数据
（3）一切合法数据
程序代码
（三）空间复杂度
int i , n = 100, sum = 0;
➢不是代码文件所占的存储空间
for( i=0; i < n; i++ )
➢是执行时所占用的附加空间数量 数据
sum = sum + i;P262
（二）时间复杂度
➢不是算法执行所消耗的真正时间
➢是与问题规模（通过统计某语句的执行次数得出）有关
➢是一个预估值，在执行次数中去掉常数项、去掉系数、保留最高阶，用大O表示法
➢量级大小：O(1) < O( log n) < O(n) <O(n log n) < O(n2) < O(2n) < O(n!) < O(nn)
2 2
int i , n, sum = 0;
for( i=0; i < n; i++ )
sum = sum + i;书上无
试题巩固
1.某算法的时间复杂度为O(n)，表明该算法的（ ）。
A.问题规模等于n B.执行时间等于n
C.执行时间与n成正比 D.问题规模与n成正比
2.对于同样的问题规模n，下列哪种算法时间复杂度最大（ ）。
A.O(n) B.O(logn)
C.O(nlogn) D.O(n2)第二节 数据结构基础P263
一、相关术语
（一）数据
➢描述客观事物的符号，即计算机可以操作的对象
（二）数据元素
➢数据元素：数据的基本单位，一个整体，一个记录
➢数据项：数据元素的组成部分
（三）数据结构
➢相互之间存在关系的元素集合P263
二、数据结构的三要素
（一）数据的逻辑结构【4】
➢元素间固有关系，与在计算机中存储位置无关
（二）数据的物理结构【2】
➢数据在计算机中存储方式
（三）数据的运算
➢运算的定义和实现P263
（一）数据逻辑结构
1.线性结构
004 005 006 007
①一对一的关系
②只有一个开始节点和终端节点
③每个节点最多一个直接前驱和直接后继P264
（一）数据逻辑结构
2.树形结构
D盘
学习资料 工作娱乐 其它
数学类 …类 电影
课件
一对多的关系P264
（一）数据逻辑结构
3.图形结构
多对多的关系P264
（一）数据逻辑结构
4.集合
元素之间无关系总结下
（一）数据逻辑结构
元素间固有关系，与在计算机中存储位置无关
◆
逻辑结构 结构类型 关系
线性结构（线性表） 线性 一对一
树 一对多
非线性结构 图 多对多
集合 松散集合P264
（二）数据物理结构
1.顺序存储结构
内存
1
2 A
A B C D 3 B
4
C
5
D
6
1.逻辑上相邻的节点在物理位置上也邻接
2.借助相邻位置找下一个数据P265
（二）数据物理结构
2.链式存储结构
内存
1 B
2 3
3 C
A B C D 4 7
5 A
6 1
①逻辑上相邻，物理任意
7 D
②借助指针查找下一个数据
8 ……
9书上无
试题巩固
（2023 下· 初中）数据在计算机存储器中表示时，逻辑上相邻的两个元素对应的物理地址
也是相邻的，这种存储结构称为（ ）。
A. 顺序存储
B. 链式存储
C. 顺序表
D. 单链表第三节 线性表P265
一、初识线性表
定义：一组特征相同的有限序列，记为L=（a ，a ，…，a ）
1 2 n
a a … … a
1 2 n
特点1：元素个数有限，可以为0
特点2：元素具有顺序性，即有先后次序
特点3：每个元素占相同大小的存储空间
特点4：除a 外，其它元素有且仅有一个直接前驱
1
特点5：除a 外，其它元素有且仅有一个直接后继
nP266
二、线性表的顺序存储
（一）顺序表的定义
➢线性表的顺序存储又称顺序表
1 2 3 4 5 空闲空间
公式：
特点：随机访问（存取）
• 根据序号可方便找到该元素的位置书上无
试题巩固
一个顺序表中第一个元素的储存地址为100，每个元素的长度为2，则第个13元素的存储地
址为（ ）
A.122
B.124
C.126
D.128P267~P268
（二）顺序表的基本操作
操作 说明
1.初始化 构造空表，分配预设大小的数组
2.获取表长 元素的总个数
3.取值（按位查找） 找指定序号位置上的元素
4.插入 在指定位置插入新元素
5.删除 将指定位置的元素删除
a
a[0] a[1] a[2] a[3]P267
（二）顺序表的基本操作
4.插入 （第 i 位置插入新元素）
F
前： A B C D E 空闲空间
后： A B F C D E 空闲空间
结论：从最后一个元素到第 i 个元素依次向后移动一个位置，共移动 n-i+1 个元素P267
（二）顺序表的基本操作
4.插入 （第 i 位置插入新元素）
A B C D E 空闲空间
➢最好情况：在表尾插入，移动次数为0
➢最坏情况：在表头插入，移动次数为n
➢平均情况：设p是在第i个位置上插入元素的概率，则平均移动次数为：
i
𝑛+1 𝑛+1
1 𝑛
𝑝 (𝑛 − 𝑖 + 1) = (𝑛 − 𝑖 + 1) =
𝑖
𝑛 + 1 2
𝑖=1 𝑖=1P268
（二）顺序表的基本操作
5.删除 （删除第 i 位置元素）
前： A B F C D E 空闲空间
后： A B C D E 空闲空间
结论：从第i+1个到最后一个元素依次向前移动一个位置，共移动 n-i 个元素P268
（二）顺序表的基本操作
5.删除 （删除第 i 位置元素）
A B C D E 空闲空间
➢最好情况：在表尾删除，移动次数为0
➢最坏情况：在表头删除，移动次数为n-1
➢平均情况：设p是在第i个位置上删除元素的概率，则平均移动次数为：
i
𝑛 𝑛
1 𝑛 − 1
𝑝 (𝑛 − 𝑖) = (𝑛 − 𝑖) =
𝑖
𝑛 2
𝑖=1 𝑖=1书上无
试题巩固
在一个长度为n的顺序表中删除第i个元素，需要向前移动（ ）个元素。
A.n-i
B.n-i+1
C.n-i-1
D.i+1P269
三、线性表的链式存储
（一）单链表的定义
➢线性表的链式存储又称单链表
内存
C
B
D
①组成：数据域和指针域
②本节点的数据：P -> data，下一个节点：P -> next
A
③术语：头指针、头节点、第1个节点P270
（二）单链表的操作
1. 初始化:构造空表，只有头节点
2. 建立单链表
（1）头插法：将新节点插入到当前链表的表头，即头节点之后
（2）尾插法：将新节点插入到当前链表的表尾。P270
（二）单链表的操作
3. 获取表长（节点总数，不含头节点）
P
᥈
a a a a
1 2 3 … n
1 2 3 … n
4. 取值（找第 i 位的值，从头查找）
➢ 最好情况：查找第1个位置的节点，比较次数为1
➢ 最坏情况：查找最后位置的节点，比较次数为n
➢ 平均情况：ASL= (n+1)/2
结论：从第一个节点开始，依次向后查找【顺序存取/访问】P271
（二）单链表的操作
5.插入 （若在p节点后面插入一个新节点s）
【补充】
核心步骤（引入q节点） 核心步骤（不引入q节点）
①s -> next = q ①s -> next = p -> next
②p -> next = s ②p -> next = s
①②顺序可以颠倒 ①②顺序不可颠倒书上无
试题巩固
在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p和q之间插入s结点，这执
行（ ）操作。
A.s->next=p->next; p->next=s;
B.q->next=s; s->next=p;
C.p->next=s->next; s->next=p;
D.p->next=s; s->next=q;P271
（二）单链表的操作
6.删除 （若删除p节点后面的节点）
【补充】
核心步骤（引入q节点）：
核心步骤（不引入q节点）：
p -> next = q -> next
p -> next = p -> next -> next总结下
顺序表和单链表
顺序表【顺序存储】 单链表【链式存储】
存储分配 一段连续的空间 一组任意的空间
空间性能 预先分配，容易浪费 不需提前分配
查找 查找方便（随机存取/访问） 查找麻烦（顺序存取/访问）
插入 移动n-i+1个元素 只需移动2个指针
删除 移动n-i个元素 只需移动1个指针书上无
试题巩固
（2022 下· 高中）线性表的链式存取是一种（ ）存储结构。
A.顺序存取
B.随机存取
C.索引存取
D.散列存取下
节
内
容
2024FENBI
