c语言数据结构：循环队列解决约瑟夫问题

爱被打了一巴掌 2023-01-16 02:58 107阅读 0赞

### 目录 ###

*  1.函数代码：
 *  2.主函数以及其他结构体定义：

# 1.函数代码： #

void JosephCircle(SqQueue&Q,int n,int m)
    { 
        ElemType e;
        int i=1;
        int Count = n;//用来记录剩下的人数
        while(Count != 1)
        { 
            i = 1;//i用来控制是第几个人报数
            while(i != m)//当i的值不等于m的值时
            { 
                Q.front = (Q.front+1)%(Q.MAXSIZE-1);//因为此时的MAXSIZE比总的人数大1，所以需要减去1
                if(Q.base[Q.front] != 0)//当此时不为0的话，i++用来控制第几个人
                { 
                    i++;
                }
            }
            DeQueue(Q,e);
            while(Q.base[Q.front] == 0)//当此时为0的时候，循环找到下一个不为0的位置
            { 
                Q.front = (Q.front+1)%(Q.MAXSIZE-1);
            }
            printf("%d\t",e);
            Count--;
        }
        DeQueue(Q,e);
        printf("%d\t",e);
    }

# 2.主函数以及其他结构体定义： #

#include<malloc.h>
    #include<stdio.h>
    typedef int ElemType;
    typedef struct
    { 
        ElemType *base;
        int front;
        int rear;
        int MAXSIZE;
    }SqQueue;
    bool InitQueue(SqQueue& Q,int n)
    { 
        Q.base = new ElemType[100];
        if(!Q.base)
        { 
           printf("创建失败！\n");
            return false;
        }
        Q.front=Q.rear=0;
        Q.MAXSIZE = n+1;//MAXSIZE是总人数+1，是为了留出一个空位置来放置rear
        return true;
    }
     
    void QueueTraverse(SqQueue Q)
    { 
    	int i;
    	i=Q.front;
    	while(i!=Q.rear)
    	{ 
    	    printf("%d\t",Q.base[i]);
    		i=(i+1)%Q.MAXSIZE;
    	}
        printf("\n");
    }
     
     
    bool EnQueue(SqQueue& Q,ElemType e)
    { 
        if((Q.rear+1)%Q.MAXSIZE==Q.front)
        { 
           printf("队列已满！\n");
            return false;
        }
        Q.base[Q.rear] = e;
        Q.rear = (Q.rear+1)%Q.MAXSIZE;
        return true;
    }
     
    bool DeQueue(SqQueue& Q,ElemType& e)
    { 
        if(Q.front==Q.rear)
        { 
            printf("队列已满！\n");
            return false;
        }
        e = Q.base[Q.front];
        Q.base[Q.front] = 0;
        Q.front = (Q.front+1)%(Q.MAXSIZE-1);//因为此时的MAXSIZE比总的人数大1，所以需要减去1
        return true;
    }