問題描述 :
目的：使用C++模闆設計單連結清單的抽象資料類型（ADT）。并在此基礎上，使用單連結清單ADT的基本操作，設計并實作單連結清單的簡單算法設計。
内容：
（1）請使用模闆設計單連結清單的抽象資料類型。（由于該環境目前僅支援單檔案的編譯，故将所有内容都集中在一個源檔案内。在實際的設計中，推薦将抽象類及對應的派生類分别放在單獨的頭檔案中。參考網盤中的ADT原型檔案。）
（2）ADT的簡單應用：使用該ADT設計并實作單連結清單應用場合的一些簡單算法設計。
應用6：假設2個線性表分别由單連結清單A和B存儲，其中資料元素按值非遞減有序排列（即已經有序），現要求設計一個算法，将A和B歸并為一個線性表 , 其資料元素仍按值非遞減排列，且表中不存在值相同的元素。要求使用A和B的原存儲空間，且B不再單獨存在。
參考函數原型：
template<class ElemType>
void Merge_L_Pure_Order( LinkList<ElemType> &A, LinkList<ElemType> &B );
輸入說明 :
第一行：有序單連結清單A的資料元素（資料元素之間以空格分隔）
第二行：有序單連結清單B的資料元素（資料元素之間以空格分隔）
輸出說明 :
如第一行輸入值為0、1、2、3之外的值，直接輸出“err”
否則：
第一行：單連結清單A的周遊結果
第二行：單連結清單B的周遊結果
空行
第四行：歸并+提純後單連結清單A的周遊結果
輸入範例 :
3 3 5 5 8 8 11 11
2 2 6 8 8 9 11
輸出範例 :
3->3->5->5->8->8->11->11
2->2->6->8->8->9->11
2->3->5->6->8->9->11
解題代碼：
#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>
using namespace std;
//單連結清單ADT
/* 單連結清單的結點定義 */
template<class ElemType>
struct LinkNode
{
ElemType data;//元素
LinkNode<ElemType>* next;//next指針
LinkNode(LinkNode<ElemType>* ptr = NULL)
{
//建立節點的時候可以傳入next指針
next = ptr;
}
LinkNode(const ElemType& item, LinkNode<ElemType>* ptr = NULL)
{
//建立節點的時候可以傳入一個元素或者：元素+next指針。
next = ptr;
data = item;
}
};
//帶頭結點的單連結清單
template<class ElemType>
class LinkList
{
private:
LinkNode<ElemType>* head; // 頭指針
LinkNode<ElemType>* tail; // 尾指針
void empty_push(ElemType num)//空連結清單插入第一個節點
{
head = new LinkNode<ElemType>;//頭指針指向建立節點
tail = head;//尾指針指向頭指針
head->data = num;//指派
//head->next = NULL;
return;
}
bool check_P(int n)//檢查下标是否合法：0-n
{
if (0 <= n && n < size())
return true;
return false;
}
public:
/*
int size(void)擷取長度
LinkNode<ElemType>* get_address(int i)//擷取指定下标的位址
void have_look(void) //輸出
void push_back(ElemType num) //尾部插入
void insert_head(ElemType num) 頭部插入
bool insert_back(int place, ElemType num) 插入到指定位置之後
*/
LinkList()
{
//無參數的構造函數
//head = new LinkNode<ElemType>;//頭指針指向建立節點
//tail = head;//尾指針指向頭指針
head = NULL;
tail = NULL;
}
LinkList(const ElemType& item)
{
//帶參數的構造函數 我覺得沒幾個人會用吧
head = new LinkNode<ElemType>(item);
tail = head;
}
LinkList(LinkList<ElemType>& List)
{
//拷貝構造函數
;
}
~LinkList()
{
//析構函數
}
LinkNode<ElemType>* get_address(int i)//擷取指定下标的位址
{
LinkNode<ElemType>* pla=head;
while (i--)
{
pla = pla->next;
}
return pla;
}
void have_look(void)
{
LinkNode<ElemType>* p = head;
while (p->next!= NULL)
{
cout << p->data;
cout << "->";
p = p->next;
}
cout << p->data << endl;
return;
}
int size(void)//finish 傳回數組的長度
{
int len = 0;
if (head == NULL && tail == NULL)
return 0;
LinkNode<ElemType>* p;
p = head;
while (p != NULL)
{
len++;
p = p->next;
}
return len;
}
void push_back(ElemType num)
{
if (size()==0)//空連結清單特判
{
empty_push(num);
return;
}
LinkNode<ElemType>* p = new LinkNode<ElemType>;//建立節點
p->data = num;//指派
tail->next = p;//尾指針指向節點next指派為p
tail = p;//尾指針指向p
return;
}
void insert_head(ElemType num)
{
if (size() == 0)//空連結清單特判
{
empty_push(num);
return;
}
LinkNode<ElemType>* p = new LinkNode<ElemType>;//建立節點
p->data = num;//指派
p->next = head;//連結
head = p;
return;
}
bool insert_back(int place, ElemType num)
{
if (size() == 0 && place==0)//空連結清單特判
{
empty_push(num);
return true;
}
if (check_P(place) == false)//位置合法性判斷
return false;
if (place == size() - 1)//尾部插入特判
{
push_back(num);
return true;
}
LinkNode<ElemType>* p=get_address(place);
LinkNode<ElemType>* p2 = new LinkNode<ElemType>;//建立
p2->data = num;//指派
p2->next = p->next;//定位
p->next = p2;//連結
return true;
}
LinkNode<ElemType>* get_front(LinkNode<ElemType>* p)//擷取一個指針的上一個，頭指針和非法指針會報錯.
{
LinkNode<ElemType>* p1;
p1 = head;
while (p1->next != NULL)
{
if (p1->next == p)
return p1;
p1=p1->next;
}
}
bool del(int i)//删除指定位置元素 。注意，沒有寫非法請求檢查（0->n-1）
{
return del_p(get_address(i));
}
bool del_p(LinkNode<ElemType>* p)
{
if (size() == 0)
return false;
if (head == tail)
{
if (p == head)
{
delete head;
head = NULL;
tail = NULL;
return true;
}
else
return false;
}
if (p == head)
{
LinkNode<ElemType>* p1 = head->next;
delete head;
head = p1;
return true;
}
if (p == tail)
{
LinkNode<ElemType>* p1 = get_front(p);
delete p;
p1->next=NULL;
tail = p1;
return true;
}
LinkNode<ElemType>* p1 = get_front(p);
p1->next = p->next;
delete p;
return true;
}
ElemType at(int i)
{
LinkNode<ElemType>* p=get_address(i);
return p->data;
}
void reverse(int m, int n)//反轉m->n區間
{
m++, n++;
LinkNode<ElemType>* newHead = new LinkNode<ElemType>;
newHead->next = head;
LinkNode<ElemType>* p = newHead;
for (int i = 0; i < m - 1; i++)
p = p->next;
LinkNode<ElemType>* start = p->next;
LinkNode<ElemType>* t = start->next;
if (n == size())
{
tail = start;
}
for (int i = m; i < n; i++)
{
start->next = t->next;
t->next = p->next;
p->next = t;
t = start->next;
}
head = newHead->next;
return;
}
LinkList<ElemType>* get_head(void)
{
return head;
}
LinkList<ElemType>* get_tail(void)
{
return head;
}
void pick(LinkList<ElemType> &lis)
{
tail->next=lis.head;
tail = lis.tail;
return;
}
};
//LinkList<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_L_Order(LinkList<ElemType>& A, LinkList<ElemType>& B)
{
int i=0, j=0;
LinkList<ElemType> c;
while (i < A.size())
{
while (j < B.size() && B.at(j) <= A.at(i) )
{
c.push_back(B.at(j));
j++;
}
c.push_back(A.at(i));
i++;
}
while (j < B.size())
{
c.push_back(B.at(j));
j++;
}
for (i = 0; i < c.size()-1;)
{
if (c.at(i) == c.at(i + 1))
c.del(i);
else
i++;
}
c.have_look();
}
//===================================================
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;
LinkList<int> LI_1, LI_2;
LinkList<double> LD_1, LD_2;
LinkList<char> LC_1, LC_2;
LinkList<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.have_look();
if (kinds == 1)
LD_1.have_look();
if (kinds == 2)
LC_1.have_look();
if (kinds == 3)
LS_1.have_look();
//--------------
if (kinds == 0)
LI_2.have_look();
if (kinds == 1)
LD_2.have_look();
if (kinds == 2)
LC_2.have_look();
if (kinds == 3)
LS_2.have_look();
//--------------
cout << endl;
//+++++++++++++++++++++++++
if (kinds == 0)
Merge_L_Order(LI_1, LI_2);
if (kinds == 1)
Merge_L_Order(LD_1, LD_2);
if (kinds == 2)
Merge_L_Order(LC_1, LC_2);
if (kinds == 3)
Merge_L_Order(LS_1, LS_2);
return 0;
}
//===============================================================