[cpp]
/**a. 編寫文件LinkNode.h和Linklist.h，定義單鏈表類模板Linklist，以及其上的TailInsert、遍歷及初始化等操作。
b. 利用帶頭結點的單鏈表結構，在Linklist.h文件中添加兩個成員函數:
(1) Delete(Linklist<int> &L)用於實現單鏈表中重復元素的刪除；
(2) Reverse(Linklist<int> &L)用於實現單鏈表的就地逆置（即在原表的存儲空間實現元素的逆置）。
編寫算法Print（const int &）用於實現數據元素的輸出。
*/ www.2cto.com
#include<iostream>
#include"LinkList.h"
using namespace std;
void print(const int& e)
{
cout<<e<<" ";
}
int main()
{
LinkList<int> lt;
int array[12] = {2,3,3,4,5,5,7,8,8,9,10,23};
for(int i = 0;i <= 11;i++)
{
cout<<array[i]<<" ";
lt.Append(array[i]);
}
cout<<endl;
lt.Reverse();
lt.Traverse(print);
cout<<endl;
lt.Delete();
lt.Traverse(print);
return 0;
}
/***************頭文件***************/
#include<iostream>
template<class T>
struct LinkNode
{
T data;
LinkNode<T> *next;
};
template<class T>
class LinkList
{
public:
LinkList();
LinkList(const LinkList<T>&);
~LinkList();
bool IsEmpty()const{return len<=0;}
int Length()const{return len;}
void Clear();
bool GetElem(T&,int)const;
bool SetElem(const T&,int);
int LocateElem(const T&)const;
int LocatePrior(const T&)const;
int LocateNext(const T&)const;
bool Insert(const T&,int);
bool Append(const T&);
bool Delete(T&,int);
void Traverse(void(*visit)(const T&))const;
LinkList<T>& operator=(const LinkList<T>&);
void Delete();
void Reverse();
private:
int len;
LinkNode<T> *head;
LinkNode<T> *tail;
void CopyFrom(const LinkList<T>&);
};
using namespace std;
template<class T>
LinkList<T>::LinkList()//默認構造函數
{
len=0;
head=tail=new LinkNode<T>;
head->next=NULL;
}
template<class T>
LinkList<T>::LinkList(const LinkList<T>& r)//拷貝構造函數
{
CopyFrom(r);
}
template<class T>
LinkList<T>::~LinkList()//析構函數
{
Clear();
delete head;
}
template<class T>
void LinkList<T>::Clear()//清空鏈表
{
LinkNode<T>* p=head->next,*q;
while(p)
{
q=p->next;
delete p;
p=q;
}
tail=head;
head->next=NULL;
len=0;
}
template<class T>
bool LinkList<T>::GetElem(T&e,int i)const//獲得第i位的元素
{
if(i<1 || i>len)
return false;
LinkNode<T> *p=head->next;
int k=1;
while(k<i)
{
p=p->next;
k++;
}
e=p->data;
return true;
}
template<class T>
bool LinkList<T>::SetElem(const T&e,int i)//設置第i位置的元素為e
{
if(i<1 || i>len)
return false;
LinkNode<T> *p=head->next;
int k=1;
while(k<i)
{
p=p->next;
k++;
}
p->data=e;
return true;
}
template<class T>
int LinkList<T>::LocateElem(const T&e)const
{
int i=1;
LinkNode<T> *p=head->next;
while(p && p->data!=e)
{
i++;
p=p->next;
}
if(p)
return i;
return 0;
}
template<class T>
int LinkList<T>::LocatePrior(const T&e)const
{
int i=LocateElem(e);
if(i>1)
return i-1;
else
return 0;
}
template<class T>
int LinkList<T>::LocateNext(const T&e)const
{
int i=LocateElem(e);
if(i>=1 && i<len)
return i+1;
else
return 0;
}
template<class T>
bool LinkList<T>::Insert(const T&e,int i)
{
LinkNode<T> *p,*q;
int k=1;
if(i<1 || i>len+1)
return false;
q=new LinkNode<T>;
q->data=e;
p=head;
while(k<i)
{
p=p->next;
k++;
}
q->next=p->next;
p->next=q;
if(i==len+1) //表尾插入後修改尾指針
tail=q;
++len;
return true;
}
template<class T>
bool LinkList<T>::Append(const T&e) //畫圖分析
{
LinkNode<T> *q;
q=new LinkNode<T>;
q->data=e;
tail->next=q;
tail=q; //漏了一句，要自己寫，弄清原理
tail->next=NULL;
++len;
return true;
}
template<class T>
bool LinkList<T>::Delete(T&e,int i)
{
if(i<1 || i>len)
return false;
LinkNode<T> *p,*q;
int k=1;
p=head;
while(k<i)
{
p=p->next;
k++;
}
q=p->next;
p->next=q->next;
if(q==tail)
tail=q;
e=q->data;
delete q;
--len;
return true;
}
template<class T>
void LinkList<T>::Traverse(void (*visit)(const T&e))const
{
LinkNode<T>*p=head->next;
while(p)
{
visit(p->data);
p=p->next;
}
}
template<class T>
LinkList<T>& LinkList<T>::operator=(const LinkList<T>&r)
{
Clear();
delete head;
CopyFrom(r);
return *this;
}
template<class T>
void LinkList<T>::CopyFrom(const LinkList<T>& r)
{
len=0;
head=tail=new LinkNode<T>;
head->next=NULL;
LinkNode<T> *p=r.head->next;
while(p)
{
Append(p->data);
p=p->next;
}
}
template <class ElemType>
void LinkList<ElemType>::Delete()
{
LinkNode<ElemType> *r,*t,*y,*q;
for(r = head;r != NULL;r = r->next)
{
q = r;
for(t = r->next;t!=NULL;t = t->next)
{
if(r->data < t -> data)
break;
if(r->data == t -> data)
{
q ->next = t->next;
}
else{
q = q ->next;
}
}
}
}
template <class ElemType>
void LinkList<ElemType>::Reverse()
{
int temp;
LinkNode<ElemType> *p = head->next,*q = head;
for(int i =0 ;i < len/2;i++)
{
for(int j = 0;j < len-i;j++)
{
q = q->next;
}
temp = q->data;
q->data = p -> data;
p->data = temp;
q = head;
p = p->next;
}
}
