数据结构第3章链表.doc

第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 //将单链表定义在List.h
#define LIST_H
template <class Type> class List; //前视的类定义
template <class Type> class ListNode { //链表结点类的定义
friend class List<Type>; //List类作为友元类定义
private:
Type data; //数据域
ListNode<Type> *link; //链指针域
public:
ListNode ( ) : link (NULL) { } //仅初始化指针成员的构造函数
ListNode ( Type item, ListNode<Type> * next = NULL ) : data (item), link (next) { }
//初始化数据与指针成员的构造函数
ListNode<Type> * getLink ( ) { return link; } //取得结点的下一结点地址
Type getData ( ) { return data; } //取得结点中的数据
void setLink ( ListNode<Type> * next ) { link = next; } //修改结点的link指针
void setData ( Type value ) { data = value; } //修改结点的data值
};

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; //计算链表的长度
ListNode<Type> * Find ( Type value ); //搜索含value的元素并成为当前元素
ListNode<Type> * Locate( int i ); //搜索第i个元素并置为当前元素
Type GetData ( ) { return current->data; } //取出表中当前元素的值
int Insert ( Type value ); //将value插在当前位置后并成为当前元素
Type *Remove ( ); //将表中当前元素删去, 填补者为当前元素
ListNode<Type> * Firster ( ) { current = first; return first; } //当前指针定位于表头
Type First ( ) { ; //当前指针定位于表第一个元素并返回值
Type *Next ( ); //将当前指针进到表中下一个元素并返回值
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在表中不存在
ListNode <Type> * p = first; int k = 0; //从表头结点开始检测
while ( p != NULL && k < i ) { p = p->link; k++; } //循环, p == NULL表示链短, 无第i个结点
return p; //否则k == i, 返回第i个结点地址
}

(2) 实现求最大值的函数如下：
template <class Type> ListNode <Type> * List <Type> :: Max ( ) {
//在单链表中进行一趟检测，找出具有最大值的结点地址, 如果表空, 返回指针NULL
if ( first->link == NULL ) return NULL; //空表, 返回指针NULL
ListNode <Type> * pmax = first->link, p = first->link->link;
//假定第一个结点中数据具有最大值
while ( p != NULL ) { //循环, 下一个结点存在
if ( p->data > pmax->data ) pmax = p; //指针pmax记忆当前找到的具最大值结点
p = p->link; //检测下一个结点
}
return pmax;
}

(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++; //找到一个, 计数器加1
p = p->link; //检测下一个结点
}
return n;
}

(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] ); //链入一个新结点, 值为A[i]
p = p->link; //指针p总指向链中最后一个结点
}
p->link = NULL;
}
采用递归方法实现时，需要通过引用参数将已建立的单链表各个结点链接起来。为此，在递归地扫描数组A[n]的过程中，先建立单链表的各个结点，在退出递归时将结点地址p（被调用层的形参）带回上一层（调用层）的实参p->link。
template<Type> void List<Type> :: create ( Type A[ ], int n, int i, ListNode<Type> *& p ) {
//私有函数：递归调用建立单链表
if ( i == n ) p = NULL;
else { p = new ListNode<Type>( A[i] ); //建立链表的新结点
create ( A, n, i+1, p->link ); //递归返回时p->link中放入下层p的内容
}
}
template<Type> void List<Type> :: create ( Type A[ ], int n ) {
//外部调用递归过程的共用函数
first = current = new ListNode<Type>; //建立表头结点
create ( A, n, 0, first->link ); //递归建立单链表
}

(5) 实现在非递减有序的单链表中删除值相同的多余结点的函数如下：
template <class Type> void List <Type> :: tidyup ( ) {
ListNode<Type> * p = first->link, temp; //检测指针, 初始时指向链表第一个结点
while ( p != NULL && p->link != NULL ) //循环检测链表
if ( p->data == p->link->data ) { //若相邻结点所包含数据的值相等
temp = p->first; p->link = temp->link; //为删除后一个值相同的结点重新拉链
delete temp; //删除后一个值相同的结点
}
else p = p->link; //指针p进到链表下一个结点
}

3-3 设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。
【解答】
#include <iostream.h>
template <class Type> class List;
template <class Type> class ListNode {
friend class List<Type>;
public:
ListNode ( ) : link ( NULL ) { } //构造函数, 仅初始化指针成员
ListNode ( Type item, ListNde<Type> * next = NULL ) : data ( item ), link ( next ) { }
private: //构造函数, 初始化数据与指针成员
Type data;
ListNode<Type> *link;
};

