文档内容
~ 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) 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
