9

以前の質問と同じように、リンクされたリストを作成しています。リンクされたリストを開発する最良の方法は、頭と尾を別の構造に持つことであることがわかりました。製品の構造体は、この構造体内にネストされます。そして、追加と削除のためにリストを関数に渡す必要があります。この概念はわかりにくいと思います。

初期化、追加、およびクリーンアップを実装しました。ただし、それが正しく行われたかどうかはわかりません。

製品をリストに追加するとき、calloc を使用していくつかのメモリを宣言します。しかし、代わりに製品のメモリを宣言するべきではないと考えています。私はこの追加について本当に混乱しています。

ご提案いただきありがとうございます。

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

#define PRODUCT_NAME_LEN 128

typedef struct product_data 
{
    int product_code;
    char product_name[PRODUCT_NAME_LEN];
    int product_cost;
    struct product_data_t *next;
}product_data_t;

typedef struct list 
{
    product_data_t *head;
    product_data_t *tail;
}list_t;

void add(list_t *list, int code, char name[], int cost); 
void initialize(list_t *list);
void clean_up(list_t *list);

int main(void)
{
    list_t *list = NULL;

    initialize(list);
    add(list, 10, "Dell Inspiron", 1500);
    clean_up(list);

    getchar();

    return 0;
}

void add(list_t *list, int code, char name[], int cost)
{
    // Allocate memory for the new product
    list = calloc(1, sizeof(list_t));
    if(!list)
    {
        fprintf(stderr, "Cannot allocated memory");
        exit(1);
    }

    if(list)
    {
        // First item to add to the list
        list->head->product_code = code;
        list->head->product_cost = cost;
        strncpy(list->head->product_name, name, sizeof(list->head->product_name));
        // Terminate the string
        list->head->product_name[127] = '/0';
    } 
}

// Initialize linked list
void initialize(list_t *list)
{
    // Set list node to null
    list = NULL;
    list = NULL;
}

// Release all resources
void clean_up(list_t *list)
{    
    list_t *temp = NULL;

    while(list)
    {
        temp = list->head;
        list->head = list->head->next;
        free(temp);    
    }
    list = NULL;
    list = NULL;
    temp = NULL;
}

============================= 編集済み ================== =========

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

#define PRODUCT_NAME_LEN 64

// typedef struct product_data product_data_t;
typedef struct product_data 
{
    int product_code;
    char product_name[PRODUCT_NAME_LEN];
    int product_cost;
}product_data_t;

typedef struct list
{
    struct list *head;
    struct list *tail;
    struct list *next;
    struct list *current_node;
    product_data_t *data;

}list_t;

void add(list_t *list, int code, char name[], int cost); 

int main(void)
{
    list_t *list = NULL;
    list = initialize(list);
    add(list, 1001, "Dell Inspiron 2.66", 1299);

    add(list, 1002, "Macbook Pro 2.66", 1499);

    clean_up(list);

    getchar();

    return 0;
}

void add(list_t *list, int code, char name[], int cost)
{
    /* Allocate memory for the new product */
    product_data_t *product = (product_data_t*) calloc(1, sizeof(*product));
    if(!product)
    {
        fprintf(stderr, "Cannot allocate memory.");
        exit(1);
    }

    /* This is the first item in the list */
    product->product_code = code;
    product->product_cost = cost;
    strncpy(product->product_name, name, sizeof(product->product_name));
    product->product_name[PRODUCT_NAME_LEN - 1] = '\0';

    if(!list->head)
    {
        /* Assign the address of the product. */
        list = (list_t*) product;   
        /* Set the head and tail to this product */
        list->head = (list_t*) product;
        list->tail = (list_t*) product;
    }
    else
    {
        /* Append to the tail of the list. */
        list->tail->next = (list_t*) product;
        list->tail = (list_t*) product;
    }

    /* Assign the address of the product to the data on the list. */
    list->data = (list_t*) product;
}
4

14 に答える 14

6

おそらく、リストのデータ構造は、格納するデータの外部にある必要があります。

あなたが持っているとしましょう:

なんでも構造体
{
   int x_;
}

次に、リスト構造は次のようになります。

構造物Whatever_Node
{
   Whatever_Node* next_
   何でも* data_
}

Ryan Oberoi も同様にコメントしましたが、例はありません。

于 2009-06-11T17:25:27.563 に答える
5

リンクされたリストの基本をよりよく理解したい場合は、次のドキュメントをご覧ください。

http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

于 2009-06-11T17:16:21.623 に答える
4

あなたの場合、頭と尾は単にリンクリストの最初と最後を指すことができます。単独でリンクされたリストでは、実際に必要なのは頭だけです。最も基本的なことですが、次のような構造体だけを使用して、リンクされたリストを作成できます。

typedef struct listnode
{
   //some data
   struct listnode *next;
}listnodeT;

listnodeT *list;
listnodeT *current_node;
list = (listnodeT*)malloc(sizeof(listnodeT));
current_node = list;

