Какое представление данных в наибольшей степени отвечало бы смыслу задачи об изменяющейся цепочке пронумерованных участников? Это – связанный список.
Связанный список – структура, в которой отдельные записи последовательно связаны друг с другом. Одно из полей связанного цикла имеет тип – указатель и указывает на очередной объект в списке. Указатель – это переменная, которая в качестве своего значения содержит адрес первого байта памяти, по которому записаны данные.
Используем связанный список, каждый элемент которого состоит из двух половинок:
- Inf – информационная половинка,
- Nxt – половинка указателя на следующий элемент.
Здесь в информационные половинки внесена начальная нумерация участников, а в половинки указателей – порядковые номера.
Чтобы удалить какой-нибудь элемент из списка, можно переписать последующий элемент на место выбывшего. Тогда указатель будет указывать на элемент через 1.
Запрограммировать этот список можно с помощью двумерного массива: M[1..N,1..2], где
- M[i][0] = i – номер участника игры,
- M[i][1] = i + 1 – указатель на следующий элемент массива.
Удаление элемента можно осуществить по схеме:
- M[k][0] = M[M[k][1]][0], где M[k][1] – указатель на следующий элемент, M[M[k][1]][0] – следующий элемент,
- M[k][1] = M[M[k][1]][1] – номер последующего элемента.
Переход к следующему элементу можно сделать так:
- k = M[k][1]
Цикл по подсчету элементов надо вести до S-1, т.к. на первом шагу мы уже стоим на первом элементе массива.
N = 7 S = 5 |
M = (1, 2, 3, 4, 5, 6, 7) (1, 2, 3, 4, 5, 6, 0) |
1. k = M[0][1] = 1 2. k = M[1][1] = 2 3. k = M[2][1] = 3 4. k = M[3][1] = 4 |
Выбывший элемент - 5 | Удаляем: M[5][0] = M[M[5][1]][0] = M[6][0] = 6 M[5][1] = M[M[5][1]][1] = M[6][1] = 6 |
| M = (1, 2, 3, 4, 6, 6, 7) (1, 2, 3, 4, 6, 6, 0) |
1. k = M[4][1] = 6 2. k = M[6][1] = 0 3. k = M[0][1] = 1 4. k = M[1][1] = 2 |
Выбывший элемент - 3 | Удаляем: M[2][0] = M[M[2][1]][0] = M[3][0] = 4 M[2][1] = M[M[2][1]][1] = M[3][1] = 4 |
|
| M = (1, 2, 4, 4, 6, 6, 7) (1, 2, 4, 4, 6, 6, 0) |
1. k = M[2][1] = 4 2. k = M[4][1] = 6 3. k = M[6][1] = 0 4. k = M[0][1] = 1 |
Выбывший элемент - 2 | Удаляем: M[1][0] = M[M[1][1]][0] = M[2][0] = 4 M[1][1] = M[M[1][1]][1] = M[2][1] = 4 |
|
| M = (1, 4, 4, 4, 6, 6, 7) (1, 4, 4, 4, 6, 6, 0) |
1. k = M[1][1] = 4 2. k = M[4][1] = 6 3. k = M[6][1] = 0 4. k = M[0][1] = 1 |
Выбывший элемент - 4 | Удаляем: M[1][0] = M[M[1][1]][0] = M[4][0] = 6 M[1][1] = M[M[1][1]][1] = M[4][1] = 6 |
|
| M = (1, 6, 4, 4, 6, 6, 7) (1, 6, 4, 4, 6, 6, 0) |
1. k = M[1][1] = 6 2. k = M[6][1] = 0 3. k = M[0][1] = 1 4. k = M[1][1] = 6 |
Выбывший элемент - 7 | Удаляем: M[6][0] = M[M[6][1]][0] = M[0][0] = 1 M[6][1] = M[M[6][1]][1] = M[0][1] = 1 |
|
| M = (1, 6, 4, 4, 6, 6, 1) (1, 6, 4, 4, 6, 6, 1) |
1. k = M[6][1] = 1 2. k = M[1][1] = 6 3. k = M[6][1] = 1 4. k = M[1][1] = 6 |
Выбывший элемент - 1 | Удаляем: M[6][0] = M[M[6][1]][0] = M[1][0] = 6 M[6][1] = M[M[6][1]][1] = M[1][1] = 6 |
|
| M = (1, 6, 4, 4, 6, 6, 6) (1, 6, 4, 4, 6, 6, 6) |
1. k = M[6][1] = 6 2. k = M[6][1] = 6 3. k = M[6][1] = 6 4. k = M[6][1] = 6 |
Выбывший элемент - 6 |
При подсчете элементов мы видим, что с помощью указателей на следующий элемент мы пропускаем выбывшие элементы.
По сравнению с третьим способом скорость значительно возросла. Это объясняется тем, что не происходит частых изменений в массиве. Однако здесь возникает новая проблема – для хранения связанного списка требуется в два раза больше памяти, чем для хранения массива в третьем способе. При больших значениях исходных данных проблема становится значительной. Попытка решить эту проблему была предпринята в пятом способе.
| Результаты тестирования программы: для n=2000, s=2000 получится результат – 63 миллисекунды, для n=10000, s=10000 время работы – 563 миллисекунды |