АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. A) линейные
  2. Абстрактные линейные системы
  3. Б) линейные.
  4. Виды связей в организации: вертикальные и горизонтальные, линейные и функциональные, прямые и косвенные, формальные и неформальные.
  5. Двойные и криволинейные интегралы
  6. Линейные дешифраторы
  7. Линейные и аппаратные (штабные) полномочия
  8. Линейные и линейно-функциональные структуры управления: определение, схема, достоинства и недостатки.
  9. ЛИНЕЙНЫЕ И ШТАБНЫЕ СТРУКТУРЫ МЕНЕДЖМЕНТА
  10. Линейные измерения на местности
  11. Линейные измерения. Средства измерений и их точность.
  12. Линейные изоляторы

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

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

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

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

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

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

struct Spis {

int info;

Spis *p;

};

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

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

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

– начальное формирование списка (создание первого элемента);

– добавление элемента в список;

– обработка (чтение, удаление и т.п.) элемента с заданным ключом;

– вставка элемента в заданное место списка (до или после элемента с заданным ключом);

– упорядочивание списка по ключу.

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

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

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

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.)