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

Вот «правильный» линейный список

x=VAL(Голова(p)). Вот результат применения функции Голова:

оп=Голова(p)^.атом. Вот результат второго применения функции Голова:

y=VAL(p). Вот результат третьего применения функции Голова:

Вопросы:

1)  В какой последовательности будут выполняться операции одного уровня?

2)  Почему рекурсия обязательно завершится?

Задача

Имеется правильное выражение в виде строки. Построить линейный список для этого выражения.

pElem=^Elem;

Elem=record

след:pElem;

case R:0..1 of

0: (уров:pElem);

1: (атом:T)

end;

Выражение вводится с клавиатуры.

procedure LS(var p:pElem);

var c:char;

begin

if not eoln

begin

read(c);

case c of

‘(‘ : begin

new(p); p^.R:=0; LS(p^.уров); LS(p^.след);

end;

‘a’..’z’,’+’,’-‘,’*’,’/’: begin

new(p); p^.R:=1; p^.атом:=с; LS(p^.след);

end;

‘)’ : p:=nil;

end;

end

else p:=nil;

end;

Задачи

1)  Написать алгоритм вычисления значения арифметического выражения, используя операцию "расчленение".

2)  Имеется линейный список для "правильного" арифметического выражения. Построить линейный список для обратной польской записи этого выражения.

3)  Построить алгоритм обхода элементов линейного списка (восстановить строку символов с учетом вложенности).

Лекция 5

5.1 Деревья

Дерево – структура данных, позволяющая смоделировать иерархические отношения. У каждого элемента этой структуры имеется свой единственный «непосредственный начальник» и некоторое количество «подчиненных». Примерами древовидной структуры могут служить подчиненность служащих в армии, структура бюрократического управления производством, почтовый адрес, организация хранения данных в файловой подсистеме системы Windows, и другие.

Термины: корень, узлы, листы, ветки, поддерево, пень, предок, потомок, братья, уровень, высота.

Определение (рекурсивное):

Dn – n-арное дерево (n>=2), Dno – непустое n-арное дерево.

Dn = (либо пусто, либо Dno);

Dno = (i:инф; n штук Dn)

n=2 - бинарное дерево.

5.2 Бинарные деревья

D = (либо пусто, либо Dо);

Dо = (i:инф; лев:D; прав:D).

Операции:

·  Создать (Создается пустое дерево)

·  Пусто? (Функция логического типа, истина, если дерево пусто, ложь в противном случае)

·  Корень? (Функция логического типа, истина, если дерево состоит лишь из корня. Такое дерево можно назвать «пнем»)

·  Корень (Процедура выделяет из дерева корень, левое и правое поддеревья как самостоятельные деревья)

·  Левое поддерево (Процедура выделяет из дерева левое поддерево, корень, и правое поддерево как самостоятельные деревья)

·  Правое поддерево (Процедура выделяет из дерева правое поддерево, корень и левое поддерево как самостоятельные деревья)

·  Конструирование (Из «пня» и двух деревьев конструируется дерево. Это операция, обратная к предыдущим трем)

·  Обходы (6 штук! Их названия – ЛКП, ЛПК, ПКЛ, ПЛК, КЛП, КПЛ зависят от порядка обхода)

Пример. Правильное арифметическое выражение (((a+b)*c)/(c+d)).

Представим в виде бинарного дерева

Обходы:

ЛКП – (((a+b)*c)/(c+d)) – исходное выражение.

ЛПК – ab+c*cd+/ – обратная польская запись.

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

pTree=^Tree; Tree=record Корень:Inf; Лев, Прав:pTree end;

Корень
Лев	Прав

Арифметическое выражение как линейный список p погрузить в двоичное дерево

Голова(p) – функция с побочным эффектом

(Голова указывает на голову, p на хвост).

Функция Погрузить(р:pElem):pTree;

если атом?(р) то создается пень q,

иначе

q:=Конструирование(Погрузить(Голова(р)), Погрузить(Голова(р)), Погрузить(Голова(р)));

Погрузить=q

5.3 Реализация операций

Конструирование(р1:pTree; i:Inf; p2:pTree):pTree

Var p:pTree;

begin

NEW(p);

p^.Корень:=i;

p^.Лев:=p1;

p^.Прав:=p2;

Конструирование:=p

end

