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

Размещено на http://www.allbest.ru/

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

Хусаинов Исмагильян Гарифьянович



Аннотация

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача №1

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

Решение

#include

#include

#include

#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, отсортировать по алфавиту.

Решение

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

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){

coutp!=0){

q=g;w=g->p;

if (strcmp(q->fam,w->fam)>0) {

if(q==t){t=w;r=w;q->p=w->p;w->p=q;}

else {q->p=w->p;w->p=q;r->p=w;r=w;}

flag=0; }

else {g=g->p;r=q;}

}

}while (flag==0);

cout <<"\n Отсортированный по алфавиту список\n";

j=1;

while(t!=0){

cout



Вывод

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



Список литературы

1. Дейтел П. Дж., Дейтел Х. М. Программирование на С++: Пер. с англ. - М.: ЗАО "Издательство БИНОМ", 2000. - 1024 с.

2. Подбельский В.В. Язык программирования С++: Учебное пособие - 5 изд. - М: Финансы и статистика, 2004. - 560 c.

3. Страуструп Б. Язык программирования С++. - 3-е издание. - Пер. с англ. - СПб.; М.: "Невский Диалект" - "Издательство БИНОМ", 1999. - 991с.

4. Хафизов Р.М., Хусаинов И.Г., Шагапов В.Ш. Динамика восстановления давления в «вакуумированной» скважине // Прикладная математика и механика. 2009. Т. 73. Вып. 4. С. 615-621.

Размещено на Allbest.ru