C++数据结构之链表复习资料

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