Лекция 8. Динамическая организация данных¶

Динамическое распределение памяти¶

• Происходит во время выполнения программы (run-time)
• Объем ограничивается размером виртуальной памяти ЭВМ
• Размер может переопределяться
• Выделение и освобождение может происходить в любом месте программы

• Объявить указатель на желаемый тип
• Запросить блок желаемого размера
• Проверить результат запроса
• Использовать
• Освободить

Функции для работы с ДП¶

Пример использования malloc¶

int  *arr1=(int *)malloc(N*sizeof(int));
char *arr2=(char*)malloc(M*sizeof(char));
if(!arr1 || !arr2)
{
   puts("Memory allocation error!");
   exit(1);
}
..
free(arr1);
free(arr2);

Пример использования сalloc¶

int  *arr1=(int *)calloc(N,sizeof(int));
char *arr2=(char*)calloc(M,sizeof(char));
if(!arr1 || !arr2)
{
   puts("Memory allocation error!");
   exit(1);
}
..
free(arr1);
free(arr2);

Пример с чтением файла¶

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

FILE *fp=fopen(argv[1],"rt");
if(!fp) { puts("File error!");    exit(1); }
long len=0;
fseek(fp,0L,SEEK_END);
len=ftell(fp);
char *buf=(char*)malloc(len*sizeof(char));
if(!buf) { puts("Memory error!");    exit(2); }
fseek(fp,0L,SEEK_SET);
fread(buf,sizeof(char),len,fp);
..
fclose(fp);
free(buf);

Многомерные массивы¶

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

float **arr=(float**)malloc(N*sizeof(float*));
for(i=0;i<N;i++)
  arr[i]=(float*)malloc(M*sizeof(float));

Уничтожение массива происходит в обратном порядке:

for(i=0;i<N;i++)
  free(arr[i]);
free(arr);

Ошибки, связанные с памятью¶

По различным данным, до 90% всех сбоев в программах на С/С++ возникает в связи с неправильным обращением к памяти. При работе с ДП возможны следующие виды ошибок:

• Утечки памяти (memory leaks)
• Ошибочные запросы на выделение
• Повторное освобождение
• Выход за границы выделенной памяти

Пример с двойным освобождением¶

void fun(int *p)
{
  ...
  free(p);
}

int main()
{
   int *arr=(int*)malloc(N*sizeof(int));
   ...
   fun(arr);
   free(arr); // Ошибка!
   ...
}

Пример с утечкой памяти¶

void alloc(int * arr, int N)
{
   arr=(int*)calloc(N,sizeof(int));
}
int main()
{
   int *arr=NULL;
   alloc(arr);
   ...
   free(arr); // error!
   ...
}

float **arr=(float**)malloc(N*sizeof(float*));
for(i=0;i<N;i++)
  arr[i]=(float*)malloc(M*sizeof(float));
...
free(arr);

Пример пожирателя памяти¶

Данная программа безостановочно ‘’пожирает’’ динамическую память, вызывая проблемы в ОС.

int main()
{
   while(1)
   {
      double *ptr;
      ptr=(double*)malloc(10000*sizeof(double));
   }
   return 0;
}

Достоинства и недостатки массивов¶

Достоинства массива:

• простота организации,
• высокая скорость доступа к элементам ( \(O(1)\) ).

Недостатки:

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

Недостатки массивов¶

Для вставки элемента в массив необходимо произвести поэлементное копирование с целью освобождения позиции для вставки. Чем далее позиция от конца массива, тем больше операций копирования

Понятие связанного списка¶

Связанный список является альтернативой массиву для хранения набора однотипных данных.

Классификация списков¶

Существует несколько разновидностей связанных списков:

1. Односвязные - связь только от предшествующего к последующему.
2. Двусвязные - связь в обоих направлениях.
3. Кольцевые - от последнего элемента мы вновь переходим к первому.

Терминология списков¶

