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

Сентябрь 7, 2022

Главная
Алгебра
Динамические структуры данных

Содержание

2. Элемент динамической структуры Р – указатель; D – данные.
3. Типы структур: списки деревья графы односвязный двунаправленный (двусвязный) циклические списки (кольца)
4. Объявление динамических структур struct имя_типа { информационное поле; адресное поле; };
5. struct TNode { //информационное поле int Data; //адресное поле TNode *Next; };
7. Доступ к данным в динамических структурах
8. УказательНаСтруктуру->ИмяЭлемента Например: p->Data; p->Next;
9. struct Node { char Name[20]; int Value; Node *Next; };
10. int _tmain() { //объявляется указатель Node *PNode; //выделяется память PNode = new Node; //присваиваются значения strcpy(PNode->Name
11. Memo1->Clear(); Node *PNode; PNode = new Node; AnsiString St="STO"; strcpy(PNode->Name ,St.c_str()); PNode->Value = 28; PNode->Next =
12. struct Node { String Name; int Value; Node *Next; };
13. Node *PNode; PNode = new Node; PNode->Name= "STO"; PNode->Value = 28; PNode->Next = NULL; Memo1->Lines->Add("name="+(PNode->Name)+ "
14. Списки Однонаправленный (односвязный) список
15. struct имя_типа { информационное поле; адресное поле; }; struct Node { int key; Node *pnext; };
16. struct List {//структура данных int Data; //информационное поле List *Next; //адресное поле };
17. Создание однонаправленного списка int n; cout cin>>n; //указатель на текущий элемент списка List *head, *first;//указатель на
18. //заполняем первый элемент cout cin >>head->Data; //заполняем остальные элементы списка for(int i=1;i { head->Next= new List;
19. просмотр однонаправленного списка cout head=first; //пока не встретится признак //конца списка NULL while(head != NULL) {
20. В визуальной среде
21. TForm1 *Form1; struct List {//структура данных int Data; //информационное поле List *Next; //адресное поле }; List
22. Обработчик события нажатие на кнопку «Заполнить первый элемент» head=new List; //сохранили адрес первого элемента, //чтобы потом
23. Обработчик события нажатие на кнопку «Заполнить следующий элемент» head->Next= new List; head=head->Next; head->Data=StrToInt(Edit1->Text);
24. Обработчик события нажатие на кнопку «Конец списка» //определяем конец списка для //последнего элемента head->Next=NULL;
25. Обработчик события нажатие на кнопку «Просмотр списка» Memo1->Clear(); head=first; //пока не встретится признак конца списка NULL
27. void PrintM(List *head) { //head=first; //пока не встретится признак конца списка NULL while(head != NULL) {
28. Вставка элемента в однонаправленный список
29. /*функция добавления элемента с заданным номером в однонаправленный список*/ List* InsertM(List* Head, int Number, //номер добавляемого
30. else { //список не пуст List *Current=Head; for(int i=1; i Next!=NULL; i++) Current=Current->Next; if (Number ==
31. Обработчик события кнопки «Добавить элемент» int Numb, DataIt; Numb=StrToInt(Edit3->Text); DataIt=StrToInt(Edit1->Text); //добавляем элемент, в качестве аргумента функции
32. Удаление элемента из однонаправленного списка
33. /*удаление элемента с заданным номером из однонаправленного списка*/ List* DeleteM(List* Head, int Number){ List *ptr;//вспомогательный указатель
34. else {//удаляем не первый элемент ptr = Head; while (ptr->Next != Current) ptr = ptr->Next; ptr->Next
35. Обработчик события нажатие на кнопку «Удалить элемент» int Numb; Numb=StrToInt(Edit3->Text); head=DeleteM(head,Numb); Memo1->Clear(); PrintM(head);
36. /*функция поиска элемента с заданным значением в однонаправленном списке результат работы функции: true − искомый элемент
37. //функция удаления однонаправленного списка void Delete_ListM(List* Head){ if (Head != NULL){ Delete_ListM(Head->Next); delete Head; } }
38. Пример класса для работы с односвязным списком struct element { //значения из x //будут передаваться в
39. class List //Класс Список { element **Head, *First; public: List() { Head=new element; First=Head; Head->x=1;} //Конструктор
40. List::~List() //Деструктор определен вне класса { //Пока по адресу не пусто while (Head!=NULL) { //Временная переменная
41. //Функция добавления элементов в список //после х указываются все заполняемые поля //структуры void List::Add(int x) {
42. //Функция отображения списка на экране void List::Show() { //Определяем указатель, который изначально //равен адресу начала списка
43. //использование класса List ob;//Переменная, тип которой список объявляем //глобально . . . . Обработчик события нажатие
45. Скачать презентацию

Слайд 2

Элемент динамической структуры
Р – указатель;
D – данные.

Слайд 3

Типы структур:
списки
деревья
графы
односвязный
двунаправленный
(двусвязный)
циклические списки (кольца)

Слайд 4

$Объявление динамических структур struct имя_типа { информационное поле; адресное поле; };$

Объявление динамических структур
struct имя_типа {
информационное поле;
адресное поле;
};

Слайд 5

struct TNode {
//информационное поле
int Data;
//адресное поле
TNode *Next;
};

Слайд 6

Слайд 7

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

Слайд 8

УказательНаСтруктуру->ИмяЭлемента
Например:
p->Data;
p->Next;

Слайд 9

struct Node
{
char Name[20];
int Value;
Node *Next;
};

Слайд 10

$int _tmain() { //объявляется указатель Node *PNode; //выделяется память PNode =$

int _tmain()
{ //объявляется указатель
Node *PNode;
//выделяется память
PNode = new Node;
//присваиваются

значения
strcpy(PNode->Name , "STO");
PNode->Value = 28;
PNode->Next = NULL;
cout<< "name="<Name
<<"\nvalue="<< PNode->Value;
//освобождение памяти
delete PNode;}

Слайд 11

Memo1->Clear();
Node *PNode;
PNode = new Node;
AnsiString St="STO";
strcpy(PNode->Name ,St.c_str());
PNode->Value = 28;
PNode->Next = NULL;
Memo1->Lines->Add("name="+

AnsiString(PNode->Name)+
" value="+(PNode->Value));
delete PNode;

Слайд 12

struct Node
{
String Name;
int Value;
Node *Next;
};

Слайд 13

Node *PNode;
PNode = new Node;
PNode->Name= "STO";
PNode->Value = 28;
PNode->Next = NULL;
Memo1->Lines->Add("name="+(PNode->Name)+ "

value="+(PNode->Value));
delete PNode;

Слайд 14

Списки Однонаправленный (односвязный) список

Слайд 15

$struct имя_типа { информационное поле; адресное поле; }; struct Node {$

struct имя_типа {
информационное поле;
адресное поле;
};
struct Node {
int

key;
Node *pnext;
};
struct point {
char name[10]; //String name;
int age;
point *pnext; };

Слайд 16

struct List {//структура данных int Data; //информационное поле List *Next; //адресное

поле
};

Слайд 17

Создание однонаправленного списка
int n;
cout<<"vvedite kol-vo elementov spiska:”;
cin>>n;
//указатель на текущий элемент списка
List

*head,
*first;//указатель на первый элемент
//выделяется память под первый элемент
head=new List;
//сохранили адрес первого элемента,
//чтобы потом обратиться к нему
first=head;

Слайд 18

//заполняем первый элемент
cout << "Vvedite znachenie ";
cin >>head->Data;
//заполняем остальные элементы списка
for(int

i=1;i{ head->Next= new List;
head=head->Next;
cout << "Vvedite znachenie ";
cin >>head->Data;
}
//определяем конец списка для
//последнего элемента
head->Next=NULL;

Слайд 19

просмотр однонаправленного списка
cout<<"elementi spiska:\n";
head=first;
//пока не встретится признак
//конца списка NULL
while(head !=

NULL)
{ //вывод на экран значения //информационного поля
cout << head->Data << "\t";
//переход к следующему элементу
head=head->Next;
} cout << "\n";

Слайд 20

В визуальной среде

Слайд 21

TForm1 Form1;
struct List {//структура данных
int Data; //информационное поле
List Next; //адресное поле

};
List *head,//указатель на текущий элемент списка
*first;//указатель на первый элемент списка

Слайд 22

Обработчик события нажатие на кнопку
«Заполнить первый элемент»
head=new List;
//сохранили адрес

первого элемента,
//чтобы потом обратиться к нему
first=head;
//заполняем первый элемент
head->Data=StrToInt(Edit1->Text);

Слайд 23

Обработчик события нажатие на кнопку
«Заполнить следующий элемент»
head->Next= new List;
head=head->Next;
head->Data=StrToInt(Edit1->Text);

Слайд 24

Обработчик события нажатие на кнопку
«Конец списка»
//определяем конец списка для

//последнего элемента
head->Next=NULL;

Слайд 25

Обработчик события нажатие на кнопку
«Просмотр списка»
Memo1->Clear();
head=first;
//пока не встретится признак конца

списка NULL
while(head != NULL)
{
//вывод на экран значения информационного поля
Memo1->Lines->Add(head->Data);
head=head->Next;
}

Слайд 26

Слайд 27

void PrintM(List *head) {
//head=first;
//пока не встретится признак конца списка NULL
while(head !=

NULL) {
Form1->Memo1->Lines->Add(head->Data);
head=head->Next;
}
}
Обработчик события кнопки
«Просмотр списка»
Memo1->Clear();
PrintM(first);

Слайд 28

Вставка элемента в однонаправленный список

Слайд 29

/функция добавления элемента с заданным номером в однонаправленный список/
List* InsertM(List* Head,
int

Number, //номер добавляемого элемента списка
int DataItem ) { //значение добавляемого элемента списка
Number--; //значение номер уменьшается на 1
//выделяется память для вспомогательного списка
List *NewItem=new(List);
//в поле дата вспомогательного списка
//заносится значение добавляемого элемента списка
NewItem->Data=DataItem;
// признак конца списка NULL в адресное поле
NewItem->Next = NULL;
//если список пуст
if (Head == NULL) {
Head = NewItem; //создаем первый элемент списка
}

Слайд 30

else {
//список не пуст
List *Current=Head;
for(int i=1; i < Number

&& Current->Next!=NULL; i++)
Current=Current->Next;
if (Number == 0) {
//вставляем новый элемент на первое место
NewItem->Next = Head;
Head = NewItem;
}
else {//вставляем новый элемент на не первое место
if (Current->Next != NULL)
NewItem->Next = Current->Next;
Current->Next = NewItem;
}
} return Head;}

Слайд 31

Обработчик события кнопки
«Добавить элемент»
int Numb, DataIt;
Numb=StrToInt(Edit3->Text);
DataIt=StrToInt(Edit1->Text);
//добавляем элемент,

в качестве аргумента функции используем сохраненный
//указатель на первый элемент first
head=InsertM(first, Numb, DataIt);
Memo1->Clear();
PrintM(head);

Слайд 32

Удаление элемента из однонаправленного списка

Слайд 33

/удаление элемента с заданным номером из однонаправленного списка/
List* DeleteM(List* Head, int

Number){
List *ptr;//вспомогательный указатель
List *Current = Head;
for (int i = 1; i < Number && Current != NULL; i++)
Current = Current->Next;
if (Current != NULL){//проверка на корректность
if (Current == Head){//удаляем первый элемент
Head = Head->Next;
delete(Current);
Current = Head;
}

Слайд 34

else {//удаляем не первый элемент
ptr = Head;
while (ptr->Next !=

Current)
ptr = ptr->Next;
ptr->Next = Current->Next;
delete(Current);
Current=ptr;
}
}
return Head;
}

Слайд 35

Обработчик события нажатие на кнопку
«Удалить элемент»
int Numb;
Numb=StrToInt(Edit3->Text);
head=DeleteM(head,Numb);
Memo1->Clear();

PrintM(head);

Слайд 36

/*функция поиска элемента с заданным значением в однонаправленном списке результат работы

функции: true − искомый элемент имеется, false − искомый элемент отсутствует*/

bool FindM (List* Head, int DataItem){
//вспомогательный указатель
List *ptr;
ptr = Head;
//пока не конец списка
while (ptr != NULL){
//последовательное сравнение элементов списка с заданным значением
if (DataItem == ptr->Data) return true;
//значение найдено
else ptr = ptr->Next; // переход к следующему
}
return false; } //значение не найдено

Слайд 37

$//функция удаления однонаправленного списка void Delete_ListM(List* Head){ if (Head != NULL){ Delete_ListM(Head->Next); delete Head; } }$

//функция удаления однонаправленного списка
void Delete_ListM(List* Head){
if (Head != NULL){
Delete_ListM(Head->Next);
delete Head;

}
}

Слайд 38

Пример класса для работы с односвязным списком
struct element {
//значения из x

//будут передаваться в список
//сюда добавить другие поля вашей структуры
int x;
//Адресное поле
element *Next;
};

Слайд 39

class List //Класс Список
{
element **Head, *First;
public:
List() {
Head=new element;

First=Head;
Head->x=1;} //Конструктор и инициализация
//первого элемента списка
~List(); //Деструктор. определен вне класса
//Функция для добавления значений в список
void Add(int x);
//Функция для отображения списка на экране
void Show();
};

Слайд 40

List::~List() //Деструктор определен вне класса
{
//Пока по адресу не пусто
while (Head!=NULL)

{
//Временная переменная для хранения адреса //следующего элемента
        element *temp=Head->Next;
//Освобождаем адрес обозначающий начало delete Head;
//Меняем адрес на следующий
        Head=temp;
}
}

Слайд 41

//Функция добавления элементов в список
//после х указываются все заполняемые поля //структуры
void

List::Add(int x) {
//При каждом вызове выделяется память
Head->Next= new element;
Head=Head->Next;
Head->x=x;
}

Слайд 42

//Функция отображения списка на экране
void List::Show() {
//Определяем указатель, который изначально //равен

адресу начала списка
element *temp=First;
//До тех пор пока не встретит пустое значение
while (temp!=NULL) {
//Выведет элемент x из списка в Memo1 на форме с именем Form3 – указывайте свою форму
Form3->Memo1->Lines->Add(temp->x);
//Указываем, что далее нам нужен следующий //элемент
temp=temp->Next;
} }

Слайд 43

//использование класса
List ob;//Переменная, тип которой список объявляем //глобально
. . . .
Обработчик

события нажатие на кнопку
«Заполнить следующий элемент»
//Считывание из визуальных компонентов
int x=StrToInt(Edit1->Text);
//Добавление элемента в список
ob.Add(x);

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

Содержание

Элемент динамической структурыР – указатель; D – данные.

Типы структур:спискидеревьяграфыодносвязныйдвунаправленный (двусвязный)циклические списки (кольца)

Объявление динамических структурstruct имя_типа { информационное поле; адресное поле; };

struct TNode {//информационное полеint Data;//адресное полеTNode *Next;};

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

УказательНаСтруктуру->ИмяЭлементаНапример:p->Data;p->Next;

struct Node {char Name[20];int Value;Node *Next; };

int _tmain(){ //объявляется указательNode *PNode; //выделяется памятьPNode = new Node; //присваиваются

Memo1->Clear();Node *PNode;PNode = new Node;AnsiString St="STO";strcpy(PNode->Name ,St.c_str());PNode->Value = 28;PNode->Next = NULL;Memo1->Lines->Add("name="+

struct Node{String Name;int Value;Node *Next; };

Node *PNode;PNode = new Node;PNode->Name= "STO";PNode->Value = 28;PNode->Next = NULL;Memo1->Lines->Add("name="+(PNode->Name)+ "

Списки Однонаправленный (односвязный) список

struct имя_типа { информационное поле; адресное поле; };struct Node { int

struct List {//структура данных int Data; //информационное поле List *Next; //адресное

Создание однонаправленного списка int n;cout<<"vvedite kol-vo elementov spiska:”;cin>>n;//указатель на текущий элемент спискаList

//заполняем первый элементcout << "Vvedite znachenie ";cin >>head->Data;//заполняем остальные элементы спискаfor(int

просмотр однонаправленного спискаcout<<"elementi spiska:\n";head=first;//пока не встретится признак //конца списка NULL while(head !=

В визуальной среде

TForm1 *Form1;struct List {//структура данныхint Data; //информационное полеList *Next; //адресное поле

Обработчик события нажатие на кнопку «Заполнить первый элемент» head=new List;//сохранили адрес

Обработчик события нажатие на кнопку «Заполнить следующий элемент»head->Next= new List;head=head->Next;head->Data=StrToInt(Edit1->Text);

Обработчик события нажатие на кнопку «Конец списка» //определяем конец списка для

Обработчик события нажатие на кнопку «Просмотр списка»Memo1->Clear();head=first;//пока не встретится признак конца

void PrintM(List *head) {//head=first;//пока не встретится признак конца списка NULL while(head !=