實驗目的
- 深入理解佇列的“先進先出”特性；
- 掌握鏈佇列及回圈佇列結構型別定義及其基本演算法;
- 能在實際問題背景下靈活運用佇列，
實驗內容
設有n個人站成一排，從左向右的編號分別為1~n，現在從左往右報數“1，2，1，2，…”,數到“1”的人出列,數到“2”的立即站到隊伍的最右端，報數程序反復進行，直到n個人都出列為止，要求給出他們的出列順序，
.cpp檔案后綴名
演算法思想
- 讓所有元素入隊
- 當佇列不為空時，第奇數個元素出隊輸出，第偶數個元素重新進隊
Source Code
#include<stdio.h>
#include<malloc.h>
#define MaxSize 100
typedef int ElemType;
typedef struct
{
ElemType data[MaxSize]; //存放隊中元素
int front,rear; //隊頭和隊尾指標
}SqQueue;
//初始化佇列
void InitQueue(SqQueue *&q)
{
q=(SqQueue *)malloc(sizeof(SqQueue));
q->front=q->rear=0;
}
//進隊
bool enQueue(SqQueue *&q,ElemType e)
{
if((q->rear+1)%MaxSize==q->front)
return false;
q->rear = (q->rear+1)%MaxSize;
q->data[q->rear] = e;
return true;
}
//出隊
bool deQueue(SqQueue *&q,ElemType &e)
{
if(q->front==q->rear)
return false;
q->front=(q->front+1)%MaxSize;
e=q->data[q->front];
return true;
}
//判佇列是否為空
bool QueueEmpty(SqQueue *q)
{
return (q->front==q->rear);
}
//銷毀佇列
void DestroyQueue(SqQueue *&q)
{
free(q);
}
//報數
void Bs(int n)
{
int i;
int count=1; //count用來記第幾個元素
SqQueue *q;
InitQueue(q);
for(i=1;i<=n;i++)
{
enQueue(q,i);
}
while(!QueueEmpty(q))
{
deQueue(q,i);
if(count%2==0) //第偶數個元素時，進隊
enQueue(q,i);
else
printf("%d ",i); //第奇數個元素時，出隊輸出
count++;
}
printf("\n");
DestroyQueue(q);
}
int main(void)
{
int n;
printf("輸入n的個數：");
scanf("%d",&n);
Bs(n);
return 0;
}
Computational Results
Analyze
在環形佇列q中
- 設定隊空條件是：q->rear == q->front
- 設定隊滿條件是：(q->rear+1)%MaxSize == q->front
- 佇列中元素個數：(rear-front+MaxSize)%MaxSize
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/205355.html
標籤：其他