問題描述：
目的：使用C++模闆設計單連結清單的抽象資料類型（ADT）。并在此基礎上，使用單連結清單ADT的基本操作，設計并實作單連結清單的簡單算法設計。
内容：（1）請使用模闆設計單連結清單的抽象資料類型。（由于該環境目前僅支援單檔案的編譯，故将所有内容都集中在一個源檔案内。在實際的設計中，推薦将抽象類及對應的派生類分别放在單獨的頭檔案中。參考網盤中的ADT原型檔案。）
（2）ADT的簡單應用：使用該ADT設計并實作單連結清單應用場合的一些簡單算法設計。
應用1：假設有一個帶頭結點的單連結清單A，現要求設計一個算法，實作單連結清單的就地逆置，即利用原表的存儲空間實作表中前m 個元素和後n 個元素的互換。
參考函數原型：
template
void Exchange_L( LinkList &L, int m );
單連結清單ADT原型如下：
template
struct LinkNode
{
ElemType data;
LinkNode *next;
LinkNode(LinkNode *ptr = NULL){next = ptr;}
LinkNode(const ElemType &item, LinkNode *ptr = NULL)
//函數參數表中的形參允許有預設值，但是帶預設值的參數需要放後面
{
next = ptr;
data = item;
}
};
//帶頭結點的單連結清單
template
class LinkList:public link
{
private:
LinkNode head; // 頭指針
LinkNode tail; // 尾指針
public:
//無參數的構造函數
LinkList(){head = new LinkNode; tail =head;}
//帶參數的構造函數
LinkList(const ElemType &item){head = new LinkNode(item); tail = head;}
//拷貝構造函數
LinkList(LinkList &List);
//析構函數
~LinkList(){ListDestroy();}
//重載函數:指派
LinkList& operator=(LinkList &List);
//銷毀連結清單
void ListDestroy();
//清空連結清單
void ListClear();
//傳回連結清單的長度
int ListLength() const;
//判斷連結清單是否為空表
bool ListEmpty() const;
//在首結點之前插入一個結點
bool InsFirst( ElemType &e );
//在尾結點之前插入一個結點
bool InsTail( ElemType &e );
//擷取連結清單頭指針
LinkNode GetHead() const{ return head;}
//擷取連結清單尾指針
LinkNode GetTail() const{ return tail;}
//設定連結清單頭指針
void SetHead(LinkNode *p){ head = p;}
//設定連結清單尾指針
void SetTail(LinkNode *p){ tail = p;}
//用e傳回連結清單的第i個元素
ElemType GetElem(int pos);
//在連結清單的第pos個位置之前插入e元素
bool ListInsert(int pos,ElemType e);
//删除連結清單的首結點
//bool DelFirst( ElemType &e);
//表頭插入法動态生成連結清單
void CreateList_Head(vector &A);
//表尾插入法動态生成連結清單
void CreateList_Tail(vector &A);
//删除連結清單的第pos個位置的元素
ElemType ListDelete(int pos);
//compare函數，用來判斷a和b是否相等
//bool compare(ElemType a, ElemType *b);
//按指定條件查找，傳回指向第一個符合條件（=e）的元素的指針
bool LocateElem(const ElemType &e, LinkNode *pos);
//傳回連結清單給定資料元素的前驅資料元素的值
//bool PriorElem(ElemType cur_e, ElemType &pri_e);
//傳回連結清單給定資料元素的後繼資料元素的值
bool NextElem(LinkNode *p, ElemType &e);
//周遊連結清單
bool ListTraverse() const;
};
輸入說明：
第一行：順序表A的資料元素的資料類型标記（0：int，1：double，2：char，3：string）
第二行：待逆置單連結清單的資料元素（資料元素之間以空格分隔）
第三行：逆置位置m
輸出說明：
如第一行輸入值為0、1、2、3之外的值，直接輸出“err”
否則：
第一行：待逆置單連結清單的周遊結果（資料元素之間以"->“分隔）
空行
第三行：逆置後單連結清單的周遊結果（資料元素之間以”->"分隔）
SAMPLE INPUT：
13 5 27 9 32 123 76 98 54 87
5
SAMPLEOUTPUT：
13->5->27->9->32->123->76->98->54->87 /n 123->76->98->54->87->13->5->27->9->32
思路：
<font color
很令人絕望的題幹，主要是學會怎麼用adt的模闆進行操作。各個函數的代碼實作可以借鑒(https://blog.csdn.net/Blackoutdragon/article/details/109118889)，對于這道題來說，需要進行的操作是将先确定要互換的位置，注意當交換前後兩段連結清單的時候，修改做不索引的同時，不要忘記了修改置換之後的尾指針
基本的思路就是切斷，然後重新連接配接。總的來說需要找到四個結點，因為總共就兩處斷點。（這道題做的迷迷糊糊的，有什麼不懂的可以一起讨論讨論，有寫的不對的地方也請多多指教）
AC代碼：
#include<bits/stdc++.h>
using namespace std;
int no,i;
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;
}
};
template<class ElemType>
class LinkList
{
private:
LinkNode<ElemType> *head;
public:
LinkList()
{
head = new LinkNode<ElemType>;
}
LinkList(const ElemType &item)
{
head = new LinkNode<ElemType>(item);
}
LinkList(LinkList<ElemType> &List);
~LinkList()
{
ListDestroy();
}
LinkList<ElemType>& operator=(LinkList<ElemType> &List);
void ListDestroy();
void ListClear();
int ListLength() const;
bool ListEmpty() const;
bool InsFirst( ElemType e );
LinkNode<ElemType>* GetHead() const
{
return head;
}
void SetHead(LinkNode<ElemType> *p)
{
*head = *p;
}
ElemType GetElem(int pos);
bool ListInsert(int pos,ElemType e);
bool DelFirst( ElemType &e);
void CreateList_Head(int n, ElemType *A);
void CreateList_Tail(int n, ElemType *A);
void CreateList_Tail1(int n, double *A);
ElemType ListDelete(int pos);
bool LocateElem(const ElemType &e, LinkNode<ElemType> *pos);
bool PriorElem(ElemType cur_e, ElemType &pri_e);
bool NextElem(LinkNode<ElemType> *p, ElemType &e);
void ListTraverse() ;
LinkNode<ElemType> *getIndex(int times);
LinkNode<ElemType> *getTail();
};
template <class ElemType>
LinkList<ElemType>::LinkList(LinkList<ElemType> &List)
{
LinkNode<ElemType> *temp = List.head;
head = new LinkNode<ElemType>(*temp);
LinkNode<ElemType> *temp2 = head;
while(temp)
{
temp2->next = new LinkNode<ElemType>(*temp->next);
temp = temp->next;
temp2 = temp2->next;
}
}
template<class ElemType>
LinkList<ElemType>& LinkList<ElemType>::operator=(LinkList<ElemType> &List)
{
if(!head)
{
this = LinkList(List);
}
else
{
LinkNode<ElemType> *temp1 = List->head;
LinkNode<ElemType> *temp2 = head;
while(temp1 && temp2)
{
*temp1 = *temp2;
temp1 = temp1->next;
temp2 = temp2->next;
}
if(temp1)
{
while(temp1)
{
temp2 = new ElemType(*temp1);
temp1 = temp1->next;
temp2 = temp2->next;
}
return *this;
}
if(temp2)
{
LinkNode<ElemType> temp3 = temp2->next;
while(temp2)
{
temp3 = temp2->next;
delete temp2;
temp2 = temp3;
}
return *this;
}
}
}
template<class ElemType>
void LinkList<ElemType>::ListDestroy()
{
LinkNode<ElemType> *temp = NULL;
while(head)
{
temp = head->next;
delete head;
head = temp;
}
}
template<class ElemType>
void LinkList<ElemType>::ListClear()
{
LinkNode<ElemType> *temp = head->next;
LinkNode<ElemType> *temp2 = NULL;
while(temp)
{
temp2 = temp->next;
delete temp;
temp = temp2;
}
head->next = NULL;
}
template<class ElemType>
int LinkList<ElemType>::ListLength() const
{
int length = 0;
LinkNode<ElemType> *temp = head->next;
while(temp)
{
length ++;
temp = temp->next;
}
return length;
}
template<class ElemType>
bool LinkList<ElemType>::ListEmpty() const
{
if(head->next)
{
return false;
}
else
{
return true;
}
}
template<class ElemType>
bool LinkList<ElemType>::InsFirst(ElemType e)
{
LinkNode<ElemType> *temp = new LinkNode<ElemType>(e);
if(!temp)
{
return false;
}
temp->next = head->next;
head->next = temp;
cout<<endl;
return true;
}
template<class ElemType>
ElemType LinkList<ElemType>::GetElem(int pos)
{
LinkNode<ElemType> *temp = head;
int index = 0;
while(temp && index < pos)
{
temp = temp->next;
index ++;
}
if(!temp || index < pos-1)
{
cout<<"the index of the element you want is wrong"<<endl;
return;
}
return temp->data;
}
template<class ElemType>
bool LinkList<ElemType>::ListInsert(int pos,ElemType e)
{
LinkNode<ElemType> *temp = head;
int index = 0;
while(temp && index < pos - 1)
{
temp = temp->next;
index ++;
}
if(!temp || index < pos-1)
{
cout<<"the index of the element you want is wrong"<<endl;
return false;
}
LinkNode<ElemType> *temp2 = new LinkNode<ElemType>();
temp2->data = e;
temp2->next = temp->next;
temp->next = temp2;
}
template<class ElemType>
bool LinkList<ElemType>::DelFirst(ElemType &e)
{
LinkNode<ElemType> *temp = head->next;
e = temp->data;
if(!temp) return false;
head->next = temp->next;
delete temp;
return true;
}
template<class ElemType>
void LinkList<ElemType>::CreateList_Head(int n,ElemType *A)
{
ElemType *temp = NULL;
for(int i = 0; i < n; i ++)
{
temp = A + i;
InsFirst(*temp);
}
}
template<class ElemType>
void LinkList<ElemType>::CreateList_Tail(int n,ElemType *A)
{
LinkNode<ElemType> *temp=head;
int length = ListLength(),cont = 0;
while(temp && cont < length)
{
temp = temp->next;
cont++;
}
LinkNode<ElemType> *temp2 = temp;
if(!temp || cont<length)
{
return;
}
for(int i = 0; i < n; i ++)
{
temp->next = new LinkNode<ElemType>(*(A+i));
temp = temp->next;
}
}
template<class ElemType>
ElemType LinkList<ElemType>::ListDelete(int pos)
{
LinkNode<ElemType> *temp = head;
int i = 0;
while(temp && i < pos - 1)
{
temp = temp->next;
i ++;
}
if(!temp || i < pos - 1)
{
cout<<"the position you input is invalid"<<endl;
return ElemType();
}
LinkNode<ElemType> *temp2 = NULL;
temp2 = temp->next;
temp->next = temp2->next;
ElemType result = temp2->data;
delete temp2;
return result;
}
template<class ElemType>
bool LinkList<ElemType>::LocateElem(const ElemType &e, LinkNode<ElemType> *pos)
{
LinkNode<ElemType> *temp = head;
while(temp)
{
if(temp->data == e)
{
pos->data = temp->data;
pos->next = temp->next;
return true;
}
temp = temp->next;
}
return false;
}
template<class ElemType>
bool LinkList<ElemType>::PriorElem(ElemType cur_e, ElemType &pri_e)
{
LinkNode<ElemType> *temp = head;
while(temp->next)
{
if(temp->next->data == cur_e)
{
pri_e = temp->data;
return true;
}
temp = temp->next;
}
return false;
}
template<class ElemType>
bool LinkList<ElemType>::NextElem(LinkNode<ElemType> *p, ElemType &e)
{
if(LocateElem(e,p))
{
p = p->next;
return true;
}
else
{
return false;
}
}
template<class ElemType>
void LinkList<ElemType>::ListTraverse()
{
LinkNode<ElemType>*temp=head->next;
while(temp)
{
cout<<temp->data;
temp=temp->next;
if(temp)
cout<<"->";
}
cout<<endl;
}
template<class ElemType>
LinkNode<ElemType> *LinkList<ElemType>::getTail()
{
LinkNode<ElemType> *temp = head;
while(temp->next)
{
temp = temp->next;
}
return temp;
}
template<class ElemType>
LinkNode<ElemType> *LinkList<ElemType>::getIndex(int times)
{
LinkNode<ElemType> *temp=head;
while(times--)
{
temp=temp->next;
}
return temp;
}
template<class ElemType>
void Lk_Reverse( LinkList<ElemType>&L,int m)
{
L.ListTraverse();
cout<<endl;
if(m==i)
{
LinkNode<ElemType> *finalNode = L.getTail();
LinkNode<ElemType> *endTrue = finalNode;
LinkNode<ElemType> *temp = NULL;
LinkNode<ElemType> *temp2 = NULL;
while(L.GetHead()->next != finalNode)
{
temp=L.GetHead()->next;
L.GetHead()->next=temp->next;
temp2=finalNode->next;
finalNode->next=temp;
temp->next=temp2;
}
L.ListTraverse();
exit(0);
}
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;
L.ListTraverse();
}
int main()
{
int n;
cin>>n;
getchar();
if(n!=0&&n!=1&&n!=2&&n!=3)
{
cout<<"err";
exit(0);
}
string s;
i=0;
getline(cin,s);
if(n==0)
{
int temp[100005];
long long num=0;
for (unsigned j=0; j<s.size(); j++)
{
if (s[j]==' ')
{
temp[i]=num;
i++;
num=0;
}
else
{
num=num*10+s[j]-'0';
}
}
temp[i++]=num;
cin>>no;
LinkList<int> A;
A.CreateList_Tail(i,temp);
Lk_Reverse(A,no);
}
if(n==1)
{
double b[10005];
double num=0.0,sum=0.0;
int judge=0,t=0,j=0;
for(unsigned i=0; i<s.size(); i++)
{
if(s[i]==' ')
{
num=num/pow(10,t);
b[j++]=num;
num=0.0;
judge=0,t=0;
}
else if(s[i]=='.')
{
judge=1;
}
else
{
num=num*10+s[i]-'0';
if(judge==1)
{
t++;
}
}
}
num=num/pow(10,t);
b[j++]=num;
cin>>no;
LinkList<double> A;
A.CreateList_Tail(j,b);
Lk_Reverse(A,no);
}
if(n==2)
{
char c[10005];
char ch;
int j=0;
for(unsigned i=0; i<s.size(); i++)
{
ch=s[i];
if(ch!=' ')
{
c[j++]=ch;
}
}
cin>>no;
LinkList<char> A;
A.CreateList_Tail(j,c);
Lk_Reverse(A,no);
}
if(n==3)
{
string d[10005];
string k;
k.clear();
int j=0;
for(unsigned i=0;i<s.size();i++)
{
if(s[i]==' ')
{
d[j]=k;
j++;
k.clear();
}
else
{
k+=s[i];
}
}
d[j++]=k;
cin>>no;
LinkList<string> A;
A.CreateList_Tail(j,d);
Lk_Reverse(A,no);
}
return 0;
}