« Структуры данных и алгоритмы. Теория. Рекурсия. Структуры данных и алгоритмы. Теория. Общие правила и рекомендации к разработке собственных контейнерных структур данных »

Структуры данных и алгоритмы. Теория. Динамические структуры данных

January 5, 2007

Мы уже знакомы с такими типами данных как скалярные типы (целые, вещественные числа, логические величины), массивы, записи (структуры). У всех этих типов есть общая черта – когда мы создаем переменную заданного типа, мы жестко ограничиваем ее структуру и набор допустимых значений. Так объявив массив размерностью 10 элементов в большинстве языков программирования не возможно увеличить или уменьшить его размер. В таком случае мы говорим, что тип определяется на этапе разработки программы или является статическим. В противоположность статическим типам существуют динамические типы данных. Для них характерно изменение на этапе выполнения не только отдельных значений, которые они принимают, но и структуры. Динамические типы данных наиболее часто являются по своей природе рекурсивными, т.е. динамический тип данных «X» состоит из набора компонент, некоторые из которых имеют тип «X». Вспомните, что с помощью рекурсии мы могли описать конечным набором выражений бесконечное множество объектов. Так в математике определение натурального числа основывается на положении:
  • 0 – есть натуральное число;
  • всякое число, следующее за натуральным является натуральным.

При построении рекурсивных алгоритмов, важное значение имело понятие терминальной ветви вычисления. Также и для рекурсивных типов данных необходим инструмент, который ограничивал их размер. В качестве простейших примеров, когда является необходимым использовать динамические типы данных можно привести задачу создания класса DynamicVector, который будет служить для хранения некоторого множества чисел. Вы уже обладаете необходимыми знаниями, для того чтобы написать следующий фрагмент кода: 
  1. class DynamicVector {
  2. protected:
  3.   int * data;
  4.   int count;
  5. public:
  6.   DynamicVector (int s) : data (new int [s] ) , count (s) {}
  7.   ~DynamicVector () {delete [] data;}
  8.   int & operator [] (int idx) {
  9.      assert (idx >=0 && idx < count);
  10.      return data [idx];
  11.   }
  12. };
Здесь мы создали класс массива, при создании экземпляра данного класса необходимо указать его размер – максимальное количество элементов которые будут в нем храниться. Разумеется, что в реальных приложениях подобные ситуации, когда количество обрабатываемых данных постоянно и не изменяется во время исполнения приложения, крайне редки. На практике массив часто не будет использоваться и на половину, а может быть заранее захваченного размера будет не достаточно. Единственное решение это выделять память более гибко, когда наличного объема массива будет не хватать, то его увеличивать, а когда, соответственно, размер будет слишком велик и память будет простаивать, то часть ее можно освободить. Разумеется, что подобная практика более сложна, чем в ранее приведенном примере и, уж тем более сложнее, чем просто объявить “int arr [100]”, но наши программы, прежде всего, должны быть эффективными.

Еще одним примером необходимости использования динамических структур данных будет задача анализа математических выражений (для упрощения будем рассматривать только бинарные операции). Действительно любое математическое выражение может быть представлено как “X op Y”, где X,Y – это скаляры или математические выражения, а “op” – операция над ними. Общепринято при повторяющихся вычислениях по формуле с изменениями значения переменных входящих в нее, для оптимизации по скорости выполнять только один раз анализ строки и затем размещать полученное выражение в некоторой специализированной структуре данных.

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

Итак, как я сказал ранее, структура динамического типа данных не фиксирована и определяется на этапе выполнения программы, следовательно, не возможно заранее выделить для хранения переменной фиксированного участка памяти. Выделение памяти должно проходить на этапе выполнения программы. Все языки программирования имеют средства для выполнения операции выделения и освобождения не нужной памяти.
Язык Выделение памяти Освобождение памяти Обозначение пустой ссылки
Pascal New Dispose NIL
C Malloc Free NULL
C++ New Delete NULL
Java New Автоматически null
Перед тем как мы начнем детальное рассмотрение динамических структур данных, вспомните, что вы знаете об архитектуре памяти компьютера. В общем случае для приложения доступны два вида памяти: стековая память, ее выделяется ограниченный размер и количество не может изменяться в ходе работы программы без специальных приемов. В данном виде памяти выделяется место для хранения локальных переменных, размещения параметров вызова функций и хранения точек возврата. Размер стека не слишком велик и для хранения больших массивов данных он не предназначен, попробуйте, например, проверить следующий фрагмент кода: 
  1. void main (void){
  2.  int arr [1000000];
  3. }
Ваше приложение должно завершиться с сообщением об ошибке. В подобной ситуации следует выделять память динамически, запрашивая ее по мере необходимости у операционной системы и освобождая тогда, когда она более не нужна. 
  1. void main (void){
  2.   int * arr = new int [1000000];
  3.   // some code … некоторые действия с данным большим массивом
  4.   delete [] arr;
  5. }


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

Списки



Наиболее простым типом контейнера является список. Так, как количество элементов списка заранее не известно, то список определяется по следующему рекурсивному правилу:
  • NULL – список (пустой список);
  • A = (x, B) – список, в данном случае “x” – элемент списка, “B” – список.



Рассмотрим пример объявления узла списка и заполнения его элементами 1..n. 
  1. struct LNode {
  2.      int inf;
  3.      LNode * next;
  4. };
Обратите внимание на определение структуры узла списка. Узел содержит информационную компоненту “inf”, следует отметить, что не существует никаких ограничений на ее тип (даже возможно это будет ссылка на иную динамическую структуру отличную от создаваемого нами списка) и ссылки на следующий элемент списка. В том случае, когда некоторый элемент “X” является последним, то значение “X->next” будет равно пустой ссылке (NULL).

Схема наполнения элементами списка приводится ниже. 
  1. LNode *begin = NULL
  2. for (int i=0; i < 100; i++){
  3.    LNode *n = new LNode;
  4.    n->inf = i;
  5.    n->next = begin;
  6.    begin = n;
  7. }
Созданный список содержит элементы в порядке обратном тому как элементы поступали на вход алгоритму добавления нового элемента в список (99, 98, 97 .., 0). Если же необходимо добавлять элементы в прямом порядке необходимо иметь ссылку на последний элемент. 
  1. last->next = n;
  2. n->next = NULL;
  3. n->inf = i;
Задача усложняется необходимость постоянного вычисления последнего элемента. Можно найти выход из ситуации, создав еще одну переменную и хранить в ней ссылку на последний добавленный элемент. 
  1. Node * last = NULL;
  2. Node * first = NULL; // ссылка на начало нашего списка
  3.  
  4. // некоторый объем кода в котором last начинает ссылаться не некоторый
  5. //элемент – последний в нашем списке
  6. last->next = n;
  7. n->next = NULL;
  8. n->inf = i;
  9. last = n;
Следует отметить, что часто задача добавления нового элемента не тривиальна и оформляется в виде отдельной процедуры (функции). 
  1. void addElement (int inf , LNode ** begin){
  2.    LNode * n = new LNode;
  3.    n->inf = inf;
  4.    n->next = *begin;
  5.    *begin = n;
  6. }
  7.  
  8. // добавление
  9.  
  10. LNode *begin = NULL;
  11. for (int i=0; i < 100; i++)
  12.    addElement (i , &begin);
Однако давайте сначала рассмотрим вопрос просмотра созданного списка. Задача просмотра легко формулируется в терминах рекурсии: что означает распечатать список:
  • если список пуст, то ничего не надо делать (конец работы алгоритма);
  • если список не пуст, то сначала необходимо будет распечатать первый элемент, а затем остаток списка (так же являющийся списком).

Очевидно, что данный алгоритм также может быть легко представлен в виде простейшей итерации. 
  1. LNode *p = begin;
  2. while (p){
  3.    printf  ("%5d" ,p->inf);
  4.    p =p->next;
  5. }
Не стоит забывать, что при завершении работы программы необходимо освобождать выделенную память, данная задача практически идентична ранее рассмотренной задаче печати элементов списка, только вместо “printf” необходимо воспользоваться “delete”. 
  1. LNode *p = begin;
  2. while (p){
  3.    LNode *temp = p->next;
  4.    delete p;
  5.    p = temp;
  6. }
