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

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

В силу дисциплин обслуживания в стеке всегда известен только один элемент - поступивший в него последним.(20 лабораторка)

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

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

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

 

35.

Дерево с базовым  типом Т - а)пустое дерево;б)некоторая  вершина типа Т, соединенная с  конечным числом отдельных деревьев с базовым типом Т, называемых поддеревьями.

Видно сходство определений  последовательностей и деревьев.

Последовательность (список) - дерево, в котором каждая вершина имеет не более 1го поддерева.

Упорядоченное дерево - дерево, у которого все ветви (ребра) исходящие  из каждой вершины упорядочены.

Вершина У, находящаяся  непосредственно ниже вершины Х,называется непосредственным потомком Х. Если Х лежит на уровне i, то говорят, что вершина У лежит на уровне i+. При этом Х называют непосредственным предком У, считается, что корень дерева лежит на уровне 0.

Максимальный уровень  какой-либо вершины дерева называется высотой или глубиной дерева.

Если некоторая вершина  дерева не имеет непосредственных потомков, то она называется терминальной или  листом, в противном случае вершина  называется внутренней.

Число непосредственных потомков некоторой внутренней вершины  дерева называется степенью этой вершины. Максимальная степень всех вершин дерева называется степенью дерева.

Дерево степени больше 2 называют сильно ветвящимся.

Дерево степени 2 называют двоичным (бинарным).

Можно поставить задачу построения дерева из n вершин минимальной  глубины. Понятно, что этого можно достичь, если размещать на каждом уровне дерева, кроме возможно последнего, максимальное количество вершин.

Алгоритм построения идеально сбалансированного дерева:1)взять  одну из вершин в качестве корня;2)тем  же способом построить левое поддерево из n div 2 вершин;3)тем же способом построить правое поддерево из n-(n div 2)-1 вершин.

Дерево называется идеально сбалансированным, если число вершин в его правом и левом поддереве  отличается не больше чем на 1.

 

37.

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

В Visual Basic вы можете применять следующие типы данных:числовой (Integer, Long, Single,Double,Currency);строковый (string);типа дата (Date);байтовый (Byte);логический (Boolean);произвольный (Variant);объектный (Object).

Для хранения чисел в Visual Basic используется пять разных типов данных. Для хранения целочисленных данных предназначены типы Integer и Long. Первый из них служит для хранения целых чисел в диапазоне от -32768 до 32767 и занимает в оперативной памяти два байта. Для хранения больших целочисленных значений в диапазоне от -2147483648 до 2147483648 следует выбрать тип данных Long. В этом случае для хранения переменной выделяется 4 байта. Аналогично, для хранения десятичных чисел с плавающей точкой предназначены типы данных Single и Double. Переменная с типом данных Single занимает 4 байта и может принимать значения в диапазоне -3,438...-1,4-45 для отрицательных чисел и 1,4-45 ... 3,438 для положительных чисел. Если этого диапазона вам недостаточно, используйте десятичные числа с плавающей точкой двойной точности, определяя для них тип данных Double. В этом случае переменной выделяется 8 байтов, которых достаточно для хранения чисел в диапазоне -1,7-308 ... -4,9-324 для отрицательных чисел и 4,9-324 ... 1,7+308 для положительных чисел. Для хранения чисел с фиксированной точкой служит тип Currency. Переменная данного типа занимает в оперативной памяти 8 байт. Целая часть числа может содержать до 15 цифр, а дробная - до 4.

Используя переменные строкового типа, вы можете хранить строки как  фиксированной (до 216 символов), так и переменной длины (до 231 символов). Для переменной, имеющей тип строки с фиксированной длиной, указывается максимальная длина строки. Если длина строки, присваиваемая этой переменной, меньше заданной длины строки, то оставшиеся свободные места заполняются пробелами. При присвоении переменной строки, количество символов которой превышает максимальное значение, все лишние символы отбрасываются. Количество символов, хранящихся в строке с переменной длиной, определяется длиной присваиваемых ей данных.

Для хранения двоичных данных рекомендуется использовать массив переменных типа Byte. Каждый элемент  массива данного типа занимает один байт оперативной памяти.

Логический тип данных Boolean используется для хранения данных, принимающих одно из двух значений: True (Правда) или False (Ложь). По умолчанию переменной данного типа присваивается значение False. В оперативной памяти она занимает два байта.

Тип данных Date используется для хранения даты и времени. Переменная этого типа требует 8 байт в оперативной памяти.

Тип данных Variant является универсальным. Переменная этого типа может хранить любой из выше описанных  типов данных. Все необходимые  преобразования выполняются при  присвоении переменной значения. Выделяемый переменной объем оперативной памяти зависит от типа присвоенного значения, но не может быть менее 16 байт.

Для хранения ссылок на объекты  используется тип данных Object. Каждая переменная данного типа требует 4 байта.

Объявление переменных может быть явным или неявным. Для явного определения переменных существуют два способа. Первый способ предполагает использование следующего синтаксиса:

