2.2链表 学案 2023—2024学年浙教版（2019）信息技术选择性必修1

在刚开始学习选修课程的时候，大家一定最头痛的是链表这个章节吧，尤其很多同学之前接触的是VB，在Python中这块内容变化多端，考试中试题类型也很丰富，那下面我们就从最基础的链表基本知识学起，深入浅出地讲解下去，大家夯实基础，以不变应万变！ 链表的概念： 链表是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。 节点结构： data(数据域)：用来保存实际需要处理的数据元素。 next(指针域)：用来保存该节点相邻节点的存储地址。 链表的存储方式 链表内存存放方式： 链表的种类： 链表的特性 链表的时间复杂度：要访问由n个节点组成的链表中的第x个节点，时间复杂度为O（x） 链表的基本操作： 案例List=[[“煎饺”，1]，[“馄饨”，3]，[“面饽饽”，-1]，[“生煎包”，4]，[“麦糊烧”，2]] 链表元素的全访问： head=0 p=head While p!=-1 print List[p][0] p=List[p][1] 链表元素的条件访问： head=0 p=head While p!=-1 if len(List[p][0])==2 print List[p][0] p=List[p][1] 链表头节点的删除： head=List[head][1] 链表尾节点的删除： head=0 q=p=head While List[p][1]!=-1 q=p p=List[p][1] List[q][1]=-1 链表中间指定节点的删除： ⅰ 指定删除节点的索引m head=0 q=p=head While p!=m q=p p=List[p][1] List[q][1]=List[m][1] ⅱ 指定删除节点的数据域 （生煎包） head=0 q=p=head While List[p][0]!= “生煎包” q=p p=List[p][1] List[q][1]=List[p][1] 链表节点的插入（newdata= “酱香饼”） 链表头节点的插入： List.append([“酱香饼”，head]) head=len(List)-1 链表尾节点的插入： head=0 q=p=head While p!= -1 q=p p=List[p][1] List.append([“酱香饼”，-1]) List[q][1]=len(List)-1 链表指定索引前位置插入（m） head=0 q=p=head While p!=m q=p p=List[p][1] List.append([“酱香饼”，m]) List[q][1]=len(List)-1 链表指定索引后位置插入（m） head=0 p=head While p!=m p=List[p][1] List.append([“酱香饼”，List[m][1]]) List[p][1]=len(List)-1 链表节点的替换（replacedata= “酱香饼”） 链表头节点的替换 List.append([“酱香饼”，List[head][1]]) head=len(List)-1 链表尾节点的替换 head=0 q=p=head While List[p][1]!=-1 q=p p=List[p][1] List.append([“酱香饼”，-1]) List[q][1]=len(list)-1 链表指定索引m节点的替换 head=0 q=p=head While p!=m q=p p=List[p][1] List.append([“酱香饼”，List[m][1]) List[q][1]=len(list)-1 链表指定数据域（生煎包）节点的替换 head=0 q=p=head While List[p][0]!= “生煎包” q=p p=List[p][1] List.append([“酱香饼”，List[p][1]) List[q][1]=len(list)-1 学科网（北京）股份有限公司 $$