М.Э. Абрамян - Programming Taskbook (1157415), страница 28
Текст из файла (страница 28)
Даны указатели на первый, последний и текущий элементыдвух непустых двусвязных списков. Используя тип TList (см. заданиеDynamic59), описать процедуру InsertList(L1 , L2 ), которая вставляет всеэлементы из списка L1 (в том же порядке) в список L2 перед его текущимэлементом; в результате список L1 становится пустым. Текущим элементом списка L2 становится первый из вставленных элементов.
Оба параметра процедуры имеют тип TList и являются входными и выходными.Операции выделения и освобождения памяти в процедуре не использовать. С помощью этой процедуры вставить первый из исходных списковв текущую позицию второго и вывести адреса первого, последнего и текущего элементов объединенного списка.Dynamic69. Даны указатели на первый, последний и текущий элементы двухдвусвязных списков (второй список может быть пустым). Используя типTList (см. задание Dynamic59), описать процедуру MoveCurrent(L1 , L2 ),которая перемещает текущий элемент списка L1 в список L2 (элементвставляется после текущего элемента списка L2 и сам становится текущим; в списке L1 текущим становится следующий элемент или, еслиследующего элемента не существует, последний элемент).
Оба параметрапроцедуры имеют тип TList и являются входными и выходными. Операции выделения и освобождения памяти в процедуре не использовать. Спомощью этой процедуры переместить текущий элемент первого спискаДинамические структуры данных131во второй и вывести адреса первого, последнего и текущего элементовполученных списков.Список с барьерным элементомИспользованная в заданиях Dynamic31–Dynamic69 реализация двусвязного списка в виде цепочки узлов, ограниченной по краям нулевыми указателями,не является единственно возможной.
Двусвязный список можно также реализовать в виде замкнутой цепочки узлов с дополнительным фиктивным, илибарьерным, элементом. Этот барьерный элемент связан своими полями Nextи Prev с первым и последним «настоящим» элементом списка соответственно, поэтому, имея указатель на барьерный элемент, можно сразу перейти какк первому, так и к последнему элементу списка (естественно, первый и последний элементы также связаны с барьерным элементом своими полями Prevи Next соответственно).
Для работы с двусвязным списком, снабженным барьерным элементом, достаточно хранить два указателя: Barrier, указывающийна барьерный элемент, и Current, указывающий на текущий элемент (которыйможет быть как «настоящим», так и барьерным элементом).
Поле Data барьерного элемента может быть произвольным; для определенности его можноположить равным 0. Пустой список в данной реализации представляет собойединственный барьерный элемент, «замкнутый на себя».Задания Dynamic70–Dynamic80 посвящены двусвязным спискам с барьерным элементом.Dynamic70◦ . Даны указатели P1 и P2 на первый и последний элементы двусвязного списка, реализованного в виде цепочки узлов, ограниченной покраям нулевыми указателями (если список пуст, то P1 = P2 = nil). Преобразовать исходный список в циклический список (см.
задание Dynamic55),снабженный барьерным элементом. Барьерный элемент должен иметьзначение 0 и быть связан своими полями Next и Prev с первым и последним элементом исходного списка (в случае пустого исходного списка поля Next и Prev барьерного элемента должны указывать на сам барьерныйэлемент). Вывести указатель на барьерный элемент полученного списка.Операцию выделения памяти использовать только для создания барьерного элемента.Dynamic71. Даны указатели P1 и P2 на барьерный и текущий элементы двусвязного списка (о списке с барьерным элементом см. задание Dynamic70).132М. Э.
Абрамян. Электронный задачник Programming Taskbook 4.6Разбить список на два, перенеся во второй список все элементы от текущего до последнего и добавив ко второму списку барьерный элемент.Если текущий элемент исходного списка является барьерным элементом,то второй список должен быть пустым (то есть состоять только из барьерного элемента). Вывести указатель на барьерный элемент второгосписка. Операцию выделения памяти использовать только для созданиябарьерного элемента второго списка.Dynamic72. Даны указатели P1 и P2 на барьерные элементы двух двусвязныхсписков (о списке с барьерным элементом см.
задание Dynamic70). Объединить исходные списки, связав конец первого и начало второго списка(барьерным элементом объединенного списка должен остаться барьерный элемент первого списка). Вывести указатели на первый и последнийэлементы объединенного списка (если объединенный список является пустым, то дважды вывести указатель на его барьерный элемент).
Послеудаления лишнего барьерного элемента освободить занимаемую им память.Dynamic73. Даны указатели P1 и P2 на барьерные элементы двух двусвязныхсписков (о списке с барьерным элементом см. задание Dynamic70). Объединить исходные списки, связав конец первого и начало второго списка(барьерным элементом объединенного списка должен остаться барьерный элемент второго списка).
Вывести указатели на первый и последнийэлементы объединенного списка (если объединенный список является пустым, то дважды вывести указатель на его барьерный элемент). Послеудаления лишнего барьерного элемента освободить занимаемую им память.Dynamic74◦ . Даны указатели P1 и P2 на барьерный и текущий элементы двусвязного списка (о списке с барьерным элементом см. задание Dynamic70).Также дано число N (> 0) и набор из N чисел. Описать тип TListB — записьс полями Barrier и Current типа PNode (поля указывают соответственно набарьерный и текущий элементы списка) — и процедуру LBInsertLast(L, D),которая добавляет новый элемент со значением D в конец списка L (L —входной и выходной параметр типа TListB, D — входной параметр целоготипа).
Добавленный элемент становится текущим. С помощью этой процедуры добавить в конец исходного списка данный набор чисел (в том жепорядке) и вывести адрес текущего элемента полученного списка.Dynamic75. Даны указатели P1 и P2 на барьерный и текущий элемен-Динамические структуры данных133ты двусвязного списка. Также дано число N (> 0) и набор из N чисел. Используя тип TListB (см. задание Dynamic74), описать процедуруLBInsertFirst(L, D), которая добавляет новый элемент со значением D вначало списка L (L — входной и выходной параметр типа TListB, D — входной параметр целого типа). Добавленный элемент становится текущим.С помощью этой процедуры добавить в начало исходного списка данныйнабор чисел (добавленные числа будут располагаться в списке в обратномпорядке) и вывести адрес текущего элемента полученного списка.Dynamic76.
Даны указатели P1 и P2 на барьерный и текущий элементы двусвязного списка. Также даны пять чисел. Используя тип TListB (см. задание Dynamic74), описать процедуру LBInsertBefore(L, D), которая вставляет новый элемент со значением D перед текущим элементом списка L (L— входной и выходной параметр типа TListB, D — входной параметр целого типа). Вставленный элемент становится текущим. С помощью этойпроцедуры вставить пять данных чисел в исходный список и вывестиновый адрес его текущего элемента.Dynamic77.
Даны указатели P1 и P2 на барьерный и текущий элементы двусвязного списка. Также даны пять чисел. Используя тип TListB (см. задание Dynamic74), описать процедуру LBInsertAfter(L, D), которая вставляетновый элемент со значением D после текущего элемента списка L (L —входной и выходной параметр типа TListB, D — входной параметр целоготипа). Вставленный элемент становится текущим. С помощью этой процедуры вставить пять данных чисел в исходный список и вывести новыйадрес его текущего элемента.Dynamic78◦ . Даны указатели P1 и P2 на барьерный и текущий элементы двусвязного списка.
Используя тип TListB (см. задание Dynamic74),описать процедуры LBToFirst(L) (делает текущим первый элемент списка L), LBToNext(L) (делает текущим в списке L следующий элемент),LBSetData(L, D) (присваивает текущему элементу списка L значение Dцелого типа, если данный элемент не является барьерным) и функциюIsBarrier(L) логического типа (возвращает TRUE, если текущий элементсписка L является его барьерным элементом, и FALSE в противном случае). Параметр L имеет тип TListB; в процедурах LBToFirst и LBToNextон является входным и выходным. С помощью этих процедур и функцийприсвоить нулевые значения элементам исходного списка с нечетныминомерами и вывести количество элементов в списке, а также новый ад-134М. Э. Абрамян.
Электронный задачник Programming Taskbook 4.6рес текущего элемента списка. Нумерация ведется от первого элементасписка; барьерный элемент не нумеруется и не учитывается при подсчетеэлементов.Dynamic79. Даны указатели P1 и P2 на барьерный и текущий элементы двусвязного списка. Используя тип TListB (см. задание Dynamic74), описатьпроцедуры LBToLast(L) (делает текущим последний элемент списка L),LBToPrev(L) (делает текущим в списке L предыдущий элемент) и функцию LBGetData(L) целого типа (возвращает значение текущего элемента списка L). Параметр L имеет тип TListB; в процедурах LBToLast иLBToPrev он является входным и выходным.
С помощью этих процедур и функций, а также с использованием функции IsBarrier из заданияDynamic78, вывести все четные значения элементов исходного списка,просматривая список с конца. Вывести также количество элементов всписке. Барьерный элемент не обрабатывается и не учитывается при подсчете элементов.Dynamic80. Даны указатели P1 и P2 на барьерный и текущий элементы непустого двусвязного списка, причем текущий элемент не совпадает с барьерным. Используя тип TListB (см.
задание Dynamic74), описать функцию LBDeleteCurrent(L) целого типа, удаляющую из списка L текущийэлемент и возвращающую его значение (L — входной и выходной параметр типа TListB). Текущим становится следующий элемент или, еслиследующий элемент является барьерным, предыдущий элемент списка.Функция также освобождает память, занимаемую удаленным элементом.Если текущим элементом является барьерный элемент, то функция не выполняет никаких действий и возвращает 0. С помощью этой функции,а также функции IsBarrier из задания Dynamic78, удалить из исходногосписка пять элементов (или все элементы, если их менее пяти) и вывестиих значения. Вывести также новый адрес текущего элемента списка.Динамические структуры данных (.NET)Данный раздел содержит описание варианта группы Dynamic, предназначенного для языков программирования платформы .NET: C# и Visual Basic.NET.Все числа, упоминаемые в заданиях данной группы, являются целыми.Все объекты имеют тип Node.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