Static | Public | Private | Dim ИмяПеременной1 [As Тип1][, ИмяПеременной2 [As Тип2]]

Другим способом явного объявления переменных является указание типа с помощью суффикса. Явное объявление переменных с помощью суффикса имеет следующий синтаксис:

Static | Private | Public | Dim ИмяПеременнойСуффикс

Integer%;Long&;Single!;Double#;Currency@;String$;ByteНет;BooleanНет;DateНет;ObjectНет;VariantНет

Неявное объявление переменных осуществляется также двумя способами. Первый способ заключается в использовании оператора DefТип_Данных. Этот оператор устанавливает тип данных для переменных, параметров процедур и тип возвращаемого значения для процедур типа Function и Property Get, имена которых начинаются с определенных символов. Синтаксис оператора имеет вид:

DefТип_Данных ДиапазонБукв [, ДиапазонБукв]...

При втором способе неявного объявления переменная декларируется  просто указанием ее имени, в тексте программы.

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

Область действия переменных

Переменная может быть доступна для всей программы либо только для одной или нескольких ее частей. Область программы, в которой может быть использована переменная, называется областью видимости переменной. Переменные могут быть видимы в одной процедуре, в любой процедуре какой-либо формы или во всей программе. Если переменная видима, то она доступна и, следовательно, существует. Переменная может существовать и быть доступной для некоторых частей программы и при этом быть недоступной ("невидимой") для других частей программы.

Dim - объявляет локальные  переменные, существующие только  во время вызова процедур или функций, в которых они объявлены. Если переменная объявляется в разделе глобальных объявлений модуля или формы, то она доступна для всех процедур и функций этого модуля. Для других модулей она будет не видна;

Private - не может объявлять  переменную внутри процедуры или функции, при объявлении в разделе глобальных объявлений модуля Dim и Private равнозначны;

Public - объявленная таким  образом переменная является  глобальной на уровне приложения  и доступна из всех его модулей.

Различают динамические и статические переменные. Статические переменные объявляются внутри процедуры или функции и вне их недоступны. В отличие от обычных локальных переменных они не инициализируются при входе в процедуру или функцию, где они объявлены. Для создания статической переменной необходимо при ее объявлении вместо ключевого слова Dim указать слово Static:

Static intNumber As Integer

 

44.

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

Различают две категории  оптимизирующих преобразований:1)преобразование на уровне исходной программы в ее внутренней форме);2)преобразование на уровне объектной программы.

Преобразования первого  вида допустимы ко многим языкам высокого уровня:1)свертка, т.е. выполнение операций, операнды которых известны во время компиляции;2)исключение лишних операций;3)вынесение из циклов операций, операнды которых внутри цикла не меняются;4)замена в циклах сложных операций на более простые.

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

 

 

 

 

 

 

38.

Для хранения величин  кроме простых переменных можно  использовать массивы. Массив представляет собой набор переменных с одним  именем и разными индексами. Каждая такая переменная называется элементом  массива. Количество хранящихся в массиве элементов называется размером массива. Размер массива ограничен объемом оперативной памяти и типом данных элементов массива.

Все элементы массива  имеют одинаковый тип. Однако если массив имеет тип variant, то отдельные элементы могут содержать данные разных типов. Например, одни элементы могут быть числами, другие - строками или объектами. Индекс элемента указывается в круглых скобках после имени массива. Например, strNames(1), strNames(2), strNames(10) являются элементами массива с именем strNames. Можно использовать каждый из элементов массива точно так же, как и простую переменную.

Объявление массива

В Visual Basic существуют массивы  фиксированного размера и динамические массивы. Массив фиксированного размера  имеет неизменный размер, заданный при его объявлении. Динамические массивы могут изменять размер в процессе выполнения.

Объявление массива  фиксированного размера

Объявление массива  фиксированного размера зависит  от области его видимости и  осуществляется следующим образом:

- глобальный массив  объявляется с помощью оператора  Public в секции Declaration модуля;

- массив уровня модуля - с помощью оператора Private в  секции Declaration модуля;

- локальный массив - с  помощью оператора Private процедуры.

При объявлении массива  после его имени в круглых  скобках указывается верхняя  граница массива. По умолчанию нижней границей массива является 0. Например, в приведенном ниже коде, который  вводится в секцию Declaration модуля, задается массив из 21 элемента. Индекс элементов массива изменяется от 0 до 20:

Dim intCountPar (20) As Integer

Для создания глобального  массива такого же размера необходимо использовать следующий код:

Public intCountPar (20) As Integer

Можно явно задать нижнюю границу массива, используя ключевое слово To:

Dim intCountPar (1 To 20) As Integer

В этом случае задается массив из 20 элементов. Индекс элементов массива  изменяется от 1 до 20.

Visual Basic позволяет использовать  многомерные массивы. Например, в следующем коде объявляется двумерный массив размерностью 21x21:

Dim intCountPar (20, 20) As Integer

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

Dim intCountPar (1 To 20, 1 То 20) As Integer

Dim intCountPar (20, 1 Tо 20) As Integer

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

Объявление динамического  массива

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

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