Сортировка кучей

@songpls · Регистрация: 16.06.2019

Студворк — интернет-сервис помощи студентам

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

@Constantin Cat · 17.06.2019, 11:04

Сообщение от songpls

с использованием сложных структур данных

Что есть сложная структура?

Assembler
1
2
3
4
POINT STRUCT
  x  DWORD ?
  y  DWORD ?
POINT ENDS

или это

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
FILETIME STRUCT
  dwLowDateTime     DWORD     ?
  dwHighDateTime    DWORD     ?
FILETIME ENDS
MSG STRUCT
  hwnd      DWORD      ?
  message   DWORD      ?
  wParam    DWORD      ?
  lParam    DWORD      ?
  time      DWORD      ?
  pt        POINT      <>
MSG ENDS
WIN32_FIND_DATA STRUCT
  dwFileAttributes      DWORD      ?
  ftCreationTime        FILETIME <>
  ftLastAccessTime      FILETIME <>
  ftLastWriteTime       FILETIME <>
  nFileSizeHigh         DWORD      ?
  nFileSizeLow          DWORD      ?
  dwReserved0           DWORD      ?
  dwReserved1           DWORD      ?
  cFileName             BYTE MAX_PATH dup(?)
  cAlternate            BYTE 14 dup(?)
WIN32_FIND_DATA ENDS

ps:все цытаты взяты из windows.inc

ФедосеевПавел · 24.06.2019, 02:38

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
.686
.model flat, stdcall
option casemap :none
 
        include \masm32\include\windows.inc
 
        include \masm32\include\user32.inc
        include \masm32\include\kernel32.inc
        include \masm32\include\masm32.inc
 
        includelib \masm32\lib\user32.lib
        includelib \masm32\lib\kernel32.lib
        includelib \masm32\lib\masm32.lib
.data
        aszMsgInstant   db      0Dh, 0Ah, 'The data before sorting:', 0Dh, 0Ah, 0
        aszMsgResult    db      0Dh, 0Ah, 'The data after sorting:', 0Dh, 0Ah, 0
        aszInteger      db      '%4d', 0
        aszPressEnter   db      0Dh, 0Ah, 0Dh, 0Ah, "Press ENTER to exit", 0
        aszCrLf         db      0Dh, 0Ah, 0
        Array           dd      22,  8, 42,  7, 43, 81, 51, 14, 49,  7
        ASize           dd      LENGTHOF Array
 
.data?
        hConsoleOutput  HANDLE  ?
        hConsoleInput   HANDLE  ?
        Buffer          db      1024 dup(?)
        BufLen          dd      ?
 
.code
 
;вспомогательная процедура для сортировки кучей
;алгоритм процедуры восстановления баланса пирамиды при добавлении нового A[K]
;  A[]   - исходный массив
;  K     - индекс добавляемого/просеиваемого элемента
;  N     - максимальное значение индекса массива
;процедура просеивания следующего элемента:
;До процедуры: A[K+1]...A[N]  - пирамида
;После:  A[K]...A[N]  - пирамида
siftDown        proc      lpArray:DWORD, K:DWORD, N:DWORD       ;procedure siftDown(var A: TArray; K, N: integer);
                                                                ;  var
                                                                ;    temp: integer;
                                                                ;    childPos: integer;
        pushad                                                  ;  begin
        mov     ebx,    [N]
        mov     esi,    [lpArray]
        mov     ecx,    [K]
                                                                ;    {Это чтобы при K=0 И N=0 не делалось лишней перестановки}
        test    ebx,    ebx                                     ;    if 0 = N then
        jz      _exit                                           ;      exit;
        mov     edi,    [esi+ecx*4]                             ;    temp := A[K];
        _while:                                                 ;    while K * 2 + 1 <= N do
                                                                ;    begin
                mov     edx,    ecx                             ;      childPos := 2 * K + 1;  // Индекс левого ребенка
                add     edx,    edx
                inc     edx
                cmp     edx,    ebx
                ja      _break
                                                                ;      // выбираем в childPos индекс большего ребенка
                mov     eax,    edx                             ;      if (childPos + 1 <= N) and (A[childPos] < A[childPos + 1]) then
                inc     eax
                cmp     eax,    ebx
                ja      @f
                mov     eax,    [esi+eax*4]
                cmp     eax,    [esi+edx*4]
                jle     @f
                inc     edx                                     ;        Inc(childPos);
        @@:                                                     ;
                                                                ;      // Если A[K] больше максимального ребенка - завершение
                cmp     edi,    [esi+edx*4]                     ;      if (temp >= A[childPos]) then
                jge     _break                                  ;        break;
                                                                ;
                                                                ;      // иначе - меняем его с наибольшим ребенком
                mov     eax,    [esi+edx*4]                     ;      A[K] := A[childPos];
                mov     [esi+ecx*4],    eax
                                                                ;
                mov     ecx,    edx                             ;      K := childPos;
        jmp     _while                                          ;    end;
