当前位置：文档库 › 顺序循环队列和链式队列的类定义和实现

顺序循环队列和链式队列的类定义和实现

顺序循环队列的类定义（数组）和实现

程序构思：

本程序将data表示成数据类型为datatype的数组，front为顺序循环队列的对头指示器，rear 为顺序循环队列的队尾指示器。首先给出了顺序循环队列的类定义，然后给出了函数实现部分，最后测试，输出结果。

程序代码：

queue1.h

#define QueueSize 10

typedef int datatype;

class Cirqueue

{

private:

int front;

int rear;

int count;

datatype data[QueueSize];

public:

//构造函数

Cirqueue();

//判断栈是否为空

bool queueEmpty();

//判断栈否为满

bool queueFull();

//栈存在则返回栈的元素个数，即栈的长度

int QueueLength();

//取队列的头元素

datatype queueFront();

//入队

void enqueue(datatype);

//出对

datatype dequeue();

};

Queue1.cpp

#include

using namespace std;

#include "queue1.h"

//构造函数

Cirqueue::Cirqueue()

{

front=0;

rear=0;

count=0;

}

//判断栈是否为空

bool Cirqueue::queueEmpty()

{

if(count==0)

return true;

else

return false;

}

//判断栈否为满

bool Cirqueue::queueFull()

{

if(count==QueueSize)

return true;

else

return false;

}

//栈存在则返回栈的元素个数，即栈的长度int Cirqueue::QueueLength()

{

return count;

}

//取队列的头元素

datatype Cirqueue::queueFront()

{

if (queueEmpty()==true)

{

cout<<"队列为空！"<

exit(1);

}

return data[front];

}

//入队

void Cirqueue::enqueue(datatype x) {

if (queueFull()==true)

{

cout<<"队列已满！"<

exit(1);

}

data[rear]=x;

count++;

rear=(rear+1)%QueueSize;

}

//出对

datatype Cirqueue::dequeue()

{

datatype item;

if (queueEmpty()==true)

{

cout<<"队列为空"<

exit(1);

}

item=data[front];

count--;

front=(front+1)%QueueSize;

return item;

}

Queue1m.cpp

#include

#include "queue1.h"

void main()

