Шпаргалка по "Языкам программирования"

1.  Type massiv = аггау [1..100] of byte;massiv_ukaz = ^massiv; var ukazl: massiv_ukaz;

2.  Type int_ukaz= ^integer;char_ukaz= ^char; var p : int_ukaz; q : char_ukaz;

3.  Var  p : ^integer;q : ^char;

Из описания следует, что p — ссылка на динамический объект целого типа; q — ссылка на динамический объект символьного типа. Указатель ukazl — это ссылка на объект регулярного типа, значением которого является массив из 100 чисел байтового диапазона. Несмотря на то, что переменные ukazl, p и q связаны с объектами разных типов, все они имеют нечто общее — их значения указывают на определенное место в памяти, соответствующее началу некоторого динамического объекта. Нормальной считается ситуация, когда значение указателя не связывает его с конкретным динамическим объектом, т. e. значение ссылки пусто. Такое значение задается словом-символом NIL.

 

41.

Язык программирования - это изобразительное средство, служащее для непросредственной  реализации алгоритма на ЭВМ.

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

Синтаксис - множество правил написания отдельных конструкций и предложений языка в целом.

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

Классификация языков программирования: языки программирования делятся на две большие группы:машинно-зависимые и машинно-независимые. Машинно-зависимые делятся на машинные и машинно-ориентированные. Машинно-ориентированнные делятся на мнемокоды и автокоды. Машинно-независимые делятся на проблемно-ориентированные, процедурно-ориентированные, объектно-ориентированные, непроцедурные.

Мнемокоды - символические  обозначения машинных комманд.

Автокоды - символические  записи целой серии комманд.

28.

Важно отметить факт, что  описание ссылочной переменной вовсе не связано с существованием динамического объекта, на который эта Переменная может ссылаться, т. e. описание ссылочной переменной не определяет значения этой переменной. Описание Var   P : ^D; говорит лишь о том, что значением P могут быть ссылки на объект типа D. Непосредственное порождение динамического объекта выполняет процедура new(<ссылочная переменная>). В результате ее выполнения реально появляется динамический объект, а <ссылочная переменная> получает значение - ссылку на только что порожденнный динамический объект. При этом он не получает никакого значения, т.е  процедура new имеет тот же смысл, что и описание аналогичного статического объекта.

Для доступа к динамическому  объекту используется переменная с  указателем. Переменную с указателем можно использовать везде, где допустимо применение переменных того же типа, что и тип динамической переменной. В качестве ссылочной переменной может использоваться и более сложная конструкция, например динамический массив (getmem).

Динамический массив порожден с помощью стандартной процедуры getmem, в которой в качестве второго параметра задается количество байтов, необходимых для размещения порождаемого объекта. Первый параметр - адрес, начиная с которого в памяти будет размещен линейный вещественный массив заказанного размера. В процессе работы программы некоторые динамические объекты могут стать ненужными. От них избавляются с помощью стандартной процедуры dispose(<ссылочная переменная>) или freemem (для дин. массивом, например)

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

ДЕЙСТВИЯ НАД ССЫЛКАМИ

Над значениями ссылочного типа в языке не определено каких-либо операций, которые давали бы результат  того же типа. Данное обстоятельство связано  с тем, что язык не предусматривает  правил размещения программных объектов в памяти (этим занимается транслятор). Над значениями ссылочного типа допустимы только оператор присваивания и некоторые операции сравнения: U:=V. Здесь в качестве V может быть 1) Nil;2) переменная ссылочного типа; 3) функция, возвращающая значения того же ссылочного типа.

Отличительные особенности  использования динамических объектов:

1)вместо описания динамического  объекта в программе дается  описание указателя на него.

2) работа с таким  объектом возможна только после  его порождения соответствующими  программными средствами

3) для доступа к  динамическому объекту используется  переменная с указателем

Использование динамических объектов имеет ряд недостатков:

1)замена статической  переменной на динамическую увеличивает  код программы.

2)использование переменных  с указателем снижает наглядность программы.

3)применение динамических  объектов (создание, обработка, уничтожение)  снижает быстродействие программы

Применение операции сравнения по отношению к значениям  ссылочного типа сводится лишь к использованию  следующих операций: 1) = ; 2) <>. Два значения равны, если они оба пустые ссылки (nil) или указывают на одно место в оперативной памяти

 

29.

При использовании динамических объектов необходимо строго следить  за процессом их порождения и уничтожения, иначе может быть сбой программы или системы в целом. Одна из причин этого связана с проблемой программного мусора, под которым можно понимать динамические объекты, порожденные в ходе выполнения программы и ставшие недоступными в результате неверных операций:

var p,q:^integer;begin new(p);new(q);p^:=100;q^:=200;p:=q;

Видно, что динамический объект со значением 100 превратился  в программный мусор - его нельзя ни использовать, ни уничтожить.

Висячие ссылки возникают  при уничтожении динамического  объекта, когда на него указывают  несколько ссылочных переменных одновременно: var p,q:^integer;begin new(p);new(q);p^:=100;q^:=200;p:=q;dispose(q);

 

30.

