c++使用单链表实现链栈，使用单链表实现链栈，单链表不含头结点

公有三种方法：

1、把单链表类作为栈类的私有变量

2、把单链表类作为栈类的基类，使用继承的思想

3、把栈类作为单链表类的友元，这里略去

方法一：单链表类作为链栈的私有变量

问题：VS2005可以运行通过，但是dev通不过，不知道为什么，请各位大牛指正。

[cpp] view plaincopy
#include <iostream>
using namespace std;
template<class Type>
//定义结点
struct Node
{
Type data;
Node<Type> *next;
};
//定义链表
template<class Type>
class LinkList
{
protected:
int len;//链表中结点个数
Node<Type>* Head; //不使用头结点
public:
LinkList();//默认构造函数
LinkList(const LinkList<Type>& otherList);//拷贝构造函数
~LinkList();
void createListForward();//头插法
void createBackward();//尾插法
void initList();//生成头结点，尾部设置为NULL
bool isEmptyList();
int length();
void destoryList();
void getFirstData(Type& firstItem);
void getData(int pos,Type& firstItem);
void insertFirst(Type newItem);
void insertLast(Type newItem);
void deleteFirst(Type& data);
void deleteLast();
void reverse();
const LinkList<Type>& operator=(const LinkList<Type>&otherList);
friend ostream& operator<< <>(ostream& cout,const LinkList<Type>& list);
};

template<class Type>
LinkList<Type>::LinkList() //初始化时，只有一个头结点，有head指向
{
Head = NULL;
len =0;
}

template<class Type>
LinkList<Type>::LinkList(const LinkList<Type>&otherList)
{
Head = NULL;
len = otherList.len;
Node<Type>* current;//自己链表的尾部元素
Node<Type>* otherListCurrent=otherList.Head;//otherListCurrent指向第一个元素
while(otherListCurrent!=NULL)//拷贝的目标不为空
{
for (int i=1;i<=otherList.len;i++)
{
Node<Type>* NewNode = new Node<Type>;
NewNode->data = otherListCurrent->data;
NewNode->next = NULL;
if (i==1)
{
Head = NewNode;
current = Head;
}
else
{
current->next = NewNode;
current = current->next;
}
otherListCurrent = otherListCurrent->next;
}
}

}

template<class Type>
const LinkList<Type>& LinkList<Type>::operator=(const LinkList<Type>&otherList)//赋值函数
{
Node<Type>* current;//current总是指向要插的位置的前一结点
Node<Type>* otherListCurrent=otherList.Head;//otherListCurrent指向第一个元素
if (this!=&otherList)//避免自己给自己赋值
{
if (Head!=NULL)
{
destoryList();//自己有结点，先销毁
}
if(otherListCurrent!=NULL)
{
bool first = true;
while(otherListCurrent!=NULL)
{
Node<Type>* newNode = new Node<Type>;
newNode->data = otherListCurrent->data;
newNode->next = NULL;
if (first)
{
Head = newNode;
current = Head;
first = false;
}
else
{
current->next = newNode;
current = current->next;
}
otherListCurrent = otherListCurrent->next;
}
}
}
return *this;//为了连续赋值
}

template<class Type>
LinkList<Type>::~LinkList()
{
destoryList();
}

template<class Type>
void LinkList<Type>::createListForward()//头插法
{
Node<Type>* newNode;
cout<<”输入链表长度:”<<endl;
cin>>len;
for (int i=1;i<=len;i++)
{
newNode = new Node<Type>;
cout<<”输入元素:”<<endl;
cin>>newNode->data;
newNode->next=Head;
Head = newNode; //每插入一个结点，都是要把它放在第一个结点的位置
}
}

template<class Type>
void LinkList<Type>::createBackward()//尾插法
{
Node<Type>* newNode;
Node<Type>* current;//总是指向最后一个节点
cout<<”输入链表长度:”<<endl;
cin>>len;
for (int i=1;i<=len;i++)
{
newNode = new Node<Type>;
cout<<”输入元素:”<<endl;
cin>>newNode->data;
newNode->next = NULL;
if (i==1)
{
Head = newNode;
current = Head;
}
else
{
current->next=newNode;
current = current->next;
}

}
}

template<class Type>
void LinkList<Type>::initList() //所有结点都销毁
{
destoryList();
len=0;
Head=NULL;
}

template<class Type>
bool LinkList<Type>::isEmptyList()
{
if (Head==NULL)
{
return true;
}
else
{
return false;
}
}

template<class Type>
int LinkList<Type>::length()
{
return len;
}

