用C++设计一个单向链表类模板，可以定义多种数据类型。如整型、双精度、字符型、字符串型等。

Question

可以实现如下功能：
（1）链表节点的输入、输出；
（2）查找链表中某节点；
（3）删除指定节点；
（4）对链表节点排序；
（5）查找链表中最大、最小节点；
（6）对链表中的节点去重

Answer 1

DEV C++用下面版本
# include <iostream>
# include <string>

template <class T>
class List;

template <class T>
std::ostream &operator <<(std::ostream &os, const List<T> &lst);

template <class T>
class Node
{
private:
T Data;
Node<T> *Prev;
Node<T> *Next;
friend class List<T>;
friend std::ostream &operator << <T>(std::ostream &os, const List<T> &lst);
public:
Node(const T &Val):Data(Val), Prev(NULL), Next(NULL) {}
~Node()
{
if(Prev)
Prev = NULL;
if(Next)
Next = NULL;
}
};

template <class T>
class List
{
private:
Node<T> *Head;
Node<T> *Tail;
int Size;
void Destory(void) //销毁链表
{
while(Head)
this->pop_back();
}
static void swap(Node<T> *p1, Node<T> *p2) //交换节点的数据域
{
T Val = p1->Data;
p1->Data = p2->Data;
p2->Data = Val;
}
void BubbleSort(void) //冒泡排序（升序）
{
Node<T> *start;
Node<T> *end;
bool flag = true;
for(end = Tail; flag && end->Prev; end = end->Prev)
{
flag = false;
for(start = Head; start != end; start = start->Next)
{
if(start->Data > start->Next->Data)
{
flag = true;
swap(start, start->Next);
}
}
}
}
bool search(const T &Val) //查找指定元素，返回true或false
{
Node<T> *Temp = Head;
while(Temp)
{
if(Temp->Data == Val)
return true;
Temp = Temp->Next;
}
return false;
}
bool search(const T &Val) const //重载函数，用于const对象
{
Node<T> *Temp = Head;
while(Temp)
{
if(Temp->Data == Val)
return true;
Temp = Temp->Next;
}
return false;
}
friend std::ostream &operator << <T>(std::ostream &os, const List<T> &lst);
public:
List():Head(NULL), Tail(NULL), Size(0) {} //默认构造函数
List(const List<T> &lst):Head(NULL), Tail(NULL), Size(0) //复制构造函数
{
Node<T> *Temp = lst.Head;
while(Temp)
{
push_back(Temp->Data);
Temp = Temp->Next;
}
}
~List() //析构函数
{
Destory();
}
void push_back(const T &Val) //将数据插入链表尾部
{
Node<T> *Temp = new Node<T>(Val);
if(!Head)
Head = Tail = Temp;
else
{
Tail->Next = Temp;
Temp->Prev = Tail;
Tail = Temp;
}
++Size;
}
void pop_back(void) //弹出链表尾节点
{
if(Head)
{
if(Head != Tail)
{
Node<T> *Temp = Tail;
Tail = Tail->Prev;
delete Temp;
Tail->Next = Temp = NULL;
}
else
{
delete Head;
Head = Tail = NULL;
}
--Size;
}
}
int size(void) //返回链表中节点个数
{
return Size;
}
int size(void) const //重载函数，用于const对象
{
return Size;
}
void sort(void) //对链表排序
{
this->BubbleSort();
}
void erase(const T &Val) //删除指定节点
{
Node<T> *Temp = Head;
Node<T> *temp;
while(Temp)
{
if(Temp->Data == Val)
{
if(Temp->Prev)
{
temp = Temp;
temp->Prev->Next = temp->Next;
if(temp->Next)
temp->Next->Prev = temp->Prev;
else
Tail = temp->Prev;
Temp = temp->Next;
delete temp;
}
else
{
temp = Temp;
if(temp->Next)
temp->Next->Prev = NULL;
else
Tail = temp->Prev;
Head = Temp = temp->Next;
delete temp;
}
}
else
Temp = Temp->Next;
}
}
void find(const T &Val) //查找指定元素，有输出Yes，无输出"None"
{
std::cout<<"查找数据域为 "<<Val<<" 的节点：";
if(search(Val))
std::cout<<"Yes!"<<std::endl;
else
std::cout<<"None!"<<std::endl;
}
void find(const T &Val) const //重载函数，用于const对象
{
std::cout<<"查找数据域为 "<<Val<<" 的节点：";
if(search(Val))
std::cout<<"Yes!"<<std::endl;
else
std::cout<<"None!"<<std::endl;
}
void remove(void) //除去重复元素
{
List<T> lst;
Node<T> *Temp = Head;
while(Temp)
{
if(!lst.search(Temp->Data))
lst.push_back(Temp->Data);
Temp = Temp->Next;
}
*this = lst;
}
T maximum(void) //查找最大值，若空对象操作此函数则抛出异常
{
if(!Head)
throw 0;
List<T> lst(*this);
lst.sort();
return lst.Tail->Data;
}
const T maximum(void) const //重载函数，用于const对象
{
if(!Head)
throw 0;
List<T> lst(*this);
lst.sort();
return lst.Tail->Data;
}
T minimum(void) //查找最小值，若空对象操作此函数则抛出异常
{
if(!Head)
throw 0;
List<T> lst(*this);
lst.sort();
return lst.Head->Data;
}
const T minimum(void) const //重载函数，用于const对象
{
if(!Head)
throw 0;
List<T> lst(*this);
lst.sort();
return lst.Head->Data;
}
List<T> &operator =(const List &lst) //重载赋值运算符
{
if(Head)
this->Destory();
Node<T> *Temp = lst.Head;
while(Temp)
{
this->push_back(Temp->Data);
Temp = Temp->Next;
}
return *this;
}
};

