第 3 章 链表
一、复习要点
本章复习的要点:
1、基本知识点
单链表是一种线性结构,链表各结点的物理存储可以是不连续的,因此各结点的逻辑
次序与物理存放次序可以不一致。必须理解单链表的定义和特点,单链表的抽象数据类型
和类定义,单链表成员函数,如构造函数、搜索、插入、删除等操作的实现,对比带表头
结点单链表的搜索、插入、删除操作,比较其优缺点。其次是循环链表的定义和特点,它
与单链表的差别,它的搜索、插入、删除操作的实现。最后是双向链表的定义,它的插入
与删除操作的实现。
2、算法设计
单链表的迭代求解算法,包括统计链表结点个数,在链表中寻找与给定值 value 匹
配的结点,在链表中寻找第 i 个结点,在链表中第 i 个位置插入新结点,删去第 i 个结点,
单链表各结点顺序逆转算法,在单链表中按从左到右和从右到左的顺序遍历的逆转链算法。
带表头结点的单链表的迭代算法,包括统计链表结点个数,在链表中寻找与给定值
value 匹配的结点,在链表中寻找第 i 个结点,在链表中第 i 个位置插入新结点,删去第 i 个
结点,连续删除链表中含有 value 值的结点,两个有序链表的合并。
循环链表的迭代算法:包括统计链表结点个数,在链表中寻找与给定值 value 匹配
的结点,在链表中寻找第 i 个结点,在链表中第 i 个位置插入新结点,删去第 i 个结点,将
循环链表链入单链表的表头。
二、难点和重点
1、单链表:单链表定义、相应操作的实现。
单链表的两种定义方式(复合方式与嵌套方式)
单链表的搜索算法与插入、删除算法
单链表的递归与迭代算法
2、循环链表:单链表与循环链表的异同
3、双向链表:带表头结点的双向循环链表
双向循环链表的定义,带表头结点的优点
双向链表的搜索、插入与删除算法
三、习题的解析
3-1 线性表可用顺序表或链表存储。试问:
(1) 两种存储表示各有哪些主要优缺点?
(2) 如果有 n 个表同时并存,并且在处理过程中各表的长度会动态发生变化,表的总数
也可能自动改变、在此情况下,应选用哪种存储表示?为什么?
(3) 若表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取表中的元
素,这时,应采用哪种存储表示?为什么?