template<class Type>
void LinkList<Type>::destoryList()//销毁包括头结点
{
Node<Type>* current;
while(Head!=NULL)
{
current = Head;
Head = current->next;
delete current;
}
Head=NULL;
len=0;
}

template<class Type>
void LinkList<Type>::getFirstData(Type& firstItem)
{
if (!isEmptyList())
{
firstItem = Head->data;
}
else
{
cout<<”链表为空!”<<endl;
}
}

template<class Type>
void LinkList<Type>::getData(int pos,Type& newItem)
{
if (pos<1 || pos>len)
{
cout<<”位置不当！”<<endl;
}
else
{
Node<Type>* current = Head;
for (int i=1;i<pos;i++)
{
current = current->next;
}
newItem = current->data;
}
}

template<class Type>
void LinkList<Type>::insertFirst(Type newItem)
{
Node<Type> *newNode = new Node<Type>;
newNode->data = newItem;
newNode->next = Head;
Head= newNode;
len++;
}

template<class Type>
void LinkList<Type>::insertLast(Type newItem)
{
Node<Type>* current = Head;
while(current!=NULL && current->next!=NULL)
{
current = current->next;
}
Node<Type> *newNode = new Node<Type>;
newNode->data = newItem;
if (current==NULL)//链表为空
{
newNode->next = current;
current = newNode;
}
else
{
newNode->next = current->next;
current->next = newNode;
}
len++;
}

template<class Type>
void LinkList<Type>::deleteFirst(Type& data)
{
if (!isEmptyList())
{
data = Head->data;
Node<Type>* temp = Head;
Head = Head->next;
delete temp;
}
else
{
cout<<”栈空!”<<endl;
}
len–;
}

template<class Type>
void LinkList<Type>::deleteLast()
{
Node<Type>* current = Head;
if (isEmptyList())
{
cout<<”链表为空！”<<endl;
}
else
{
for (int i=1;i<len-1;i++)
{
current = current->next;
}
Node<Type>* nextCurrent = current->next;
current->next = nextCurrent->next;
delete nextCurrent;
}
len–;

}

template<class Type>
void LinkList<Type>::reverse()
{
Node<Type>* current = Head;
Head=NULL;
if (current==NULL)
{
cout<<”链表为空!”<<endl;
}
else
{
while (current!=NULL)
{
Node<Type>* nextCurrent = current->next;
current->next = Head;
Head=current;
current = nextCurrent;
}
}
}

template<class Type>
ostream& operator<< (ostream& cout,const LinkList<Type>& list)
{
Node<Type>*current=list.Head; //有头结点，这是current指向第一个结点
if (current!=NULL)
{
while (current!=NULL)
{
cout<<current->data<<endl;
current=current->next;
}
}
else
{
cout<<”链表为空!”<<endl;
}
return cout;
}

//栈类
/*链栈的条件
栈顶初始值：top=NULL;
栈顶:top总是指向刚刚压入值,且栈顶就是头指针，没有头结点
栈空：top=NULL
栈满：不存在栈满，可以继续申请空间
入栈: 申请空间
出栈：释放空间
*/

template<class Type>
class Stack
{
private:
LinkList<Type> linklist;
public:
Stack();
Stack(const Stack<Type>& otherStack);
~Stack();
void operator=(const Stack<Type>& otherStack);
void initStack();
bool isEmptyStack()const;
void destoryStack();
void pop(Type& data);
void top(Type& data);
void push(Type data);
int count()const;
};

/*
这里可以不定义两个构造函数、析构函数和赋值函数，因为这里系统会自动调用默认的函数，其运行时又会自动调用LinkList的对应函数
*/
template<class Type>
Stack<Type>::Stack():linklist()
{

}

template<class Type>
Stack<Type>::Stack(const Stack<Type>& otherStack):linklist(otherStack.linklist)//新建对象的数组没有空间，这时要申请空间
{

}

template<class Type>
Stack<Type>::~Stack() //有单链表进行处理
{
}

/* 返回值为Stack<Type>，就会陷入无限循环，如果不使用返回值就可以往下执行，不知道是为什么
template<class Type>
Stack<Type> Stack<Type>::operator=(const Stack<Type>& otherStack)
{
linklist.operator=(otherStack.linklist);
return *this;
}
*/

template<class Type>
void Stack<Type>::operator=(const Stack<Type>& otherStack)
{
linklist.operator=(otherStack.linklist);
}

template<class Type>
void Stack<Type>::initStack()
{
linkList.initList();
}

template<class Type>
bool Stack<Type>::isEmptyStack()const
{
return linklist.isEmptyList();
}

template<class Type>
void Stack<Type>::destoryStack()
{
linklist.destoryList();
}

