循环队列前后指针超出数组大小

Question

循环队列的前指针和后指针超出了数组的大小，这可以在打印语句中看到输入的大小为 3，其中指针指向值 4，如果 6.It 会有所帮助有人可以指出我哪里出错了。我测试的输入是 20 (size of number), 3(size of queue) ,7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 (numbers) 。输出应该是页面错误 - 15 和命中 - 5 但它是 9 和 11.

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

struct queue{
    int size;
    int f;
    int r;
    int *arr;
};

int isEmpty(struct queue *q)
{
    if(q->f == -1 || q->r == -1)
    {
        return 1;
    }
    return 0;  
}

int isFull(struct queue *q)
{
    if(q->r == q->f-1 || (q->f == 0 && q->r == q->size - 1))
    {
        return 1;
    }
    return 0;  
}

void enqueue(struct queue *q ,int data)
{
    // if(isFull(q))
    // {
    //     printf("Queue Overflow\n");
    //     return;
    // }
    if(isEmpty(q))
    {
        q->f=0;
        q->r=0;
    }
    else if(q->r == q->size-1 && q->f !=0)
    {
        q->r = 0;
    }
    else
    {
        q->r = q->r + 1;
    }
    q->arr[q->r] = data;
    // printf("%d\n",q->arr[q->r]);
}

void dequeue(struct queue *q)
{
    // int val = -1;

    // if(isEmpty(q))
    // {
    //     printf("Queue Underflow\n");
    //     return val;
    // }

    // val = q->arr[q->f];

    if(q->r == q->f)
    {
        q->f = -1;
        q->r = -1;
    }
    else if(q->f == q->size-1)
    {
        q->f = 0;
    }
    else
    {        
        q->f = q->f + 1;
    }    
    // return val;
}

int isPresent(struct queue *q ,int data)
{
    for(int i=q->f;i!=q->r;i++)
    {
        if(i == q->size-1)
        {
            if(data == q->arr[i])
            {
                return 1;
            }
            i = -1;
            continue;
        }
        if(data == q->arr[i])
        {
            return 1;
        }
    }
    if(data == q->arr[q->r])
    {
        return 1;
    }

    return 0;
}

int main(void)
{
    int m,n;
    int hit=0,miss=0;
    struct queue *q;
    q->f = -1;
    q->r = -1;

    printf("Enter the amount of numbers:\n");
    scanf("%d",&n);
 
    printf("Enter the Frame no.:\n");
    scanf("%d",&m);
    
    int num[n];
    q->size = m;
    q->arr = (int *)malloc(q->size*sizeof(int));
    
    
    printf("Enter the numbers:\n");
    for(int i=0;i<n;i++)
    {
        scanf("%d",&num[i]);
    }
    
    
    for(int i=0;i<n;i++)
    {
        printf("\n%d\n",q->f);
        printf("%d\n",q->r);
        if(!isFull(q))
        {
            enqueue(q,num[i]);
            // miss++;
        }
        else if(isPresent(q,num[i]))
        {
            hit++;
        }
        else
        {
            dequeue(q);
            enqueue(q,num[i]);
            miss++;
        }
    }

    printf("Page Fault:%d\n",miss);
    printf("Hit:%d\n",hit);
    return 0;
}

Answer 1

在启用警告的情况下编译问题中的代码显示 q 在第 113 行 q->f = -1; 中使用未初始化。在前面的行中，struct queue *q;，q 被定义但没有给出任何值。正因为如此，程序的行为没有被 C 标准定义，没有理由“输出应该是页面错误。”

您必须通过将 q 设置为指向合适的内存来初始化它，也许是用 malloc 分配的，或者重新设计您的程序，以便 q 在初始化之前不被使用.

在编译器中启用警告并将警告提升为错误。对于 Clang，从 -Wmost -Werror 开始。对于 GCC，从 -Wall -Werror 开始。使用 MSVC，从 /W3 /WX.

开始

循环队列前后指针超出数组大小

Front and rear pointers of circular queue exceed the size of array

c

struct

circular-queue