#ifndef MY_LIST_H
#define MY_LIST_H
class OutOfBound {};
class IllegalSize{};
template
class MyList
{
public:
virtual void clear() = 0;
virtual int length() const = 0;
virtual void insert(int, const elemType &) = 0;
virtual void remove(int) = 0;
virtual int search(const elemType &) const = 0;
virtual const elemType& visit(int) const = 0;
virtual void traverse() const = 0;
virtual ~MyList(){}
};
#endif
#ifndef MYDIRLIST_H
#define MYDIRLIST_H
#include "mylist.h"
#include
using namespace std;
template
class MyDirList : public MyList < elemType >
{
private:
struct node{
elemType data;
node *pNext;
node() : pNext(NULL){}
node(const elemType &_data, node *p = NULL) :
data(_data), pNext(p){}
};
node *m_pHead;
int m_dLength;
node *moveTo(int) const;
public:
MyDirList(){
m_pHead = new node;
m_dLength = 0;
}
~MyDirList(){
clear();
delete m_pHead;
}
void clear();
int length() const { return m_dLength; }
void insert(int, const elemType &);
void remove(int);
int search(const elemType &) const;
const elemType &visit(int) const;
void traverse() const;
};
template
typename MyDirList::node* MyDirList::moveTo(int pos) const
{
if (pos < -1 || pos >= m_dLength) throw OutOfBound();
node *p = m_pHead;
while (pos-->=0) p = p->pNext;
return p;
}
template
void MyDirList::clear()
{
node *p = m_pHead->pNext, *q;
while (p != NULL)
{
q = p->pNext;
delete p;
p = q;
}
m_dLength = 0;
}
template
void MyDirList::insert(int pos, const elemType &_data)
{
if (pos < 0 || pos > m_dLength) throw OutOfBound();
node *p = moveTo(pos - 1);
node *tmp = new node(_data, p->pNext);
p->pNext = tmp;
m_dLength++;
}
template
void MyDirList::remove(int pos)
{
if (pos < 0 || pos >= m_dLength) throw OutOfBound();
node *p = moveTo(pos - 1);
node *q = p->pNext;
p->pNext = q->pNext;
delete q;
m_dLength--;
}
template
int MyDirList::search(const elemType &_data) const
{
node *p = m_pHead->pNext;
int pos = 0;
while (p != NULL)
{
if (_data == p->data) return pos;
p = p->pNext;
pos++;
}
return -1;
}
template
const elemType &MyDirList::visit(int pos) const
{
if (pos < 0 || pos >= m_dLength) throw OutOfBound();
node *p = moveTo(pos);
return p->data;
}
template
void MyDirList::traverse() const
{
node *p = m_pHead->pNext;
while (p != NULL)
{
int i = 0;
cout << "Data #" << i++ << ": " << p->data << endl;
p = p->pNext;
}
cout << "End of data" << endl;
}
#endif
#ifndef MYSTACK_H
#define MYSTACK_H
#include "mydirlist.h"
//在本文件中完成类接口的定义
template
class MyStack
{
public:
MyStack()
{
m_pStack = new MyDirList;
};
~MyStack();
void push_back(const elemType &value);
void pop_back();
bool isEmpty() const { return m_pStack == NULL; };
const elemType &back() const { return m_pStack->visit(m_pStack->length()); };
private:
MyDirList *m_pStack;
};
template
MyStack::~MyStack()
{
delete m_pStack;
}
template
void MyStack::push_back(const elemType & value)
{
m_pStack->insert(m_pStack->length(), value);
}
template
void MyStack::pop_back()
{
m_pStack->remove(m_pStack->length());
}
#endif
#include
#include "mystack.h"
using namespace std;
int main( )
{
MyStacka;
}
最好只改stack里的。小白求赐教...
