Файл: Операции производимые с данными.pdf

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

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

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

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

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

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

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

Глава 1. Динамические структуры данных.

1.1. Введение в динамические структуры данных.

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

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

Рисунок 1 - Обобщенная классификация данных динамической структуры

К данным динамической структуры относят файлы, несвязанные и связанные динамические данные.

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

1.2. Статические и динамические переменные в Паскале.

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

Все переменные, объявленные в программе, размещаются в одной непрерывной области оперативной памяти – сегмент данных. Длина сегмента данных определяется архитектурой микропроцессора и составляет обычно 65536 байт.

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

Предположим, например, что у вас есть программа, требующая массива в 400 строк по 100 символов каждая. Для этого массива требуется примерно 40К, что меньше максимума в 64К. Если остальные ваши переменные помещаются в оставшиеся 24К, массив такого объема проблемы не представляет. Но что если вам нужно два таких массива? Это потребовало бы 80К, и 64К сегмента данных не хватит. Другим общим примером является сортировка. Обычно когда вы сортируете большой объем данных, то делаете копию массива, сортируете копию, а затем записываете отсортированные данные обратно в исходный массив. Это сохраняет целостность ваших данных, но требует также наличия во время сортировки двух копий данных.

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

Динамическая память (ДП) – это оперативная память ПК, предоставляемая программе при ее работе, за вычетом сегмента данных (64 Кб), стека (16 Кб) и собственно тела программы. Размер динамической памяти можно варьировать. По умолчанию ДП – вся доступная память ПК.

ДП – это фактически единственная возможность обработки массивов данных большой размерности. Многие практические задачи трудно или невозможно решить без использования ДП. Например, при разработке САПР статическое распределение памяти невозможно, т.к. размерность математических моделей в разных проектах может значительно различаться.

И статические и динамические переменные вызываются по их адресам. Без адреса не получить доступа к нужной ячейке памяти, но при использовании статических переменных, адрес непосредственно не указывается. Обращение осуществляется по имени. Компилятор размещает переменные в памяти и подставляет нужные адреса в коды команд.

Адресация динамических переменных осуществляется через Динамические структуры данных. Линейные списки. Их значения определяют адрес объекта.

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

Выделение памяти под динамическую переменную;
Инициализация указателя;
Освобождение памяти после использования динамической переменной.

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

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

1.3. Динамические структуры данных. Линейные списки

Вся ДП рассматривается как сплошной массив байтов, который называется кучей.

Рисунок 2 – Расположение кучи в памяти ПК.

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

Heaporg – начало кучи;
Heapend – конец кучи;
Heapptr – текущая граница незанятой ДП.

Выделение памяти под динамическую переменную осуществляется процедурой:

New (переменная_типа_указатель)

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

Var i, j: ^integer;

r: ^real;

begin

new( i); {после этого указатель i приобретает значение адреса Heapptr, а Heapptr смещается на 2 байта}

……………

new( r) ; { r приобретает значение Heapptr, а Heapptr смещается на 6 байт}

Рисунок 3 – Графически действие процедуры new

Вещественная переменная --->R^:= sqr( R) <---аргумент – адрес.

Рисунок 4 – Пример работы с указателями

Работа с динамическими данными имеет некоторое преимущество по сравнению с работой со статическими данными [1-4]:

Подключая динамическую память, можно увеличивать объем обрабатываемых данных;

Можно создать динамические структуры данных переменного размера.

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

В С++ элемент линейного списка представляет собой структуру, которая содержит минимум два поля. Например, первое поле для хранения данных, а второе для хранения значения указателя:

struct <имя_типа_структуры> {

<имя_типа> <имя_поля_данных>;

<имя_типа_структуры> *<имя_поля_указателя>;};

Линейный список является самым простым способом связывания множества элементов. Когда каждый элемент списка содержит ссылку на следующий элемент, то такой список называется однонаправленным или односвязным. Если каждый элемент списка имеет одну ссылку на следующий элемент, а другую — на предыдущий, то список называется двунаправленным или двусвязным.

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

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

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

чтение элемента с заданным ключом;

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

удаление элемента с заданным ключом;

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

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

Задача №1

Создать односвязный список, состоящий из списка студентов группы (ф.и.о., дата рождения (день, месяц, год)). Вывести список на экран.

Решение

#include

struct spisok{ char fam[20];

int d,m,y;

spisok *p; };

void main () {

int n,j;

// Предполагаем, что в списке больше одного элемента

cout<<"Введите количество записей: \n";

cin>>n;

spisok *t;

/*указатель first всегда будет указывать на 1-й элемент списка */

spisok *first=new spisok;

/*Вводим данные первого элемента*/

cout<<"Введите фамилию \n"; gets(first->fam);

cout<<"Введите дату рождения в виде: 7 11 2006 \ (7-е ноября 2006 года)";

cin>>first->d>>first->m>>first->y;

first->p=0;

t=first;

/*Вводим данные для последующих элементов*/

for (j=2; j<=n; j++){

spisok *z=new spisok;

if(t!=0) t->p=z;

cout<<"Введите фамилию \n"; gets(z->fam);

cout<<"Введите дату рождения в виде: 7 11 2006";

cin>>z->d>>z->m>>z->y;

t=z; t->p=0;

}

cout <<"Исходный список\n";

t=first;

j=1;

while(t!=0){

cout

Задача №2

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

Решение

/* подключение заголовочных файлов */

struct spisok{ char fam[20];

int d,m,y;

spisok *p; };

void main () {

int n,j;

cout<<"Введите количество записей: \n"; cin>>n;

spisok *t;

spisok *first=new spisok;

cout<<"Введите фамилию \n"; gets(first->fam);

cout<<"Введите дату рождения в виде: 7 11 2006 \ (7-е ноября 2006 года)";

cin>>first->d>>first->m>>first->y;

first->p=0;

t=first;

for (j=2; j<=n; j++){

spisok *z=new spisok;

if(t!=0) t->p=z;

cout<<"Введите фамилию \n"; gets(z->fam);

cout<<"Введите дату рождения в виде: 7 11 2006";

cin>>z->d>>z->m>>z->y;

t=z; t->p=0;

}

cout <<"Введенный список\n";

t=first;

j=1;

while(t!=0){

cout>d>>m>>y;

t=first;

while(t!=0){

if(d==t->d && m==t->m && y==t->y){

cout<<"\n найденный по ключу элемент списка \n";

cout

Задача №3

Список, созданной в задаче №1, отсортировать по алфавиту.

Смотрите также файлы

Корпоративная культура в организации.pdf

Развитие взглядов на управление человеческими ресурсами (новая теория и научные подходы).pdf

Стандарты управления проектами ( Управление проектами и его значение в деятельности современного предприятия ).pdf

Организационная культура и ее роль в современных организациях ( ТФакторы, влияющие на организационную культуру ).pdf

Основные нормативные документы, регулирующие ведение бухгалтерского учета в организациях. Международные стандарты бухгалтерского учета ( Национальная система нормативного регулирования бухгалтерского учета и ее структура ).pdf

Файл: Операции производимые с данными.pdf

Введение

Глава 1. Динамические структуры данных.

1.1. Введение в динамические структуры данных.

1.2. Статические и динамические переменные в Паскале.

1.3. Динамические структуры данных. Линейные списки

Смотрите также файлы

Информация

Списки файлов

Дополнительно