《数据结构第3章链表》由会员分享，可在线阅读，更多相关《数据结构第3章链表（25页珍藏版）》请在金锄头文库上搜索。
1、45第 3 章 链表一、复一、复习习要点要点本章重点讨论最简单的链表结构单链表。详细地介绍了单链表的抽象数据类型， 单链表的类定义，相应操作的实现，引入了带表头结点的单链表结构。进一步定义了用模 板描述的单链表类。作为一种应用，讨论了一元多项式的类定义及其加法操作的实现。此 外，讨论了循环链表和双向链表。在复习这一章时需要对 C+ 语言中的指针和引用类型的 使用有清楚的理解。对带表头结点的链表和不带表头结点的链表在插入、删除、搜索时的 差别有清楚的认识。而且需要明确：链表是一种实现级的结构。 本章复习的要点： 1、基本知识点 单链表是一种线性结构，链表各结点的物理存储可以是不连续的，因此各结点
2、的逻辑 次序与物理存放次序可以不一致。必须理解单链表的定义和特点，单链表的抽象数据类型 和类定义，单链表成员函数，如构造函数、搜索、插入、删除等操作的实现，对比带表头 结点单链表的搜索、插入、删除操作，比较其优缺点。其次是循环链表的定义和特点，它 与单链表的差别，它的搜索、插入、删除操作的实现。最后是双向链表的定义，它的插入 与删除操作的实现。 2、算法设计 单链表的迭代求解算法，包括统计链表结点个数，在链表中寻找与给定值 value 匹 配的结点，在链表中寻找第 i 个结点，在链表中第 i 个位置插入新结点，删去第 i 个结点， 单链表各结点顺序逆转算法，在单链表中按从左到右和从右到左的顺序
3、遍历的逆转链算法。 带表头结点的单链表的迭代算法，包括统计链表结点个数，在链表中寻找与给定值 value 匹配的结点，在链表中寻找第 i 个结点，在链表中第 i 个位置插入新结点，删去第 i 个结点，连续删除链表中含有 value 值的结点，两个有序链表的合并。 单链表的递归算法，包括统计链表结点个数，在链表中寻找与给定值 value 匹配的 结点，在链表中寻找第 i 个结点，求链表各结点值的和，求链表各结点的值的平均值。 循环链表的迭代算法：包括统计链表结点个数，在链表中寻找与给定值 value 匹配 的结点，在链表中寻找第 i 个结点，在链表中第 i 个位置插入新结点，删去第 i 个结点，
4、将 循环链表链入单链表的表头。 多项式的建立，两个多项式的相加，两个多项式的相减。 用单链表实现字符串操作，每个结点仅存一个字符。二、二、难难点和重点点和重点1、单链表：单链表定义、相应操作的实现。 单链表的两种定义方式(复合方式与嵌套方式)单链表的搜索算法与插入、删除算法单链表的递归与迭代算法 2、循环链表：单链表与循环链表的异同 3、双向链表：带表头结点的双向循环链表 双向循环链表的定义，带表头结点的优点 双向链表的搜索、插入与删除算法464、多项式：多项式的定义、多项式的表示及加法 多项式.的三种表示 多项式链接表示的优点 多项式加法的实现(有序链表的合并算法)三、教材中三、教材中习题习
5、题的解析的解析3-1 线性表可用顺序表或链表存储。试问： (1) 两种存储表示各有哪些主要优缺点? (2) 如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总 数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？ (3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的 元素，这时，应采用哪种存储表示？为什么？ 【解答】 (1) 顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下 标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行 期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，
6、为保持原有次序，平 均需要移动一半(或近一半)元素，修改效率不高。 链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中 还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的 物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针， 修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。 (2) 如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总 数也可能自动改变、在此情况下，应选用链接存储表示。 如果采用顺序存储表示，必须在一个连续的可用空间中为这 n 个表分配空间。初始时 因不
7、知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增 长得快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用 了少量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行 插入；在元素删除时，为填补空白，也可能移动许多元素。这个处理过程极其繁琐和低效。如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动 态存储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储 释放实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对 于 n 个表(包括表的总数可能变化)共存的情形，
8、处理十分简便和快捷。所以选用链接存储 表示较好。 (3) 应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的 总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用 顺序存储表示较好。3-2 针对带表头结点的单链表，试编写下列函数。 (1) 定位函数 Locate：在单链表中寻找第 i 个结点。若找到，则函数返回第 i 个结点的 地址；若找不到，则函数返回 NULL。 (2) 求最大值函数 max：通过一趟遍历在单链表中确定值最大的结点。 (3) 统计函数 number：统计单链表中具有给定值 x 的所有元素。 (4) 建立函数 create：根据一
9、维数组 an建立一个单链表，使单链表中各元素的次序与47an中各元素的次序相同，要求该程序的时间复杂性为 O(n)。 (5) 整理函数 tidyup：在非递减有序的单链表中删除值相同的多余结点。 【解答】 单链表的结点类(ListNode class)和链表类(List class)的类定义。#ifndef LIST_H/将单链表定义在 List.h#define LIST_Htemplate class List;/前视的类定义template class ListNode /链表结点类的定义friend class List;/List 类作为友元类定义private:Type data;
10、/数据域ListNode *link;/链指针域public:ListNode ( ) : link (NULL) /仅初始化指针成员的构造函数ListNode ( Type item, ListNode * next = NULL ) : data (item), link (next) /初始化数据与指针成员的构造函数ListNode * getLink ( ) return link; /取得结点的下一结点地址Type getData ( ) return data; /取得结点中的数据void setLink ( ListNode * next ) link = next; /修改结点
11、的 link 指针void setData ( Type value ) data = value; /修改结点的 data 值;template class List /单链表类定义private:ListNode *first, *current;/链表的表头指针和当前元素指针public:List ( Type value ) first = current = new ListNode ( value ); /构造函数List ( ) MakeEmpty ( ); delete first; /析构函数void MakeEmpty ( );/将链表置为空表int Length ( )
12、const;/计算链表的长度ListNode * Find ( Type value );/搜索含 value 的元素并成为当前元素ListNode * Locate( int i );/搜索第 i 个元素并置为当前元素Type GetData ( ) return current-data; /取出表中当前元素的值int Insert ( Type value );/将 value 插在当前位置后并成为当前元素Type *Remove ( );/将表中当前元素删去, 填补者为当前元素ListNode * Firster ( ) current = first; return first; /
13、当前指针定位于表头Type First ( ) ;/当前指针定位于表第一个元素并返回值Type *Next ( );/将当前指针进到表中下一个元素并返回值int NotNull ( ) return current != NULL; /表中当前元素空否？空返回 1, 不空返回 0int NextNotNull ( ) return current != NULL ;/当前元素的下一元素空否？空返回 1, 不空返回 0(1) 实现定位函数的算法如下：template ListNode * List : Locate ( int i ) /取得单链表中第 i 个结点地址, i 从 1 开始计数,
14、i * p = first; int k = 0;/从表头结点开始检测while ( p != NULL k+; /循环, p = NULL 表示链短, 无第 i 个结点return p;/否则 k = i, 返回第 i 个结点地址(2) 实现求最大值的函数如下：template ListNode * List : Max ( ) /在单链表中进行一趟检测，找出具有最大值的结点地址, 如果表空, 返回指针 NULLif ( first-link = NULL ) return NULL;/空表, 返回指针 NULLListNode * pmax = first-link, p = first-
15、link-link;/假定第一个结点中数据具有最大值while ( p != NULL ) /循环, 下一个结点存在if ( p-data pmax-data ) pmax = p;/指针 pmax 记忆当前找到的具最大值结点p = p-link;/检测下一个结点return pmax;(3) 实现统计单链表中具有给定值 x 的所有元素的函数如下：template int List : Count ( TypeListNode * p = first-link;/从第一个结点开始检测while ( p != NULL ) /循环, 下一个结点存在if ( p-data = x ) n+;/找到
16、一个, 计数器加 1p = p-link;/检测下一个结点return n;(4) 实现从一维数组 An建立单链表的函数如下：template void List : Create ( Type A , int n ) /根据一维数组 An建立一个单链表，使单链表中各元素的次序与 An中各元素的次序相同ListNode * p;first = p = new ListNode;/创建表头结点for ( int i = 0; i link = new ListNode ( Ai );/链入一个新结点, 值为 Aip = p-link;/指针 p 总指向链中最后一个结点p-link = NULL; 采用递归方法实现
