Сборник по задачам и примерам Assembler

         

каждая конечная вершина имеет высоту


  • каждая конечная вершина имеет высоту h или h-1;


  • каждая конечная вершина высоты h нажщится слева от любой конечной вершины высоты h-1;


  • метка любой вершины больше метки любой следующей за ней вершины.


    • На Рисунок 2.3 изображено несколько деревьев, из которых лишь одно Т4 является пирамидой.



    Рисунок 2.3. Примеры деревьев (Т4 — пирамида)

    Такая структура пирамид позволяет компактно располагать их в памяти. Например, пирамида, показанная на рисунке, в памяти будет представлена следующим массивом: 27, 9, 14, 8, 5, 11, 7, 2, 3. Оказывается, что такая последовательность чисел легко подвергается сортировке.

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

    ПРОЦЕДУРА insert_item_in_tree (i. mas. N) //

    //insert_item_in_tree - процедура на псевдоязыке вставки элемента на свое место

    в пирамиду //Вход: mas[n] - сформированная не до конца пирамида: 1 - номер добавляемого элемента

    в пирамиду из mas[n] (с конца): n - длина пирамиды //Выход:действие - элемент добавлен в пирамиду.

    НАЧ_ПРОГ

    j:=i @@ml: k:=2*j: h-k+1

    ЕСЛИ (1=<N И (mas[j]<mas[k] ИЛИ mas[j]<mas[l]) TO ПЕРЕЙТИ_НА @йп6

    ИНАЧЕ ПЕРЕЙТИ_НА @@m2

    КОН_ЕСЛИ @@m6: ЕСЛИ tnas[k]>mas[l] TO ПЕРЕЙТИ_НА @@т4

    ИНАЧЕ ПЕРЕЙТИ_НА @@тЗ

    КОН_ЕСЛИ @@т4: x:=mas[j]

    mas[j]:=mas[k]

    j:=k

    mas[k]:=x ПЕРЕЙТИ_НА (a0ml (а@тЗ: x:=mas[j]

    mas[j]:=mas[l]

    mas[l]:=x

    ПЕРЕЙТИ_НА @@ml*

    @@m2: ЕСЛИ (k==n И mas[j]<mas[k]) TO ПЕРЕЙТИ_НА @@m7

    ИНАЧЕ ПЕРЕЙТИ_НА @@m8

    КОН_ЕСЛИ @@m7: x:=mas[j]

    mas[j]:=mas[n]

    ;m-n/2 - значение, равное половине числа элементов массива mas

    push si push ex

    movj.si :j\»1 @@m4:

    movsi.j :i->si

    movax.j :k:=2*j; l:-k+l

    shlax.l :j*2

    movk.ax : k :=j*2

    inc ax

    movl.ax :l:»k+l

    cmpax.m :l<m

    ja @@m2

    moval ,raas[si-l] ;ax:-mas[j]


    Содержание  Назад  Вперед




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