1. List - список.
2. Item - элемент списка.
3. Head - головной (первый) элемент списка.
4. Tail - хвостовой (последний) элемент списка.
5. Link - cвязь.
6. Next - указатель на следующий элемент.
7. Prev - указатель на предыдущий элемент.
8. NULL - маркер нулевого адреса.

Достоинства и недостатки списков¶

Связные списки устраняют недостатки массива, при этом сложность алгоритма нахождения заданного элемента равна \(O(n)\) . Платой за эффективность использования памяти является наличие дополнительных процедур по построению и поддержанию целостности списка. Особенностью списка по сравнению с массивами является хранение адресов связанных элементов в каждом элементе.

Пример:

На платформе Win32, односвязный список, состоящий из 1000 элементов будет дополнительно расходовать 4000 Байт памяти, независимо от размера хранимых данных.

Методы программной реализации списков¶

Для описания элемента списка (item) в С и C++ используется понятие структуры, которая описывается ключевым словом tetxbf{struct}.

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

1. служебная информация помещается в одну структуру вместе с полезными данными;
2. служебная информация выносится в отдельную структуру.

Рассмотрим пример организации элемента списка для хранения информации о событии

typedef unsigned char UC;
typedef unsigned short US;
struct EVENT
{
   UC day;        // день месяца
   char mon[10];  // месяц
   US year;       // год
   char buf[256]; // описание события
   struct EVENT *next;   // следующее событие
};

Обращаем внимание на то, что служебное поле next содержится в одной структуре с информационными полями.

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

Второй метод реализации немного сложнее, зато отличается большей гибкостью

struct EVENT
{
   UC day;        // день месяца
   char mon[10];  // месяц
   US year;       // год
   char buf[256]; // описание события
};

struct ITEM
{
   struct EVENT *event; // адрес записи
   struct ITEM  *next;  // следующий элемент
};

Схема списка при раздельной реализации

Набор операций¶

Для работы со списком необходимо определить набор операций (API - Application Programming Interface)

• create() - создание списка,
• access() - получение доступа к i-ому элементу в списке,
• add() - добавление нового элемента в список,
• remove() - удаление элемента из списка,
• count() - подсчет числа элементов в списке,
• save() - сохранение списка в файле,
• load() - чтение списка из файла,
• search() - поиск элемента по значению поля,
• union() - объединение двух списков в один,
• swap() - перестановка двух элементов списка,
• sort() - сортировка элементов по некоторому полю,
• copy() - создание копии списка

Функция create¶

Функция create создает новый список с одним элементом.

struct ITEM *create(struct EVENT *event)
{
   struct ITEM *head=(struct ITEM*)malloc(sizeof(struct ITEM));
   head->event=event;
   head->next=NULL;
   return head;
}

Функция add - добавление элемента¶

Добавление элемента в существующий список

void add(struct ITEM *head, struct EVENT *event)
{
   while(head->next)
      head=head->next;
   head->next=(struct ITEM*)malloc(sizeof(struct ITEM));
   head->next->event=event;
   head->next->next=NULL;
}

