Сложные структуры данных Массивы. Строки переменной длины. Перечисления. Множества. Записи. Структуры. Объединения. Списки. - презентация

1

2 Сложные структуры данных Массивы. Строки переменной длины. Перечисления. Множества. Записи. Структуры. Объединения. Списки.

3 Массивы - упорядоченные множества элементов одного типа, занимающих непрерывное пространство в памяти машины. Упорядоченность элементов массива определяет- ся набором целых чисел, называемых индекса- ми, которые связываются с каждым элементом массива и однозначно определяют его положе- ние среди остальных элементов этого массива.

4 X = {x ij : aib и cjd} x a,c x a,c+1 …x a,d-1 x a,d x a+1,c x a+1,c+1 …x a+1,d-1 x a+1,d …x ij … x b-1,c x b-1,c+1 …x b-1,d-1 x b-1,d x b,c x b,c+1 …x b,d-1 x b,d

5 Расположение в памяти По строкам: x a,c x a,c+1 … x a,d-1 x a,d x a+1,c x a+1,c+1 … x a+1,d-1 x a+1,d … x a+1,c x a+1,c+1 … x a+1,d-1 x a+1,d x b,c x b,c+1 … x b,d-1 x b,d По столбцам: x a,c x a+1,c … x b-1,c x b,c x a,c+1 x a+1,c+1 … x b-1,c+1 x b,c+1 … x a,d-1 x a+1,d-1 … x b-1,d-1 x b,d-1 x a,d x a+1,d … x b-1,d x b,d X+((i-a)*(d–c+1) + j-c)*Type X X+((j-c)*(b–a+1) + i-a)*Type X

6 Строки переменной длины Си String db Это строка С,0 Паскаль String db Len-1,Строка Паскаля Len = $ - String Произвольная длина Длину необходимо вычислять Длина не более 255 Длина всегда известна без вычислений

7 Перечислимые типы данных Azb enum a,b,c,d,e,f,g,h,i,j,k,l,n,m,o,p,q,r,s,t,v,u,w,x,y,z ; a=0, b=1, …, z=25 Azb enum a=61h,b,c,… ; a=61h, b=62h, … moval,azb; al=31 Число бит, необходимых для представления множества, с перечисленным числом компонент

8 Множество –совокупность элементов, обладающих общим для них характеристическим свойством. –конечная упорядоченная совокупность элементов, т.е. каждому элементу поставлено в соответствие натуральное число, являющееся номером элемента множества. Множество можно моделировать набором бит в количестве равном числу элементов множества, когда значение i-ого бита отвечает наличию или отсутствию i–ого элемента в множестве. Для множества мощностью n требуется n/8+1 байт

9 Setofmacroname,pw,x rr =pw/8 if pw mod 8 ne 0 rr=rr+1 endif if rr eq 1 namelabelbyte elseif rr eq 2 namelabelword elseif rr le 4 namelabeldword elseif rr le 8 namelabelqword else Выделение места для размещения множества

10 .err "Не могу создать множество такого размера exitm endif kk=0 while kk lt rr shablon=0 irpi, if i/8 eq kk shablon=shablon or (1 shl (i mod 8)) endif endm dbshablon kk=kk+1 endm endm

11 Сегмент данных. data Alphabet enum A,B,C,D,E,F,G,H,I,J,K,L,N,M,O,P,Q,R,S,T,V,U,W,X,Y,Z SETOF VOWELS,Alphabet, SETOF CONSONANTS,Alphabet, Сегмент команд. codejnc short no main procbeepspkr mov no:.exit0 mov ds,ax mainendp inmn VOWELS,B endmain

12 Проверка присутствия элемента в множестве Inmnmacro name,k ;; Результат в fc ifndef.errИмя &name не определено exitm elseifndef.errИмя &k не определено exitm endif ifk gt (type name)*8 clc exitm endif push ax push bx mov ax,k ror ax,3 shr ah,5 ;; ah= номер бита, ;; al= номер байта mov bl,al xor bh,bh mov bl,byte ptr name[bx] shr ax,8 bts bx,ax pop bx pop ax endm

13 Вспомогательный макрос beepspkrmacrotimes:= push ax push dx mov ah,2 mov dl,7 rept times int21h endm pop dx pop ax endm

14 Записи -наборы групп битовых полей внутри байта, слова или двойного слова. Формат описания шаблона: Имя_шаблона RECORD айтем[,айтем…] Например: День Месяц Год Имя:длина[=значение по умолчанию] Date_format record day:5=1,month:4=1,year:7=0 Константа равная сдвигу поля от правого края 0711

15 Описание переменных типа запись Test_dateDate_format MillenniumDate_format YesterdayDate_format {year =4,month=4} Операторы работы с записями Mask имя_поля mov ax,mask year ; ax = 007fh Width имя_поля mov ax,width month ; ax = 4 Getfild getfild month bl,test_date Setfild and test_date,not mask month mov bx,6 setfild month test_date,6 movax,test_date andax,mask month shrax,month And test_date,not mask month Or test_date,6 shl month

16 Структуры -совокупности переменных различного типа. Формат описания шаблона структуры: Имя_шаблонаstruc Описатель переменной [… Описатель переменной] Имя_шаблонаends Например: Complexstruc Redd0. Imdd0. Complexends Имена переменных – константы, характеризующие расстояние поля от начала структуры в байтах Mov ax,type complex.re ; ax = 4 Mov ax,type complex ; ax = 8

17 Описание переменных формата структура Cnulcomplex Cedcomplex Cicomplex{im=1.0} Carraycomplex10 dup Доступ к полям структуры Прямая адресация Mov eax,Cnul.Re mov Cnul.Im,eax Косвенная адресация Mov bx,offset Ci Mov eax,[bx].Im

