Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23
Download 1.85 Mb. Pdf ko'rish
|
C# Алгоритмы и структуры данных 2018 Тюкачев, Хлебостроев
- Bu sahifa navigatsiya:
- Листинг 4.15. Создание турнирной пирамиды
|
Листинг 4.14. Класс Node
public class Node { 23 / 23 93 public int data; // данные public Node left; public Node right; // потомки public Node next; // брат public int x; public int y; // координаты узла public Node(int data, Node left, Node right, int x, int y) } На первом этапе строится линейный список из элементов сортируемой последовательности. Следующий уровень пирамиды формируется путем сравнения ключей в каждой из пар и выбора элемента с меньшим значением ключа. Процесс продолжается до тех пор, пока не будет достигнут уровень, содержащий единственный элемент с минимальным значением ключа. Для построения пирамиды необходимо, чтобы все значения были из- вестны. Поэтому вводимые значения считываются из текстового поля и зано- сятся в массив. При построении пирамиды одновременно производится про- рисовка ее на форме. В листинге 4.15 приведено описание метода HeapCre- ate (), в котором производится построение пирамиды и вывод ее графическо- го изображения на экран. Входным параметром этого метода является высота области построения изображения пирамиды H, а результатом – узел на вер- шине пирамиды. Листинг 4.15. Создание турнирной пирамиды public Node HeapCreate(int H) // Создание дерева-пирамиды { Node pLevel; // первый узел текущего уровня Node pNew, pOld; // рабочие переменные Node comp1, comp2; // узлы соревнующейся пары // построение самого нижнего уровня пирамиды int x = deltaX; int y = H-diametr-deltaY; 1 / 23 94 // создание первого элемента pLevel = new Node(a[0],null,null,x,y); pOld = pLevel; pNew = null; // включение в список элементов массива for (int i = 1; i < a.Length; i++) { x = x + deltaX + radius; pNew = new Node(a[i],null,null,x,y); pOld.next= pNew; // линейный список по уровню pOld = pNew; } pNew.next = null; // построение других уровней while (pLevel.next != null) { // цикл до вершины пирамиды y = y - deltaY - diametr; comp1 = pLevel; pLevel = null; // начало нового уровня while (comp1 != null) { // цикл по очередному уровню comp2 = comp1.next; // адреса потомков из предыдущего уровня pNew = new Node(0,comp1,comp2,x,y); // связывание в линейный список по уровню if (pLevel==null) pLevel = pNew; // назначение pLevel else pOld.next = pNew; 2 / 23 95 pOld = pNew; // состязание данных за выход на уровень if ((comp2 == null) || (comp2.data > comp1.data)) pNew.data = comp1.data; else pNew.data = comp2.data; if (comp2==null) x = comp1.x; else x = (comp1.x+comp2.x)/2; pNew.x = x; pNew.y = y; // переход к следующей паре if (comp2!=null) comp1 = comp2.next; else comp1 = null; } } return pLevel; } Метод HeapCreate() является членом класса MyTour, который кроме того содержит открытое целочисленное поле-массив a и поле-массив arr эк- земпляров класса Node. В массиве a хранится исходная последовательность значений, а в массиве arr – отсортированная последовательность узлов де- рева-пирамиды. Членами класса MyTour являются методы, выполняющие построение изображения пирамиды – Draw(), DrawNode() и SetDelta(). Обработчик события клика по кнопке «Создать», представленный на листинге 4.16, считывает данные из текстового поля textBox1 на форме, сохраняя их в поле-массиве a, вызывает метод HeapCreate() и затем метод Draw () (листинг 4.16). Download 1.85 Mb. Do'stlaringiz bilan baham: 
|