Стивен Прата - Язык программирования 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 даже не требует реализации простого списка в виде связного списка. Ниже показана еще одна возможность:

#define MAXSIZE 100 typedef struct list {

Item entries[MAXSIZE]; /* массив элементов */

int items; /* количество элементов в списке */

} List;

744 Глава 17

Это снова потребует переписывания файла list .с, но программа, использующая такой список, в изменениях не нуждается.

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

Создание очереди с помощью ADT

Как вы видели, подход к программированию на С с применением абстрактных типов данных подразумевает выполнение следующих трех шагов.

1. Описание типа, включая его операции, в абстрактной обобщенной манере.

2. Определение интерфейса в виде функций для представления нового типа.

3. Написание подробного кода для реализации интерфейса.

Этот подход был задействован при создании простого списка. Теперь воспользуемся им для построения несколько более сложного объекта — очереди.

Определение абстрактного типа данных для представления очереди

Очередь — это список, обладающий двумя особыми свойствами. Во-первых, новые элементы могут добавляться только в конец списка. В этом смысле очередь подобна простому списку. Во-вторых, элементы могут удаляться только из начала списка. Очередь можно сравнить с цепочкой людей, стоящих друг за другом в билетную кассу. Каждый новый человек становится в конец цепочки и покидает ее в самом начале после приобретения билетов. Очередь является формой данных типа первым прибыл, первым обслужен (first in, first out — EIFO), подобной очереди в кассу (если только никто не вклинится в очередь). Ниже дано неформальное абстрактное определение.

Имя типа: Очередь

Свойства типа: Может содержать упорядоченную последовательность элементов