_break:
        mov     [esi+ecx*4],    edi                             ;    A[K] := temp;
_exit:                                                          ;  end;
        popad
        ret
siftDown        endp
 
;сортировка кучей (пирамидальная сортировка)
;на входе:
;  lpArray  - адрес массива
;  uiAmount - длина массива
HeapSort        proc    lpArray:DWORD, uiAmount:DWORD                   ;  procedure HeapSort(var A: TArray; N: integer);
                                                                        ;  var
                                                                        ;    i: integer;
                                                                        ;    temp: integer;
        pushad                                                          ;  begin
        mov     esi,    [lpArray]
        mov     ebx,    [uiAmount]
        ;Построение пирамиды                                            ;    { Построение пирамиды }
        mov     ecx,    ebx                                             ;    for i := (N div 2) - 1 downto 0 do
        shr     ecx,    1
        dec     ebx     ;т.к. в дальнейшем нужно только значение (N-1)
        jmp     _next
        _for:
                invoke  siftDown,       esi, ecx, ebx                   ;      siftDown(A, i, N - 1);
        _next:
                dec     ecx
        jns     _for
                                                                        ;    {Формирование конечной отсортированной
                                                                        ;     последовательности + "балансирование"
                                                                        ;     пирамиды }
        mov     ecx,    ebx                                             ;    i := N - 1;
        jmp     _test_while                                             ;    while i > 0 do
        _while:                                                         ;    begin
                ;меняем первый с последним                              ;      {меняем первый с последним}
                push    dword ptr [esi]                                 ;      temp := A[0];
                push    dword ptr [esi+4*ecx]                           ;      A[0] := A[i];
                pop     dword ptr [esi]                                 ;      A[i] := temp;
                pop     dword ptr [esi+4*ecx]
                ;Восстановление баланса для пирамиды A[0..i-1]          ;      {Восстановление баланса для пирамиды A[0..i-1]}
                dec     ecx                                             ;      Dec(i);
                invoke  siftDown,       esi, 0, ecx                     ;      siftDown(A, 0, i);
        _test_while:                                                    ;    end;
                test    ecx,    ecx
        jnz     _while
        popad                                                           ;  end;
        ret
HeapSort        endp
 
ShowArray       proc    lpArray:DWORD, uiAmount:DWORD
        pushad
 
        mov     ecx,    [uiAmount]
        mov     esi,    [lpArray]
        @@ForI:
                push    ecx
                lodsd
                invoke  wsprintf,       ADDR Buffer, ADDR aszInteger, eax
                mov     [BufLen],       eax
                invoke  WriteConsole,   hConsoleOutput, ADDR Buffer,\
                                        BufLen, ADDR BufLen, NULL
                pop     ecx
        loop    @@ForI
 
        popad
        ret
ShowArray       endp
 
main    proc
 
        ; получение описателей ввода и вывода консоли
        invoke  GetStdHandle,   STD_INPUT_HANDLE
        mov     hConsoleInput,  eax
 
        invoke  GetStdHandle,   STD_OUTPUT_HANDLE
        mov     hConsoleOutput, eax
 
        invoke  ClearScreen
 
        ;вывод исходных данных
        invoke  WriteConsole,   hConsoleOutput, ADDR aszMsgInstant,\
                                LENGTHOF aszMsgInstant - 1,\
                                ADDR BufLen, NULL
        invoke  ShowArray,      ADDR Array, [ASize]
 
        ;обработка массива - сортировка
        invoke  HeapSort,       ADDR Array, [ASize]
        ;вывод результата
        invoke  WriteConsole, hConsoleOutput, ADDR aszMsgResult,\
                LENGTHOF aszMsgResult - 1, ADDR BufLen, NULL
        invoke  ShowArray,      ADDR Array, [ASize]
 
        ;ожидание нажатия ENTER
        invoke  WriteConsole,   hConsoleOutput, ADDR aszPressEnter,\
                                LENGTHOF aszPressEnter - 1, ADDR BufLen, NULL
        invoke  ReadConsole,    hConsoleInput, ADDR Buffer,\
                                LENGTHOF Buffer, ADDR BufLen, NULL
 
        invoke  ExitProcess,    0
main    endp
 
end     main

Новые блоги и статьи Все статьи Все блоги /
Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .
Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .	Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .

@songpls 0 / 0 / 0 Регистрация: 16.06.2019 Сообщений: 1

	Сортировка кучей 16.06.2019, 15:29. Показов 1764. Ответов 2 Метки ассемблер (Все метки) Здравствуйте, нужно написать программу вычисления арифметических операций, с использованием сложных структур данных. Подсказали массив с сортировкой кучей, особо не разбираюсь в ассемблере, надеюсь на помощь. 0