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

        Односвязные списки – стек и очередь. Реализация стека  и  очереди.

Динамическая структура данных состоит из узлов, включающих в себя информационную часть (данное, ради которого создается узел) и ссылочную часть (указатели на себе подобных). Динамические структуры данных классифицируются на списки, деревья и графы. Списки бывают односвязными и двусвязными. Узел односвязных списков содержит один указатель на следующий узел. Односвязные списки подразделяются на стеки, очереди, деки, циклические списки и списки прямого доступа. Двусвязные списки реализуются только как списки прямого доступа. На языке С узел односвязного списка можно задать структурой, содержащей, например, поле данных info и поле типа указатель на Node next:

struct Node

{

       double info;

       Node* next;

};

Стек

Логика стека - первым пришел, последним ушел. Для работы со стеком нам нужен только один указатель на первый узел (вершина стека):

struct Stack

{

       Node* top;

};

Вся работа выполняется только с этим элементом. Мы добавляем новые элементы в вершину стека и удаляем элементы из вершины.

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

1. Инициализация стека:

Stack initStack()

{

       Stack S = {0};

       return S;

}

1. Добавление элемента в стек:

void push(Stack &S, double inf)

{

       Node* work = new Node;

       work->info = inf;

       work->next = S.top;

       S.top = work;

}

1. Удаление элемента из стека:

bool pop(double& inf, Stack& S)

{

       if(!S.top) return false;

       Node* work = S.top;

       S.top = S.top->next;

       inf = work->info;

       delete work;

       return true;

}

1. Очистка стека:

void clear(Stack& S)

{

       while(S.top)

       {

                   Node* work = S.top;

                   S.top = S.top->next;

                   delete work;

       }

}

1. Получение данного из вершины стека:

bool get(double& inf, const Stack& S)

{

       if(!S.top) return false;

       inf = S.top->info;

       return true;

}

1. Проверка состояния стека:

bool empty(const Stack& S)

{

       return !S.top;

}

Очередь

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

struct Queue

{

       Node* top, * bottom;

};

Для работы с очередью можно выделить такие же операции, как и над стеком. Будет отличаться только реализация.

Итераторы

 Итераторы - односвязные списки прямого доступа. Реализация Итератора. Обратная польская запись - алгоритм Дейкстры.

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

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

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

struct List

{

       Node* top, * bottom;

};

struct Iterator

{

       Node* current;

};

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

1. Инициализация списка:

List initList()

{

       List L = {0, 0};

       return L;

}

1. Добавление элемента в голову списка:

void push(List &L, double inf)

{

       Node *work = new Node;

       work->info = inf;

       work->next = L.top;

       if(!L.top)

                   L.bottom = work;

       L.top = work;

}

1. Удаление элемента из головы списка:

bool pop(double& inf, List& L)

{

       if(!L.top) return false;

       Node* work = L.top;

       L.top = L.top->next;

       inf = work->info;

       delete work;

       return true;

}

1. Очистка списка:

void clear(List& L)

{

       while(L.top)

       {

                   Node* work = L.top;

                   L.top = L.top->next;

                   delete work;

       }

       L.bottom = 0;

}

1. Получение данного из головы списка:

bool get(double& inf, const List& L)

{

       return L.top ? (inf = L.top->info, true) : false;

}

1. Проверка состояния списка:

bool empty(const List& L)

{

       return !L.top;

}

1. Установка итератора в голову списка:

Iterator begin(List& L)

{

       Iterator I = {L.top};

       return I;

}

1. Установка итератора в хвост списка:

Iterator end(List& L)

{

       Iterator I= {L.bottom};

       return I;

}

1. Перемещение итератора на следующий узел:

bool next(Iterator& I)

{

       return I.current ? (I.current = I.current->next, true) : false;

}

1. Добавление узла после узла, на который установлен итератор:

bool add(List &L, Iterator &I, double inf)

{

       if(!I.current && L.top)     return false;

       Node* work = new Node;

       work->info = inf;

       if(!L.top)

       {

                   work->next = 0;

                   L.top = L.bottom = I.current = work;

       }

       else if(!I.current->next)

       {

                   work->next = 0;

                   L.bottom = I.current->next = work;

       }

       else

       {

                   work->next = I.current->next;

                   I.current->next = work;

       }

       return true;

}

1. Удаление узла, расположенного после узла, на который установлен итератор:

bool del(double& inf, List &L, const Iterator &I)

{

       if(!L.top || !I.current || !I.current->next) return false;

       Node* work = I.current->next;

       inf = work->info;

       I.current->next = work->next;

       if(!work->next)

       {

                   L.bottom = I.current;

       }

       delete work;

       return true;

}

1. Получение информационной части узла, на который установлен итератор:

double get(const Iterator &I)

{

       return I.current ? I.current->info : 0.;

}

1. Получение информационной части узла следующего за тем, на который установлен итератор;

double getNext(const Iterator &I)

