首页 / 算法 / 6 循环链表ADT模板简单应用算法设计：循环链表的合并

6 循环链表ADT模板简单应用算法设计：循环链表的合并

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了6 循环链表ADT模板简单应用算法设计：循环链表的合并，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7651字，纯文字阅读大概需要11分钟。

内容图文

问题描述：

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

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

应用1：假设2个线性表分别由带头结点的循环链表A和B存储。现要求设计一个算法，将A和B归并为一个线性表。要求利用循环链表的特点，使用A和B的原存储空间，且合并后B成为一空表。

参考函数原型：
template
void Merge_Cur_Linklist( CirLinkList &A, CirLinkList &B );

循环链表模板类原型参考如下：
/* 循环单链表的结点定义*/
template
struct LinkNode
{
ElemType data;
LinkNode *next;
LinkNode(LinkNode *ptr = NULL){next = ptr;} //构造函数1，用于构造头结点
LinkNode(const ElemType &item, LinkNode *ptr = NULL) //构造函数2，用于构造其他结点
//函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
{
next = ptr;
data = item;
}
//int getNum(){ return number; } //取得结点的序号
ElemType getData(){ return data; } //取得结点的数据域的值
void SetLink( LinkNode *link ){ next = link; } //修改结点的next域
void SetLink( ElemType value ){ data = value; } //修改结点的next域
};

//带头结点的循环单链表
template
class CirLinkList{
private:
LinkNode head; // 头结点
LinkNode tail; // 尾结点
public:
//无参数的构造函数
CirLinkList(){head = new LinkNode; tail = head; head->next = head;}
//带参数的构造函数
CirLinkList(const ElemType &item){head = new LinkNode(item); tail = head; head->next = head;}
//拷贝构造函数
CirLinkList(CirLinkList &List);
//析构函数
~CirLinkList(){ListDestroy();}
//销毁链表
void ListDestroy();
//清空链表
void ListClear();
//返回链表的长度
int ListLength() const;
//判断链表是否为空表
bool ListEmpty() const;
//获取循环链表头结点
LinkNode GetHead() { return head;}
//获取循环链表尾结点
LinkNode GetTail() { return tail;}
//设置链表头结点
void SetHead(LinkNode *p){ head = p;}
//在链表的第pos个位置之后插入e元素
bool ListInsert_next(int pos,ElemType e);
//在首结点之前插入一个结点
bool InsFirst( ElemType &e );
//在尾结点之前插入一个结点
bool InsTail( ElemType &e );
//表头插入法动态生成链表
void CreateList_Head(vector &A);
//表尾插入法动态生成链表
void CreateList_Tail(vector &A);
//遍历链表
bool ListTraverse() const;
};

输入说明：

第一行：顺序表A的数据元素的数据类型标记（0：int，1：double，2：char，3：string）
第二行：第一个循环链表的数据元素（元素与元素之间以空格分隔）
第三行：第二个循环链表的数据元素（元素与元素之间以空格分隔）

输出说明：

如第一行输入值为0、1、2、3之外的值，直接输出“err”
否则：

第一行：第一个循环链表的遍历结果
第二行：第二个循环链表的遍历结果
空行
第四行：合并后循环链表的遍历结果

SAMPLE INPUT：

0
13 5 27 9 32 123 76 98 54 87
1 3 7 8 11

SAMPLEOUTPUT：

13->5->27->9->32->123->76->98->54->87
1->3->7->8->11

13->5->27->9->32->123->76->98->54->87->1->3->7->8->11

思路：

整体代码还是一个ADT表，ADT表的具体操作与先前的顺序表的大致相同，只需要做一些简单的改变（循环链表的尾结点是指向头部的，而不是顺序表中的指向NULL）本题的核心是两个不同的循环链表的合并。循环链表的特征是尾结点指向头结点，也就是对于循环链表A，其尾结点指向头部，B也是如此，那么想要将两个循环链表合并，我只需要让A的尾结点指向B的头结点，B的尾结点指向A的头结点即可，其他不需要任何额外操作了。
P.S数据的输入部分我照搬了先前的代码，有更加便捷的写法，这绝不是最佳方法！！！

AC代码：