template <class Type> class List {
private:
ListNode<Type> *first, *last;
public:
List ( Type finishied ) { first = last = new ListNode<Type>( finished ); }
//建立链表, 在表头结点的data域中存放数据输入结束标志, 它是表中不可能出现的数据
void Merge ( List<Type> &hb ); //连接链表
friend istream& operator >> ( istream& in, List<Type> inList ); //输入链表
friend ostream& operator << ( ostream& out, List<Type> outList ); //输出链表
}

istream& operator >> ( istream& in, List<Type> inList ) {
Type value; ListNode<Type> *p, *q, *s;
in >> value;
while ( value != inList.first->data ) { //循环建立各个结点
s = new ListNode<Type>( value );
q = first; p = inList.first->link; //寻找新结点插入位置
while ( p != NULL && p->data <= value ) { q = p; p = p->link; }
q->link = s; s->link = p; //在q, p间插入新结点
if ( p == NULL ) inList.last = s;
in >> value;
}
}

ostream& operator << ( ostream& out, List<Type> outList ) {
cout<<"\nThe List is : \n";
ListNode<Type> *p = outList.first->link;
while ( p != NULL ) {
out << p->data;
if ( p != last ) out << "->";
else out << endl;
p = p->link;
}
}

template <class Type> void List <Type> :: Merge ( List<Type>& hb ) {
//将当前链表this与链表hb按逆序合并，结果放在当前链表this中。
ListNode<Type> *pa, *pb, *q, *p;
pa = first->link; pb = hb.first->link; //检测指针跳过表头结点
first->link = NULL; //结果链表初始化
while ( pa != NULL && pb != NULL ) { //当两链表都未结束时
if ( pa->data <= pb->data )
{ q = pa; pa = pa->link; } //从pa链中摘下
else
{ q = pb; pb = pb->link; } //从pb链中摘下
q→link = first->link; first->link = q; //链入结果链的链头
}
p = ( pa != NULL ) ? pa : pb; //处理未完链的剩余部分
while ( p != NULL ) {
q = p; p = p->link;
q->link = first->link; first->link = q;
}
}

3-4 设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。

【解答1】
template<class Type> void List<Type> :: Inverse ( ) {
if ( first == NULL ) return;
ListNode<Type> *p = first->link, *pr = NULL;
while ( p != NULL ) {
first->link = pr; //逆转first指针
pr = first; first = p; p = p->link; //指针前移
}
first->link = pr;
}
【解答2】
template<class Type> void List<Type> :: Inverse ( ) {
ListNode<Type> *p, *head = new ListNode<Type> ( ); //创建表头结点, 其link域默认为NULL
while ( first != NULL ) {
p = first; first = first->link; //摘下first链头结点
p->link = head->link; head->link = p; //插入head链前端
}
first = head->link; delete head; //重置first, 删去表头结点
}

3-5 从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆转，如右图所示。在图中的指针p指向当前正在访问的结点，指针pr指向指针p所指结点的左侧的结点。此时，指针p所指结点左侧的所有结点的链接方向都已逆转。
(1) 编写一个算法，从任一给定的位置(pr, p)开始，将指针p右移k个结点。如果p移出链表，则将p置为0，并让pr停留在链表最右边的结点上。
(2) 编写一个算法，从任一给定的位置(pr, p)开始，将指针p左移k个结点。如果p移出链表，则将p置为0，并让pr停留在链表最左边的结点上。

【解答】
(1) 指针p右移k个结点
template<class Type> void List<Type> ::
siftToRight ( ListNode<Type> *& p, ListNode<Type> *& pr, int k ) {
if ( p == NULL && pr != first ) { //已经在链的最右端
cout << "已经在链的最右端，不能再右移。" << endl;
return;
}
int i; ListNode<Type> *q;
if ( p == NULL ) //从链头开始
{ i = 1; pr = NULL; p = first; } //重置p到链头也算一次右移
else i = 0;
while ( p != NULL && i < k ) { //右移k个结点
q = p->link; p->link = pr; //链指针p→link逆转指向pr
pr = p; p = q; i++; //指针pr, p右移
}
cout << "右移了" << i << "个结点。" << endl;
}

(2) 指针p左移k个结点
template<class Type> void List<Type> ::
siftToLeft ( ListNode<Type> *& p, ListNode<Type> *& pr, int k ) {
if ( p == NULL && pr == first ) { //已经在链的最左端
cout << "已经在链的最左端，不能再左移。" << endl;
return;
}
int i = 0; ListNode<Type> *q;
while ( pr != NULL && i < k ) { //左移k个结点
q = pr->link; pr->link = p; //链指针pr->link逆转指向p
p = pr; pr = q; i++; //指针pr, p左移
}
cout << "左移了" << i << "个结点。" << endl;
if ( i < k ) { pr = p; p = NULL; } //指针p移出表外，重置p, pr
}

