第 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) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？45【解答】(1) 顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下 标)直接存取它的存储效率高，存取速度快但它的空间大小一经定义，在程序整个运行 期间不会发生改变，因此，不易扩充同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还 有空间，就不会产生存储溢出的问题。
同时在插入和删除时不需要保持数据元素原来的物理 顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高2) 如果有n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用链接存储表示如果采用顺序存储表示，必须在一个连续的可用空间中为这 n 个表分配空间初始时因不知道哪个表增长得快，必须平均分配空间在程序运行过程中，有的表占用的空间增长得快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入；在元素删除时，为填补空白，也可能移动许多元素这个处理过程极其繁琐和低效如果采用链接存储表示，一个表的存储空间可以连续，可以不连续表的增长通过动态存储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便对于 n 个表(包括表的总数可能变化)共存的情形，处理十分简便和快捷所以选用链接存储表示较好。
3) 应采用顺序存储表示因为顺序存储表示的存取速度快，但修改效率低若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序 存储表示较好3-2 针对带表头结点的单链表，试编写下列函数1) 定位函数 Locate：在单链表中寻找第 i 个结点若找到，则函数返回第i 个结点的地址；若找不到，则函数返回NULL2) 求最大值函数max：通过一趟遍历在单链表中确定值最大的结点解答】单链表的结点类(ListNode class)和链表类(List class)的类定义ifndef LIST_H#define LIST_Htemplate class List; template class ListNode { friend class List;private:Type data; ListNode *link;public:ListNode ( ) : link (NULL) { }//将单链表定义在 List.h//前视的类定义//链表结点类的定义//List 类作为友元类定义//数据域//链指针域//仅初始化指针成员的构造函数ListNode ( Type item, ListNode * next = NULL ) : data (item), link (next) { }//初始化数据与指针成员的构造函数ListNode * getLink ( ) { return link; } //取得结点的下一结点地址Type getData ( ) { return data; } //取得结点中的数据void setLink ( ListNode * next ) { link = next; } //修改结点的 link 指针void setData ( Type value ) { data = value; }};template class List { private:ListNode *first, *current;public://修改结点的 data 值//单链表类定义//链表的表头指针和当前元素指针List ( Type value ) { first = current = new ListNode ( value ); } //构造函数~List ( ) { MakeEmpty ( ); delete first; } //析构函数void MakeEmpty ( ); int Length ( ) const;ListNode * Find ( Type value ); ListNode * Locate( int i );Type GetData ( ) { return current->data; }int Insert ( Type value ); Type *Remove ( );//将链表置为空表//计算链表的长度//搜索含 value 的元素并成为当前元素//搜索第 i 个元素并置为当前元素//取出表中当前元素的值//将 value 插在当前位置后并成为当前元素//将表中当前元素删去, 填补者为当前元素ListNode * Firster ( ) { current = first; return first; } //当前指针定位于表头Type First ( ) { ; Type *Next ( );int NotNull ( ) { return current != NULL; }//当前指针定位于表第一个元素并返回值//将当前指针进到表中下一个元素并返回值//表中当前元素空否？空返回 1, 不空返回 0int NextNotNull ( ) { return current != NULL && current->link != NULL; }}; //当前元素的下一元素空否？空返回 1, 不空返回 0(1) 实现定位函数的算法如下：template ListNode * List :: Locate ( int i ) {//取得单链表中第 i 个结点地址, i 从 1 开始计数, i <= 0 时返回指针NULLif ( i <= 0 ) return NULL; //位置 i 在表中不存在ListNode * p = first; int k = 0; //从表头结点开始检测while ( p != NULL && k < i ) { p = p->link; k++; } //循环, p == NULL 表示链短, 无第 i 个结点return p;}//否则 k == i, 返回第 i 个结点地址(2) 实现求最大值的函数如下：template ListNode * List :: Max ( ) {//在单链表中进行一趟检测，找出具有最大值的结点地址, 如果表空, 返回指针 NULL if ( first->link == NULL ) return NULL; //空表, 返回指针 NULL ListNode * pmax = first->link, p = first->link->link;//假定第一个结点中数据具有最大值while ( p != NULL ) {if ( p->data > pmax->data ) pmax = p; p = p->link;//循环, 下一个结点存在//指针 pmax 记忆当前找到的具最大值结点//检测下一个结点}return pmax;}3-3 设 ha 和 hb 分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表。
要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间表中允许有重复的数据解答】#include template class List; template class ListNode { friend class List;public:ListNode ( ) : link ( NULL ) { } //构造函数, 仅初始化指针成员ListNode ( Type item, ListNde * next = NULL ) : data ( item ), link ( next ) { }private:Type data; ListNode *link;//构造函数, 初始化数据与指针成员};template class List { private:ListNode *first, *last; public:List ( Type finishied ) { first = last = new。