#include <bits/stdc++.h>
using namespace std;
int no;
template<class ElemType>
struct LinkNode
{
    ElemType data;
    LinkNode<ElemType> *next;
    LinkNode(LinkNode<ElemType> *ptr = NULL)
    {
        next = ptr;
    }
    LinkNode(const ElemType &item, LinkNode<ElemType> *ptr = NULL)
    {
        next = ptr;
        data = item;
    }
    ElemType getData()
    {
        return data;
    }
    void SetLink( LinkNode<ElemType> *link )
    {
        next = link;
    }
    void SetLink( ElemType value )
    {
        data = value;
    }
};
template<class ElemType>
class CirLinkList
{
private:
    LinkNode<ElemType> *head;
    LinkNode<ElemType> *tail;
public:
    CirLinkList()
    {
        head=NULL;
        tail=NULL;
    }
    CirLinkList(const ElemType &item)
    {
    }
    CirLinkList(CirLinkList<ElemType> &List);
    ~CirLinkList()
    {
        ListDestroy();
    }
    void del(int x);
    void ListDestroy();
    void ListClear();
    int ListLength() const;
    bool ListEmpty() const;
    LinkNode<ElemType>* GetHead()
    {
        return head;
    }
    LinkNode<ElemType>* GetTail()
    {
        return tail;
    }
    void SetHead(LinkNode<ElemType> *p)
    {
        head = p;
    }
    bool ListInsert_next(int pos,ElemType e);
    bool InsFirst( ElemType &e );
    bool InsTail( ElemType &e );
    void CreateList_Head(vector<ElemType> &A);
    void CreateList_Tail(vector<ElemType> &A);
    bool ListTraverse() const;
    void push_back(ElemType element);
    void Merge_Cur_Linklist( CirLinkList<ElemType> &A, CirLinkList<ElemType> &B );
    void changeTail(LinkNode<ElemType>*p);
    LinkNode<ElemType>* getHead()
    {
        return head;
    }
    LinkNode<ElemType>* getTail()
    {
        return tail;
    }
};
template <class ElemType>
void CirLinkList<ElemType>::changeTail(LinkNode<ElemType>*p)
{
    tail = p;
    return;
}
template <class ElemType>
void CirLinkList<ElemType>::push_back(ElemType element)
{
    if(head==NULL)
    {
        head=new LinkNode<ElemType>;
        head->data=element;
        tail=head;
        tail->next=head;
        return ;
    }
    LinkNode<ElemType>*p=new LinkNode<ElemType>;
    p->data=element;
    p->next=head;
    tail->next=p;
    tail=p;
    return;
}
template <class ElemType>
bool CirLinkList<ElemType>::ListTraverse() const
{
    LinkNode<ElemType>* p;
    bool fir = 0;
    p = head;
    if (p == NULL)
    {
        cout << "wrong! NULL List!!!" << endl;
        return 0;
    }
    while (1)
    {
        if (p == head && fir == 1)
            break;
        cout << p->data;
        if (p->next != head)
            cout << "->";
        else
            cout << endl;
        fir = 1;
        p = p->next;
    }
    return 1;
}
template <class ElemType>
void CirLinkList<ElemType>::ListDestroy()
{

}

template <class ElemType>
void Merge_Cur_Linklist( CirLinkList<ElemType> &A, CirLinkList<ElemType> &B )
{
    LinkNode<ElemType>* a1=A.getTail();
    LinkNode<ElemType>* a2=A.getHead();
    LinkNode<ElemType>* b1=B.getTail();
    LinkNode<ElemType>* b2=B.getHead();
    A.changeTail(b1);
    a1->next=b2;
    b1->next=a2;
    A.ListTraverse();
    return;
}
int main()
{
    int n;
    cin>>n;
    getchar();
    if(n!=0&&n!=1&&n!=2&&n!=3)
    {
        cout<<"err";
        exit(0);
    }
    string s1,s2;
    getline(cin,s1);
    getline(cin,s2);
    if(n==0)
    {
        CirLinkList<int> A,B;
        int cont1=0,cont2=0;
        int num1=0,num2=0;
        for (unsigned i=0; i<s1.size(); i++)
        {
            if (s1[i]==' ')
            {
                A.push_back(num1);
                num1=0;
            }
            else
            {
                num1=num1*10+s1[i]-'0';
            }
        }
        A.push_back(num1);
        for (unsigned i=0; i<s2.size(); i++)
        {
            if (s2[i]==' ')
            {
                B.push_back(num2);
                num2=0;
            }
            else
            {
                num2=num2*10+s2[i]-'0';
            }
        }
        B.push_back(num2);
        A.ListTraverse();
        B.ListTraverse();
        cout<<endl;
        Merge_Cur_Linklist(A,B);
    }
    if(n==1)
    {
        CirLinkList<double>C,D;
        double num1=0.0,sum1=0.0,num2=0.0,sum2=0.0;
        int judge1=0,t1=0,judge2=0,t2=0;
        for(unsigned i=0; i<s1.size(); i++)
        {
            if(s1[i]==' ')
            {
                num1=num1/pow(10,t1);
                C.push_back(num1);
                num1=0.0;
                judge1=0,t1=0;
            }
            else if(s1[i]=='.')
            {
                judge1=1;
            }
            else
            {
                num1=num1*10+s1[i]-'0';
                if(judge1==1)
                {
                    t1++;
                }
            }
        }
        num1=num1/pow(10,t1);
        C.push_back(num1);
        C.ListTraverse();
        for(unsigned i=0; i<s2.size(); i++)
        {
            if(s2[i]==' ')
            {
                num2=num2/pow(10,t2);
                D.push_back(num2);
                num2=0.0;
                judge2=0,t2=0;
            }
            else if(s2[i]=='.')
            {
                judge2=1;
            }
            else
            {
                num2=num2*10+s2[i]-'0';
                if(judge2==1)
                {
                    t2++;
                }
            }
        }
        num2=num2/pow(10,t2);
        D.push_back(num2);
        D.ListTraverse();
        cout<<endl;
        Merge_Cur_Linklist(C,D);
    }
    if(n==2)
    {
        char ch1,ch2;
        CirLinkList<char>A,B;
        for(unsigned i=0; i<s1.size(); i++)
        {
            ch1=s1[i];
            if(ch1!=' ')
            {
                A.push_back(ch1);
            }
        }
        A.ListTraverse();
        for(unsigned i=0; i<s2.size(); i++)
        {
            ch2=s2[i];
            if(ch2!=' ')
            {
                B.push_back(ch2);
            }
        }
        B.ListTraverse();
        cout<<endl;
        Merge_Cur_Linklist(A,B);
    }
    if(n==3)
    {
        string k1,k2;
        k1.clear();
        k2.clear();
        CirLinkList<string >A,B;
        for(unsigned i=0; i<s1.size(); i++)
        {
            if(s1[i]==' ')
            {
                A.push_back(k1);
                k1.clear();
            }
            else
            {
                k1+=s1[i];
            }
        }
        A.push_back(k1);
        A.ListTraverse();
        for(unsigned i=0; i<s2.size(); i++)
        {
            if(s2[i]==' ')
            {
                B.push_back(k2);
                k2.clear();
            }
            else
            {
                k2+=s2[i];
            }
        }
        B.push_back(k2);
        B.ListTraverse();
        cout<<endl;
        Merge_Cur_Linklist(A,B);
    }
    return 0;
}

内容总结

以上是互联网集市为您收集整理的6 循环链表ADT模板简单应用算法设计：循环链表的合并全部内容，希望文章能够帮你解决6 循环链表ADT模板简单应用算法设计：循环链表的合并所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/588795.html

来源：【匿名】

【上一篇】活动选择问题理解贪心算法【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【6 循环链表ADT模板简单应用算法设计：循环链表的合并】教程文章相关的互联网学习教程文章

8皇后以及N皇后算法探究，回溯算法的JAVA实现，非递归，循环控制及其优化【代码】【图】

上两篇博客8皇后以及N皇后算法探究，回溯算法的JAVA实现，递归方案8皇后以及N皇后算法探究，回溯算法的JAVA实现，非递归，数据结构“栈”实现研究了递归方法实现回溯，解决N皇后问题，下面我们来探讨一下非递归方案实验结果令人还是有些失望，原来非递归方案的性能并不比递归方案性能高代码如下：package com.newflypig.eightqueen;import java.util.Date;/*** 使用循环控制来实现回溯，解决N皇后* @author newflydd@189.cn* Time ...

三类基本查找算法（循环，二分，分块）

/******************************************************************** 循环查找，二分法查找，分块查找 (二叉查找树（二叉排序树），哈希表查找以后碰到时在做笔记) ********************************************************************///顺序查找 #include <stdio.h> int sequeceSearch(int* range,int length, int key) {for(int i=0; i<length; i++){if(range[i] == key)return i; //查找成功}return -1;//查找失败 } /...

C语言算法设计一个算法，将数组m个元素循环右移。要求算法空间复杂度为O(1)【代码】

题目如题：数组是一个常规一维数组，直接放代码，代码讲解见注解#include<stdio.h> void swap(int a[],int i,int j) {a[i]=a[i]+a[j]-(a[j]=a[i]); } void insert(int a[],int i,int n)//插入算法，每次把第i个数放到这个数组的最后面{int key=a[i];//插入算法的核心思想和插入排序当中是一样的，设定一个key，让key插入到最后面while(i<n){a[i]=a[i+1];++i;if(i+1==n)//当i处于数组最后一位的时候，停止循环break;}a[i]=key;//在数...

循环赛日程表（用来说明算法导论上的题目！！）【代码】

设有n=2k个选手参加比赛，要求设计一个满足一下要求的比赛日程表:（1）每个选手必须与其他的n-1个选手个比赛一次；（2）每个选手每天只能赛一次。按此要求可以把比赛日程表设计成一个n行n-1列的二维表，其中第i行第j列表示第i个选手在第j天比赛的选手。代码：（分治策略） 1 #include<stdio.h>2 #include<math.h>3 4void gametable(int k)5{6int a[100][100];7int n,temp,i,j,p,t;8 n=2;//k=0两个参赛选手日程可以直接求得...

数据结构与算法 1 :基本概念，线性表顺序结构，线性表链式结构，单向循环链表【代码】【图】

【本文谢绝转载】《大纲》数据结构：起源：基本概念数据结构指数据对象中数据元素之间的关系逻辑结构物理结构数据的运算算法概念：概念算法和数据结构区别算法特性算法效率的度量大O表示法时间复杂度案例空间复杂度时间换空间案例 1)线性表：线性表初步认识：线性表顺序结构案例线性表顺序结构案例，单文件版线性表的优缺点企业级线性表链式存储案例：C语言实现企业级线性表链式存储案例：C语言实现单文件版企业级线性表链式存...

数据结构与算法（四）-线性表之循环链表【代码】【图】

前言：前面几篇介绍了线性表的顺序和链式存储结构，其中链式存储结构为单向链表（即一个方向的有限长度、不循环的链表），对于单链表，由于每个节点只存储了向后的指针，到了尾部标识就停止了向后链的操作。也就是说只能向后走，如果走过了，就回不去了，还得重头开始遍历，所以就衍生出了循环链表一、简介　　定义：将单链表中中断结点的指针端有空指针改为指向头结点，就使整个单链表形成一个环，这种头尾详解的单链表称为单循环...

冒泡排序,swich语句,while循环...基础性的一道综合题初学者可以做一个简单的测试

这道题是没有什么太大的难度,但是是比较基础性的知识点的应用!对学习OC有一定的帮助.1. 创建一对文件Student.h Student.m2. 在Student.h中，定义一个Student结构体，成员变量包括：姓名、性别、年龄、学号、分数 3. 声明一个打印Student的函数。参数是结构体指针4. 声明一个打印数组中所有学生的函数5. 声明一个实现学生数组排序的函数，按照姓名升序6. 声明一个实现学生数组排序的函数，按照年龄降序7. 声明一个实现学生数组排序...

算法 - 堆栈类和嵌套循环实例运用【代码】

