1

QueueADT の単一リンク リスト バージョンを実装しています。キューの作成時に、クライアントが比較機能を提供する場合、新しいデータをキューに挿入するときにそれを使用します。クライアントが比較機能を提供しない場合は、標準のキュー挿入を使用して、キューの最後に挿入します。

比較関数を使用して挿入するロジックに問題があります。比較関数が返すものしかわかりません。

compare( void*a, void*b)
//compare returns < 0 if a < b
//compare returns = 0 if a == b
//compare returns > 0 if a > b

標準のキューとリンクされたノード構造があります。

typedef struct queueStruct {
    Node *front;
    Node *rear;
    int count;
    int (*compare)(const void*, const void*);
};

typedef struct Node {
    void* value;
    struct Node *next;
}Node;

そして、これが挿入機能での私の試みです。ロジックが正しいとは思わないので、洞察や疑似コードをいただければ幸いです。

void que_insert(queueStruct queue, void *data){
    //if the queue is empty
    if (que_empty(queue)){
        Node *node;
        node = malloc(sizeof(Node));
        node -> value = data;
        node -> next = NULL;
        queue->front  = node;
        queue->rear = node;
        queue->count++;
     }
     else{
        //if there is no comparison function, just use FIFO
        if (queue->compare == NULL){
            printf("Fifo\n");
            Node *node;
            node = malloc(sizeof(Node));
            node->value = data;
            node->next = NULL;
            queue->rear->next = node;
            queue->rear = node;
            queue->count++;

         }
         else{
            Node *temp;
            temp = queue->front;
            //if what we are adding is smaller than the head, then we found our new head
            if (queue->compare(data, temp->value) < 0){
                printf("Less Than 0\n");
                Node *node;
                node = malloc(sizeof(Node));
                node->value = data;
                node->next = queue->front;
                queue->front = node;
                queue->count++;
                return;
             }
             while (temp->next != NULL){
                if (queue->compare(data, temp->value)> 0){
                    printf("Greater than 0\n");
                    temp = temp->next;
                }
                else if (queue->compare(data, temp->value) ==  0){
                    printf("Equals 0\n");
                    Node *node;
                    node = malloc(sizeof(Node));
                    node->value = data;
                    node->next = temp->next;
                    temp->next = node;
                    queue->count++;
                    return;
                 }
             }
             //temp should be at the rear
             if (queue->compare(data, temp->value)> 0){
                printf("Adding to rear");
                Node *node;
                node = malloc(sizeof(Node));
                node->value = data;
                node->next = NULL;
              }
          }
     }
}

テスト:

次のデータをキューに挿入しようとすると:

42, 17, -12, 9982, 476, 2912, -22, 3291213, 7782

これらの値を挿入すると、最後の値まで機能するようです。プログラムは次の場所でハングします

inserting 7782
Greater than 0
Greater than 0
Greater than 0
Greater than 0
4

1 に答える 1

2

初め。比較で厳密な弱い順序付けが必要な場合 (必要な場合)、追加のコンパレーター呼び出しをすべて行う必要はありません。これは本質的に次のことを意味します

if (compare(a,b) < 0) 
    then a is less than b
else if !(compare(b,a) < 0) 
    then a and b are equal
else b is less than a

これは、標準ライブラリで一般的に使用されます。1 つは、比較の列挙を追跡しやすくするためです。また、論理演算を1 つ定義するだけで済みます。"以下"

一般的なコメントで述べたように、新しいノードが割り当てられている場所を統合します。あなたのキューは重複をサポートしているようです（そうすべきです）。したがって、常に新しいノードを追加していても、最初から作成してから、どこに行くかを見つけることに集中してください。

最後に、pointer-to-pointer-to-Node を使用すると、挿入がかなり簡潔になります (実際、非常に短いことがわかると思います)。

void que_insert(queueStruct* queue, void *data)
{
    // going to need this sooner or later
    Node *node = malloc(sizeof(*node));
    node->value = data;
    node->next = NULL;

    //if the queue is empty
    if (queue->count == 0)
    {
        queue->front = queue->rear = node;
        queue->count = 1;
    }

    // else not empty, but no comparator
    else if (queue->compare == NULL)
    {
        //if there is no comparison function, just use FIFO
        queue->rear->next = node;
        queue->rear = node;
        queue->count++;
    }

    // else not empty and we have a comparator
    else
    {   // walk over chain of node pointers until we  find a pointer 
        //  that references a node equal or greater than ours, or EOQ
        Node **pp = &queue->front;
        while (*pp && queue->compare((*pp)->value, data) < 0)
            pp = &(*pp)->next;

        // no more nodes means new rear. otherwise link mid-stream
        if (!*pp)
            queue->rear = node;
        else
            node->next = *pp;

        // either way, this is always done.
        *pp = node;
        queue->count++;
    }
}

使い方

pointer-to-pointer-to-Node を使用して、ヘッド ポインターから始めて、調べている各ポインターのアドレスを保持します。これにはいくつかの利点があります。「次の」ノードにアクセスするためだけにノードへのポインターを追跡する必要はありません。ヘッド ポインターアドレスから開始するため、自動フロント挿入が行われます。考慮しなければならない唯一のことは、手動で行う必要があるリア更新です。

ポインターからポインターへのトラバーサルは、最初は少し難しいように思えるかもしれませんが、いくつかの素晴らしい特徴があります。ノードへのポインター列挙子はありません。実際には、リスト内のポインターを列挙変数として使用しています。それらの「値」だけでなく、実際のポインターとその値。あなたがしているのは、ポインタツーポインタのアドレスを更新して、扱っているリスト(リストだけでなく) 内のどの物理ポインタを反映することによって、使用しているものを変更することだけです。何かを変更するときが来たら、変更する必要がある「次の」ポインタであるノードへのポインタは必要ありません。変更しようとしているポインターのアドレスが既にある場合、

添付のコードはテストしていませんが、動作するはずです。queueStructリアとフロントの両方のポインターで NULL を使用して、イニシャルがゼロ カウントに設定されていることを確認してください。それは（明らかに）重要です。

最後に、デバッガーを使用してこれを実行することを強くお勧めします。コード内を飛んでいる実際のポインタ アドレスと値を「見る」ことに代わるものはありません。鉛筆と、ボックス、ボックスへの矢印、およびボックスへの矢印から矢印への矢印が付いた紙も、アルゴリズムを理解するのにかなり役立ちます。

于 2013-11-06T16:35:39.737 に答える