問題描述 :
目的：使用C++模闆設計循環連結清單的抽象資料類型（ADT）。并在此基礎上，使用循環連結清單ADT的基本操作，設計并實作單連結清單的簡單算法設計。
内容：（1）請使用模闆設計循環連結清單的抽象資料類型。（由于該環境目前僅支援單檔案的編譯，故将所有内容都集中在一個源檔案内。在實際的設計中，推薦将抽象類及對應的派生類分别放在單獨的頭檔案中。參考網盤中的單連結清單ADT原型檔案，自行設計循環連結清單的ADT。）
（2）ADT的簡單應用：使用該ADT設計并實作循環連結清單應用場合的一些簡單算法設計。
應用1：假設2個線性表分别由帶頭結點的循環連結清單A和B存儲。現要求設計一個算法，将A和B歸并為一個線性表 。要求利用循環連結清單的特點，使用A和B的原存儲空間，且合并後B成為一空表。
參考函數原型：
template<class ElemType>
void Merge_Cur_Linklist( CirLinkList<ElemType> &A, CirLinkList<ElemType> &B );
循環連結清單模闆類原型參考如下：
template<class ElemType>
struct LinkNode
{
ElemType data;
LinkNode<ElemType> *next;
LinkNode(LinkNode<ElemType> *ptr = NULL){next = ptr;} //構造函數1，用于構造頭結點
LinkNode(const ElemType &item, LinkNode<ElemType> *ptr = NULL) //構造函數2，用于構造其他結點
//函數參數表中的形參允許有預設值，但是帶預設值的參數需要放後面
{
next = ptr;
data = item;
}
//int getNum(){ return number; } //取得結點的序号
ElemType getData(){ return data; } //取得結點的資料域的值
void SetLink( LinkNode<ElemType> *link ){ next = link; } //修改結點的next域
void SetLink( ElemType value ){ data = value; } //修改結點的next域
};
//帶頭結點的循環單連結清單
template<class ElemType>
class CirLinkList{
private:
LinkNode<ElemType> *head; // 頭結點
LinkNode<ElemType> *tail; // 尾結點
public:
//無參數的構造函數
CirLinkList(){head = new LinkNode<ElemType>; tail = head; head->next = head;}
//帶參數的構造函數
CirLinkList(const ElemType &item){head = new LinkNode<ElemType>(item); tail = head; head->next = head;}
//拷貝構造函數
CirLinkList(CirLinkList<ElemType> &List);
//析構函數
~CirLinkList(){ListDestroy();}
//銷毀連結清單
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;}
//在連結清單的第pos個位置之後插入e元素
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;
};
輸入說明 :
第一行：順序表A的資料元素的資料類型标記（0：int，1：double，2：char，3：string）
第二行：第一個循環連結清單的資料元素（元素與元素之間以空格分隔）
第三行：第二個循環連結清單的資料元素（元素與元素之間以空格分隔）
輸出說明 :
如第一行輸入值為0、1、2、3之外的值，直接輸出“err”
否則：
第一行：第一個循環連結清單的周遊結果
第二行：第二個循環連結清單的周遊結果
空行
第四行：合并後循環連結清單的周遊結果
輸入範例 :
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
13->5->27->9->32->123->76->98->54->87->1->3->7->8->11
解題代碼：
// 循環連結清單.cpp : 此檔案包含 "main" 函數。程式執行将在此處開始并結束。
//
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <sstream>
#include <stack>
#include <map>
#include <ctime>
#include <array>
#include <set>
#include <list>
using namespace std;
template<class ElemType>
struct LinkNode
{
ElemType data;
LinkNode<ElemType>* next;
LinkNode(LinkNode<ElemType>* ptr = NULL)
{
next = ptr; //構造函數1，用于構造頭結點
}
LinkNode(const ElemType& item, LinkNode<ElemType>* ptr = NULL)
{
//構造函數2，用于構造其他結點
//函數參數表中的形參允許有預設值，但是帶預設值的參數需要放後面
next = ptr;
data = item;
}
//int getNum(){ return number; } //取得結點的序号
ElemType getData()
{
return data; //取得結點的資料域的值
}
void SetLink(LinkNode<ElemType>* link)
{
next = link;
//修改結點的next域
}
void SetLink(ElemType value)
{
data = value;
//修改結點的next域
}
};
//帶頭結點的循環單連結清單
template<class ElemType>
class CirLinkList {
private:
LinkNode<ElemType>* head; // 頭結點
LinkNode<ElemType>* tail; // 尾結點
public:
//無參數的構造函數
CirLinkList()
{
head = NULL;
tail = NULL;
}
CirLinkList(CirLinkList<ElemType>& List);//拷貝構造函數
~CirLinkList()
{
//析構函數
del_clear();
}
void del(int n)
{
//删除連結清單指定元素
LinkNode<ElemType>* p = getPlace(n);
if (p == head && p == tail)
{
//only have one
//沒寫删除元素
head = NULL;
tail = NULL;
delete p;
return;
}
if (p == head)
{
LinkNode<ElemType>* p1 = head->next;
head = p1;
tail->next = head;
return;
}
if (p == tail)
{
LinkNode<ElemType>* p1 = getPlace(n - 1);
p1->next = head;
tail = p1;
return;
}
if (p != head && p != tail)
{
LinkNode<ElemType>* p1 = getPlace(n - 1);
p1->next = p->next;
return;
}
return;
}
void del_clear()
{
//釋放連結清單
return;
}
int size() const//ok
{
//傳回連結清單的長度
int cnt = 0;
LinkNode<ElemType>* p;
bool fir = 0;
p = head;
if (p == NULL)
{
return 0;
}
while (1)
{
if (p == head && fir == 1)
break;
//------------
//循環操作
cnt++;
//------------
fir = 1;
p = p->next;
}
return cnt;
}
bool empty() const//ok
{
//判斷連結清單是否為空表
if (size() == 0 || head == NULL)
{
return 0;
}
return 1;
}
LinkNode<ElemType>* getHead() //ok
{
//擷取循環連結清單頭結點
return head;
}
LinkNode<ElemType>* getTail() //ok
{
//擷取循環連結清單尾結點
return tail;
}
void changeTail(LinkNode<ElemType>*p)
{
tail = p;
return;
}
void changeHead(LinkNode<ElemType>*p)
{
head = p;
return;
}
LinkNode<ElemType>* getPlace(int n)
{
LinkNode<ElemType>* p;
p = head;
if (p == NULL)
{
cout << "wrong! NULL List!!!" << endl;
return NULL;
}
while (n--)
{
p = p->next;
}
return p;
}
ElemType getNum(int n)
{
LinkNode<ElemType>* p = getPlace(n);
return p->data;
}
bool Insert_next(int pos, ElemType num)
{
//在連結清單的第pos個位置之後插入num元素
}
bool InsFirst(ElemType num)//ok
{
//在首結點之前插入一個結點
if (head == NULL)
{
//空連結清單插入
head = new LinkNode<ElemType>;
head->data = num;
tail = head;
tail->next = head;
return 0;
}
LinkNode<ElemType>* p = new LinkNode<ElemType>;
p->next = head;
p->data = num;
head = p;
tail->next = head;
return 1;
}
void push_back(ElemType num)//ok
{
if (head == NULL)
{
//空連結清單插入
head = new LinkNode<ElemType>;
head->data = num;
tail = head;
tail->next = head;
return;
}
LinkNode<ElemType>* p = new LinkNode<ElemType>;
p->data = num;
p->next = head;
tail->next = p;
tail = p;
return;
}
bool ListTraverse() const//ok
{
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;
}
};
//CirLinkList<int> a;
//===============================================================
vector<int> departString_int(string data)
{
vector<int> back_part;//output type
int i, j;
vector<string> part;
string A_part;
stringstream room;
room.str(data);
while (room >> A_part)
part.push_back(A_part);
for (i = 0; i < part.size(); i++)
{
int num_cahe;
num_cahe = atoi(part[i].c_str());
back_part.push_back(num_cahe);
}
return back_part;
}
vector<double> departString_double(string data)
{
vector<double> back_part;//output type
int i, j;
vector<string> part;
string A_part;
stringstream room;
room.str(data);
while (room >> A_part)
part.push_back(A_part);
for (i = 0; i < part.size(); i++)
{
double num_cahe;
num_cahe = atof(part[i].c_str());
back_part.push_back(num_cahe);
}
return back_part;
}
vector<char> departString_char(string data)
{
vector<char> back_part;//output type
int i, j;
vector<string> part;
string A_part;
stringstream room;
room.str(data);
while (room >> A_part)
part.push_back(A_part);
for (i = 0; i < part.size(); i++)
{
char num_cahe;
num_cahe = part[i].at(0);
back_part.push_back(num_cahe);
}
return back_part;
}
vector<string> departString_string(string data)
{
vector<int> back_part;//output type
int i, j;
vector<string> part;
string A_part;
stringstream room;
room.str(data);
while (room >> A_part)
part.push_back(A_part);
return part;
}
//===================================================
template<class ElemType>
void Merge_Cur_Linklist(CirLinkList<ElemType>& A, CirLinkList<ElemType>& B)
{
LinkNode<ElemType>* at = A.getTail();
LinkNode<ElemType>* ah = A.getHead();
LinkNode<ElemType>* bt = B.getTail();
LinkNode<ElemType>* bh = B.getHead();
A.changeTail(bt);
at->next = bh;
bt->next = ah;
A.ListTraverse();
return;
}
//===================================================
int main()
{
int i, j;
int kinds;
string s1, s2;
int m;
//數值類型輸入判斷
cin >> kinds;
if (kinds != 0 && kinds != 1 && kinds != 2 && kinds != 3)
{
cout << "err" << endl;
return 0;
}
cin.get();
vector<int> I_1, I_2;
vector<double> D_1, D_2;
vector<char> C_1, C_2;
vector<string> S_1, S_2;
CirLinkList<int> LI_1, LI_2;
CirLinkList<double> LD_1, LD_2;
CirLinkList<char> LC_1, LC_2;
CirLinkList<string> LS_1, LS_2;
//---------------
getline(cin, s1);
if (kinds == 0)
I_1 = departString_int(s1);
if (kinds == 1)
D_1 = departString_double(s1);
if (kinds == 2)
C_1 = departString_char(s1);
if (kinds == 3)
S_1 = departString_string(s1);
//--------------
getline(cin, s2);
if (kinds == 0)
I_2 = departString_int(s2);
if (kinds == 1)
D_2 = departString_double(s2);
if (kinds == 2)
C_2 = departString_char(s2);
if (kinds == 3)
S_2 = departString_string(s2);
//--------------
if (kinds == 0)
{
for (i = 0; i < I_1.size(); i++)
LI_1.push_back(I_1[i]);
}
if (kinds == 1)
{
for (i = 0; i < D_1.size(); i++)
LD_1.push_back(D_1[i]);
}
if (kinds == 2)
{
for (i = 0; i < C_1.size(); i++)
LC_1.push_back(C_1[i]);
}
if (kinds == 3)
{
for (i = 0; i < S_1.size(); i++)
LS_1.push_back(S_1[i]);
}
//--------------
if (kinds == 0)
{
for (i = 0; i < I_2.size(); i++)
LI_2.push_back(I_2[i]);
}
if (kinds == 1)
{
for (i = 0; i < D_2.size(); i++)
LD_2.push_back(D_2[i]);
}
if (kinds == 2)
{
for (i = 0; i < C_2.size(); i++)
LC_2.push_back(C_2[i]);
}
if (kinds == 3)
{
for (i = 0; i < S_2.size(); i++)
LS_2.push_back(S_2[i]);
}
//--------------
if (kinds == 0)
LI_1.ListTraverse();
if (kinds == 1)
LD_1.ListTraverse();
if (kinds == 2)
LC_1.ListTraverse();
if (kinds == 3)
LS_1.ListTraverse();
//--------------
if (kinds == 0)
LI_2.ListTraverse();
if (kinds == 1)
LD_2.ListTraverse();
if (kinds == 2)
LC_2.ListTraverse();
if (kinds == 3)
LS_2.ListTraverse();
//--------------
cout << endl;
//+++++++++++++++++++++++++
if (kinds == 0)
Merge_Cur_Linklist(LI_1, LI_2);
if (kinds == 1)
Merge_Cur_Linklist(LD_1, LD_2);
if (kinds == 2)
Merge_Cur_Linklist(LC_1, LC_2);
if (kinds == 3)
Merge_Cur_Linklist(LS_1, LS_2);
return 0;
}