Теперь можно реализовать функцию Погрузить

ЛКП(р)

если р<>NIL то ЛКП(р^.Лев), TRT(p^.Корень), ЛКП(р^.Прав)

(TRT(i:Inf) - процедура обработки данного типа Inf, например печать)

5.4 Программа

ПАВ (строка символов) => LS => Линейный список

ПАВ (строка символов) => Задача! => Двоичное дерево

Линейный список => Погрузить => Двоичное дерево

Линейный список => Val => Значение выражения (число!)

Двоичное дерево => ЛПК => Обратная польская запись

Обратная польская запись => Стек => Значение выражения (число!)

program from_list_and_tree_to_list;

uses crt;

type

pList=^List;

List=record

next:pList;

case R:0..1 of

0: (level:pList);

1: (atom:char);

end;

pTree=^Tree;

Tree=record

root:char;

left:pTree;

right:pTree;

end;

var p:pList; q:pTree;

procedure Input_to_List(var p:pList);

var c:char;

begin

if not eoln then

begin

read(c);

case c of

'(': begin

new(p); p^.R:=0;

Input_to_List(p^.level);

Input_to_List(p^.next);

end;

'a'..'z','+','-','*','/': begin

new(p); p^.R:=1;

p^.atom:=c;

Input_to_List(p^.next);

end;

')': p:=nil

end

end else p:=nil

end;

procedure Print_of_List(p:pList);

var q:pList;

begin

if p<>nil then

begin

if p^.R=1 then write(p^.atom)

else

begin

write('(');

q:=p^.level;

while q<>nil do

begin

Print_of_List(q);

q:=q^.next

end;

write(')');

end

end

end;

function CutHead(var p:pList):pList;

var q:pList;

begin

q:=p^.level;

p^.level:=q^.next;

q^.next:=nil;

CutHead:=q

end;

function List_to_Tree(p:pList):pTree;

var q:pTree;

begin

new(q);

if p^.R=1 then

begin

q^.root:=p^.atom;

q^.left:=nil;

q^.right:=nil

end else

begin

q^.left:=List_to_Tree(CutHead(p));

q^.root:=CutHead(p)^.atom;

q^.right:=List_to_Tree(CutHead(p));

end;

List_to_Tree:=q

end;

procedure Print_of_Tree(p:pTree);

begin

if p<>nil then

begin

if (p^.left<>nil)and(p^.right<>nil)then write('(');

Print_of_Tree(p^.left);

write(p^.root);

Print_of_Tree(p^.right);

if (p^.left<>nil)and(p^.right<>nil)then write(')');

end;

end;

Procedure AddHead(var p:pList; q:pList);

begin

q^.next:=p^.level;

p^.level:=q

end;

function Tree_to_List(p:pTree):pList;

var ps:pList; pright, pleft, proot:pTree;

begin

new(ps);

ps^.next:=nil;

if (p^.left=nil) and (p^.right=nil) then

begin

ps^.R:=1;

ps^.atom:=p^.root;

dispose(p)

end else

begin

ps^.R:=0;

ps^.level:=nil;

{Расчленение p на pleft, pright, proot}

pright:=p^.right;

pleft:=p^.left;

p^.right:=nil;

p^.left:=nil;

proot:=p;

AddHead(ps, Tree_to_List(pright));

AddHead(ps, Tree_to_List(proot));

AddHead(ps, Tree_to_List(pleft));

end;

Tree_to_List:=ps

end;

begin

ClrScr;

Input_to_List(p);

Print_of_List(p);

writeln;

q:=List_to_Tree(p);

print_of_Tree(q);

writeln;

p:=Tree_to_List(q);

Print_of_List(p);

writeln;

repeat until keypressed

end.

5.5 Дерево двоичного поиска

Пусть тип данных Inf допускает порядок (то есть данные этого типа можно сравнивать на «больше» и «меньше»).

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

Операции: Создать, Добавить, Найти, Обход.

Пример: 22,10,3,5,13,26,18,19,17,2,4,7,...

5.6 Реализация операций

Добавить(р:^Эл, i:Inf)

Если p=NIL то NEW(p);p^.кор=i;p^.лев=NIL;p^.прав=NIL

иначе

если i<p^.кор > то Добавить(p^.лев, i),

иначе Добавить(p^.прав, i)

