数据结构基础知识02--高考信息技术一轮，二轮复习 数据结构基础知识（浙教版2019）

数据结构基础知识（二） 【知识要点】 1.链表的概念与特性 链表的概念：链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。 2.表头:每个链表拥有一个表头——head(也称头指针),有两个作用: (1)链表的入口,只有通过头指针才能进入链表。 (2)为循环链表设立边界,便于数据处理时的边界判断和处理。 3.节点：链表中的每个节点一般由“数据区域”和“指针区域”两部分构成。 数据区域用于保存实际需要处理的数据元素，指针区域用来保存该节点相邻节点的存储地址。某个节点前面的相邻节点称为该节点的前驱节点，后面的相邻节点称为该节点的后继节点。 4.链表的分类。 (1)单向链表:只有一个指针区域,指向该节点的后继节点。 (2) 双向链表:有两个指针区域,一个指向该节点的前驱节点,一个指向该节点的后继节点。 (3) 循环链表:根据需要把链表第一个节点和最后一个节点使用指针链接,就形成了循环链表。 5.链表的特性 ①同一个链表中每个节点的结构均相同。 (1)每个节点的数据区域中的数据类型是相同的。(2)每个节点指针区域中的指针数量和功能相同的。 ②每个链表必定有一个头指针,以实现对链表的引用和边界处理。 (1)引用链表时使用头指针head进入链表。 (2)访问链表中某一个节点只能从头指针开始,通过指针链接依次访问,不能通过下标直接引用。 (3)对于循环链表,一轮访问的开始和结束都可以借助头指针指向位置进行判断,即边界处理。 ③链表占用的空间不固定。 (1)链表的相邻节点存储时不需要连续空间,充分利用了内存的零散空间,提高了存储空间利用率。 (2)链表的存储空间由节点数决定,节点的增加或减少会导致链表占用的空间不固定。 6.链表的基本操作（python中没有专门的链表结构,但是列表(list)相当灵活,可以用二维列表来模拟链表。为了方便模拟,先做几个约定:空链表:头指针head=-1,为空链表；节点:每个节点又是一个列表,含有二个元素:[数据,指针]；尾节点:某个节点元素,指针=-1,说明不存在后继节点；索引:每个节点在列表的索引位置,模拟节点在内存中的位置。） ①链表的创建：例：item=[];head=-1 (1)根据问题特点规划节点的数据域和指针域。 (2)根据规划创建一个空链表 (3)根据输入的实际数据形成节点并逐步插入到已有的链表中。 ②链表节点的访问。 例：p = head #头节点入口 while p != -1: #节点不为空 print(item[p][0]) #输出数据域 p=item[p][1] #下一个节点 (1) 链表只能通过头指针(head)进行访问。 (2) 其他节点通过节点间的指针依次访问。 (3) 若要访问链表中第n个节点,则步骤是:通过头指针进入链表→通过第一个节点的指针访问第二个节点→通 过第二个节点的指针访问第三个节点→……→通过第n-1个节点的指针访问第n个节点。 ③链表节点的插入与删除。 (1)链表节点的插入。 ①链表节点的插入指的是根据新输入的实际数据形成节点,然后修改新节点与其前驱节点的指针,将新节点插入到链表的正确位置。 ②插入举例（一定要注意语句的先后顺序,防止链表断链。下面的代码在p指向节点后插人一个新的节点t） item[t][1]=item[p][1] item[p][1]=t 情况 操作步骤 在空/非空单向链表中插入第一个节点 根据新输入的实际数据形成新节点﹔修改新节点的指针指向与头指针一致;修改头指针指向新节点 在非空单向链表两个节点中间插入新节点 (或者在末尾插入新节点) 根据新输入的实际数据形成新节点﹔修改新节点的指针指向与前一节点的指针指向一致;将前一节点的指针指向新节点 ③插入过程。 插入新的节点，一定要注意语句的先后顺序,防止链表断链。下面的代码在p指向节点后插入一个新节点t: item[t][1]=item[p][1]；item[p][1]=t (2)链表节点的删除 ①链表节点的删除，是通过将需要删除的节点的前驱节点和其后继节点直接相连的方式实现。 ②删除举例。 情况 操作步骤 删除链表第一个节点 修改头指针head指向该节点的后继节点 删除非空链表中间的一个节点 修改该节点的前驱节点的指针指向该节点的后继节点 删除链表最后一个节点 修改该节点的前驱节点的指针指向为空 ③删除过程 删除某个节点,一定要保留它的前驱节点的信息。假定变量p指向待删除节点,变量t指向p的前驱节点: item[t][1]=item[p][1] 根据链表的特点，还可以写成：item[t][1]=item[item[t][1]][1]。 7.Python