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

typedef struct queue
{
    int *arr, // array to store values
    size, // queue size (array size)
    put, // index location which the next value will be pushed in
    take, // index location which the next value will be popped out
    countVals; // Counts the number of values that the queue contains
} queue;

// queue nitialization
void newQueue (queue *q, int size)
{
    if (size < 0)
        q->arr = NULL;
    else
    {
        q->arr = (int*) malloc (sizeof (int) * size);
        q->size = size;
        q->put = q->take = q->countVals = 0;
    }
}

// free array allocated to queue
void freeQueue (queue *q)
{
    free (q->arr);
}

// is the queue full?
int isFullQueue (queue q)
{
    return q.countVals == q.size;
}

// is the queue empty?
int isEmptyQueue (queue q)
{
    return q.countVals == 0;
}

// how many values queue contains?
int countQueueVals (queue q)
{
    return q.countVals;
}

// push value to queue
void pushQueue (queue *q, int val)
{
    if (q->arr && !isFullQueue (*q))
    {
        q->arr[q->put] = val;
        q->put = (q->put + 1) % q->size;
        q->countVals++;
    }
}

// pop out value from queue
void popQueue (queue *q)
{
    if (q->arr && !isEmptyQueue (*q))
    {
        q->take = (q->take + 1) % q->size;
        q->countVals--;
    }
}

// What is the value at top of queue
int topQueue (queue q)
{
    if (q.arr && !isEmptyQueue (q))
        return q.arr[q.take];
    return -1;
}

// show all queue values
void showQueue (queue q)
{
    if (q.arr)
        while (!isEmptyQueue(q))
        {
            printf ("%d ", topQueue(q));
            popQueue (&q);
        }
        //  printf ("\n");
}

// are values of queue arranged in palindrome?
int isQueuePalindrome (queue q)
{
    int i, num1, num2;
    queue tmpQ;

    if (!q.arr)
        return -1;

    newQueue (&tmpQ, q.countVals);
    while (!isEmptyQueue(q))
    {
        pushQueue (&tmpQ, topQueue(q));
        popQueue (&q);
    }

    while (tmpQ.countVals > 1)
    {
        for (i = 0; i < tmpQ.countVals - 1; i++)
        {
            num1 = topQueue (tmpQ);
            popQueue (&tmpQ);
            pushQueue (&tmpQ, num1);
        }

        num1 = topQueue (tmpQ);
        popQueue (&tmpQ);

        num2 = topQueue (tmpQ);
        popQueue (&tmpQ);

        if (num1 != num2)
        {
            freeQueue (&tmpQ);
            return 0;
        }
    }
    freeQueue (&tmpQ);
    return 1;
}

void main ()
{
    queue q;
    newQueue (&q, -1);
    showQueue (q);
    printf ("%d\n", isQueuePalindrome(q)); // -1
    newQueue (&q, 5);
    showQueue (q);
    printf ("-> %d\n", isQueuePalindrome (q)); // 1
    pushQueue (&q, 10);
    showQueue (q);
    printf ("-> %d\n", isQueuePalindrome (q)); // 1
    pushQueue (&q, 10);
    showQueue (q);
    printf ("-> %d\n", isQueuePalindrome (q)); // 1
    popQueue (&q);
    pushQueue (&q, 20);
    showQueue (q);
    printf ("-> %d\n", isQueuePalindrome (q)); // 0
    pushQueue (&q, 30);
    showQueue (q);
    printf ("-> %d\n", isQueuePalindrome (q)); // 0
    pushQueue (&q, 20);
    showQueue (q);
    printf ("-> %d\n", isQueuePalindrome (q)); // 0
    pushQueue (&q, 10);
    showQueue (q);
    printf ("-> %d\n", isQueuePalindrome (q)); // 1
}

我试着用函数检查队列的值是否按回文排列。
我不明白为什么当我调用函数时,函数会更改它的值,即使我没有将队列作为指针发送。而且,我不明白为什么只有当队列满了时才会发生这种情况。
函数根据以下算法检查队列:
如果队列未正确分配,将返回-1(错误)。
只要队列包含多个值:
i.假设队列实际上包含n个值,那么它将弹出一个值,并一次又一次地将其推回n-1次。
二。接下来的两个值将被弹出如果他们是平等的,这个过程将继续下去(不把他们推倒回去)。如果没有,它将结束并返回0(false)。
如果前面的部分将结束,这意味着队列为空或只包含一个值,那么它将返回1(true,因为它是回文)。
更新:
感谢Christian Gibbons和Yunnosch,我修复了另一个队列的问题(我只能复制数组,但我希望整个解决方案都按队列)。
我想知道是否有一种方法可以检查队列是否是没有任何额外数据结构(队列、堆栈、数组等)的回文?

最佳答案

如果复制包含指针的结构,则复制将包含相同的指针地址,两者都指向同一内存。
如果您随后更改该内存,则两个副本中的指针(尽管它们本身没有更改)将指向同一内存,因为它们没有更改,尽管没有更改。
因此,副本和原始文件都仍然包含指向更改值的指针。

关于c - C函数,它接收一个结构,并使其在函数外部进行更改,即使该结构未作为指针发送,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/51312753/

10-14 13:09
查看更多