文档内容
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) 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顺序表和单链表 总结下
顺序表【顺序存储】 单链表【链式存储】
存储分配 一段连续的空间 一组任意的空间
空间性能 预先分配，容易浪费 不需提前分配
查找 查找方便 查找麻烦
插入和删除 移动大量元素 只需移动指针下
节
内
容