Информационно-справочное обслуживание — широко распространенный вид услуг, эффективно реализуемых  с помощью ЭВМ. Хранимые сведения, как правило, представляются записями. Типичные операции в таких системах — поиск и выдача требуемой записи. Для этих целей можно использовать структуру данных, называемую таблицей. В ней любой записи соответствует определенное имя. При этом в заказе на выдачу требуемой информации необходимо указать только имя записи, а реализация структуры должна обеспечить ее быстрый поиск.

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

1)  поиск записи  по заданному ключу;

2)  включение в таблицу  записи с заданным ключом;

3)  удаление записи с заданным ключом.

Существует много способов организации таблиц, каждый из кото- j рых имеет свои достоинства и  недостатки. Рассмотрим некоторые из них.

ПРОСТАЯ ЦЕПОЧКА

Простейший способ организации  таблицы — однонаправленный список. Любое звено имеет следующую структуру:

Достоинства подобной организации  списка:

1)  экономичность представления  информации (дополнительная информация  в звене всего лишь ссылка  на следующее звено);

2)  простота перебора  записей при поиске;

З)простота включения  в таблицу заведомо новой информации.

Однако имеются и  недостатки:

1) поиск может оказаться  слишком длительным (здесь под  поис-1 ком понимается последовательный  перебор записей, в среднем  поиск требует перебора [N/2] элементов;  если n велико, то время поиска  может оказаться неприемлемым);

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

 

31.

Цепочка с упорядоченными записями

Недостаток, связанный  с отсутствием в таблице элемента с заданным ключом, можно устранить, если в таблице поддерживать определенный порядок следования записей, например по возрастанию ключей. Поиск требует в среднем просмотра [N/2] элементов независимо от нахождения в таблице записи с заданным ключом. В этом случае поддержание упорядоченности записей требует определенных затрат, так как включение в таблицу новой записи становится более трудоемкой операцией. Эти затраты оправдываются, если включение производится редко, а поиск — часто.

 

32.

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

При такой организации  информационная часть хранится отдельно от ключей (при ключе — только ссылка на нее). Как видно, все элементы таблицы имеют одинаковую структуру, следовательно, их можно объединить в массив (вектор): Type IND = l..N;

Info = TInfo;   {тип информационной  части} TUKaz = ^Info; Type Zapis = Record;

Key : integer; Ukaz : TUkaz end;Type Vector = array [ind] of zapis; Var x : Vector;

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

В этом случае появляется возможность получить прямой доступ к любому элементу таблицы с помощью  индексированной переменной X[i].Key. Данные обстоятельства позволяют применить эффективный метод поиска — дихотомический.

Теперь задача сводится к нахождению элемента массива с  заданным значением ключа. Информационную часть получаем с помощьет конструкции x[i].Ukaz^.

Первоначальной зоной  поиска является весь интервал индексов! от 1 до n. Далее берем компоненту с индексом I = [n /2]. Если1 требуемый ключ найден, то поиск закончен. Если k < x[i].Key, то в качестве правой границы поиска берем I - 1, иначе в качестве левой — I + 1. В результате на каждом шаге зона поиска становится в два раза короче. В любом случае для поиска требуется не более (1 + log2n) шагрв. Эффект дихотомии быстро растет с увеличением n.

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

Function DXTM (k : integer; var m : integer): Boolean; Var L_gr, R_gr : integer; B : Boolean; i : IND; Begin

L_gr := 1;           {левая граница интервала поиска}

R_gr := n;          {правая граница интервала поиска}

В := false;          {ключ не найден?}

M := 0; {инициализация побочного результата} Repeat

i := trunc (( L_gr + R_gr ) / 2 + 0.1); if    К = x[i].key then Begin В := true; M := i 'End else iF k < x[i].Key then

R_gr := i - 1 else L_gr := i + 1 Until  b or (L_gr > R_gr); DXTM := b End;

 

33.

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

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

Элемент дерева имеет  следующую структуру:

Каждую вершину дерева представляют четыре поля:

1)  ключ;

2)  ссылка на левую  ветвь;

3)  ссылка на правую  ветвь;

4)  ссылка на информационную  часть. Опишем типы данных:

Type  Info = TInfo;    {тип информационной части} TUkaz = ^Info; TZveno_Ukaz = ^Zveno; Zveno = Record; Key : integer; Left : TZveno_Ukaz; Right : TZveno_Ukaz; U : TUkaz End;

Var B_Derevo : TZveno_Ukaz;

Логическая функция  поиска Poisk в качестве побочного эффекта возвращает ссылку на найденную вершину (в случае успеха). Function Poisk (k : integer; var d, {d — указатель на дерево} Result : TZveno_Ukaz) : Boolean; Var b : Boolean;

P : TZveno_Ukaz; Begin

В := false; {ключ не найден?} P := d;

if d  <>  nil then Repeat if k = p^.Key

then b := true else

if k < p^.key then p := p^.left

else p := p^. right Until b or (p = nil); Result := p; Poisk := b End.

Для выполнения операции вставки функция Poisk непригодна так  как она не фиксирует вершину, из которой была выбрана пустая ссылка nil. Функция Poiskl в качестве побочного эффекта фиксирует ссылку на вершину с заданным ключом (успешный поиск), либо ссылку на вершину, после обработки которой поиск был прекращен (неуспешный поиск).

 

 

 

 

34.

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

Над очередью определены две операции: а)занесение элемента в очередь (заказ на обслуживание);б)удаление элемента из очереди (обслуживание)