3-6 试写出用单链表表示的字符串类及字符串结点类的定义，并依次实现它的构造函数、以及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等7个成员函数。要求每个字符串结点中只存放一个字符。
【解答】
//用单链表表示的字符串类string1的头文件string1.h
#include <iostream.h>
const int maxLen = 300; //字符串最大长度为300（理论上可以无限长）
class string1 {
public:
string1 ( ); //构造空字符串
string1 ( char * obstr ); //从字符数组建立字符串
~string1 ( ); //析构函数
int Length ( ) const { return curLen; } //求字符串长度
string1& operator = ( string1& ob ); //串赋值
int operator == ( string1& ob ); //判两串相等
char operator [ ] ( int i ); //取串中字符
string1 operator ( ) ( int pos, int len ); //取子串
string1& operator += ( string1& ob ); //串连接
int Find ( string1& ob ); //求子串在串中位置(模式匹配)
friend ostream& operator << ( ostream& os, string1& ob );
friend istream& operator >> ( istream& is, string1& ob );
private:
ListNode<char>*chList; //用单链表存储的字符串
int curLen; //当前字符串长度
}
//单链表表示的字符串类string1成员函数的实现，在文件string1.cpp中
#include <iostream.h>
#include "string1.h"
string1 :: string1( ) { //构造函数
chList = new ListNode<char> ( '\0' );
curLen = 0;
}

string1 :: string1( char *obstr ) { //复制构造函数
curLen = 0;
ListNode<char> *p = chList = new ListNode<char> ( *obstr );
while ( *obstr != '\0' ) {
obstr++;
p = p->link = new ListNode<char> ( *obstr );
curLen++;
}
}

string1& string1 :: operator = ( string1& ob ) { //串赋值
ListNode<char> *p = ob.chList;
ListNode<char> *q = chList = new ListNode<char> ( p->data );
curLen = ob.curLen;
while ( p->data != '\0' ) {
p = p->link;
q = q->link = new ListNode<char> ( p->data );
}
return this;
}

int string1 :: operator == ( string1& ob ) { //判两串相等
if ( curLen != ob.curLen ) return 0;
ListNode <char> *p = chList, *q = ob.chList;
for ( int i = 0; i < curLen; i++ )
if ( p->data != q->data ) return 0;
else { p = p->link; q = q->link; }
return 1;
}

char string1 :: operator [ ] ( int i ) { //取串中字符
if ( i >= 0 && i < curLen ) {
ListNode <char> *p = chList; int k = 0;
while ( p != NULL && k < i ) { p = p->link; k++; }
if ( p != NULL ) return p->data;
}
return '\0';
}

string1 string1 :: operator ( ) ( int pos, int len ) { //取子串
string1 temp;
if ( pos >= 0 && len >= 0 && pos < curLen && pos + len - 1 < curLen ) {
ListNode<char> *q, *p = chList;
for ( int k = 0; k < pos; k++; ) p = p->link; //定位于第pos结点
q = temp.chList = new ListNode<char> ( p->data );
for ( int i = 1; i < len; i++ ) { //取长度为len的子串
p = p->link;
q = q->link = new ListNode<char> ( p->data );
}
q->link = new ListNode<char> ( '\0' ); //建立串结束符
temp.curLen = len;
}
else { temp.curLen = 0; temp.chList = new ListNode<char> ( '\0' ); }
return temp;
}

string1& string1 :: operator += ( string1& ob ) { //串连接
if ( curLen + ob.curLen > maxLen ) len = maxLen - curLen;
else len = ob.curLen; //传送字符数
ListNode<char> *q = ob.chList, *p = chList;
for ( int k = 0; k < curLen - 1; k++; ) p = p->link; //this串的串尾
k = 0;
for ( k = 0; k < len; k++ ) { //连接
p = p->link = new ListNode<char> ( q->data );
q = q->link;
}
p→link = new ListNode<char> ( '\0' );
return this;
}

int string1 :: Find ( string1& ob ) { //求子串在串中位置(模式匹配)
int slen = curLen, oblen = ob.curLen, i = slen - oblen;
string1 temp = this;
while ( i > -1 )
if ( temp( i, oblen ) == ob ) break;
else i-- ;
return i;
}

3-7 如果用循环链表表示一元多项式，试编写一个函数Polynomial :: Calc(x)，计算多项式在x处的值。
【解答】
下面给出表示多项式的循环链表的类定义。作为私有数据成员，在链表的类定义中封装了3个链接指针：first、last和current，分别指示链表的表头结点、链尾结点和最后处理