0

Здравствуйте, мне дали задание, реализовать односвязный список на массиве. Я не совсем понимаю, что от меня требуется. Реализовывать стеки/деки/двусвязные и односвязные списки/очереди и т.д. умею, операции к ним тоже но с использованием структур

struct list {
      string val = " "; 
      list* next; 
}

Как должна выглядеть реализация на массиве?

1
  • Если у кого - то будут вопросы по реализации функций - пишите, я всё сделал 20 дек 2017 в 21:23

2 ответа 2

2

В массиве просто вместо указателя на следующий элемент используется индекс следующего элемента. Т.е. ваша структура выглядит как

struct list {
    string val; 
    size_t next; 
}

Соответственно, заголовок - просто size_t, равный индексу первого элемента массива, и т.д.

Например, элементы:

    0           1            2             3
"str1",1     "str2",3     "str4",0      "str3",2

образуют список из элементов массива 0 -> 1 -> 3 -> 2

0
1

Предположу что имеется в виду динамический массив. То есть элементы списка хранятся фактически в массиве - непрерывной области памяти. Из-за этого вам не должны требоваться указатели на следующие элементы next. Должна остаться возможность добавлять и удалять элементы из любого места этого списка-массива. Что, в свою очередь, требует очень тонкой работы с динамически выделяемой памятью.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.