Информация


Programm.ws - это сайт, на котором вы можете почитать литературу по языкам программирования, а так-же посмотреть примеры работающих программ на С++, ассемблере, паскале и много другого..

Программирование — в обычном понимании, это процесс создания компьютерных программ.
В узком смысле (так называемое кодирование) под программированием понимается написание инструкций — программ — на конкретном языке программирования (часто по уже имеющемуся алгоритму — плану, методу решения поставленной задачи). Соответственно, люди, которые этим занимаются, называются программистами (на профессиональном жаргоне — кодерами), а те, кто разрабатывает алгоритмы — алгоритмистами, специалистами предметной области, математиками.
В более широком смысле под программированием понимают весь спектр деятельности, связанный с созданием и поддержанием в рабочем состоянии программ — программного обеспечения ЭВМ. Более точен современный термин — «программная инженерия» (также иначе «инженерия ПО»). Сюда входят анализ и постановка задачи, проектирование программы, построение алгоритмов, разработка структур данных, написание текстов программ, отладка и тестирование программы (испытания программы), документирование, настройка (конфигурирование), доработка и сопровождение.

Глава 2. Сложные структуры данных

Построение двоичного дерева

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

:prg02_12.asm - программа построения и инициализации двоичного дерева.
:Вход: произвольный массив чисел в памяти.
:Выход: двоичное дерево в памяти.
;объявления структур:
node_tree struc :узел дерева
simbol db 0 содержательная часть
l_son dd 0 указатель на старшего (левого) сына
r_son dd 0 указатель на младшего (правого) сына
ends
.data
mas db 37h.12h.8h.65h.4h.54h.llh.02h.32h.5h.4h.87h.7h.21h.65h.45h.22h.
Ilh,77h.51h,26h.73h.35h.l2h.49h.37h.52h l_mas=$-mas
.code
BuildBinTree proc
формируем корень дерева и указатель на дерево HeadTree
:для размещения дерева используем кучу, выделяемую процессу по умолчанию (1 Мбайт).
:но при необходимости можно создать и доп. кучу с помощью HeapCreate
iHANDLE GetProcessHeap (VOID):
call GetProcessHeap
movHand_Head,eax сохраняем дескриптор ;запрашиваем и инициализируем блок памяти из кучи для корня дерева:
xorebx.ebx :здесь будет указатель на предыдущий узел ;LPVOID HeapAllос(HANDLE hHeap, DWORD dwFlags, DWORD dwBytes):
push type node_tree :размер структуры для узла дерева
push 0 ;флаги не задаем
push eax :описатель кучи (он же в Hand_Head)
call НеарАПос
mov HeadTree.eax запоминаем указатель на корень дерева
mov ebx.eax :и в ebx :подчистим выделенную область памяти в куче
push ds
pop es
mov edi .eax
mov ecx.type node_tree
mov al .0 rep stosb
leaesi.mas ;первое число из mas в корень дерева
lodsb ;число в al
mov [ebx].simbol.al
mov ecx.l_mas-l @@cycll: ;далее в цикле работаем с деревом и массивом mas
push ecx ;НеарА11ос портит ecx. возвращая в нем некоторое значение ;запрашиваем блок памяти из кучи для узла дерева: ;LPVOID HeapAllос(HANDLE hHeap. DWORD dwFlags, DWORD dwBytes);
push type node_tree:размер структуры для узла дерева
push 0 :флаги не задаем
push HandJHead :описатель кучи
call НеарАПос
pop ecx
mov ebx.eax запоминаем указатель на узел дерева в ebx
mov NewNode.eax :и во врем, перем. ¦подчистим выделенную область памяти в куче
movedi.eax
push ecx
mov ecx.type node_tree
mov al .0 rep stosb
pop ecx
:читаем очередное число из mas и записываем его в новый узел lodsb :число в al mov [ebx].simbol,al
;ищем место в дереве согласно условиям упорядочивания ;и настраиваем указатели в узлах дерева
mov ebx.HeadTree m_search: cmpal.[ebx].simbol mov edi .ebxпродублируем
jae ml :если al >= [ebxj.simbol :если меньше, то идем по левой ветке
mov ebx.[ebx].l_son
cmp ebx.O
jnem_search ;если этого сына нет. то добавляем его к папе
mov ebx.NewNode
mov [edi].l_son.ebx
jmp end_cycl 1
:если больше или равно, то по правой ml: mov ebx. [ebx]. r_son
cmp ebx.O
jnem_search :если этого сына нет. то добавляем его к папе
mov ebx.NewNode
mov [edi].r_son.ebx end_cycll: loop @@cycll
ret ;двоичное дерево поиска построено BuildBinTree endp start proc near :точка входа в программу:
call BuildBinTree

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

2h.4h.4h,5h.7h,8h.nh.llh,12h.l2h.21h.22h.26h.32h,35h,37h.37h.4*5h.49h.51h.52h. 54h.65h.65h.73h.77h.87h.

бедимся в этом, разработав программу обхода двоичного дерева.