Функция определяет хвостовой элемент (по значению NULL в поле next, затем создаёт новый элемент и включает его в список, делая хвостовым.

Функция remove - удаление элемента¶

Удаление элемента из списка, находящегося на позиции i

struct ITEM* remove(struct ITEM *head,int i)
{
   struct ITEM *newhead=head,*temp;
   // удаляем первый элемент, head меняется
   if(i==0) {
      newhead=head->next; // второй делается первым
   }
   else {
      while(head->next) {
        if(--i==0)
          break; // обнаружили удаляемый элемент
        head=head->next;
      }
      if(i>0)
        return newhead; // удаляемого элемента не существует
      else if(head->next) { // удаляем элемент из середины
        temp=head->next; // удаляемый элемент
        head->next=head->next->next;
        free(temp); // освобождаем память
      }
   }
   return newhead;
}

Функция print - печать элемента¶

Для того, чтобы распечатать заданный элемент, нам необходимо найти его в списке

void printItem(struct ITEM *head,struct ITEM *item)
{
   while(head)
   {
      if(head==item) {
         printEvent(head->event);
         return;
      }
      head=head->next;
   }
}

Бинарные деревья¶

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

У каждого узла бинарного дерева может быть 0,1 или 2 потомка. По отношению к левому узлу применяется термин левый потомок, по отношению к узлу справа - правый потомок. Бинарное дерево является рекурсивной структурой. Каждый узел является корнем своего собственного поддерева.

На любом уровне \(N\) бинарное дерево может содержать от \(1\) до \(2^N\) узлов. Вырожденным будет называться такое дерево, у которого один лист и каждый узел имеет одного сына. Вырожденное бинарное дерево эквивалентно связанному списку.

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

Полное дерево глубины 2:

Вырожденное дерево с теми же элементами:

Операции¶

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

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

При прохождении дерева используется рекурсия, поскольку каждый узел является корнем своего поддерева. Каждый алгоритм выполняет в узле три действия: заходит в узел, рекурсивно спускается по левому и по правому поддереву. Спуск прекращается при достижении пустого поддерева (нулевой указатель).

Обход бинарного дерева¶

Порядок действий при прямом обходе:

1. Обработка данных узла.
2. Прохождение левого поддерева.
3. Прохождение правого поддерева.

Порядок действий при обратном обходе:

1. Прохождение левого поддерева.
2. Прохождение правого поддерева.
3. Обработка данных узла.

Порядок действий при симметричном обходе:

1. Прохождение левого поддерева.
2. Обработка данных узла.
3. Прохождение правого поддерева.

Последовательность обработки узлов:

• прямой обход: ABDECFG
• симметричный обход: DBEAFCG
• обратный обход: DEBFGCA

Упорядоченные данные¶

При создании дерева часто используется свойство упорядоченности.

Свойство упорядоченности. Пусть \(x\) - произвольная вершина бинарного дерева. Если вершина \(y\) находится в левом поддереве вершины \(x\) , то

\(y \to data \le x \to data\) . Если вершина \(y\) находится в правом поддереве вершины \(x\) , то \(y \to data \geq x \to data\) .

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

Основные операции¶

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

1. AddTree() - создание узла дерева и помещение в него данных,
2. PrintTree() - печать дерева с данными в узлах,
3. GoTree() - обход дерева (для обработки данных),

Создание дерева¶

Функция принимает два параметра - указатель на узел и код символа. Если указатель нулевой (находимся в листе дерева) выделяем память под узел и присваиваем указателям на потомков нулевые значения, а код символа и счетчик (равен 1) присваиваем информационным полям.

Если значение кода символа совпадает с данными в текущем узле увеличиваем значение счетчика на 1 и возвращаемся к родителю, если код меньше текущего, переходим к левому потомку (или к пустому указателю), а если код больше, то к правому.

В результате мы получим дерево, в котором каждому прочитанному из файла символу будет соответствовать свой узел, а поле count будет хранить число совпавших символов.

struct TNODE *AddTree(struct TNODE *node,char symbol)
{
   if(node==NULL)
   {
     node=(struct TNODE*)malloc(sizeof(struct TNODE));
     node->symbol=symbol;
     node->count=1;
     node->left=NULL;
     node->right=NULL;
   }
   else if(symbol==node->symbol)
     node->count++;
   else if(symbol<node->symbol)
    node->left=AddTree(node->left,symbol);
   else
    node->right=AddTree(node->right,symbol);
   return node;
}

Пример: для строки tkrpaptzs дерево примет следующий вид

Обход дерева¶

Симметричный обход дерева

void GoTree(struct TNODE *node)
{
   if(node) {
     GoTree(node->left);
     printf("%c\n",node->symbol);
     GoTree(node->right);
   }
}

Симметричный обход позволяет вывести символы в порядке возрастания значений.