链表的概念、特性、基本操作　　 【核心知识精讲精析】 浙教版（2019）高中信息技术选修1

选择性必修1《数据与数据结构》第二章数组与链表2.2.1链表的概念、特性、基本操作情境导入——排队与插队数组的缺点：插入和删除元素操作需要移动大量的元素频繁增、删数据导致数据规模不稳，形成存储空间“碎片”需要限定最大空间，造成资源浪费链表基本概念整队前的位置和链接关系链表指的是将需要处理的数据对象以结点的形式，通过指针串联在一起的一种数据结构。链表结点结构保存数据元素保存相邻结点的存储地址链表基本概念：头指针（head）作用：一是链表的入口，只有通过头指针才能进入链表二是为循环链表设立一个边界，便于数据处理时的边界判断和处理链表基本概念链表的基本概念根据每个结点中指针的数量分为：单向链表：双向链表：循环链表：第一个结点和最后一个结点使用指针链接，这样就形成了循环链表。next吴坚黄刚王林李丰headnextnextnext根据指针数量分为：单向链表、循环链表链表基本概念单向链表中各个结点在内存中可以随意存储，每个结点使用指针指向其后继结点的存储地址。进入链表只能通过头指针head，其他结点则需要经过所有在它之前的结点才可以访问，尾结点的指针指向为null，表示指向为空。链表的特性（1）同一链表中每个结点的结构均相同数据类型相同指针数量和功能相同（2）每个链表必定有一个头指针，以实现对链表的引用和边界处理head（3）链表占用的空间不固定链表的基本操作——链表的创建Item=[]Head=-1其中head值为–1，表示头指针指向为空，该链表为空链表。

创建链表时，首先要根据问题特点规划结点的数据域和指针域，然后根据规划创建一个空表和头结点。接下来就可以根据输入的实际数据形成结点并逐步插入到已有的链表中。链表的基本操作——链表结点的插入与删除Newdatanextdata1nextdata2nextdata3-1headNewdatanextdata1nextdata2nextdata3-1headnext在单向链表data1和data2所处结点的中间位置插入一个新结点1.在单向链表中插入新结点时，指针指向的修改是否必须有先后？如果将其顺序逆转，能否完成新结点的插入？为什么？链表的基本操作——链表结点的插入与删除描述未删除列表前链表结点的链接关系：data[8][1]=data[1][1]data[1][1]=8实现语句：参考上图，描述出在有8个结点的单向链表中删除第一个结点、中间结点及尾结点的过程。data:2在指定节点后插入新数据list[s][1]=list[p][1]list[p][1]=snext[s]=next[p]next[p]=s两个一维列表放数据和地址一个二维列表放数据和地址list删除结点list[s][1]=list[p][1]next[s]=next[p]两个一维列表放数据和地址一个二维列表放数据和地址spq链表的基本操作——数据合并（1）算法设计

①初始化两个空链表data_a和data_b，并使用head_a和head_b作为两个链表的头指针，其中data_a作为存储结果的链表。②使用随机函数randint(start,end)模拟生成两个降序序列数据，生成新的结点在尾部插入。链表的基本操作——数据合并19161285^data_a:head_aq_ak_a20151432^data_b:head_bk_b链表的基本操作——数据合并程序实现程序测试结果fromrandomimportrandintdata_a=[]head_a=-1data_b=[]head_b=-1tmp=randint(95,100)data_a.append([tmp,head_a])head_a=0foriinrange(1,4):tmp=data_a[i-1][0]-randint(1,5)

data_a.append（________________)____________________print("链表结构的原始数据序列一")print(data_a)([tmp,data_a[i-1][1]][tmp,data_a[i-1][1]]data_a[i-1][1]=i链表的基本操作——数据合并程序实现程序测试结果tmp=randint(95,100)data_b.append([tmp,head_b])head_b=0foriinrange(1,3):tmp=data_b[i-1][0]-randint(1,5)

__________________________________________________print("链表结构的原始数据序列二")print(data_b)#初始化列表索引k_a=head_aq_a=head_ak_b=head_bdata_b.append([tmp,data_b[i-1][1]])data_b[i-1][1]=i链表的基本操作——数据合并程序实现程序测试结果while(k_a!=-1andk_b!=-1):ifdata_a[k_a][0]>=data_b[k_b][0]:__________________________else:ifk_a==head_a:#在链表data_a的头部插入结点data_a.append([data_b[k_b][0],head_a])head_a=____________

q_a=___________

k_b=___________

else:

data_a.append_____________data_a[q_a][1]=________________

q_a=____________

k_b=q_a=k_ak_a=data_a[k_a][1]len(data_a)-1head_adata_b[k_b][1]([data_b[k_b][0],k_a])len(data_a)-1data_a[q_a][1]data_b[k_b][1]链表的基本操作——数据合并程序实现程序测试结果whilek_b!=-1:data_a.append______________

data_a[q_a][1]=___________q_a=_______________k_b=data_b[k_b][1]print("链表结构的合并后数据序列")print(data_a)print("按链表链接顺序输出数据序列")tmp