{

cout<<"-------------queue1---------------"<

Cirqueue MyQueue;

int i,x,m;

cout<<"输入随机产生的种子数：";

cin>>m;

srand(m);

for (i=0;i

{

x=rand()%100;

MyQueue.enqueue(x);

}

cout<<"循环队列的长度"<

cout<<"输出循环队列："<

while (MyQueue.queueEmpty()!=true)

{

x=MyQueue.dequeue();

cout<

}

cout<

}

程序运行结果：

注：本程序可将data[QueueSize]改成指针类型datatype *data,然后在构造函数中对data进行初始化。

链式队列的类定义和实现

程序构思：

本程序将front表示成数据类型为结构体queuenode的指针变量，front为链式队列的对头指示器，rear为链式队列的队尾指示器。首先给出了链式队列的类定义，然后给出了函数实现部分，最后测试，输出结果。

程序代码：

Linqueue.h

#define QueueSize 10

typedef int datatype;

typedef struct QueueNode

{

datatype data;

struct QueueNode *next;

}queuenode;

class linkqueue

{

private:

queuenode *front;

queuenode *rear;

int count;

public:

//构造函数

linkqueue();

//析构函数

~linkqueue();

//判断栈是否为空

bool queueEmpty();

//判断栈否为满

bool queueFull();

//栈存在则返回栈的元素个数，即栈的长度

int QueueLength();

//取队列的头元素

datatype queueFront();

//入队

void enqueue(datatype);

//出对

datatype dequeue();

};

Linqueue.cpp

#include

using namespace std;

#include "linqueue.h"

//构造函数

linkqueue::linkqueue()

{

front=rear=NULL;

count=0;

}

//析构函数

linkqueue::~linkqueue()

{

front=rear=NULL;

}

//判断栈是否为空

bool linkqueue::queueEmpty()

{

return front==NULL&&rear==NULL;

}

//判断栈否为满

bool linkqueue::queueFull()

{

return count==QueueSize;

}

//栈存在则返回栈的元素个数，即栈的长度int linkqueue::QueueLength()

{

return count;

}

//取队列的头元素

datatype linkqueue::queueFront()

{

if (queueEmpty()==true)

{

cout<<"队列为空！"<

exit(1);

}

return front->data;

}

//入队

void linkqueue::enqueue(datatype x)

{

if (queueFull()==true)

{

cout<<"队列已满！"<

exit(1);

}

queuenode *p=(queuenode*)malloc(sizeof(queuenode));

if (!p)

{

cout<<"内存不足！"<

exit(1);

}

p->data=x;

p->next=NULL;

if (!queueEmpty())

{

rear->next=p;

rear=p;

}

else

front=rear=p;

count++;

}

//出对

datatype linkqueue::dequeue()

{

datatype item;

if (queueEmpty()==true)

{

cout<<"队列为空"<

exit(1);

}

queuenode *p;

p=front;

item=front->data;

front=p->next;

if (rear==p)

{

rear=NULL;

}

delete p;

count--;

return item;

}

Linqueuem.cpp

#include

#include "linqueue.h"

void main()

{

cout<<"-------------linkqueue---------------"<

linkqueue MyQueue;

int i,x,m;

cout<<"输入随机产生的种子数：";

cin>>m;

srand(m);

for (i=0;i

{

x=rand()%100;

MyQueue.enqueue(x);

}

cout<<"循环队列的长度"<

cout<<"输出循环队列："<

while (MyQueue.queueEmpty()!=true)

{

x=MyQueue.dequeue();

cout<

}

cout<

}

程序运行结果：

C语言之循环队列的基本操作

1）：循环队列的基本操作 #include #include #define OK 1 #define ERROR 0 typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等typedef int QElemType; #define MAXQSIZE 100 // 最大队列长度(对于循环队列，最大队列长度要减1) typedef struct { QElemType *base; // 初始化的动态分配存储空间 int front; // 头指针,若队列不空,指向队列头元素 int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置 }SqQueue; Status InitQueue(SqQueue &Q) { Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q.base) { return ERROR; } Q.front=Q.rear=0; return OK; } Status EnQueue(SqQueue &Q,QElemType e) { if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK; } Status DeQueue(SqQueue &Q, QElemType &e) { if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; return OK; }

数据结构实验——队列(附程序)

?、实验目的 1. 了解队列的特性。 2. 掌握队列的顺序表示和实现。 3. 掌握队列的链式表示和实现。 1、实验内容实验3. 3队列的顺序表示和实现编写一个程序实现顺序队列的各种基本运算（采用循环队列），主程序，完成如下功能： ⑴ 初始化队列。 ⑵ 建立顺序队列。 ⑶ 入队。 ⑷ 岀队。 (5) 判断队列是否为空。 ⑹ 取队头元素。 (7) 遍历队列。实验3.4队列的链式表示和实现编写一个程序实现链队列的各种基本运算，并在此基础上设计能： (1) 初始化并建立链队列 ⑵ 入链队列。 ⑶ 岀链队列。 ⑷ 遍历链队列。 #i nclude #in clude #defi ne MAXQSIZE 100 typedef struct { int *base; int front; int rear; }SqQueue;实验三队列并在此基础上设计一个个主程序，完成如下功

int Ini tQueue(SqQueue &Q) { Q.base=(i nt*)malloc(MAXQSIZE*sizeof(i nt)); if(!Q.base)exit(O); Q.fro nt=Q.rear=0; return 0; }//初始化顺序队列 int QueueLe ngth(SqQueue Q) { int i; i=(Q.rear-Q.fro nt+MAXQSIZE)%MAXQSIZE; printf(“队列长度％5d\n",i); if(i)printf(" 队列非空“)； else printf(" 队列为空"); return 0; }//判断队列是否为空 int En Queue(SqQueue &Q,i nt e) { if((Q.rea 叶1)%MAXQSIZE==Q.fro nt)return 0; Q.base[Q.rear]=e; Q.rear=(Q.rea r+1)%MAXQSIZE; return 0; }//将元素e入队 int DeQueue(SqQueue & Q,i nt e) { if(Q.fro nt==Q.rear)return 0; e=Q.base[Q.fro nt]; prin tf("%5d\n",e); Q.fron t=(Q.fr on t+1)%MAXQSIZE; return 0; }// 删除元素e并返回其值

队列实验报告

一．实验项目名称循环队列和链式队列的创建二、实验目的 1、掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等， 2、队列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵活应用。三、实验内容 1．链式队列的实现和运算 2．循环队列的实现和运算四、主要仪器设备及耗材 VC++6.0运行环境实现其操作五．程序算法 (1) 循环队列操作的算法 1>进队列 V oid enqueue (seqqueue &q, elemtype x) { if ((q.rear+1)%maxsize = = q.front) cout<<”overflow”; else { q.rear=(q.rear+1)%maxsize; //编号加1或循环回第一个单元 q.queue[q.rear]=x; } } 2>出队列 V oid dlqueue(seqqueue &q ) { if (q.rear= =q.front) cout<<”underflow”; else q.front =(q.front+1)%maxsize; } 3>取对头元素

elemtype gethead(seqqueue q ) { if (q.rear= =q.front) { cout<<”underflow”； return NULL;} else return q.queue[(q.front+1)%maxsize]; //front指向队头前一个位置 } 4>判队列空否 int empty(seqqueue q ) { if (q.rear= =q.front) reurn 1; else return 0; } （2）.链队列操作的算法 1>.链队列上的初始化 void INIQUEUE( linkqueue &s) { link *p; p=new link; p->next=NULL; //p是结构体指针类型，用-> s.front=p; //s是结构体变量，用. s.rear=p; //头尾指针都指向头结点 } 2>.入队列 void push(linkqueue &s, elemtype x) { link *p; //p是结构体指针类型，用-> p=new link; p->data=x; p->next=s.rear->next; //s是结构体变量，用. s.rear->next=p; s.rear=p; //插入最后 } 3>判队空 int empty( linkqueue s ) { if (s.front= =s.rear) return 1; else return 0; } 4>.取队头元素 elemtype gethead( linkqueue s ) { if (s.front= =s.rear) return NULL; else retuen s.front->next->data; }

顺序队的基本操作

上机实验报告学院：计算机与信息技术学院专业：计算机科学与技术(师范）课程名称：数据结构实验题目：顺序队的基本操作班级序号：师范1班学号： 2731 学生姓名：邓雪指导教师：杨红颖完成时间： 2015年12月25号

一、实验目的： 1．熟悉掌握队的定义、结构及性质；? 2. 熟练掌握循环队列的操作及应用,掌握循环队列的入队和出队等基本操作。? 3. 加深对队列结构的理解，逐步培养解决实际问题的编程能力二、实验环境： Windows Microsoft Visual c++ 三、实验内容及要求：掌握队列的概念及性质，并建立顺序队，实现如下功能： 1.建立一个顺序队 2.输出队 3.求队长 4.判队空 5.取队头 6.入队 7.出队 8. 清空栈四、概要设计： 1、通过循环，由键盘输入一串数据。创建并初始化一个顺序队。 2、编写实现相关功能函数，完成子函数模块如下。 3、调用子函数，实现菜单调用功能，完成顺序表的相关操作。

#include <> #include <> #define maxsize 1024 typedef int datatype; //定义结构体 typedef struct { datatype data[maxsize]; int front,rear; }sequeue; sequeue *sq; //建立顺序队 sequeue *SET() { sequeue *sq; datatype x; sq=(sequeue *)malloc(sizeof(sequeue)); sq->front=maxsize-1; sq->rear=maxsize-1; printf("请输入要存入的结点值(以0结尾)\n"); scanf("%d",&x); while(x!=0) { sq->rear=(sq->rear+1)%maxsize; sq->data[sq->rear]=x; scanf("%d",&x); } printf("顺序队输入成功\n\n"); return sq; }

环形队列实现原理链式实现

环形队列实现原理/链式实现环形队列是在实际编程极为有用的数据结构,它有如下特点。它是一个首尾相连的FIFO的数据结构，采用数组的线性空间,数据组织简单。能很快知道队列是否满为空。能以很快速度的来存取数据。因为有简单高效的原因，甚至在硬件都实现了环形队列. 环形队列广泛用于网络数据收发，和不同程序间数据交换（比如内核与应用程序大量交换数据,从硬件接收大量数据）均使用了环形队列. 一.环形队列实现原理 ------------------------------------------------------------ 内存上没有环形的结构，因此环形队列实上是数组的线性空间来实现。那当数据到了尾部如何处理呢？它将转回到0位置来处理。这个的转回是通过取模操作来执行的。因此环列队列的是逻辑上将数组元素q[0]与q[MAXN-1]连接，形成一个存放队列的环形空间。为了方便读写，还要用数组下标来指明队列的读写位置。head/tail.其中head指向可以读的位置，tail指向可以写的位置。环形队列的关键是判断队列为空，还是为满。当tail追上head时，队列为满时，当head 追上tail时，队列为空。但如何知道谁追上谁。还需要一些辅助的手段来判断. 如何判断环形队列为空，为满有两种判断方法。 1.是附加一个标志位tag 当head赶上tail，队列空，则令tag=0, 当tail赶上head，队列满，则令tag=1,

2.限制tail赶上head，即队尾结点与队首结点之间至少留有一个元素的空间。队列空：head==tail 队列满：(tail+1)% MAXN ==head 二.附加标志实现算法采用第一个环形队列有如下结构 typedef struct ringq { int head; /* 头部，出队列方向*/ int tail; /* 尾部，入队列方向*/ int tag ; int size ; /* 队列总尺寸*/ int space[RINGQ_MAX]; /* 队列空间*/ }RINGQ; 初始化状态: q->head = q->tail = q->tag = 0; 队列为空:(q->head == q->tail) && (q->tag == 0) 队列为满: ((q->head == q->tail) && (q->tag == 1)) 入队操作:如队列不满，则写入 q->tail = (q->tail + 1) % q->size ; 出队操作：如果队列不空，则从head处读出。下一个可读的位置在 q->head = (q->head + 1) % q->size 完整代码头文件ringq.h #ifndef __RINGQ_H__ #define __RINGQ_H__ #ifdef __cplusplus extern "C" { #endif #define QUEUE_MAX 20 typedef struct ringq { int head; /* 头部，出队列方向*/ int tail; /* 尾部，入队列方向*/ int tag ; /* 为空还是为满的标志位*/ int size ; /* 队列总尺寸*/ int space[QUEUE_MAX]; /* 队列空间*/ } RINGQ; /* 第一种设计方法: 当head == tail 时，tag = 0 为空，等于= 1 为满。 */

顺序循环队列表实现

————————————————————————————————作者：————————————————————————————————日期：

队列的基本概念队列也是一种特殊的线性表，队列的数据元素以及数据元素间的逻辑关系与线性表完全相同，其差别是线性表允许在任意位置插入和删除，而队列只允许在其一端进行插入操作，在其另一端进行删除操作。队列中允许进行插入操作的一端称为队尾。允许进行删除操作的一端称为队头。队头和队尾分别由队头指针和队尾指针指示。队列的插入操作称为入队列，队列的删除操作称为出队列。最先入队列的元素总是最先出队列，所以队列也称为先进先出表。下图是一个一次向队列中插入数据元素a0,a1,a2,….an-1后的示意图，其中，a0是当前队头数据元素，an-1是当前队尾的数据元素。队头队尾 a0 a1 a2 ……an-1 <-出<-入队列抽象数据类型数据集合：队列的数据集合可以表示为a0,a1,a2,a3….an-1，每个数据元素的数据类型为DataType。操作集合：（1）初始化QueueInitiate(Q)：初始化队列Q （2）非空否QueueNotEmpty(Q)：队列Q非空否，若队列非空，函数返回值为1。否则，函数返回0。（3）入队列QueueAppend(Q,x)：在队列Q的队尾插入数据元素x。入队列成功返回1；失败则返回0。（4）出队列QueueDelete(Q,d)：把队列Q的队头数据元素删除并由参数d带回。如出队列成功，返回1；失败则返回0。（5）取队头数据元素QueueGet(Q,d)：取队头数据元素并由参数d带回。如取到数据元素返回1，否则，返回0。顺序队列顺序存储结构的队列称作顺序队列

试验 --循环队列的基本操作及应用

数据结构实验报告 ----试验三循环队列的基本操作及应用一、问题描述：熟悉并掌握循环队列的相关操作，自己设计程序，实现循环队列的构造、清空、销毁及队列元素的插入和删除等相关操作。二、数据结构设计： #define MAXQSIZE 10 //最大队列长度 struct SqQueue { QElemType *base; //初始化动态分配存储空间 Int front; // 头指针，若队列不空，只想对列头元素 int rear; //尾指针，若队列不空，指向队列尾元素的 //下一个位置 }; 三、功能设计：程序中所涉及到的函数如下： Status InitQueue(SqQueue &Q) //构造一个空队列Q Status DestroyQueue(SqQueue &Q) //销毁队列Q,Q不再存在 Status ClearQueue(SqQueue &Q) //将Q清为空队列 Status QueueEmpty(SqQueue Q) //若队列Q为空队列，则 //返回TRUE，否则返回FALSE int QueueLength(SqQueue Q) //返回Q的元素个数，即队列长度Status GetHead(SqQueue Q,QElemType &e)//若队列不空，则用e返回Q的对 //头元素，并返回OK，否则返回ERROR Status EnQueue(SqQueue &Q,QElemType e)//插入元素e为Q的新的队尾元素Status DeQueue(SqQueue &Q,QElemType &e)//若队列不空，则删除Q的队头 //元素，用e返回其值，并返回 //OK，否则返回ERROR Status QueueTraverse(SqQueue Q,void(*vi)(QElemType))//从队头到队尾依次 //对队列Q中每个元素调用函数 //vi()。一旦vi失败，则操作失败四、源程序： // c1.h (程序名) #include #include #include // malloc()等 #include // INT_MAX等 #include // EOF(=^Z或F6),NULL

队列的表示及实现实验报告

陕西科技大学实验报告班级信工082 学号200806030202 姓名李霄实验组别实验日期2010-12-20 室温报告日期2010-12-20 成绩报告内容：(目的和要求，原理，步骤，数据，计算，小结等) 实验名称：实验三队列的表示及实现实验目的： 1、通过实验进一步理解队列的“先进先出”特性。 2、掌握队列的逻辑结构及顺序存储结构和链式存储结构。 3、熟练运用C语言实现队列的基本操作。 4、灵活运用队列解决实际问题。实验内容： 1、实现链队列，并编写主函数进行测试。测试方法为：依次10、20、 30、40，然后，出对3个元素。再次入队50、60，然后出队3个元素。查看屏幕上显示的结果是否与你分析的结果一致。 2、在1的基础上，再出队1个元素。查看屏幕上显示的结果是否与你分析的结果一致。 3、编写主函数比较取队头元素操作和出队操作。实验学时：2学时实验程序 #include "stdio.h" #include "conio.h" typedef int DataType; typedef struct { DataType data; struct QNode* next; }LQNode,*PQNode; typedef struct { PQNode front,rear; }LinkQueue; int InitQueue(LinkQueue *Q) { Q->front=Q->rear=(PQNode)malloc(sizeof(LQNode));

if (!Q->front){printf("errors\n");return 0;} Q->front->next=NULL; return 1; } int QueueEmpty(LinkQueue Q) { if(Q.front==Q.rear) return 1; else return 0; } int EnQueue(LinkQueue *Q,DataType e) { PQNode p; p=(PQNode)malloc(sizeof(LQNode)); if(!p) { printf("\n\nerrors\n\n"); return 0; } p->data=e; p->next=NULL; Q->rear->next=p; Q->rear=p; return 1; } int DeQueue(LinkQueue *Q,DataType *e) { PQNode p; if( Q->front==Q->rear) { printf("\nerrors\n");

实验二栈与队列操作实验题目

实验二栈与队列操作实验目的： (1)理解栈与队列的结构特征和运算特征，以便在实际问题背景下灵活运用。 (2)了解复杂问题的递归算法设计。本次实验中，下列实验项目选做一。 1、顺序栈的基本操作 [问题描述] 设计算法，实现顺序栈的各种基本操作 [基本要求] （1）初始化栈s。（2）从键盘输入10个字符以$结束，建立顺序栈。（3）从键盘输入1个元素，执行入栈操作。（4）将栈顶元素出栈。（5）判断栈是否为空。（6）输出从栈顶到栈底元素。要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 2、链栈的基本操作 [问题描述] 设计算法，实现链栈的各种基本操作 [基本要求] （1）初始化栈s。（2）从键盘输入10个字符以$结束，建立带头结点的链栈。（3）从键盘输入1个元素，执行入栈操作。（4）完成出栈操作。（5）判断栈是否为空。（6）输出从栈顶到栈底元素。（7）输出链栈的长度。要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 3、循环队列的基本操作 [问题描述] 设计算法，实现循环顺序队列的建立、入队、出队等操作。 [基本要求] （1）从键盘输入10个字符以$结束，建立循环队列，并显示结果。（2）从键盘输入1个元素，执行入队操作，并显示结果。（3）将队头元素出队，并显示结果。（4）要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。

4、只用尾指针表示的循环链表队列的综合操作 [问题描述] 假设以带头结点的的循环链表表示队列，并且只设一个指针指向队尾元素的结点（注意不设头指针），试编写队列初始化、入队、出队函数。 [基本要求及提示] （1）首先定义链表结点类型。（2）编写带头结点的循环链表的初始化函数，只用尾指针表示。（3）编写入队函数、出队函数。（4）在主函数中编写菜单（1.初始化；2.入队；3.出队；4.退出），调用上述功能函数。 5、用标志域表示队空队满状态的循环队列的综合操作 [问题描述] 要求循环队列不损失一个空间全部都得到利用，设置一个标志域tag，以0和1来区分当队头与队尾指针相同时队列状态的空和满，试编写与此结构相对应的入队和出队操作。 [基本要求及提示] （1）教材中为区分当队头与队尾指针相同时队列状态的空和满，以牺牲一个空间的代价来实现的，空：Q->front==Q->rear,满：（Q->rear+1）%MAXSIZE==Q->front。（2）本题不损失一个空间全部都得到利用，为此如下定义循环队列类型： Typedef struct { QueueElementType element[MAXSIZE]; int front; int rear; int tag; }SeqQueue; 此时，循环队列空和满的条件分别为： Q->front==Q->rear&&tag==0 和 Q->front==Q->rear&&tag==1 （3）编写入队函数、出队函数。（4）在主函数中编写菜单（1.入队；2.出队；3.退出），调用上述功能函数。 6、利用辅助数组进行栈的逆置 [问题描述] 利用辅助栈将栈中的元素逆置。 [基本要求及提示] 在主函数中编写菜单（1.入栈；2.出栈；3.逆置；4.退出）调试运行程序。 7、利用辅助栈进行队列的逆置 [问题描述] 利用辅助栈进行队列元素逆置。 [基本要求及提示] 在主函数中编写菜单（1.入队；2.出队；3.逆置；4.退出）调试运行程序。 8、Hanoi塔问题

4 队列的链式结构实现

>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>> >>>>>> >>>>>>>>>>>>>>> >>> > >>> >>> > >>> >> >>> ! "# $ %&'() *+,-./01 >> >>> %&2() 3+,-.401 > >>> >> >>> /%5

4%5 >>> 67 >>> 89 :;< >>> + => ? => >>> @ABCDE >>> FE >>> GH >>> IJ >>> KL M N >>>

OPQR.%53SDTUVW%5 X3 %5YZ:;<3[2\]^.W%5%& _`a b c d !# 3efg?h 89 :;< >>>> ijk"!lmDWnopq3TUrstpquv FEwR stxyijk"!lm + =>pq zz++ N zz >>> zz z zz++ zz >>>> zz z

zz zzzczz zz z GH zGH zz 67pq z 67zz zcz IJ%? pq zz+tIJ zzz zz z >>> > > zz z zz Nzzzcz >>>> zzJzz zzcz ? =>pq zz+? N zz

zz z >>>> > z? zz zcz >>>> ztz? zz3? zzzzcz 67pq z? uzz 67zz zcz GH z? uzzGH zz FE pq GH zFEuGH zz

>>> > :;< >>> >> >> >> >>> > > > /%5%&/) > 4%5%&/) > + =>*401 z + QRz+++3SD++++? => KLz+.

实验4顺序循环队列基本操作

实验4: 顺序循环队列基本操作一、实验目的 1．熟悉并能实现顺序循环队列的定义和基本操作。 2．了解用队列解决实际应用问题。二、实验要求 1．进行队列的基本操作时要注意队列“先进先出”的特性。 2．复习关于栈操作的基础知识。 3．编写完整程序完成下面的实验内容并上机运行。 4．整理并上交实验报告。三、实验内容 1．任意输入队列长度和队列中的元素值，构造一个队列，对其进行清空、插入新元素、返回队头元素以及删除队头元素操作。 2．约瑟夫环的实现：设有n个人围坐在圆桌周围，现从某个位置i 上的人开始报数，数到m 的人就站出来。下一个人，即原来的第m+1个位置上的人，又从1开始报数，再是数到m的人站出来。依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。由于该问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为 Josephus 问题。例如：当n=8,m=4,i=1时，得到的新序列为： 4，8，5，2，1，3，7，6 编写程序选择循环队列（也可换为自己熟悉的数据结构）作为存储结构模拟整个过程，并依次输出出列的各人的编号。 3．(选做实验)设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。程序编写提示：以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。