18 Объединения -наложение переменных различного типа. Формат описания шаблона объединения: Имя_шаблонаUnion описатель переменной [… описатель переменной] Имя_шаблонаends Правила работы те же, что и со структурами Другой способ – использование директивы Имя LABELтип

19 Списки -совокупность элементов типа структура, расположенных в произвольных местах памяти, связанных друг с другом через поля связи – переменные в которых хранятся ссылки (адреса) на следующий элемент. Последний элемент списка (не связанный с другими) хранит в таком поле пустую ссылку, называемую nil. Ссылка на первый элемент списка хранится в переменной, которую называют указателем на вершину списка.

20 Примерный формат элемента списка (aitem). fildsstruc fild1dw? … fildsends Aitemstruc list filds next dw ? Aitemends

21 Пример устройства «диспетчера» кучи.model small.386 nil = -1 Heap_size = 64*1024 fildsstruc fild1db8 dup(?) fild2db? fildsends aitemstruc listfilds nextdw? aitemends

22 Пример устройства «диспетчера» кучи.data StatusdbHeap_size/8 dup(0) topdw? str1db'String 1' str2db'String 2' str3db'String 3'.stack256 Heapsegmentpara Htop dbHeap_size dup(?); Куча Heapends.code

23 Создание нового элемента списка newmacrosize ifndefHeap.err exitm elseifndefStatus.err exitm endif mov ax,size; Размер искомого свободного участка call find endm

24 Удаление элемента списка Delitemacroadr,size mov bx,adr ; Адрес освобождаемой памяти в bx mov cx,size ; Размер освобождаемой области callclear endm Startmacro assumees:Heap movds,ax movax,Heap moves,ax xorax,ax endm

25 Сохранение и загрузка регистров SaveReg macro r1,r2,r3,r4,r5,r6,r7,r8,r9 ifnb push r1 SaveRegr2,r3,r4,r5,r6,r7,r8,r9 endif endm LoadReg macro r1,r2,r3,r4,r5,r6,r7,r8,r9 irp k, ifnb pop k endif endm endm

26 Основная программа mainproc.Start new%type aitem ; Найти подходящую область памяти для ; размещения элемента списка movtop,ax ; Указатель на вершину списка ; Первый элемент movbx,ax movcx,8 leasi,str1 leadi,[bx].list.fild1 repmovsb ;заполнение поля fild1 первого элемента new%type aitem moves:[bx].next,ax; адрес второго элемента moves:[bx].list.fild2,'$'

27 Создание 2 и 3 элементов movbx,ax movcx,8 leasi,str2 leadi,[bx].list.fild1 repmovsb ;заполнение поля fild1 второго элемента new%type aitem moves:[bx].next,ax ; адрес третьего элемента moves:[bx].list.fild2,'$' movbx,ax movcx,8 leasi,str3 leadi,[bx].list.fild1 repmovsb ;заполнение поля fild1 третьего элемента moves:[bx].next,nil ; конец списка moves:[bx].list.fild2,'$'

28 Удаление элемента и печать списка movbx,top delite es:[bx].next,%type aitem movbx,top movdi,es:[bx].next movax,es:[di].next moves:[bx].next,ax movbx,top ; Адрес текущего элемента списка cont: cmpbx,nil jzfin ; достигнут конец списка leadx,[bx].list.fild1 pushds pushes popds movah,09h int21h ;Печать тестового поля текущего элемента popds movbx,es:[bx].next jmpcont fin:.exit0 mainendp

29 Процедура поиска места в куче findproc ; ax - размер требующейся памяти в байтах SaveReg bx,cx,dx movcx,Heap_size/8 ; кол-во байт под статус movbx,0 pushax; сохранить объем памяти в стеке m0:cmpstatus[bx],0ffh; проверка на все единицы jznext1 movdl,1 ; 1 в левый бит m7:teststatus[bx],dl ; проверка бита jzm1 popax; текущий бит равен 1 - заново pushax jmpshort m2 m1:decax; найден еще один нулевой бит jzyes; найден нужный объем памяти m2:shldl,1; маска для следующего бита jzm3; нужно перейти к новому байту jmpm7

30 Процедура поиска места в куче next1: popax ; восстановление размера pushax m3:incbx ; увеличение номера байта loopm0 ; цикл по всем байтам jzno yes:shlbx,3 ; вычисление номера последнего бита popcx ; считан размер m4:incbx; добавить сдвиг внутри байта shrdl,1 jnzm4 subbx,cx ; номер первого бита поля movax,bx pusha shrbx,3 ; номер байт andax,07h ; и еще сдвиг на несколько бит movah,1 pushcx movcl,al shlah,cl ; сдвиг маски в позицию первого бита

31 Заполнение массива Status popcx m6: orstatus[bx],ah ; заполнение 1 маски отводимого поля deccx jzm5 shlah,1 jnzm6 incbx movah,1 jmpm6 no:movax,-1 m5:LoadRegbx,cx,dx,ax ret findendp

32 Процедура освобождения памяти clearproc SaveRegax,dx movax,bx shrbx,3 ; номер байта andax,07h ; и еще сдвиг на несколько бит movah,0feh pushcx movcl,al rolah,cl ; сдвиг маски в позицию первого бита popcx m16: and status[bx],ah ; заполнение 1 маски отводимого поля deccx jzm15 rolah,1 cmpah,0feh jnzm16 incbx jmpm16 m15: LoadReg ax,dx ret clear endp endmain РезультатРезультат: