Как реализовать связанный список в C? - PullRequest
8 голосов
/ 11 июня 2009

Я создаю связанный список , как и в предыдущем вопросе, который я задал. Я обнаружил, что лучший способ создать связанный список - это иметь голову и хвост в другой структуре. Моя структура продуктов будет вложена в эту структуру. И я должен передать список функции для добавления и удаления. Я нахожу эту концепцию запутанной.

Я реализовал инициализацию, добавление и clean_up. Однако я не уверен, что сделал это правильно.

Когда я добавляю продукт в список, я объявляю некоторую память с помощью 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;
}

Ответы [ 14 ]

1 голос
/ 11 июня 2009

В памяти ваши элементы связаны указателями в структуре списка

item1 -> item2

Почему бы не сделать структуру списка частью вашего элемента?

Затем вы выделяете товар, и структура списка находится внутри него.

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;
0 голосов
/ 11 октября 2017
#include <stdio.h>
struct node
 {
  int data;
  struct node* next;
 };

int main()
{

//create pointer node for every new element

struct node* head = NULL;
struct node* second = NULL;
struct node* third = NULL;

//initialize every new pointer with same structure memory

head = malloc(sizeof(struct node));
second = malloc(sizeof(struct node));
third = malloc(sizeof(struct node));

head->data = 18;
head->next = second;

second->data = 20;
second->next = third;


third->data = 31;
third->next = NULL;

//print the linked list just increment by address 

  for (int i = 0; i < 3; ++i)
    {
      printf("%d\n",head->data++);
      return 0;
    }
 }

Это простой способ понять, как указатель работает с указателем. Здесь вам нужно просто создать приращение указателя с новым узлом, чтобы мы могли сделать это автоматически.

0 голосов
/ 24 мая 2017

В языке C нам нужно определить узел для хранения целочисленных данных и указатель на следующее значение.

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

Чтобы добавить новый узел, у нас есть функция add, которая имеет данные в качестве параметра int. Сначала мы создаем новый узел n. Если программа не создает n, мы печатаем сообщение об ошибке и возвращаем значение -1. Если мы создаем n, тогда мы устанавливаем данные n, чтобы иметь данные параметра, а следующий будет содержать корень, поскольку он имеет вершину стека. После этого мы устанавливаем корень для ссылки на новый узел n.

0 голосов
/ 11 июня 2009

По маршруту STL. Объявление связанных списков должно быть независимым от данных. Если вам действительно нужно написать это самостоятельно, посмотрите, как это реализовано в STL или Boost.

Вы даже не должны сохранять * следующий указатель со своей структурой данных. Это позволяет вам использовать структуру данных вашего продукта в различном количестве структур данных - деревьев, массивов и очередей.

Надеюсь, эта информация поможет вам в вашем дизайнерском решении.

Edit:

Поскольку запись помечена как C, у вас есть эквивалентные реализации, использующие указатели void *, которые следуют основному принципу разработки. Для примера, проверьте:

Документация | list.c | list.h

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...