Программирование
<<  Лекции по курсу «Программирование» Методическая разработка урока по физике  >>
Лекции по курсу «Программирование»
Лекции по курсу «Программирование»
Структуры данных и их классификация
Структуры данных и их классификация
Структуры данных и их классификация
Структуры данных и их классификация
Структуры данных и их классификация
Структуры данных и их классификация
Основные статические структуры данных
Основные статические структуры данных
Основные статические структуры данных
Основные статические структуры данных
Основные статические структуры данных
Основные статические структуры данных
Массивы
Массивы
Массивы
Массивы
Массивы
Массивы
Массивы
Массивы
Записи
Записи
Записи
Записи
Записи
Записи
Основные особенности полустатических структур
Основные особенности полустатических структур
Стеки
Стеки
Демонстрирующий принцип включения элементов в стек и исключения
Демонстрирующий принцип включения элементов в стек и исключения
Операции стека
Операции стека
Следующий пример поясняет реализацию операций создания, включения,
Следующий пример поясняет реализацию операций создания, включения,
Очереди
Очереди
Схематичное представление логической структуры очереди а) б) в) г) а)
Схематичное представление логической структуры очереди а) б) в) г) а)
Физическое представление очереди в памяти ПК
Физическое представление очереди в памяти ПК
Физическое представление очереди в памяти ПК
Физическое представление очереди в памяти ПК
Следующий пример поясняет простейшую реализацию операций создания,
Следующий пример поясняет простейшую реализацию операций создания,
Строки
Строки
Векторное представление строк
Векторное представление строк
Представление строк вектором переменной длины с признаком конца
Представление строк вектором переменной длины с признаком конца
Представление строк вектором переменной длины со счётчиком
Представление строк вектором переменной длины со счётчиком
?
?

Презентация: «Лекции по курсу «Программирование»». Автор: Shalin Aleksey. Файл: «Лекции по курсу «Программирование».ppt». Размер zip-архива: 206 КБ.

Лекции по курсу «Программирование»

содержание презентации «Лекции по курсу «Программирование».ppt»
СлайдТекст
1 Лекции по курсу «Программирование»

Лекции по курсу «Программирование»

Лекция 11. Структуры данных и их классификация. Основные статические и полустатические структуры данных.

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС

2 Структуры данных и их классификация

Структуры данных и их классификация

Под структурой данных в общем случае понимают множество элементов данных и множество связей между ними. ФИЗИЧЕСКОЙ структурой данных называется способ физического представления данных в памяти машины. ЛОГИЧЕСКОЙ структурой данных называется описание данных без учёта их представления устройствами-носителями информации.

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС

3 Структуры данных и их классификация

Структуры данных и их классификация

Общая классификация структур данных по нескольким признакам:

1. В зависимости от характера взаимного расположения элементов в памяти структуры данных можно разделить на структуры со СМЕЖНЫМ (или последовательным) распределением элементов в памяти и структуры со СВЯЗНЫМ распределением элементов в памяти. 2. По признаку изменчивости количества элементов и связей между ними различают структуры СТАТИЧЕСКИЕ (векторы, массивы, записи) ПОЛУСТАТИЧЕСКИЕ (стеки, очереди, строки) и ДИНАМИЧЕСКИЕ (списки, деревья, графы).

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС

4 Структуры данных и их классификация

Структуры данных и их классификация

Помимо этих общих операций для каждой структуры данных могут быть определены операции специфические, работающие только с данной структурой.

Операции над структурами данных:

Операция СОЗДАНИЯ – в общем случае выделение памяти для структуры данных; Операция УНИЧТОЖЕНИЯ - противоположна по своему действию операции создания; она помогает эффективно использовать память; Операция ДОСТУПА – обращение к данным структуры. Способ доступа - один из наиболее важных свойств, определяющих эффективность работы конкретной структуры; Операция ОБНОВЛЕНИЯ – изменение значения данных в структуре.

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС

5 Основные статические структуры данных

Основные статические структуры данных

Векторы

Логическое и физическое представления:

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

Физически элементы вектора размещаются в ячейках памяти, расположенных подряд. Необходимое число байтов памяти для хранения одного элемента вектора называется слотом.

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС

6 Основные статические структуры данных

Основные статические структуры данных

Векторы

Синтаксис описания вектора (PASCAL):

< Имя > : array [n..k] of < тип >; где n-номер первого элемента, k-номер последнего элемента. Представление в памяти вектора будет такое, как показано на рисунке далее.

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС

7 Основные статические структуры данных

Основные статические структуры данных

Векторы

Синтаксис описания вектора (PASCAL): (продолжение)

Здесь @Имя – адрес вектора, Sizeof(тип) – размер слота, (k-n)*Sizeof(тип) – смещение элемента с номером k. Обращение к i-тому элементу вектора выполняется по адресу вектора плюс смещение к данному элементу. Смещение i-ого элемента вектора определяется по формуле ( i- n ) * Sizeof (тип), а адрес его @Имя + ( i- n ) * Sizeof(тип), где @Имя - адрес первого элемента вектора.

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС

8 Массивы

Массивы

Логическое и физическое представления:

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

Пример двумерного массива [1..n,1..k]:

Наиболее часто реализуемым способом физического размещения многомерного массива является смежное представление (подобно одномерному). В этом случае массив любой размерности представляется, фактически, в виде вектора.

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС

9 Массивы

Массивы

Физическое представление массива в виде вектора

При таком представлении, например, адрес i, j элемента двумерного массива, индексы которого ограничены значениями [1, n][1, k] вычисляется как @Имя + j * Sizeof(тип)+ i * Sizeof(тип) * k, где @Имя - адрес первого элемента массива.

@Имя

+K*sizeof(тип)

+2*k*sizeof(тип)

+3*k*sizeof(тип)

+K*n*sizeof(тип)

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС

10 Массивы

Массивы

Размещение многомерных структур с помощью вектора Айлиффа:

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

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС

11 Массивы

Массивы

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

На рисунке приведена физическая структура двумерного массива В[0..2,0..2], представленная по методу Айлиффа.

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС

12 Записи

Записи

Логическое представление:

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

Данные о клиентах

Фамилия

Имя

Год рождения

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС

13 Записи

Записи

Физическое представление:

Физически запись может быть размещена в памяти двумя способами. В первом случае, подобно вектору, она представляет собой последовательность полей, размещённых смежно. Это дает экономию памяти, но лишнюю трату времени на вычисление адресов полей записи.

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС

14 Записи

Записи

Физическое представление:

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

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС

15 Основные особенности полустатических структур

Основные особенности полустатических структур

Полустатические структуры данных характеризуются следующими признаками: 1. Они имеют переменное число элементов; 2. Изменение длины структуры происходит, как правило, в определённых пределах, не превышая какого-то максимального числа элементов; 3. Логически полустатические структуры представляют собой последовательность данных, связанных отношениями линейного списка. К полустатическим структурам относятся: стек, очередь, строка

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС, при участии Можаровского ИС

16 Стеки

Стеки

Логически стек представляет собой последовательность элементов с переменной длиной; включение и исключение элементов из последовательности происходит при этом только с одной стороны, называемой вершиной стека. Другие названия стека – магазин и очередь LIFO (last in first out). Основные операции над стеком это: - включение нового элемента (английское название push - заталкивать); - исключение элемента из стека (англ. pop - выскакивать); - определение текущего числа элементов в стеке; - очистка стека;

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС, при участии Можаровского ИС

17 Демонстрирующий принцип включения элементов в стек и исключения

Демонстрирующий принцип включения элементов в стек и исключения

элементов из стека

На рисунке изображены состояния стека: а) б) в) г) а) пустого; б) после последовательного включения в него элементов A, B, C; в) после исключения из него двух элементов; г) после включения в него элемента D.

C

B

D

А

А

А

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС, при участии Можаровского ИС

18 Операции стека

Операции стека

Операция ВКЛЮЧЕНИЯ Операция ИСКЛЮЧЕНИЯ Операция ОЧИСТКИ Операция ОПРЕДЕЛЕНИЕ РАЗМЕРА

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС, при участии Можаровского ИС

19 Следующий пример поясняет реализацию операций создания, включения,

Следующий пример поясняет реализацию операций создания, включения,

исключения и определения размера стека на языке С.

//------------------------------------------------------ int n=10; //Максимальное число элементов в стеке int* pmem; //Указатель на область памяти, занимаемой стеком int* pstack; //Указатель вершины стека int i, m; pmem=new int[n]; // Выделяем память под стек максимальным размером n pstack=pmem; // Присваиваем начальное значение указателю стека *pstack=1; pstack=pstack+1; // Помещаем в стек число 1 *pstack=2; pstack=pstack+1; // Помещаем в стек число 2 pstack=pstack-1; i=*pstack; // Читаем из стека число (в данном случае 2) m=pstack-pmem; // Определяем текущий размер стека //-----------------------------------------------------------------------------

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС, при участии Можаровского ИС

20 Очереди

Очереди

Очередью (или очередью FIFO - first in first out) называется такая последовательность элементов с переменной длиной, в которой включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а чтение (исключение) - с другой стороны (называемой началом или головой очереди). Основные операции над очередью - те же, что и над стеком: включение, исключение, определение размера, очистка.

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС, при участии Можаровского ИС

21 Схематичное представление логической структуры очереди а) б) в) г) а)

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

пустая очередь; б) после последовательного включения в очередь элементов A, B, C; в) после исключения из очереди двух элементов; г) после включения в очередь элемента D.

Логическая структура очереди

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС, при участии Можаровского ИС

22 Физическое представление очереди в памяти ПК

Физическое представление очереди в памяти ПК

Физически очередь представляется в памяти машины аналогично стеку. При ВКЛЮЧЕНИИ элемента в очередь элемент записывается по адресу, определяемому указателем на конец, после чего этот указатель модифицируется (увеличивается на размер слота). При ИСКЛЮЧЕНИИ элемента из очереди читается элемент, адресуемый указателем на начало, после чего этот указатель также модифицируется (уменьшается на размер слота).

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС, при участии Можаровского ИС

23 Физическое представление очереди в памяти ПК

Физическое представление очереди в памяти ПК

Два способа представления очереди в памяти 1. Кольцевая организация очереди в памяти. 2. Организация очереди как очереди со сдвигом.

E

F

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС, при участии Можаровского ИС

24 Следующий пример поясняет простейшую реализацию операций создания,

Следующий пример поясняет простейшую реализацию операций создания,

включения, исключения и определения размера очереди на языке С.

//----------------------------------------------------------------------------- int n = 10; //Максимальное число элементов в очереди int* pmem; //Указатель на область памяти, занимаемой очередью int* pout; //Указатель начала очереди int* pin; //Указатель на конец очереди int i, m; pmem = new int[n]; // Выделяем память под очередь размером n pout = pmem; pin=pmem; // Присваиваем начальные значения указателям очереди *pin=1; pin=pin+1; // Помещаем в очередь число 1 *pin=2; pin=pin+1; // Помещаем в очередь число 2 i=*pout; pout=pout+1;// Читаем из очереди число (в данном случае 1) m=pin-pout; // Определяем текущий размер очереди //-----------------------------------------------------------------------------

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС, при участии Можаровского ИС

25 Строки

Строки

Строкой называется линейная упорядоченная последовательность символов, принадлежащих некоторому множеству (алфавиту). Основным свойство строк является их переменная длина. Основными операциями над строками являются:- определение длины строки;- конкатенация (сцепление) строк;- поиск вхождения символа в строку. Физическое представление строк в памяти и особенности выполнения операций над ними зависит от того, насколько изменчивыми являются строки в каждой конкретной задаче.

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС, при участии Можаровского ИС

26 Векторное представление строк

Векторное представление строк

Представление строки в виде вектора постоянной длины является самым простым способом. Пример размещения в памяти строки “ABC” :

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС, при участии Можаровского ИС

27 Представление строк вектором переменной длины с признаком конца

Представление строк вектором переменной длины с признаком конца

Этот метод учитывает переменную длину строк. Признак конца - это особый символ, принадлежащий алфавиту (таким образом, полезный алфавит оказывается меньше на один символ), и занимающий то же количество разрядов, что и все остальные символы.

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС, при участии Можаровского ИС

28 Представление строк вектором переменной длины со счётчиком

Представление строк вектором переменной длины со счётчиком

Счетчик символов - это целое число, которое задаёт длину строки. Обычно для счетчика отводят от 8 до 16 битов. При таком представлении издержки памяти в расчете на одну строку составляют 1-2 символа. При использовании счетчика символов возможен произвольный доступ к символам в пределах строки, поскольку можно легко проверить, что обращение не выходит за пределы строки. Счетчик размещается в таком месте, где он может быть легко доступен – в начале строки или в её дескрипторе.

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС, при участии Можаровского ИС

29 ?

?

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

При таком способе представления строк память под них отводится при создании строки и ее размер (определяющий максимальную длину строки) и размещение остаются неизменными все время существования строки. В дескрипторе строки при этом отводится поле для размещения текущей длины строки. "Лишняя" часть отводимой памяти может быть заполнена любыми кодами - она не принимается во внимание при оперировании со строкой. Представление строк в виде вектора с управляемой длиной (при максимальной длине строки 10) показано на рисунке.

© В.М. Гриняк, доц. каф. ИСКТ ВГУЭС, при участии Можаровского ИС

«Лекции по курсу «Программирование»»
http://900igr.net/prezentacija/informatika/lektsii-po-kursu-programmirovanie-252586.html
cсылка на страницу
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Программирование > Лекции по курсу «Программирование»