Использование указателя на структуру для создания связанного списка и выделения памяти в C - PullRequest
Новая
       18

Использование указателя на структуру для создания связанного списка и выделения памяти в C

0 голосов
/ 12 апреля 2011

У меня есть концептуальный вопрос, я полагаю. Когда мне нужно создать связанный список, но мне просто дают указатель на структуру (и структура содержит некоторый тип данных и указатель «следующий»). Как мне убедиться, что я создаю другие ссылки, а не только корневой узел? Я не использую malloc, иначе это был бы более очевидный ответ. Этот список действует как сам malloc.

Заранее спасибо!

Уточнить:

Будет один массив измерений, который будет действовать как блок памяти фиксированного размера. Затем связанный список будет «выделяться», удаляя узел и помещая его в массив, или «освобождая» данные, удаляя его из массива для добавления обратно в список.

пример

(структура определяется некоторым типом данных и указателем) структура называется узел 

node array[10];  //this acts as memory
node* linked_list;  //this gives or removes data to memory (array)

Ответы [ 3 ]

2 голосов
/ 12 апреля 2011

Это похоже на то, как мы делали вещи в моем классе Data Structures, используя FORTRAN 77 (еще в середине мела); мы выделили массив фиксированного размера и использовали его в качестве пула памяти.

По сути, вы должны поддерживать «свободный» список; это узлы, которые доступны для использования. При первом запуске вы инициализируете каждый элемент в вашем массиве, чтобы явно указать следующий элемент: 

struct node {T data; struct node *next; } pool[N]; // for some type T
...
for (i = 0; i < N-1; i++)
  pool[i].next = &pool[i+1];
pool[i].next = NULL;

Ваш свободный список изначально указывает на первый элемент в пуле: 

struct node *free = &pool[0];

Когда вы выделяете узел, вы получаете элемент, на который указывает free, обновляете free, чтобы он указывал на следующий доступный элемент в списке (если он существует), затем инициализируете элемент по мере необходимости: 

if (free) // is there a free node available
{
  struct node *newNode = free;
  free = free->next;
  newNode->data = ...;
  newNode->next = NULL;
  ...
}

Когда вы закончите работу с узлом, вы добавляете его обратно в начало списка free: 

node->next = free;
free = node;

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

1 голос
/ 12 апреля 2011

Я не могу быть уверен, относится ли это к вашему конкретному вопросу, но я хотел бы отметить кое-что о создании связанного списка без использования malloc.

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

Например, мы можем построить связанный список из массива. 

#include <stdio.h>

typedef struct node_t {
    int value;
    struct node_t *next;
} node;

int main() {

    int i;
    node linked_list[10];

    // build the linked list
    for ( i = 0; i < 10; i++ ) {
        linked_list[i].value = i * i;
        linked_list[i].next = ( i < 9 ) ? &linked_list[i+1] : 0;
    }

    // now traverse it
    node *head = &linked_list[0];
    while ( head ) {
        printf( "%d\n", head->value );
        head = head->next;
    }
}

EDIT : чтобы использовать массив в качестве места, из которого можно «выделить» или «освободить» узлы связанного списка, вы можете дополнить узел struct флагом, чтобы указать, является ли узел используется или нет. 

typedef struct node_t {
    char in_use;
    int value;
    struct node_t *next;
} node;

EDIT2 : давайте сделаем еще одну попытку. Ниже приведена функция, которая «выделяет» один узел из массива (или возвращает NULL, если ни один не доступен). Предположим, что linked_list является глобальным. 

node *get_node() {
    int i;
    for ( i = 0; i < 10; i++ )
        if ( !linked_list[i].in_use ) {
            linked_list[i].in_use = true;
            return &linked_list[i];
        }
    return 0;
}

EDIT3 : если массив будет использоваться в качестве пула памяти, то путь Джона Боде - это ответ.

0 голосов
/ 12 апреля 2011

Существует несколько возможных сценариев:

  • В связанном списке используется malloc.Связанный список затем отвечает за распределение и перераспределение узлов.Это стандартная реализация.

  • Связанный список использует статически выделенный фрагмент памяти, то есть статический массив фиксированного размера.Такой связанный список является более сложным, так как вам придется отслеживать, какие части массива содержат данные.Вам также нужно будет отслеживать размер связанного списка.

  • Связанный список представляет собой «массив узлов с таблицей поиска индекса».Тогда он не выделяет никаких данных, но вместо этого каждый узел содержит индексы массива.Связанный список должен отслеживать размер списка.

  • Связанный список не выполняет никакого выделения.Выделение осуществляется вызывающим абонентом (статически или динамически).В этом случае связанный список отслеживает только следующие указатели и ничего не выделяет.Эта версия плохого объектно-ориентированного дизайна, так как она нарушает частную инкапсуляцию данных.

РЕДАКТИРОВАТЬ после смены операции: похоже, вы используете версию 3 выше.Google для "связанного списка с использованием массива" или подобного.

...