堆栈链表看起来简单，真让写，还是有一定困难的。动手用模板实现链表，练练手。
#include<iostream>
using namespace std;
template <class T>
class Node {
public:
Node(T e, Node *ptr=NULL) : data(e), next(ptr) {};
T data;
Node *next;
};
template <class T>
class List {
public:
List() { head=tail=NULL; };
~List();
bool isEmpty() {return (head == NULL)}; //检查List是否为空
void addToHead(T); //插入头节点
void addToTail(T); //插入尾节点
T delFromHead(); //删除头结点
T delFromTail(); //删除尾节点
int isInList(T) const; //查找指定元素是否在List中，有则返回第一次找到匹配的位置(从0开始),没有则返回-1
void deleteNode(T); //删除指定元素节点
//private:
Node<T> *head,*tail; //模板类用的时候记得这么写 Node<T>
};
template <class T>
List<T>::~List() { //注意类成员函数定义使用模板时的格式 template<class T> List<T>::~List(){...}
Node<T> *ptr;
while(head != NULL) //List不为空
{
ptr = head;
head = head->next;
delete ptr;
}
}
template <class T>
void List<T>::addToHead(T data) {
head = new Node<T>(data, head);
if (tail == NULL) //原来List为空的话，tail和head都指到该节点上
tail = head;
}
template <class T>
void List<T>::addToTail(T data) {
if (tail == NULL)
head = tail = new Node<T>(data);
else //原来List不空，加到末尾
{
tail->next = new Node<T>(data);
tail = tail->next;
}
}
template <class T>
T List<T>::delFromHead() {
if(head == NULL) //List为空
{
cerr << "List is empty! Fail to delete from head." << endl;
exit(1);
}
T e = head->data;
Node<T> *ptr = head;
if(head == tail) //只有一个节点
head = tail = NULL;
else //不只一个节点
head = head->next;
delete ptr; //释放内存
return e;
}
template <class T>
T List<T>::delFromTail() {
if(tail == NULL) //List为空
{
cerr << "List is empty! Fail to delete from tail." << endl;
exit(1);
}
T e = tail->data;
Node<T> *ptr;
if(tail == head) //只有一个节点
{
ptr = tail;
tail = head = NULL;
delete ptr; //释放内存
}
else //不止一个节点
{
ptr = head;
while(ptr->next != tail) //使ptr->next == tail;
ptr = ptr->next;
delete tail;
tail = ptr;
tail->next = NULL; //这步不要忘了，使tail->next = NULL;
}
return e;
}
template <class T>
int List<T>::isInList(T data) const{ //const函数体在声明和定义时都要写明const
Node<T> *ptr = head;
for(int index = 0; ptr->next != NULL; index++) {
if(ptr->data == data)
return index;
}
return -1; //没有找到返回-1
}
template <class T>
void List<T>::deleteNode(T data) {
if (head == NULL) //检查List是否为空
{
cerr << "List is empty." << endl;
return;
}
else if (head == tail) //只有一个节点
{
if (data == head->data) { //如果data == head->data
delete head;
head = tail = NULL;
}
else {
cerr << "Data is no found." << endl;
return;
}
}
else //有多个节点
{
if (data == head->data) { //如果data == head->data
Node<T> *ptr = head;
head = head->next;
delete ptr;
}
else {
Node<T> *ptr,*pre;
for(pre=head, ptr=head->next; (data!=ptr->data) && (ptr!=NULL); pre=ptr, ptr=ptr->next) ; //别忘了分号
if(ptr!=NULL) //找到节点,删除
{
pre->next = ptr->next;
if (ptr == tail) //如果找到的节点是尾节点，则记得要重设尾节点
tail = pre;
delete ptr;
}
else //没有找到节点
cerr << "Data is no found." << endl;
}
}
}
void main()
{
List<int> list;
list.addToHead(1);
list.addToHead(2);
list.addToHead(3);
list.addToHead(4);
list.addToHead(5);
list.delFromHead();
list.deleteNode(3);
list.delFromTail();
Node<int> *p = list.head;
while(p!=NULL)
{
cout << p->data << ' ';
p = p->next;
}
}
[版权声明]BSD爱好者乐园站内文章，如来源不是互联网，则均系原创或翻译之作，可随意转载，或以此为基础进行演译，但务必以链接形式注明原始出处和作者信息，否则属于侵权行为。另对本站转载他处文章，俱有说明，如有侵权请联系本人，本人将会在第一时间删除侵权文章。
TAG: 模板 链表