2022年数据结构实验三题目和源程序 3.pdf

《2022年数据结构实验三题目和源程序 3.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构实验三题目和源程序 3.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验三 :循环队列基本操作一 、实验目的1熟悉并能实现循环队列的定义和基本操作。2了解用队列解决实际应用问题。二、实验要求1进行队列的基本操作时要注意队列“先进先出”的特性。2复习关于队列操作的基础知识。3编写完整程序完成下面的实验内容并上机运行。4整理并上交实验报告。三、实验内容1任意输入队列长度和队列中的元素值，构造一个顺序循环队列，对其进行清空、插入新元素、返回队头元素以及删除队头元素操作。2约瑟夫环的实现：设有n 个人围坐在圆桌周围，现从某个位置i 上的人开始报数，数到m 的人就站出来。下一个人，即原来的第m+1 个位置上的人，又从 1 开始报数，再是数到m 的人站出来。依次重复下去，

2、直到全部的人都站出来， 按出列的先后又可得到一个新的序列。由于该问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus 问题。例如：当 n=8,m=4,i=1 时，得到的新序列为：4，8，5，2，1，3，7，6 编写程序选择循环队列作为存储结构模拟整个过程，并依次输出出列的各人的编号。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - /*- * 03_循环队列 .cpp - 循环队列基本操作*

3、对循环队列的每个基本操作都用单独的函数来实现* 水上飘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 InitQ

4、ueue(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.baseQ.rear = e; Q.rear = (Q.rear + 1) % MAXQSIZE; /给队列随机赋m 个值名师资料总结 - - -精品资料欢迎

5、下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - 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 ClearQue

6、ue(SqQueue &Q) Q.front = Q.rear = 0; /若队列不空，则删除Q 的队头元素，并返回其值int DeleteFront(SqQueue &Q) int e; if(Q.front = Q.rear) cout 队列为空。 endl; e = Q.baseQ.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.

7、rear) if(k % 5 = 0) cout endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - cout setw(5) Q.basek; 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; /

8、第一个元素位置while(Q.front != Q.rear) for(int i = 1; i m; i+) /移动 m-1 次if(p = Q.rear) / 保证 Q.basep中有值p = Q.front; p+; if(p = Q.rear) p = Q.front; cout setw(5) Q.basep; if(j % 5 = 0) cout endl; j+; k = p; if(k+1) = Q.rear) / 删除 Q.basep中的值 Q.rear = (MAXQSIZE + (Q.rear-1) % MAXQSIZE; continue; else while(k+1

9、) Q.rear) /Q.basep之后的值依次往前移 Q.basek = Q.basek+1; k+; Q.rear = (MAXQSIZE + (Q.rear-1) % MAXQSIZE; cout endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - /第一题void FirstTitle() SqQueue Q; cout 第一题开始： endl; cout m; InitQueue(Q); Evaluate(Q,

10、m); OutPut(Q); cout 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 n; cout m; Josephus(Q,m,n); int _tmain(int argc, _TCHAR* argv) srand(time(NULL); FirstTitle(); cout - endl; SecondTitle(); cin.get(); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -