ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.06.2021
Просмотров: 1693
Скачиваний: 3
76
Beg – указатель на начало списка
22. Динамические структуры данных
Во многих задачах требуется использовать данные, у которых конфигурация,
размеры и состав могут меняться в процессе выполнения программы. Для их
представления используют динамические информационные структуры. К таким
структурам относят:
-
линейные списки;
-
стеки;
-
очереди;
-
бинарные деревья;
Они отличаются способом связи отдельных элементов и допустимыми
операциями. Динамическая структура может занимать несмежные участки
динамической памяти.
Наиболее
простой
динамической
структурой
является
линейный
однонаправленный список, элементами которого служат объекты структурного типа
(рис.4).
Информационное
поле
адресное
поле
Информационное
поле
NULL
Рис.4. Линейный однонаправленный список
22.1. Линейный однонаправленный список
Описание простейшего элемента такого списка выглядит следующим образом:
struct имя_типа
{
информационное поле;
адресное поле;
};
Информационное поле – это поле любого, ранее объявленного или стандартного, типа;
адресное поле – это указатель на объект того же типа, что и определяемая структура, в
него записывается адрес следующего элемента списка.
Информационных полей может быть несколько.
Примеры.
1. struct Node
{
int key;//информационное поле
Node*next;//адресное поле
};
2. struct point
{
char*name;//информационное поле
int age;//информационное поле
point*next;//адресное поле
};
Каждый элемент списка содержит ключ, который идентифицирует этот элемент.
Ключ обычно бывает либо целым числом (пример 1), либо строкой (пример 2).
Над списками можно выполнять следующие операции:
-
начальное формирование списка (создание первого элемента);
-
добавление элемента в конец списка;
77
-
добавление элемента в начало списка;
-
удаление элемента с заданным номером;
-
чтение элемента с заданным ключом;
-
вставка элемента в заданное место списка (до или после элемента с
заданным ключом);
-
упорядочивание списка по ключу
и др.
Пример1. Создание и печать однонаправленного списка
#include <iostream.h>
#include<string.h>
//описание структуры
struct point
{char *name;//информационное поле
int age;//информационное поле
point*next;//адресное поле
};
point* make_point()
//создание одного элемента
{
point*p=new(point);//выделить память
char s[20];
cout<<"\nEnter the name:";
cin>>s;
p->name=new char[strlen(s)+1];//выделить память под динамическую строку
символов
strcpy(p->name,s);//записать информацию в строку символов
cout<<"\nEnter the age";
cin>>p->age;
p->next=0;//сформировать адресное поле
return p;
}
void print_point(point*p)
//печать информационных полей одного элемента списка
{
cout<<"\nNAME:"<<p->name;
cout<<"\nAGE:"<<p->age;
cout<<"\n--------------------------------\n";
}
point* make_list(int n)
//формирование списка из n элементов
{
point* beg=make_point();//сформировать первый элемент
point*r;
for(int i=1;i<n;i++)
{
r=make_point();//сформировать следующий элемент
//добавление в начало списка
r->next=beg;//сформировать адресное поле
78
beg=r;//изменить адрес первого элемента списка
}
return beg;//вернуть адрес начала списка
}
int print_list(point*beg)
//печать списка, на который указывает указатель beg
{
point*p=beg;//р присвоить адрес первого элемента списка
int k=0;//счетчик количества напечатанных элементов
while(p)//пока нет конца списка
{
print_point(p);//печать элемента, на который указывает элемент p
p=p->next;//переход к следующему элементу
k++;
}
return k;//количество элементов в списке
}
void main()
{
int n;
cout<<"\nEnter the size of list";
cin>>n;
point*beg=make_list(n);//формирование списка
if(!print_list(beg)) cout<<"\nThe list is empty";}//печать списка
Пример 2. Удаление из однонаправленного списка элемента с номером k (рис
5.).
Рис. 5. Удаление элемента с номером k из однонаправленного списка
point*del_point(point*beg,int k)
//удаление элемента с номером к
{
point*p=beg,//поставить вспомогательную переменную на начало списка
*r;//вспомогательная переменная для удаления
int i=0;//счетчик элементов в списке
if(k==0)
{//удалить первый элемент
beg=p->next;
delete[]p->name;//удалить динамическое поле name
delete[]p;//удалить элемент из списка
return beg;//вернуть адрес первого элемента списка
}
beg p k
79
while(p)//пока нет конца списка
{
if(i==k-1)//дошли до элемента с номером k-1, чтобы поменять его
поле next
{//удалить элемент
r=p->next;//поставить r на удаляемый элемент
if(r)//если p не последний элемент
{
p->next=r->next;//исключить r из списка
delete[]r->name;//удалить динамическое поле name
delete[]r;//удалить элемент из списка
}
else p->next=0;//если p -последний элемент, то в поле next
присвоить NULL
}
p=p->next;//переход к следующему элементу списка
i++;//увеличить счетчик элементов
}
return beg;//вернуть адрес первого элемента}
22.2. Работа с двунаправленным списком
beg
pred key next
Рис. 6 Двунаправленный список
Пример 3.
1. Создать двунаправленный список, выполнить удаление элемента с заданным
номером, добавление элемента с заданным номером, печать полученных списков.
#include <iostream.h>
struct point//описание структуры
{
int key;//ключевое поле
point* pred,*next;//адресные поля
};
point*make_list()
{
int n;
cout<<"n-?";cin>>n;
point *p,*r,*beg;
p=new (point);//создать первый элемент
beg=p;//запомнить адрес в переменную beg, в которой хранится начало
списка
cout<<"key-?";cin>>p->key;//заполнить ключевое поле
p->pred=0;p->next=0;//запомнить адресные поля
80
for(int i=1;i<n;i++)//добавить элементы в конец списка
{
r=new(point);//новый элемент
cout<<"key-?";cin>>r->key;//адресное поле
p->next=r;//связать начало списка с r
r->pred=p;//связать r с началом списка
r->next=0;//обнулить последнее адресное поле
p=r;//передвинуть p на последний элемент списка
}
return beg;//вернуть первый элемент списка
}
void print_list(point *beg)
{
if (beg==0)//если список пустой
{
cout<<"The list is empty\n";
return;
}
point*p=beg;
while(p)//пока не конец списка
{
cout<<p->key<<"\t";
p=p->next;//перейти на следующий
}
cout<<"\n";
}
point* del_point(point*beg, int k)
{
point *p=beg;
if(k==0)//удалить первый элемент
{
beg=beg->next;//переставить начало списка на следующий элемент
if(beg==0)return 0;//если в списке только один элемент
beg->pred=0;//обнулить адрес предыдущего элемента
delete p;//удалить первый
return beg;//вернуть начало списка
}
//если удаляется элемент из середины списка
for(int i=0;i<k-1&&p!=0;i++,p=p->next);//пройти по списку либо до
элемента с предыдущим номером, либо до конца списка
if(p==0||p->next==0)return beg;//если в списке нет элемента с номером k
point*r=p->next;//встать на удаляемый элемент
p->next=r->next;//изменить ссылку
delete r;//удалить r
r=p->next;//встать на следующий
if(r!=0)r->pred=p;//если r существует, то связать элементы
return beg;//вернуть начало списка
}
point* add_point(point *beg,int k)
{