Алгоритмизации

• Название: Алгоритмизации
• Дата: 27.09.2022
• Размер: 1.15 Mb.
• Имя файла: 12_100229_1_124427 (1).docx
• Тип: Документы; #700459
• страница: 26 из 67

ГЛАВА 15. Динамические структуры данных

1. Линейныесписки

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

Динамическая переменная хранится в некоторой области ОП, обращение к которой производится через переменную-указатель.

Как правило, динамические переменные организуются в списковые структуры данных, элементы которых имеют тип struct. Для адресации элементов в структуру включается указатель (адресное поле) на область размещения следующего элемента.

Такой список называют однонаправленным (односвязным).Если добавить в каждый элемент ссылку на предыдущий, получится двунаправленныйсписок(двусвязный),если последний элемент связать указателем с первым, получится кольцевой список.

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

infо	p

а шаблон структуры будет иметь вид

struct Spis {

int info;

Spis *p;

} ;

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

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

ключом будет являться фамилия, а при поиске, например, ветеранов труда – ключом будет стаж работы. Как правило, ключи должны быть уникальными, но могут и совпадать. В случае совпадения ключей лучше всего использовать схемы организации структур данных по принципам «хеширования».

Над списками можно выполнять следующиеоперации:

• 
  начальное формирование списка (создание первого элемента);
  
• 
  добавление элемента в список;
  
• 
  обработка (чтение, удаление и т.п.) элемента с заданным ключом;
  
• 
  вставка элемента в заданное место списка (до или после элемента с заданным ключом);
  
• 
  упорядочивание списка по ключу.
  

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

• 
  все параметры, не изменяемые внутри функций, должны передаваться с модификатором const;
  
• 
  указатели, которые могут изменяться, передаются по адресу.
  

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