1

私は C プログラミングのスキルを向上させようとしているので、二重連結リストのプログラミングを試みることから始めました。

これが私がこれまでに思いついたものです。

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
//forward definition

typedef struct Node node_t;


//Define the structures needed for double linked list

//Each node
typedef struct Node 
{
        int data;
        node_t *next;
        node_t *prev;
}node_t;




void initList(node_t** first , node_t** last)
{
    //Allocate memory for the first and the last node

    *first = (node_t*) malloc(sizeof(node_t));
    *last =  (node_t*) malloc(sizeof(node_t));
    (*first)->data = 1;
    (*last)->data = 2;

    (*first)->prev = NULL;
    (*last)->next = NULL;

    (*first)->next = (*last)->prev;

    return;

}

void destroyList(node_t** first)
{
    node_t* temp;

    temp = *first;

    free((*first)->next);
    free((*first));
    temp = NULL;



    return;
}



int main()
{

    node_t *first =NULL, *last = NULL;

    printf("Initalizing the List\n");
    initList(&first,&last);

    printf(" 1st element is %d\n",first->data);
    printf(" 2nd element is %d\n",last->data);

    printf("Destroying the List\n");




    destroyList(&first) ;


    return 0;
}

私は実際にオンラインでいくつかのコードを調べましたが、ほとんどの実装には

1) Node 用の 1 つの構造体と List 自体用の 1 つの構造体 (頭と尾を含む)。私の質問は、これは必須ですか? 1つの構造だけで実装できないのですか?

2）私の考えは、このファイルをライブラリとして作成し、アプリケーションから呼び出すことです。InitList
()、DestroyList()、AddNode、DeleteNode などのように。

そのため、INit と destroy に二重ポインタを使用しています。リストの破棄に問題があります。私はそれが間違っていることを知っています、私はそれを修正し続けます。

3) そのノードポインタを見つけました

 temp = first

あるアドレスを指していました。私がtemp ++を行う場合。次のノードを指していないのはなぜですか?

4) リスト全体を削除するために、最初または最後のノード ポインタを渡すことができますよね?. （つまり、トラバースしてシーケンシャルに削除しますか？）

ありがとう！

4

2 に答える 2

1

1）リスト構造を持つ必要はありませんが、構造が特定のメタデータ（たとえばリストの長さなど）を追跡すると、特定の操作の実行が速くなります。そうでない場合、長さを取得するには、毎回リストを反復する必要がありますこれは、大きなリストではコストがかかる可能性があります)。

3) 私はあなたが意味していると仮定しています

temp = *first

ノードが連続したメモリアドレスにあることが保証されていないため、temp ++は次のノードを指しません（一方、配列はそうです）。

4) first または last を使用してリストを削除できますが、特定のプロパティが特定のプロパティを確実に指定する必要があり、それ以外の場合は無限ループに陥る可能性があります。

于 2013-11-05T23:44:19.173 に答える