Структуры обработки данных

Сентябрь 2, 2022

Главная
Алгебра
Структуры обработки данных

Содержание

2. Литература Вирт Н. Алгоритмы+структуры данных = программы: Пер. с англ.-М.Мир,1985.-406 с., ил. Вирт Н. Алгоритмы и
3. Введение Структура данных – общее свойство информационного объекта, с которым взаимодействует та или иная программа. Это
4. Введение Любая структура на абстрактном уровне может быть представлена в виде двойки где D – конечное
5. Введение Основные виды (типы) структур данных: Множество – конечная совокупность элементов, у которой R=∅. Последовательность –
6. Введение Матрица – структура, у которой множество R состоит из двух отношений линейного порядка. Дерево –
7. Введение Вырожденные (простейшие) структуры данных называются также типами данных. Различают следующие уровни описания данных: абстрактный (математический)
8. Введение
9. Категории типов данных Встроенные типы данных, т.е. типы, предопределенные в языке программирования или языке баз данных.
10. Категории типов Указательные типы дают возможность работы с типизированными множествами абстрактных адресов переменных, содержащих значения некоторого
11. Встроенные типы данных В современных компьютерах к таким "машинным" типам относятся целые числа разного размера (2-8
12. Встроенные типы данных числа с плавающей точкой одинарной и двойной точности ( 4 и 8 байт
13. Встроенные типы данных Тип CHARACTER (или CHAR) в разных языках - это либо набор печатных символов
14. Уточняемые типы данных Type T = min..max; ПРИМЕРЫ Type year = (1900 .. 2001); digit =
15. Перечисляемые типы данных TYPE T = (C1,C2,...,Cn) где Т — идентификатор нового типа, Ci — идентификаторы
16. Перечисляемые типы данных ПРИМЕРЫ: Type color = (red, yellow, green); destination = (hell, purgatory, heaven); Var
17. Массивы Type t = array [Ti] of To ; Type row = array [1.. 5] of
18. Массивы : array [n..k] of ;
19. Массивы var m1:array[-2..2] of real;
20. Массивы Количество байтов непрерывной области памяти, занятых одновременно вектором, определяется по формуле: ByteSise = ( k
21. Массивы Обращение к i-тому элементу вектора выполняется по адресу вектора плюс смещение к данному элементу. Смещение
22. Массивы Информация, содержащаяся в дескрипторе вектора, должна позволять, сократить время доступа, (A0 = @Имя - n*Sizeof(тип)
23. Массивы (многомерные) Var Mas2D : Array [n1..k1 , n2..k2] of
24. Массивы Количество байтов памяти, занятых двумерным массивом, определяется по формуле : ByteSize = (k1-n1+1)*(k2-n2+1) *SizeOf(Тип) Адресом
25. Массивы Смещение к элементу массива Mas[i1,i2] определяется по формуле: ByteNumber = [(i1-n1)*(k2-n2+1)+(i2-n2)] *SizeOf(Тип) его адрес :
26. Массивы Например: var Mas : Array [3..5] [7..8] of Word; Этот массив будет занимать в памяти:
27. Массивы для двумерного массива c границами изменения индексов: [B(1)..E(1)][B(2)..E(2)], размещенного в памяти по строкам, адрес элемента
28. Массивы для массива произвольной размерности: Mas[B(1)..E(2)][B(2)..E(2)]...[B(n)..E(n)] получим: Addr[I(1),I(2),...,I(n)]=Addr[B(1),B(2),...B(n)] + Sizeof(Тип)*∑ [B(m)*D(m)] + Sizeof(Тип)* ∑ [I(m)*D(m)] (m=1..n)
29. Массивы При вычислении адреса элемента наиболее сложным является вычисление третьей составляющей формулы, т.к. первые две не
30. Массивы Дескриптор массива, таким образом, содержит: начальный адрес массива - Addr[I(1),I(2),...,I(n)]; число измерений в массиве -
31. Массивы Представление массивов с помощью векторов Айлиффа Для массива любой мерности формируется набор дескрипторов: основного и
32. Массивы В Java имеется большое количество классов и интерфейсов для массивов и массивоподобных структур: Arrays, Vector,
33. Массивы В JDK 5.0 ArrayList был преобразован в универсальный класс с параметром типа. Массив, предназначенный для
34. Записи Запись - конечное упорядоченное множество полей, характеризующихся различным типом данных. type complex = record re:
35. Записи struct { float re; float im; } x, y; x=y; … struct { float r;
36. Записи var rec:record num :byte; { номер студента } name :string[20]; { Ф.И.О. } fac, group:string[7];
37. Записи Представление в виде последовательности полей, занимающих непрерывную область памяти АВТФ 8B50
38. Записи в виде связного списка с указателями на значения полей записи
39. Множества Множество - такая структура, которая представляет собой набор неповторяющихся данных одного и того же типа.
40. Множества Множество в памяти хранится как массив битов, в котором каждый бит указывает является ли элемент
41. Множества где @S - адрес данного типа множество.
42. Множества Число байтов, выделяемых для данных типа множество, вычисляется по формуле: ByteSize = (max div 8)-(min
43. Множества Например, S : set of byte; S:=[15,19]; Содержимое памяти при этом будет следующим: @S+0 -
44. Указатели Понятие указателя в языках программирования является абстракцией понятия машинного адреса. Подобно тому, как зная машинный
45. Динамическая память ( указатели ) Статическое распределение памяти Динамическое распределение памяти Os, Finder библиотеки Паскаля Исходный
46. Указатели Описание переменных типа указатель Type c = array [1..100] of real; Var p1 : ^integer
47. Указатели Процедуры работы с указателями: New ( p )- выделить память в Heap для переменной, на
48. Указатели p1 := p2; Dispose ( p1 ); Dispose ( p2 ); p1 p2 10 53
49. Указатели Обмен данными массивов Program DemoPointer; Const n=1000; Type mas = array [ 1..n] of integer;
50. Указатели begin New ( p1 ); New ( p2 ); for i :=1 to n do
52. Скачать презентацию

Слайд 2

Литература
Вирт Н. Алгоритмы+структуры данных = программы: Пер. с англ.-М.Мир,1985.-406 с.,

ил.
Вирт Н. Алгоритмы и структуры данных: Пер. с англ.-М.Мир,1989.-360 с., ил.
Кнут Д. Искусство программирования для ЭВМ. В семи томах. т.1. Основные алгоритмы. М.: Мир, 1976
Кнут Д. Искусство программирования для ЭВМ. В семи томах. т.3. Сортировка и поиск. М.: Мир, 1978
Ахо А., Хопкрофт,Д., Ульман Д. Структуры данных и алгоритмы. Вильямс, С-П, 2000

Слайд 3

Введение
Структура данных – общее свойство информационного объекта, с которым

взаимодействует та или иная программа. Это общее свойство характеризуется:
множеством допустимых значений данной структуры;
набором допустимых операций;
характером организованности.

Слайд 4

Введение
Любая структура на абстрактном уровне может быть представлена в

виде двойки
где D – конечное множество элементов, которые могут быть типами данных, либо структурами данных,
R – множество отношений, свойства которого определяют различные типы структур данных на абстрактном уровне.

Слайд 5

Введение
Основные виды (типы) структур данных:
Множество – конечная совокупность элементов,

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

Слайд 6

Введение
Матрица – структура, у которой множество R состоит из двух

отношений линейного порядка.
Дерево – множество R состоит из одного отношения иерархического порядка.
Граф – множество R состоит из одного отношения бинарного порядка.

Слайд 7

Введение
Вырожденные (простейшие) структуры данных называются также типами данных.
Различают следующие

уровни описания данных:
абстрактный (математический) уровень
логический уровень
физический уровень
Классификация СД

Слайд 8

Введение

Слайд 9

Категории типов данных
Встроенные типы данных, т.е. типы, предопределенные

в языке программирования или языке баз данных.
уточняемые типы данных
перечисляемый тип данных
конструируемый тип (составной)

Слайд 10

Категории типов

Указательные типы дают
возможность работы с
типизированными

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

Слайд 11

Встроенные типы данных
В современных компьютерах к таким "машинным" типам относятся

целые числа разного размера
(2-8 байтов)

Слайд 12

Встроенные типы данных

числа с плавающей точкой
одинарной и двойной

точности
( 4 и 8 байт соответственно)

Слайд 13

Встроенные типы данных
Тип CHARACTER (или CHAR) в разных языках

- это
либо набор печатных символов из алфавита, зафиксированного в описании языка (ASCII),
либо произвольная комбинация нулей и единиц, размещаемых в одном байте или 2 байтах

Слайд 14

Уточняемые типы данных
Type T = min..max;
ПРИМЕРЫ
Type year = (1900 ..

2001);
digit = (‘0’ ..’9’);
Var y : year;
d : digit;

Слайд 15

Перечисляемые типы данных
TYPE T = (C1,C2,...,Cn)
где Т —

идентификатор нового типа,
Ci — идентификаторы новых констант

Слайд 16

Перечисляемые типы данных
ПРИМЕРЫ:
Type color = (red, yellow,

green);
destination = (hell, purgatory,
heaven);
Var c: color;
d: destination;
…
C := red;
D := heaven;

Слайд 17

Массивы
Type t = array [Ti] of To ;
Type row =

array [1.. 5] of real;
Type card = array [1.. 80] of char;
Type alfa = array [0.. 15] of char;
…
Var x: row;
С:
int x[4]
int x[] = { 0, 2, 8, 22}

Слайд 18

Массивы
<Имя>: array [n..k] of < тип >;

Слайд 19

Массивы
var m1:array[-2..2] of real;

Слайд 20

Массивы
Количество байтов непрерывной области памяти, занятых одновременно вектором, определяется

по формуле:
ByteSise = ( k - n + 1 ) * Sizeof (тип)

Слайд 21

Массивы
Обращение к i-тому элементу вектора выполняется по адресу вектора плюс

смещение к данному элементу.
Смещение i-ого элемента вектора определяется по формуле:
ByteNumer = ( i- n ) * Sizeof (тип),
а адрес его:
@ ByteNumber = @ имя + ByteNumber.
где @ имя - адрес первого элемента вектора.

Слайд 22

Массивы
Информация, содержащаяся в дескрипторе вектора, должна позволять,
сократить время доступа,
(A0

= @Имя - n*Sizeof(тип) )
обеспечивает проверку правильности обращения (верхняя и нижняя границы массива).

Слайд 23

Массивы (многомерные)
Var Mas2D : Array [n1..k1 , n2..k2] of <

Тип >

Слайд 24

Массивы
Количество байтов памяти, занятых двумерным массивом, определяется по формуле :

ByteSize = (k1-n1+1)*(k2-n2+1) *SizeOf(Тип)
Адресом массива является адрес первого байта начального компонента массива.

Слайд 25

Массивы
Смещение к элементу массива
Mas[i1,i2] определяется по формуле:
ByteNumber =

[(i1-n1)*(k2-n2+1)+(i2-n2)] *SizeOf(Тип)
его адрес :
@ByteNumber = @mas + ByteNumber

Слайд 26

Массивы
Например:
var Mas : Array [3..5] [7..8] of Word;
Этот

массив будет занимать в памяти:
(5-3+1)*(8-7+1)*2=12 байт;
а адрес элемента Mas[4,8]:
@Mas+((4-3)*(8-7+1)+(8-7)*2 = @Mas+6

Слайд 27

Массивы
для двумерного массива c границами изменения индексов:
[B(1)..E(1)][B(2)..E(2)], размещенного

в памяти по строкам, адрес элемента с индексами [I(1),I(2)] может быть вычислен как:
Addr[I(1),I(2)] = Addr[B(1),B(2)] +
{ [I(1)-B(1)] * [E(2)-B(2)+1] + [I(2)-B(2)] } *SizeOf(Тип)

Слайд 28

Массивы
для массива произвольной размерности: Mas[B(1)..E(2)][B(2)..E(2)]...[B(n)..E(n)] получим:
Addr[I(1),I(2),...,I(n)]=Addr[B(1),B(2),...B(n)]
+ Sizeof(Тип)*∑

[B(m)*D(m)] +
Sizeof(Тип)* ∑ [I(m)*D(m)]
(m=1..n)
где Dm зависит от способа размещения массива. При размещении по строкам:
D(m)=[E(m+1)-B(m+1)+1]*D(m+1),
где m = n-1,...,1 и D(n)=1

Слайд 29

Массивы
При вычислении адреса элемента наиболее сложным является вычисление третьей

составляющей формулы, т.к. первые две не зависят от индексов и могут быть вычислены заранее.
Для ускорения вычислений множители D(m) также могут быть вычислены заранее и сохраняться в дескрипторе массива

Слайд 30

Массивы
Дескриптор массива, таким образом, содержит:
начальный адрес массива -

Addr[I(1),I(2),...,I(n)];
число измерений в массиве - n;
постоянную составляющую формулы линеаризации (первые две составляющие формулы);
для каждого из n измерений массива:
значения граничных индексов - B(i), E(i);
множитель формулы линеаризации - D(i).

Слайд 31

Массивы
Представление массивов с помощью векторов Айлиффа
Для массива любой

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

Слайд 32

Массивы
В Java имеется большое
количество классов и интерфейсов
для массивов

и массивоподобных
структур:
Arrays, Vector, Collection, Map,
Hashtable, LinkedList, ArrayList

Слайд 33

Массивы
В JDK 5.0 ArrayList был преобразован в универсальный класс

с параметром типа.
Массив, предназначенный для хранения объектов Employee.
ArrayList staff = new ArrayList();

Слайд 34

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

type complex = record re: real;
im: real
end ;
var x: complex;
C:
struct complex { float re;
float im;
}
struct complex x;

Слайд 35

Записи
struct { float re;
float im;
} x, y;

x=y; …
struct { float r;
float i;
} z;

Слайд 36

Записи
var rec:record
num :byte; { номер студента }
name :string[20];

{ Ф.И.О. }
fac, group:string[7];
math,comp,lang:byte;{оценки}
end;

Слайд 37

Записи
Представление в виде последовательности полей, занимающих непрерывную область памяти

АВТФ

8B50

Слайд 38

Записи
в виде связного списка с указателями на значения полей

записи

Слайд 39

Множества
Множество - такая структура, которая
представляет собой набор
неповторяющихся

данных одного и того
же типа.
type T =set of To
Примеры
type bitset = set of (0..15);
type tapestatus = set of exception;
var B : bitset;
t : array [1.. 6] of tapestatus;

Слайд 40

Множества
Множество в памяти хранится как массив битов, в котором

каждый бит указывает является ли элемент принадлежащим объявленному множеству или нет.

Слайд 41

Множества

где @S - адрес данного типа множество.

Слайд 42

Множества
Число байтов, выделяемых для данных типа множество, вычисляется по формуле:

ByteSize = (max div 8)-(min div 8) + 1,
где max и min - верхняя и нижняя
границы базового типа данного
множества.
Номер байта для конкретного элемента Е вычисляется по формуле:
ByteNumber = (E div 8)-(min div 8),
номер бита внутри этого байта по
формуле: BitNumber = E mod 8

Слайд 43

Множества

Например, S : set of byte;
S:=[15,19];
Содержимое памяти

при этом будет следующим:
@S+0 - 00000000
@S+1 - 10000000
@S+2 - 00001000
. . . . . .
@S+31 – 0000000

Слайд 44

Указатели
Понятие указателя в языках программирования является абстракцией понятия машинного адреса.

Подобно тому, как зная машинный адрес можно обратиться к нужному элементу памяти, имея значение указателя, можно обратиться к соответствующей переменной.
var ipt : ^integer; cpt : ^char;
C:
int *ipt; char *cpt;

Слайд 45

Динамическая память ( указатели )
Статическое распределение памяти
Динамическое распределение памяти
Os,

Finder

библиотеки Паскаля

Исходный текст

Объектный код

Область динамического распределения

Рекурсивный стек

Heap

Слайд 46

Указатели
Описание переменных типа указатель
Type c = array [1..100] of real;
Var

p1 : ^integer ;
p2 : ^real ;
p3,p4 : ^c;
a, b : integer ;
p1 a
p2 b
p3
p4
p1 := nil ;.. p4 := nil; a := 5; b := 7;

Слайд 47

Указатели
Процедуры работы с указателями:
New ( p )- выделить память в Heap

для переменной, на которую указывает p
Dispose ( p )-освободить память в Heap, выделенную для переменной, на которую указывает p
Var p1, p2, p3: ^integer;
begin
New ( p1 );
p1^ := 10;
New ( p2 );
p2^ := 53;

p1^

p2^

Слайд 48

Указатели

p1 := p2;
Dispose ( p1 );
Dispose ( p2 );

Слайд 49

Указатели
Обмен данными массивов
Program DemoPointer;
Const n=1000;
Type mas = array

[ 1..n] of integer;
Var p1,p2,p3 : ^mas;
i : integer;

Слайд 50

Указатели

begin New ( p1 ); New ( p2 );

for i :=1 to n do
begin Write (‘Введи ’,i, ‘эл-т 1-го массива’ );
Readln (p1^[i]);
Write (‘Введи ’,i, ‘эл-т 2-го массива’ );
Readln (p2^[i])
end;

Структуры обработки данных

Содержание

Литература Вирт Н. Алгоритмы+структуры данных = программы: Пер. с англ.-М.Мир,1985.-406 с.,

Введение Структура данных – общее свойство информационного объекта, с которым

Введение Любая структура на абстрактном уровне может быть представлена в

Введение Основные виды (типы) структур данных:Множество – конечная совокупность элементов,

ВведениеМатрица – структура, у которой множество R состоит из двух

Введение Вырожденные (простейшие) структуры данных называются также типами данных.Различают следующие

Введение

Категории типов данных Встроенные типы данных, т.е. типы, предопределенные

Категории типов Указательные типы дают возможность работы с типизированными

Встроенные типы данных В современных компьютерах к таким "машинным" типам относятся

Встроенные типы данных числа с плавающей точкой одинарной и двойной

Встроенные типы данных Тип CHARACTER (или CHAR) в разных языках

Уточняемые типы данных Type T = min..max;ПРИМЕРЫType year = (1900 ..

Перечисляемые типы данных TYPE T = (C1,C2,...,Cn) где Т —

Перечисляемые типы данных ПРИМЕРЫ: Type color = (red, yellow,

Массивы Type t = array [Ti] of To ;Type row =

Массивы <Имя>: array [n..k] of < тип >;

Массивы var m1:array[-2..2] of real;

Массивы Количество байтов непрерывной области памяти, занятых одновременно вектором, определяется

Массивы Обращение к i-тому элементу вектора выполняется по адресу вектора плюс

Массивы Информация, содержащаяся в дескрипторе вектора, должна позволять, сократить время доступа,(A0

Массивы (многомерные) Var Mas2D : Array [n1..k1 , n2..k2] of <

Массивы Количество байтов памяти, занятых двумерным массивом, определяется по формуле :

Массивы Смещение к элементу массиваMas[i1,i2] определяется по формуле: ByteNumber =

Массивы Например: var Mas : Array [3..5] [7..8] of Word; Этот

Массивы для двумерного массива c границами изменения индексов: [B(1)..E(1)][B(2)..E(2)], размещенного

Массивы для массива произвольной размерности: Mas[B(1)..E(2)][B(2)..E(2)]...[B(n)..E(n)] получим: Addr[I(1),I(2),...,I(n)]=Addr[B(1),B(2),...B(n)] + Sizeof(Тип)*∑

Массивы При вычислении адреса элемента наиболее сложным является вычисление третьей

Массивы Дескриптор массива, таким образом, содержит: начальный адрес массива -

Массивы Представление массивов с помощью векторов Айлиффа Для массива любой

Массивы В Java имеется большоеколичество классов и интерфейсов для массивов

Массивы В JDK 5.0 ArrayList был преобразован в универсальный класс

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

Записи struct { float re; float im; } x, y;

Записи var rec:record num :byte; { номер студента } name :string[20];

Записи Представление в виде последовательности полей, занимающих непрерывную область памяти

Записи в виде связного списка с указателями на значения полей

Множества Множество - такая структура, которая представляет собой набор неповторяющихся

Множества Множество в памяти хранится как массив битов, в котором

Множества где @S - адрес данного типа множество.

Множества Число байтов, выделяемых для данных типа множество, вычисляется по формуле:

Множества Например, S : set of byte; S:=[15,19]; Содержимое памяти

Указатели Понятие указателя в языках программирования является абстракцией понятия машинного адреса.

Динамическая память ( указатели )Статическое распределение памятиДинамическое распределение памяти Os,

Указатели Описание переменных типа указательType c = array [1..100] of real;Var

УказателиПроцедуры работы с указателями:New ( p )- выделить память в Heap

Указатели p1 := p2;Dispose ( p1 );Dispose ( p2 );

УказателиОбмен данными массивов Program DemoPointer; Const n=1000; Type mas = array

Указатели begin New ( p1 ); New ( p2 );

Похожие презентации