Файл: ИНФОРМАТИКА 2-15.doc

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

8.Организация ввода-вывода в языках программирования. Работа с дисковыми файлами в языках программирования.

Turbo Pascal

Рассмотрим простейшие процедуры ввода и вывода. По умолчанию ввод осуществляется с клавиатуры, а вывод на экран. К операторам ввода относятся:

Read(<список переменных через запятую>);

Readln(<список переменных>);

Readln;

Второй отличается от первого тем, что после ввода переводит курсор на новую строку, точнее, в конце своей работы считывает с клавиатуры код клавиши <Enter>. Третий оператор используется для организации паузы - выполнение программы продолжится, как правило, только после нажатия на клавиатуре клавиши <Enter>.

К операторам вывода относятся:

Write(<список вывода>);

Writeln(<список вывода>);

Writeln;

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

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

ПРИМЕР: Простые вычисления.

program vvod_vyvod;

const n=1.5;

var y1,y2:real; x:byte;

begin

writeln('Введите натуральное число <= 255');

readln(x);

y1:=cos(n); y2:=cos(x);

write('Зачем-то посчитали: ');

writeln('n=',n,' y1=',y1:7:4, cos(Pi/2):8:4);

{напечатается

Зачем-то посчитали: n= 1.50000000000000E+0000

y1= 0.0707 1.0000}

writeln('x=',x:3,' y2=',y2:7:4);

end.

Visual Basic

Для ввода информации используется объект TextBox, для вывода информации – объект Label.

Возможен ввод информации с использованием объекта InputBox$ или InputBox:

Stroka=InputBox$(Prompt, Title, Default, Left,Top),

где

Prompt – строка-сообщение;

Title – заголовок окна;

Default – начальное значение;

Left,Top – координаты левого верхнего угла диалогового окна.

InputBox отличается от InputBox$ тем, что вместо строки выдает значение Variant.

A=InputBox$(“Введите значение”, “Ввод данных”, 0, 100, 200)

Для вывода информации можно использовать оператор MsgBox:

MsgBox Prompt, Option, Title

где

Option – целое число- информация о кнопках и других атрибутах окна;

MsgBox “Осторожно”, 32, “Внимание”

ФАЙЛЫ

Введение файлового типа в язык ПАСКАЛЬ вызвано необходимостью обеспечить возможность работы с периферийными (внешними) устройствами ЭВМ, предназначенными для ввода, вывода и хранения данных.

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

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

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

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

var tStory: Text;

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

TURBO PASCAL вводит ряд процедур и функций, применимых для любых типов файлов: Assign, Reset, Rewrite, Close, Rename, Erase, Eof, IOResult.

Процедура Assign( var f; FileName: String ) связывает логический файл f с физическим файлом, полное имя которого задано в строке FileName.

Процедура Reset( var f ) открывает логический файл f для последующего чтения данных или, как говорят, открывает входной файл. После успешного выполнения процедуры Reset файл готов к чтению из него первого элемента.

Процедура Rewrite( var f ) открывает логический файл f для последующей записи данных (открывает выходной файл). После успешного выполнения этой процедуры файл готов к записи в него первого элемента.

Процедура Close( var f ) закрывает открытый до этого логический файл. Вызов процедуры Close необходим при завершении работы с файлом.

Логическая функция EOF( var f ): Boolean возвращает значение TRUE, когда при чтении достигнут конец файла.

Процедура Rename( var f; NewName: String ) позволяет переименовать физический файл на диске, связанный с логическим файлом f. Переименование возможно после закрытия файла.

Процедура Erase( var f ) уничтожает физический файл на диске, который был связан с файловой переменной f. Файл к моменту вызова процедуры Erase должен быть закрыт.

Для описания текстовых файлов в языке определен стандартный тип Тext:

var TF1, TF2: Text;

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

С признаком конца строки связана функция EOLn(var T:Text):Boolean, где Т - имя текстового файла. Эта функция принимает значение TRUE, если достигнут конец строки, и значение FALSE, если конец строки не достигнут.

Для операций над текстовыми файлами, кроме перечисленных, определены также операторы обращения к процедурам:

ReadLn(T) - пропускает строку до начала следующей;

WriteLn(T) - завершает строку файла, в которую производится запись, признаком конца строки и переходит к началу следующей.

Для работы с текстовыми файлами введена расширенная форма операторов ввода и вывода. Оператор

Read(T,X1,X2,...,XK)

эквивалентен группе операторов

begin

Read(T,X1);

Read(T,X2);

...........

Read(T,XK)

end;

Здесь Т - текстовый файл, а переменные Х1, Х2,...ХК могут быть либо переменными целого, действительного или символьного типа, либо строкой. При чтении значений переменных из файла они преобразуются из текстового представления в машинное.

Оператор

Write(T,X1,X2,...XK)

эквивалентен группе операторов

begin

Write(T,X1);

Write(T,X2);

...........

Write(T,XK)

end;

Здесь Т - также текстовый файл, но переменные Х1,Х2,...ХК могут быть целого, действительного, символьного, логического типа или строкой. При записи значений переменных в файл они преобразуются из внутреннего представления в текстовый.

