数据结构第六次作业p134
——11411203张玉
24.
template
void SeqQueue::EnQueue(const T& x){//插入函数
if(IsFull()==true){
maxSize=2*maxSize;
elements[rear]=x;
rear=(rear+1)%maxSize;
}
elements[rear]=x;
rear=(rear+1)%maxSize;
};
template
bool SeqQueue::DeQueue(const T& x){//删除函数if(IsEmpty()==true) return false;
if(rear
maxSize=maxSize/2;
x=elements[front];
front=(front+1)%maxSize;
}
x=elements[front];
front=(front+1)%maxSize;
return true;
};
29.
// 利用优先级队列实现栈和队列
#include
template cla PQueue;//前视的类定义
template cla Stack;
template cla Queue;//优先级队列结点类的定义 template
cla PQueueNode
{
friend cla PQueue;//PQueue类作为友元类定义friend cla Stack;
friend cla Queue;
public:
PQueueNode(T &value, int newpriority, PQueueNode priority(newpriority), link(next) {}//构造函数 * next):data(value),
virtual T GetData() { return data; }//取得结点数据
virtual int GetPriority() { return priority; }//取得结点优先级
virtual PQueueNode * GetLink() { return link; }//取得下一结点地址
virtual void SetData(T& value) { data = value; }//修改结点数据
virtual void SetPriority(int newpriority) { priority = newpriority; } //修改结点优先级
virtual void SetLink(PQueueNode * next) { link = next; }//修改指向下一结点的指针 private:
T data;//数据
int priority;//优先级
PQueueNode *link;//链指针
};
//优先级队列的类定义
template
cla PQueue
{
friend cla Stack;
friend cla Queue;
public:
PQueue():front(NULL), rear(NULL) {}//构造函数
virtual ~PQueue() { MakeEmpty(); }//析构函数
virtual void Insert(T &value, int newpriority);//插入新元素value到队尾 virtual T Remove();//删除队头元素并返回 virtual T Get();//读取队头元素的值 virtual void MakeEmpty();//置空队列
virtual int IsEmpty() { return front == NULL; }//判队列空否private:
PQueueNode *front, *rear;//队头指针, 队尾指针
};template
void PQueue::MakeEmpty()
{
//将优先级队列置空
PQueueNode *q;
while(front != NULL)//链不空时, 删去链中所有结点
{
//循链逐个删除
q = front;
front = front->link;
delete q;
}
rear = NULL;//队尾指针置空
}template
void PQueue::Insert(T &value, int newpriority)
{
//插入函数
PQueueNode *q = new PQueueNode(value, newpriority, NULL);if(IsEmpty())
front = rear = q;//队列空时新结点为第一个结点
else
{
PQueueNode *p = front, *pr = NULL;//寻找q的插入位置
while(p != NULL && p->priority >= newpriority) //队列中按优先级从大到小链接{
pr = p;
p = p->link;
}
if(pr == NULL)
{
//插入在队头位置
q->link = front;
front = q;
}
else
{
q->link = p;
pr->link = q;//插入在队列中部或尾部
if(pr == rear)
rear = q;
}
}
}
//删除队头元素并返回
template
T PQueue::Remove()
{
if(IsEmpty())
return NULL; PQueueNode *q = front;
front = front->link; //将队头结点从链中摘下
T &retvalue = q->data;
delete q;
if(front == NULL)
rear = NULL; return retvalue;
}
//读取队头元素的值
template
T PQueue::Get()
if(IsEmpty())
return NULL;
else
return front->data;
}
//(1) 栈的定义与实现
template
cla Stack:public PQueue
{
//栈类定义
public:
Stack():PQueue() {} //构造函数
void Insert(T & value); //插入新元素value到队尾
};template
void Stack::Insert(T & value)
{
//插入函数
PQueueNode *q = new PQueueNode(value, 0, NULL); if(IsEmpty())front = rear = q;//栈空时新结点为第一个结点
else
{
//插入在前端
q->link = front;
front = q;
}
}// -------------------------- Queue //(2) 队列的定义与实现
template
cla Queue:public PQueue
{
//队列类定义
public:
Queue():PQueue() {}//构造函数
void Insert(T & value);//插入新元素value到队尾
};template
void Queue::Insert(T & value)
{
//插入函数
PQueueNode *q = new PQueueNode(value, 0, NULL);
if(IsEmpty())
front = rear = q;//队列空时新结点为第一个结点
else
rear = rear->link = q;//插入在队尾位置
void main() {
Stack aStack;Queue aQueue;
int n = 1;
aStack.Insert(n);aQueue.Insert(n); }
