Связные списки без указателей и динамической памяти
Как на языке C без использования указателей и динамической памяти создать связный список, добавить в него элементы (в начало, в конец и после определённого элемента), распечатать его и удалить? Использовать можно только статические массивы с постоянными границами
Ответы (1 шт):
Ну а что сложного? Список - это логическая структура, выражающая собой последовательность элементов. Массив - физическая структура, тоже выражающая последовательность элементов.
При реализации списка через динамическое выделение памяти у элемента есть указатель на следующий элемент. Если вы делаете список поверх массива - просто считаете что у элемента arr[i] указатель указывает на элемент arr[i+1]. Вот и вся концепция.
Исходя из реализации у вас только появляется одно ограничение - нельзя сделать список больше, чем размер массива.
Ну и начинаете заполнять список. Первый элемент списка попадает в arr[0], следующий arr[1] и т.д. Заполнили l элементов.
- Чтобы добавить в конец списка, записываете элемент в
arr[l+1]ячейку массива. - Чтобы добавить в начало списка, копируете (сдвигаете) все элементы в массиве на 1 ячейку и в
arr[0]записываете новый элемент. - Чтобы вставить в середину, например пятый элемент - начиная с пятого элемента и до последнего сдвигаете элементы вправо, и в позицию
arr[5]записываете новый элемент.
Чтобы немного слукавить, можно оставлять место в массиве не только в конце, но и в начале - чтобы можно было без копирований добавлять элементы и в конец и в начало списка. Примерно по такой концепции сделан std::deque<> . Но тогда нужно запоминать индексы и начала и конца списка. Например массив у вас на 100 элементов, а в списке всего 60. Тогда вы можете разместить список например с 10 по 70 ячейку массива.
Но при вставке в середину всё равно придется копировать.