Информация


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

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

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

Неупорядоченные таблицы

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

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

  • содержимое файла — идентификаторы и константы, разделенные не более чем одним пробелом, перед первым или последним идентификатором или константой в строке также следуют по одному пробелу;
  • для удобства преобразования предполагаем, что длина и количество строк файла maket.txt находятся в диапазоне 0..99, а общая длина файла — не более 240 байт.

Поле текущего состояния представляет собой запись, битовые поля которой означают следующее:

  • биты 0 и 1 — состояние элемента: 00 — свободен; 01 — используется; 10 — удален;
  • бит 2 — тип константы: 0 — десятичная константа; 1 — шестнадцатеричная константа;
  • бит 3 — 0 — не последний элемент таблицы; 1 — последний элемент таблицы.

:prg02_05.asm - программа на ассемблере демонстрации работы с неупорядоченной таблицей ;Вход: файл maket.txt с идентификаторами, среди которых присутствуют десятичные
и шестнадцатеричные константы. ;Выход: вывод информации о десятичных константах на экран.
state_tab struc
last_off dw 0 ;адрес первого байта за концом таблицы
elem_free dw 0 ;адрес первого свободного элемента (Offffh - все занято)
ends
constant struc
state db 0 ;поле состояния элемента таблицы
db 02dh форматирование вывода на экран key db 10 dup (' ') :ключ. он же значение константы
db 02dh форматирование вывода на экран
line db 2 dup (' ') :строка файла, в которой встретилась константа endjine db Odh.Oah.'S' :для удобства вывода на экран ends .data
s_tab state_tab <> tab constant 19 dup (<>)
constant <8.> последний элемент таблицы - бит 3=1 end_tab=$-tab
filename db 'maket.txf.0 handle dw 0 :дескриптор файла buf db 240 dup С ') xlat_tab db Odh dup (OO).Odh ;признак конца строки
db 'O'-Oeh dup (0)
db ':'-'0'+l dup CO') ;признак цифры 0..9
db 'H'-':' dup (0). " :признак буквы 'Н'
db 'h'-'H' dup (0). 'h' ;признак буквы 'h' db Offh-'h1 dup (00)
curjine db 0
.code
:открываем файл mov ah. 3dh
movdx,offset filename
int 21h
jc exit :ошибка (cf=l)
mov handle.ax ;читаем файл:
movah.3fh :функция установки указателя
mov bx,handle
mov ex,240 ;читаем максимум 240 байт
lea dx.buf
int 21h
jc exit
mov ex.ax фактическая длина файла в сх инициализируем дескриптор таблицы s_tab
lea si.tab :адрес таблицы в si
mov s_tab.elem_fгее.si ;первый элемент таблицы - свободен
add si .end_tab
mov s_tab.last_off,si :адрес первого байта за концом таблицы
lea bx.xlat_tab
leadi. buf
cканируем до первого пробела: push ds popes
cycll: mov al. ' ' repne scasb -.сканирование до первого пробела
jcxz displ .цепочка отсканирована -> таблица заполнена push сх :классифицируем символ после пробела (команда XLAT):
mov al.[di]
xlat
emp al. '0':первый символ после пробела - 0
je ml
cmpal.Odh :первый символ после пробела - Odh
je m2 :все остальное либо идентификаторы, либо неверно записанные числа
pop сх
jmpcycll ml: :первый символ после пробела - 0..9:
mov si.di ;откуда пересылать
fmov al. ' ' push di repne scasb сканирование до первого пробела mov cx.di dec ex subcx.si ;сколько пересылать lea di.tab emp s__tab.elem_free.0ffffh :есть свободные элементы? je displ : свободных элементов нет
mov di,s_tab.elem_free :адрес первого свободного элемента push di
lea di.[di].key rep movsb ;пересыпаем в элемент таблицы
deed! ;Какого типа это константа?
emp byte ptr [di].'h' popdi
je m4
and [di].state.Ofbh ;десятичная константа
jmp $+5 m4: or [di].state.100b ;шестнадцатеричная константа
mov al ,cur_line :текущий номер строки в al
aam преобразуем в символьное представление
or ah.030h
mov [di].line,ah
or al.030h
mov [di+1].line.al :и в элемент таблицы
or [di].state.lb ;помечаем элемент как используемый
:теперь нужно поместить в поле s_tab.elem_free адрес нового свободного элемента пб: emp di. s_tab. 1 ast_of f
ja displ
add di.type constant :к следующему элементу
test [di].state.lb
jnz m5 ; используется => к следующему элементу
mov s_tab.elem_fгее.d i pop di pop ex
jmpcycU m2: увеличить номер строки
inc cur_line
jmp cycl 1 displ: :отображение на экране элементов таблицы
lea di .tab m6:
test [di].state.100b
jnz m7 :выводим на экран строку
mov ah.9
mov dx.di
int 21h ml: add di. type constant
emp di ,s_tab.last_off
jb m6

В этой программе показаны основные приемы работы с неупорядоченной таблицей. Усложнить данную программу можно, например, дополнив набор сведений о каждой константе информацией о ее длине. Далее можно попрактиковаться в этом вопросе, поставив себе задачу удалить из таблицы данные о нулевых константах (обоих типов — 0 и 0h) и вывести окончательное содержимое таблицы на экран. В качестве ключа для доступа к ячейке таблицы можно использовать значение самой константы (размером 10 байт).
Обратите внимание на еще два момента, отраженные в этой программе.

  • Использование команды XLAT для классификации символов в качестве цифр и остальных символов (букв). Среди других кодов в таблице перекодировки особо выделен байт со значением Odh, который является первым байтом в паре OdOah. Как вы помните, эта пара вставляется редакторами ASCII-текстов для обозначения конца строки и перехода на другую строку.
  • Организация таблицы. Ей предшествует четырехбайтовый префикс, содержащий информацию о конце таблицы и первом свободном элементе таблицы. В целях оптимизации область памяти для буфера buf и таблицы перекодировки лучше выделять динамически и после анализа файла удалять.