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

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

В языках программирования существует и другой способ выделения памяти под данные, который называется динамическим. В этом случае память под величины отводится во время выполнения программы. Такие величины будем называть динамическими. Раздел оперативной памяти, распределяемый статически, называется статической памятью; динамически распределяемый раздел памяти называется динамической памятью (динамически распределяемой памятью).

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

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

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

Адрес величины — это номер первого байта поля памяти, в котором располагается величина. Размер поля однозначно определяется типом.

Величина ссылочного типа (указатель) описывается следующим образом:

                   имя_типа *<идентификатор>;

Вот примеры описания указателей:

int *P1;

char *P2; 

Здесь P1 — указатель на динамическую величину целого типа; P2 — указатель на динамическую величину символьного типа.

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

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

           

       идентификатор = (тип_идентификатора*) malloc (sizeof(тип_идентификатора))

Считается, что после выполнения этого оператора создана динамическая величина, имя которой имеет следующий вид:

                   <имя динамической величины> = *<указатель>

Пусть в программе, в которой имеется приведенное выше описание, присутствуют следующие операторы:

       P1 = (int*) malloc (sizeof(int));

       P2 = (char*) malloc (sizeof(char));

После их выполнения в динамической памяти оказывается выделенным место под три величины (две скалярные и один массив), которые имеют идентификаторы:

       *P1, *P2

Например, обозначение *P1 можно расшифровать так: динамическая переменная, на которую ссылается указатель P1.

Дальнейшая работа с динамическими переменными происходит точно так же, как со статическими переменными соответствующих типов. Им можно присваивать значения, их можно использовать в качестве операндов в выражениях, параметров подпрограмм и пр. Например, если переменной *P1 нужно присвоить число 25, переменной *P2 присвоить значение символа "A", то это делается так:

                   *P1 = 25;

                   *P2 = 'A';                  

Кроме процедуры malloc значение указателя может определяться оператором присваивания:

                              <указатель> = <ссылочное выражение>;

В качестве ссылочного выражения можно использовать

* указатель;

* ссылочную функцию (т.е. функцию, значением которой является указатель);

* константу NULL.

NULL — это зарезервированная константа, обозначающая пустую ссылку, т.е. ссылку, которая ни на что не указывает. При присваивании базовые типы указателя и ссылочного выражения должны быть одинаковы. Константу NULL можно присваивать указателю с любым базовым типом.

До присваивания значения ссылочной переменной (с помощью оператора присваивания или функции malloc) она является неопределенной.

Рассмотрим пример. Пусть в программе описаны следующие указатели:

                   int *D, *P;                 

Тогда допустимыми являются операторы присваивания

                   D = P; K = NULL;

поскольку соблюдается принцип соответствия типов. Оператор K = D ошибочен, т.к. базовые типы у правой и левой части разные.

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

Представьте себе, что в программе, в которой присутствуют описанные выше указатели, в разделе операторов записано следующее:

D = (int*) malloc (sizeof(int));

P = (int*) malloc (sizeof(int)); 

{Выделено место в динамической памяти под две целые переменные.

 Указатели получили соответствующие значения}

*D = 3; *P = 5;

{Динамическим переменным присвоены значения}

P = D;

{Указатели P и D стали ссылаться на одну и ту же величину, равную 3}

cout << *P << *D; {Дважды напечатается число 3}

Таким образом, динамическая величина, равная 5, потеряла свой указатель и стала недоступной. Однако место в памяти она занимает. Это и есть пример возникновения "мусора". На схеме показано, что произошло в результате выполнения оператора P = D.

В Паскале имеется стандартная процедура, позволяющая освобождать память от данных, потребность в которых отпала. Ее формат:

                   free(<указатель>);

Например, если динамическая переменная *P больше не нужна, то оператор

                   free(P);

удалит ее из памяти. После этого значение указателя P становится неопределенным. Особенно существенным становится эффект экономии памяти при удалении больших массивов.

В версиях Турбо-C++, работающих под операционной системой MS DOS, под данные одной программы выделяется 64 килобайта памяти (или, если быть точнее, 65520 байт). Это и есть статическая область памяти. При необходимости работать с большими массивами информации этого может оказаться мало. Размер динамической памяти — много больше (сотни килобайт). Поэтому использование динамической памяти позволяет существенно увеличить объем обрабатываемой информации.

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

Лекция 21

Тема 28. Списки

Цель лекции: изучить понятия, классификацию и объявление списков, особенности доступа к данным и работу с памятью при использовании однонаправленных и двунаправленных списков, научиться решать задачи с использованием списков на языке C++.

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

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

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

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

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

* однонаправленные (односвязные) списки;

* двунаправленные (двусвязные) списки;

* циклические (кольцевые) списки.

В основном они отличаются видом взаимосвязи элементов и/или допустимыми операциями.

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

Наиболее простой динамической структурой является однонаправленный список, элементами которого служат объекты структурного типа.

Однонаправленный (односвязный) список – это структура данных, представляющая собой последовательность элементов, в каждом из которых хранится значение и указатель на следующий элемент списка (рис. 29.1). В последнем элементе указатель на следующий элемент равен NULL.

Описание простейшего элемента такого списка выглядит следующим образом:

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

где информационное поле – это поле любого, ранее объявленного или стандартного, типа;

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

Например:

struct Node {

        int key;//информационное поле

        Node*next;//адресное поле

       };

 

Информационных полей может быть несколько.

Например:

struct point {

         char*name;//информационное поле

         int age;//информационное поле

         point*next;//адресное поле

        };

 

