Динамические структуры данных (списки)

Содержание:

ВВЕДЕНИЕ

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

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

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

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

Целью данной работы является изучение динамических структур данных и списков, в частности.

Структурно работа состоит из введения, двух глав, заключения и списка использованных источников.

ГЛАВА 1. ПОНЯТИЕ И ОСОБЕННОСТИ ДИНАМИЧЕСКИХ СТРУКТУР ДАННЫХ

1.1 Определение «динамическая структура данных» и ее
характеристики

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

В C ++ есть инструменты для создания динамических структур данных, которые позволяют формировать объекты во время выполнения программы, выделять память для них и освобождать память, когда она больше не нужна.Таким образом, можно сформулировать следующее определение динамических структур данных:

Динамические структуры данных - это структуры данных, для которых выделяется и освобождается память по мере необходимости.

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

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

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

Динамическая данных характеризуется что:

• она имеет имени;
• выделяется память процессе выполнения ;
• количество элементов может не ;
• размерность структуры меняться в выполнения программы;
• процессе выполнения может меняться взаимосвязи между структуры.

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

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

Потребность в динамических структурах данных обычно возникает в следующих случаях.

• Используются переменные, довольно большой (например, массивы размерности), необходимые одних частях и совершенно нужные в .
• В процессе работы нужен массив, или иная , размер которой в широких и трудно .
• Когда размер данных, в программе, объем сегмента .

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

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

Достоинства связного представления данных – в возможности обеспечения значительной изменчивости структур:

• размер структуры ограничивается только доступным объемом машинной памяти;

• при изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей;

• большая гибкость структуры.

Вместе с тем, связное представление не лишено и недостатков, основными из которых являются следующие:

• на поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память;

• доступ к элементам связной структуры может быть менее эффективным по времени.

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

Процедура работы с динамическими структурами данных выглядит следующим образом:

• создать (выделить место в динамической памяти);

• работать с указателем;

• удалить (свободное место, занимаемое структурой).

Классификация динамических структур данных

Многие задачи требуют использования данных, в которых конфигурация, размер и состав могут меняться во время выполнения программы. Для их представления используются динамические информационные структуры. Эти структуры включают в себя:

• однонаправленные (односвязные) списки;

• двунаправленные (двусвязные) списки;

• циклические списки;

• стек;

• очередь;

• бинарные деревья.

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

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

1.2 Объявление динамических структур данных

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

где поле Р – ; поле – данные.

Элемент динамической структуры состоит из двух полей:

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

2) адресное поле (поле связок), содержащее один или несколько указателей, связывающих этот элемент с другими элементами структуры;

Объявление элемента динамической структуры данных выглядит следующим образом:

_типа

{

информационное ;

адресное поле;

};

Например:

{

; //информационное поле

*; //адресное

};

Информационных и адресных может быть одно, так несколько.

Рассмотрим в примера динамическую , схематично указанную рис. 1:

Рисунок – Схематичное представление динамической

Эта структура состоит из 4 элементов. Его первый элемент имеет поле d, равное 73, и связан со своим собственным полем p со вторым элементом, поле d которого равно 28, и так далее до последнего, четвертого элемента, поле d которого равно 85, и поле p равно NULL, то есть нулевому адресу, который является признаком завершения структуры. Здесь Ph - указатель, который указывает на первый элемент структуры.

1.3 Доступ к данным в динамических структурах

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

Указатель содержит адрес определенного объекта в динамической памяти. Адрес формируется из двух слов: адрес сегмента и смещение. Сам указатель является статическим объектом и находится в сегменте данных (рис. 2).

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

Рисунок - Связь указателя с объектом

Доступ к в динамических осуществляется с операции "стрелка" (->), называют операцией выбора элемента объекта, адресуемого . Она обеспечивает доступ элементу структуры адресующий ее того же типа. Формат применения операции следующий:

УказательНаСтруктуру-> ИмяЭлемента

Операции "" (->) двуместная. Применяется для к элементу, правым операндом, структуры, которую левый операнд. В левого операнда быть указатель структуру, а качестве правого – элемента этой .

Например:

->;

->;

Имея возможность манипулирования с , которые могут как вне , так и "" отдельных ее , можно создавать памяти различные .

Однако необходимо помнить, работа с данными замедляет программы, поскольку к величине в два : сначала ищется , затем по – величина.

1.4 Работа с памятью при использовании динамических структур

В программах, в которых необходимо использовать динамические структуры данных, работа с памятью происходит стандартным способом. Динамическое выделение памяти выполняется с помощью новой операции или с использованием библиотечной функции malloc (calloc). Освобождение динамической памяти осуществляется с помощью операции удаления или функции free.

Например, давайте объявим динамическую структуру данных с именем Node с полями Name, Value и Next, выделим память для указателя на структуру, назначим значения элементам структуры и освободим память.

{ *;

;

*

};

*; //объявляется

= ; //выделяется

-> = ""; //присваиваются значения

-> = ;

-> = ;

; // освобождение