template<class Type>
void Stack<Type>::pop(Type& data)
{
linklist.deleteFirst(data);
}

template<class Type>
void Stack<Type>::top(Type& data)
{
linklist.getFirstData(data);
}

template<class Type>
void Stack<Type>::push(Type NewItem)
{
linklist.insertFirst(NewItem);
}

template<class Type>
int Stack<Type>::count()const
{
return linklist.len;
}

int main()
{
Stack<int> s;
int a[4]={1,2,3,4};
for (int i=0;i<4;i++)
{
s.push(a[i]);
}
Stack<int> s1 = s;
int data;
s1.top(data);
cout<<data<<endl;
system(“pause”);
return 0;
}
方法二：单链表类作为基类，栈类作为派生类
[cpp] view plaincopy
#include <iostream>
using namespace std;
template<class Type>
//定义结点
struct Node
{
Type data;
Node<Type> *next;
};
//定义链表
template<class Type>
class LinkList
{
protected:
int len;//链表中结点个数
Node<Type>* Head; //不使用头结点
public:
LinkList();//默认构造函数
LinkList(const LinkList<Type>& otherList);//拷贝构造函数
~LinkList();
void createListForward();//头插法
void createBackward();//尾插法
void initList();//生成头结点，尾部设置为NULL
bool isEmptyList();
int length();
void destoryList();
void getFirstData(Type& firstItem);
void getData(int pos,Type& firstItem);
void insertFirst(Type newItem);
void insertLast(Type newItem);
void deleteFirst(Type& data);
void deleteLast();
void reverse();
const LinkList<Type>& operator=(const LinkList<Type>&otherList);
friend ostream& operator<< <>(ostream& cout,const LinkList<Type>& list);
};

template<class Type>
LinkList<Type>::LinkList() //初始化时，只有一个头结点，有head指向
{
Head = NULL;
len =0;
}

template<class Type>
LinkList<Type>::LinkList(const LinkList<Type>&otherList)
{
Head = NULL;
len = otherList.len;
Node<Type>* current;//自己链表的尾部元素
Node<Type>* otherListCurrent=otherList.Head;//otherListCurrent指向第一个元素
while(otherListCurrent!=NULL)//拷贝的目标不为空
{
for (int i=1;i<=otherList.len;i++)
{
Node<Type>* NewNode = new Node<Type>;
NewNode->data = otherListCurrent->data;
NewNode->next = NULL;
if (i==1)
{
Head = NewNode;
current = Head;
}
else
{
current->next = NewNode;
current = current->next;
}
otherListCurrent = otherListCurrent->next;
}
}

}

template<class Type>
const LinkList<Type>& LinkList<Type>::operator=(const LinkList<Type>&otherList)//赋值函数
{
Node<Type>* current;//current总是指向要插的位置的前一结点
Node<Type>* otherListCurrent=otherList.Head;//otherListCurrent指向第一个元素
if (this!=&otherList)//避免自己给自己赋值
{
if (Head!=NULL)
{
destoryList();//自己有结点，先销毁
}
if(otherListCurrent!=NULL)
{
bool first = true;
while(otherListCurrent!=NULL)
{
Node<Type>* newNode = new Node<Type>;
newNode->data = otherListCurrent->data;
newNode->next = NULL;
if (first)
{
Head = newNode;
current = Head;
first = false;
}
else
{
current->next = newNode;
current = current->next;
}
otherListCurrent = otherListCurrent->next;
}
}
}
return *this;//为了连续赋值
}

template<class Type>
LinkList<Type>::~LinkList()
{
destoryList();
}

template<class Type>
void LinkList<Type>::createListForward()//头插法
{
Node<Type>* newNode;
cout<<”输入链表长度:”<<endl;
cin>>len;
for (int i=1;i<=len;i++)
{
newNode = new Node<Type>;
cout<<”输入元素:”<<endl;
cin>>newNode->data;
newNode->next=Head;
Head = newNode; //每插入一个结点，都是要把它放在第一个结点的位置
}
}

template<class Type>
void LinkList<Type>::createBackward()//尾插法
{
Node<Type>* newNode;
Node<Type>* current;//总是指向最后一个节点
cout<<”输入链表长度:”<<endl;
cin>>len;
for (int i=1;i<=len;i++)
{
newNode = new Node<Type>;
cout<<”输入元素:”<<endl;
cin>>newNode->data;
newNode->next = NULL;
if (i==1)
{
Head = newNode;
current = Head;
}
else
{
current->next=newNode;
current = current->next;
}

}
}

template<class Type>
void LinkList<Type>::initList() //所有结点都销毁
{
destoryList();
len=0;
Head=NULL;
}

