时间戳

首页 > 解决方案 > 当我想用纯c解决leetcode.225时，出了点问题

c - 当我想用纯c解决leetcode.225时，出了点问题

问题描述

''' 在答案的帮助下，我修改了代码，比如返回类型和函数参数设置。在这里谢谢大家，但是我还是不明白为什么我的代码还是报这样的错误。查了很多资料，感觉enqueue函数里面的代码没有问题。出了什么问题？非常感谢 ！'''

typedef struct {
    int val;
    struct QNode* next;
}QNode;

typedef struct {
    struct QNode *rear;
    struct QNode *front; 
}Queue;

typedef struct {
    struct Queue *q1;
    struct Queue *q2;
}MyStack;


Queue* qcreate(void){
    Queue* q = malloc(sizeof(Queue));

    q->front = NULL;
    q->rear = NULL;
    return q;
}

bool qisempty(Queue* q){
    return (q->rear == NULL);
}

void enqueue(Queue *q, int x){
    QNode *qn = malloc(sizeof(QNode));
    qn->val = x;
    qn->next = NULL;

    if(q->front==NULL){
        q->front = q->rear = qn; // line 35
    }
    else{
        q->rear->next = qn; // line 38
        q->rear = qn;
    }
}

int dequeue(Queue* q){
    QNode *pt;
    int n = q->front->val;
    pt = q->front;
    
    q->front = q->front->next;
    
    free(pt);
    return(n);
}

void freeq(Queue* q){
    while(!qisempty(q)){
        dequeue(q);
    }
    q->front = q->rear = NULL
    free(q);
}

/** Initialize your data structure here. */

MyStack* myStackCreate() {
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));

    st->q1 = qcreate();
    st->q2 = qcreate();
    return st;
}

/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
    int m;
    while(!qisempty(obj->q1)){
        m = dequeue(obj->q1);
        enqueue(obj->q2, m);
    }
    enqueue(obj->q1, x);
    while(!qisempty(obj->q2)){
        m = dequeue(obj->q2);
        enqueue(obj->q1, m);
    }
}

/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
    int m;
    m = dequeue(obj->q1);
    return m;
}

/** Get the top element. */
int myStackTop(MyStack* obj) {
    return obj->q1->front->val;
}

/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
    return qisempty(obj->q1);
}

void myStackFree(MyStack* obj) {
    freeq(obj->q1);
    freeq(obj->q2);
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/`enter code here`

solution.c：在函数“入队”中</p>

第 35 行：字符 28：警告：从不兼容的指针类型 'QNode *' {aka 'struct *'} [-Wincompatible-pointer-types] q->front = q->rear = qn 分配给 'struct QNode *'；^

第 38 行：字符 16：错误：取消引用指向不完整类型 'struct QNode' q->rear->next = qn 的指针；^~

标签： cdata-structuresstackqueue

解决方案

你的错误在这里：

void qinit(){

你这样称呼它：

qinit(st->q1);
qinit(st->q2);

显然，您希望函数初始化st->q1，st->q2但事实并非如此。你可能想要：

void qinit(){
    ....
    return MALLOCED_AND_INITIALIZED_QUEUE_POINTER;
}

st->q1 = qinit();
st->q2 = qinit();

那么为什么你没有收到编译器警告/错误呢？

好吧，void qinit()这意味着一个函数采用未指定数量的参数，因此您不会收到qinit(st->q1);.

如果你使用过：void qinit(void)编译器会冲着你尖叫的。

教训：永远不要在函数中使用空参数列表。void如果没有参数，请使用。

除此之外：

这是一个也需要修复的错误。

这里：

void freeq(struct Queue* q){
    while(!qisempty(q)){
        dequeue(q);
    }
    free(q->front);   // q-> front is NULL due to the while above
                      // so this does nothing

    free(q->rear);    // q->rear is pointing to an already free'ed object
                      // so this is an error
}

换句话说 - 两者都free应该被删除。

和这里：

int dequeue(struct Queue* q){
    struct QNode *pt;
    int n = q->front->val;
    pt = q->front;
    
    q->front = q->front->next;
    q->count--;
    free(pt);
    return(n);
}

您缺少q->rear. 喜欢：

    if (q->front == NULL) q->rear = NULL;
    return(n);

以及关于设计的评论：

为什么要推到队列的末尾并从前面弹出？

这就是 FIFO 的工作原理。

对于堆栈，您通常会以相同的方式同时执行 push 和 pop。这将真正简化您的代码。此外，它将表现得更好。

如果你总是从前面推动和弹出，你可以

  1. 删除q2_MyStack

  2. 删除rear_struct Queue

并因此删除所有对其进行操作的代码。

推荐阅读