第3章习题(链表).doc资源-CSDN文库

需积分: 5 169 浏览量 2021-06-27 14:49:03 上传评论收藏 210KB DOC 举报

资源推荐

资源详情

资源评论

第 3 章链表

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

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 ( const Type& item ) : data (item), link (NULL) { }

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

ListNode<Type> * getNode ( const Type& item, ListNode<Type> *next = NULL )

//以item和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 ( const 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 ( ); //取出表中当前元素的值

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

};

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

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

第 3 章链表

(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：在非递减有序的单链表中删除值相同的多余结点。

【解答】

(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; //若p != NULL, 则k == i, 返回第i个结点地址

}

第 3 章链表

(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 ) {

剩余14页未读，继续阅读

评论收藏

内容反馈

lhh5356

粉丝: 0
资源: 40

第3章习题(链表).doc

c语言链表大例题.doc

顺序表、链表试题库.doc

链表基本操作(doc)

链表实验报告1.doc

实验链表实验报告.doc

《计算机应用基础》第四章课后答案.doc.doc

西工大noj答案完整版.doc

数据结构习题及答案(1).doc

数据结构-选择题.doc

c++链表习题

C语言链表.doc

链表基本操作实验报告.doc

数据结构（c语言描述）

若干源程序资料12.rar

C 程序指导书及实践指导

生产者与消费者 进程调度模拟（ｃ＋＋）

生产者与消费者 进程的同步与互斥模拟

链表的交，并，差集.doc

C语言链表基本操作.doc

C++链表基本操作.doc

链表的合并-实验报告.doc

c语言堆和链表.doc

城市链表实验报告.doc

链表习题答案

C语言链表程序C语言链表程序.doc

最新资源

生产者与消费者进程调度模拟（ｃ＋＋）

生产者与消费者进程的同步与互斥模拟