NOJ数据结构011——循环右移

悠悠 2022-11-17 05:25 224阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]  
本体使用循环队列，申请队列空间时推荐申请n个空间，即不多预留一个空间的方法来编写。如此更加简便，只需要移动front、rear两个指针的位置即可。

代码：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct
    {
        
        int *data;
        int front;
        int rear;
        int m;//队列目前长度
        int n;//队列最长长度
    }SeqQueue;
    
    SeqQueue *seq;
    
    SeqQueue* CreateQueue(int k);           //创建队列
    int IsEmpty(SeqQueue *q);              //判空
    int IsFull(SeqQueue *q);               //判满
    void Push(SeqQueue *q, int item);     //入队
    void Pull(SeqQueue *q);               //出队
    void Circulate(SeqQueue *q, int k);   //循环队列
    void PrintQueue(SeqQueue *q);         //输出队列元素
    
    int main()
    {
        
        int len,k;
        scanf("%d%d", &len, &k);
        seq = CreateQueue(len);
        Circulate(seq, k);
        PrintQueue(seq);
        return 0;
    }
    
    SeqQueue* CreateQueue(int len)
    {
          //创建队列
        SeqQueue *q;
        q = (SeqQueue*) malloc (sizeof(SeqQueue));
        q->n = len;
        q->data = (int*) malloc (sizeof(int) * q->n);
        q ->front = 0;
        q->rear = 0;
        q->m = 0;
        for(int i = 0; i < len; i++) {
        
            int tmp;
            scanf("%d", &tmp);
            Push(q, tmp);
        }
        return q;
    }
    
    int IsEmpty(SeqQueue *q)
    {
          //判空
        if (q->m == 0) {
        
            return 1;
        }
        else {
        
            return 0;
        }
    }
    
    int IsFull(SeqQueue *q)
    {
          //判满
        if (q->m == q->n) {
        
            return 1;
        }
        else {
        
            return 0;
        }
    }
    
    void Push(SeqQueue *q, int item)
    {
               //入队
        if(IsFull(q)) {
        
            printf("full");
            return;
        }
        if(IsEmpty(q)) {
        
            q->data[q->rear] = item;
            q->m++;
        }
        else {
        
            q->rear = (q->rear + 1) % q->n;
            q->data[q->rear] = item;
            q->m++;
        }
    }
    
    void Pull(SeqQueue *q)
    {
             //出队
        if(IsEmpty(q)) {
        
            printf("empty");
            return;
        }
        q->front = (q->front + 1) % (q->n);
        q->m--;
    }
    
    void Circulate(SeqQueue *q, int k)
    {
        
        q->front = (q->front +q->n - k) % (q->n);
        q->rear = (q->rear +q->n - k) % q->n;    //-改为+即循环左移
    }
    
    void PrintQueue(SeqQueue *q)
    {
            //输出队列元素
        if(IsEmpty(q)) {
        
            return;
        }
        int tmp;
        tmp = q->front;
        while (1) {
        
            printf("%d ", q->data[tmp]);
            tmp = (tmp + 1) % q->n;
            if(tmp == q->rear) {
        
                break;
            }
        }
        printf("%d ", q->data[tmp]);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221022/dd2beed39ccc4906842816d5c3bc1fc2.png