目录
线性表的数据类型定义
1. 顺序表
1.1 顺序表的类定义
1.2 顺序表的插入
1.3 顺序表的删除
2. 链表
2.1 单链表的节点定义
2.2 单链表的类型定义
2.3 返回指定位置pos的指针
2.4 插入单链表的第i个结点
2.5 删除单链表的第i个结点
2.6 双链表的结点定义和实现
3. 栈
3.1 栈的类定义
4. 队列
4.1 队列的抽象数据类型定义
线性表的数据类型定义
template <class T>
class List
{
void Clear(); //置空线性表
bool IsEmpty(); //线性表为空时，返回true
bool Append(const T value); //在表尾添加元素value，表的长度增加1
bool Insert(const int p, const T value); //在位置p插入元素value，表的长度增加1
bool Delete(const int p); //删除位置p上的元素，表的长度减少1
bool GetValue(const int p, T& value); //把位置p上的元素值返回到变量value中
bool SetValue(const int p, const T value); //把位置p上的元素至修改为value
bool GetPos(int &p, const T value); //把值为value的元素的位置返回到变量p中
}
1. 顺序表
1.1 顺序表的类定义
template <class T>
class ArrayList : publice List<T> //定义顺序表ArrayList
{
public: //顺序表的运算集
ArrayList(const int size) //创建顺序表，表长为最大长度
{
maxSize = size;
arrayList = new T[maxSize];
curLen = 0;
position = 0;
}
~ArrayList() //析构函数，消除ArrayList的实例
{
delete [] arrayList;
}
void clear() //清空顺序表
{
delete [] arrayList;
curLen = 0;
position = 0;
arrayList = new T[maxSize];
}
int Length();
bool Append(const T value); //在表尾添加元素value，表的长度增加1
bool Insert(const int p, const T value); //在位置p插入元素value，表的长度增加1
bool Delete(const int p); //删除位置p上的元素，表的长度减少1
bool GetValue(const int p, T& value); //把位置p上的元素值返回到变量value中
bool SetValue(const int p, const T value); //把位置p上的元素至修改为value
bool GetPos(int &p, const T value); //把值为value的元素的位置返回到变量p中
private:
T *arrayList; //存储顺序表
int maxSize; //顺序表实例的最大长度
int curLen; //顺序表实例的当前长度
int positon; //当前处理位置
};
1.2 顺序表的插入
template <class T>
bool ArrayList<T> :: Insert(const int p, const T value)
{
if(curLen >= maxSize) //检查顺序表是否溢出
{
cout << "The List is overflow" << endl;
return false;
}
if(p < 0 || p > curLen) //检查插入位置是否合法
{
cout << "Insertion point is illegal" << endl;
}
for(int i = curLen; i > p; i--)
{
arrayList[i] = arrayList[i-1];
//从表尾curLen-1处向后移动一个位置知道插入位置p
}
arrayList[p] = value; //位置p处插入新元素
curLen++; //表的实际长度增加1
return ture;
}
1.3 顺序表的删除
template <class T>
bool ArrayList<T> :: Delete(const int p)
{
if(curLen <= 0) //检查顺序表是否为空
{
cout << "No element to delete" << endl;
return false;
}
if(p < 0 || p > curLen - 1) //检查删除位置的合法性
{
cout << "Deletion is illegal" <<endl;
return false;
}
for(int i = p; i < curLen - 1; i++)
{
arrayList[i] = arrayList[i+1];
//从删除位置p开始每个元素向前移动一个位置直到表尾
}
curLen--; //表的实际长度减1
return true;
}
2. 链表
2.1 单链表的节点定义
template<class T>
class LinkNode
{
public:
T data; //数据域
LinkNode<T>*link; //指向后继指针的结点
LinkNode(const T&el, LinkNode<T>*ptr = 0) //构造函数
{
data = el;
link = ptr;
}
};
2.2 单链表的类型定义
template<class T>
class LinkList
{
private:
LinkNode<T> *head, *tail; //表头和表尾指针
LinkNode<T> *prevPtr, *currPtr; //记录表当前遍历位置的指针，由插入和删除操作更新
int position; //当前元素在表中的位置序号，由函数reset使用
public:
LinkList();
~LinkList();
int getSize()const; //返回链表中的元素个数
bool isEmpty()const; //链表是否为空
void reset(int pos = 0); //初始化指针的位置(第一位数的位置设为0)
void next(); //使指针移动到下一个结点
bool endOfList()const; //指针是否到了链尾
int currentPosition(void); //返回指针当前的位置
void insertHead(const T&item); //在表头插入结点
void insertTail(const T&item); //在表尾添加结点
void insertAt(const T&item); //在当前结点之前插入结点
void insertAfter(const T&item); //在当前结点之后插入结点
T deleteHead(); //删除头结点
void deleteCurrent(); //删除当前结点
T&data(); //返回对当前结点成员数据的引用
const T&data()const; //返回对当前结点成员数据的常引用
void clear(); //清空链表：释放所有结点的内存空间
LinkNode<T>* setPos(int pos); //返回指定位置pos的指针
bool insertPos(const int i, const T value);//在指定位置插入结点
bool deletePos(const int i); //删除指定位置的结点
};
2.3 返回指定位置pos的指针
template<class T>
LinkNode<T> * LinkList<T>::setPos(int pos)
{
if(pos == -1) //i为-1则定位到头结点
return head;
int count = 0;
LinkNode<T> *p = head->link;
while(p != Null && count < pos)
{
p = p->link;
count++;
}
return p;
//指向第i个结点，当链表长度小于1时返回NULL
}
2.4 插入单链表的第i个结点
template<class T>
bool LinkList<T>::insertPos(const int i, const T value)
{
LinkNode<T> *p, *q;
if((p = setPos(i - 1)) == NULL) //p是第i个结点的前驱
{
cout << "插入操作不允许" <<endl;
return false;
}
q = new LinkNode<T>(value, p->link);
p->link = q;
if(p == tail) //在表尾进行插入操作
tail = q;
return true;
}
2.5 删除单链表的第i个结点
template<class T>
bool LinkList<T>::deletePos(const int i)
{
LinkNode<T> *p, *q;
if((p = setPos(i - 1)) == NULL || p == tail)//待删除点不存在
{
cout << "非法删除点" <<endl;
return false;
}
q = p->link; //q为真正待删除点
if(q == tail) //删除点为表尾，修改为指针
{
tail = p;
p->link = NULL;
delete q;
}
else if(q != NULL) //删除结点q，并修改指针
{
p->link = q->link;
delete q;
}
return true;
}
2.6 双链表的结点定义和实现
template<class T>
class DLLNode
{
public:
T data; //保存结点元素的内容
DLLNode<T> *next; //指向后继结点的指针
DLLNode<T> *prev; //指向前驱结点的指针
DLLNode(const T info, DLLNode<T> *prevVal = NULL, DLLNode<T>
*nextVal = NULL) //构造函数
{
data = info;
prev = prevVal;
next = nextVal;
}
DLLNode(DLLNode<T> *prevVal = NULL,DLLNode<T> *next = NULL)
{
prev = prevVal;
next = nextVal;
}
};
3. 栈
3.1 栈的类定义
template<class T>
class Stack
{
public:
void Clear(); //清空栈
bool Push(const T item); //栈的压入操作
bool Pop(T & item); //读取栈顶元素的值并删除
bool Top(T & item); //读取栈顶元素的值但不删除
bool IsEmpty(); //判断栈是否为空
bool IsFull(); //判断栈是否已满
};
4. 队列
4.1 队列的抽象数据类型定义
template<class T>
class Queue
{
public:
void Clear(); //清空队列
bool EnQueue(const T item); //队列的尾部加入元素item
bool DeQueue(T & item); //取出队列的第一个元素，并删除
bool IsEmpty(); //判断队列是否为空
bool IsFull(); //判断队列是否已满
bool GetFront(T & item); //读取队头元素，但不删除
};
|