После того как мы рассмотрели простейшие операции формирования, удаления и печати списка сосредоточимся на операциях вставки новых элементов в позицию отличную от начала и конца списка (в его середину). При выполнении операции вставки нового элемента необходимо определиться относительно механизма указания позиции. В простейшем случае можно создать процедуру вставки, получающую в качестве параметров указатель на элемент после которого необходимо будет добавить новый элемент. Часто бывает целесообразно каждому элементу списка поставить в соответствие уникальный ключ для выполнения сортировки по этому ключу и соответственно ускорению операции поиска позиции для вставки нового элемента. В приведенном ниже примере демонстрируется первый прием. 
  1. void insertElementAfterCurrent (LNode **cur , int inf){
  2.     LNode * n = new LNode;
  3.     n->inf = inf;
  4.     n->next = (*cur)->next;
  5.     (*cur)->next = n;
  6. }


Операция вставки элемента до текущего не столь проста. Необходимо найти элемент, который ссылается на текущий.

Ниже приводятся два способа решения этой задачи: 
  1. void insertElementBeforeCurrent (LNode **begin , int inf , LNode *cur){
  2.     LNode  *n = new LNode;
  3.     n->inf = inf;
  4.     n->next = cur;
  5.     LNode * p = *begin;
  6.     while (p && p->next != cur)
  7.         p=p->next;
  8.     if (cur == *begin){ // элемент перед которым необходимо сделать вставку это первый элемент
  9.        *begin = n;
  10.     }
  11.     else
  12.        if (!p) {
  13. 	    perror ("Error: element cannot be found");
  14.   	    abort ();
  15.        }
  16.        else
  17. 	    p->next = n;
  18. }
  19.  
  20. // схема использования функции
  21. insertElementBeforeCurrent (&begin , -2 , begin);
  22. insertElementBeforeCurrent (&begin , -3 , new LNode);
  1. void psevdoInsertElementBeforeCurrent (LNode *cur , int inf){
  2.    LNode * n = new LNode ;
  3.    n->inf = cur->inf;
  4.    cur->inf = inf;
  5.    n->next = cur->next;
  6.    cur->next = n;
  7. }
Стоит сказать, что второй фрагмент кода является на самом деле “обманом пользователя”. В действительности новый элемент вставляется не перед “текущим”, а после его, а затем происходит перемена значений информационной компоненты нового и текущего элемента. В том случае, когда такая перемена тривиальна и не приводит к повышению стоимости алгоритма, подобный прием имеет право на жизнь. Ведь в нем в отличие от предыдущего фрагмента не выполняется поиск предшествующего элемента. Также возможен и третий вариант реализации добавления нового элемента перед текущим. 
  1. void AnotherWayInsertElementBeforeCurrent (LNode **cur , int inf){
  2.     LNode * n = new LNode ;
  3.     n->inf = inf;
  4.     n->next = *cur;
  5.     *cur = n;
  6. }
При динамическом формировании списков всегда следует быть очень осторожными т.к. существует опасность для ссылок, которые мы используем в своей программе «потерять актуальность». Например, в приведенном ниже фрагменте кода при выводе элементов мы теряем первый из них (-33). Потеря актуальности также происходит и при использовании функции “AnotherWayInsertElementBeforeCurrent” и даже при применении “псевдовставки” (правда в этом случае теряет актуальность не ссылка, а сама информация). Отсюда следует сделать вывод, что при использовании динамических структур данных крайне не желательно давать доступ к ее произвольным фрагментам. Лучше всего скрыть реализацию от внешнего доступа, создав класс с закрытыми полями и интерфейсом, содержащим набор операций “append, insert, remove” и другие соответствующие конкретной предметной области методы. 
  1. LNode *begin = NULL;
  2.  
  3. for (int i=0; i < 10; i++){
  4.    LNode *n = new LNode;
  5.    n->inf = i;
  6.    n->next = begin;
  7.    begin = n;
  8. }
  9.  
  10. LNode *b = begin;
  11. insertElementBeforeCurrent (&begin , -33 , begin);
  12.  
  13. LNode *p = b;
  14. while (p){
  15.    printf  ("%5d" ,p->inf);
  16.    LNode *temp = p->next;
  17.    delete p;
  18.    p = temp;
  19. }


Далее рассмотрим операцию удаления элементов списка. Также как и при добавлении элементов существуют отличия в реализации в зависимости от того, как будет выполняться удаление: до или после текущего элемента или же удаляется сам текущий элемент. 
  1. void deleteElementAfterCurrent (LNode *cur){
  2.    LNode * tmp = cur->next;
  3.    if  (!tmp) // нет элемента для удаления
  4.    {
  5.        perror ("Error: no element for remove");
  6.        abort ();
  7.    }
  8.    cur->next = cur->next->next;
  9.    delete tmp;
  10. }
