Файл: Методические указания для выполнения лабораторных работ по дисциплине "Алгоритмы и структуры данных" по теме "Динамические структуры данных".doc

Односв/двухсв бин дерево

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

для выполнения лабораторных работ

по дисциплине “Алгоритмы и структуры данных”

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

оглавление

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

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

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

Большинство задач, рассмотренных ранее, требовали работы со статическими переменными, - переменными, которые создаются в момент определения (описания) и уничтожаются автоматически при выходе программы из области их действия. Статические переменные и структуры данных характеризуются фиксированным размером выделенной для них памяти. Например, если описан массив int a[100] под него будет выдела sizeof(int)*100 байт, хотя в самой программе может реально использоваться лишь несколько первых элементов массива. Существуют задачи, которые исключают использование структур данных фиксированного размера и требуют введения динамических структур данных, способных увеличиваться в размерах в процессе работы программы. Если до начала работы с данными невозможно определить, сколько памяти потребуется для их хранения, то память должна выделять по мере необходимости отельными блоками, связанными друг с другом указателями. Динамическая структура может занимать несмежные участки оперативной памяти.

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

---

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

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

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

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

1.2.Операции с указателями

1. int *P;

Указатель находится в неопределенном состоянии, после его описания.

2. 
   P
   
   = new int;
   

Процедура new – отводит место в оперативной памяти под хранение

п
еременной целого типа, и этот адрес вносится в указатель P.

2. 
   P=Null;
   

Указатель на пустой адрес (никуда).

2. 
   d
   elete P;
   

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

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

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

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

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

1.4. Односвязные списки

Динамические переменные можно объединять в связанные динамические структуры.

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

---

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

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

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

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

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

struct Student {char Name[20]; //ФИО

int Year; //дата рождения

Student *Next }; //указатель на следующий элемент

Student *P; //объявляется указатель P

P = new Student; //выделяется память

P->Name = "Иванов";

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

P->Next = NULL;

delete P; // освобождение памяти

P->Name – обращение к полям структуры.

Тип указателя на элемент динамической структуры имеет тип структуры.

Рассмотренная динамическая структура называется односвязным списком.

Односвязные списки можно формировать в виде:

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

1. 
   При работе с очередью применяют указатели на начало (begp) и на конец (endp) очереди.
   

2 . При создании динамической структуры в виде стека – используют указатель на начало стека – top.

---

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

• 
  переход от элемента к элементу;
  
• 
  добавление нового элемента к списку;
  
• 
  исключение элемента из списка;
  
• 
  сортировка элементов.
  

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

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

Где: top – указатель на начало списка;

p – указатель на текущий элемент.

Ввод прекращается, если вместо количества товаров ввести 0.

s truct stud {char name[10];

int kol; Описаниеструктуры

stud *next;

};

#include

#include

using namespace std;

// Рекурсивная функция печати элементов односвязного спмска

void output( struct stud *p)

{if (p==NULL) { cout<<"\n END____ \n";

return; // выход из функции при достижении конца списка

}

cout<<"\n "<
name<<” ”p->kol;

output(p->next);

}

int main()

{ // Объявляются указатели на структур,

// top - указатель на начало списка

// p - указатель на текущий элемент

stud *top,*p;

top = NULL;

do

{ p = new stud; // выделяется память под новый элемент списка

cout<<"\n Ведите наименование "; cin>>p->name;

cout<<"\n Введите количество "; cin>>p->kol;

if (p->kol != 0) {p->next=top; top=p;}

}

while(p->kol!=0);

cout<<"\n____ Стек____ \n";

//Обращение к рекурсивной функции печати элементов стека

output(top);

/ *do

{cout<<"\n "<
name;

cout<<"\n "<kol; // Печать элементов стека через цикл

p=p->next;

}

while (p!= NULL);*/

getch(); }

Задача: ввод и создание односвязного списка в виде стека, элементы которого отсортированы по возрастанию. Сортировка элементов выполняется непосредственно при создании списка, т.е. для каждого элемента находится свое место в списке.
Где - top, p, t, n – указатели на вершину, предыдущий, текущий и новый элемент

списка соответственно.
s truct stud {char name[10];

int kol; Описание структуры

stud *next;

};

#include

#include

#include

using namespace std;

// Рекурсивная функция печати элементов стека

void output( struct stud *p)

{ if (p==NULL) {cout<<"\n END+++++ \n"; return;}

cout<<"\n "<
name<<" "<
kol;

output(p->next);

}

int main()

{

// Описываются указатели (вершина, предыдущий, текущий, новый)

stud *top,*p,*t,*n;

char name[10]; int kol;

top = NULL;

do

{ cout<<"\n Введите наименование "; cin>>name;

cout<<"\n Введите количество "; cin>>kol;

if ( kol !=0 )

{ // Выделение памяти под новый элемент

n = new stud;

strcpy(n->name,name);

n->kol=kol;

n->next=NULL;

t=top; p=NULL;

// Поиск места для нового элемента

if (t!=NULL)

while ( kol > t->kol && t!=NULL)

{ p=t; t=t->next;

if (t==NULL)break;

}

if (p==NULL)

//Вставка элемента в начало списка

{n->next=top; top=n;}

else

// Вставка элемента в конец списка

{ if (t==NULL) {p->next=n; n->next=NULL;}

else

// Вставка элемента в середину списка

{n->next=p->next; p->next=n;}

}

}

} while( kol != 0);

cout<<"\n Stek \n";

output(top); // Печать списка

getch();

}
Задача: удаление элемента из односвязного списка.

name – элемент, который необходимо удалить;

top, t, p – указатели на вершину, текущей и предыдущий элемент соответственно;

f – флаг,

f=1 - признак того, что элемент найден.





struct stud {char name[10];

int kol;

stud *next;};

#include

#include

#include

using namespace std;

// Рекурсивная функция печати элементов стека

void output( struct stud *p)

{ if (p==NULL) {cout<<"\n END+++++ \n"; return;}

cout<<"\n "<
name<<" "<
kol;

output(p->next);

}

int main()

{

// Описываются указатели (вершина, предыдущий, текущий, новый)

stud *top,*p,*t,*n;

char name[10]; int kol;

top = NULL;

do

{ cout<<"\n vv name "; cin>>name;

cout<<"\n vv kol "; cin>>kol;

if ( kol !=0 )

{ // Выделение памяти под новый элемент

n = new stud;

strcpy(n->name,name);

n->kol=kol; n->next=NULL;

t=top; p=NULL;

// Поиск места для нового элемента

if (t!=NULL)

while ( kol > t->kol && t!=NULL)

{ p=t; t=t->next;

if (t==NULL)break;

}

if (p==NULL)

//Вставка элемента в начало списка

{n->next=top; top=n;}

else

// Вставка элемента в конец списка

{ if (t==NULL) {p->next=n; n->next=NULL;}

else

// Вставка элемента в середину списка

{n->next=p->next; p->next=n;}

}

}

} while( kol != 0);

cout<<"\n Стек \n";

output(top);

t=top; p=NULL; int f=0;

// ввести наименование товара, который необходимо удалить

cout<<"\n Введите наименование товара \n"; cin>>name;

while ( f==0 && t!=NULL)

{

if ( strcmp(t->name, name)==0)

{

if (p==NULL)

top=t->next; //Удаление первого элемента списка

else p->next=t->next; //Удаление среднего или последнего элемента //delete t;

f=1; // Элемент найден

}

else {p=t; t=t->next;} // Переход к след. элементу

}

if (f==0) cout<<"\n Элемет не найден ! \n";

else {cout<<"\n Stek \n"; output(top);}

getch();

}

1.5. Двусвязные списки.

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

Описание двусвязных списков:

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

- переход от элемента к элементу;

- сортировка элементов;

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

- исключение элемента из списка.

Описание двусвязного списка;

struct stud {char name[10];

int kol;

stud *l,*r;

};
Где: l – указатель на предыдущиц элемент списка;

r - указаиель на последующий элемент списка/

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




.

1.6. Бинарные деревья.

Бинарное дерево - это структура в которой:

• 
  есть только один узел, в который не входит ни одного ребра (этот узел называется вершиной);
  
• 
  в каждый узел, кроме вершины, входит только одно ребро;
  
• 
  из каждого узла исходит не более 2-х ребер.
  

Бинарные деревья позволяют осуществить быстрый поиск данных

Пусть дана последовательность:

100, 20, 120, 130, 50, 15, 30, 35, 25, 55, 60, 110.

При построении бинарного дерева используется следующее правило:

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


Описание бинарного дерева:

s truct stud {char name[10]; информационные поля

int kol;

stud *l,*r;

};

Где; l - указатель на узел, стоящий влево-вниз;

r - указатель на узел, стоящий вправо-вниз.

Задача: создание бинарного дерева, отсортированного по полю “kol” (количество).

Где: top, n – вершина дерева и новый узлы дерева соответственно.

В данной задаче использованы следующие рекурсивные функции:

• 
  insert – вставка нового элемента в дерево;
  
• 
  outrec – обход бинарного дерева и печать.
  

struct stud {char name[10];

int kol;

stud *l,*r;

};

#include

#include

#include

using namespace std;
// Рекурсивная функция - вставка узла в дерево

struct stud *insert( struct stud *n,struct stud *top )

{

if (top==NULL){ top=n; n->r=NULL; n->l=NULL;}

else

if ( n->kol < top->kol ) top->l=insert(n,top->l);

else top->r=insert(n,top->r);

return (top); // возвращает указатель на вершину дерева

}

// Рекурсивная функция - обход дерева и печать узлов

void output(struct stud *top)

{

if (top->l!=NULL) output(top->l);

cout<<"\n "<name<<" "<kol<<"\n";

if (top->r!=NULL) output(top->r);

}
int main()

{

stud *top,*n; // описание указателей(вершина, новый)

char name[10]; int kol;

top = NULL;

do

{ cout<<"\n Name "; cin>>name;

cout<<"\n Kol "; cin>>kol;

if ( kol !=0 )

{ n = new stud; // выделение памяти под новый узел

strcpy(n->name,name);

n->kol=kol;

top=insert(n,top); //вставка нового узла в дерево

}

} while (kol!=0);

cout<<"\n ++++++++++++++++++++++++\n";

cout<<"\n Вершина - "<kol<<"\n";

cout<<"\n Дерево\n";

output(top); //обход дерева и печать узлов

getch();

}

https://prog-cpp.ru/data-tree/

Составитель:

ст. преподаватель _______________ Д.М.Ахмедханлы

---