list が常にリストの先頭を指しており、最後の項目が次に NULL に設定されている限り、問題はなく、 current_node を使用してリストをトラバースできます。しかし、リストのトラバースを容易にし、リストに関する他のデータを保存するために、頭と尾のトークンが使用され、あなたが行ったように独自の構造にラップされることがあります。したがって、追加機能と初期化機能は次のようになります(マイナスエラー検出)

    // Initialize linked list
void initialize(list_t *list)
{
    list->head = NULL;
    list->tail = NULL;
}

void add(list_t *list, int code, char name[], int cost)
{
    // set up the new node
    product_data_t *node = (product_data_t*)malloc(sizeof(product_data_t));
    node->code = code;
    node->cost = cost;
    strncpy(node->product_name, name, sizeof(node->product_name));
    node->next = NULL;

    if(list->head == NULL){ // if this is the first node, gotta point head to it
        list->head = node;
        list->tail = node;  // for the first node, head and tail point to the same node
    }else{
        tail->next = node;  // append the node
        tail = node;        // point the tail at the end
    }
}

この場合、単独でリンクされたリストであるため、テールはリストにアイテムを追加する場合にのみ役立ちます。アイテムを挿入するには、先頭からリストをトラバースする必要があります。末尾が実際に役立つのは、二重にリンクされたリストの場合です。これにより、どちらかの端から開始してリストをトラバースできます。このリストを次のようにトラバースできます

// return a pointer to element with product code
product_data_t*  seek(list_t *list, int code){
   product_data_t* iter = list->head;
   while(iter != NULL)
       if(iter->code == code)
           return iter;
       iter = iter->next;
   }
   return NULL; // element with code doesn't exist
}

多くの場合、head と tail は完全に構築されたノード自体であり、リストの開始と終了を示す標識として使用されます。それらはデータ自体を保存するのではなく (むしろ、それらのデータはセンチネル トークンを表します)、表と裏の単なるプレース ホルダーです。これにより、リンクされたリストを扱う一部のアルゴリズムのコーディングが容易になりますが、2 つの余分な要素が必要になります。全体として、リンクされたリストは柔軟なデータ構造であり、それらを実装する方法がいくつかあります。

そうそう、nik の言うとおりです。リンクされたリストで遊ぶことは、ポインターと間接参照をうまく処理するための優れた方法です。また、再帰の練習にも最適です。リンクされたリストに慣れたら、次にツリーを構築し、再帰を使用してツリーをたどります。

于 2009-06-11T19:04:05.000 に答える
2

C ポインター理論を学んでいる場合、これは良い練習になります。そうしないと、(ライブラリのように) 一般的ではないコードの間接化が多すぎるように感じられます。

静的な 128 バイトの文字列を割り当てる代わりに、さらにポインタの練習を行い、終了時にクリーンアップする割り当てられた正確な長さの文字列を使用することをお勧めします。

学術的には、kungfucraigs の構造は、定義した構造よりも一般的に見えます。

于 2009-06-11T17:25:46.937 に答える
2

ここではコードを書きませんが、次のことを行う必要があります。

  • リストの作成とオブジェクト。これは、プログラムの間グローバルのままです。
  • product_data_t のサイズを malloc します。
  • 最初の要素 (head は NULL) の場合、head は malloced のアドレスを指します。
  • 次の要素を追加するには、リストの最後に移動してから、malloced アドレスのポインターを最後の要素の次の要素に追加します。(最後の要素の次は常に NULL になるため、最後までトラバースする方法です。)
  • しっぽのことはしばらく忘れてください。
于 2009-06-11T17:20:49.413 に答える
1

メモリ内では、アイテムはリスト構造のポインターによってリンクされています

アイテム1 -> アイテム2

リスト構造をアイテムの一部にしてみませんか?

次に、製品項目を割り当てると、リスト構造がその中にあります。

typedef struct product_data 
{
    int product_code;
    char product_name[PRODUCT_NAME_LEN];
    int product_cost;
    struct list_t list; // contains the pointers to other product data in the list
}product_data_t;
于 2009-06-11T17:16:30.860 に答える
1

list_t 構造体のスペースを呼び出しています。リストの先頭と末尾へのポインターだけです。これは、やりたいことではありません。

リンクされたリストに追加するときは、リスト内の実際のノード (product_data_t 構造体) にスペースを割り当てます。

于 2009-06-11T17:19:13.427 に答える
1

間違ったメモリのチャンクを割り当てています。リスト要素ごとにメモリを割り当てる代わりに、リストの先頭と末尾にメモリを割り当てています。

簡単にするために、頭と尾の別個の構造を取り除きます。それらをグローバル変数 (現在と同じスコープ) にして、listhead と listtail に変更します。これにより、コードがはるかに読みやすくなり (別の構造体を不必要に通過することはなくなります)、間違った構造体に割り当てるという間違いを犯すこともありません。

双方向リンク リストを作成する場合を除き、テール ポインターは必要ありません。リンクされたリストを作成したら、追加する主要な要素ではありませんが、必須でもありません。

于 2009-06-11T17:20:00.587 に答える
1

Linux カーネルで使用される実装に触発された連結リストの実装:

// for 'offsetof', see: https://stackoverflow.com/q/6433339/5447906.
#include <stddef.h>

// See: https://stackoverflow.com/q/10269685/5447906.
#define CONTAINER_OF(ptr, type, member) \
    ( (type *) ((char *)(ptr) - offsetof(type, member)) )

// The macro can't be used for list head.
#define LIST_DATA(ptr, type, member) \
    CONTAINER_OF(ptr, type, member);

// The struct is used for both: list head and list nodes.
typedef struct list_node
{
    struct list_node *prev, *next;
}
list_node;

// List heads must be initialized by this function.
// Using the function for list nodes is not required.
static inline void list_head_init(list_node *node)
{
    node->prev = node->next = node;
}

// The helper function, mustn't be used directly.
static inline void list_add_helper(list_node *prev, list_node *next, list_node *nnew)
{
    next->prev = nnew;
    nnew->next = next;
    nnew->prev = prev;
    prev->next = nnew;
}

// 'node' must be a list head or a part of a list.
// 'nnew' must not be a list head or a part of a list. It may
//   be uninitialized or contain any data (even garbage).
static inline void list_add_after(list_node *node, list_node *nnew)
{
    list_add_helper(node, node->next, nnew);
}

// 'node' must be a list head or a part of a list.
// 'nnew' must not be a list head or a part of a list. It may
//   be uninitialized or contain any data (even garbage).
static inline void list_add_before(list_node *node, list_node *nnew)
{
    list_add_helper(node->prev, node, nnew);
}

// 'node' must be part of a list.
static inline list_node *list_del(list_node *node)
{
    node->prev->next = node->next;
    node->next->prev = node->prev;
    return node->prev;
}

使用例:

#include <stdio.h>

// The struct must contain 'list_node' to be able to be inserted to a list
typedef struct
{
    int       data;
    list_node node;
}
my_struct;

// Convert 'list_node *' to 'my_struct*' that contains this 'list_node'
static inline my_struct* get_my_struct(list_node *node_ptr)
{
    return LIST_DATA(node_ptr, my_struct, node);
}

void print_my_list(list_node *head)
{
    printf("list: {");
    for (list_node *cur = head->next; cur != head; cur = cur->next)
    {
        my_struct *my = get_my_struct(cur);
        printf(" %d", my->data);
    }
    printf(" }\n");
}

// Print 'cmd' and run it. Note: newline is not printed.
#define TRACE(cmd) \
    (printf("%s -> ", #cmd), (cmd))

int main()
{
    // The head of the list and the list itself. It doesn't contain any data.
    list_node head;
    list_head_init(&head);

    // The list's nodes, contain 'int' data in 'data' member of 'my_struct'
    my_struct el1 = {1};
    my_struct el2 = {2};
    my_struct el3 = {3};

    print_my_list(&head); // print initial state of the list (that is an empty list)

    // Run commands and print their result.
    TRACE( list_add_after (&head    , &el1.node) ); print_my_list(&head);
    TRACE( list_add_after (&head    , &el2.node) ); print_my_list(&head);
    TRACE( list_add_before(&el1.node, &el3.node) ); print_my_list(&head);
    TRACE( list_del       (head.prev)            ); print_my_list(&head);
    TRACE( list_add_before(&head    , &el1.node) ); print_my_list(&head);
    TRACE( list_del       (&el3.node)            ); print_my_list(&head);

    return 0;
}

上記のコードの実行結果:

list: { }
list_add_after (&head , &el1.node) -> list: { 1 }
list_add_after (&head , &el2.node) -> list: { 2 1 }
list_add_before(&el1.node, &el3.node) -> list: { 2 3 1 }
list_del (head.prev) -> list: { 2 3 }
list_add_before(&head , &el1.node) -> list: { 2 3 1 }
list_del (&el3.node) -> list: { 2 1 }

http://coliru.stacked-crooked.com/a/6e852a996fb42dc2

mallocもちろん、実際にはリスト要素に使用する可能性が最も高いでしょう。

于 2018-05-31T07:46:39.673 に答える
0

C 言語では、整数データと次の値へのポインターを格納するノードを定義する必要があります。

struct Node{
    int data;
    struct Node *next;
};

新しいノードを追加するには、データを int パラメーターとして持つ add 関数があります。まず、新しいノード n を作成します。プログラムが n を作成しない場合は、エラー メッセージを出力し、値 -1 を返します。n を作成すると、n のデータがパラメータのデータを持つように設定され、次のデータにはスタックの一番上にあるルートが含まれます。その後、新しいノード n を参照するようにルートを設定します。

于 2017-05-24T03:56:31.990 に答える
-1

STL ルートに進みます。リンクされたリストの宣言は、データに依存しない必要があります。本当に自分で書かなければならない場合は、STL または Boost での実装方法を調べてください。

*next ポインターをデータ構造に保持することさえすべきではありません。これにより、製品データ構造をさまざまな数のデータ構造 (ツリー、配列、キュー) で使用できます。

この情報が設計上の決定に役立つことを願っています。

編集:

投稿には C のタグが付けられているため、基本的な設計原則に従う void* ポインターを使用した同等の実装があります。例として、以下を確認してください。

ドキュメンテーション| list.c | list.h

于 2009-06-11T17:23:08.847 に答える