Java教程
6 循环链表ADT模板简单应用算法设计：循环链表的合并
问题描述：
目的：使用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;
}
-
初学者必备：订单系统资料详解与实操教程12-25
-
内网穿透资料入门教程12-24
-
微服务资料入门指南12-24
-
微信支付系统资料入门教程12-24
-
微信支付资料详解：新手入门指南12-24
-
Hbase资料：新手入门教程12-24
-
Java部署资料12-24
-
Java订单系统资料：新手入门教程12-24
-
Java分布式资料入门教程12-24
-
Java监控系统资料详解与入门教程12-24
-
Java就业项目资料：新手入门必备教程12-24
-
Java全端资料入门教程12-24
-
Java日志系统资料详解：新手入门指南12-24
-
Java微服务系统资料：入门与初级应用指南12-24
-
Java小程序资料：入门教程与实战技巧12-24
