文档文本内容
2023下 粉笔教资
《 信 息技术》
数 据 结 构与算法 2 / 5
▹ 讲师：阿彬
更多干货关注 粉笔教师教育 粉笔教师书上无
（2016下·高中）请画出利用穷举法解决鸡兔同笼问题的流程图。鸡兔同笼问题：今有雉兔
同笼，上有三十五头，下有九十四足，问雉兔各几何？书上无
【参考答案】四、算法的分析 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书上无
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)（二）时间复杂度 补充
2.平方阶 O(n2)
1.线性阶 O(n)
int i, j, n = 100;
int i = 0, n = 100, sum = 0;
for( i=0; i < n; i++ )
for ( i = 0; i < n; i++)
{
{
sum = sum + i; for( j=0; j < n; j++ )
}
{
printf("hello");
}
}第二节 数据结构基础一、相关术语 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
逻辑上相邻的节点在物理位置上也邻接（二）数据物理结构 P265
内存
2.链式存储结构
1 B
2 3
3
C
A B C D 4 7
5 A
6 1
①逻辑上相邻，物理任意
7 D
②借助指针查找下一个数据
8 ……
9（二）数据物理结构 总结下
数据在计算机中的存储方式
◆
内存 内存
A C
B 1.顺序存储结构：
2.链式存储结构：
C • 数据存放在地址连续的空间 B • 数据存放在任意的空间
• 借助相邻位置找下一个数据
D D • 借助指针查找下一个数据
A第三节 线性表一、初识线性表 P265
定义：一组特征相同的有限序列，记为L=（a ，a ，…，a ）
1 2 n
a a … … a
1 2 n
特点1：元素个数有限，可以为0
特点2：元素具有顺序性，即有先后次序
特点3：每个元素占相同的存储空间
特点4：除a 外，其它元素有且仅有一个前驱
1
特点5：除a 外，其它元素有且仅有一个后继
n二、线性表的顺序存储 P266
（一）顺序表的定义
➢线性表的顺序存储又称顺序表
1 2 3 4 5 空闲空间
公式：
特点：随机访问
• 根据序号可方便找到该元素的位置书上无
一个顺序表中第一个元素的储存地址为100，每个元素的长度为2，则第个3元素的存储地址
为（ ）
A.102
B.104
C.106
D.108（二）顺序表的基本操作 P267
1. 初始化（创建）
➢核心操作：分配一个预定义大小的数组空间。
2. 获取表长（实际元素个数）
0 1 2 3 4
➢操作：n = L.length
a b c d e
3. 取值（找第i个元素）
➢操作：e = L.data [i-1]，时间复杂度O(1)
L（二）顺序表的基本操作 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 𝑖=1（二）顺序表的基本操作 P267
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+1三、线性表的链式存储 P269
（一）单链表的定义
内存
C
B
D
1、组成：数据域和指针域
2、本节点的数据：P －> data，下一个节点：P －> next
A
3、术语：头指针、头节点、第1个节点（二）单链表的操作 P270
1. 初始化:构造空表，只有头节点
2. 建立单链表
（1）头插法：将新节点插入到当前链表的表头，即头节点之后
（2）尾插法：将新节点插入到当前链表的表尾。（二）单链表的操作 P270
3. 获取表长（节点总数，不含头节点）
᥈
L a a a a
1 2 3 4
4. 取值（找第 i 位的值，从头查找）
➢ 最好情况：查找第1个位置的节点，比较次数为1
➢ 最坏情况：查找最后位置的节点，比较次数为n
➢ 平均情况：ASL= (n+1)/2（二）单链表的操作 P271
4.取值（查找第 i 位置的数值）
P
᥈
a a a a
1 2 3 … n
1 2 3 … n
➢最好情况：查找第1个位置的节点，比较次数为1
➢最坏情况：查找最后位置的节点，比较次数为n
➢平均情况：设p 是在查找第i个位置上节点的概率，Ci是所需要比较的次数，则平均查找长度为：
i
𝑛 𝑛
1 𝑛 + 1
𝑝 𝐶 = × 𝑖 =
𝑖 𝐼
𝑛 2
𝑖=1 𝑖=1（二）单链表的操作 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;（二）单链表的操作 P294
6.删除 （若删除p节点后面的节点）
【补充】
核心步骤（引入q节点）：
核心步骤（不引入q节点）：
p → next = q → next
p → next = p → next → next顺序表和单链表 总结下
顺序表【顺序存储】 单链表【链式存储】
存储分配 一段连续的空间 一组任意的空间
空间性能 预先分配，容易浪费 不需提前分配
查找 查找方便 查找麻烦
插入和删除 移动大量元素 只需移动指针下
节
内
容
