单链表ADT模板简单应用算法设计：单链表中前 m 个元素和后 n 个元素的互换

54 阅读 0 评论 36 点赞

我是靠谱客的博主明亮黑猫，最近开发中收集的这篇文章主要介绍单链表ADT模板简单应用算法设计：单链表中前 m 个元素和后 n 个元素的互换，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题描述

目的：使用C++模板设计单链表的抽象数据类型（ADT）。并在此基础上，使用单链表ADT的基本操作，设计并实现单链表的简单算法设计。

内容：（1）请使用模板设计单链表的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。参考网盘中的ADT原型文件。）

（2）ADT的简单应用：使用该ADT设计并实现单链表应用场合的一些简单算法设计。

应用1：假设有一个带头结点的单链表A，现要求设计一个算法，实现单链表的就地逆置，即利用原表的存储空间实现表中前m 个元素和后n 个元素的互换。

参考函数原型：

template<class ElemType>

void Exchange_L( LinkList<ElemType> &L, int m );

输入说明

第一行：待逆置单链表的长度

第二行：待逆置单链表的数据元素（数据元素之间以空格分隔）

第三行：逆置位置m

输出说明

第一行：待逆置单链表的遍历结果

第二行：逆置后单链表的遍历结果

（输入与输出之间以空行分隔）

输入范例

10
13 5 27 9 32 123 76 98 54 87
5

输出范例

13 5 27 9 32 123 76 98 54 87 

123 76 98 54 87 13 5 27 9 32

思路分析

注意当交换前后两段链表的时候，修改做不索引的同时，不要忘记了修改置换之后的尾指针
基本的思路就是切断，然后重新连接。
总的来说需要找到四个结点，因为总共就两处断点。每次断开这个数据链，为了保证对应的数据不丢失，所以就需要保存断开的数据链的头结点

伪代码

emplate<class ElemType>
void Exchange_L( LinkList<ElemType> &L, int m )
{
    L.ListTraverse();
    //原链表的尾结点
    LinkNode<ElemType> *tail = L.getIndex(L.ListLength());
    //m处的右半部分的链表的头结点
    LinkNode<ElemType> *temp = L.getIndex(m + 1);
    //m处的左半部分的尾结点
    LinkNode<ElemType> *temp2 = L.getIndex(m);
    //总体的首位相接
    tail->next = L.GetHead()->next;
    //首节点的1
    L.GetHead()->next = temp;
    temp2->next = NULL;
    cout<<endl;
    L.ListTraverse();
}