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

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

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

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

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

Формат описания структуры:

struct [имя типа]

{

     тип1 имя_элемента1;

     тип2 имя_элемента 2;

   тип n имя_элемента n;

}[список определителей];

Элементы структуры могут иметь любой тип, кроме типа этой же структуры.

Например, опишем структуру с тремя полями:

struct student

{

     char fio[30];

     int group;

     int mark;

} s1, *s2;

Такое определение вводит новый тип данных student, который может быть использован при определении программных объектов. Например, создадим структурированный объект и массив структурированных объектов.

student s3,s4[10];

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

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

имя_структуры.имя_элемента_структуры

Например,

s1.group= 121;

s1.mark=5;

Если определен указатель на структуру, то для обращения к элементам структуры можно использовать операцию выбора компонентов структурного объекта ->

имя указателя->имя элемента структуры

Например,

student *st;

st->group= 222; //это равносильно (*st).group=222;

Инициализировать конкретную структуру можно только при описании перечислением ее элементов в скобках {} в порядке их описания, например

student s4= {“Fedorov”, 122, 4};

Для переменных одного и того же структурного типа определена операция присваивания, то есть поэлементное копирование, например s3=s1;

Часто в качестве поля структуры используют объединения. Объединение представляет собой частный случай структуры, все поля которой располагаются по одному и тому же адресу. Формат описания такой же, но используются ключевое слово union. Размер объединения равен наибольшему размеру из его полей.

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

Например,

union

{

     float a;

     unsigned int b;

}ab;

Если ввести ab.a=3.78, то затем можно рассматривать код его представления как беззнаковое целое cout<<ab.b;

Основное назначение объединения – обеспечить возможность доступа к одному и тому же участку памяти с помощью объектов разных типов.

Пример. Описать структуру СОТРУДНИК с полями ФАМИЛИЯ, ГОД_РОЖДЕНИЯ, ПОЛ. Для женщин – указывать количество детей, для мужчин – отношение к военной службе. Ввести данные о сотруднике и вывести их на экран.

# include <iostream.h>

# include <conio.h>

main ()

{

enum sextype {male, female};

enum ranktype {not,soldier,officier};

struct

{

    char fio[40];

    int year;

    sextype sex;

    union

    {

       int children;

       ranktype rang;

    };

}s1;

cout<<"Enter fio ";

cin.getline(s1.fio,40);

cout<<"Enter sex ";

cin>>int(s1.sex);

switch(s1.sex)

{

    case male: {    cout<< "Enter rank ";

                cin>>int (s1.rang);

                cout<<"\n"<<s1.fio;

                cout<< " male, rank="<<s1.rang;

                break;

                }

  case female:{cout<< "Enter number of children ";

                cin>>s1.children;

                cout<<"\n"<<s1.fio;

                cout<< " female, children ="<<s1.children;

                break;

                }

}

getch();

}

Вернемся к рассмотрению динамических структур данных. Элемент любой динамической структуры данных представляет собой структуру (в смысле struct), содержащую по крайней мере два поля: для хранения данных и для указателя на этуже структуру. Полей данных и указателей может быть несколько. Например, элемент списка целых чисел имеет вид

struct el

{

int a;

     el *b;

}

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

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

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

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

struct student

{

     char *fio;

     int mark;

     student *next;

}

Для формирования списка требуется иметь по крайней мере один указатель – на начало списка (голова списка).

student * begin=NULL;

и один вспомогательный указатель student *adr;.

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

void vvod ()

{

     int n;

     cout<< “Введите количество студентов ”;

     cin>>n;

     const int dlin=20;

     char f[dlin];                                 // вспомогательный массив для хранения

                                                       // введенной фамилии студента

for (int i=1;i<=n; i++)

{

                 if (begin==NULL)           // выделение памяти под первый элемент списка

{

begin=new (student);

adr=begin;

}

                 else                                 // выделение памяти под очередной элемент списка

{

adr->next=new(student);

adr=adr->next;

                 }

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

                 cout<< “Введите фамилию ”;

                 cin.getline(f,dlin);       

adr->fio=new (char [strlen(f)+1]);

                 strcpy(adr->fio,.f);

                 cout<< “Введите оценку ”;

                 cin>>(adr->mark);

                 adr->next=NULL;

                 }

}

В данном случае мы создали список студентов как очередь. Очередь – это частный случай списка, добавление элементов в который выполняется в один конец, а выборка – из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Очередь реализует принцип FIFO (firs in – first out, первым пришел – первым вышел). В нашем примере указатель begin указывает на начало списка, и не изменяется во время выполнения программы. Добавление элементов происходит в конец списка. Очевидно, что обработка элементов для списка, сформированного таким образом, может происходить только с первого введенного.

Другим частным случаем однонаправленного списка является стек, добавление в который и выборка из которого выполняется с одного конца. Другие операции со стеком не определены. При выборке элемент исключается из стека. Стек реализует принцип LIFO (last in – first out, последним пришел – первым вышел). Создадим список студентов как стек, постоянно передвигая указатель begin и последний созданный элемент делая головой списка.

void vvod1 ()

{

     int n;

     cout<< “Введите количество студентов ”;

     cin>>n;

     const int dlin=20;

     char f[dlin];                                         // вспомогательный массив для хранения

                                                               // введенной фамилии студента

for (int i=1;i<=n; i++)

     {

                 adr=new(student);

                 cout<< “Введите фамилию ”;

                 cin.getline(f,dlin);       

adr->fio=new (char [strlen(f)+1]);

                 strcpy(adr->fio,.f);

                 cout<< “Введите оценку ”;

                 cin>>(adr->mark);

adr->next=begin;

                 begin=adr;

     }

}

Чтобы вывести на экран элементы списка, созданного любым из предложных способов, можно использовать следующую процедуру

void vivod()

{

     adr=begin;

     while (adr!=NULL)

     {

                 cout<<"\n "<<(adr->fio)<<" "<<adr->mark;

                 adr=adr->next;

     }

}

Кроме процедур создания и вывода на экран для списка обычно определяют следующие процедуры:

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

Добавить комментарий


Защитный код
Обновить

Мобильные устройства

Технологические системы

Программирование

Реклама

Яндекс.Метрика
© 2011-2016 pc-4you.ru Копирование материалов разрешено только с указанием активной ссылки на первоисточник