ОСНОВЫ ПРОГРАММИРОВАНИЯ_2014. Учебное пособие для 1го курса оглавление Оглавление 2 основы программирования 2 Введение 2
 Скачать 4.81 Mb.
|
3.18. Понятие множества. Множественный тип данныхОдним из фундаментальных разделов математики является теория множеств. Некоторые моменты математического аппарата этой теории реализованы в Паскале через множественный тип данных (множества). Множеством называется совокупность однотипных элементов, рассматриваемых как единое целое. В Паскале могут быть только конечные множества. В Турбо Паскале множество может содержать от 0 до 255 элементов. В отличие от элементов массива элементы множества не пронумерованы, не упорядочены. Каждый отдельный элемент множества не идентифицируется, и с ним нельзя выполнить какие-либо действия. Действия могут выполняться только над множеством в целом. Тип элементов множества называется базовым типом. Базовый тип может быть любым скалярным, за исключением типа Real. Конструктор множества. Конкретные значения множества задаются с помощью конструктора множества, представляющего собой список элементов, заключенный в квадратные скобки. Сами элементы могут быть либо константами, либо выражениями базового типа. Вот несколько примеров задания множеств с помощью конструктора: [3,4,7,9,12] — множество из пяти целых чисел; [1.. 100] — множество целых чисел от 1 до 100; ['a','b','c'] — множество, содержащее три литеры а, Ь, с; ['a'.,'z','?','!'] — множество, содержащее все прописные латинские буквы, а также знаки ? и !. Символы [] обозначают пустое множество, т.е. множество, не содержащее никаких элементов. Не имеет значения порядок записи элементов множества внутри конструктора. Например, [1,2,3] и [3,2,1] эквивалентные множества. Каждый элемент в множестве учитывается только один раз. Поэтому множество [1,2,3,4,2,3,4,5] эквивалентно [1.. 5 ]. Переменные множественного типа описываются так: Var <идентификатор>: Set Of <базовый тип> Например: Var A,D: Set Of Byte; В: Set Of ' a' . . ' z; C: Set Of Boolean; Нельзя вводить значения во множественную переменную оператором ввода и выводить оператором вывода. Множественная переменная может получить конкретное значение только в результате выполнения оператора присваивания следующего формата: <множественная переменная>: <множественное выражение> Например: А:=[50,100,150,200]; B:=['m', 'n','k']; С:=[True,False] ; D:=A; Кроме того, выражения могут включать в себя операции над множествами. Операции над множествами. В Паскале реализованы основные операции теории множеств. Это объединение, пересечение, разность множеств. Во всех таких операциях операнды и результаты есть множественные величины одинакового базового типа. Объединение множеств. Объединением двух множеств А и В называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из множеств А или В. Знак операции объединения в Паскале +. На рис. 34, а схематически показан результат объединения двух множеств. Например: [1,2,3,4]+[3,4,5,6]→[1,2,3,4,5,6] Пересечение множеств. Пересечением двух множеств А и В называется множество, состоящее из всех элементов принадлежащих, одновременно множеству А и множеству В (см. рис. 34, б) Знак операции пересечения в Паскале *. Например: [1,2,3,4]*[3,4,5,6]→[3,4] Разность множеств. Разностью двух множеств А и В называется множество, состоящее из элементов множества А, не принадлежащих множеству В (см. рис. 34, в). Например: [1,2,3,4]-[3,4,5,6]→[1,2] [3,4,5,6]-[1,2,3,4]→[5,6]  Очевидно, что операции объединения и пересечения — перестановочны, а разность множеств — не перестановочная операция. Операции отношения. Множества можно сравнивать между собой, т.е. для них определены операции отношения. Результатом отношения, как известно, является логическая величина true или false. Для множеств применимы все операции отношения, за исключением > и <. В таблице описаны операции отношения над множествами. Предполагается, что множества А и В содержат элементы одного типа.  Вот несколько примеров использования операций отношения. Пусть переменная м описана в программе следующим образом: Var М: Set Of Byte; В разделе операторов ей присваивается значение: М:=[3,4,7,9]; Тогда операции отношения дадут следующие результаты: М=[4,7,3,3,9] - true, М<>[7,4,3,9] - false, [3,4]<=М - true, []<=M — true, M>=[1..10] - false, M<=[3..9] - true. Операция вхождения. Это операция, устанавливающая связь между множеством и скалярной величиной, тип которой совпадает с базовым типом множества. Если х — такая скалярная величина, а M — множество, то операция вхождения записывается так: X In M Результат — логическая величина true, если значение х входит в множество M, и false — в противном случае. Для описанного выше множества 4 In M — true, 5 In М - false. Рассмотрим несколько задач, для решения которых удобно использовать множества. Пример 1. Дана символьная строка. Подсчитать в ней количество знаков препинания (. - , ; : ! * ?). Program P1; Var S: String; I,K: Byte; Begin ReadLn(S); K:=0; For I:=1 To Length(S) Do If S[I] In ['.','-',',',';',':', '!', '*','?'] Then K:=K+1; WriteLn('Число знаков препинания равно',К) End. В этом примере использована множественная константа с символьным типом элементов. Эту задачу можно решить и без множества, записав в операторе If длинное логическое выражение: (S[l]='.') Or (S[l]='-') и т.д. Использование множества сокращает запись. Пример 2. Даны две символьные строки, содержащие только строчные латинские буквы. Построить строку S3, в которую войдут только общие символы S1 и S2 в алфавитном порядке и без повторений. Program Р2; Type Mset=Set Of 'a'..'z'; Var S1,S2,S3: String; MS1,MS2,MS3: Mset; C: Char; Procedure SM(S: String; Var MS: Mset); {Процедура формирует множество MS, содержащее все символы строки S} Var I: Byte; Begin MS:=[] ; For I:=1 To Length(S) Do MS:=MS+[S[I]] End; Begin {Ввод исходных строк) ReadLn(S1);ReadLn(S2); {Формирование множеств MS1 и MS2 из символов строк S1 и S2) SM(S1,MS1);SM(S2,MS2); {Пересечение множеств - выделение общих элементов в множество MS3} MS3:=MS1*MS2; {Формирование результирующей строки S3) S3:="; For С: ='а' То 'z' Do If С In MS3 Then S3:=S3+C; WriteLn('Результат:',S3) End. Пример 3. Составить программу, по которой из последовательности натуральных чисел от 2 до N (1 < N ≤ 255) будут выбраны все простые числа. Для решения задач такого типа существует алгоритм, известный под названием «Решето Эратосфена». Суть его в следующем: 1. Из числовой последовательности выбираем минимальное значение, это будет простое число. 2. Удаляем из последовательности все числа, кратные выбранному. 3. Если после удаления последовательность не стала пустой, то возвращаемся к выполнению пункта 1. Вот пример работы такого алгоритма для N = 15 (подчеркнуты выбранные простые числа): 2 3 4 5 6 7 8 9 10 11 12 13 14 15 3 5 7 9 11 13 15 5 7 11 13 7 11 13 11 13 13 Решение этой задачи удобно программировать, используя множественный тип. Program Eratosfen; Const N=201; {Возможно любое значение 1 Var А,В: Set Of 2..N; K,P: Integer; Begin {Формирование исходного множества А; В - искомое множество простых чисел, сначала - пустое} A:=[2..N]; В:=[]; Р:=2; Repeat {Поиск минимального числа в множестве А} While Not(P In A) Do Р:=Р+1; {Включение найденного числа в множество В) В:=В+[Р]; К:=Р; {Исключение из А чисел, кратных Р} While K<=N Do Begin A:=A-[K]; K:=K+P; End Until A= [ ] ; {Вывод результата, т.е. всех чисел из множества В в порядке возрастания} For Р:=2 То N Do If P In В Then WriteLn(P) End. Красивая программа! К сожалению, ею нельзя воспользоваться для N > 255 из-за отмеченного выше ограничения на максимальный размер множества в Турбо Паскале. Пример 4. Как уже говорилось, нельзя вводить значения непосредственно в множество. Однако такая потребность у программиста может возникнуть. В этом случае можно прибегнуть к процедуре INSET, описанной ниже. Для примера рассматривается множество с символьным базовым типом. Предполагается, что в основной программе глобально объявлен тип SetChar. Type SetChar: Set Of Char; Procedure INSET(Var M: SetChar); Var I,N: Byte; C: Char; Begin Write('Укажите размер множества:'); ReadLn(N); M:=[]; For I:=l To N Do Begin Write(1:1,'-и элемент:'); ReadLn(С); M:=M+[C] End; WriteLn('Ввод завершен!') End. В основной программе для ввода значений в множество, например с именем sim, достаточно записать оператор: INSET (SIM); Произойдет диалоговый ввод значений. 3.19. Файлы. Файловые переменныеС термином «файл» вам уже приходилось встречаться. Прежде всего это понятие обычно связывают с информацией на устройствах внешней памяти. В Паскале понятие файла употребляется в двух смыслах: • как поименованная информация на внешнем устройстве (внешний файл); • как переменная файлового типа в Паскаль-программе (внутренний файл). В программе между этими объектами устанавливается связь. Вследствие этого все, что происходит в процессе выполнения программы с внутренним файлом, дублируется во внешнем файле. С элементами файла можно выполнять только две операции: читать из файла и записывать в файл. Файловый тип переменной — это структурированный тип, представляющий собой совокупность однотипных элементов, количество которых заранее (до исполнения программы) не определено. Структура описания файловой переменной: Var <имя переменной>: File Of <тип элемента>; где <тип элемента> может быть любым, кроме файлового. Например: Var Fi: File Of Integer; Fr: File Of Real; Fc: File Of Char; Файл можно представить как последовательную цепочку элементов (эл.), пронумерованных от 0, заканчивающуюся специальным кодом, называемым маркером конца (<м. к.>):  Количество элементов, хранящихся в данный момент в файле, называется его текущей длиной. Существует специальная ячейка памяти, которая хранит адрес элемента файла, предназначенного для текущей обработки (записи или чтения). Этот адрес называется указателем или окном файла. Для того чтобы начать запись в файл, его следует открыть для записи. Это обеспечивает процедура Rewrite (FV); где FV — имя файловой переменной. При этом указатель устанавливается на начало файла. Если в файле есть информация, то она исчезает. Схематически выполнение процедуры Rewrite можно представить так:  Стрелка внизу отмечает позицию указателя. Запись в файл осуществляется процедурой Write (FV, V); где V — переменная того же типа, что и файл FV. Запись происходит туда, где установлено окно (указатель). Сначала записывается значение, затем указатель смещается в следующую позицию. Если новый элемент вносится в конец файла, то сдвигается маркер конца. Схема выполнения оператора:  Пример 1. В файловую переменную Fx занести 20 вещественных чисел, последовательно вводимых с клавиатуры. Var Fx: File Of Real; X: Real; I: Byte; Begin Rewrite(Fx); For I:=1 To 20 Do Begin Write ('?'); ReadLn(X); Write(Fx,X) End End. Для чтения элементов файла с его начала следует открыть файл для чтения. Это делает процедура Reset (FV). В результате указатель устанавливается на начало файла. При этом вся информация в файле сохраняется. Схема выполнения процедуры:  Чтение из файла осуществляется процедурой Read (FV,V); где V — переменная того же типа, что и файл FV. Значение текущего элемента файла записывается в переменную V; указатель смещается к следующему элементу.  Доступ к элементам файла может быть последовательным или прямым. В стандартном Паскале реализован только последовательный доступ. Принцип последовательного доступа: для того чтобы прочитать п-ю запись файла, сначала нужно прочитать все предыдущие записи с 1-й по (п-1)-ю. Пример 2. В переменной х получить 10-й элемент вещественного файла Fx. Program А; Var Fx: File Of Real; X: Real; Begin Reset(Fx) ; For I:=l To 10 Do Read(Fx,X) End. Функция Eof (FV) проверяет маркер конца файла (end of file). Это логическая функция, которая получает значение true, если указатель установлен на маркер конца, в противном случае — false. Пример 3. Просуммировать все числа из файла Fx, описанного в предыдущем примере. Reset(Fx) ; Sx:=0; While Not Eof(Fx) Do Begin Read(Fx,X) ; Sx:=Sx+X End; To же самое с помощью цикла Repeat можно делать следующим образом: Repeat Read(Fx,X); Sx:=Sx+X Until Eof(Fx); Во втором варианте возможна ошибка чтения, если файл Fx пустой. Первый вариант от такой ошибки застрахован, поэтому он более предпочтителен. Внешние файлы. В Турбо Паскале все внешние устройства (дисплей, клавиатура, принтер, диски и т.д.) трактуются как логические устройства с файловой структурой организации данных. Все немагнитные внешние устройства однофайловые. Иначе говоря, с каждым из них связан один файл со стандартным именем, предназначенный для обмена с внутренней памятью ЭВМ текстовой (символьной) информацией. Стандартные имена логических устройств определяются операционной системой, в среде которой работает Паскаль. В системе MS DOS определены следующие имена: CON (консоль) — логическое устройство, связанное при вводе с клавиатурой, при выводе — с экраном; PRN (принтер) — логическое имя файла, связанного с устройством печати; AUX — логическое имя коммуникационного канала, который используется для связи ПК с другими машинами; INPUT — логическое имя стандартного устройства ввода, связанного с клавиатурой; при этом вводимые с клавиатуры символы отражаются на экране дисплея; OUTPUT — логическое имя стандартного устройства вывода на экран. Магнитный диск (МД) - многофайловое устройство. На нем хранятся как стандартные (системные) файлы, так и файлы, создаваемые пользователем. На магнитном диске могут создаваться файлы любых типов. Файлы на МД используются как в режиме чтения, так и в режиме записи. Список файлов на диске хранится в директории (каталоге) диска. Каталог вызывается на экран системной командой DIR. В полной форме каталог содержит идентификаторы файлов, объем занимаемой памяти, дату и время создания файла. Идентификатор файла состоит из имени и типа файла: <имя файла>.<тип файла> Имя содержит от 1 до 8 латинских букв и (или) цифр; тип — необязательный элемент (от 0 до 3 символов), указывающий на характер информации, хранимой в файле. Например: PROGRAM. PAS — в файле текст программы на Паскале; NUMBER. DAT — файл числовых данных; NAMES. ТХТ — текстовый файл. Для организации связи между файловой переменной и внешним файлом в Турбо Паскале используется процедура назначения: Assign (<имя файловой переменной>, <идентификатор внешнего файла>); Здесь <идентификатор внешнего файла> — строковая величина (константа или переменная). Например: Assign(Fi,'Number.dat'); После выполнения процедур Assign и Rewrite создается новый внешний файл, имя которого заносится в директорию. Если файл открывается для чтения (Assign и Reset), то в указанном каталоге уже должен содержаться указанный внешний файл. В противном случае будет обнаружена ошибка. Работа с файлом в программе завершается его закрытием с помощью процедуры Close (<имя файловой, переменной>) Например: Close(Fi) Подведем итог. Для создания и заполнения файла требуется следующая последовательность действий: 1. Описать файловую переменную. 2. Описать переменную того же типа, что и файл. 3. Произвести назначение (Assign). 4. Открыть файл для записи (Rewrite). 5. Записать в файл данные (Write). 6. Закрыть файл (Close). Пример 4. Создать файл, содержащий среднесуточные температуры за некоторое количество дней. При этом необязательно предварительно указывать количество чисел во вводимой информации Можно договориться о каком-то условном значении, которое будет признаком конца ввода. Пусть, например, признаком конца ввода будет число 9999. Program Taskl; Var Ft: File Of Real; T: Real; Begin Assign(Ft,'Temp.dat'); Rewrite(Ft); WriteLn('Вводите данные. Признак конца - 9999'); ReadLn(T); While T<>9999 Do Begin Write(Ft,T); Write ('?'); ReadLn(T) End; WriteLn ('Ввод данных закончен"); Close(Ft) End. В результате работы этой программы на диске будет создан файл с именем Temp. dat, в котором сохранится введенная информация. Для последовательного чтения данных из файла требуется выполнить следующие действия: 1. Описать файловую переменную. 2. Описать переменную того же типа. 3. Выполнить назначение (Assign). 4. Открыть файл для чтения (Reset). 5. В цикле читать из файла (Read). 6. Закрыть файл (Close). Пример 5. Определить среднюю температуру для значений, хранящихся в файле Temp.dat. Program Task2; Var Ft: File Of Real; T,St: Real; N: Integer; Begin Assign(Ft,'Temp.dat'); Reset(Ft); St:=0; While Not Eof(Ft) Do Begin Read(Ft,T); St:=St+T End; N:=FileSize(Ft); St:=St/N; WriteLn('Средняя температура зa',N:3,'суток равна',St:7:2,'гр-в'); Close(Ft) End. В этой программе использована функция определения размера файла: FileSize (<имя файловой переменной>); Ее результат — целое число, равное текущей длине файла. Замечание: согласно стандарту Паскаля в файл, открытый оператором Rewrite, можно только записывать информацию, а файл, открытый оператором Reset, можно использовать только для чтения. В Турбо Паскале допускается запись (Write) в файл, открытый для чтения (Reset). Это создает определенные удобства для модификации файлов. Текстовые файлы. Текстовый файл — наиболее часто употребляемая разновидность файлов. Как уже отмечалось раньше, немагнитные внешние устройства (логические) работают только с текстовыми файлами. Файлы, содержащие тексты программ на Паскале и других языках программирования, являются текстовыми. Различная документация, информация, передаваемая по каналам электронной связи, — все это текстовые файлы. В программе файловая переменная текстового типа описывается следующим образом: Var <идентификатор>:tехt; Текстовый файл представляет собой символьную последовательность, разделенную на строки Каждая строка заканчивается специальным кодом — маркером конца строки (м.к.с.). Весь файл заканчивается маркером конца файла (м.к.ф.). Схематически это выглядит так:  Каждый символ представлен во внутреннем коде (ASCII) и занимает 1 байт. Текстовый файл отличается от символьного не только делением на строки. В текстовой файл можно записать и из него прочитать информацию любого типа. Если эта информация несимвольная, то в процессе чтения или записи происходит ее преобразование из символьной формы во внутреннюю и обратно. Текстовый файл можно создать или преобразовать с помощью текстового редактора. Его можно просмотреть на экране дисплея или распечатать на принтере. В программах на Паскале для работы с текстовыми файлами наряду с процедурами Read и Write употребляются процедуры ReadLn и WriteLn. ReadLn(FV, Эта процедура читает строку из файла с именем FV, помещая прочитанное в переменные из списка ввода. WriteLn(FV,<список вывода>) Процедура записывает в файл FV значения из списка вывода, после чего выставляет маркер конца строки. Для обнаружения конца строки в текстовом файле используется функция Eoln(FV) (End of line — конец строки). Это логическая функция, которая принимает значение true, если указатель файла достиг маркера конца строки и false — в противном случае. Употребление операторов Read и ReadLn без указания имени файловой переменной обозначает чтение из стандартного файла Input (ввод с клавиатуры). Употребление операторов Write и WriteLn без имени файловой переменной обозначает запись в стандартный файл Output (вывод на экран). В таком варианте этими операторами мы уже многократно пользовались. Считается, что файлы INPUT и OUTPUT всегда открываются соответственно для чтения и записи при работе любой программы. При вводе с клавиатуры маркер конца строки обнаруживается при нажатии на клавишу Enter. Процедура ReadLn может использоваться без списка ввода. В этом случае происходит пропуск текущей строки в читаемом файле. Употребление процедуры WriteLn без списка вывода обозначает вывод пустой строки (в файле выставляется маркер конца строки). При записи в текстовый файл в списке вывода могут присутствовать форматы. Действия форматов мы уже рассматривали при обсуждении вывода данных на экран. Точно так же форматы работают и при выводе в текстовые файлы, связанные с любыми другими устройствами. Пример 6. Пусть файл с именем Note.txt содержит некоторый текст. Требуется подсчитать количество строк в этом тексте. Var Note: Text; К: Integer; Begin Assign (Note,'Note.txt'); Reset(Note); K:=0; While Not Eof(Note) Do Begin ReadLn(Note); K:=K+1 End; WriteLn ('Количество строк равно',К); Close(Note) End. Используемый здесь оператор ReadLn (Note) «пролистывает» строки из текстового файла Note, не занося их в какую-либо переменную. Пример 7. В текстовом файле Note.txt определить длину самой большой строки. Var Note: Text; Max,К: Integer; С: Char; Begin Assign(Note,'Note.txt'); Reset (Note); Max:=0; While Not Eof(Note) Do Begin K:=0; While Not Eoln(Note) Do Begin Read(Note,C); K:=K+1 End; If K>Max Then Max:=K; ReadLn(Note) End; WriteLn('Наибольшая строка имеет', Max,'знаков'); Close(Note) End. Здесь каждая строчка прочитывается посимвольно, при этом в переменной к работает счетчик числа символов в строке. В переменной Мах отбирается наибольшее значение счетчика. 3.20. Комбинированный тип данныхВсе структурированные типы данных, с которыми мы уже познакомились, представляют собой совокупности однотипных величин. Комбинированный тип данных — это структурированный тип, состоящий из фиксированного числа компонент (полей) разного типа. Комбинированный тип имеет еще и другое название — запись. Обычно запись содержит совокупность разнотипных атрибутов, относящихся к одному объекту. Например, анкетные сведения о студенте вуза могут быть представлены в виде информационной структуры (рис. 35).  Такая структура называется двухуровневым деревом. В Паскале эта информация может храниться в одной переменной типа Record (запись). Задать тип и описать соответствующую переменную можно следующим образом: Type Anketa1=Record FIO: String[50]; {поля} Pol: Char; Dat: String[16]; {записи} Adres: String[50]; Curs: 1..5; (или элементы) Grup: 1..10; Stip: Real {записи} End; Var Student: Anketa1; Такая запись, так же как и соответствующее ей дерево, называется двухуровневой. К каждому элементу записи можно обратиться, используя составное имя, которое имеет следующую структуру: <имя переменной>.<имя поля> Например, student. fio; student. dat и т.п. Если, например, требуется полю курс присвоить значение 3, то это делается так: Student.Curs:=3 ; Поля записи могут иметь любой тип, в частности сами могут быть записями. Такая возможность используется в том случае, когда требуется представить многоуровневое дерево (более 2 уровней). Например, те же сведения о студентах можно отобразить трехуровневым деревом (рис.36).  Такая организация данных позволит, например, делать выборки информации по году рождения или по городу, где живут студенты. В этом случае описание соответствующей записи будет выглядеть так: Type Anketa2=Record FIO: String[50]; Pol: Char; Dat: Record God: Integer; Mes: String[10]; Den: 1..31 End; Adres: Record Gorod: String[20]; UlDomKv: String[30]; End; Curs: 1..5 ; Grup: 1..10; Stip: Real End; Var Student: Anketa2; Поля такой записи, находящиеся на третьем уровне, идентифицируются тройным составным именем. Например, student.Dat.God; student.Adres.Gorod. Приведем структурограмму задания комбинированного типа (рис.37).  В программе могут использоваться массивы записей. Если на факультете 500 студентов, то все анкетные данные о них можно представить в массиве: Var Student: Array[1..500] Of Anketal; В таком случае, например, год рождения пятого в списке студента хранится в переменной student[5].Dat.God. Любая обработка записей, в том числе ввод и вывод, производится поэлементно. Например, ввод сведений о 500 студентах можно организовать следующим образом: For I:=1 То 500 Do With Student[I] Do Begin Write('Ф.И.0.:'); ReadLn(FIO); Write('Пол (м/ж):'); ReadLn(Pol); Write('Дата рождения:'); ReadLn(Dat); Write('Адрес:'); ReadLn(Adres); Write('Курс:'); ReadLn(Curs); Write('Группа:'); ReadLn(Grup) ; Write('Стипендия (руб.):'); ReadLn(Stip) End; В этом примере использован оператор присоединения, который имеет следующий вид: With <переменная типа запись> Do <оператор>; Он позволяет, один раз указав имя переменной типа запись после слова With, работать в пределах оператора с именами полей как с обычными переменными, т. е. не писать громоздких составных имен. Тип запись в Паскале может иметь переменный состав полей, который меняется в ходе выполнения программы. Такая возможность реализуется с использованием так называемой вариантной части записи. Подробнее об этом можно прочитать в книгах по Паскалю. Работа с файлами записей. Чаще всего записи используются как элементы файлов, составляющих компьютерные информационные системы. Рассмотрим примеры программ, работающих с файлами записей. Пример 1. Сформировать файл FM.dat, содержащий экзаменационную ведомость одной студенческой группы. Записи файла состоят из следующих элементов: фамилия, имя, отчество; номер зачетной книжки; оценка. Program Examen; Type Stud=Record FIO: String[30]; Nz: String[6]; Mark: 2..5 End; Var Fstud: File Of Stud; S: Stud; N,I: Byte; Begin Assign(Fstud,'FM.DAT'); Rewrite(Fstud); Write('Количество студентов в группе?'); ReadLn(N); For I:=1 To N Do Begin Write(I:1,'-й,Фамилия И.О.'); ReadLn(S.FIO); Write('Номер зачетки:'); ReadLn(S.Nz); Write('Оценка:'); ReadLn(S.Mark); Write(Fstud,S) End; WriteLn('Формирование файла закончено!'); Close(Fstud) End. Прежде чем перейти к следующему примеру, связанному с обработкой сформированного файла, рассмотрим еще одно средство работы с файлами, которое мы пока не обсуждали. Прямой доступ к записям файла В стандарте языка Паскаль допустим только последовательный доступ к элементам файла. Одной из дополнительных возможностей, реализованных в Турбо Паскале, является прямой доступ к записям файла. Как уже отмечалось, элементы файла пронумерованы в порядке их занесения в файл, начиная с нуля. Задав номер элемента файла, можно непосредственно установить на него указатель. После этого можно читать или перезаписывать данный элемент. Установка указателя на нужный элемент файла производится процедурой Seek(FV,n) Здесь FV — имя файловой переменной, n — порядковый номер элемента. В следующем примере эта процедура будет использована. Пример 2. Имеется файл, сформированный программой из предыдущего примера. Пусть некоторые студенты пересдали экзамен и получили новые оценки. Составить программу внесения результатов переэкзаменовки в файл. Программа будет запрашивать номер студента в ведомости и его новую оценку. Работа заканчивается, если вводится несуществующий номер (9999). Program New_Marks; Type Stud=Record FIO: String[30]; Nz: String[6] ; Mark: 2..5 End; Var Fstud: File Of Stud; S: Stud; N: Integer; Begin Assign(Fstud,'FM.DAT'); Reset(Fstud) ; Write('Номер в ведомости?'); ReadLn(N); While N<>9999 Do Begin Seek(Fstud,N-l); Read(Fstud,S); Write(S.FIO,'оценка?'); ReadLn(S.Mark); Seek(Fstud,N-l); Write(Fstud,S); Write('Номер в ведомости?'); ReadLn(N); End; WriteLn('Работа закончена!'); Close(Fstud) End. Пример требует некоторых пояснений. Список студентов в ведомости пронумерован, начиная от 1, а записи в файле нумеруются от 0. Поэтому, если n — это номер в ведомости, то номер соответствующей записи в файле равен n-1. После прочтения записи «номер n—1» указатель смещается к следующей n-й записи. Для повторного занесения на то же место исправленной записи повторяется установка указателя. 3.21. Указатели и динамические структурыДо сих пор мы рассматривали программирование, связанное с обработкой только статических данных. Статическими называются такие величины, память под которые выделяется во время компиляции и сохраняется в течение всей работы программы. В Паскале существует и другой способ выделения памяти под данные, который называется динамическим. В этом случае память под величины отводится во время выполнения программы. Такие величины будем называть динамическими. Раздел оперативной памяти, распределяемый статически, называется статической памятью; динамически распределяемый раздел памяти называется динамической памятью. Использование динамических величин предоставляет программисту ряд дополнительных возможностей. Во-первых, подключение динамической памяти позволяет увеличить объем обрабатываемых данных. Во-вторых, если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации. В-третьих, использование динамической памяти позволяет создавать структуры данных переменного размера. Работа с динамическими величинами связана с использованием еще одного типа данных — ссылочного. Величины, имеющие ссылочный тип, называют указателями. Указатель содержит адрес поля в динамической памяти, хранящего величину определенного типа. Сам указатель располагается в статической памяти (рис. 38).  Адрес величины — это номер первого байта поля памяти, в котором располагается величина. Размер поля однозначно определяется типом. Величина ссылочного типа (указатель) описывается в разделе описания переменных следующим образом: Var <идентификатор>:<ссылочный тип> В стандарте Паскаля каждый указатель может ссылаться на величину только одного определенного типа, который называется базовым для указателя. Имя базового типа и указывается в описании в следующей форме: <ссылочный тип>:=^<имя типа> Вот примеры описания указателей: Type Massiv=Array[l..100] Of Integer; Var PI: ^Integer; P2: ^Char; PM: ^Massiv; Здесь Р1 — указатель на динамическую величину целого типа; P2 — указатель на динамическую величину символьного типа; PM — указатель на динамический массив, тип которого задан в разделе Type. Сами динамические величины не требуют описания в программе, поскольку во время компиляции память под них не выделяется Во время компиляции память выделяется только под статические величины. Указатели — это статические величины, поэтому они требуют описания. Каким же образом происходит выделение памяти под динамическую величину? Память под динамическую величину, связанную с указателем, выделяется в результате выполнения стандартной процедуры NEW. Формат обращения к этой процедуре выглядит так: NEW(<указатель>); Считается, что после выполнения этого оператора создана динамическая величина, имя которой имеет следующий вид: <имя динамической величины>::=<указатель>^. Пусть в программе, в которой имеется приведенное выше описание, присутствуют операторы NEW(Pl); NEW(P2); NEW(PM); После их выполнения в динамической памяти оказывается выделенным место под три величины (две скалярные и один массив), которые имеют идентификаторы P1^, Р2^, РМ^ Например, обозначение P1^ можно расшифровать так: динамическая переменная, на которую ссылается указатель Р1. На схеме, представленной на рис. 39, показана связь между динамическими величинами и их указателями.  Дальнейшая работа с динамическими переменными происходит точно так же, как со статическими переменными соответствующих типов. Им можно присваивать значения, их можно использовать в качестве операндов в выражениях, параметров подпрограмм и т.п. Например, если переменной Р1^ нужно присвоить значение 25, переменной P2^ присвоить значение символа 'W', a массив PM^ заполнить по порядку целыми числами от 1 до 100, то это делается так: Р1^:=25; Р2^: ='W'; For I:=l То 100 Do PM^ [I]:=I; Кроме процедуры NEW значение указателя может определяться оператором присваивания: <указатель>:=<ссылочное выражение>; В качестве ссылочного выражения можно использовать: • указатель; • ссылочную функцию (т. е. функцию, значением которой является указатель); • константу Nil. Nil — это зарезервированная константа, обозначающая пустую ссылку, т. е. ссылку, которая ни на что не указывает. При присваивании базовые типы указателя и ссылочного выражения должны быть одинаковыми. Константу Nil можно присваивать указателю с любым базовым типом. До присваивания значения ссылочной переменной (с помощью оператора присваивания или процедуры NEW) она является неопределенной. Ввод и вывод указателей не допускается. Рассмотрим пример. Пусть в программе описаны следующие указатели: Var D,P:^Integer; К: ^Boolean; Тогда допустимыми являются операторы присваивания D:=P; K:=Nil; поскольку соблюдается принцип соответствия типов. Оператор K:=D ошибочен, так как базовые типы у правой и левой части разные. Если динамическая величина теряет свой указатель, то она становится «мусором». В программировании под этим словом понимают информацию, которая занимает память, но уже не нужна. Представьте себе, что в программе, в которой присутствуют описанные выше указатели, в разделе операторов записано следующее: NEW(D); NEW(P) ; {Выделено место в динамической памяти под две целые переменные. Указатели получили соответствующие значения) D^:=3; Р^:=5; {Динамическим переменным присвоены значения} P:=D; {Указатели Р и D стали ссылаться на одну и ту же величину, равную 3} WriteLn(P",D^); {Дважды напечатается число 3} Таким образом, динамическая величина, равная 5, потеряла свой указатель и стала недоступной. Однако место в памяти она занимает. Это и есть пример возникновения «мусора». На схеме, представленной на рис. 40, показано, что произошло в результате выполнения оператора Р:=D.  В Паскале имеется стандартная процедура, позволяющая освобождать память от данных, потребность в которых отпала. Ее формат: DISPOSE(<указатель>); Например, если динамическая переменная P^ больше не нужна, то оператор DISPOSE(Р) удалит ее из памяти. После этого значение указателя Р становится неопределенным. Особенно существенным становится эффект экономии памяти при удалении больших массивов. В версиях Турбо Паскаля, работающих под управлением операционной системы MS DOS, под данные одной программы выделяется 64 килобайта памяти. Это и есть статическая область памяти. При необходимости работать с большими массивами информации этого может оказаться мало. Размер динамической памяти намного больше (сотни килобайт). Поэтому использование динамической памяти позволяет существенно увеличить объем обрабатываемой информации. Следует отчетливо понимать, что работа с динамическими данными замедляет выполнение программы, поскольку доступ к величине происходит в два шага: сначала ищется указатель, затем по нему — величина. Как это часто бывает, действует «закон сохранения неприятностей»: выигрыш в памяти компенсируется проигрышем во времени. Пример 1. Создать вещественный массив из 10000 чисел, заполнить его случайными числами в диапазоне от 0 до 1. Вычислить среднее значение массива. Очистить динамическую память. Создать целый массив размером 10000, заполнить его случайными целыми числами в диапазоне от -100 до 100 и вычислить его среднее значение. Program Sr; Const NMax=10000; Type Diapazon=l..NMax; MasInt=Array[Diapazon] Of Integer; MasReal=Array[Diapazon] Of Real; Var Flint: ^Masint; PReal: ^MasReal; I,Midint: Longint; MidReal: Real; Begin MidReal:=0; Midlnt:=0; Randomize; NEW(PReal); {Выделение памяти под вещественный массив} {Вычисление и суммирование массива} For I:=1 То NMax Do Begin PReal^[I]:=Random; MidReal:=MidReal+PReal^[I] End; DISPOSE(PReal);{Удаление вещественного массива} NEW(Pint); (Выделение памяти под целый массив} {Вычисление и суммирование целого массива) For I:=l To NMax Do Begin PInt^[I]:=Random(200)-100; MidInt:=MidInt+PInt^[I] End; {Вывод средних значений} WriteLn('среднее целое равно:',MidInt DivMax); WriteLn('среднее вещественное равно:', (MidReal/NMax):10:6) End. Связанные списки. Обсудим вопрос о том, как в динамической памяти можно создать структуру данных переменного размера. Разберем следующий пример. В процессе физического эксперимента многократно снимаются показания прибора (допустим, термометра) и записываются в компьютерную память для дальнейшей обработки. Заранее неизвестно, сколько измерений будет произведено. Если для обработки таких данных не использовать внешнюю память (файлы), то разумно расположить их в динамической памяти. Во-первых, динамическая память позволяет хранить больший объем информации, чем статическая. А во-вторых, в динамической памяти эти числа можно организовать в связанный список, который не требует предварительного указания количества чисел, подобно массиву. Что же такое связанный список? Схематически он выглядит так:  Каждый элемент списка состоит из двух частей: информационной части (x1, x2 и т.д.) и указателя на следующий элемент списка (p2, р3, и т.д.). Последний элемент имеет пустой указатель Nil. Связанный список такого типа называется однонаправленной цепочкой. Для сформулированной выше задачи информационная часть представляет набор вещественных чисел: x1 — результат первого измерения, x2 — результат второго измерения и т д., х4 — результат последнего измерения. Связанный список обладает тем замечательным свойством, что его можно дополнять по мере поступления новой информации. Добавление происходит путем присоединения нового элемента к концу списка. Значение Nil в последнем элементе заменяется ссылкой на новый элемент цепочки:  Связанный список не занимает лишней памяти. Память расходуется в том объеме, который требуется для поступившей информации. В программе для представления элементов цепочки используется комбинированный тип (запись). Для нашего примера тип такого элемента может быть следующим: Type Pe=^Elem; Elem=Record Т: Real; P: Ре End; Здесь Ре — ссылочный тип на переменную типа Elem. Этим именем обозначен комбинированный тип, состоящий из двух полей: T — вещественная величина, хранящая температуру, P — указатель на динамическую величину типа Elem. В таком описании нарушен один из основных принципов Паскаля, согласно которому на любой программный объект можно ссылаться только после его описания. В самом деле, тип Ре определяется через тип Elem, а тот, в свою очередь, определяется через тип Ре. Однако в Паскале допускается единственное исключение из этого правила, связанное со ссылочным типом. Приведенный фрагмент программы является правильным. Пример 2. Рассмотрим программу формирования связанного списка в ходе ввода данных. Type Pe=^TypElem; TypElem=Record Т: Real; P: Ре End; Var Elem,Beg: Pe; X: Real; Ch: Char; Begin (Определение адреса начала списка и его сохранение} NEW(Elem); Beg:=Elem; Elem^.P:=Elem; {Диалоговый ввод значений с занесением их в список и организацией связи между элементами) While Elem^.P<>Nil Do Begin Write('Вводите число:'); ReadLntElem^.T); Write('Повторить ввод? (Y/N)'); ReadLn(Ch); If (Ch='n') Or (Ch=-'N') Then Elem^.P:=Nil Else Begin NEW(Elem^.P) ; Elem:=Elem^.P End End; WriteLn(«Ввод данных закончен»); {Вывод полученной числовой последовательности} WriteLn(«Контрольная распечатка»); Elem:=Beg; Repeat WriteLn (N,':'/Elem^.T:8:3); Elem:=Elem^.P Until Elem=Nil End. Здесь ссылочная переменная Beg используется для сохранения адреса начала цепочки. Всякая обработка цепочки начинается с ее первого элемента. В программе показано, как происходит продвижение по цепочке при ее обработке (в данном примере — распечатке информационной части списка по порядку). Однонаправленная цепочка — простейший вариант связанного списка. В практике программирования используются двунаправленные цепочки (когда каждый элемент хранит указатель на следующий и на предыдущий элементы списка), а также двоичные деревья. Подобные структуры данных называются динамическими структурами. Пример 3. Задача о стеке. Одной из часто употребляемых в программировании динамических структур данных является стек. Стек — это связанная цепочка, начало которой называется вершиной. Состав элементов постоянно меняется. Каждый вновь поступающий элемент размещается в вершине стека. Удаление элементов из стека также производится с вершины. Стек подобен детской пирамидке, в которой на стержень надеваются кольца. Всякое новое кольцо оказывается на вершине пирамиды. Снимать кольца можно только сверху. Принцип изменения содержания стека часто формулируют так: «Последним пришел — первым вышел». Составим процедуры добавления элемента в стек (INSTEK) и исключения элемента из стека (OUTSTEK). При этом будем считать, что элементы стека — символьные величины. В процедурах используется тип Pе, который должен быть глобально объявлен в основной программе. Type Pe=^TypElem; TypElem=Record С: Char; P: Ре End; В процедуре INSTEK аргументом является параметр Sim, содержащий включаемый в стек символ. Ссылочная переменная Beg содержит указатель на вершину стека при входе в процедуру и при выходе из нее. Следовательно, этот параметр является и аргументом, и результатом процедуры. В случае, когда стек пустой, указатель Beg равен Nil. Procedure INSTEK(Var Beg: Ре; Sim: Char); Var X: Pe; Begin New(X); X^.C:=Sim; X^.P:=Beg; Beg:=X End; В процедуре OUTSTEK параметр Beg играет ту же роль, что и в предыдущей процедуре. После удаления последнего символа его значение станет равным Nil. Ясно, что если стек пустой, то удалять из него нечего. Логический параметр Flag позволяет распознать этот случай. Если на выходе из процедуры Flag=True, то, значит, удаление произошло; если Flag=False, значит, стек был пуст и ничего не изменилось. Процедура не оставляет после себя «мусора», освобождая память из-под удаленных элементов. Procedure OUTSTEK(Var Beg: Pe; Var Flag: Boolean); Var X: Pe; Begin If Then Flag:=False Else Begin Flag:=True; X:=Beg; Beg:=Beg^.P; DISPOSE(X) End End; |