ГЛАВА 2. СПИСКИ

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

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

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

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

В простейшем случае каждый узел содержит только одну ссылку. Для определенности будем считать, что задача частотного анализа текста решается - определение всех найденных в тексте слов и их количества. В этом случае область данных элемента включает строку (не более 40 символов) и целое число.

Рисунок 3

Каждый элемент также ссылку следующий за элемент. У последнего списке элемента ссылки содержит . Чтобы потерять список, должны где- (в переменной) адрес его узла – он «головой» списка. В надо объявить новых типа – узел списка указатель на . Узел представляет собой , которая содержит поля - строку, число и на такой узел. Правилами языка Си объявление

{

[40]; // данных

;

*; // ссылка следующий узел

};

*; // тип данных: на узел

В мы будем , что указатель на начало , то есть, в виде

= ;

Первая «» в названии происходит от – указатель (.) В начале работы списке нет одного элемента, в указатель нулевой адрес .

2.2 Создание элемента списка

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

( [] )

{

= ; // указатель новый узел

(->, ); // записать

-> = 1; // слов = 1

-> = ; // следующего узла

; // результат – адрес узла

}

После узел надо к списку ( начало, в или в ).

2.3 Добавление узла

Добавление узла в списка

При добавлении узла в списка надо ) установить ссылку на голову списка и ) установить голову на новый .

Рисунок 4

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

( &, )

{

-> = ;

= ;

}

Добавление узла после указанного

Дан адрес NewNode нового узла и адрес p одного из существующих узлов в списке. Требуется вставить новый узел в список после узла с адресом p. Эта операция выполняется в два этапа:

1) установить связь нового узла с узлом, следующим за данными;

2) установить ссылку этого узла p на NewNode.

Рисунок 5

Последовательность операций менять , потому что сначала поменять у узла , будет потерян следующего узла.

( , )

{

-> = ->;

-> = ;

}

Добавление узла перед

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

Задача либо к узла в списка (если узел – первый), к вставке заданного узла.

( &, , )

{

= ;

( == ) {

(, ); // вставка первым узлом

;

}

( && ->!=) // узел, за следует

= ->;

( ) // если такой узел,

(, ); // добавить новый него

}

Такая процедура обеспечивает «защиту от дурака»: если указан узел, которого нет в списке, то в конце цикла указатель q равен NULL и ничего не происходит.

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

Добавить узел в конец списка

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

( &, )

{

= ;

( == ) { // если список ,

(, ); // вставляем первый

;

}

(->) = ->; // ищем элемент

(, );

}

2.4 Проход по списку

Для того, чтобы весь список сделать что- с каждым элементом, надо с головы , используя указатель , продвигаться к узлу.

= ; // с головы

( != ) { // не дошли конца

// делаем -нибудь с

= ->; // переходим следующему узлу

}

2.5 Поиск узла в списке

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

1) начать с заголовка списка;

2) пока текущий элемент существует (указатель не NULL), проверьте требуемое условие и перейдите к следующему элементу;

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

Например, следующая функция ищет в списке элемент, соответствующий данному слову (для которого поле слова соответствует указанной строке NewWord), и возвращает его адрес или NULL, если такого узла нет.

( , [])

{

= ;

( && (->, ))

= ->;

;

}

Вернемся к проблеме построения буквенно-частотного словаря. Чтобы добавить новое слово в нужное место (в алфавитном порядке), вам нужно найти адрес узла, перед которым вам нужно вставить новое слово. Это будет первый узел в начале списка, для которого «его» слово окажется «больше», чем новое слово. Следовательно, достаточно просто изменить условие в цикле while в функции Find, учитывая, что функция strcmp возвращает «разность» первого и второго слова.

( , [])

{

= ;

( && ((->, ) > 0))

= ->;

;

}

Эта функция вернет узла, перед надо вставить слово (когда вернет значение), или , слово надо в конец .

2.6 Алфавитно-частотный словарь

Теперь можно написать программу, обрабатывает файл . и для него -частотный словарь файле ..

()

{

= , , ;

*, *;

[];

;

= ( ".", "" );

( ) {

= ( , "%", ); // слово из

( <= ) ;

= ( , ); // ищем слово списке

( != ) // если нашли ,

-> ++; // счетчик

{

= ( ); // создаем узел

= ( , ); // ищем место

( ! )

( , );

( , , );

}

}

();

= ( ".", "" );

= ;

( ) { // проход по и вывод

( , "%-\%\", ->, -> );

= ->;

}

();

}

В переменной n хранится значение, возвращаемое функцией fscanf (количество успешно прочитанных элементов). Если это число меньше единицы (чтение не удалось или данные в файле закончились), выйдите из цикла while.

Сначала мы пытаемся найти это слово в списке, используя функцию поиска. Если найдено, просто увеличьте счетчик найденного узла. Если слово встречается впервые, новый узел создается в памяти и заполняется данными. Затем, используя функцию FindPlace, мы определяем, перед каким узлом списка нам нужно его добавить.

Когда список будет готов, откройте файл для вывода и, используя стандартный проход по списку, отобразите найденные слова и значения счетчиков.

2.7 Удаление узла

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

Рисунок 6

Отдельно случай, когда первый элемент . При удалении узла память, которую занимал. Отдельно рассматриваем , когда удаляется элемент списка. В случае адрес узла совпадает адресом головы и надо записать в следующего элемента.

( &, )

{

= ;

( == )

= ->; // удаляем первый

{

( && -> != ) // элемент

= ->;

( == ) ; // если нашли, выход

-> = ->;

}

; // освобождаем память

}

2.8 Барьеры

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

2.9 Двусвязный список

Многие проблемы при с односвязным вызваны тем, в них перейти к элементу. Возникает естественная – хранить в ссылку не на следующий, и на элемент списка. Для к списку не одна -указатель, а – ссылка на «» списка () и «хвост» - последний ().

Рисунок 7

Каждый узел (кроме полезных ) также ссылку следующий за узел (поле ) и предыдущий ( ). Поле последнего элемента поле первого содержат . Узел так:

{

[40]; // данных

;

*, *; // на соседние

};

*; // тип «указатель на »

В дальнейшем мы считать, что указывает на списка, а – на конец :

= , = ;

Для пустого списка указателя равны .

2.10 Операции с двусвязным списком

Добавление узла начало списка.

При нового узла начало списка

1) установить узла голову существующего и его в ;

) установить ссылку бывшего первого (если он ) на ;

3) голову списка новый узел;

) если в не было одного элемента, списка также на новый .

Рисунок 8

По такой работает следующая :

( &, &, )

{

-> = ;

-> = ;

( ) -> = ;

= ;

( ! ) = ; // этот элемент –

}

Добавление узла в конец списка.

Из-за симметрии добавление нового узла NewNode в конец списка полностью аналогично, в процедуре вы всегда должны заменить Head на Tail и наоборот, а также изменить prev и next.

Добавление узла после указанного.

Дан адрес NewNode нового узла и адрес p одного из существующих узлов в списке. Вам нужно вставить новый узел в список после p. Если узел p является последним, то операция сводится к добавлению в конец списка (см. Выше). Если узел p не последний, то операция вставки выполняется в два этапа:

1) установить ссылки нового узла на следующий следующий (следующий) и предыдущий (предыдущий);

2) установить ссылки соседних узлов для включения NewNode в список.

Этот метод реализуется с помощью следующей процедуры (он также учитывает возможность вставки элемента в конец списка; для этого в параметрах передаются ссылки на начало и конец списка):

Рисунок 9

( &, &,

, )

{

( ! -> )

(, , ); // в конец

{

-> = ->; // меняем нового узла

-> = ;

->-> = ; // меняем соседних узлов

-> = ;

}

}

Добавление узла заданным выполняется .

Поиск узла в .

Проход по двусвязному может выполняться двух направлениях – головы к (как для ) или от к голове.

Удаление

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

Рисунок 10

( &, &, )
{
( == ) {
= ->; // удаляем элемент
( )
-> = ;
= ; // удалили элемент
}
{
->-> = ->;
( -> )
->-> = ->;
= ; // последний элемент
}
;
}

2.11 Циклические списки

Иногда список (односвязный или двусвязный) замыкают в кольцо, то есть указатель next последнего элемента указывает на первый элемент, и (для двусвязных списков) указатель prev первого элемента указывает на последний. В таких списках понятие «хвоста» списка не имеет смысла, для работы с ним надо использовать указатель на «голову», причем «головой» можно считать любой элемент.

ЗАКЛЮЧЕНИЕ

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

Динамическая структура данных характеризуется тем, что:

• у нее нет имени;

• выделяется память при выполнении программы;

• количество элементов конструкции не может быть фиксированным;

• размер структуры может измениться во время выполнения программы;

• в процессе выполнения программы характер взаимоотношений между элементами структуры может измениться.

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

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1. Антонов В.Б., Назарова О.В. Объектно-ориентированные данных // Информатика и техника, 2016
2. Вылиток А.А., Матвеева Т.К. Динамические данных. Задание практикума. Язык Паскаль: Учебно- пособие. (издание , переработанное и ) - М.: Издательский отдел Факультета ВМиК МГУ им. М.В. Ломоносова,
3. Кузниченко М.А. Динамические структуры данных: Учебное . – Орск: ОГТИ, 2011
4. Ландовский В.В. Структуры данных: Учебное . – Новосибирск, 2016
5. Назаренко, П. А. Н Алгоритмы и данных: учебное / П. А. Назаренко – Самара : ПГУТИ, 2015
6. Никлаус Вирт. Алгоритмы и данных. Новая версия Оберона + / Пер.с англ. Ткачев Ф. В. – М.: ДМК Пресс,
7. Русакова З.Н. Динамические структуры данных вычислительные алгоритмы. ++ - СПб.,
8. Степович-Цветкова Г.С. Программная реализация динамических данных: сборник трудов по международной научно- конференции: в частях. Научный центр «Диспут».