Стивен Прата - Язык программирования C. Лекции и упражнения (6-е изд.) 2015

Код сохраняет адрес следующего узла, поскольку в принципе вызов функции free() может сделать содержимое текущего узла (на который ссылается указатель *plist) более недоступным.

НА ЗАМЕТКУ! Ограничения const

Некоторые функции обработки списка имеют в качестве параметра выражение List * plist. Это отражает тот факт, что такие функции не модифицируют список. Здесь const обеспечивает определенную защиту, предотвращая изменение указателя *plist (величины, на которую указывает plist). В рассматриваемой программе plist указывает на movies, так что спецификатор const предотвращает изменение этими функциями переменной movies, которая, в свою очередь, указывает на первую ссылку в списке. Таким образом, код вроде показанного ниже недопустим, скажем, в функции ListltemCount(): *plist = (*plist)->next; // не разрешено, если *plist - константа

Это хорошо, поскольку изменение *plist и, следовательно, movies привело бы утере программой возможности отслеживания данных. Однако то, что переменные *plist и movies трактуются как const, совершенно не означает, что данные, на которые указывает *plist или movies, являются константами. Например, следующий код вполне допустим:

(*р list) ->item.rating = 3; // разрешено, даже если *plist - константа

Причина в том, что этот код не изменяет переменную *plist; он изменяет данные, на которые указывает *plist. Вывод из всего сказанного заключается в том, что на const нельзя полностью полагаться при выявлении программных ошибок, которые приводят к случайному изменению данных.

Анализ проделанной работы

Сейчас мы посвятим некоторое время оценке того, что нам дал подход с использованием ADT. Для начала сравним листинги 17.2 и 17.4. В обеих программах для решения задачи с созданием списка фильмов применяется один и тот же фундаментальный

Расширенное представление данных 743

метод (динамическое выделение памяти для связанных структур). Но программа в листинге 17.2 показывает все программные нюансы, помещая malloc() и prev->next в открытое представление. С другой стороны, код в листинге 17.4 скрывает эти детали и выражает программу на языке, который напрямую связан с решаемой задачей. Это значит, что в нем речь идет о создании списка и добавлении в него элементов, а не о вызове функций управления памятью или о переустановке указателей. Короче говоря, листинг 17.4 представляет программу в терминах решаемой задачи, а не в терминах низкоуровневых инструментов, необходимых для ее решения. Версия с ADT ориентирована на проблемы конечного пользователя, поэтому читать ее гораздо легче.

Вместе файлы list.h и list.с образуют многократно используемый ресурс. Если вам необходим простой список элементов другого типа, достаточно обратиться к этим файлам. Предположим, что необходимо хранить сведения о своих родственниках: имена, родственные отношения, адреса и номера телефонов. Прежде всего, следует обратиться к файлу list.h и переопределить тип Item:

typedef struct itemtag {

char fname[14]; char lname [24]; char relationship[36]; char address [60]; char phonenum[20];

} Item;

Затем... что ж, в данном случае это все, что вы должны были сделать, поскольку все функции простого списка определены в терминах типа Item. В некоторых случаях пришлось бы также переопределить функцию CopyToNode(). Например, если бы элемент был массивом, то его не удалось бы копировать с помощью операции присваивания.

Еще один важный момент связан с тем, что пользовательский интерфейс определен в терминах операций абстрактного списка, а не какого-то конкретного набора представлений данных и алгоритмов. Это позволяет свободно манипулировать реализацией, не переделывая конечную программу. Например, созданная нами функция Addltem() несколько неэффективна, т.к. она всегда начинает работу с начала списка и затем выполняет поиск его конца. Указанный недостаток можно устранить, отслеживая конец списка. Например, тип List можно переопределить следующим образом:

typedef struct list {

Node * head; /* указывает на начало списка*/

Node * end; /* указывает на конец списка */

} List;

Конечно, после этого пришлось бы переписать функции обработки списка, применив это новое определение, но не нужно было бы изменять что-либо в листинге 17.4. Такой вид изолирования реализации от финального интерфейса особенно полезен в крупномасштабных программных проектах. Этот подход называется сокрытием данных, т.к. подробное представление данных скрыто от конечного пользователя.

Обратите внимание, что этот конкретный тип ADT даже не требует реализации простого списка в виде связного списка. Ниже показана еще одна возможность: