Разделы презентаций

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

Содержание

Литература Вирт Н. Алгоритмы+структуры данных = программы: Пер. с англ.-М.Мир,1985.-406 с., ил. Вирт Н. Алгоритмы и структуры данных: Пер. с англ.-М.Мир,1989.-360 с., ил. Кнут Д. Искусство программирования для ЭВМ. В семи

Слайды и текст этой презентации

Слайд 1Структуры

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

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

с., ил.
Вирт Н. Алгоритмы и структуры данных: Пер. с

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

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

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

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

характеризуется:

множеством допустимых значений данной структуры;
набором допустимых операций;
характером организованности.
Введение Структура данных – общее свойство информационного объекта, с которым взаимодействует та или иная программа.

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

представлена в виде двойки
где D – конечное множество элементов,

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

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

Слайд 5 Введение
Основные виды (типы) структур данных:
Множество – конечная

совокупность элементов, у которой R=∅.
Последовательность – абстрактная структура, у которой

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

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

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

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


ВведениеМатрица – структура, у которой множество R состоит из двух отношений линейного порядка.Дерево – множество R

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

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


Классификация СД

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

Слайд 8 Введение






Введение

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

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

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

Слайд 10 Категории типов

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


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

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

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

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

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

Слайд 12 Встроенные типы данных

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


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




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

Слайд 13 Встроенные типы данных
Тип CHARACTER (или CHAR)

в разных языках - это
либо набор печатных символов из

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



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

Слайд 14 Уточняемые типы данных
Type T = min..max;

ПРИМЕРЫ
Type year =

(1900 .. 2001);
digit = (‘0’

..’9’);

Var y : year;
d : digit;

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

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


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






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

Слайд 16 Перечисляемые типы данных
ПРИМЕРЫ:
Type color =

(red, yellow, green);
destination = (hell, purgatory,


heaven);
Var c: color;
d: destination;
…
C := red;
D := heaven;
Перечисляемые типы данных ПРИМЕРЫ: Type color = (red, yellow, green);

Слайд 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}
Массивы Type t = array [Ti] of To ;Type row = array [1.. 5]

Слайд 18 Массивы
: array [n..k] of < тип >;









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

Слайд 19 Массивы
var m1:array[-2..2] of real;







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

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

вектором, определяется по формуле:

ByteSise = ( k - n

+ 1 ) * Sizeof (тип)


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

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

вектора плюс смещение к данному элементу.
Смещение i-ого элемента вектора

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

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

время доступа,
(A0 = @Имя - n*Sizeof(тип) )
обеспечивает проверку

правильности обращения (верхняя и нижняя границы массива).
Массивы Информация, содержащаяся в дескрипторе вектора, должна позволять, сократить время доступа,(A0 = @Имя -

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

< Тип >



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

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

формуле :
ByteSize = (k1-n1+1)*(k2-n2+1) *SizeOf(Тип)
Адресом массива является адрес

первого байта начального компонента массива.




Массивы Количество байтов памяти, занятых двумерным массивом, определяется по формуле : ByteSize = (k1-n1+1)*(k2-n2+1)

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

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

@mas + ByteNumber
Массивы Смещение к элементу массиваMas[i1,i2] определяется по формуле: ByteNumber = [(i1-n1)*(k2-n2+1)+(i2-n2)] *SizeOf(Тип)

Слайд 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
Массивы Например: var Mas : Array [3..5] [7..8] of Word; Этот массив будет занимать

Слайд 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(Тип)
Массивы для двумерного массива 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)
где Dm зависит от способа размещения массива. При размещении по строкам:
D(m)=[E(m+1)-B(m+1)+1]*D(m+1),
где m = n-1,...,1 и D(n)=1
Массивы для массива произвольной размерности: 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)] +

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

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

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

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

адрес массива - Addr[I(1),I(2),...,I(n)];
число измерений в массиве - n;


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

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

массива любой мерности формируется набор дескрипторов: основного и несколько уровней

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

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


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

LinkedList, ArrayList
Массивы В Java имеется большоеколичество классов и интерфейсов для массивов и массивоподобных структур: Arrays, Vector,

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

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

Employee.
ArrayList staff = new ArrayList();
Массивы В JDK 5.0 ArrayList был преобразован в универсальный класс с параметром типа. Массив, предназначенный

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

данных.
type complex = record re: real;

im: real
end ;
var x: complex;
C:
struct complex { float re;
float im;
}
struct complex x;
ЗаписиЗапись - конечное упорядоченное множество полей, характеризующихся различным типом данных. type complex = record re: real;

Слайд 35 Записи
struct { float re;

float im;

} x, y;
x=y; …

struct { float r;
float i;
} z;


Записи struct { float re; float im;

Слайд 36 Записи
var rec:record

num :byte; { номер студента }

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



Записи var rec:record num :byte; { номер студента

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

памяти






АВТФ

8B50

Записи Представление в виде последовательности полей, занимающих непрерывную область памяти АВТФ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 - адрес данного типа множество.

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

Слайд 42 Множества
Число байтов, выделяемых для данных типа множество, вычисляется по

формуле:
ByteSize = (max div 8)-(min div 8) + 1,


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

Слайд 43 Множества

Например, S : set of byte;
S:=[15,19];


Содержимое памяти при этом будет следующим:
@S+0 - 00000000
@S+1 - 10000000
@S+2

- 00001000
. . . . . .
@S+31 – 0000000

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

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

адреса.
Подобно тому, как зная машинный адрес можно обратиться к

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

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


Os, Finder
библиотеки Паскаля
Исходный текст
Объектный код
Область динамического распределения
Рекурсивный

стек



Heap

Динамическая память ( указатели )Статическое распределение памятиДинамическое распределение памяти Os, Finder библиотеки ПаскаляИсходный текстОбъектный кодОбласть

Слайд 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;










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

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

Heap для переменной, на которую указывает p
Dispose ( p )-освободить

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

New ( p2 );

p2^ := 53;






p1

p1^

10

p2

p2^

53

p1

p2

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

Слайд 48Указатели

p1 := p2;



Dispose ( p1 );



Dispose (

p2 );








p1

p2

10

53


p1

p2



p1

p2

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

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

Type mas = array [ 1..n] of integer;

Var p1,p2,p3 : ^mas;
i : integer;


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

Слайд 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;

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

Слайд 51Указатели
….

{ обмен данными }
p3 :=

p1;
p1:= p2;
p2 := p3;
...
Dispose ( p1 );
...
Указатели …. { обмен данными }

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

Презентация Мы - против наркотиков Презентация Мы - против наркотиков 353
Архитектура древней Греции Архитектура древней Греции 189
Химия в повседневной жизни человека Химия в повседневной жизни человека 239
Личность Личность 312
" Пионербол" 192
Литература 10-16 веков Литература 10-16 веков 231
английский 6 класс 14.04.docx английский 6 класс 14.04.docx 121
Квадрат и ку б Квадрат и ку б 148
Охрана российских изобретений за рубежом Охрана российских изобретений за рубежом 274
Нумерация чисел в пределах 1000. Закрепление Нумерация чисел в пределах 1000. Закрепление 183
ТЕМА 3: ПРИРОДНО-РЕСУРСНЫЙ ПОТЕНЦИАЛ МИРОВОГО ХОЗЯЙСТВА ТЕМА 3: ПРИРОДНО-РЕСУРСНЫЙ ПОТЕНЦИАЛ МИРОВОГО ХОЗЯЙСТВА 340
УВАЖАЕМЫЕ ПОСЕТИТЕЛИ! В связи с введением на территории Вологодской области УВАЖАЕМЫЕ ПОСЕТИТЕЛИ! В связи с введением на территории Вологодской области 161
Проксимальный  — расположенный ближе к центру тела или к его медианной Проксимальный  — расположенный ближе к центру тела или к его медианной 308
Производственные технологии. (Промышленные технологии. Технологии сельского Производственные технологии. (Промышленные технологии. Технологии сельского 262
"Т?уелсіздікті? ?асиетті белгілері" атты сынып са?аты 253
Введение в психотерапию Введение в психотерапию 271
Документооборот Документооборот 622
ЦИВИЛИЗАЦИЯ ИНКОВ ЦИВИЛИЗАЦИЯ ИНКОВ 251
Перечень планируемых результатов по русскому языку Перечень планируемых результатов по русскому языку 248
Lec2.ppt Lec2.ppt 234

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.

Для правообладателей

Яндекс.Метрика