{

       return I.current && I.current->next ? I.current->next->info : 0.;

}

1. Установлен ли итератор на список;

bool check(const Iterator &I)

{

       return I.current;

}

1. Сравнение итераторов;

bool operator ==(const Iterator& I1, const Iterator& I2)

{

       return I1.current == I2.current;

}

bool operator !=(const Iterator& I1, const Iterator& I2)

{

       return I1.current != I2.current;

}

1. Замена информационной части узла, на который установлен итератор:

bool set(Iterator& I, double inf)

{

       if(!I.current) return false;

       I.current->info = inf;

       return true;

}

1. Замена информационной части узла, следующего за тем, на который установлен итератор:

bool setNext(Iterator& I, double inf)

{

       if(!I.current || !I.current->next) return false;

       I.current->next->info = inf;

       return true;

}

Обратная польская запись

Для вычисления выражений используется обратная польская запись или обратная польская нотация. Она была разработана австралийским философом и специалистом в области теории вычислительных машин Чарльзом Хэмблином в середине 1950-х на основе польской нотации, которая была предложена в 1920 году польским математиком Яном Лукасевичем.

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

• Выражение состоит из последовательности операндов и операторов.
• Выражение читается слева направо. Когда в выражении встречается оператор, выполняется соответствующая операция над двумя или одним (в зависимости от арности оператора) последними встретившимися перед ним операндами в порядке их записи. Результат операции заменяет в выражении последовательность её операндов и оператора, после чего выражение вычисляется дальше по тому же правилу.
• Результатом вычисления выражения становится результат последней вычисленной операции.

Эдсгер Дейкстра предложил алгоритм для преобразования выражений из инфиксной нотации в обратную польскую нотацию.

Алгоритм:

1. Пока в выражении есть лексемы:
1. Берем очередную лексему;
2. Если лексема операнд, добавляем в выходную строку;
3. Если лексема является функцией, помещаем его в стек;
4. Если – оператор и приоритет его меньше, либо равен приоритету оператора, находящегося на вершине стека, выталкиваем верхние операторы из стека в выходную строку до тех пор, пока не встретится оператор с меньшим приоритетом, или открывающая круглая скобка, или стек станет пустым и помещаем его в стек;
5. Если оператор и приоритет его больше приоритета оператора на вершине стека, то просто помещаем его в стек;
6. Если лексема является открывающей скобкой, помещаем ее в стек;
7. Если символ является закрывающей скобкой, то до тех пор, пока верхним элементом стека не станет открывающая скобка, выталкиваем элементы из стека в выходную строку. При этом открывающая скобка удаляется из стека, но в выходную строку не добавляется. Если после этого на вершине стека оказывается функция, выталкиваем ее в выходную строку.
2. Когда входное выражение закончилось, выталкиваем все символы из стека в выходную строку.

Мы получили выражение в обратной польской записи.

3.4. Примеры с использованием списка прямого доступа и итераторов.

Рассмотрим несколько примеров с использование итераторов.

Вывод списка:

void printList(const List& L)

{

       for(Iterator I = begin(L); check(I); next(I))

                   printf(“%7.3lf ”, get(I));

       printf(“\n”);

}

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

int insertSort(List &L, double inf)

{

       int Pos = 0;

       Iterator I = begin(L);

       if(!check(I) || get(I) >= inf)

                   push(L, inf);

       else

       {

                   for(Pos = 1; I != end(L) && getNext(I) < inf; next(I), Pos++);

                   add(L, I, inf);

       }

       return Pos;

}

Удаление повторяющихся элементов:

int delElem(List &L)

{

       int Count = 0;

       for(Iterator I1 = begin(L); I1 != end(L); next(I))

                   for(Iterator I2 = I1; I2 != end(L); )

                              if(get(I1) == getNext(I2))

                              {

                                          double temp;

                                          del(temp, L, I2);

                                          Count++;

                              }

                              else

                                          next(I2);

       return Count;

}

Сортировка элементов списка:

void sortList(List &L)

{

       for(Iterator I1 = begin(L); I1 != end(L); next(I))

       {

                   double temp1 = get(I1);

                   for(Iterator I2 = I1; next(I2), check(I2); )

                              if(temp1 > get(I2))

                              {

                                          temp1 = get(I2);

                                          set(I2, get(I1));

                                          set(I1, temp1);

                              }

       }

}

 3.5. Графика.

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

Компоненты графики.

На любом визуализируемом компоненте можно рисовать, но лучше использовать стандартный компонент pictureBox.

Для рисования на компонентах используется класс Graphics, который содержит методы для рисования. Все методы рисования можно разделить на две группы: те, которые используют ручку Pen, и те, которые используют кисточку SolidBrush. Те методы, которые используют Pen, начинаются со слова Draw, а те, которые SolidBrush со слова Fill.

Методы, использующие Pen:

• Рисование линии:

