(2)查找链表中某节点可以实现如下功能:
(1)链表节点的输入、输出;
(3)删除指定节点;
(4)对链表节点排序;
(5)查找链表中最大
用C++设计一个单向链表类模板,可以定义多种数据类型。如整型、双精度、字符型、字符串型等。
答案:2 悬赏:50
解决时间 2021-03-13 09:40
- 提问者网友:喜遇你
- 2021-03-12 09:31
最佳答案
- 二级知识专家网友:苦柚恕我颓废
- 2021-03-12 10:31
DEV C++用下面版本
# include
# include
template
class List;
template
std::ostream &operator <<(std::ostream &os, const List &lst);
template
class Node
{
private:
T Data;
Node *Prev;
Node *Next;
friend class List;
friend std::ostream &operator <<(std::ostream &os, const List &lst);
public:
Node(const T &Val):Data(Val), Prev(NULL), Next(NULL) {}
~Node()
{
if(Prev)
Prev = NULL;
if(Next)
Next = NULL;
}
};
template
class List
{
private:
Node *Head;
Node *Tail;
int Size;
void Destory(void) //销毁链表
{
while(Head)
this->pop_back();
}
static void swap(Node *p1, Node *p2) //交换节点的数据域
{
T Val = p1->Data;
p1->Data = p2->Data;
p2->Data = Val;
}
void BubbleSort(void) //冒泡排序(升序)
{
Node *start;
Node *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 *Temp = Head;
while(Temp)
{
if(Temp->Data == Val)
return true;
Temp = Temp->Next;
}
return false;
}
bool search(const T &Val) const //重载函数,用于const对象
{
Node *Temp = Head;
while(Temp)
{
if(Temp->Data == Val)
return true;
Temp = Temp->Next;
}
return false;
}
friend std::ostream &operator <<(std::ostream &os, const List &lst);
public:
List():Head(NULL), Tail(NULL), Size(0) {} //默认构造函数
List(const List &lst):Head(NULL), Tail(NULL), Size(0) //复制构造函数
{
Node *Temp = lst.Head;
while(Temp)
{
push_back(Temp->Data);
Temp = Temp->Next;
}
}
~List() //析构函数
{
Destory();
}
void push_back(const T &Val) //将数据插入链表尾部
{
Node *Temp = new Node(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 *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 *Temp = Head;
Node *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<<"查找数据域为 "<
if(search(Val))
std::cout<<"Yes!"<
else
std::cout<<"None!"<
}
void find(const T &Val) const //重载函数,用于const对象
{
std::cout<<"查找数据域为 "<
if(search(Val))
std::cout<<"Yes!"<
else
std::cout<<"None!"<
}
void remove(void) //除去重复元素
{
List lst;
Node *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 lst(*this);
lst.sort();
return lst.Tail->Data;
}
const T maximum(void) const //重载函数,用于const对象
{
if(!Head)
throw 0;
List lst(*this);
lst.sort();
return lst.Tail->Data;
}
T minimum(void) //查找最小值,若空对象操作此函数则抛出异常
{
if(!Head)
throw 0;
List lst(*this);
lst.sort();
return lst.Head->Data;
}
const T minimum(void) const //重载函数,用于const对象
{
if(!Head)
throw 0;
List lst(*this);
lst.sort();
return lst.Head->Data;
}
List &operator =(const List &lst) //重载赋值运算符
{
if(Head)
this->Destory();
Node *Temp = lst.Head;
while(Temp)
{
this->push_back(Temp->Data);
Temp = Temp->Next;
}
return *this;
}
};
template
std::ostream &operator <<(std::ostream &os, const List &lst) //重载输出运算符
{
Node *Temp = lst.Head;
while(Temp)
{
os<Data;
if(Temp->Next)
os<<'\t';
Temp = Temp->Next;
}
return os;
}
int main(void)
{
List 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.pop_back(); //pop_back用于弹出尾节点
std::cout<
lst.sort(); //sort用于排序
std::cout<
lst.remove(); //remove用于除去重复节点
std::cout<
lst.erase(1); //erase用于删除指定节点
std::cout<
lst.find(4); //find用于查找指定节点,有输出Yes,无输出None
lst.find(1);
std::cout<
std::cout<
return 0;
}
VC6.0用下面版本
# include
# include
template
class List;
template
class Node
{
private:
T Data;
Node *Prev;
Node *Next;
friend class List;
friend std::ostream &operator <<(std::ostream &os, const List &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 List
{
private:
Node *Head;
Node *Tail;
int Size;
void Destory(void) //销毁链表
{
while(Head)
this->pop_back();
}
static void swap(Node *p1, Node *p2) //交换节点的数据域
{
T Val = p1->Data;
p1->Data = p2->Data;
p2->Data = Val;
}
void BubbleSort(void) //冒泡排序(升序)
{
Node *start;
Node *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 *Temp = Head;
while(Temp)
{
if(Temp->Data == Val)
return true;
Temp = Temp->Next;
}
return false;
}
bool search(const T &Val) const //重载函数,用于const对象
{
Node *Temp = Head;
while(Temp)
{
if(Temp->Data == Val)
return true;
Temp = Temp->Next;
}
return false;
}
friend std::ostream &operator <<(std::ostream &os, const List &lst);
public:
List():Head(NULL), Tail(NULL), Size(0) {} //默认构造函数
List(const List &lst):Head(NULL), Tail(NULL), Size(0) //复制构造函数
{
Node *Temp = lst.Head;
while(Temp)
{
push_back(Temp->Data);
Temp = Temp->Next;
}
}
~List() //析构函数
{
Destory();
}
void push_back(const T &Val) //将数据插入链表尾部
{
Node *Temp = new Node(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 *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 *Temp = Head;
Node *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<<"查找数据域为 "<
if(search(Val))
std::cout<<"Yes!"<
else
std::cout<<"None!"<
}
void find(const T &Val) const //重载函数,用于const对象
{
std::cout<<"查找数据域为 "<
if(search(Val))
std::cout<<"Yes!"<
else
std::cout<<"None!"<
}
void remove(void) //除去重复元素
{
List lst;
Node *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 lst(*this);
lst.sort();
return lst.Tail->Data;
}
const T maximum(void) const //重载函数,用于const对象
{
if(!Head)
throw 0;
List lst(*this);
lst.sort();
return lst.Tail->Data;
}
T minimum(void) //查找最小值,若空对象操作此函数则抛出异常
{
if(!Head)
throw 0;
List lst(*this);
lst.sort();
return lst.Head->Data;
}
const T minimum(void) const //重载函数,用于const对象
{
if(!Head)
throw 0;
List lst(*this);
lst.sort();
return lst.Head->Data;
}
List &operator =(const List &lst) //重载赋值运算符
{
if(Head)
this->Destory();
Node *Temp = lst.Head;
while(Temp)
{
this->push_back(Temp->Data);
Temp = Temp->Next;
}
return *this;
}
};
template
std::ostream &operator <<(std::ostream &os, const List &lst) //重载输出运算符
{
Node *Temp = lst.Head;
while(Temp)
{
os<Data;
if(Temp->Next)
os<<'\t';
Temp = Temp->Next;
}
return os;
}
int main(void)
{
List 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.pop_back(); //pop_back用于弹出尾节点
std::cout<
lst.sort(); //sort用于排序
std::cout<
lst.remove(); //remove用于除去重复节点
std::cout<
lst.erase(1); //erase用于删除指定节点
std::cout<
lst.find(4); //find用于查找指定节点,有输出Yes,无输出None
lst.find(1);
std::cout<
std::cout<
return 0;
}
# include
# include
template
class List;
template
std::ostream &operator <<(std::ostream &os, const List
template
class Node
{
private:
T Data;
Node
Node
friend class List
friend std::ostream &operator <<
public:
Node(const T &Val):Data(Val), Prev(NULL), Next(NULL) {}
~Node()
{
if(Prev)
Prev = NULL;
if(Next)
Next = NULL;
}
};
template
class List
{
private:
Node
Node
int Size;
void Destory(void) //销毁链表
{
while(Head)
this->pop_back();
}
static void swap(Node
{
T Val = p1->Data;
p1->Data = p2->Data;
p2->Data = Val;
}
void BubbleSort(void) //冒泡排序(升序)
{
Node
Node
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
while(Temp)
{
if(Temp->Data == Val)
return true;
Temp = Temp->Next;
}
return false;
}
bool search(const T &Val) const //重载函数,用于const对象
{
Node
while(Temp)
{
if(Temp->Data == Val)
return true;
Temp = Temp->Next;
}
return false;
}
friend std::ostream &operator <<
public:
List():Head(NULL), Tail(NULL), Size(0) {} //默认构造函数
List(const List
{
Node
while(Temp)
{
push_back(Temp->Data);
Temp = Temp->Next;
}
}
~List() //析构函数
{
Destory();
}
void push_back(const T &Val) //将数据插入链表尾部
{
Node
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
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
Node
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<<"查找数据域为 "<
std::cout<<"Yes!"<
std::cout<<"None!"<
void find(const T &Val) const //重载函数,用于const对象
{
std::cout<<"查找数据域为 "<
std::cout<<"Yes!"<
std::cout<<"None!"<
void remove(void) //除去重复元素
{
List
Node
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
lst.sort();
return lst.Tail->Data;
}
const T maximum(void) const //重载函数,用于const对象
{
if(!Head)
throw 0;
List
lst.sort();
return lst.Tail->Data;
}
T minimum(void) //查找最小值,若空对象操作此函数则抛出异常
{
if(!Head)
throw 0;
List
lst.sort();
return lst.Head->Data;
}
const T minimum(void) const //重载函数,用于const对象
{
if(!Head)
throw 0;
List
lst.sort();
return lst.Head->Data;
}
List
{
if(Head)
this->Destory();
Node
while(Temp)
{
this->push_back(Temp->Data);
Temp = Temp->Next;
}
return *this;
}
};
template
std::ostream &operator <<(std::ostream &os, const List
{
Node
while(Temp)
{
os<
if(Temp->Next)
os<<'\t';
Temp = Temp->Next;
}
return os;
}
int main(void)
{
List
lst.push_back(2); //push_back用于输入
lst.push_back(1);
lst.push_back(1);
lst.push_back(4);
lst.push_back(2);
std::cout<
std::cout<
std::cout<
std::cout<
std::cout<
lst.find(1);
std::cout<
return 0;
}
VC6.0用下面版本
# include
# include
template
class List;
template
class Node
{
private:
T Data;
Node
Node
friend class List
friend std::ostream &operator <<(std::ostream &os, const List
public:
Node(const T &Val):Data(Val), Prev(NULL), Next(NULL) {}
~Node()
{
if(Prev)
Prev = NULL;
if(Next)
Next = NULL;
}
};
template
class List
{
private:
Node
Node
int Size;
void Destory(void) //销毁链表
{
while(Head)
this->pop_back();
}
static void swap(Node
{
T Val = p1->Data;
p1->Data = p2->Data;
p2->Data = Val;
}
void BubbleSort(void) //冒泡排序(升序)
{
Node
Node
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
while(Temp)
{
if(Temp->Data == Val)
return true;
Temp = Temp->Next;
}
return false;
}
bool search(const T &Val) const //重载函数,用于const对象
{
Node
while(Temp)
{
if(Temp->Data == Val)
return true;
Temp = Temp->Next;
}
return false;
}
friend std::ostream &operator <<(std::ostream &os, const List
public:
List():Head(NULL), Tail(NULL), Size(0) {} //默认构造函数
List(const List
{
Node
while(Temp)
{
push_back(Temp->Data);
Temp = Temp->Next;
}
}
~List() //析构函数
{
Destory();
}
void push_back(const T &Val) //将数据插入链表尾部
{
Node
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
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
Node
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<<"查找数据域为 "<
std::cout<<"Yes!"<
std::cout<<"None!"<
void find(const T &Val) const //重载函数,用于const对象
{
std::cout<<"查找数据域为 "<
std::cout<<"Yes!"<
std::cout<<"None!"<
void remove(void) //除去重复元素
{
List
Node
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
lst.sort();
return lst.Tail->Data;
}
const T maximum(void) const //重载函数,用于const对象
{
if(!Head)
throw 0;
List
lst.sort();
return lst.Tail->Data;
}
T minimum(void) //查找最小值,若空对象操作此函数则抛出异常
{
if(!Head)
throw 0;
List
lst.sort();
return lst.Head->Data;
}
const T minimum(void) const //重载函数,用于const对象
{
if(!Head)
throw 0;
List
lst.sort();
return lst.Head->Data;
}
List
{
if(Head)
this->Destory();
Node
while(Temp)
{
this->push_back(Temp->Data);
Temp = Temp->Next;
}
return *this;
}
};
template
std::ostream &operator <<(std::ostream &os, const List
{
Node
while(Temp)
{
os<
if(Temp->Next)
os<<'\t';
Temp = Temp->Next;
}
return os;
}
int main(void)
{
List
lst.push_back(2); //push_back用于输入
lst.push_back(1);
lst.push_back(1);
lst.push_back(4);
lst.push_back(2);
std::cout<
std::cout<
std::cout<
std::cout<
std::cout<
lst.find(1);
std::cout<
return 0;
}
全部回答
- 1楼网友:万千宠爱
- 2021-03-12 11:32
用win-tc编译的,手里没vc
我要举报
如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