Рис.5.3. Структура элемента разветвленного списка
Элементы списка могут быть двух видов: атомы - содержащие данные и узлы - содержащие указатели на подсписки. В атомах не используется поле down элемента списка, а в узлах - поле data. Поэтому логичным является совмещение этих двух полей в одно, как показано на рис.5.4.
| type | data/down | next |
Рис.5.4. Структура элемента разветвленного списка
Поле type содержат признак атом/узел, оно может быть 1-битовым. Такой формат элемента удобен для списков, атомарная информация которых занимает небольшой объем памяти. В этом случае теряется незначительный объем памяти в элементах списка, для которых не требуется поля data. В более общем случае для атомарной информации необходим относительно большой объем памяти. Наиболее распространенный в данной ситуации формат структуры узла представленный на рис.5.5.
| type | down | next |
Рис. 5.5. Структура элемента разветвленного списка
В этом случае указатель down указывает на данные или на подсписок. Поскольку списки могут составляться из данных различных типов, целесообразно адресовать указателем down не непосредственно данные, а их дескриптор, в котором может быть описан тип данных, их длина и т.п. Само описание того, является ли адресуемый указателем данных объект атомом или узлом также может находиться в этом дескрипторе. Удобно сделать размер дескриптора данных таким же, как и элемента списка.
Операции обработки списков
Базовыми операциями при обработке списков являются операции (функции): car, cdr, cons и atom.
Операция car в качестве аргумента получает список (указатель на начало списка). Ее возвращаемым значением является первый элемент этого списка (указатель на первый элемент).
Операция cdr в качестве аргумента также получает список. Ее возвращаемым значением является остаток списка - указатель на список после удаления из него первого элемента. Например:
Операция cons имеет два аргумента: указатель на элемент списка и указатель на список. Операция включает аргумент-элемент в начало аргумента-списка и возвращает указатель на получившийся список.
|
|
Операция atom выполняет проверку типа элемента списка. Она должна возвращать логическое значение: true - если ее аргумент является атомом или false - если ее аргумент является подсписком.
Стек и очередь
Дата добавления: 2014-02-04; просмотров: 4.
Begin
Begin
if (p<> nil) and (p^.next<>p) then begin
q:=p^.next^.next;
dispose(p^.next);
p^.next:=q;
q^.prev:=p;
end;
end;
{Вставить перед указанным:}
procedure InsertBefore(p: tItemPtr; d: tData);
var q: tItemPtr;
if p<> nil then begin
new(q);
q^.data:=d;
q^.next:=p;
q^.prev:=p^.prev;
p^.prev:=q;
q^.prev^.next:=q;
end;
end;
Стеком называется такой способ хранения данных, при котором элемент, записанный в хранилище данных, последним всегда извлекается первым (дисциплина LIFO – «last in - first out»). При извлечении элемента происходит его удаление со стека.
Рассмотрим простейший пример использования стека. Предположим, что имеется строка, состоящая из одних лишь открывающих и закрывающих скобок. Требуется определить, является ли она правильным скобочным выражением (то есть для каждой открывающей скобки должна найтись закрывающая). Заведём массив и переменную для хранения номера последнего значимого элемента в массиве (то есть вершины стека), в который при проходе по строке будем складывать все открывающиеся скобки (с увеличением номера вершины на 1), а при встрече с закрывающей будем удалять соответствующую открывающую (попросту уменьшать номер вершины стека). Если окажется, что «пришла» закрывающая скобка, а стек пуст (то есть номер вершины равен 0), то выражение ошибочно. Это же можно сказать и в случае, когда строка закончилась, а стек не пуст.
Очевидно, что для реализации такого стека массив использовать не обязательно, достаточно хранить в некоторой переменной лишь число открывающих скобок. При поступлении закрывающей скобки из этой переменной вычитается 1. Ошибка возникает, если значение переменной стало отрицательным, или при достижении конца строки оно не равно нулю.
Для данных более сложного вида стек можно организовать с помощью однонаправленного некольцевого списка. Чтобы положить элемент в стек, нужно добавить его в начало списка, чтобы извлечь со стека – получить данные первого элемента, после чего удалить его из списка.
|
|
Любая реализация стека должна содержать следующие процедуры и функции:
procedure InitStack – инициализация стека;
procedure Push(d: tData) – положить элемент в стек;
procedure Pop(var d: tData) – извлечь элемент с вершины стека;
function NotEmpty: boolean – проверка стека на пустоту;
Очередь отличается от стека тем, что последний пришедший в неё элемент будет извлечён последним, а первый – первым («FIFO»). С помощью списков её можно организовать следующим образом: будем хранить не только указатель на «голову» списка, но и на «хвост»; добавлять будем в «хвост», а извлекать – из «головы».
Любая реализация очереди (не обязательно с помощью списков) должна «уметь» выполнять такие действия:
procedure InitQueue – инициализация очереди;
procedure AddQueue(d: tData) – поставить элемент в очередь;
procedure SubQueue(var d: tData) – извлечь элемент из очереди;
function NotEmpty: boolean – проверка очереди на пустоту;
Системы программирования
Дата добавления: 2013-12-23; просмотров: 5.
Транслятором языка программирования называется программа, осуществляющая перевод текста программы с языка программирования в (как правило) машинный код. Комплекс средств, включающих в себя входной язык программирования, транслятор, машинный язык, библиотеки стандартных программ, средства отладки оттранслированных программ и компоновки их в единое целое, называется системой программирования. В системе программирования транслятор переводит программу, написанную на входном языке программирования, на язык машинных команд конкретной ЭВМ. В зависимости от способа перевода с входного языка (языка программирования) трансляторы подразделяются на компиляторы и интерпретаторы. В компиляции процессы трансляции и выполнения программы разделены во времени. Сначала компилируемая программа преобразуется в набор объектных модулей на машинном языке, которые затем собираются (компонуются) в единую машинную программу, готовую к выполнению и сохраняемую в виде файла на магнитном диске. Эта программа может быть выполнена многократно без повторной трансляции. Интерпретатор осуществляет пошаговую трансляцию и немедленное выполнение операторов исходной программы: каждый оператор входного языка программирования транслируется в одну или несколько команд машинного языка, которые тут же выполняются без сохранения на диске. Таким образом, при интерпретации программа на машинном языке не сохраняется и поэтому при каждом запуске исходной программы на выполнение ее нужно (пошагово) транслировать заново. Главным достоинством интерпретатора по сравнению с компилятором является простота. Входной язык программирования называется языком высокого уровня по отношению к машинному языку, называемому языком низкого уровня. Особое место в системе программирования занимают ассемблеры, представляющие собой комплекс, состоящий из входного языка программирования ассемблера и ассемблер―компилятора. Ассемблер представляет собой мнемоническую (условную) запись машинных команд и позволяет получить высокоэффективные программы на машинном языке. Однако его использование требует высокой квалификации программиста и больших затрат времени на составление и отладку программ.
Наиболее распространенными языками программирования являются: Pascal, Basic, C++, Fortran и др. Тенденции развития ― появление языков четвертого поколения типа Visual Basic. |
Языки программирования
Дата добавления: 2014-02-04; просмотров: 5.
Компьютерной программой называется совокупность инструкций, направленных на решение конкретной задачи. Каждый тип ЭВМ имеет свой набор команд, из которых может состоять программа для данного типа ЭВМ – машинный код. Машинный код состоит из последовательности инструкций, которые хранятся двоичном виде. Так как для человека такой вид представления инструкций не удобен было разработано большое число различных языков программирования. Языки программирования – это искусственные языки, созданные человеком для целей описания алгоритмов обработки данных. Все языки программирования разделяют на два основных вида. Языки низкого уровня (Машино-ориентированные языки) – это средство записи инструкций программы простыми командами на аппаратном уровне. Такие языки зависят от набора команд конкретной ЭВМ. Для упрощения программирования были разработаны языки символического кодирования – ассемблеры. Программа на таком языке содержит вместо двоичных кодов символические обозначения команд ЭВМ, данных и адресов памяти. Языки высокого уровня (Машино-независимые языки) – средство записи программы в наглядном, легко воспринимаемом виде. Каждый язык ВУ ориентирован не на систему команд конкретной ЭВМ, а на систему инструкций, характерных для записи алгоритмов определенного класса. Обычно в состав инструкций входят слова английского языка, что упрощает понимание смыла конкретной инструкции. К современным ЯВУ относятся BASIC, Pascal, C, Java. Существуют также языки сверхвысокого уровня, в которых формализуется описание языка и используются сверхмощные конструкции и операторы. Это такие языки как Algol-68, APL и в некоторой степени XML. Программа на любом языке программирования состоит из инструкций понятных программисту, но не понятных процессору ЭВМ. Для того чтобы процессор мог выполнить программу, программа должна быть переведена (транслирована) в машинный код. Такой перевод выполняется специальными программами трансляторами. Транслятор – программа, осуществляющая перевод программы с определенного языка программирования в машинный код конкретной ЭВМ.
Существуют три вида трансляторов. Ассемблеры – трансляторы, предназначенные для перевода программы, написанной на языке ассемблера в машинный код. Интерпретатор - трансляторы, переводящие текст программы поэтапно (покомандно) и сразу же выполняющие оттранслированную команду программы. Современные интерпретаторы – Microsoft Visual Basic, InternetExplorer (интерпретатор языка HTML), интерпретатор языка PHP. Компилятор – транслирует весь текст программы с языка программирования в машинный код. Современные компиляторы – Microsoft Visual C++, Borland Delphi, Borland C++ Builder. Компилятор выполняет следующие основные задачи: - Выполняет анализ и проверяет синтаксис транслируемой программы, и, в случае обнаружения синтаксической ошибки, прерывает свою работу и выдает соответствующее сообщение. - Генерирует машинный код программы Существует разновидность компиляторов, которые транслируют программу не в машинный код, а в специальный виртуальный код, который может быть выполнен при помощи специальной программы-интерпретатора, называемым виртуальным процессором. Преимущества такого метода трансляции заключается в том, что такая программа может выполняться на различных типах ЭВМ, для которых создан виртуальный процессор. Недостатком является более низкая производительность программ оттранслированных в виртуальный код, по сравнению с программами оттранслированных в машинный код. Областями использования таких программ являются места, где используются различные типы процессоров – Интернет (языки Visual Basic и Java) и сотовые телефоны (язык Java). Примерами таких компиляторов являются Microsoft Visual Basic, Microsoft Visual Java, Borland Java Builder. |
31.
| Компоненты ЭВМ можно разделить на 4 основные категории: процессор, оперативная память, внешняя память и прочие внешние устройства. Последние позволяют компьютеру обмениваться информацией с человеком и другими компьютерами, управлять технологическими процессами и т. д. Главная компонента компьютера — процессор. Процессор обеспечивает обработку данных, передачу данных, управление различными устройствами. Процессор имеет собственный достаточно сложный «язык» и может выполнять фиксированный набор действий-команд. Последовательность команд, записанная на языке процессора и переданная ему для исполнения, называется машинной программой. Процессор имеет свою сверхбыструю память, которая называется регистрами процессора. Минимальный элемент памяти (бит) способен хранить минимально возможный объем информации — одну двоичную цифру. Биты в памяти любого вида объединяются в байты — восьмерки битов. Принято для именования байтов использовать неотрицательные целые числа и говорить о номерах или адресах байтов. Процессор мол-сет прочитать нечто из байта памяти с адресом /V или записать нечто в этот байт. Для этого от процессора к памяти должен поступить адрес байта, а сам байт информации должен быть передан от процессора к памяти (при записи) или от памяти к процессору (при чтении). Эта информация передается по проводам. Провода разделены на два пучка, называемые шинами. Одна часть проводов называется шина адреса, другая — шина данных. Адрес байта передается по шине адреса, а байт — по шине данных. Число проводов в шине данных называется разрядностью шины. Обычно разрядность равна 8, 16, 32 или 64. Говорят, что процессор и память обслуживаются шиной. Шина может обслуживать и другие компоненты ЭВМ. Эти компоненты подсоединяются не к процессору или к памяти, а к шине. Каждому устройству отводится несколько уникальных адресов, и все устройства на шине общаются с процессором (и между собой) с помощью стандартных команд чтения и записи по адресам, отведенным устройству. |
32. Устройства внешней памяти
|
|
Назначение и виды внешней памяти. Классическая функция внешней памяти состоит в том, чтобы сохранять информацию для повторного использования. Отсюда следует, что всю информацию целесообразно хранить во внутреннем двоичном представлении, т. к. это позволяет в случае необходимости немедленно обрабатывать её без всяких дополнительных преобразований.
Внешние запоминающие устройства (ВЗУ) можно разделить на следующие классы:
по типу доступа:
ü с произвольным доступом (диски, флэш-карты);
ü с последовательным доступом (ленты);
по используемой технологии записи/считывания информации:
ü с магнитными носителями (НЖМД, НГМД);
ü с оптическими носителями (CD, DVD);
ü с магнитооптическими носителями;
ü использующие флэш-память;
по типу носителя:
ü с постоянным носителем (жесткие диски);
ü со сменными носителями (гибкие диски, картриджи стримеров, сменные пакеты жестких дисков).
Внешняя память на бумажных носителях. (Из истории ВТ)
Если рассматривать разнообразные устройства внешней памяти в историческом аспекте, следуя той последовательности, в которой они появились, то первыми следует упомянуть бумажные носители: перфоленты и перфокарты, на которых единица кодировалась пробивкой отверстия, а ноль – его отсутствием. Информация на бумажных носителях не могла быть повторно перезаписана, а поиск информации в архивах производился оператором «вручную». Перфокарты еще использовались в машинах третьего поколения.