void DrawLine(Pen^ pen, PointF p1, PointF p2).

• Рисование ломаной линии:

void DrawLines(Pen^ pen, array<PointF>^ points).

• Рисование замкнутой области:

void DrawPolygon(Pen^ pen, array<PointF>^ points).

• Рисование прямоугольника:

void DrawRectangle(Pen^ pen, Rectangle rect).

• Рисование эллипса

void DrawEllipse(Pen^ pen, RectangleF rect).

• Рисование дуги эллипса

void DrawArc(Pen^ pen, RectangleF rect, float startAngle, float sweepAngle).

• Рисование сектора эллипса

void DrawPie(Pen^ pen, RectangleF rect, float startAngle, float sweepAngle).

Методы, использующие SolidBrush:

• Рисование замкнутой области:

void FillPolygon(Brush^ brush, array<PointF>^ points).

• Рисование прямоугольника

void FillRectangle(Brush^ brush, Rectangle rect).

• Рисование эллипса

void FillEllipse(Brush^ brush, RectangleF rect).

• Рисование сектора эллипса

void FillPie(Brush^ brush, RectangleF rect, float startAngle, float sweepAngle).

Для того, чтобы что-нибудь нарисовать, надо создать объект класса Graphics и необходимые инструменты: ручки и кисточки.

Объект Graphics необходимо связать c полем для рисования. Если просто рисовать на поле компонента, то это нигде не будет сохраняться, и при свертывании окна или при перекрытии компонента рисунок будет потерян. Поэтому необходимо выделять память под поле Image компонента и связывать объект класса Grapics c ним.

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

График функции.

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

Для того, чтобы разместить график функции на поле выбранного компонента, необходимо выполнить преобразование координат, в которых задана функция ( такие координаты принято называть мировыми ), в экранные координаты или, точнее, в координаты выбранной для постороения графика компоненты Среды. Аргумент функции изменяется в задавемом пользователем интервале [a,b]. На заданном интервале функия изменяется в пределах от Ymin до Ymax. Интервал [a,b] надо сопоставить с шириной окна, в поле которого буде выводится график функции, а интервал [Ymin,Ymax] сопоставить с высотой окна. Для построения графика функции удобно использовать класс Rectangle и его свойства Width и Height, а затем связать объект Rectangle Rec с pictureBox1->ClientRectangle.

Удобно сначала сформировать массив точек PointF, а затем вывести изображение графика функции на экран, используя метод DrawLines().

Для нахождения максимального и минимального значения функции на заданном интервале a,b  можно использовать функции maxY() и  minY(), возвращающие значение типа double.

double maxY(double A, double B, double h, double (*Pf)(double))

{

       double Ymax = Pf(A);

       for(double X = A + h; X < B + h/2; X += h)

       if(Ymax < Pf(X))

                   Ymax = Pf(X);

       return Ymax;

}

double minY(double A, double B, double h, double (*Pf)(double))

{

       double Ymin = Pf(A);

       for(double X = A + h; X < B + h/2; X += h)

       if(Ymin > Pf(X))

                   Ymin = Pf(X);

       return Ymin;

}

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

   Для выполнения преобразования координат необходимо найти масштабные коэффициенты по осям X и Y: масштаб по оси X – Mx определяется как отношение количества точек экрана по оси Х к интервалу изменения аргумента выводимой на экран функции; масштаб по оси Y – mY определяется как отношение размера экрана по оси Y (Rec.Height - Rec.Y) к (Ymax – Ymin).

array<Point>^ DrawGraph(Rectangle Rec, double A, double B, double (*Pf)(double))

{

       int Count = Rec.Width - Rec.X + 1;

       double h = (B - A)/(Count - 1);

       double Ymax = maxY(A, B, h, Pf);

       double Ymin = minY(A, B, h, Pf);

       double Mx = 1/h;

       double My = (Rec.Height - Rec.Y)/(Ymax - Ymin);

       array<Point>^ mas = gcnew array<Point>(Count);

       double X = A;

       for(int i = 0; i < Count; i++, X += h)

                   mas[i] = Point(Rec.X + Mx*(X - A), Rec.Height - My*(Pf(X) - Ymin));

       return mas;

}

Вызов функции DrawGraph() осуществляется из gr->DrawLines(). В примере показана передача функции DrawGraph() функции Sin(х), заданной на интервале [0., 12.56].

private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e)

 {

        Pen ^pen = gcnew Pen(Color::Black);

        Graphics^ gr = pBox->CreateGraphics();

       gr->Clear(Color::White);       

       gr->DrawLines(pen, DrawGraph(pictureBox1->ClientRectangle, 0., 12.56, Math::Sin));

 }

Для построения гистограммы можно использовать массив целых чисел. Так же, как и при построении графика, надо вычислить масштаб по X и по Y:

Mx = W/Length,

где Length – размерность массива;

My = H/ElemMax,

Где ElemMax – значение максимального элемента массива.

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