Линейные списки
Некоторые задачи исключают использование структур данных фиксированного размера и требуют введения структур, способных увеличивать или уменьшать свой размер уже в процессе работы программы. Основу таких структур составляют динамические переменные.
Динамическая переменная хранится в некоторой области ОП, обращение к которой производится через переменную-указатель.
Как правило, динамические переменные организуются в списковые структуры данных, элементы которых имеют тип struct. Для адресации элементов в структуру включается указатель (адресное поле) на область размещения следующего элемента.
Такой список называют однонаправленным (односвязным). Если добавить в каждый элемент ссылку на предыдущий, получится двунаправленный список (двусвязный), если последний элемент связать указателем с первым, получится кольцевой список.
Например, пусть необходимо создать линейный список, содержащий целые числа, тогда каждый элемент списка должен иметь информационную (infо) часть, в которой будут находиться данные, и адресную часть (р), в которой будут размещаться указатели связей, т.е. элемент такого списка имеет вид
а шаблон структуры будет иметь вид
struct Spis {
int info;
Spis *p;
} ;
Каждый элемент списка содержит ключ, идентифицирующий этот элемент. Ключ обычно бывает либо целым числом, либо строкой и является частью поля данных. В качестве ключа в процессе работы со списком могут выступать разные части поля данных.
Например, если создается линейный список из записей, содержащих фамилию, год рождения, стаж работы и пол, любая часть записи может выступать в качестве ключа. При упорядочивании такого списка по алфавиту ключом будет являться фамилия, а при поиске, например, ветеранов труда – ключом будет стаж работы. Как правило, ключи должны быть уникальными, но могут и совпадать. В случае совпадения ключей лучше всего использовать схемы организации структур данных по принципам «хеширования».
Над списками можно выполнять следующие операции:
– начальное формирование списка (создание первого элемента);
– добавление элемента в список;
– обработка (чтение, удаление и т.п.) элемента с заданным ключом;
– вставка элемента в заданное место списка (до или после элемента с заданным ключом);
– упорядочивание списка по ключу.
Если программа состоит из функций, решающих вышеперечисленные задачи, то необходимо соблюдать следующие требования:
– все параметры, не изменяемые внутри функций, должны передаваться с модификатором const;
– указатели, которые могут изменяться, передаются по адресу. Например, при удалении из списка последнего элемента, измененный указатель на конец списка требует корректировки, т.е. передачи в точку вызова.
Дата добавления: 2014-12-30; просмотров: 904;