最近碰到两个算法题，觉得比较有代表性，特记录分享如下：题1：给定一个整形数字，求一串数字，这串数字需要满足相加等于这个给定的数字，且这串数字必须顺序排列。题2：有一个字符串，判断字符串内的括号(大括号，小括号，中括号，尖括号等等)是全闭合的，也就是说一个正括号后必须是相同括号类型的反括号，比如{{[]}}是合法的，({])是非法，括号中可夹杂数字，字母。开始拿到第一个题目，首先就想到了和冒泡算法有点类似，原理...

循环神经网络（RNN）模型与前向反向传播算法,LSTM模型笔记

循环神经网络（RNN）模型与前向反向传播算法,LSTM模型笔记输出和模型间有反馈的神经网络：循环神经网络（Recurrent Neural Networks），广泛用于自然语言处理中的语音识别、手写识别以及机器翻译等领域。特点：1.隐藏状态h由输入x和前一隐藏状态hi-1共同决定。2.模型的线性关系参数U、W、V矩阵在整个RNN网络中共享，从而体现了RNN模型的循环反馈思想。在语音识别、手写识别以及机器翻译等领域实际应用比较广泛的是基于RNN模型的LST...

PHP基于二分法实现数组查找功能示例【循环与递归算法】_php技巧【图】

这篇文章主要介绍了PHP基于二分法实现数组查找功能,结合实例形式分析了while循环与递归调用算法实现二分查找功能的相关实现技巧,需要的朋友可以参考下本文，本文实例讲述了PHP基于二分法实现数组查找功能。分享给大家供大家参考，具体如下：二分法。分别使用while循环的方法和递归调用的方法。<?php // 二分法的使用数组必须是有序的，或升序，或降序 $arr = array(1, 3, 5, 7, 9, 13 ); // 递归调用（相比较好理解 function bsear...

冒泡排序两个for循环分别有什么作用？能用最简单的话解释吗？

回复内容：本来想上个直观图：发现知乎不支持 gif 格式，给个链接吧http://upload.wikimedia.org/wikipedia/commons/3/37/Bubble_sort_animation.gif对于「冒泡排序」算法，核心是冒泡。如何冒泡？也就是说，把数组中最小的那个往上冒，冒的过程就是和他相邻的元素交换。这个冒的过程就是内循环。经过了一个冒的过程，可以使一个最小的元素冒出来，如果数组里面有 n 个元素，就得冒 n-1 次，这就是外循环。附我一篇博文：为什么说...

PHP实现字符串翻转功能的方法【递归与循环算法】【图】

本文实例讲述了PHP实现字符串翻转功能的方法。分享给大家供大家参考，具体如下：提到实现字符串反转的方法，大家都会想到用循环。确实，循环是一个内存占用量小且实现简单的方式。但是还有一种方式可以实现这样的功能，那就是递归。 php支持递归函数，递归函数就是函数调用自己本身。这些函数特别适用于动态浏览数据结构，例如连接列表和树。例子： <?php //递归实现字符串翻转 function reverse_r($str){if(strlen($str)>0){re...

PHP基于二分法实现数组查找功能示例【循环与递归算法】【图】

本文实例讲述了PHP基于二分法实现数组查找功能。分享给大家供大家参考，具体如下：二分法。分别使用while循环的方法和递归调用的方法。 <?php // 二分法的使用数组必须是有序的，或升序，或降序 $arr = array(1, 3, 5, 7, 9, 13 ); // 递归调用（相比较好理解 function bsearch_r($v, $arr, $low, $high){if ($low > $high) {// 先判断结束条件return -1;}$i = intval(($high + $low)/2);if ($arr[$i] > $v){return bsearch_r($v,...

JavaScript求一组数的最小公倍数和最大公约数常用算法详解【面向对象，回归迭代和循环】

本文实例讲述了JavaScript求一组数的最小公倍数和最大公约数常用算法。分享给大家供大家参考，具体如下：方法来自求多个数最小公倍数的一种变换算法（详见附录说明）最小公倍数的算法由最大公约数转化而来。最大公约数可通过如下步骤求得：（1）找到a1,a2,..,an中的最小非零项aj，若有多个最小非零项则任取一个（2） aj以外的所有其他非0项ak用ak mod aj代替；若没有除aj以外的其他非0项，则转到（4）（3）转到（1）（4） ...