А.А. Вылиток, Т.К. Матвеева - Динамические структуры данных. Задание практикума. Язык Паскаль (1113471), страница 2
Текст из файла (страница 2)
Послеприсваивания q:=p (результат изображен на рисунке)pq35{ q:=p }qnilзначение qравно nilpдоприсваивания35значение qпосле присваиваниясовпадает со значением p, т.е. qссылается на тот же объект, что и pлогические выражения p=q и q<>nil дают значение "истина".Если объект, созданный с помощью оператора new, больше не нуженпрограмме, его целесообразно уничтожить, чтобы он зря не занимал место воперативной памяти (на его месте могут быть созданы другие объекты).Уничтожение динамического объекта осуществляется операторомпроцедуры dispose(<ссылочное выражение>). Значением выражения,указанного в качестве фактического параметра должна быть ссылка на ужесуществующий динамический объект (иначе ошибка).
Этот объект перестаетсуществовать, a ссылка на него удаляется из множества значений ссылочного-7-типа, в результате чего все указатели, содержащие ссылку на уничтоженныйобъект, становятся неопределёнными.Для переменных p и q, изображённых на последней схеме, выполнениеоператора dispose(q) приведёт к исчезновению динамического объекта созначением 35, а значения переменных p и q станут неопределёнными.pq35{dispose(q)}значения p и q определены иравны между собойpqзначения pопределеныи q ( оба! )неЛинейные списки и их реализация посредством статических идинамических структур данныхПонятие списка хорошо известно из жизненных примеров: списокстудентов учебной группы, список призёров олимпиады, список (перечень)документов для представления в приёмную комиссию, список почтовойрассылки, список литературы для самостоятельного чтения и т.п.В математике список (или кортеж) – это конечная последовательность(допускающая повторения) элементов какого-нибудь множества Ψ.
Списокобозначается <x1,x2,…,xn>, где n (n≥0) – количество элементов, или длинасписка, для i=1,…,n xi есть i-й элемент списка (xi ∈ Ψ). Об элементе xiговорят также, что он занимает i-ю позицию в списке. При n = 0 получаетсяпустой список, который не содержит элементов и обозначается < >.Элементы множества Ψ могут иметь весьма сложную структуру, отражаяреальные объекты и процессы. Вследствие этого возможны списки, в которыхнекоторые элементы сами являются списками или содержат списки внутри себя.Такие списки называют иерархическими. В отличие от них списки, недопускающие таковых внутри себя, называются линейными.Далее в качестве множества Ψ будем рассматривать множество значенийнекоторого типа языка Паскаль.
Этот тип в общем случае будем обозначатьименем elemtype (от англ. element type – тип элемента).Важной структурной особенностью списка является то, что его элементылинейно упорядочены в соответствии с их позицией в списке. Для i=1,…,n-1элемент 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. Удалить из списка символов химических элементов <Ag,Au> первыйэлемент.Результат: <Au>.Длина списка уменьшилась на единицу.
Если к результату применить ту жеоперацию – удалить первый элемент – получим пустой список < >.4. Вставить в пустой список вещественных чисел < > число 3.1415927.Результат: <3.1415927>.Если в начало полученного списка вставить число 2.7182818, получимсписок <2.7182818,3.1415927>.5. Из списка названий месяцев удалить повторные названия: <December,January, February, March, April, May, December, May, May>.Результат: <December, January, February, March, April, May>.Реализация списков на ПаскалеСписки представляют собой удобную структуру данных для решениямногих практических задач.
Они используются, например, в программах-9-информационного поиска, трансляторах, при моделировании различныхпроцессов. Однако по отношению к языку Паскаль список являетсяабстрактным понятием: в Паскале не предусмотрены ни встроенные операциинад списками, ни средства для их описания, подобные тем, что имеются,скажем, для массивов.1 Поэтому для обработки списков на Паскале потребуетсяих программная реализация. Для этого необходимо:1)сконструировать средствами Паскаля структуру данных, которая будетпредставлять в программе список (в этой структуре будут хранитьсяэлементы списка);2)описать в виде процедур и функций требуемые операции над списками.Мы рассмотрим два наиболее типичных способа реализации списков:посредством массивов и с помощью цепочки звеньев.Реализация списков посредством массивовВ этой реализации элементы списка располагаются по порядку вкомпонентах массива, начиная с первой; i-й элемент списка хранится в i-ойкомпоненте.
Размер массива определяет максимально возможную длину списка.В программе размер массива зададим константой maxlen. Для работы сосписком требуется ещё знать его текущую длину (или номер компонентымассива, в которой находится текущий последний элемент). Опишем тип list(список) как запись, имеющую два поля: первое с именем elems (от англ.elements – элементы) – собственно массив; второе с именем last – позицияпоследнего элемента списка.
Дадим также описание переменной L типа list:constmaxlen =… {подходящее для конкретной задачи целоечисло};typeelemtype = … {подходящий для задачи тип элементов};list = recordelems: array [1..maxlen] of elemtype;last: integerend;var L: list;Выражение L соответствует понятию «список». Конструкцияобозначает в программе i -й элемент списка.L.elems[i]Пусть в качестве elemtype задан перечислимый тип: (Monday,Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday).Реализация списка названий дней недели < Monday, Wednesday, Friday,Saturday> на схеме будет выглядеть так (считаем, что maxlen = 7) :1В языке Лисп, напротив, список является основной структурой данных с богатым наборомопераций, а массивы отсутствуют.- 10 -LMondayWednesdayFridaySaturday4Создать такой список можно следующими действиями: сделать список Lпустым, затем поочередно вставлять в него элементы в нужном порядке.Сделать список пустым весьма просто – достаточно обнулить поле last,поскольку список пуст, если его длина равна нулю.
Оформим это действие ввиде процедуры make_null(L):procedure make_null(var L: list);{ делает список L пустым }beginL.last:=0 { длина списка стала равна нулю }end; {make_null}Вставка нового элемента x перед i-м элементом списка осуществляется вдва этапа: во-первых, все значения из компонент массива elems с индексами i,i+1, …, last перемещаются соответственно в компоненты с индексами i+1, i+2,…, last+1; во-вторых, в i-ю компоненту помещается элемент x,и значениеполя last увеличивается на единицу.Ниже показано, что происходит при вставке значенияThursdayперед третьим элементом списка < Monday, Wednesday, Friday,Saturday>.после 2-го этапа вставки:после 1-го этапа вставки:LMondayWednesdayFridayFridaySaturdayL43-я компонента свободна для записи новогозначениябывшие третий ичетвертый элементытеперь занимаютчетвертую и пятуюкомпонентыMondayWednesdayThursdayFridaySaturday5в 3-ей компоненте теперь новоезначениеОперацию вставки оформим в виде процедуры insert(L,x,i).procedure insert(var L: list; x: elemtype; i:integer);{ вставляет в список L элемент x перед i-м элементом }var p: integer;begin- 11 -for p:=L.last downto i do{перемещение значений из компонент i,i+1,…,last наодну компоненту к концу массива}L.elems[p+1]:=L.elems[p];L.elems[i]:=x;L.last:=L.last+1; {длина списка увеличивается на 1}end; {insert}Итак, чтобы вставить значение Thursday перед третьим элементом списка L,в программе следует использовать оператор insert(L, Thursday,3).Процедуру insert можно использовать и для вставки элемента в пустойНапример,список, задав единицу в качестве третьего параметра.make_null(L); insert(L, Sunday,1):{make_null(L)}LL0…{insert(L,Sunday,1)}Sunday1…Теперь покажем, как создать наш исходный список < Monday,Wednesday, Friday, Saturday >.
Такой список получится в результатевыполнения следующей последовательности операторов: make_null(L);insert(L, Saturday,1); insert(L, Friday,1); insert(L,Wednesday,1); insert(L, Monday,1).Для удаления i-го элемента опишем процедуру delete(L,i).procedure delete(var L: list; i:integer);{ удаляет из списка L i-й элемент }var p: integer;beginfor p:=i to L.last-1 do{перемещение значений из компонент i+1,i+2,…,last на одну компоненту к началумассива}L.elems[p]:=L.elems[p+1];L.last:=L.last-1;{длина списка уменьшается на 1}end; {delete}При использовании процедур insert и delete следует проявлятьосторожность: нельзя вставлять элемент, если длина списка максимальна, т.е.- 12 -равна maxlen; нельзя удалять из пустого списка; необходимо правильнозадавать номер i элемента в списке: 1 ≤ i ≤ last.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
