WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |
Московский государственный университет им. М.В. Ломоносова Факультет вычислительной математики и кибернетики Отделение по работе с иностранными учащимися А.А. Вылиток, Т.К. Матвеева Динамические структуры данных.

Задание практикума. Язык Паскаль (Учебно-методическое пособие для студентов 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-© Вылиток А.А., Матвеева Т.К.

Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, Статические и динамические объекты. Ссылочный тип в языке Паскаль.

Во многих языках программирования объекты программы (переменные, константы, функции и др.) могут быть статическими или динамическими. Здесь мы ограничимся рассмотрением одного вида программных объектов – переменных. Примером статического объекта в языке Паскаль является переменная, описанная в блоке программы или подпрограммы (процедуры, функции). Так, описание var n : integer;

порождает статическую переменную целого (или целочисленного) типа.

Отметим три важных момента, связанных с описанием переменной:

1) Переменная получает имя (в нашем примере это имя n), с помощью которого она изображается в программе. Другими словами, данное имя позволяет обращаться к переменной в программе1.

2) Тип переменной задаёт множество допустимых для неё значений. Для переменной n это целые числа из диапазона от – Maxint до + Maxint, где Maxint – константа, определяемая реализацией языка Паскаль.

3) Тип переменной задаёт её размер, т.е. объём машинной памяти, необходимый для размещения в этой переменной значений данного типа.

Размер значений того или иного типа определяется конкретной реализацией языка. Так, в системе Турбо Паскаль все значения типа integer в машинном представлении имеют одинаковый размер – два байта (или 16 двоичных разрядов).

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

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

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

n В начальный момент выполнения программы значение переменной не определено. Этот факт изображается пустым прямоугольником. Значение, присвоенное переменной в процессе выполнения программы, будем вписывать внутрь соответствующего прямоугольника. Например, после выполнения оператора n:=32, рисунок изменится так:

n Переменная и ее имя – это две разные сущности. Вместо полной фразы «переменная, имеющая имя 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].

a b a[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.

Рисунок q nil говорит о том, что значением q является пустая ссылка, то есть в данный момент q не указывает ни на какой объект (пустой прямоугольник означал бы, что значение q не определено).

Переменную ссылочного типа можно также описать, непосредственно используя задание типа в разделе описания переменных, например var p :integer.

- 5 - Осталось выяснить, как в программе работать с порождённым динамическим объектом, например, как присвоить ему значение. Если к обозначению указателя приписать справа стрелку, то мы получим обозначение объекта, ссылка на который хранится в данном указателе.

Выполнение оператора p:= 35 приведёт к тому, что целая переменная, на которую указывает p, получит значение 35:

p p {p:= 35} значение p до присваивания не значение p после присваивания определено равно Пусть n – имя переменной типа integer. Тогда при выполнении оператора n:=p значение динамической переменной будет присвоено статической переменной n:

n n { n:=p } p p значение n до присваивания не значение n после присваивания определено равно Итак, приписывание стрелки справа к указателю – это способ изобразить динамическую переменную в программе. Такое обозначение (со стрелкой справа) называется переменная с указателем. С помощью металингвистических формул (БНФ) подытожим все возможные обозначения переменных в языке Паскаль:

<переменная>::= <полная переменная> | <переменная с индексом> | <компонента записи> | <буферная переменная> | <переменная с указателем> <полная переменная> ::= <имя переменной> <переменная с индексом> ::= <переменная-массив> [ <индексное выражение> {,<индексное выражение>}] <компонента записи> ::= <переменная-запись>.<имя поля>| <имя поля> <буферная переменная> ::= <файловая переменная> <переменная с указателем> ::= <ссылочная переменная> <переменная-массив> ::= <переменная>типа 'массив' <переменная-запись> ::= <переменная>типа 'запись' <файловая переменная> ::= <переменная>типа 'файл' <ссылочная переменная> ::= <переменная>типа 'ссылка' <имя переменной>::=<идентификатор> - 6 - Заметим, что возможны случаи, когда синтаксически верное обозначение переменной не имеет смысла. Тогда программа, в которой встретилось такое обозначение, не может быть исполнена (или её исполнение приведёт к ошибке). Например, обозначение a[i]ошибочно, если имя a в программе не означает массив. Если это имя описано с помощью var a :





array[1..5] of integer, а значение индекса i во время исполнения программы равно 6, то обращение к a[i] приведёт к ошибке, так как не существует компоненты массива с таким индексом.

Следует проявлять осторожность и при работе с указателями. Если, например, значение указателя q не определено или равно nil, то обращение к q приведёт к ошибке.

Теперь рассмотрим операции над ссылочными значениями одного и того же типа. В Паскале ссылки можно присваивать и сравнивать на равенство и неравенство. Присваивание осуществляется, как обычно, с помощью оператора присваивания:

<ссылочная переменная> := <ссылочное выражение>, где <ссылочная переменная> – обозначение переменной ссылочного типа, <ссылочное выражение> – это либо пустая ссылка nil, либо ссылочная переменная, либо вызов функции ссылочного типа.

Пусть переменные p и q имеют значения, изображенные на схеме:

p q nil Тогда логические выражения p=q и q<>nil дают значение "ложь". После присваивания q:=p (результат изображен на рисунке) p p { q:=p } q q nil значение q до присваивания значение q после присваивания равно nil совпадает со значением p, т.е. q ссылается на тот же объект, что и p логические выражения p=q и q<>nil дают значение "истина".

Если объект, созданный с помощью оператора new, больше не нужен программе, его целесообразно уничтожить, чтобы он зря не занимал место в оперативной памяти (на его месте могут быть созданы другие объекты).

Уничтожение динамического объекта осуществляется оператором процедуры dispose(<ссылочное выражение>). Значением выражения, указанного в качестве фактического параметра должна быть ссылка на уже существующий динамический объект (иначе ошибка). Этот объект перестает существовать, a ссылка на него удаляется из множества значений ссылочного - 7 - типа, в результате чего все указатели, содержащие ссылку на уничтоженный объект, становятся неопределёнными.

Для переменных p и q, изображённых на последней схеме, выполнение оператора dispose(q) приведёт к исчезновению динамического объекта со значением 35, а значения переменных p и q станут неопределёнными.

p p 35 {dispose(q)} q q значения p и q определены и значения p и q ( оба! ) не равны между собой определены Линейные списки и их реализация посредством статических и динамических структур данных Понятие списка хорошо известно из жизненных примеров: список студентов учебной группы, список призёров олимпиады, список (перечень) документов для представления в приёмную комиссию, список почтовой рассылки, список литературы для самостоятельного чтения и т.п.

В математике список (или кортеж) – это конечная последовательность (допускающая повторения) элементов какого-нибудь множества. Список обозначается , где n (n0) – количество элементов, или длина списка, для i=1,…,n xi есть i-й элемент списка (xi ). Об элементе xi говорят также, что он занимает i-ю позицию в списке. При n = 0 получается пустой список, который не содержит элементов и обозначается < >.

Элементы множества могут иметь весьма сложную структуру, отражая реальные объекты и процессы. Вследствие этого возможны списки, в которых некоторые элементы сами являются списками или содержат списки внутри себя.

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

Далее в качестве множества будем рассматривать множество значений некоторого типа языка Паскаль. Этот тип в общем случае будем обозначать именем elemtype (от англ. element type – тип элемента).

Важной структурной особенностью списка является то, что его элементы линейно упорядочены в соответствии с их позицией в списке. Для i=1,…,n-элемент xi предшествует элементу xi+1; для i=2,…,n элемент xi следует за элементом xi-1.

Следующие операции можно применять к линейным спискам:

1) Получить значение i-го элемента списка или изменить i-й элемент;

2) Напечатать элементы списка в порядке их расположения;

3) Найти в списке элемент с заданным значением;

4) Определить длину списка;

- 8 - 5) Вставить новый элемент непосредственно за i-м элементом или перед ним, вставить элемент в пустой список;

6) Удалить i-й элемент;

7) Соединить два линейных списка в один список;

8) Разбить список на два списка;

9) Создать копию списка;

10) Сделать список пустым.

Возможны и более сложные операции над линейными списками.

Примеры.

1. Вставить в список целых чисел <1,3,4,2,1,5> число 7 после третьего элемента.

Результат: <1,3,4,7,2,1,5>.

В полученном списке первые три элемента не изменились, четвертую позицию заняло вставляемое число 7, остальные элементы сдвинулись на одну позицию вправо. Длина списка увеличилась на единицу.

2. Вставить строку "фиолетовый" в конец списка строк <"красный", "оранжевый", "жёлтый", "зелёный", "голубой", "синий">.

Результат: <"красный", "оранжевый", "жёлтый", "зелёный", "голубой", "синий", "фиолетовый"> 3. Удалить из списка символов химических элементов первый элемент.

Результат: .

Длина списка уменьшилась на единицу. Если к результату применить ту же операцию – удалить первый элемент – получим пустой список < >.

4. Вставить в пустой список вещественных чисел < > число 3.1415927.

Результат: <3.1415927>.

Pages:     || 2 | 3 | 4 | 5 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.