1 ГОУ ВПО Уральский государственный технический университет – УПИ

2 Кафедра «Автоматика и управление в технических системах» направление – Автоматизация и управление специальность – Управление и информатика в технических системах ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ СИСТЕМ УПРАВЛЕНИЯ Лекция ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Списковые структуры Последовательное распределение памяти Связанное распределение памяти Преподаватели: Чесноков Юрий Николаевич, доц., к.т.н., Дружинина Надежда Геннадьевна, доц.

3 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Цель изучения материала: изучить представление данных в памяти компьютера с помощью списковых структур; изучить последовательное распределение памяти компьютера; изучить связанное распределение памяти компьютера. Компетенций, формирующиеся в процессе знакомства с материалом: готовность учитывать современные тенденции развития информационных технологий в своей профессиональной деятельности (ОНК-2); готовность работать с информацией из различных источников (ИК- 4); способность к приобретению новых знаний, используя современные информационные технологии (СЛК-4); готовность использовать современные инструментальные средства и технологии проектирования программных средств (ПТД-2); способность составлять техническую документацию на разработку программного обеспечения (ПТД-4).

4 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Содержание лекции ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Списковые структуры Последовательное распределение памяти Связанное распределение памяти

5 Элементы данных и логические структурные отношения между ними задаются формальным языком – языком описания данных (ЯОД). Логические структуры представляются: - таблицами, - древовидными иерархическими структурами, - сетевыми структурами. Различные структуры данных по разному отображаются в памяти компьютера. Представление данных в памяти компьютера включает в себя как сами данные, так и взаимосвязи между ними, которые определяют структурирование. 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Списковые структуры

6 Простейшей формой хранения данных в памяти компьютера является линейный список – множество n 0 объектов (узлов) X[1], X[2], …, X[n]. Структурные свойства его связаны с линейным (одномерным) относительным расположением узлов. Для 1 < i < n узел X[1] – первый узел; узел X[i – 1] предшествует узлу X[i], узел X[i + 1] следует за ним, X[n] – последний узел. Линейный список в памяти компьютера называют вектором данных или физической структурой хранения данных. 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Списковые структуры

7 Адресная функция – это отображение логических структур данных на физическую структуру хранения в памяти компьютера. Различают два метода реализации адресной функции: - последовательное распределение памяти; - связанное распределение памяти. 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Списковые структуры

8 При последовательном распределении памяти – узлы списка размещаются в последовательных элементах памяти, а вектор данных логически отделен от описания структуры хранимых данных, которые хранятся в отдельной записи и содержат: N – размер вектора данных (количество элементов списка записей); m – размер записи (элемента списка) в байтах; – адрес базы – начало вектора данных в памяти. 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Последовательное распределение памяти

9 Адрес каждой записи вычисляется с помощью адресной функции, отображающей логический индекс, идентифицирующий запись в структуре, в адрес физической памяти (рис. 10.1) (i) = + (i – 1)m. АдресСодержимое (1) = y1y1 (2) = + m y2y2 … (i) = + (i – 1)m yiyi … (n) = + (n – 1)m ynyn Рис Пример последовательного распределения памяти для представления линейного списка

10 В случае линейного списка адресная функция состоит из операций смещения и масштабирования. Для примера на рис показана реализация логической структуры типа регулярного двоичного дерева с помощью линейного списка при последовательном распределении памяти. 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Последовательное распределение памяти

11 Рис Распределение памяти для представления двоичного дерева 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Последовательное распределение памяти y2y2 y1y1 y3y3 y4y4 y6y6 y5y5 y7y7 y8y8 y 10 y9y9 y 11 y 12 y 14 y 13 y 15 y7y7 y6y6 y2y2 y3y3 y 10 y5y5 y1y1 y4y4 y8y8 y9y9 y 11 y 12 y 14 y 13 (1) = (2) = + m (3) = + 2m и т.д.

12 В элементе памяти (1) расположены данные, соответствующие узлу y 1 – корня дерева. В элементах памяти (2) и (3) размещают непосредственных потомков узла y 1 – узлы y 2 и y 3 и т.д. В общем случае непосредственные потомки узла y k размещаются по адресам (2k) и (2k + 1). Адресная функция имеет вид (k) = + (2k + 1)m, где k – номер узла древовидной структуры; – базовый адрес; m – размер элемента памяти, необходимый для хранения данных узлов дерева (каждый узел – запись фиксированной длины). 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Последовательное распределение памяти

13 По полученному списку можно двигаться как по дереву в обоих направлениях. От узла y k можно перейти к его потомкам, удвоив k (или удвоив k и прибавив единицу). Можно перейти к узлу, являющимся исходным для узла y k, разделив k на 2 и отбросив дробную часть. Недостаток описанного метода – сложность представления деревьев, имеющих более двух потомков или имеющих разное количество потомков для различных исходных узлов. 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Последовательное распределение памяти

14 Связанное представление линейного списка – это связанный список. Для построения структуры задаются отношения следования и предшествования элементов с помощью указателей. Указатель – это адрес, хранимый в записях данных. Значение адресной функции можно получить только путем просмотра хранящихся указателей. В этом методе можно расширить либо сократить структуру без перемещения самих данных в памяти компьютера. 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

15 Однако хранение указателей требует больше памяти по сравнению с последовательным распределением. При связанном распределении каждый узел содержит указатель на следующий узел списка (адрес следующего узла). При этом нет необходимости хранить список в последовательных элементах памяти. Линейная структура списка обеспечивается указателями. 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

16 Структура линейного списка в виде связанного распределения – цепная структура или цепь. Примеры связанных линейных списков приведены на рис На этом рисунке показано добавление в список узла y 2А и удаление узла y 4. Как видно, названные операции сводятся только к изменению ссылок. Данные, соответствующие узлам связанного списка могут располагаться в любом месте памяти компьютера. 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

17 Рис Исходный список и список с удаленных узлом y 4 и вставленным узлом y 2А 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти y1y1 y2y2 y3y3 y4y4 λ y1y1 y2y2 y3y3 y4y4 y 2А y5y5 λ

18 Двунаправленный линейный список (рис. 10.4) в каждом узле содержит два указателя: один задает адрес узла X[i – 1], а другой – адрес узла X[i + 1]. Такой список обеспечивает большую гибкость при работе с данными. 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

19 Рис Двунаправленный линейный список 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти y2y2 y3y3 y1y1 λ y4y4 λ

20 Обозначим SOC(X[i]) – указатель в записи на следующий узел; PRE(X[i]) – на предыдущий узел; TOP(X[1]) – указатель базового узла (задается к обращении к списку). Адресная функция для связанного однонаправленного линейного списка Здесь символ λ означает конец списка. 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

21 Адресная функция для связанного двунаправленного линейного списка в прямом и обратном направлениях соответственно: 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

22 Любое произвольное изменение порядка записей в связанном списке, сокращение или расширение вектора данных в какой-либо записи достигается за счет изменения указателей (полей связи) без перемещения записей в памяти компьютера. Однако доступ к конкретному узлу требует больше временных затрат по сравнению с последовательным распределением памяти. Чтобы получить доступ к данным узла X[i] необходимо сделать i итераций, используя TOP(X[1]) и поля связи в узлах X[k], где k = 1, 2, …, i, т.е. последовательно просмотреть все предшествующие узлы списка. 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

23 Уменьшить время доступа позволяет организация связанного линейного списка с пропусками (рис. 10.5), в котором список разделен на группы узлов, связанные между собой обратными указателями. Вначале по обратным указателям идут к группе, в которой есть требуемый узел, а затем по прямым указателям перебираются узлы группы, пока не будет найден требуемый узел. Вход в список в этом случае выполняется с конца. 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

24 Рис Линейный список с пропусками 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти y1y1 λ y2y2 y7y7 λ y3y3 y4y4 y5y5 y6y6

25 Другой способ уменьшения времени доступа – построение специального линейного списка – индекса (с последовательным распределением памяти). Элементы индекса – это значения первых узлов каждой группы и указатели в них (рис. 10.6). 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

26 Рис Линейный связанный список с индексами 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти y1y1 y2y2 y7y7 λ y3y3 y4y4 y5y5 y6y6 y1y1 y3y3 y5y5

27 Оптимальный размер группы (количество узлов в группе) при равновероятном нахождении узла в любой из групп, где n – количество элементов списка. Число групп l = ]n/n г [, где ] [ означает округление до ближайшего большего целого. При равновероятном нахождении узла в любой из групп при доступе к узлу необходимо просмотреть в среднем l/2 групп, а в каждой группе nг/2 узлов. Следовательно, общее количество просмотров 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

28 Циклический связанный линейных список (рис. 10.7) имеет связь от последнего узла к первому узлу списка, т.е. SOC(X[n]) =. Этот список позволяет получить доступ к любому узлу списка, отправляясь от любого заданного узла. Циклические списки называют кольцевыми структурами или кольцами. Голова списка – специальный узел, в котором хранится служебная информация (идентификатор списка, количество узлов в списке и т.п.). 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

29 Рис Циклический список 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти y1y1 y2y2 y3y3 Голова списка

30 Двунаправленный циклический список содержит два указателя в каждом узле (рис. 10.8,а). Есть циклические списки с указателями на голову списка (рис. 10.8,б). 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

31 Рис Двунаправленные циклические списки 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти y2y2 y3y3 y1y1 Голова списка y1y1 y2y2 y3y3 а б

32 Из рассмотренных списков можно реализовать в памяти компьютера сложные нелинейные структуры (древовидные или сетевые) – многосвязные списки. В узлах таких списков необходимо иметь достаточное количество указателей. Их наличие повышает эффективность навигации. 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

33 Для примера рассмотрим представление списками в памяти компьютера исходной древовидной структуры (рис. 10.9). Ее представление возможно с помощью однонаправленных списков из двухзвенных узлов, в которых в первом поле находится либо метка вершины, либо указатель, а во втором – всегда указатель (рис ). 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

34 Рис Пример древовидной структуры 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти и к м жл в г з б а д

35 Рис Представление древовидной структуры однонаправленными списками с двухзвенными узлами 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти б в а л г λ ж λ д λ з λ к λ λ и λ λ λ λ λ м

36 На рис показано представление этой же структуры с помощью однонаправленных списков с узлами фиксированной длины. Ее также можно представить двунаправленными списками с узлами переменной длины и счетчиками количества указателей (рис ) 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

37 Рис Представление древовидной структуры однонаправленными списками с узлами фиксированной длины 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти а б в λ и г λ д λ з λ ж λ к λ л λ м

38 Рис Представление древовидной структуры двунаправленными списками с узлами переменной длины со счетчиками количества указателей 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти а 4 λ в 2 г 3 1 д 1 ж 1 и 1 з 1 м 1 к 2 л б 4

39 Таким образом, указатели – основа построения связанных списковых структур. Есть три типа указателей (адресов записей): - машинный (действительный); - относительный; - символический (идентификатор). 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

40 Действительный указатель (адрес) – обеспечивает наибольшую скорость обработки данных. Однако он имеет жесткую привязку записей к конкретному месту расположения в памяти, что требует изменения всех указателей при перемещении списка в памяти компьютера на иное место. 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

41 Относительный адрес – позволяет размещать списки в любом месте памяти и на различных внешних устройствах без изменения значений указателей. При перемещении списка лишь изменяется адрес, а указатели остаются прежними. Относительные указатели применяются при страничной организации памяти. Скорость доступа к узла с такими указателями ниже, чем при действительных адресах. 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

42 Символический адрес (указатель) – позволяет перемещать отдельные записи относительно друг друга, включать или удалять записи в список без изменения указателей во всех остальных записях. Время доступа к узлам в этом случае наибольшее. Преобразование символического адреса в машинный адрес при обращении к узлам выполняется по специальному алгоритму. Он зависит от выбранного метода адресации. 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Связанное распределение памяти

43 Выводы и заключение по лекции: изучили представление данных в памяти компьютера с помощью списковых структур; изучили последовательное распределение памяти компьютера; изучили связанное распределение памяти компьютера 10. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА

ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ КОМПЬЮТЕРА Перечень источников: Четвериков В.Н. Базы и банки данных/ В.Н. Четвериков, Г.И. Ревунков, Э. Н. Самохвалов; под ред. В.Н. Четверикова. М.: Высшая школа, с. Дейт К. Дж. Руководство по реляционной СУБД DB2/ К. Дж. Дейт. М.: Финансы и статистика, с. Дейт К. Дж. Введение в системы баз данных/ К. Дж. Дейт. М.: Издательский дом «Вильямс», 2001, 1072 с. Дмитриев В.И.Прикладная теория информации/В.И. Дмитриев. М.:Высшая школа, с. Гайдамакин Н.А. Автоматизированные информационные системы, базы и банки данных/ Н.А. Гайдамакин. М.: Гелиос АРВ, С. Карпова Т.С. Базы данных: модели, разработка, реализация/ Т.С. Карпова. СПб.: Питер, с. Мамаев Е.В. MS SQL Server 7.0. Проектирование и реализация баз данных/ Е.В. Мамаев. СПб.: БХВ-Санкт-Петербург, с. Озкарахан Э. Машины баз данных и управление базами данных/ Э. Озкарахан. М.: Мир, с. Селко Джо. SQL для профессионалов. Программирование/ Джо Селко. М.:«Лори», с. Системы управления базами данных и знаний/ А.Н. Наумов [и др.]; под общ. ред. А.Н. Наумова. М.: Финансы и статистика, с. Теория автоматического управления/ С.Е. Душин [и др.]; под общ. ред. Б. Б. Яковлева. М.: Высшая школа, с. Харрингтон Дж. Л. Проектирование реляционных баз данных. Просто и доступно/ Дж. Л. Харрингтон. М.: «Лори», с. Хендерсен К. Delphi 3 и системы клиент/сервер: руководство разработчика/ К. Хендерсен. Киев: Диалектика, с.