数据结构第3章链表.pdf资源-CSDN文库

版权申诉

90 浏览量 2022-07-13 00:01:28 上传评论收藏 1.21MB PDF 举报

资源详情

资源评论

第 3 章链表

一、复习要点

本章重点讨论最简单的链表结构——单链表。详细地介绍了单链表的抽象数据类型，单

链表的类定义，相应操作的实现，引入了带表头结点的单链表结构。进一步定义了用模板描

述的单链表类。作为一种应用，讨论了一元多项式的类定义及其加法操作的实现。此外，讨

论了循环链表和双向链表。在复习这一章时需要对 C++ 语言中的指针和引用类型的使用有

清楚的理解。对带表头结点的链表和不带表头结点的链表在插入、删除、搜索时的差别有清

楚的认识。而且需要明确：链表是一种实现级的结构。

本章复习的要点：

1、基本知识点

单链表是一种线性结构，链表各结点的物理存储可以是不连续的，因此各结点的逻辑次

序与物理存放次序可以不一致。必须理解单链表的定义和特点，单链表的抽象数据类型和类

定义，单链表成员函数，如构造函数、搜索、插入、删除等操作的实现，对比带表头结点单

链表的搜索、插入、删除操作，比较其优缺点。其次是循环链表的定义和特点，它与单链表

的差别，它的搜索、插入、删除操作的实现。最后是双向链表的定义，它的插入与删除操作

的实现。

2、算法设计

单链表的迭代求解算法，包括统计链表结点个数，在链表中寻找与给定值 value 匹配

的结点，在链表中寻找第 i 个结点，在链表中第 i 个位置插入新结点，删去第 i 个结点，单

链表各结点顺序逆转算法，在单链表中按从左到右和从右到左的顺序遍历的逆转链算法。

带表头结点的单链表的迭代算法，包括统计链表结点个数，在链表中寻找与给定值

value 匹配的结点，在链表中寻找第 i 个结点，在链表中第 i 个位置插入新结点，删去第 i 个

结点，连续删除链表中含有 value 值的结点，两个有序链表的合并。

单链表的递归算法，包括统计链表结点个数，在链表中寻找与给定值 value 匹配的结

点，在链表中寻找第 i 个结点，求链表各结点值的和，求链表各结点的值的平均值。

循环链表的迭代算法：包括统计链表结点个数，在链表中寻找与给定值 value 匹配的

结点，在链表中寻找第 i 个结点，在链表中第 i 个位置插入新结点，删去第 i 个结点，将循

环链表链入单链表的表头。

多项式的建立，两个多项式的相加，两个多项式的相减。

用单链表实现字符串操作，每个结点仅存一个字符。

二、难点和重点

1、单链表：单链表定义、相应操作的实现。

单链表的两种定义方式(复合方式与嵌套方式)

单链表的搜索算法与插入、删除算法

单链表的递归与迭代算法

2、循环链表：单链表与循环链表的异同

3、双向链表：带表头结点的双向循环链表

双向循环链表的定义，带表头结点的优点

精品

双向链表的搜索、插入与删除算法

4、多项式：多项式的定义、多项式的表示及加法

多项式.的三种表示

多项式链接表示的优点

多项式加法的实现(有序链表的合并算法)

三、教材中习题的解析

3-1 线性表可用顺序表或链表存储。试问：

(1) 两种存储表示各有哪些主要优缺点?

(2) 如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数

也可能自动改变、在此情况下，应选用哪种存储表示？为什么？

(3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元

素，这时，应采用哪种存储表示？为什么？

【解答】

(1) 顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)

直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间

不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要

移动一半(或近一半)元素，修改效率不高。

链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还

有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理

顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效

率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。

(2) 如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数

也可能自动改变、在此情况下，应选用链接存储表示。

如果采用顺序存储表示，必须在一个连续的可用空间中为这 n 个表分配空间。初始时因

不知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得

快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量

的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入；在

元素删除时，为填补空白，也可能移动许多元素。这个处理过程极其繁琐和低效。

如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动态

存储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放

实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对于 n

个表(包括表的总数可能变化)共存的情形，处理十分简便和快捷。所以选用链接存储表示较

好。

(3) 应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总

数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序

存储表示较好。

3-2 针对带表头结点的单链表，试编写下列函数。

(1) 定位函数 Locate：在单链表中寻找第i 个结点。若找到，则函数返回第i 个结点的地

址；若找不到，则函数返回 NULL。

(2) 求最大值函数 max：通过一趟遍历在单链表中确定值最大的结点。

精品

(3) 统计函数 number：统计单链表中具有给定值 x 的所有元素。

(4) 建立函数 create：根据一维数组 a[n]建立一个单链表，使单链表中各元素的次序与 a[n]

中各元素的次序相同，要求该程序的时间复杂性为O(n)。

(5) 整理函数 tidyup：在非递减有序的单链表中删除值相同的多余结点。

【解答】

单链表的结点类(ListNode class)和链表类(List class)的类定义。

#ifndef LIST_H

#define LIST_H

template <class Type> class List;

friend class List<Type>;

private:

Type data;

public:

ListNode ( ) : link (NULL) { }

ListNode<Type> * getLink ( ) { return link; }

Type getData ( ) { return data; }

//仅初始化指针成员的构造函数

//初始化数据与指针成员的构造函数