Задачи

1.  Заполнить дерево двоичного поиска из файла?

2.  Найти элемент с заданной информационной частью в дереве двоичного поиска?

3.  Что дает ЛКП обход дерева двоичного поиска?

Лекция 6

Повторение темы «Структуры данных»

Лекция 7

Программное окружение = пользовательские (авторские) программы, инструментальные средства, примитивы.

7.1 Примитивы

Примитивы – это подпрограммы, назначение которых – локализовать систмно-зависимые операции. Чтобы программу, работающую в одной операционной среде, использовать в другой операционной среде, необходимо «переписать» все системно-зависимые операторы. Как правило, это операции обращения к внешним устройствам. Для удобства такого «переписывания» зависящие от системы операции локализуют в отдельных подпрограммах (примитивах). В случае перехода в другую операционную среду достаточно «переписать» только эти подпрограммы. Вот пример из книги Г. Кернигана и Ф. Плоджера «Инструментальные средства программирования на языке Паскаль» («Ф и С», 1985).

Program primitiv;

Const _endfile_=-1; _endline_=-2;

Type character=-2..255;

var f, g:text;

function getc(var f:text):character;

var ch:char; c:character;

begin

if eof(f) then c:=_endfile_else

if eoln(f) then

begin

readln(f); c:=_endline_

end

else begin

read(f, ch);

c:=ord(ch)

end;

getc:=c;

end;

procedure putc(var f:text; c:character);

begin

if c<>_endfile_ then

if c=_endline_ then writeln(f) else write(f, chr(c))

end;

procedure copy(var f, g:text);

var c:character;

begin

c:=getc(f);

while c<>_endfile_ do

begin

putc(g,c);

c:=getc(f)

end;

close(g)

end;

begin {Тело программы}

assign(f,'primitiv. pas'); assign(g,'cop. pas');

reset(f); rewrite(g); copy(f, g);

end.

7.2 Инструментальные средства. Архивация файлов (пока без сжатия)

Файлы с любым базовым типом – file of byte.

Операции: создать, добавить, исключить, просмотреть.

Procedure addfile(arh, fl:string);

var A, B,F:File Of Byte; c:Byte;

begin

assign(A, arh); assign(F, fl); assign(B,’workfile. d’);

reset(A); reset(F); rewrite(B);

while not eof(A) do begin read(A, c);write(B, c) end;

while not eof(F) do begin read(F, c);write(B, c) end;

erase(A); rename(B, arh);

end;

Каковы недостатки такого «добавления»?

Как эти недостатки исправить?

Уникальный разделитель Указание длины каждого файла Каталог содержимого всего архива

7.3 Программы хранения и обработки информации

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

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

Свойства алгоритмов хранения и обработки информации:

Корректность (однозначное восстановление из архива);

Надежность (восстановление после сбоя)

7.4 Код Цезаря

Код k каждого символа заменяется кодом k+n, где n – константа кодирования. Следует иметь в виду, что среди символов кодовой таблицы имеются «странные» символы, которые не имеют собственного изображения, а при попытке их отображения на экране происходят странные вещи…

Коды 0..255, например.

«Странные» символы – с 0 до 20 в шестнадцатеричной системе

7.5 Упаковка текста

В нашем задачнике задача:

III.4.3. Написать программу, которая упаковывает (и восстанавливает упакованный) текст. Упаковка производится заменой всех повторяющихся более трех раз символов комбинацией #АВС, где А и В - цифры, составляющие целое положительное К, С - символ, который в исходном тексте был повторен ровно К раз.

Проблемы упаковки:

Если символ повторяется более 99 раз, он кодируется блоками по 99 + остаток.

Если символ # имеется в кодируемом тексте…

7.6 Код Хаффмана

Пример: Закодировать сообщение: АВАССДАСА

Способ 1:

А=00, В=01, С=10, Д=11

получаем

Убедиться, что закодированный текст однозначно восстанавливается.

Любой ли код соответствует некоторому тексту?

Способ 2 (Код Хаффмана):

Частота: А(3)=0, С(2)=10, В(1)=110, Д(1)=111

получаем

Принцип: наиболее часто используемые символы кодируются наиболее короткими кодами.

Убедиться, что закодированный текст однозначно восстанавливается.

Любой ли код соответствует некоторому тексту?

Сформулировать условие эффективности кодирования по Хаффману.

Сообщение – последовательность байт (8 бит) рассматриваем как последовательность пар бит (00, 01, 10, 11), пусть их (пар бит) n штук.

Статистика: Х1 – к1 раз, Х2 – к2, Х3 – к3, Х4 – к4, причем к1>=к2>=к3>=к4

Кодируем Х1 – 0, Х2 – 10, Х3 – 110, Х4 – 111.

Хотим, чтобы длина кода к1+2*к2+3*к3+3*к4 < 2*n;

Причем к1+к2+к3+к4=n. Откуда 2*к1+к2>n – условие реального сжатия.

1.  При к1>n/2 – всегда происходит сжатие;

2.  При к1<n/3 – сжатия не будет.

Задача: Испытать этот метод сжатия на файлах различного типа.

7.7 Код Хемминга

Для передачи 11-битного кода используется 15 бит.

Плюсиками обозначены номера столбцов в двоичном коде.

Знаки вопроса – это 1, если четное число единиц в позициях, помеченных знаком +, 0, если нечетное.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

?

+

+

+

+

+

+

+

2

?

+

+

+

+

+

+

+

4

?

+

+

+

+

+

+

+

8

?

+

+

+

+

+

+

+

Сумма номеров контрольных кодов (подчеркнуты) с нарушением четности дает номер разряда со сбоем.

Пусть нужно передать сообщение:

Передаем??1?010?1 с учетом четности .

Пусть при передаче изменился 13 бит (вместо 1 – 0), тогда по таблице нарушение четности произойдет в строках, помеченных числами 1, 4 и 8, их сумма – 13!

7.8 Вектор Айлиффа

A=array[1..L,1..M,…,1..N]of T; - k-мерный массив.

Координата записи A[k, i,…,j] вычисляется по формуле, сод. к-1 умножение.

Трехмерный массив А[L, M,N]

Приведенный индекс для A[k, i,j] – ((N*M)*k+N*i+j)=((M*k+i)*N+j)

Вектор F: Fk=адрес(A[1,1,1])+sizeof(T)*(N*M)*k, k=0..L-1

Вектор Q: Qi=sizeof(T)*N*i, i=0..M-1

Вектор R: Rj=sizeof(T)*j, j=0..N-1

адрес(A[k, i,j])=F(k)+Q(i)+R(j)

Как устроен массив.

m: array[ 1..n1]of T; ( элементы)

mm: array[ 1..n2,1..n1]of T; ( строки, элементы)

mmm:array[1..n3,1..n2,1..n1]of T; (слои, строки, элементы)

Приведенный индекс.

Элемент массива	Приведенный индекс (смещение)
m[i]	i-1
mm[j, i]	(j-1)*n2+i-1
mmm[k, j,i]	((k-1)*n3+j-1)*n2+i-1

Вектор Айлиффа

w:=sizeof(T); v:=sizeof(pointer); A1,A2,A3:pointer;

Адрес начала массива	Адрес элемента массива
A1:=@m;	A1+(i-1)*w
A1:=@A2; A2=(@mm[1],@mm[2],..,@mm[n2])	(A1+(j-1)*v)^+(i-1)*w
A1:=@A2; A2:=(@A21,@A22,..,@A2n3); A2k=(@mmm[k,1],@mmm[k,2],..,@mmm[k, n2])	((A1+(k-1)*v)^+(j-1)*v)^+(I-1)*w

Лекция 8

Хранение данных в оперативной памяти или на внешних устройствах.

В оперативной памяти данные хранятся в структурах.

На внешних устройствах данные хранятся в файлах.

Обработка данных в структурах - вставка, удаление, поиск.

Для линейных структур «массив», «таблица» (а иногда и «очередь») – сортировка.

Для нелинейных структур - обход.

Операцию сортировки иногда применяют к файлам.

8.1 Сортировка – перестановка элементов линейной структуры

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

Запись:

Mem=record key:integer; info:inf end;

Mass=array[0..L]of Mem;

Считаем далее, что

a:Mass; x:Mem;

Всего элементов массива – n штук.

Для определенности считаем, что элементы массива a должны быть упорядочены по возрастанию значения ключа. Для простоты изложения будем говорить, что a[i]>a[j], если a[i].key>a[j].key.