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

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

Ответ

Запросто.
Структура типа
struct Data { int value; // Данные, словом int next, prev; // ИНДЕКСЫ следующего и предыдущего элементов списка, // скажем, -1 - в роли NULL };
Все. Массив таких структур. Каждая структура связана с предыдущей и следующей, храня не указатели на них, а их индексы в этом массиве.
Подробнее разжевывать не надо? :)
Вот демонстрационная программка (с очень небольшой функциональностью):
#include #include #include
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);
}
Как видите, просто роль указателей выполняют индексы. Что такое указатель, в конце концов? Средство показать, где лежит интересующая информация. Он и показывает - в ячейке с таким-то номером.
Вот, нашел статейку, можно было и не мучиться :) - см. тут: https://rsdn.org/article/alg/list.xml