template<class Type>
bool LinkList<Type>::isEmptyList()
{
if (Head==NULL)
{
return true;
}
else
{
return false;
}
}

template<class Type>
int LinkList<Type>::length()
{
return len;
}

template<class Type>
void LinkList<Type>::destoryList()//销毁包括头结点
{
Node<Type>* current;
while(Head!=NULL)
{
current = Head;
Head = current->next;
delete current;
}
Head=NULL;
len=0;
}

template<class Type>
void LinkList<Type>::getFirstData(Type& firstItem)
{
if (!isEmptyList())
{
firstItem = Head->data;
}
else
{
cout<<”链表为空!”<<endl;
}
}

template<class Type>
void LinkList<Type>::getData(int pos,Type& newItem)
{
if (pos<1 || pos>len)
{
cout<<”位置不当！”<<endl;
}
else
{
Node<Type>* current = Head;
for (int i=1;i<pos;i++)
{
current = current->next;
}
newItem = current->data;
}
}

template<class Type>
void LinkList<Type>::insertFirst(Type newItem)
{
Node<Type> *newNode = new Node<Type>;
newNode->data = newItem;
newNode->next = Head;
Head= newNode;
len++;
}

template<class Type>
void LinkList<Type>::insertLast(Type newItem)
{
Node<Type>* current = Head;
while(current!=NULL && current->next!=NULL)
{
current = current->next;
}
Node<Type> *newNode = new Node<Type>;
newNode->data = newItem;
if (current==NULL)//链表为空
{
newNode->next = current;
current = newNode;
}
else
{
newNode->next = current->next;
current->next = newNode;
}
len++;
}

template<class Type>
void LinkList<Type>::deleteFirst(Type& data)
{
if (!isEmptyList())
{
data = Head->data;
Node<Type>* temp = Head;
Head = Head->next;
delete temp;
}
else
{
cout<<”栈空!”<<endl;
}
len–;
}

template<class Type>
void LinkList<Type>::deleteLast()
{
Node<Type>* current = Head;
if (isEmptyList())
{
cout<<”链表为空！”<<endl;
}
else
{
for (int i=1;i<len-1;i++)
{
current = current->next;
}
Node<Type>* nextCurrent = current->next;
current->next = nextCurrent->next;
delete nextCurrent;
}
len–;

}

template<class Type>
void LinkList<Type>::reverse()
{
Node<Type>* current = Head;
Head=NULL;
if (current==NULL)
{
cout<<”链表为空!”<<endl;
}
else
{
while (current!=NULL)
{
Node<Type>* nextCurrent = current->next;
current->next = Head;
Head=current;
current = nextCurrent;
}
}
}

template<class Type>
ostream& operator<< <>(ostream& cout,const LinkList<Type>& list)
{
Node<Type>*current=list.Head; //有头结点，这是current指向第一个结点
if (current!=NULL)
{
while (current!=NULL)
{
cout<<current->data<<endl;
current=current->next;
}
}
else
{
cout<<”链表为空!”<<endl;
}
return cout;
}

//栈类
/*链栈的条件
栈顶初始值：top=NULL;
栈顶:top总是指向刚刚压入值,且栈顶就是头指针，没有头结点
栈空：top=NULL
栈满：不存在栈满，可以继续申请空间
入栈: 申请空间
出栈：释放空间
*/

template<class Type>
class Stack:public LinkList<Type>
{
public:
void initStack();
bool isEmptyStack()const;
void destoryStack();
void pop(Type& data);
void top(Type& data);
void push(Type data);
int count()const;
};

template<class Type>
void Stack<Type>::initStack()
{
initList();
//或使用LinkList::initList();
}

template<class Type>
bool Stack<Type>::isEmptyStack()const
{
return isEmptyList();
}

template<class Type>
void Stack<Type>::destoryStack()
{
destoryList();
}

template<class Type>
void Stack<Type>::pop(Type& data)
{
deleteFirst(data);
}

template<class Type>
void Stack<Type>::top(Type& data)
{
getFirstData(data);
}

template<class Type>
void Stack<Type>::push(Type NewItem)
{
insertFirst(NewItem);
}

template<class Type>
int Stack<Type>::count()const
{
return len;
}

void main()
{
Stack<int> s;
int a[4]={1,2,3,4};
for (int i=0;i<4;i++)
{
s.push(a[i]);
}
Stack<int> s1;
s1 = s;
for (int i=0;i<4;i++)
{
int temp;
s.pop(temp);
cout<<temp<<endl;
}
cout<<s1.count();
system(“pause”);
}