数据结构实习报告_数据结构程序实习报告
数据结构实习报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构程序实习报告”。
数据结构第六次作业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);}
