Курсовая работа: Односвязный список на основе указателей
Операция добавления элемента после указанного сильно отличается от уже разработанной операции добавления элемента в список и пред-, постусловия предыдущей операций будут неполными в данном контексте. Прежде всего это связано с тем, что вводится решающий фактор существования (или не существования) элемента, указываемого пользователем по имени. В случае несуществования элемента, указанного пользователем, вставка становится невозможной.
К тому же, необходимо сначала найти указанный элемент или выявить признак его отсутствия. Для этой цели необходимо произвести обход списка. Так как список неупорядоченный мы не можем применить бинарный поиск, который значительно более эффективный, чем последовательный – его сложность порядка О(log2 n) против О(n), т.е., например, при количестве записей 106 , алгоритм бинарного поиска найдет элемент в худшем случае за 19 тактов, в то время как последовательный – за 106 тактов. Основные алгоритмы поиска и сортировки подробно рассмотрены в [3, 4, 5].
Последовательный поиск представляет собой обход списка со сравнением с контрольным ключом (в данном случае именем микросхемы) в каждом узле. Поскольку данный процесс совершенно линейный, удобно реализовать всю функцию рекурсивно. Базовая задача – создание нового узла и его связывание с предыдущим и последующим узлами, шаг рекурсии – сравнение записи с контрольной, условие завершения рекурсии – решение базовой задачи либо завершение обхода.
Предусловия: список существует, указанный элемент существует
Постусловие: новый элемент вставлен после указанного, сохраняя связность списка
3.3 ОперациЯ удаления указанного элемента
Инварианты для данной операции сходны с аналогичными для предыдущей операции, так как основным процессом является последовательный поиск указанного элемента.
Предусловие: список существует, указанный элемент существует
Постусловие: указанный элемент удален, связность списка сохранена
Очевидно, что для сохранения связности списка необходимо переопределить связи элементов записи таким образом, чтоб миновать в цепочке указанный элемент, но сохранить указатель на удаляемый узел, во избежании утечки памяти. Для этой цели, кроме указателя на удаляемый узел, необходим указатель на предыдущий узел. Обход списка совершается как раз для получения такого указателя.
Очевидно, что операции удаления первого и последнего элементов списка представляют собой отдельные задачи, так как требуют переопределения указателей на голову и хвост списка.
Случай удаления хвоста списка, кроме всего прочего, означает, что указатель на хвост получает значение константы NULL, несмотря на то, что список необязательно пуст. Строго говоря, установка значения указателя на хвост (голову) равным константе NULL является флагом, устанавливающим, признак того, что список пуст. Это приводит к тому, что нарушается механизм, обеспечивающий связность списка, иными словами список перестает существовать.
Во избежании подобной ситуации, носящей для списка, вообще говоря, катастрофический характер, необходимо в теле самой функции, непосредственно в блоке, в котором реализован алгоритм удаления узла, являющегося хвостом списка, предусмотреть операцию установки указателя на хвост.
Для этого достаточно совершить обход списка, начиная с головы до тех пор, пока не будет достигнут хвост.
Для удаления всех элементов с указанным именем, необходимо реализовать цикл, в котором бы выполнялась уже реализованная процедура удаления одного элемента.
В данном случае, нет необходимости совершать обход в этой же функции, тем более, что необходимо не только произвести обход, но и определить, существует ли еще элемент с указанным именем.
Пусть данная функция поиска возвращает ноль, если элемент не найден, единицу, если элемент с указанным именем найден. Данная функция не имеет права модифицировать данные, следовательно, объявляется с ключевым словом const.
Очевидно, что от значения, возвращаемого функцией поиска, зависит, будет ли продолжен последовательный обход списка для удаления элемента.
Таким образом, функция Remove_ предполагает интерфейс для операций удаления вне зависимости от количества удаляемых записей.
Операция удаления первого элемента:
Операция удаления указанного элемента:
3.4 Операция распечатки записей списка
По сути, операция распечатки записей списка представляет собой все тот же последовательный обход списка, начиная с головы списка. Единственным дополнением является тот момент, что при посещении каждого узла, производится вывод на экран данных, хранящихся в каждом конкретном узле (записи).
Обход списка реализован рекурсивно.
4. Реализация АТД-список
4.1 Главнаяфункция
#include <iostream>