数据结构实验三（循环队列基本操作）题目和源程序.doc

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：0.03M 资料格式：doc 举报版权申诉

sspiao123-4195956-4744300845223433922.doc.pdf-第1页.png

第1页 / 共6页

sspiao123-4195956-4744300845223433922.doc.pdf-第2页.png

第2页 / 共6页

sspiao123-4195956-4744300845223433922.doc.pdf-第3页.png

第3页 / 共6页

sspiao123-4195956-4744300845223433922.doc.pdf-第4页.png

第4页 / 共6页

sspiao123-4195956-4744300845223433922.doc.pdf-第5页.png

第5页 / 共6页

sspiao123-4195956-4744300845223433922.doc.pdf-第6页.png

第6页 / 共6页

文本预览

实验三:循环队列基本操作一、实验目的 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 编写程序选择循环队列作为存储结构模拟整个过程，并依次输出出列的各人的编号。

03_循环队列.cpp -- 循环队列基本操作 /*---------------------------------------- * * 对循环队列的每个基本操作都用单独的函数来实现 * 水上飘 2009 年写 ----------------------------------------*/ // ds03.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include #include #include #include #define MAXQSIZE 100 //最大队列长度 using namespace std; typedef struct { int *base; //初始化的动态分配存储空间 int front; //头指针，若队列不空，指向队列头元素 int rear; //尾指针，若队列不空，指向队列尾元素的下一个位置 }SqQueue; //构造一个空队列 void InitQueue(SqQueue &Q) { Q.base = (int *)malloc(MAXQSIZE * sizeof(int)); if(!Q.base) cout << "存储分配失败。" << endl; Q.front = Q.rear = 0; } //插入元素 e 为新的队尾元素 void InsertEnd(SqQueue &Q, int e) { if((Q.rear + 1) % MAXQSIZE == Q.front) cout << "队列已满。" << endl; Q.base[Q.rear] = e; Q.rear = (Q.rear + 1) % MAXQSIZE; } //给队列随机赋 m 个值

void Evaluate(SqQueue &Q, int m) { int k; for(int i = 0; i < m; i++) { k = rand() % 100; InsertEnd(Q,k); } } //返回 Q 的元素个数，即队列的长度 int QueueLength(SqQueue Q) { return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE; } //清空队列 void ClearQueue(SqQueue &Q) { Q.front = Q.rear = 0; } //若队列不空，则删除 Q 的队头元素，并返回其值 int DeleteFront(SqQueue &Q) { int e; if(Q.front == Q.rear) cout << "队列为空。" << endl; e = Q.base[Q.front]; Q.front = (Q.front + 1) % MAXQSIZE; return e; } //输出循环队列 void OutPut(SqQueue &Q) { if(Q.front == Q.rear) cout << "队列为空。" << endl; int k; k = Q.front; while(k != Q.rear) { if(k % 5 == 0) cout << endl;

cout << setw(5) << Q.base[k]; k++; } cout << endl; } void Josephus(SqQueue &Q, int m, int n) { int p,k,j = 1; for(int i = 1; i <= n; i++) //给队列中的人依次赋序号 InsertEnd(Q,i); p = Q.front; //第一个元素位置 while(Q.front != Q.rear) { for(int i = 1; i < m; i++) { //移动 m-1 次 if(p == Q.rear) //保证 Q.base[p]中有值 p = Q.front; p++; if(p == Q.rear) p = Q.front; } cout << setw(5) << Q.base[p]; if(j % 5 == 0) cout << endl; j++; k = p; if((k+1) == Q.rear) //删除 Q.base[p]中的值 { Q.rear = (MAXQSIZE + (Q.rear-1)) % MAXQSIZE; continue; } else while((k+1) < Q.rear) //Q.base[p]之后的值依次往前移 { Q.base[k] = Q.base[k+1]; k++; } Q.rear = (MAXQSIZE + (Q.rear-1)) % MAXQSIZE; } cout << endl; }

//第一题 void FirstTitle() { SqQueue Q; cout << "第一题开始：" << endl; cout << "输入循环队列的元素个数："; int m,n,k; cin >> m; InitQueue(Q); Evaluate(Q,m); OutPut(Q); cout << "输入插入队尾的元素："; cin >> n; InsertEnd(Q,n); OutPut(Q); k = DeleteFront(Q); cout << "删除队头元素成功，其值为：" << k << endl; ClearQueue(Q); cout << "队列已清空。" << endl; } //第二题 void SecondTitle() { cout << "第二题开始：" << endl; SqQueue Q; InitQueue(Q); int m,n; cout << "输入人数："; cin >> n; cout << "输入循环数："; cin >> m; Josephus(Q,m,n); } int _tmain(int argc, _TCHAR* argv[]) { srand(time(NULL)); FirstTitle(); cout << "------------------------------------------------------------" << endl; SecondTitle(); cin.get(); return 0; }

分享到：

赞收藏

资料库

数据结构实验三（循环队列基本操作）题目和源程序.doc

相关推荐

课程资源

热门标签

最新资料