аи. Лекции 6-7. Работа с текстовыми файлами. Тип запись. Алгоритмы сортировки

• Название: Работа с текстовыми файлами. Тип запись. Алгоритмы сортировки
• Дата: 19.11.2021
• Размер: 94 Kb.
• Имя файла: Лекции 6-7.doc
• Тип: Лекция; #276501

Лекция №6

1. Работа с текстовыми файлами. Тип запись. Алгоритмы сортировки

   1. Файловые типы

Рассмотрим только работу с текстовыми файлами. Файловые переменные для текстовых файлов описываются с помощью типа Text.

 Пример

VAR

F:Text;
Файловые переменные являются структурированными и содержат различную информацию, необходимую для работы с файлом на диске, с которым они связаны. Это имя файла, его размер, текущая позиция в файле и т.д. Если вы пишите процедуры или функции для работы с файлами, передавать в них файловые переменные можно только с модификатором VAR.

2. Процедуры и функции для работы с текстовыми файлами

Процедура или функция	Описание
Процедура Assign(F,<Имя>)	Назначает имя файла файловой переменной F
Процедура Reset(F)	Открывает файл для чтения. Если файла с назначенным именем нет, возникает ошибка ввода-вывода
Процедура Rewrite(F)	Создает файл и открывает его для записи. Если файл уже есть, он перезаписывается
Процедура Close(F)	Закрывает файл, открытый ранее процедурами Resetили Rewrite
Процедура Read[Ln](F,<Список переменных>)	Читает из файла значения указанных переменных. ReadLnпосле чтения значений пропускает все оставшиеся данные до конца текущей строки и переходит на следующую
Процедура Write[Ln](F,<Список значений>)	Работает, как и обычный оператор вывода, но данные записываются в текстовый файл, задаваемый переменной F
Функция Eof(F)	Возвращает истину, если достигнут конец файла при чтении

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

Входной файл (Test.txt)	→	Двумерный массив (A)				→	Выходной файл (Out.txt)
1.2 5 7.3 3.3 9 4 8 6 1.1 . . .			1	2	3		13.5 16.3 15.1 . . .
		1	1.2	5	7.3
		2	3.3	9	4
		3	8	6	1.1
		…	…

 Текст программы

VAR

F:Text;

n,i:Integer;

A:ARRAY [1..100,1..3] OF Real;

BEGIN

Assign(F,'Test.txt');

Reset(F);

n:=0;

WHILE NOT Eof(F) DO

BEGIN

Inc(n);

Readln(F,A[n][1],A[n][2],A[n][3]);

END;

Close(F);
Assign(F,'Out.txt');

Rewrite(F);

FOR i:=1 to n DO

Writeln(F,A[n][1]+A[n][2]+A[n][3]);

Close(F);

END.

3. Стандартные текстовые файлы

В языке Паскаль имеется два стандартных текстовых файла: Inputи Output.

Input– это файл для ввода, чтение из которого равносильно вводу данных с клавиатуры. Например, если в программе используется оператор ввода Readln(a,b), то он выполняется аналогично оператору Readln(Input,a,b).

Файл Output– стандартный текстовый файл для вывода, запись в который приводит к выводу данных на экран. Аналогично предыдущему оператор вывода Writeln(a,b) будет выполняться как Writeln(Output,a,b).

Файлы Inputи Outputможно использовать только в консольных приложениях.

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

Фамилия	Имя	Отчество	Факультет	Группа	…
Иванов	Петр	Николаевич	ММ	112	…
Петров	Иван	Алексеевич	ЭТ	2135	…
…	…	…	…	…	…

Каждый атрибут имеет свой тип. Как же можно описать такой список студентов в программе? Это можно сделать, например, с помощью нескольких массивов:

 Пример_D.Day:=23;_D.Month:=Oct;_D.Year:=2002;_S[5].Fam:=Иванов;_S[5].Fakultet:=MM;'>Пример_TYPE__Date=RECORD__Day:1..31;__Month:(Jan,Feb,Mar,…,Nov,Dec);__Year:Integer;__END;'>Пример_VAR__FIO:ARRAY_[1..100,1..3]_OF_STRING;__Fakultet:ARRAY_[1..100]_OF_(MM,RT,MT,_…_);__Group:ARRAY_[1..100]_OF_Integer;'>Пример

VAR

FIO:ARRAY [1..100,1..3] OF STRING;

Fakultet:ARRAY [1..100] OF (MM,RT,MT, … );

Group:ARRAY [1..100] OF Integer;
Такой способ во многих случаях является достаточно неудобным по целому ряду причин. Однако язык Паскаль позволяет описывать такие структуры по-другому.

4. Тип запись

 Синтаксис

RECORD

<Список имен 1>:<Тип 1>;

<Список имен 2>:<Тип 2>;

∙ ∙ ∙

<Список имен N>:<Тип N>;

END
При описании переменной типа «запись» в памяти создается последовательность переменных различного типа (сравните с типом массив, который описывает последовательность переменных одного типа).

 Пример

TYPE

Date=RECORD

Day:1..31;

Month:(Jan,Feb,Mar,…,Nov,Dec);

Year:Integer;

END;

Student=RECORD { К примеру со списком студентов}

Fam,Name,Pat:STRING;

Fakultet:(MM,RT,MT,FT, … );

Group:Integer;

END;

VAR

D:Date;

S:ARRAY [1..100] OF Student;

5. Обращение к элементам записи

Осуществляется с помощью оператора « . » (точка).

 Пример

D.Day:=23;

D.Month:=Oct;

D.Year:=2002;

S[5].Fam:='Иванов';

S[5].Fakultet:=MM;
Переменные одного и того же типа «запись» можно присваивать друг другу:

 Пример

S[4]:=S[5];
Таким образом, тип «запись» позволяет группировать данные различного типа в одной переменной (или, например, в одном элементе
массива).

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

Лекция №7

2. Алгоритмы сортировки

   1. Алгоритмы сортировки

Все алгоритмы сортировки можно поделить на две группы: сортировка сравнениями и лексикографическая сортировка. Эти два вида алгоритмов отличаются тем, что при сортировке сравнениями неизвестна внутренняя структура объектов. При этом они вообще могут иметь различную структуру, необходимо только уметь сравнивать объекты друг с другом (например, числа). На самом деле только одного сравнения объектов недостаточно, оно должно обладать еще некоторыми дополнительными свойствами, например транзитивностью, т.е. если a<bи b<c, то должно быть a<c. Предположим, что мы должны сравнивать вектора фактически являющиеся парами чисел вида r=(x,y). Определим операцию сравнения двух объектов r₁=(x₁,y₁) и r₂=(x₂,y₂) так: r₁<r₂тогда и только тогда, когда x₁<x₂или y₁<y₂. Удовлетворяет ли такое сравнение вышеприведенному условию? Возьмем 3 вектора: a=(3,9), b=(4,7), c=(1,8). По описанному способу сравнения получаем: a<b, b<c, но aне меньше c. Таким образом, при выборе этого отношения порядка не в каждом случае можно упорядочить заданную последовательность элементов.

Лексикографическая сортировка обычно применяется при сортировке объектов с известной внутренней структурой. Например, упорядочивание текстовых строк по алфавиту. Внутренняя структура строк известна: строка состоит из символов; количество символов алфавита ограничено.

2. Алгоритмы сортировки сравнениями

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

 Алгоритм «Пузырьковая сортировка»

1. Повторять:

А. Для всех элементов списка, кроме последнего, повторять:

1. Если текущий элемент больше следующего, то поменять их местами.

2. Конец цикла при условии, что ни одной замены не произошло.
Проиллюстрируем работу алгоритма на примере последовательности из 5-ти чисел: 5, 3, 1, 4, 2. Работа алгоритма пузырьковой сортировки проиллюстрирована на следующем рисунке.

►	5┐		3		3		3		3		►	3┐		1		1		1		1		►	1		1		1		1		1
	3┘	►	5┐		1		1		1			1┘	►	3		3		3		3			3	►	3┐		2		2		2
	1		1┘	►	5┐		4		4			4		4	►	4┐		2		2			2		2┘	►	3		3		3
	4		4		4┘	►	5┐		2			2		2		2┘	►	4		4			4		4		4	►	4		4
	2		2		2		2┘		5			5		5		5		5		5			5		5		5		5		5

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

 Алгоритм «Пузырьковая сортировка»

1. Присвоить переменной kколичество элементов списка.

2. Повторять:

А. Уменьшить kна 1.

Б. Для первых kэлементов списка повторять:

1. Если текущий элемент больше следующего, то поменять их местами.

3. Конец цикла, при условии, что ни одной замены не произошло.
Сколько времени будет выполняться такая сортировка? За элементарную операцию примем операцию сравнения двух элементов и подсчитаем, сколько таких операций необходимо произвести, если дан список из nэлементов. На каждом шаге будет просматриваться на один элемент меньше. В худшем случае (когда исходный массив отсортирован по убыванию) каждый раз будет производиться хотя бы один обмен элементов, пока не останется только один элемент, и сортировку не закончится. На первом шаге будет сделано n-1 сравнение, на втором n-2 сравнения, и т.д. до одного сравнения. Итого, имеем арифметическую прогрессию от 1 до n-1 с n-1 элементом. Сумма этой прогрессии:

.

При больших значениях nэта функция ведет себя как n². В таком случае говорят, что вычислительная сложность алгоритма равна O(n²). Эта оценка вычислительной сложности алгоритма называется асимптотической. Такая оценка обычно является достаточно плохой. Возникают вопросы: можно ли написать алгоритм, который будет работать быстрее и какой самый быстрый алгоритм вообще можно написать? Ответ – можно, и это . Невозможно написать более быстрый алгоритм сортировки сравнениями. Для лексикографической сортировки наиболее быстрый алгоритм имеет вычислительную сложность .

При сортировке для обмена элементов списка можно использовать дополнительную переменную.

 Пример (см. пример из параграфа 6.4)

VAR

Temp:Student;

k,i:Integer;

Stop:Boolean;

. . .

{ Сортировка массива S со списком студентов по
фамилии. Пусть длина списка задана переменной n }

k:=n;

REPEAT

Dec(k);

Stop:=True;

FOR i:=1 TO k DO

IF S[i].Name>W[i+1].Name THEN

BEGIN

Temp:=S[i];

S[i]:=S[i+1];

S[i+1]:=Temp;

Stop:=False;

END;

UNTIL Stop;