Списки без использования указателей

Tommy

Как можно реализовать связный список без использования указателей (создавать списки, добавлять в список, удалять из списка), если есть только статический массив?

1 ответ

Tommy

Запросто.

Структура типа

struct Data
{
   int value; // Данные, словом
   int next, prev; // ИНДЕКСЫ следующего и предыдущего элементов списка,
                   // скажем, -1 - в роли NULL
};

Все. Массив таких структур. Каждая структура связана с предыдущей и следующей, храня не указатели на них, а их индексы в этом массиве.

Подробнее разжевывать не надо? :)

Вот демонстрационная программка (с очень небольшой функциональностью):

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

typedef struct Node_
{
    int value;
    int prev, next;
    int occupied;
} Node;


int getNode(Node*list, int size)     // Возврат первого свободного
{
    for(int i = 0; i < size; ++i)
        if (!list[i].occupied)
        {
            list[i].occupied = 1;
            return i;
        }
    return -1;
}

void freeNode(Node*list, int index)
{
    list[index].occupied = 0;
}

// Добавление в список, возврат индекса
int addToList(int*head, Node* list, int size, int value)
{
    int idx = getNode(list,size);
    if (idx >= 0)
    {
        list[idx].value = value;
        list[idx].next = list[idx].prev = -1;
        if (*head < 0) // Пустой список
        {
            *head = idx;
        }
        else
        {
            // Ищем последний
            int curr = *head;
            while(list[curr].next >= 0)
            {
                curr = list[curr].next;
            }
            list[curr].next = idx;
            list[idx].prev = curr;
        }
    }
    return idx;
}

void showList(int head, Node* list)
{
    // Идем по списку и выводим
    int curr = head;
    while(curr >= 0)
    {
        printf("%d  ",list[curr].value);
        curr = list[curr].next;
    }
    puts("");
}


int main(int argc, const char * argv[])
{
    Node list[100] = {{0,0,0,0}};
    int head = -1;
    addToList(&head,list,100,1);
    addToList(&head,list,100,2);
    addToList(&head,list,100,3);
    showList(head,list);

}
</string.h></stdio.h></stdlib.h>

Как видите, просто роль указателей выполняют индексы. Что такое указатель, в конце концов? Средство показать, где лежит интересующая информация. Он и показывает - в ячейке с таким-то номером.

Вот, нашел статейку, можно было и не мучиться :) - см. тут: https://rsdn.org/article/alg/list.xml

licensed under cc by-sa 3.0 with attribution.