Базы данных
<<  Данные собраны Символьный тип данных  >>
Сложные структуры данных
Сложные структуры данных
Массивы
Массивы
X = {xij: a
X = {xij: a
Расположение в памяти
Расположение в памяти
Строки переменной длины
Строки переменной длины
Перечислимые типы данных
Перечислимые типы данных
Множество
Множество
Setof macro name,pw,x rr=pw/8 if pw mod 8 ne 0 rr=rr+1 endif if rr eq
Setof macro name,pw,x rr=pw/8 if pw mod 8 ne 0 rr=rr+1 endif if rr eq
.err "Не могу создать множество такого размера“ exitm endif kk=0 while
.err "Не могу создать множество такого размера“ exitm endif kk=0 while
Сегмент данных
Сегмент данных
Проверка присутствия элемента в множестве
Проверка присутствия элемента в множестве
Вспомогательный макрос
Вспомогательный макрос
Записи
Записи
Описание переменных типа запись
Описание переменных типа запись
Структуры
Структуры
Описание переменных формата структура
Описание переменных формата структура
Объединения
Объединения
Списки
Списки
Примерный формат элемента списка (aitem)
Примерный формат элемента списка (aitem)
Пример устройства «диспетчера» кучи
Пример устройства «диспетчера» кучи
Пример устройства «диспетчера» кучи
Пример устройства «диспетчера» кучи
Создание нового элемента списка
Создание нового элемента списка
Удаление элемента списка
Удаление элемента списка
Сохранение и загрузка регистров
Сохранение и загрузка регистров
Основная программа
Основная программа
Создание 2 и 3 элементов
Создание 2 и 3 элементов
Удаление элемента и печать списка
Удаление элемента и печать списка
Процедура поиска места в куче
Процедура поиска места в куче
Процедура поиска места в куче
Процедура поиска места в куче
Заполнение массива Status
Заполнение массива Status
Процедура освобождения памяти
Процедура освобождения памяти

Презентация на тему: «Сложные структуры данных». Автор: KOROTIN. Файл: «Сложные структуры данных.ppt». Размер zip-архива: 65 КБ.

Сложные структуры данных

содержание презентации «Сложные структуры данных.ppt»
СлайдТекст
1 Сложные структуры данных

Сложные структуры данных

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

2 Массивы

Массивы

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

3 X = {xij: a

X = {xij: a

i?b и c?j?d}

xa,c xa,c+1 … xa,d-1 xa,d xa+1,c xa+1,c+1 … xa+1,d-1 xa+1,d … xij … xb-1,c xb-1,c+1 … xb-1,d-1 xb-1,d xb,c xb,c+1 … xb,d-1 xb,d

4 Расположение в памяти

Расположение в памяти

Быстый последний индекс

Быстрый первый индекс

По строкам: xa,c xa,c+1 … xa,d-1 xa,d xa+1,c xa+1,c+1 … xa+1,d-1 xa+1,d … xa+1,c xa+1,c+1 … xa+1,d-1 xa+1,d xb,c xb,c+1 … xb,d-1 xb,d По столбцам: xa,c xa+1,c … xb-1,c xb,c xa,c+1 xa+1,c+1 … xb-1,c+1 xb,c+1 … xa,d-1 xa+1,d-1 … xb-1,d-1 xb,d-1 xa,d xa+1,d … xb-1,d xb,d

X+((i-a)*(d–c+1) + j-c)*Type X

X+((j-c)*(b–a+1) + i-a)*Type X

5 Строки переменной длины

Строки переменной длины

Си String db ‘Это строка С’,0 Паскаль String db Len-1,‘Строка Паскаля’ Len = $ - String

Произвольная длина Длину необходимо вычислять

Длина не более 255 Длина всегда известна без вычислений

6 Перечислимые типы данных

Перечислимые типы данных

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, … mov al,azb ; al=31

Число бит, необходимых для представления множества, с перечисленным числом компонент

7 Множество

Множество

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

8 Setof macro name,pw,x rr=pw/8 if pw mod 8 ne 0 rr=rr+1 endif if rr eq

Setof macro name,pw,x rr=pw/8 if pw mod 8 ne 0 rr=rr+1 endif if rr eq

1 name label byte elseif rr eq 2 name label word elseif rr le 4 name label dword elseif rr le 8 name label qword else

Выделение места для размещения множества

9 .err "Не могу создать множество такого размера“ exitm endif kk=0 while

.err "Не могу создать множество такого размера“ exitm endif kk=0 while

kk lt rr shablon=0 irp i,<x> if i/8 eq kk shablon=shablon or (1 shl (i mod 8)) endif endm db shablon kk=kk+1 endm endm

10 Сегмент данных

Сегмент данных

Сегмент команд

.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,<a,e,i,j,o,u> SETOF CONSONANTS,Alphabet,<b,c,d,f,g,h,k,l,m,n,p,q,r,s,t,v,w,x,y,z>

.code jnc short no main proc beepspkr mov ax,@data no: .exit 0 mov ds,ax main endp inmn VOWELS,B end main

11 Проверка присутствия элемента в множестве

Проверка присутствия элемента в множестве

Inmn macro name,k ;; Результат в fc ifndef <name> .err ‘Имя &name не определено‘ exitm elseifndef <k> .err ‘Имя &k не определено‘ exitm endif if k 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

12 Вспомогательный макрос

Вспомогательный макрос

beepspkr macro times:=<1> push ax push dx mov ah,2 mov dl,7 rept times int 21h endm pop dx pop ax endm

13 Записи

Записи

наборы групп битовых полей внутри байта, слова или двойного слова. Формат описания шаблона: Имя_шаблона RECORD айтем[,айтем…] Например: День Месяц Год

Date_format record day:5=1,month:4=1,year:7=0

Имя:длина[=значение по умолчанию]

Константа равная сдвигу поля от правого края

15

14

13

12

11

11

10

9

8

7

7

6

5

4

3

2

1

0

0

14 Описание переменных типа запись

Описание переменных типа запись

Операторы работы с записями

mov ax,test_date and ax,mask month shr ax,month

And test_date,not mask month Or test_date,6 shl month

Test_date Date_format <7,5,4> Millennium Date_format <> Yesterday Date_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

15 Структуры

Структуры

Mov ax,type complex.re ; ax = 4 Mov ax,type complex ; ax = 8

совокупности переменных различного типа. Формат описания шаблона структуры: Имя_шаблона struc Описатель переменной [ … Описатель переменной] Имя_шаблона ends Например: Complex struc Re dd 0. Im dd 0. Complex ends

Имена переменных – константы, характеризующие расстояние поля от начала структуры в байтах

16 Описание переменных формата структура

Описание переменных формата структура

Доступ к полям структуры

Cnul complex <> Ced complex <1.,> Ci complex {im=1.0} Carray complex 10 dup <?,?>

Прямая адресация Mov eax,Cnul.Re mov Cnul.Im,eax

Косвенная адресация Mov bx,offset Ci Mov eax,[bx].Im

17 Объединения

Объединения

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

18 Списки

Списки

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

19 Примерный формат элемента списка (aitem)

Примерный формат элемента списка (aitem)

filds struc fild1 dw ? … filds ends

Aitem struc list filds <> next dw ? Aitem ends

20 Пример устройства «диспетчера» кучи

Пример устройства «диспетчера» кучи

.model small .386 nil = -1 Heap_size = 64*1024 filds struc fild1 db 8 dup(?) fild2 db ? filds ends aitem struc list filds <> next dw ? aitem ends

21 Пример устройства «диспетчера» кучи

Пример устройства «диспетчера» кучи

.data Status db Heap_size/8 dup(0) top dw ? str1 db 'String 1' str2 db 'String 2' str3 db 'String 3' .stack 256 Heap segment para Htop db Heap_size dup(?) ; Куча Heap ends .code

22 Создание нового элемента списка

Создание нового элемента списка

new macro size ifndef Heap .err exitm elseifndef Status .err exitm endif mov ax,size ; Размер искомого свободного участка call find endm

23 Удаление элемента списка

Удаление элемента списка

Delite macro adr,size mov bx,adr ; Адрес освобождаемой памяти в bx mov cx,size ; Размер освобождаемой области call clear endm Start macro assume es:Heap mov ax,@data mov ds,ax mov ax,Heap mov es,ax xor ax,ax endm

24 Сохранение и загрузка регистров

Сохранение и загрузка регистров

SaveReg macro r1,r2,r3,r4,r5,r6,r7,r8,r9 ifnb <r1> push r1 SaveReg r2,r3,r4,r5,r6,r7,r8,r9 endif endm LoadReg macro r1,r2,r3,r4,r5,r6,r7,r8,r9 irp k,<r9,r8,r7,r6,r5,r4,r3,r2,r1> ifnb <k> pop k endif endm endm

25 Основная программа

Основная программа

main proc .Start new %type aitem ; Найти подходящую область памяти для ; размещения элемента списка mov top,ax ; Указатель на вершину списка ; Первый элемент mov bx,ax mov cx,8 lea si,str1 lea di,[bx].list.fild1 rep movsb ;заполнение поля fild1 первого элемента new %type aitem mov es:[bx].next,ax ; адрес второго элемента mov es:[bx].list.fild2,'$'

26 Создание 2 и 3 элементов

Создание 2 и 3 элементов

Mov bx,ax mov cx,8 lea si,str2 lea di,[bx].List.Fild1 rep movsb ;заполнение поля fild1 второго элемента new %type aitem mov es:[bx].Next,ax ; адрес третьего элемента mov es:[bx].List.Fild2,'$' mov bx,ax mov cx,8 lea si,str3 lea di,[bx].List.Fild1 rep movsb ;заполнение поля fild1 третьего элемента mov es:[bx].Next,nil ; конец списка mov es:[bx].List.Fild2,'$'

27 Удаление элемента и печать списка

Удаление элемента и печать списка

mov bx,top delite es:[bx].next,%type aitem mov bx,top mov di,es:[bx].next mov ax,es:[di].next mov es:[bx].next,ax mov bx,top ; Адрес текущего элемента списка cont: cmp bx,nil jz fin ; достигнут конец списка lea dx,[bx].list.fild1 push ds push es pop ds mov ah,09h int 21h ;Печать тестового поля текущего элемента pop ds mov bx,es:[bx].next jmp cont fin: .exit 0 main endp

28 Процедура поиска места в куче

Процедура поиска места в куче

Find proc ; ax - размер требующейся памяти в байтах savereg bx,cx,dx mov cx,heap_size/8 ; кол-во байт под статус mov bx,0 push ax ; сохранить объем памяти в стеке m0: cmp status[bx],0ffh ; проверка на все единицы jz next1 mov dl,1 ; 1 в левый бит m7: test status[bx],dl ; проверка бита jz m1 pop ax ; текущий бит равен 1 - заново push ax jmp short m2 m1: dec ax ; найден еще один нулевой бит jz yes ; найден нужный объем памяти m2: shl dl,1 ; маска для следующего бита jz m3 ; нужно перейти к новому байту jmp m7

29 Процедура поиска места в куче

Процедура поиска места в куче

Next1: pop ax ; восстановление размера push ax m3: inc bx ; увеличение номера байта loop m0 ; цикл по всем байтам jz no yes: shl bx,3 ; вычисление номера последнего бита pop cx ; считан размер m4: inc bx ; добавить сдвиг внутри байта shr dl,1 jnz m4 sub bx,cx ; номер первого бита поля mov ax,bx push a shr bx,3 ; номер байт and ax,07h ; и еще сдвиг на несколько бит mov ah,1 push cx mov cl,al shl ah,cl ; сдвиг маски в позицию первого бита

30 Заполнение массива Status

Заполнение массива Status

Pop cx m6: or status[bx],ah ; заполнение 1 маски отводимого поля dec cx jz m5 shl ah,1 jnz m6 inc bx mov ah,1 jmp m6 no: mov ax,-1 m5: loadreg bx,cx,dx,ax ret find endp

31 Процедура освобождения памяти

Процедура освобождения памяти

Результат:

Clear proc savereg ax,dx mov ax,bx shr bx,3 ; номер байта and ax,07h ; и еще сдвиг на несколько бит mov ah,0feh push cx mov cl,al rol ah,cl ; сдвиг маски в позицию первого бита pop cx m16: and status[bx],ah ; заполнение 1 маски отводимого поля dec cx jz m15 rol ah,1 cmp ah,0feh jnz m16 inc bx jmp m16 m15: loadreg ax,dx ret clear endp end main

«Сложные структуры данных»
http://900igr.net/prezentacija/informatika/slozhnye-struktury-dannykh-241794.html
cсылка на страницу

Базы данных

19 презентаций о базах данных
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Базы данных > Сложные структуры данных