Теория алгоритмов

Лабораторная работа 5 На рисунке 5.1 показаны два связных списка, в которых содер­жатся цифры 31, 72,47 и 9. Верхняя переменная top - это указатель на первую ячейку списка, а нижняя - первая ячейка в списке. Оба списка заканчиваются квадратиком с косым перекрестием - так обозначается нулевой указатель. 31 72 47 к. 9 31 72 47 9 top 72 47 9 31 72 47 9 31 72 47 ^ 9 Рисунок 5. !.Примеры связных списков Связные списки - хороший способ хранить элементы, количе­ство которых может со временем увеличиваться или уменьшаться. Чтобы присовокупить новую ячейку, нужно всего лишь добавить ее в начало или в конец связного списка. Массив располагает фикси­рованным размером, поэтому его сложно увеличить, если требует­ся включить новые элементы. В однонаправленном связном списке (рисунок 5.1) каждая ячей­ка связана со следующей с помощью одинарной ссылки. Чтобы использовать такой список, нам понадобятся алгоритмы для пе­редвижения по списку, поиска, добавления и удаления элементов. Рассмотрим некоторые из них. Передвижение по спискам. Если программа содержит встроен­ные или связные списки, переход по ее ячейкам осуществляется относительно просто. Следующий алгоритм показывает, как это сделать и как работать со значениями в ячейках. В приведенном ниже примере используется метод Print (он выводит значения яче­ек), однако вы можете заменить его любым другим. - 6 5 -