//取得结点的下一结点地址

ListNode ( Type item, ListNode<Type> * next = NULL ) : data (item), link (next) { }

//数据域

//链指针域ListNode<Type> *link;

//前视的类定义

//链表结点类的定义

//List 类作为友元类定义

template <class Type> class ListNode {

//将单链表定义在 List.h

//取得结点中的数据

//修改结点的 data 值

void setLink ( ListNode<Type> * next ) { link = next; } //修改结点的 link 指针

void setData ( Type value ) { data = value; }

};

template <class Type> class List {

private:

ListNode<Type> *first, *current;

public:

List ( Type value ) { first = current = new ListNode<Type> ( value ); }

~List ( ) { MakeEmpty ( ); delete first; } //析构函数

void MakeEmpty ( );

int Length ( ) const;

//将链表置为空表

//搜索含 value 的元素并成为当前元素

//搜索第 i 个元素并置为当前元素

//取出表中当前元素的值

//将 value 插在当前位置后并成为当前元素

//将表中当前元素删去, 填补者为当前元素

//当前指针定位于表第一个元素并返回值

//将当前指针进到表中下一个元素并返回值

//计算链表的长度

//构造函数

//链表的表头指针和当前元素指针

//单链表类定义

ListNode<Type> * Find ( Type value );

ListNode<Type> * Locate( int i );

int Insert ( Type value );

Type *Remove ( );

Type First ( ) { ;

Type *Next ( );

Type GetData ( ) { return current->data; }

ListNode<Type> * Firster ( ) { current = first; return first; } //当前指针定位于表头

int NotNull ( ) { return current != NULL; } //表中当前元素空否？空返回 1, 不空返回 0

int NextNotNull ( ) { return current != NULL && current->link != NULL; }

//当前元素的下一元素空否？空返回 1, 不空返回 0

(1) 实现定位函数的算法如下

：

精品

template <class Type> ListNode <Type> * List <Type> :: Locate ( int i ) {

//取得单链表中第 i 个结点地址, i 从 1 开始计数, i <= 0 时返回指针 NULL

if ( i <= 0 ) return NULL; //位置 i 在表中不存在

//从表头结点开始检测

//否则 k == i, 返回第 i 个结点地址

ListNode <Type> * p = first; int k = 0;

return p;

}

while ( p != NULL && k < i ) { p = p->link; k++; } //循环, p == NULL 表示链短, 无第 i 个结点

(2) 实现求最大值的函数如下：

template <class Type> ListNode <Type> * List <Type> :: Max ( ) {

//在单链表中进行一趟检测，找出具有最大值的结点地址, 如果表空, 返回指针 NULL

if ( first->link == NULL ) return NULL; //空表, 返回指针 NULL

//假定第一个结点中数据具有最大值

while ( p != NULL ) {

p = p->link;

}

return pmax;

}

//循环, 下一个结点存在

//指针 pmax 记忆当前找到的具最大值结点

//检测下一个结点

if ( p->data > pmax->data ) pmax = p;

ListNode <Type> * pmax = first->link, p = first->link->link;

(3) 实现统计单链表中具有给定值 x 的所有元素的函数如下：

template <class Type> int List <Type> :: Count ( Type& x ) {

//在单链表中进行一趟检测，找出具有最大值的结点地址, 如果表空, 返回指针 NULL

int n = 0;

ListNode <Type> * p = first->link;

while ( p != NULL ) {

if ( p->data == x ) n++;

p = p->link;

}

return n;

}

//从第一个结点开始检测

//循环, 下一个结点存在

//找到一个, 计数器加 1

//检测下一个结点

(4) 实现从一维数组 A[n]建立单链表的函数如下：

template <class Type> void List <Type> :: Create ( Type A[ ], int n ) {

//根据一维数组 A[n]建立一个单链表，使单链表中各元素的次序与 A[n]中各元素的次序相同

ListNode<Type> * p;

first = p = new ListNode<Type>;

for ( int i = 0; i < n; i++ ) {

p->link = new ListNode<Type> ( A[i] );

p = p->link;

}

p->link = NULL;

}

//链入一个新结点, 值为 A[i]

//指针 p 总指向链中最后一个结点

//创建表头结点

采用递归方法实现时，需要通过引用参数将已建立的单链表各个结点链接起来。为此，

在递归地扫描数组 A[n]的过程中，先建立单链表的各个结点，在退出递归时将结点地址

精品

剩余26页未读，继续阅读

评论收藏

内容反馈

版权申诉

数据结构第3章链表.pdf

评论0

最新资源

数据结构第3章链表.pdf

评论0

最新资源

相关推荐

数据结构总结（自学、期末复习或考研备用）.pdf

数据结构与算法实验内容.pdf

数据结构：八大数据结构分析.pdf

数据结构-链表.pdf

数据结构之链表

数据结构 链表

数据结构1800题及答案.pdf

数据结构(C#语言版).

数据结构与算法(C#)

数据结构作业(1).pdf

数据结构链表

考研数据结构代码.pdf

数据结构：八大数据结构分类及图解.pdf

C语言进阶 (东大 凌明 非常不错)

数据结构(C#语言版)

Lua中文教程(pdf版)

数据结构-链表

数据结构：八大数据结构分类.pdf

世界500强面试题.pdf

数据结构链表

C语言进阶 (东大凌明非常不错)