1 / 1 / 0
Регистрация: 14.11.2018
Сообщений: 651
|
|
1 | |
Как так получилось?11.01.2019, 14:38. Показов 1349. Ответов 13
Метки нет (Все метки)
Линейный список реализуется с помощью вспомогательного массива целых чисел и переменной, хранящей номер первого элемента, например:
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
|
11.01.2019, 14:38 | |
Ответы с готовыми решениями:
13
Переставить цифры местами так, чтобы получилось большее число Переставить цифры числа так, чтобы получилось минимальное возможное число Переставить цифры числа так, чтобы получилось максимальное возможное число Рекурсивно расставить знаки операций так, чтобы получилось заданное число |
2376 / 833 / 317
Регистрация: 10.02.2018
Сообщений: 1,961
|
|
11.01.2019, 14:57 | 2 |
0
|
1 / 1 / 0
Регистрация: 14.11.2018
Сообщений: 651
|
|
11.01.2019, 15:04 [ТС] | 3 |
Ygg, Тогда должно получиться 1 6 8 10 20 21 25 30 , а индексы 8 5 7 2 4 6 3 -1. Почему по другому?
0
|
2376 / 833 / 317
Регистрация: 10.02.2018
Сообщений: 1,961
|
|
11.01.2019, 15:15 | 4 |
Так и получается
Код
1 2 3 4 5 6 7 8 3 8 5 6 2 1 4 -1 10 25 20 6 21 8 1 30 Код
7 -> 4 -> 6 -> 1 -> 3 -> 5 -> 2 -> 8 -> -1 1 6 8 10 20 21 25 30
0
|
1 / 1 / 0
Регистрация: 14.11.2018
Сообщений: 651
|
|
11.01.2019, 15:32 [ТС] | 5 |
Ок. Про основной я понял А как тогда поменялся 2 3 4 5 6 7 8 -1 - вспомогательный массив на 3 8 5 6 2 1 4 -1
0
|
2376 / 833 / 317
Регистрация: 10.02.2018
Сообщений: 1,961
|
|
11.01.2019, 16:12 | 6 |
Поменялся в результате работы некой программы, которую и нужно реализовать по заданию, наверное.
Просто нужно сопоставить пример с описанием и понять алгоритм обхода списка по вспомогательному массиву.
0
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
11.01.2019, 16:30 | 7 |
Извращение я тут вижу только одно. Зачем последний элемент вспомогательного массива равен -1 ? Если его сделать равным 1, то задача самая естественная.
Есть некие объекты и есть указатели на них. Отсортировать массив объектов, не трогая (не перемещая) сами объекты, а перемещая только указатели на них. Эта задача полезна, когда объекты внушительного или переменного размера, например, являются строками.
0
|
1 / 1 / 0
Регистрация: 14.11.2018
Сообщений: 651
|
|
11.01.2019, 16:53 [ТС] | 8 |
Байт, Это все хорошо конечно. Но может кто-нибудь объяснит роль вспомогательного массива в реализации ,в данном случае, линейного списка с помощью массива?
Добавлено через 1 минуту Ygg, Вы можете мне объяснить на простеньком примере смысл использования вспомогательного массива в реализации линейного списка с помощью массива?
0
|
2376 / 833 / 317
Регистрация: 10.02.2018
Сообщений: 1,961
|
|
11.01.2019, 17:39 | 9 |
Гуру77777, вспомогательный массив определяет последовательность элементов в списке. Но реализовать задание последовательности можно по разному. Первый вариант, который сразу вырисовывается, это последовательное использование вспомогательного массива. Значение по первому индексу определяет индекс первого элемента данных, значение по второму индексу - индекс второго элемента данных. Но это не соответствует описанию задачи и, полагаю, что в этом ваша загвоздка. Второй вариант, предложенный автором задания, подразумевает не последовательное использование вспомогательного массива. Фактически, основной массив не является списком, а списком является вспомогательный массив. Элемент вспомогательного массива определяет индекс следующего индекса вспомогательного массива. Не знаю, как ещё это можно объяснить.
2
|
1 / 1 / 0
Регистрация: 14.11.2018
Сообщений: 651
|
|
11.01.2019, 21:27 [ТС] | 10 |
ВYgg, Вы конечно хорошо расписали. Все вроде понятно. Вот только непонятно, это я взял с сайта в учебнике тоже самое написано.т.е у них там везде каким-то образом после сортировки вспомогательный массив становится в неизвестно каком порядке
0
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
||||||
11.01.2019, 22:36 | 11 | |||||
В вашем примере смысл не так уж просто понять. Ибо сам массив ничем не лучше, чем вспомогательный. Да и устроен вспомогательны хрен знает как. И все это не делает чести тем, кто эту штуку придумал. А идея использования вспомогательного массива, вот, я как мог, ее объяснил в посте 7.
А что во вспомогательном, указатели или номера, это уж дело десятое. Номера легко перевести в указатели. Идея в том, что сравнение происходит не по значениям вспомогательного массива, а по тем объектам, на которые они указывают. А переставляются элементы вспомогательного. Что чаще бывает проще. Ведь какие главные составляющие сортировки (и единственные): Сравнение и Перестановка. И тут сравниваются сами объекты, а переставляются указатели. Примеры? Возьмите массив строк
0
|
2376 / 833 / 317
Регистрация: 10.02.2018
Сообщений: 1,961
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
11.01.2019, 23:50 | 12 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Да почему же неизвестном?
Давайте рассмотрим другой пример. Есть список из трёх элементов: 90, 80 и 100. В зависимости от того, как его создавали он может лежать в массивах разными способами, например так:
Или так:
Обе последовательности задают один и тот же список. После упорядочивания по возрастанию список должен стать таким: 80, 90 и 100. При этом мы не должны менять основной массив, нам нужно только задать другую последовательность с помощью вспомогательного. Для первого варианта:
Для второго варианта:
0
|
1 / 1 / 0
Регистрация: 14.11.2018
Сообщений: 651
|
|
12.01.2019, 13:52 [ТС] | 13 |
Как реализовать код если это непонятноYgg,
0
|
2376 / 833 / 317
Регистрация: 10.02.2018
Сообщений: 1,961
|
|||||||||||||||||||
12.01.2019, 14:37 | 14 | ||||||||||||||||||
Сообщение было отмечено Гуру77777 как решение
Решение
Конечно закономерно, так что бы список получился отсортирован по возрастанию.
Ещё раз, формирование списка для первого варианта:
Читаем из вспомогательного массива ячейку 5, там лежит значение 1. Это значит, что второй элемент списка находится в ячейке 1. Читаем из вспомогательного массива ячейку 1, там лежит значение 3. Это значит, что третий элемент списка находится в ячейке 3. Читаем из вспомогательного массива ячейку 3, там лежит значение -1. Это значит, что список закончился. Получилось, что список лежит в ячейках 5, 1 и 3. В данных ячейках уже основного массива лежат числа: 90, 80 и 100.
1
|
12.01.2019, 14:37 | |
12.01.2019, 14:37 | |
Помогаю со студенческими работами здесь
14
Расставить знаки между цифрами так, чтобы получилось заданное число Заменить в числе одну цифру так, чтобы получилось максимальное число Фибоначчи Заданы цифры - расставить знаки сложения и вычитания так, чтобы получилось выражение с заданным результатом Между заданными числами расставить знаки сложения и вычитания так, чтобы в итоге получилось указанное число Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |