0

既に作成したリンク リスト ライブラリに基づくキュー ライブラリを作成しようとしています。具体的には、新しいノードをリンク リストに追加した後、キュー構造のテール ポインターを更新する際に問題が発生しています。

連結リスト構造:

struct listNode {
    int nodeLength;
    int nodeValue;
    struct listNode *next;
};

typedef struct listNode node;

キュー構造:

struct QueueRecord {
    node *list;
    node *front;
    node *back;
    int maxLen;
};
typedef struct QueueRecord queue;

これがキューライブラリの追加機能です

void add(queue currentQueue, int data){
    addTail(currentQueue.list, data, data+5);
    currentQueue.back = currentQueue.back->next;

}

およびリンクされたリスト ライブラリの addTail 関数

void addTail (node *head, int value, int length) {
    node *current = head;
    node *newNode = (struct listNode *)malloc(sizeof(node));
    newNode = initNode(value, length);

    while (current->next != NULL)   
        current = current->next;

    newNode->next = NULL;
    current->next = newNode;
}

繰り返しますが、私の問題は、テールポインターがリストの最後のノードに設定されていないことです。ヘッドポインターと同じ場所に残ります。これを何時間も調査して、何か小さなものを見逃しているだけかどうかを確認しようとしましたが、見つかりません。私の問題を理解するためにさらにコードや説明が必要な場合は、提供できます。

キューの作成方法:

queue createQueue(int maxLen){
    queue newQueue;
    newQueue.list = createList();
    newQueue.front = newQueue.list;
    newQueue.back = newQueue.list;
    newQueue.maxLen = maxLen;
    return newQueue;
}    

node *createList (){
    node *head = NULL;
    head = (struct listNode *)malloc(sizeof(node));
    head->next = NULL;
    return head;
}

node *initNode (int value, int length){
    node *newNode = NULL;
    newNode = (struct listNode *)malloc(sizeof(node));
    newNode->nodeValue = value;
    newNode->nodeLength = length;
    newNode->next = NULL;
    return newNode;
}
4

2 に答える 2

2 
void add(queue currentQueue, int data){

構造体のコピーを に渡しているため、コピーのメンバーのみが変更されます。それ自体のメンバーを変更できるようにするには、関数にa を渡す必要があります。queueaddqueue*queue

void add(queue *currentQueue, int data){
    if (currentQueue == NULL) {
        exit(EXIT_FAILURE);
    }
    addTail(currentQueue->list, data, data+5);
    currentQueue->back = currentQueue->back->next;
}

そしてそれを次のように呼び出しますadd(&your_queue);

あなたのaddTail関数では、あまりにもあるかどうかを確認する必要headがありNULLます。

そして

node *newNode = (struct listNode *)malloc(sizeof(node));
newNode = initNode(value, length);

でaddTail、深刻な問題を抱えています。代入newNode = initNode(value, length);を使用すると、ちょうどmalloced メモリへの参照が失われます。

initNode malloc新しいメモリ チャンクが「単なる」メモリ リークである場合は、 in を削除する必要がありmallocますaddTail。

そうしないinitNodeと、ローカル変数のアドレスが返されるのではないかと心配しています。

node * initNode(int val, int len) {
    node new;
    new.nodeValue = val;
    new.nodeLength = len;
    new.next = NULL;
    return &new;
}

これinitNodeに似ていると、関数が戻るとすぐにアドレスが無効になるため、問題が発生します。initNodeしかし、そのように見えた場合、コンパイラは警告するはずです。

とにかく、 のコードを見initNodeないと、原因を診断できません。

しかし、あなたがに変更addTailした場合

void addTail (node *head, int value, int length) {
    if (head == NULL) { // violation of contract, die loud
        exit(EXIT_FAILURE);
    }
    node *current = head;
    node *newNode = malloc(sizeof(node));
    if (newNode == NULL) {
        exit(EXIT_FAILURE); // or handle gracefully if possible
    }
    newNode->nodeValue = value;
    newNode->nodeLength = length;
    newNode->next = NULL;

    while (current->next != NULL)   
        current = current->next;

    current->next = newNode;
}

それはうまくいくはずです。

backただし、リストの最初と最後のノードへのポインターがあるため、ポインターを使用して新しいノードを追加する方が効率的です。

void add(queue *currentQueue, int data){
    node *newNode = malloc(sizeof *newNode);
    if (newNode == NULL) {
        exit(EXIT_FAILURE); // or handle gracefully if possible
    }
    newNode->nodeValue = data;
    newNode->nodeLength = data+5;
    newNode->next = NULL;
    currentQueue->back->next = newNode;
    currentQueue->back = newNode;
}

最後を見つけるためにリスト全体をトラバースする必要がないためです。

簡単なサンプルプログラム

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

struct listNode {
    int nodeLength;
    int nodeValue;
    struct listNode *next;
};

typedef struct listNode node;

struct QueueRecord {
    node *list;
    node *front;
    node *back;
    int maxLen;
};
typedef struct QueueRecord queue;

node *createList (){
    node *head = NULL;
    head = (struct listNode *)malloc(sizeof(node));
    head->next = NULL;
    return head;
}

void addTail (node *head, int value, int length) {
    if (head == NULL) { // violation of contract, die loud
        exit(EXIT_FAILURE);
    }
    node *current = head;
    node *newNode = malloc(sizeof(node));
    if (newNode == NULL) {
        exit(EXIT_FAILURE); // or handle gracefully if possible
    }
    newNode->nodeValue = value;
    newNode->nodeLength = length;
    newNode->next = NULL;

    while (current->next != NULL)   
        current = current->next;

    current->next = newNode;
}

queue createQueue(int maxLen){
    queue newQueue;
    newQueue.list = createList();
    newQueue.front = newQueue.list;
    newQueue.back = newQueue.list;
    newQueue.maxLen = maxLen;
    return newQueue;
}

void add(queue *currentQueue, int data){
    if (currentQueue == NULL) {
        exit(EXIT_FAILURE);
    }
    addTail(currentQueue->list, data, data+5);
    currentQueue->back = currentQueue->back->next;
}

int main(void) {
    queue myQ = createQueue(10);
    for(int i = 1; i < 6; ++i) {
        add(&myQ, i);
        printf("list:  %p\nfront: %p\nback:  %p\n",
                (void*)myQ.list, (void*)myQ.front, (void*)myQ.back);
    }
    node *curr = myQ.front->next;
    while(curr) {
        printf("Node %d %d, Back %d %d\n", curr->nodeValue,
                 curr->nodeLength, myQ.back->nodeValue, myQ.back->nodeLength);
        curr = curr->next;
    }
    while(myQ.list) {
        myQ.front = myQ.front->next;
        free(myQ.list);
        myQ.list = myQ.front;
    }
    return 0;
}

代替add実装でも期待どおりに動作します。

于 2012-10-07T19:06:25.240 に答える
0

私はあなたが元に戻って初期化したことがないと思うので、戻る->次はいくつかのランダムなポインタですか？

于 2012-10-07T19:09:17.407 に答える