II семестр (стр. 1 )

II семестр

0. Содержание курса

Лекций -2; Семинаров; Лабораторных -2;

До 1 апреля 10 баллов на F (кто не успел - 15 баллов до 15 апреля).

Апрель - контрольная по составлению проекта программы.

Май - защита курсовых работ.

Июнь - экзамен.

Литература по Фортрану (в дополнение к списку 1 семестра):

. Fortran для персонального компьютера (Справочное пособие). М 1991. , , . Фортран 77 для ПЭВМ. М, «Ф и С», 1991.

Лекция 1

1.1 Cтруктуры данных

1.1.1 Основные понятия

Вычислительные машины первоначально были задуманы как быстрые вычислители и использовались, в основном, для решения вычислительных задач. Однако, со временем, все в большей степени вычислительные машины используются для сбора, хранения и обработки информации. Нельзя классифицировать задачи на чисто вычислительные и задачи обработки информации, поскольку эффективность решения всякой задачи зависит и от организации вычислений и от организации работы с данными.

Задача для ЭВМ = вычислительная часть + обработка информации.

·  Информация – совокупность сведений или знаний.

·  Данные - информация, пригодная для обработки.

·  Система – совокупность взаимосвязанных объектов, подчиненных определенной (единой) цели.

·  Автоматизированные информационные системы (АИС) - системы обработки данных.

·  Базы данных (БД) - совокупность взаимосвязанных данных.

·  Структура - взаимосвязь отдельных элементов.

·  Запись - совокупность (группа) элементов (полей).

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

Под структурой данных можно понимать совокупность данных, на которой описана структура (взаимосвязь отдельных элементов). Над структурой данных определена совокупность операций обработки данных с учетом структуры. С другой стороны, совокупность операций обработки данных требует наличия определенной взаимосвязи данных, то есть определенной структуры. Таким образом, можно отождествить структуру данных с набором операций обработки данных, определенных на ней.

Три уровня абстракции описания структур данных:

Ø  Набор функциональных спецификаций;

Ø  Логическое описание (типы данных);

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

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

Линейные	Нелинейные
Прямоугольные	Структуры ряда	Списковые	Древовидные	Графы	Мульти графы
Массивы, таблицы	Строки, очереди, стеки, деки	Линейный список	n-дерево, бинарное дерево, дерево двоичного поиска

Указатель - адрес начала записи.

1.1.3 Обозначения и договоренности

Пусть Т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 - информационная часть (часть данных, не влияющих на структуру).

1.1.4 Множества.

Множество записей - простейшая вырожденная структура данных, характеризуемая отсутствием взаимосвязи между элементами множества (записями). В языке Паскаль логическое описание и физическое представление множества берет на себя транслятор (тип данных множество предопределен в языке, описатель set of T). Операции над множествами сведены в таблицу.

Имя операции	Функциональные спецификации	Аргументы	Результат	Описание
Создать	®U		Æ	Создается пустое множ
Включить	T´U®U	t, u	{xÎTïxÎu или x=t}	К u добавляется t, если он не принадлежит u
Принадлежит?	T´U®Boolean	t, u	Истина, если tÎu,	Принадлежит ли элемент t множеству u?
Исключить	T´U®U	t, u	{xÎTïxÎu и x¹t}	Удалить элемент t из множества u
Пусто?	U®Boolean	u	Истина, если u=Æ	Пусто ли множество u?
Объединение	U´U®U	u1, u2	{xÎTïxÎu1 или xÎu2}	Объединение u1 и u2
Пересечение	U´U®U	u1, u2	{xÎTïxÎu1 и xÎu2}	Пересечение u1 и u2
Разность	U´U®U	u1, u2	{xÎTïxÎu1 и xÏu2}	Разность u1 и u2
Дополнение	U®U	u	{xÎTï xÏu}	Дополнение к u

Здесь Т – базовый тип множества, U – тип множество, t – данное базового типа (t:T или tÎT), u, u1, u2 – данные типа U.

1.1.5 Прямоугольные структуры. Массивы

Массив - конечное упорядоченное множество элементов (записей) одного типа. Индекс (номер по порядку) указывает относительное положение элемента (отсчет ведется от первого элемента). В языках программирования структура данных "массив" поддерживается транслятором. Пусть Т - базовый тип, т. е. тип элементов, I – индексный тип (множество допустимых индексов). Тогда можно определить новый тип данных М = array[I]of Т.

Над массивом определены следующие операции:

Ø  создание массива (это делает транслятор),

Ø  инициализация элемента,

Ø  чтение значение элемента

Задача. Записать функциональные спецификации для структуры данных «массив».

Создание массива ®М,

Инициализация массива М´I´T®М,

Чтение значения элемента массива М´I®T.

Лекция 2

2.1 Прямоугольные структуры. Таблицы

Таблица – неограниченный набор однотипных записей, содержащих ключ.

Пусть Key и Inf - известные типы, тогда таблица B есть конечный (но не ограниченный заранее) набор записей B={зап}, где зап = record кл:Key, инф:Inf end.

На данных типа Key, как правило, определен порядок.

Частным случаем таблицы можно считать массив (с определенной натяжкой!), если в качестве Key взять множество индексов.

Таблицы можно характеризовать как неупорядоченные и упорядоченные.

Упорядоченные таблицы могут быть упорядочены по ключу и по частоте обращения. Основные операции над таблицами и их функциональные спецификации приведены в таблице.

Имя операции	Функциональные спецификации	Описание
Создать	®B	Создается пустая таблица
Добавить	B´Key´Inf®B	Добавляется запись
Найти	B´Key®Inf	Ищется запись
Удалить	B´Key®B	Удаляется запись
Пусто?	B®Boolean	Пуста ли таблица?

Решение этих задач зависит от типа таблицы:

·  неупорядоченная

·  упорядоченная по ключу

·  упорядоченная по частоте обращения.

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

2.2 Реализация с использованием параллельных массивов (статическое представление таблицы)

type

PElem=1..N;

MInf = array [PElem] of Inf;

MKey = array [PElem] of Key;

var

k:integer - количество записей в таблице.

MI:MInf; MK:MKey;

2.3 Реализация операций для неупорядоченной таблицы с использованием статической памяти

Заголовок	Действие
Создать (var k:integer)	k:=0
Таблица пуста? (k:integer): Boolean	Таблица пуста?:= k=0
Добавить в начало (var k:integer, x:Key, ii:Inf)	if k<N then begin for i:=k downto 1 do begin MI[k+1]:=MI[k]; MK[k+1]:=MK[k] end; k:=k+1; MI[1]:=ii; MK[1]:=x end else печать «оп. выполнить не могу»
Добавить в конец (var k:integer, x:Key, ii:Inf)	if k<N then begin k:=k+1; MI[k]:=ii; MK[k]:=x end else печать «оп. выполнить не могу»
Найти по ключу последовательный поиск(k:integer, x:Key): PElem	k1:=1; while (k1<=k)and(MK[k1]<>x) do k1:=k1+1; Найти по ключу=k1
Найти по ключу бинарный поиск(k:integer, x:Key): PElem	Сами!!!
Удалить запись таблицы, заданную ключем, если она есть (var k:integer, x:Key)	k1:=Найти по ключу(k, x); if k1<=k then begin for i:=k1+1 to k do begin MI[i-1]:=MI[i];MK[i-1]:=MK[i] end; k:=k-1 end

2.4 Динамическая память. Куча

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

В отличие от таких статических переменных в программах, написанных на языке ПАСКАЛЬ, могут быть созданы динамические переменные. Основное свойство динамических переменных заключается в том, что их создание (и распределение памяти под них) осуществляется пользовательской программой на этапе ее выполнения. Размещаются динамические переменные за пределами статической области памяти – в динамической области памяти (в heap-области, в куче).

Пусть Т – некоторый тип данных, t:T, тогда ^T – новый тип данных. Переменная q:^T называется типизированным указателем. Типизированный указатель предназначен для хранения адреса участка динамической памяти, куда может быть записано значение базового типа Т.

Инициализация указателя с помощью процедуры NEW(q). По запросу процедуры NEW диспетчер динамической памяти находит в динамической области памяти (в куче) свободный участок памяти, размером данного типа T, и адрес начала этого участка записывает в q. С этого момента указатель q является инициализированным, а выделенный участок имеет имя q^. Диспетчер динамической памяти считает участок q^ занятым. Для его освобождения можно использовать процедуру DISPOSE(q). Переменная q становится неопределенной (неинициализированной), а конструкция q^ – бессмысленной.

Использование указателя. Если указатель q инициализирован с помощью NEW, то q^ – имя динамической переменной типа Т. Динамическую переменную q^ можно инициализировать значением типа Т, например q^:=t.

"Заземление" – константа NIL, совместимая со всеми указателями (в частности, с типизированными указателями любых базовых типов). Можно q:=NIL, тогда q – определено (инициализировано), однако q^ – бессмысленно. Инициализированный константой NIL указатель может сравниваться с другими инициализированными указателями на равенство и неравенство.

2.5 Операции над указателями

Указатель может находиться в одном из трех состояний:

1.  Указатель не инициализирован. Можно только инициализировать значением другого (инициализированного) указателя, процедурой NEW, или константой NIL;

2.  Указатель инициализирован процедурой NEW. Можно использовать динамическую переменную q^, как переменную типа T, сам указатель сравнивать с другими указателями (только на совпадение или несовпадение), переинициализировать любым способом (см.1.);

3.  Указатель инициализирован константой NIL. Можно указатель сравнивать с другими указателями (только на совпадение или несовпадение), переинициализировать любым способом (см.1.);

Операция взятия адреса.

program adres;

var x:real;

p:^real;

begin

x:=3.1415;

p:=@x;

writeln(integer(p),p^)

end.

2.6 Геометрическая интерпретация

Указатель q:^T;

NEW(q);

Куча;

Диспетчер Динамической Памяти;

q^:T;

2.7 Динамическая цепочка

Pelem=^Elem;

Elem=Record inf:Inform, next:PElem end

Считаем, что Inf=real;

Таблица задается инициализированным указателем p.

Задача: Распечатать третью запись цепочки, если она есть (печать p^.след^.след^.инф)

Задача: Распечатать k-ую запись цепочки.

q:=p;

i:=1;

while (q<>nil) and (i<k) do

begin

i:=i+1;

q:=q^.next;

end;

if q<>nil then writeln(q^.inf) else writeln(‘нет записи’);

2.8 Реализация операций для неупорядоченной таблицы с использованием динамической памяти

PElem = ^Elem;

Elem=record кл:Key; инф:Inf, след:Pelem end;

Заголовок	Действие
Создать (var p:PElem)	p:=NIL
Таблица пуста? (p:PElem): Boolean	Таблица пуста?:= p=NIL
Добавить в начало (var p:PElem, x:Key, i:Inf) (доп. перем p1:PElem)	NEW(p1); p1^.кл:=x; p1^.инф:=i; p1^.след:=p; p:=p1;
Добавить в конец (var p:PElem, x:Key, i:Inf) (доп. перем p1,p2:PElem) (можно обойтись одной доп. перем.)	p1:=p; p2:=p; while p1<>NIL do begin p2:=p1; p1:=p1^.след end; NEW(p1); p1^.кл:=x; p1^.инф:=i; p1^.след:=p; p2^.след:=p1;
Найти по ключу(p:PElem, x:Key) : PElem (доп. перем. p1:PElem)	p1:=p; while (p1<>NIL)and(p1^.кл<>x) do p1:=p1^.след; Найти по ключу:=p1
Удалить запись таблицы, заданную ключем, если она есть(var p:PElem, x:Key): (доп. перем. p1,p2:PElem)	p1:=p; p2:=p; while (p1<>NIL)and(p1^.кл<>x) do begin p2:=p1; p1:=p1^.след end; if p1<>NIL then if p1:=p2 then begin p:=p1^.след; DISPOSE(p1) end else begin p2^.след:=p1^.след; DISPOSE(p1) end

Задача

Реализовать операции для упорядоченной по ключу и упорядоченной по частоте обращения таблиц.

Лекция 3

3.1 Структуры ряда

Последовательный набор записей (цепочка). Доступ к записям структуры ряда осуществляется последовательным просмотром записей цепочки. Определена последующая запись для каждой записи цепочки, кроме последней, и определена предыдущая запись для каждой записи, кроме первой. Структуры ряда подразделяются на строки, очереди, стеки и деки.

3.1.1 Строки

Строка - структура ряда, в которой открыт доступ к любому элементу (любой записи) через последовательный просмотр как от начала цепочки к концу, так и от коца цепочки к началу. Пусть Е - множество элементарных данных, Е(К) - множество всех последовательностей, состоящих из К элементов множества Е, т. е. элементами множества Е(К) являются строки длиной К. В таблице приведены основные операции над строками (использованы обозначения аÎЕ(К1), вÎЕ(К2), сÎЕ(К3), авÎЕ(К1+К2), авсÎЕ(К1+К2+К3) и т. д., dÎЕ(К1-К2+К3))

Имя операции	Функциональные спецификации	Аргументы	Результат	О п и с а н и е
Конкатенация	Е(К1)´Е(К2)® Е(К1+К2)	а, в	ав	Строка, полученная склейкой строк а и в
Вычеркивание подстроки	Е(К1+К2+К3)® Е(К1+К3)	авс	ас	Строка, полученная из авс отбрасыванием в
Разделение	Е(К1+К2)® Е(К1)´Е(К2)	ав	а, в	Разделение на две строки
Подстановка	Е(К1+К2)´Е(К3)® Е(К1+К3+К2)	ав, с	асв	Подстановка
Контекстный поиск?	Е(К1)´Е(К2)® Boolean	а, в	истина или ложь	Истина, если в строке а есть подстрока в
Контекстная замена	Е(К1)´Е(К2)´Е(К3)® Е(К1-К2+К3)	а, в, с	либо d, либо а	Если контекст в найден в а, то он заменяется на контекст с, иначе без изменения

Представление с помощью массивов

N - максимальная длина строки, s1,s2,... :array[1..N] of Inf.