В случае необходимости удалить текущий элемент алгоритм заметно усложняется. Для удаления элемента нам необходимо будет найти предшествующий ему элемент. Операция поиска похожа на ту, которую мы использовали при вставке элемента перед текущим. 
  1. void deleteCurrentElement (LNode **begin , LNode *cur){
  2.    if (*begin == cur){
  3.       LNode *n = *begin;
  4.       *begin = (*begin)->next;
  5.       delete n;
  6.       return;
  7.    }
  8.    LNode * p = *begin;
  9.    while (p && p->next != cur)
  10.       p = p->next;
  11.       if (! p ){
  12.          perror ("Error: no element for remove");
  13.          abort ();
  14.       }
  15.       deleteElementAfterCurrent (p);
  16. }


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

Стек



Стек представляет собой линейный список с дисциплиной обслуживания LIFO (Last In First Out) или же FILO (First In Last Out). Это означает, что элемент, который был помещен в стек самым первым, будет извлечен из него самым последним. Для работы со стеком реализуют две функции, традиционно сложились их названия: pop – служит для извлечения элементов из списка, push – для добавления. Схему работы стека можно понять с помощью следующей таблицы:
Операция Состояние стека
Первоначальное состояние (ПУСТО)
Push(A) (A)
Push(B) (BA)
Push(C) (CBA)
POP = C (BA)
POP = B POP = B
Push(E) (EA)
В отдельных ситуациях разработчиков в стеке интересует не возможность динамически изменять свой размер, а именно дисциплина обслуживания и скорость работы. В подобных случаях можно увидеть замену или имитацию стека с помощью массива. 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3.  
  4. #define MAX_STACK_SIZE 100 
  5.  
  6. class PsevdoStack {
  7. protected:
  8. 	int size;
  9. 	int arr [MAX_STACK_SIZE];
  10. public:
  11. 	PsevdoStack () : size (0){}
  12. 	void push (int a){
  13. 		if (size >= MAX_STACK_SIZE){
  14. 			perror ("Stack Is Filled");
  15. 			abort ();
  16. 		}
  17. 		arr [size++] =a;
  18. 	}
  19.  
  20. 	int pop (){
  21. 		if (size <= 0){
  22. 			perror ("Stack Is Empty");
  23. 			abort ();
  24. 		}
  25. 		return arr[--size];
  26. 	}
  27. 	bool isEmpty (){
  28. 		return size == 0;
  29. 	}
  30. };
  31.  
  32. void main (void){
  33. 	PsevdoStack ps;
  34. 	for (int i=0; i < 10; i++)
  35. 		ps.push (i);
  36. 	while (! ps.isEmpty ())
  37. 		printf ("%5d" , ps.pop ());
  38. }
Ценой простоты работы и увеличения скорости является негибкость данной реализации: часто в программе заранее не известен размер данных, которые должны храниться в стеке. Далее мы рассмотрим пример “настоящего” динамического стека. 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3.  
  4. struct StackNode {
  5. 	int inf;
  6. 	StackNode * next;
  7. };
  8.  
  9. void push (StackNode ** root , int inf){
  10. 	StackNode *n = new StackNode ;
  11. 	n->inf = inf;
  12. 	n->next = *root;
  13. 	*root = n;
  14. }
  15.  
  16.  
  17. int pop (StackNode ** root){
  18. 	if (root == NULL){
  19. 		perror ("Error: stack is empty");
  20. 		abort ();
  21. 	}
  22. 	int itmp = (*root)->inf;
  23. 	StackNode * n = (*root)->next;
  24. 	delete *root;
  25. 	*root = n;
  26. 	return itmp;
  27. }
  28.  
  29. void main (void){
  30. 	StackNode * root = NULL;
  31. 	for (int i=0; i < 10; i++)
  32. 		push (&root , i);
  33. 	while (root)
  34. 		printf ("%5d" , pop(&root));
  35. }
Структура данных типа стека применяется при решении задач на упорядочение последовательности объектов. Например, в железнодорожной практике существует необходимость сортировать вагоны состава, разделяя на группы по общему признаку (например, груз), для этого используют тупик, схема работы которого LIFO.



