1

我有机会通过几个 C 练习获得一些额外的分数。任务是增强程序以使用头和尾指针(用于 FIFO 队列)以避免提取函数中不必要的 while 循环。

Insert()工作正常。它设置了尾部和头部,但extract()总是运行到无限循环或崩溃。MinGWgcc没有显示任何额外的警告(-Wall),所以我在这里有点困惑。

我做了一些调试,找到了线,事情发生在未知宇宙的某个地方……

    queue->previous->next = queue->previous; // works
    *head = (*head)->next;   // loses pointer
    free(queue);   // as it should be,
    return qtail;  // caller function loses queue 

有趣的是,原始代码(在此之前)可以正常工作而不会丢失指向队列的指针。我重写了整个程序(清理了我的烂摊子),但仍然有问题。

程序输出:

 queue tester

 insert 0: first head: first,  tail: first
 insert 1: second head: second,  tail: first
 insert 2: third head: third,  tail: first
 insert 3: foruth head: foruth,  tail: first
 insert 4: some head: some,  tail: first
 insert 5: another head: another,  tail: first
 insert 6: last head: last,  tail: first

 ***

 extracting last  head: last,  tail: first
 extracting ê7H  head: ê7H,  tail: first
 extracting ê7H  head: ê7H,  tail: first
 extracting ê7H  head: ê7H,  tail: first

… 以此类推,直到程序被Ctrl+终止C

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

#define MAXLEN 50
#define MAX 7

typedef struct qelement *qpointer;

typedef struct qelement {
    char name[ MAXLEN ];
    qpointer next, previous;

} qelement;

qpointer insert(char *name, qpointer queue, qpointer *head, qpointer *tail); 
qpointer extract(qpointer queue, qpointer *head, qpointer *tail);

qpointer insert(char *name, qpointer queue, qpointer *head, qpointer *tail) {

    qpointer new = (qpointer)malloc(sizeof(qelement));
    strcpy(new->name, name);

    if(queue != (qpointer)NULL) {
        new->next = queue;
        queue->previous = new;
        (*head) = new;
    } 
    else {
        new->next = new;
        (*head) = new;
        (*tail) = new;
    }
    new->previous = new;
    return new;
    }

qpointer extract(qpointer queue,  qpointer *head, qpointer *tail) {

    qpointer qtail =(*head);

    if(queue == (qpointer)NULL)
        return (qpointer)NULL;
    else {
        if(queue->previous != queue) {
            free(queue);
            (*head)=NULL;
            (*tail)=NULL;
            return (qpointer)NULL;
        }
        else {
            queue->previous->next = queue->previous;
            *head = (*head)->next;  
            free(queue);
            return qtail; // usually main program loses queue after this. 
        }
    }
}




int main ( void ) {

    int i;

    qpointer qptr =NULL;
    qpointer head =NULL ;
    qpointer tail =NULL ;

    char teksti[MAX][MAXLEN] = {
        "first", "second", "third", "foruth", "some", "another", "last"
    };

    /* insert into queue */
    printf("\n queue tester \n");
    for (i =0; i<= MAX-1 ; i++) {

        printf("\n insert %d: %s", i , teksti[i]);
        qptr= insert( teksti[i], qptr, &head, &tail);
        printf(" head: %s, ", head->name ? head->name : "no data");
        printf(" tail: %s ",  tail->name ? tail->name : "no data");
    }
    printf("\n\n");

    /* remove from queue */
    printf("\n ***\n");
    while (  qptr != NULL ) {

        printf("\n extracting %s ",qptr->name);
        printf(" head: %s, ", head->name ? head->name : "no data");
        printf(" tail: %s ",  tail->name ? tail->name : "no data");
        qptr = extract(qptr, &head, &tail);
    }

    return(0);
}

谢谢!

4

1 回答 1

1

应修改如下

qpointer extract(qpointer queue,  qpointer *head, qpointer *tail) {

    qpointer qtail =(*head);

    if(queue == (qpointer)NULL)
        return (qpointer)NULL;
    else {
        if(queue->next == queue) {
            free(queue);
            (*head)=NULL;
            (*tail)=NULL;
            return (qpointer)NULL;
        }
        else {
            queue->next->previous = queue->next;
            *head = (*head)->next;  
            free(queue);
            return *head; // qtail already free
        }
    }
}
于 2013-04-30T20:19:27.397 回答