Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лекций -2; Семинаров -0 (2); Лабораторных -2;
До 1 апреля 10 баллов на F (кто не успел - 15 баллов до 15 апреля).
Апрель - контрольная по составлению проекта программы.
Май - защита курсовых работ.
Июнь – экзамен (теоретический материал 1 и 2 семестров).
Что нужно повторить
Вычислительные машины первоначально были задуманы как быстрые вычислители и использовались, в основном, для решения вычислительных задач. Однако, со временем, все в большей степени вычислительные машины используются для сбора, хранения и обработки информации. Нельзя классифицировать задачи на чисто вычислительные и задачи обработки информации, поскольку эффективность решения всякой задачи зависит и от организации вычислений и от организации работы с данными.
Задача для ЭВМ = вычислительная часть + обработка информации.
Эффективность обработки данных зависит от формы представления (типы данных), взаимосвязи отдельных элементов (структур данных), последовательности действий (алгоритма).
Три уровня абстракции описания структур данных:
|
Линейные |
Нелинейные |
||||
|
Прямоугольные |
Структуры ряда |
Списковые |
Древовидные |
Графы |
Мульти графы |
|
Массивы, таблицы |
Строки, очереди, стеки, деки |
Линейный список |
n-дерево, бинарное дерево, дерево двоичного поиска |
Указатель (на запись) – переменная, в которой хранится адрес начала записи.
Пусть Т1, Т2, ..., Тn - имена известных типов данных
Т=record N1:T1; N2:T2; ...; Nn:Tn end - новый тип - запись, Ni - имена полей, i=1,2,...,n.
Пусть t:T, ti:Ti, i=1,2,...,n; инициализация t.N1:=t1; t.N2:=t2; ..., t.Nn:=tn; если tt:T, то можно tt:=t (присваивание).
Пример:
type
Comp=record {Комплексное число}
Re:real;
Im:real
end;
var
z:Comp;
zz:Comp;
В секции действий
z.Re:=3.14; z.Im:=1.0;{инициализация}
zz:=z (присваивание).
Глобальный тип: Inf - информационная часть (часть данных, не влияющих на структуру).
Множество записей – простейшая вырожденная структура данных, характеризуемая отсутствием взаимосвязи между элементами множества (записями). В языке Паскаль логическое описание и физическое представление множества берет на себя транслятор (тип данных множество предопределен в языке, описатель set of T). Операции над множествами сведены в таблицу.
|
Имя операции |
Функциональные спецификации |
Аргументы |
Результат |
Описание |
|
Создать |
U |
|
Создается пустое множ |
|
|
Включить |
TUU |
t, u |
{xTxu или x=t} |
К u добавляется t, если он не принадлежит u |
|
Принадлежит? |
TUBoolean |
t, u |
Истина, если tu |
Принадлежит ли элемент t множеству u? |
|
Исключить |
TUU |
t, u |
{xTxu и xt} |
Удалить элемент t из множества u |
|
Пусто? |
UBoolean |
u |
Истина, если u= |
Пусто ли множество u? |
|
Объединение |
UUU |
u1, u2 |
{xTxu1 или xu2} |
Объединение u1 и u2 |
|
Пересечение |
UUU |
u1, u2 |
{xTxu1 и xu2} |
Пересечение u1 и u2 |
|
Разность |
UUU |
u1, u2 |
{xTxu1 и xu2} |
Разность u1 и u2 |
|
Дополнение |
UU |
u |
{xT xu} |
Дополнение к u |
Здесь Т – базовый тип множества, U – тип множество, t – данное базового типа (t:T или tT), u, u1, u2 – данные типа U.
Массив - конечное упорядоченное множество элементов (записей) одного типа. Индекс (номер по порядку) указывает относительное положение элемента (отсчет ведется от первого элемента). В языках программирования структура данных "массив" поддерживается транслятором. Пусть Т - базовый тип, т.е. тип элементов, I – индексный тип (множество допустимых индексов). Тогда можно определить новый тип данных М = array[I]of Т.
Над массивом определены следующие операции:
Задача. Записать функциональные спецификации для структуры данных «массив».
Создание массива М,
Инициализация массива МITМ,
Чтение значения элемента массива МIT.