Пример: Еще одним примером стека кроме железнодорожного тупика можно назвать метод, применяемый в браузерах для хранения истории посещения страничек в сети интернет: когда пользователь вводит новый адрес, он помещается в стек. Таким образом, при нажатии на кнопку “НАЗАД” последний положенный элемент извлекается и пользователь возвращается на предшествовавшую текущей страницу.

При создании стека, который будет интенсивно использоваться: т.е. будет большое количество операций добавления и удаления элементов, что приводит к фрагментации памяти и большим накладным расходам на выделение и освобождение ресурсов, то имеет смысл создать пул памяти который будет выделяться в начале работы программы (и возможно будет расти по мере необходимости) и именно внутри этого пула будут размещаться элементы стека. Пример кода реализующий данную функциональность приводится ниже: 
  1. #include <iostream>
  2.  
  3. #include <assert.h>
  4.  
  5. template <class T>
  6. class MySuperStack {
  7.     T * heap;
  8.     int s;
  9.     int a;
  10.     int p;
  11.  
  12. public:
  13.     MySuperStack (int s1, int a1) : 
  14.         heap( (T *) malloc (s1*sizeof(T)) ), s(s1), a(a1), p(0) {}
  15.  
  16.         void push(T tt);
  17.         T pop(void);
  18.         ~MySuperStack() {
  19.             free(heap);
  20.             printf ("\nMemory was Free\n");
  21.         }
  22. };
  23.  
  24. template <class T> void MySuperStack<T>::push (T tt){
  25.     if(p==s){
  26.         s+=a;
  27. 	heap=(T*)realloc(heap,s*sizeof(T));
  28.     }
  29.     heap[p++]=tt;
  30. }
  31.  
  32. template <class T> T MySuperStack<T>::pop (void){
  33.     if ( p <= 0)
  34.        exit (0);
  35.     return  heap[--p];
  36. }
  37.  
  38. void main (void){
  39.     MySuperStack ms <int>(10 , 10);
  40.  
  41.     ms.push (123);
  42.     ms.pop ();
  43. }
В примере данного кода конструктору стека как параметр передается два числа: “s1” - это начальный размер блока памяти, который выделяется для хранения всех элементов помещаемых в стек. Разумеется, что на какой-то стадии выделенного первоначально массива будет уже не хватать и тогда мы перевыделим для себя памяти добавив к существующему месту для “s1” элементов еще “a1” мест.

Задание: В большинстве языков программирования символы скобок “[({})]” должны быть симметричными. Составить алгоритм, который проверяет корректность заключения в скобки некоторой строки символов за время пропорциональное размеру строки. В качестве вспомогательной структуры данных использовать стек.

Очередь