template <class T>
std::ostream &operator <<(std::ostream &os, const List<T> &lst) //重载输出运算符
{
Node<T> *Temp = lst.Head;
while(Temp)
{
os<<Temp->Data;
if(Temp->Next)
os<<'\t';
Temp = Temp->Next;
}
return os;
}

int main(void)
{
List<int> lst;
lst.push_back(2); //push_back用于输入
lst.push_back(1);
lst.push_back(1);
lst.push_back(4);
lst.push_back(2);
std::cout<<lst<<std::endl;
lst.pop_back(); //pop_back用于弹出尾节点
std::cout<<lst<<std::endl;
lst.sort(); //sort用于排序
std::cout<<lst<<std::endl;
lst.remove(); //remove用于除去重复节点
std::cout<<lst<<std::endl;
lst.erase(1); //erase用于删除指定节点
std::cout<<lst<<std::endl;
lst.find(4); //find用于查找指定节点，有输出Yes，无输出None
lst.find(1);
std::cout<<lst.maximum()<<std::endl; //maximum返回最大节点的数据域
std::cout<<lst.minimum()<<std::endl; //minimum返回最小节点的数据域

return 0;
}

VC6.0用下面版本
# include <iostream>
# include <string>

template <class T>
class List;

template <class T>
class Node
{
private:
T Data;
Node<T> *Prev;
Node<T> *Next;
friend class List<T>;
friend std::ostream &operator <<(std::ostream &os, const List<T> &lst); //这一语句其实是错误的，但是VC6.0的BUG让我不得不这么写
public:
Node(const T &Val):Data(Val), Prev(NULL), Next(NULL) {}
~Node()
{
if(Prev)
Prev = NULL;
if(Next)
Next = NULL;
}
};

template <class T>
class List
{
private:
Node<T> *Head;
Node<T> *Tail;
int Size;
void Destory(void) //销毁链表
{
while(Head)
this->pop_back();
}
static void swap(Node<T> *p1, Node<T> *p2) //交换节点的数据域
{
T Val = p1->Data;
p1->Data = p2->Data;
p2->Data = Val;
}
void BubbleSort(void) //冒泡排序（升序）
{
Node<T> *start;
Node<T> *end;
bool flag = true;
for(end = Tail; flag && end->Prev; end = end->Prev)
{
flag = false;
for(start = Head; start != end; start = start->Next)
{
if(start->Data > start->Next->Data)
{
flag = true;
swap(start, start->Next);
}
}
}
}
bool search(const T &Val) //查找指定元素，返回true或false
{
Node<T> *Temp = Head;
while(Temp)
{
if(Temp->Data == Val)
return true;
Temp = Temp->Next;
}
return false;
}
bool search(const T &Val) const //重载函数，用于const对象
{
Node<T> *Temp = Head;
while(Temp)
{
if(Temp->Data == Val)
return true;
Temp = Temp->Next;
}
return false;
}
friend std::ostream &operator <<(std::ostream &os, const List<T> &lst);
public:
List():Head(NULL), Tail(NULL), Size(0) {} //默认构造函数
List(const List<T> &lst):Head(NULL), Tail(NULL), Size(0) //复制构造函数
{
Node<T> *Temp = lst.Head;
while(Temp)
{
push_back(Temp->Data);
Temp = Temp->Next;
}
}
~List() //析构函数
{
Destory();
}
void push_back(const T &Val) //将数据插入链表尾部
{
Node<T> *Temp = new Node<T>(Val);
if(!Head)
Head = Tail = Temp;
else
{
Tail->Next = Temp;
Temp->Prev = Tail;
Tail = Temp;
}
++Size;
}
void pop_back(void) //弹出链表尾节点
{
if(Head)
{
if(Head != Tail)
{
Node<T> *Temp = Tail;
Tail = Tail->Prev;
delete Temp;
Tail->Next = Temp = NULL;
}
else
{
delete Head;
Head = Tail = NULL;
}
--Size;
}
}
int size(void) //返回链表中节点个数
{
return Size;
}
int size(void) const //重载函数，用于const对象
{
return Size;
}
void sort(void) //对链表排序
{
this->BubbleSort();
}
void erase(const T &Val) //删除指定节点
{
Node<T> *Temp = Head;
Node<T> *temp;
while(Temp)
{
if(Temp->Data == Val)
{
if(Temp->Prev)
{
temp = Temp;
temp->Prev->Next = temp->Next;
if(temp->Next)
temp->Next->Prev = temp->Prev;
else
Tail = temp->Prev;
Temp = temp->Next;
delete temp;
}
else
{
temp = Temp;
if(temp->Next)
temp->Next->Prev = NULL;
else
Tail = temp->Prev;
Head = Temp = temp->Next;
delete temp;
}
}
else
Temp = Temp->Next;
}
}
void find(const T &Val) //查找指定元素，有输出Yes，无输出"None"
{
std::cout<<"查找数据域为 "<<Val<<" 的节点：";
if(search(Val))
std::cout<<"Yes!"<<std::endl;
else
std::cout<<"None!"<<std::endl;
}
void find(const T &Val) const //重载函数，用于const对象
{
std::cout<<"查找数据域为 "<<Val<<" 的节点：";
if(search(Val))
std::cout<<"Yes!"<<std::endl;
else
std::cout<<"None!"<<std::endl;
}
void remove(void) //除去重复元素
{
List<T> lst;
Node<T> *Temp = Head;
while(Temp)
{
if(!lst.search(Temp->Data))
lst.push_back(Temp->Data);
Temp = Temp->Next;
}
*this = lst;
}
T maximum(void) //查找最大值，若空对象操作此函数则抛出异常
{
if(!Head)
throw 0;
List<T> lst(*this);
lst.sort();
return lst.Tail->Data;
}
const T maximum(void) const //重载函数，用于const对象
{
if(!Head)
throw 0;
List<T> lst(*this);
lst.sort();
return lst.Tail->Data;
}
T minimum(void) //查找最小值，若空对象操作此函数则抛出异常
{
if(!Head)
throw 0;
List<T> lst(*this);
lst.sort();
return lst.Head->Data;
}
const T minimum(void) const //重载函数，用于const对象
{
if(!Head)
throw 0;
List<T> lst(*this);
lst.sort();
return lst.Head->Data;
}
List<T> &operator =(const List &lst) //重载赋值运算符
{
if(Head)
this->Destory();
Node<T> *Temp = lst.Head;
while(Temp)
{
this->push_back(Temp->Data);
Temp = Temp->Next;
}
return *this;
}
};

template <class T>
std::ostream &operator <<(std::ostream &os, const List<T> &lst) //重载输出运算符
{
Node<T> *Temp = lst.Head;
while(Temp)
{
os<<Temp->Data;
if(Temp->Next)
os<<'\t';
Temp = Temp->Next;
}
return os;
}

int main(void)
{
List<int> lst;
lst.push_back(2); //push_back用于输入
lst.push_back(1);
lst.push_back(1);
lst.push_back(4);
lst.push_back(2);
std::cout<<lst<<std::endl;
lst.pop_back(); //pop_back用于弹出尾节点
std::cout<<lst<<std::endl;
lst.sort(); //sort用于排序
std::cout<<lst<<std::endl;
lst.remove(); //remove用于除去重复节点
std::cout<<lst<<std::endl;
lst.erase(1); //erase用于删除指定节点
std::cout<<lst<<std::endl;
lst.find(4); //find用于查找指定节点，有输出Yes，无输出None
lst.find(1);
std::cout<<lst.maximum()<<std::endl; //maximum返回最大节点的数据域
std::cout<<lst.minimum()<<std::endl; //minimum返回最小节点的数据域

return 0;
}本回答被提问者采纳