@Гуру77777

Линейный список реализуется с помощью вспомогательного массива целых чисел и переменной, хранящей номер первого элемента, например:

10 25 20 6 21 8 1 30 - массив данных

2 3 4 5 6 7 8 -1 - вспомогательный массив

1 - индекс первого элемента в спис
i -й элемент вспомогательного массива содержит для каждого i -го элемента массива данных индекс следующего за ним элемента. Отрицательное число или нуль используется как признак конца списка. Говоря более точно, для этого можно использовать любое число, не входящее в множество значений индекса массива. Этот же массив после сортировки выглядит так:

10 25 20 6 21 8 1 30 - массив данных

3 8 5 6 2 1 4 -1 - вспомогательный массив

7 - индекс первого элемента в списке.

Вопрос: Тут написано, что после сортировки вспомогательный массив получился в таком порядке. Каким образом он получился таким? Т.е. как его сортировали что он получился таким?

0

@Ygg

Сортировали по возрастанию значений элементов основного массива

0

@Гуру77777

Ygg, Тогда должно получиться 1 6 8 10 20 21 25 30 , а индексы 8 5 7 2 4 6 3 -1. Почему по другому?

0

@Ygg

Так и получается

7 - индекс первого элемента в списке

0

@Гуру77777

Ок. Про основной я понял А как тогда поменялся 2 3 4 5 6 7 8 -1 - вспомогательный массив на 3 8 5 6 2 1 4 -1

0

@Ygg

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

0

Байт

Извращение я тут вижу только одно. Зачем последний элемент вспомогательного массива равен -1 ? Если его сделать равным 1, то задача самая естественная.
Есть некие объекты и есть указатели на них. Отсортировать массив объектов, не трогая (не перемещая) сами объекты, а перемещая только указатели на них.
Эта задача полезна, когда объекты внушительного или переменного размера, например, являются строками.

0

@Гуру77777

Байт, Это все хорошо конечно. Но может кто-нибудь объяснит роль вспомогательного массива в реализации ,в данном случае, линейного списка с помощью массива?

Добавлено через 1 минуту
Ygg, Вы можете мне объяснить на простеньком примере смысл использования вспомогательного массива в реализации линейного списка с помощью массива?

0

@Ygg

Гуру77777, вспомогательный массив определяет последовательность элементов в списке. Но реализовать задание последовательности можно по разному. Первый вариант, который сразу вырисовывается, это последовательное использование вспомогательного массива. Значение по первому индексу определяет индекс первого элемента данных, значение по второму индексу - индекс второго элемента данных. Но это не соответствует описанию задачи и, полагаю, что в этом ваша загвоздка. Второй вариант, предложенный автором задания, подразумевает не последовательное использование вспомогательного массива. Фактически, основной массив не является списком, а списком является вспомогательный массив. Элемент вспомогательного массива определяет индекс следующего индекса вспомогательного массива. Не знаю, как ещё это можно объяснить.

2

@Гуру77777

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

0

Байт

В вашем примере смысл не так уж просто понять. Ибо сам массив ничем не лучше, чем вспомогательный. Да и устроен вспомогательны хрен знает как. И все это не делает чести тем, кто эту штуку придумал. А идея использования вспомогательного массива, вот, я как мог, ее объяснил в посте 7.
А что во вспомогательном, указатели или номера, это уж дело десятое. Номера легко перевести в указатели.
Идея в том, что сравнение происходит не по значениям вспомогательного массива, а по тем объектам, на которые они указывают. А переставляются элементы вспомогательного. Что чаще бывает проще.
Ведь какие главные составляющие сортировки (и единственные): Сравнение и Перестановка. И тут сравниваются сами объекты, а переставляются указатели.
Примеры?
Возьмите массив строк

0

@Ygg

Да почему же неизвестном?
Давайте рассмотрим другой пример.
Есть список из трёх элементов: 90, 80 и 100.
В зависимости от того, как его создавали он может лежать в массивах разными способами, например так:

индексы массивов	1	2	3	4	5
значения основного массива	80	x	100	x	90
значения вспомогательного массива	3	x	-1	x	1

Первый элемент списка лежит в ячейке 5.

Или так:

индексы массивов	1	2	3	4	5
значения основного массива	80	90	x	100	x
значения вспомогательного массива	4	1	x	-1	x

Первый элемент списка лежит в ячейке 2.

Обе последовательности задают один и тот же список.
После упорядочивания по возрастанию список должен стать таким: 80, 90 и 100.
При этом мы не должны менять основной массив, нам нужно только задать другую последовательность с помощью вспомогательного.

Для первого варианта:

индексы массивов	1	2	3	4	5
значения основного массива	80	x	100	x	90
значения вспомогательного массива	5	x	-1	x	3

Первый элемент списка лежит в ячейке 1.

Для второго варианта:

индексы массивов	1	2	3	4	5
значения основного массива	80	90	x	100	x
значения вспомогательного массива	2	4	x	-1	x

Первый элемент списка лежит в ячейке 1.

0

@Гуру77777

Как реализовать код если это непонятноYgg,
Мы задаем эту последовательность случайно или с помощью закономерности(закона,правила)? Потому что я не понимаю каким образом для первого варианта значения вспомогательного массива для 80 равно 3, а потом стала 5

0

@Ygg

Конечно закономерно, так что бы список получился отсортирован по возрастанию.

Ещё раз, формирование списка для первого варианта:

индексы элементов	1	2	3	4	5
значения основного массива	80	x	100	x	90
значения вспомогательного массива	3	x	-1	x	1

Дано: первый элемент списка в ячейке 5
Читаем из вспомогательного массива ячейку 5, там лежит значение 1. Это значит, что второй элемент списка находится в ячейке 1.
Читаем из вспомогательного массива ячейку 1, там лежит значение 3. Это значит, что третий элемент списка находится в ячейке 3.
Читаем из вспомогательного массива ячейку 3, там лежит значение -1. Это значит, что список закончился.
Получилось, что список лежит в ячейках 5, 1 и 3.
В данных ячейках уже основного массива лежат числа: 90, 80 и 100.

1