Следующей структурой данных, которую мы рассмотрим, будет очередь. Она подобна стеку за исключением того, что работает по принципу FIFO (First In First Out). Таким образом, для очереди характерно добавление элементов в конец, а удаление из начала. Заметьте, что именно в таком порядке и никак иначе. Для очереди равно как и для стека характерно отсутствие механизмов доступа к произвольному элементу последовательности. Доступ к первому элемент автоматически означает и его удаление из очереди. Гораздо больший интерес представляет собой двунаправленная очередь или дек. Дек – характеризуется возможностью добавления и удаления элементов с обоих концов, для достижения данной функциональности необходимо ввести понятие двунаправленного списка. в тех списках с которыми мы работали ранее существовал только один элемент типа указатель на узел списка, который ссылался на следующий за ним элемент. В случае дека каждый элемент содержит в себе две ссылки на предыдущий и последующий элементы. 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3.  
  4. struct DeqNode{
  5. 	int inf;
  6. 	DeqNode * next , * prev;
  7. };
  8.  
  9. void addElementToEnd (DeqNode ** begin , DeqNode ** end , int inf){
  10. 	DeqNode * n = new DeqNode ;
  11. 	n->inf = inf;
  12. 	if (*begin == NULL){
  13. 		n->next = *end;
  14. 		n->prev = *begin;
  15. 		*end =  *begin = n;
  16. 	}
  17. 	else{
  18. 		n->prev = *end;
  19. 		n->prev->next = n;
  20. 		(*end)->next = n;
  21. 		n->next = NULL;
  22. 		*end = n;
  23. 	}
  24. }
  25.  
  26. void addElementToBegin (DeqNode ** begin , DeqNode ** end , int inf){
  27. 	DeqNode * n = new DeqNode ;
  28. 	n->inf = inf;
  29. 	if (*begin == NULL){
  30. 		n->next = *end;
  31. 		n->prev = *begin;
  32. 		*end =  *begin = n;
  33. 	}
  34. 	else{
  35. 		n->prev = NULL;
  36. 		n->next = *begin;
  37. 		n->next->prev = n;
  38. 		*begin = n;
  39. 	}
  40. }
  41.  
  42.  
  43. void removeElementFromEnd (DeqNode ** begin , DeqNode ** end ){
  44. 	if (*begin == NULL){
  45. 		perror ("error deq is empty, cannot delete last element");
  46. 		abort ();
  47. 	}
  48. 	if (*begin == *end){
  49. 		delete *begin;
  50. 		*begin = *end = NULL;
  51. 		return;
  52. 	}
  53. 	DeqNode *n = (*end)->prev;
  54. 	delete *end;
  55. 	n->next = NULL;
  56. 	*end = n;
  57. }
  58.  
  59. void removeElementFromBegin (DeqNode ** begin , DeqNode ** end ){
  60. 	if (*begin == NULL){
  61. 		perror ("error deq is empty, cannot delete first element");
  62. 		abort ();
  63. 	}
  64. 	if (*begin == *end){
  65. 		delete *begin;
  66. 		*begin = *end = NULL;
  67. 		return;
  68. 	}
  69. 	DeqNode *n = (*begin)->next;
  70. 	delete *begin;
  71. 	n->prev = NULL;
  72. 	*begin = n;
  73. }
  74.  
  75. void printForward (DeqNode ** begin , DeqNode ** end){
  76. 	DeqNode * p = *begin;
  77. 	while (p){
  78. 		printf ("%5d" , p->inf );
  79. 		p = p->next;
  80. 	}
  81. }
  82.  
  83. void deleteDeq (DeqNode ** begin , DeqNode ** end){
  84. 	DeqNode * p = *begin;
  85. 	while (p){
  86. 		DeqNode *n  = p->next;
  87. 		delete p;
  88. 		p = n;
  89. 	}
  90. 	*end = *begin = NULL;
  91. }
  92.  
  93. void main (void){
  94. 	DeqNode * begin = NULL, * end =  NULL;
  95. 	for (int i=0; i < 10; i++)
  96. 		addElementToBegin (&begin , &end , i);
  97. 	printForward (&begin , &end);
  98. 	printf ("\n");
  99.  
  100. 	removeElementFromBegin (&begin , &end);
  101. 	printForward (&begin , &end);
  102. 	printf ("\n");
  103. 	removeElementFromEnd (&begin , &end);
  104. 	printForward (&begin , &end);
  105. 	deleteDeq (&begin , &end);
  106. }




Следует отметить, что логически оба конца двусвязной очереди равноценны. 
 <h5> Задание: </h5>
1) При продаже акций компании капитальная прибыль (или убыток) определяются разностью между стоимостью акций при продаже и той суммой, которая была уплачена при их покупке. Этот механизм понятен при операциях с одной акцией, однако при большом количестве акций, которые продавались и покупались в течении длительного времени, необходимо установить какие именно акции продаются. Стандартный бухгалтерский принцип определения продаваемых акций – заключается в использовании метода FIFO: продаваемые акции – это те, которыми владеют наиболее долгое время. Допустим, покупаются 100 акций по цене 20$ за акцию в первый день, затем 20 акций по 24$, 200 акций по 36$ и наконец в четвертый день продаем 150 акций по 30$. В данном примере согласно принципу FIFO 100 акций были теми которые мы купили в первый день, 20 – во второй, и 30 – в третий. Тогда капитальная прибыль составит 100*10 + 20*6 + (-6)*30 = 940$.

Необходимо написать программу исходными данными, которой будет являться последовательность банковских операций:
  • купить X акций по цене Z$;
  • продать X акций по цене Z$.

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

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

4) Развейте вышеприведенный пример добавив возможность роста очереди по мере необходимости. Подсказка: воспользуйтесь решением из примера стека.

5) Создайте реализацию кругового списка в виде класса с предварительно выделяемой памятью.

6) Создайте рекурсивный алгоритм подсчета количества узлов списка.

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

Categories: Структуры данных и алгоритмы

« Структуры данных и алгоритмы. Теория. Рекурсия. Структуры данных и алгоритмы. Теория. Общие правила и рекомендации к разработке собственных контейнерных структур данных »