Процедура Append( var f: Text ) служит для специального открытия выходных файлов. Она применима к уже существующим физическим файлам и открывает их для дозаписи в конец файла.

Visual Basic

В Visual Basic наиболее часто используются файлы:

• последовательные (sequential), записи которых могут быть переменной длины;

• прямого доступа (random access), записи которых могут быть только одинаковой длины;

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

Open имя_файла For {Append | Input | Output} As #номер_фаила fLen ⁼{размер буфера памяти}

Input — файл открывается для ввода.

Output — файл открывается для вывода.

Append — устанавливает считывающе-записывающее устройство на конец файла и выводимая информация записывается в файл после существующих записей.

Имя_файла — имя файла (символьная константа или переменная) или путь.

Номер файла — целочисленное выражение, значение которого должно лежать в диапазоне от 1 до 255 (присваиваемый файлу номер).

Len — определяет размер буфера операций ввода-вывода (по умолчанию 512 Кб).

Примеры:

Open “С:\CONFIC.SYS” For Input As #5 'открывается

файл с именем CONFIG.SYS в директории С: для ввода

и ему присваивается номер 5

Doc$ = “a:\Utilits\NC.DOC”

присвоение значения константе

Open Doc$ For Input As #2

'открытие файла NC.DOC на диске А: в директории Utilits для ввода, файлу присваивается номер 2

Open “Resulc.txt“ For Output As #7

'открытие файла для вывода.

Если открывается для вывода несуществующий файл, то он создается при значениях параметров Append и Output. Если для ввода открывается несуществующий файл, то Visual Basic сообщает об ошибке.

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

Пример.

If Dir$(“FilePrim.Txt”) <> “” Then

Open “FilePrim.Txt” For Input As #12

End If

После завершения операций ввода — вывода файл должен быть закрыт. Для этого используется оператор

Close #номер_файла где Close — ключевое слово;

Для ввода информации из последовательного файла используется оператор

Line Input #номер_файла, имя_переменной где Line Input — ключевое слово;

имя_переменной — имя переменной, которая принимает значение записи файла, типа String или Variant.

Встроенная функция EOF (аббревиатура английских слов End Of File - конец файла) позволяет проверять при чтении файла: достигнут конец файла или нет.

Пример.

Dim FileYura, StrokaVvoda As String

Open FileYura For Input As #5

Do Until EOF(5)

Line Input #5, StrokaVvoda

Loop

Close #5

Для вывода информации в последовательный файл используется оператор

{Print | Write} #номер_файла, имя переменной

Print# — обеспечивает вывод в последовательный файл в формате дисплея.

Если выражения разделяются “;”, то в файл они записываются без пробелов слитно. Если выражения разделяются “,”, то в файл они записываются в фиксированные зоны длиной 14 символов (зонный формат).

Spc(n) и Таb(n) определяют соответственно вставку n пробелов между выводимыми выражениями и табуляцию на n колонок перед списком выражений.

Для удаления с дискового пространства неиспользуемого файла используется оператор Kill имя_файла где Kill — ключевое слово.

Файлы произвольного доступа по структуре похожи на файлы баз данных, поэтому лучше организовывать данный тип данных из СУБД.

9.Алгоритмы сортировки, сравнение алгоритмов сортировки. Последовательный и бинарный поиск.

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

Оценка алгоритма сортировки

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:

• Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = | A | . Для типичного алгоритма хорошее поведение — это ^[1] и плохое поведение — это . Идеальное поведение для упорядочения — . Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью , использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О-обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать n чисел за операций. При этом число n должно быть заранее известно;

• Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляет ). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.

Классификация алгоритмов сортировки

• Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов.(особенно полезна, если сортируются элементы с неск значениями по одному из них)

• Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

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

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

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

  • В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.

• Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т. е. в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.

Список алгоритмов сортировки

В этой таблице n — это количество записей, которые необходимо упорядочить, а k — это количество уникальных ключей.

Алгоритмы устойчивой сортировки

• Сортировка пузырьком (англ. Bubble sort ) — сложность алгоритма: O(n²); для каждой пары индексов производится обмен, если элементы расположены не по порядку.

• Сортировка перемешиванием (Шейкерная, Cocktail sort, bidirectional bubble sort) — Сложность алгоритма: O(n²)

• Сортировка вставками (Insertion sort) — Сложность алгоритма: O(n²); определяем где текущий элемент должен находиться в упорядоченном списке и вставляем его туда

• Сортировка с помощью двоичного дерева (англ. Tree sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти

Алгоритмы неустойчивой сортировки

• Сортировка выбором (Selection sort) — Сложность алгоритма: O(n²); поиск наименьшего или наибольшего элемента и помещения его в начало или конец упорядоченного списка

• Сортировка Шелла (Shell sort) — Сложность алгоритма: O(n log² n); попытка улучшить сортировку вставками

• Быстрая сортировка (Quicksort) — Сложность алгоритма: O(n log n) — среднее время, O(n²) — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине