链式队列的C++实现
在这里,我们实现了用单向链表的节点来创建一个队列,然而我们可以使用一个循环链表(尾节点的next域为头节点指针值)来实现队列,这时last->next==first,而判断队列是否为空,只要判断last是否等于first就行了.过多这种方法实现的细节不再阐述,因为看了下面的单向链表构成的队列就可以很容易写出循环链表构成的队列.下面是定义链式队列的四个文件的源代码:
Queue.h文件:
//////////////////////////////////////////////////////////////////////
//Queue.h文件:它创建了一个纯虚基类,用于定义链式队列的功能.
//////////////////////////////////////////////////////////////////////
template
class Queue
{
public:
virtual void Clear() =0; //清空队列中的所有节点内存.
virtual bool AddValue(const type &) =0; //从队列头部添加一个节点.
virtual bool DelValue(type &) =0; //从队列尾部删除一个节点.
virtual bool GetValue(type &) =0; //得到队列头部节点的值,但不删除.
virtual int Length() =0; //得到队列节点数目.
};
Link.h文件:
//////////////////////////////////////////////////////////////////////
//Link.h文件:创建一个节点类,它包含数据域以及指针域,它的定义与链表节点
//的定义完全相同.两个构造函数用于在创建节点时同时赋值.该类还可以实现节
//点内存回收,用于快速分配以及释放节点内存,这一点是由一个栈实现的.
//////////////////////////////////////////////////////////////////////
template
class Link
{
public:
type data; //数值域
Link *next; //指针域
Link(const type &,Link * =NULL);
Link(Link * =NULL);
~Link(); //两个构造函数以及一个析构函数.
void* operator new(size_t);
void operator delete(void*); //用于实现节点内存的回收和分配.
private:
static Link *freeList; //用于创建一个栈.而所有该类的对象都共享该成员.
};
//////////////////////////////////////////////////////////////////////
//构造以及析构函数的实现.
//////////////////////////////////////////////////////////////////////
template
Link::Link(const type &val,Link *n)
{
data=val;
next=n;
}
template
Link::Link(Link *n)
{
next=n;
}
template
Link::~Link()
{
Link *temp;
while(freeList)
{
temp=freeList;
freeList=freeList->next;
::delete temp; //当Link类的对象删除时,同时释放栈中的节点内存.
}
}
//////////////////////////////////////////////////////////////////////
//栈的实现,我们要先对静态私有成员进行初始化,然后重载new和delete运算符.
//////////////////////////////////////////////////////////////////////
template
Link* Link::freeList=NULL; //初始化成NULL
template
void* Link::operator new(size_t)
{
Link *temp;
if(freeList)
{
temp=freeList; //如果栈是有内存节点,那么从栈中得到.
freeList=freeList->next;
return temp;
}
return ::new Link; //如果栈中没有节点,那么让系统分配内存.
}
template
void Link::operator delete(void *temp)
{
((Link*)temp)->next=freeList; //将删除掉的节点放处栈中,以便能更好的重复利用.
freeList=((Link*)temp);
}
LQueue.h文件:
//////////////////////////////////////////////////////////////////////
//LQueue.h文件:用于创建LQueue类,它实现了链式队列的功能.
//////////////////////////////////////////////////////////////////////
#include "Queue.h"
#include "Link.h"
template
class LQueue :public Queue
{
public:
LQueue();
~LQueue();
void Clear();
bool AddValue(const type &);
bool DelValue(type &);
bool GetValue(type &);
int Length();
private:
Link *first; //队列头节点.
Link *last; //队列尾节点.
int size; //节点总数.
};
LQueue.cpp文件:
//////////////////////////////////////////////////////////////////////
// LQueue.cpp文件:对LQueue类的成员函数的定义以及测试该类.
//////////////////////////////////////////////////////////////////////
#include
#include "LQueue.h"
using namespace std;
//////////////////////////////////////////////////////////////////////
//LQueue类成员函数的实现.
//////////////////////////////////////////////////////////////////////
template
LQueue::LQueue()
{
first=last=NULL;
size=0;
}
template
LQueue::~LQueue()
{
Clear();
}
template
void LQueue::Clear()
{
while(first)
{
last=first; //一个一个删除队列中的所有节点.
first=first->next;
delete last;
}
last=NULL;
size=0;
}
template
bool LQueue::AddValue(const type &val)
{
if(first==NULL)
first=last=new Link(val,NULL); //如果队列为空,那么添加第一个节点.
else
last=last->next=new Link(val,NULL); //否则在后面添加节点.
size++; //节点数加一.
return true; //返回真.
}
template
bool LQueue::DelValue(type &val)
{
Link *temp;
if(first==NULL)
return false; //如果队列为空,那么返回false.
val=first->data; //否则得到头节点的值.
temp=first;
first=first->next; //然后指向下一节点.
delete temp; //删除上一节点.
size--; //节点数减一.
return true; //返回true.
}
template
bool LQueue::GetValue(type &val)
{
if(first==NULL)
return false; //如果队列为空,那么返回false.
val=first->data;
return true; //否则得到头节点值,并返回.
}
template
int LQueue::Length()
{
return size; //返回节点数.
}
int _tmain(int argc, _TCHAR* argv[])
{
int num,len;
LQueue value;
value.AddValue(1);
value.AddValue(2);
value.AddValue(3);
len=value.Length();
for(int i=0;i
{
value.DelValue(num);
cout<
}
cout<
value.Clear();
value.AddValue(1);
value.AddValue(2);
value.AddValue(3);
value.AddValue(4);
len=value.Length();
for(int i=0;i
{
value.GetValue(num);
cout<
value.DelValue(num);
cout<
}
cout<
return 0;
}
在写这个程序的时候我犯了两个非常大的错误:
1.纯虚类Queue中的DelValue函数名写成了:DecValue,那么在LQueue类中用DelValue作为函数名,从而导致了类型无法实例化的错误.
2.对于LQueue类的测试函数(主函数)中,把对AddValue函数的调用写成了:
value.AddValue,1
等这种情况,从而出现了"构造一个指向成员的指针需要显示使用 address-of运算符('')和限定名.",从而让我重写了好几遍代码都没有编译通过,而当我把value改成指针后再用"->"运算符调用时,仔细看了后面的提示才看出应该用()而不是用逗号这个问题.
上面的这两点错误都可以看出,我把汇编语言和C++语言的语法混淆了,第一个问题是因为我习惯了用dec指针写代码,所以把del写成了dec,然后出现了类型无法实例化的错误;而第二点就更明显的说明了这一点,因为在汇编语言中使用逗号来分隔参数与参数和参数与函数名.而在写C++程序的时候我经常把赋值运算符用mov代替,而调用一个没有返回值的函数时还经常先写call,等等.所以一定要区分两种语言的语法,因为不清楚,没有在任何语言之上分析这些问题的解法,所以才会出现混淆的情况.
本文来源 我爱IT技术网 http://www.52ij.com/jishu/1742.html 转载请保留链接。
- 评论列表（网友评论仅供网友表达个人看法，并不表明本站同意其观点或证实其描述）
-