Каждый элемент списка содержит ключ, который идентифицирует этот элемент. Ключ обычно бывает либо целым числом, либо строкой.

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

* создание списка;

* печать (просмотр) списка;

* вставка элемента в список;

* удаление элемента из списка;

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

* проверка пустоты списка;

* удаление списка.

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

Рассмотрим подробнее каждую из приведенных операций.

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

struct Single_List {//структура данных

               int Data; //информационное поле

               Single_List *Next; //адресное поле

              };

..........

Single_List *Head; //указатель на первый элемент списка

..........

Single_List *Current;

//указатель на текущий элемент списка (при необходимости)

Создание однонаправленного списка

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

//создание однонаправленного списка (добавления в конец)

void Make_Single_List(int n,Single_List** Head){

if (n > 0) {

(*Head) = new Single_List();

//выделяем память под новый элемент

cout << "Введите значение ";

cin >> (*Head)->Data;

//вводим значение информационного поля

(*Head)->Next=NULL;//обнуление адресного поля

Make_Single_List(n-1,&((*Head)->Next));

}

}

Печать (просмотр) однонаправленного списка

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

//печать однонаправленного списка

void Print_Single_List(Single_List* Head) {

if (Head!= NULL) {

cout << Head->Data << "\t";

Print_Single_List(Head->Next);

//переход к следующему элементу

}

else cout << "\n";

}

Лекция 22

Тема 29. Рекурсия

екурсия — это такой способ организации вспомогательного алгоритма (подпрограммы), при котором эта подпрограмма (процедура или функция) в ходе выполнения ее операторов обращается сама к себе. Вообще, рекурсивным называется любой объект, который частично определяется через себя.

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

       <двоичный код>::= <двоичная цифра> | <двоичный код><двоичная цифра>

       <двоичная цифра>::= 0 | 1

Здесь для описания понятия были использованы, так называемые, металингвистический формулы Бэкуса-Наура (язык БНФ); знак "::=" обозначает "по определению есть", знак "|" — "или".

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

Приведём другие примеры рекурсивных определений.

Пример 1. Классический пример, без которого не обходятся ни в одном рассказе о рекурсии, — определение факториала. С одной стороны, факториал определяется так: n!=1*2*3*...*n. С другой стороны,

Факториал, рекурсивное определение

Граничным условием в данном случае является n<=1.

Пример 2. Определим функцию K(n), которая возвращает количество цифр в заданном натуральном числе n:

Количество цифр в натуральном числе, рекурсивное определение

Задание. По аналогии определите функцию S(n), вычисляющую сумму цифр заданного натурального числа.

Пример 3. Функция C(m, n), где 0 <= m <= n, для вычисления биномиального коэффициента по следующей формуле является рекурсивной.

Ниже будут приведены программные реализации всех этих (и не только) примеров.

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

Порождение все новых копий рекурсивной подпрограммы до выхода на граничное условие называется рекурсивным спуском. Максимальное количество копий рекурсивной подпрограммы, которое одновременно может находиться в памяти компьютера, называется глубиной рекурсии. Завершение работы рекурсивных подпрограмм, вплоть до самой первой, инициировавшей рекурсивные вызовы, называется рекурсивным подъёмом.

 

Выполнение действий в рекурсивной подпрограмме может быть организовано одним из вариантов:

 

{           {             {

P;          операторы;      операторы;

операторы;   P;           P;

}           }              операторы;

                                  }

 

рекурсивный подъём     рекурсивный спуск и рекурсивный спуск,

                                   и рекурсивный подъём

 

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

Реализуем приведённые выше рекурсивные определения в виде функций.

 

Пример 1.

 

double Factorial(int N)

{

double F;

if (N<=1) F=1.; else F=Factorial(N-1)*N;

return F;

}

 

Пример 2.

 

int K(int N)

{

int Kol;

if (N<10) Kol=1; else Kol=K(N/10)+1;

return Kol;

}

 

Пример 3.

 

int C(int m, int n)

{

int f;

if (m==0||m==n) f=1; else f=C(m, n-1)+C(m-1, n-1);

return f;

}

 

Пример 4. Вычислить сумму элементов линейного массива.

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

 

        #include <stdio.h>

        #include <conio.h>

        #include <stdlib.h>

        #include <time.h>

 

        int summa(int N, int a[100]);

        int i,n, a[100];

 

        void main()

        {

       clrscr();

       printf("\nКоличество элементов массива? "); scanf("%d", &n);

       printf("\nВ сформированном массиве %d чисел:\n", n);

       randomize();

       for (i=0; i<n; i++)

       {a[i]= -10+random(21); printf("%d ", a[i]);}

       printf("Сумма: %d", summa(n-1, a));

        }

        int summa(int N, int a[100])

        {

       if (N==0) return a[0]; else return a[N]+summa(N-1, a);

        }

 

Пример 5. Определить, является ли заданная строка палиндромом, т.е. читается одинаково слева направо и справа налево.

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

 

        #include <stdio.h>

        #include <conio.h>

        #include <string.h>

           

       char s[100];

       int pal(char s[100]);

           

       void main()

       { clrscr();

       printf("\nВведите строку: "); gets(s);

       if (pal(s)) printf("Строка является палиндромом");

       else printf("Строка не является палиндромом");

       }

       int pal(char s[100])

       { int l; char s1[100];

       if (strlen(s)<=1) return 1;

       else {l=s[0]==s[strlen(s)-1];

          strncpy(s1, s+1, strlen(s)-2);

          s1[strlen(s)-2]='\0';

          return l&&pal(s1);}

       }

 

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

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