А.А. Вылиток, Т.К. Матвеева - Динамические структуры данных. Задание практикума. Язык Паскаль (1113471)
Текст из файла
Московский государственный университет им. М.В. ЛомоносоваФакультет вычислительной математики и кибернетикиОтделение по работе с иностранными учащимисяА.А. Вылиток, Т.К. МатвееваДинамические структуры данных.Задание практикума. Язык Паскаль(Учебно-методическое пособие для студентов 1 курса)Москва2004УДК 519.682ББК 32.973-018В92Печатается по решениюРедакционно-издательского совета факультетавычислительной математики и кибернетики МГУ им.
М.В. ЛомоносоваРецензенты:доцент кафедры системногопрограммирования ВМиК МГУКузьменкова Е.А.доцент кафедры русского языкадля иностранцев естественных факультетов МГУКузьмич И.П.Вылиток А.А., Матвеева Т.К.В92 Динамические структуры данных. Задание практикума. ЯзыкПаскаль: Учебно-методическое пособие. - М.: Издательский отделФакультета ВМиК МГУ им. М.В. Ломоносова (лицензия ИД № 05899 от24.09.2001 г.), 2004. – 44с.ISBN 5-89407-207-7Учебно-методическое пособие «Динамические структуры данных.Задание практикума.
Язык Паскаль» предназначено для студентов 1 курсафакультета ВМиК МГУ им. М.В. Ломоносова. В пособии подробно освещаетсяодна из непростых тем для начинающих программистов – работа сдинамическими структурами данных.Рассмотрены линейные списки и их реализация на языке Паскальпосредством как статических, так и динамических структур данных. Приведенобольшое количество примеров с решениями.В заключение сформулировано задание практикума, предназначенноедля иностранных студентов факультета ВМиК. Дан образец решения одного извозможных вариантов задания.Библиогр. 7.УДК 519.682ББК 32.973-018Учебно-методическое пособиеВЫЛИТОК Алексей АлександровичМАТВЕЕВА Тамара КонстантиновнаДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ.
ЗАДАНИЕ ПРАКТИКУМА. ЯЗЫК ПАСКАЛЬЛицензия ИД №05899 от 24.09.01.119992, ГСП-2, Москва, Ленинские Горы, МГУ им. М.В. Ломоносова, 2-й учебный корпусISBN 5-89407-207-7© Вылиток А.А., Матвеева Т.К.Издательский отдел факультета вычислительной математики икибернетики МГУ им. М.В. Ломоносова, 2004Статические и динамические объекты. Ссылочный тип в языкеПаскаль.Во многих языках программирования объекты программы (переменные,константы, функции и др.) могут быть статическими или динамическими. Здесьмы ограничимся рассмотрением одного вида программных объектов –переменных.
Примером статического объекта в языке Паскаль являетсяпеременная, описанная в блоке программы или подпрограммы (процедуры,функции). Так, описаниеvar n : integer;порождает статическую переменную целого (или целочисленного) типа.Отметим три важных момента, связанных с описанием переменной:1) Переменная получает имя (в нашем примере это имя n), с помощьюкоторого она изображается в программе. Другими словами, данное имяпозволяет обращаться к переменной в программе1.2) Тип переменной задаёт множество допустимых для неё значений.
Дляпеременной n это целые числа из диапазона от – Maxint до + Maxint,где Maxint – константа, определяемая реализацией языка Паскаль.3) Тип переменной задаёт её размер, т.е. объём машинной памяти,необходимый для размещения в этой переменной значений данного типа.Размер значений того или иного типа определяется конкретнойреализацией языка.
Так, в системе Турбо Паскаль все значения типаinteger в машинном представлении имеют одинаковый размер – двабайта (или 16 двоичных разрядов).Отвлекаясь от машинного представления, переменную можно считатьячейкой или ящиком, который предназначен для хранения значенийопределённого типа, причём в каждый момент в ящике хранится не болееодного значения.Для наглядного представления характера значений и действий надпеременными договоримся о следующей схеме их графического изображения.Переменные целого типа и других простых типов будем изображать нарисунках в виде прямоугольников.
Слева от фигуры, изображающейпеременную, указывается её имя. Для целочисленной переменной n рисунокбудет таким:nВ начальный момент выполнения программы значение переменной неопределено. Этот факт изображается пустым прямоугольником. Значение,присвоенное переменной в процессе выполнения программы, будем вписыватьвнутрь соответствующего прямоугольника. Например, после выполненияоператора n:=32, рисунок изменится так:n321Переменная и ее имя – это две разные сущности. Вместо полной фразы «переменная,имеющая имя n , порождённая данным описанием var n : integer» будем использоватьболее короткую – «переменная n» (там, где это не вызовет недоразумений).-3-Массивы и записи будем изображать фигурами, составленными изфигур, изображающих их компоненты и расположенных соответственно однапод другой по вертикали или одна рядом с другой по горизонтали.
Нижепоказаны порожденные описаниемvar a : array[1..5] of integer;b : record x: array[1..3] of integer; y,z: real end;массив из пяти чисел и запись с тремя полями. В записи первое поле – массив изтрех целых чисел, второе и третье поля – вещественные числа.
Имена a и bобозначают объекты целиком. Для указания компонент сложных объектовиспользуются более сложные обозначения, например a[3], b.z илиb.x[2].aba[3]b.x[2]b.zСтатические программные объекты порождаются автоматическиперед выполнением программы или подпрограммы, в которой они описаны, исуществуют, пока выполнение этой программы или подпрограммы незавершится.
Размер статических объектов не изменяется на протяжении всеговремени их существования.К динамическим относятся объекты, которые с помощью специальныхдействий создаются (или изменяют свой размер) уже в процессе выполненияпрограммы (подпрограммы).В языке Паскаль для создания динамических объектов используетсястандартная процедура new, имеющая один параметр. Объект, созданный спомощью new в процессе выполнения программы или подпрограммы,существует вплоть до завершения основной программы, или до тех пор, пока онне будет уничтожен явно с помощью другой стандартной процедуры –dispose.Для того, чтобы в программе на Паскале обращаться к статическомуобъекту, мы используем имя, данное ему в разделе описаний.
Динамическиеобъекты заранее не описываются – как же к ним обращаться? Для этого вместе спорождаемым объектом создается специальное значение – ссылка на этотобъект. Чтобы хранить ссылочные значения, используются переменныеспециального ссылочного типа.
При порождении объекта ссылка на негопомещается в переменную, указанную в качестве фактического параметраоператора процедуры new. Каждому динамическому объекту соответствуетсвоя ссылка, различные объекты имеют различные ссылки.На рисунках будем изображать ссылку точкой и связывать ее стрелкой ссоответствующим объектом:В машинных терминах ссылка – это адрес объекта в оперативной памятикомпьютера. Язык Паскаль не позволяет явно записывать адреса в программе,к тому же на этапе составления программы не известно, по какому адресу будет-4-расположен тот или иной динамический объект. Поскольку ссылки не имеютявного обозначения в программе, работа с динамическими объектамипроисходит посредством статических переменных ссылочного типа.Синтаксис задания ссылочного типа определяется следующим правиломБНФ:<задание ссылочного типа>::= ↑<имя типа>,где стрелка означает, что задаётся ссылочный тип, а <имя типа> – это имялюбого стандартного или ранее описанного типа.Значениями переменных ссылочного типа могут быть ссылки надинамические объекты, причём только того типа, имя которого указано взадании после стрелки.
Переменные ссылочного типа описываются обычнымспособом. Например, в силу описанийtype ref_integer = ↑integer;var p : ref_integer;значением переменной p может быть ссылка на динамический объект целоготипа.1 В начальный момент выполнения программы переменная p не имеетникакого значения (значение не определено) :pЕсли далее с помощью оператора new(p) порождается динамический объект,ссылка на него автоматически присваивается переменной p. Схематичнорезультат изображается следующим образом:pдинамический объект ( переменная типа integer )Можно сказать, что переменная p теперь "указывает" на объект целого типа.Поэтому переменные ссылочного типа часто называют указателями. Заметим,что параметр процедуры new однозначно определяет, какого типа объектпорождается.
В данном случае из описания типа переменной p следует, чтопорождается объект типа integer. Отметим также, что порождаемые объектыне имеют никакого начального значения.Среди значений любого ссылочного типа есть специальное значение,которое называется пустая ссылка. Оно не связано ни с каким объектом, т.е. нина что фактически не ссылается. В программе такое значение для всехссылочных типов явно изображается служебным словом nil.Пусть q – ссылочная переменная того же типа, что и переменная p.Рисунокqnilговорит о том, что значением q является пустая ссылка, то есть в данныймомент q не указывает ни на какой объект (пустой прямоугольник означал бы,что значение q не определено).1Переменную ссылочного типа можно также описать, непосредственно используя задание типав разделе описания переменных, например var p :↑integer.-5-Осталось выяснить, как в программе работать с порождённымдинамическим объектом, например, как присвоить ему значение.
Если кобозначению указателя приписать справа стрелку ↑, то мы получимобозначение объекта, ссылка на который хранится в данном указателе.Выполнение оператора p↑:= 35 приведёт к тому, что целая переменная, накоторую указывает p, получит значение 35:{p↑:= 35}pзначение p↑ до присваивания неопределеноp35значение p↑ после присваиванияравно 35Пусть n – имя переменной типа integer.
Тогда при выполнении оператораn:=p↑ значение динамической переменной будет присвоено статическойпеременной n:npn{ n:=p↑ }35значение n до присваивания неопределено35p35значение n после присваиванияравно 35Итак, приписывание стрелки справа к указателю – это способ изобразитьдинамическую переменную в программе. Такое обозначение (со стрелкойсправа) называется переменная с указателем. С помощью металингвистическихформул (БНФ) подытожим все возможные обозначения переменных в языкеПаскаль:<переменная>::= <полная переменная> | <переменная синдексом> | <компонента записи> | <буферная переменная> |<переменная с указателем><полная переменная>::= <имя переменной><переменная с индексом> ::= <переменная-массив> [<индексное выражение> {,<индексное выражение>}].<компонента записи> ::= <переменная-запись> <имя поля>|<имя поля><буферная переменная>::= <файловая переменная>↑<переменная с указателем> ::= <ссылочная переменная>↑<переменная-массив>::=<переменная>типа'массив'<переменная-запись>::=<переменная>типа'запись'<файловая переменная>::=<переменная>типа'файл'<ссылочная переменная> ::=<переменная>типа'ссылка'<имя переменной>::=<идентификатор>-6-Заметим, что возможны случаи, когда синтаксически верноеобозначение переменной не имеет смысла.
Тогда программа, в которойвстретилось такое обозначение, не может быть исполнена (или её исполнениеприведёт к ошибке). Например, обозначение a[i]ошибочно, если имя a впрограмме не означает массив. Если это имя описано с помощью var a :array[1..5] of integer, а значение индекса i во время исполненияпрограммы равно 6, то обращение к a[i] приведёт к ошибке, так как несуществует компоненты массива с таким индексом.Следует проявлять осторожность и при работе с указателями. Если,например, значение указателя q не определено или равно nil, то обращениек q↑ приведёт к ошибке.Теперь рассмотрим операции над ссылочными значениями одного и тогоже типа. В Паскале ссылки можно присваивать и сравнивать на равенство инеравенство. Присваивание осуществляется, как обычно, с помощью оператораприсваивания:<ссылочная переменная> := <ссылочное выражение> ,где <ссылочная переменная> – обозначение переменной ссылочноготипа, <ссылочное выражение> – это либо пустая ссылка nil, либоссылочная переменная, либо вызов функции ссылочного типа.Пусть переменные p и q имеют значения, изображенные на схеме:pq35nilТогда логические выражения p=q и q<>nil дают значение "ложь".
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
