М. Э. Абрамян Programming Taskbook
жүктеу/скачать 0,52 Mb. Pdf көрінісі
|
Задачник Абрамяна
| Двусвязный список
Dynamic29. Дан адрес P 2 записи типа TNode, содержащей поле Data (целого типа) и поля Prev и Next (типа PNode — указателя на TNode). Эта запись связана полями Prev и Next соответственно с предыдущей и последую- щей записью того же типа. Вывести значения полей Data предыдущей и последующей записи, а также адреса P 1 и P 3 предыдущей и последующей записи. Dynamic30 ◦ . Дан указатель P 1 на начало непустой цепочки элементов-записей типа TNode, связанных между собой с помощью поля Next. Используя по- ле Prev записи TNode, преобразовать исходную (односвязную) цепочку в двусвязную, в которой каждый элемент связан не только с последующим элементом (с помощью поля Next), но и с предыдущим (с помощью поля Prev). Поле Prev первого элемента положить равным NIL . Вывести указа- тель на последний элемент преобразованной цепочки. В заданиях Dynamic31–Dynamic69 структура «двусвязный список» (doubly linked list) моделируется цепочкой узлов-записей типа TNode, связанных как с предыдущим, так и с последующим узлом (см. задание Dynamic30). Поле Next последнего элемента цепочки и поле Prev первого элемента цепочки равны NIL . Для доступа к любому элементу двусвязного списка достаточно иметь указатель на один из его элементов, однако для ускорения операций со списком обычно хранят три указателя: на первый элемент списка (first), на его последний элемент (last) и на текущий элемент (current). Для пустого списка все эти указатели полагаются равными NIL . Как в случае стека и очереди, значением элемента списка считается значение его поля Data. Dynamic31. Дан указатель P 0 на один из элементов непустого двусвязного списка. Вывести число N — количество элементов в списке, а также ука- затели P 1 и P 2 на первый и последний элементы списка. 118 М. Э. Абрамян. Электронный задачник Programming Taskbook 4.5 Dynamic32. Даны числа D 1 и D 2 и указатель P 0 на один из элементов непу- стого двусвязного списка. Добавить в начало списка новый элемент со значением D 1 , а в конец — новый элемент со значением D 2 . Вывести адреса первого и последнего элементов полученного списка. Dynamic33. Дано число D и указатель P 0 на один из элементов непустого дву- связного списка. Вставить перед данным элементом списка новый элемент со значением D и вывести указатель на добавленный элемент списка. Dynamic34. Дано число D и указатель P 0 на один из элементов непустого дву- связного списка. Вставить после данного элемента списка новый элемент со значением D и вывести указатель на добавленный элемент списка. Dynamic35. Даны указатели P 1 и P 2 на первый и последний элементы дву- связного списка, содержащего не менее двух элементов. Продублировать в списке первый и последний элементы (новые элементы добавлять перед существующими элементами с такими же значениями) и вывести указа- тель на первый элемент преобразованного списка. Dynamic36. Даны указатели P 1 и P 2 на первый и последний элементы дву- связного списка, содержащего не менее двух элементов. Продублировать в списке первый и последний элементы (новые элементы добавлять после существующих элементов с такими же значениями) и вывести указатель на последний элемент преобразованного списка. Dynamic37. Дан указатель P 1 на первый элемент непустого двусвязного спис- ка. Продублировать в списке все элементы с нечетными номерами (но- вые элементы добавлять перед существующими элементами с такими же значениями) и вывести указатель на первый элемент преобразованного списка. Dynamic38. Дан указатель P 1 на первый элемент непустого двусвязного спис- ка. Продублировать в списке все элементы с нечетными номерами (новые элементы добавлять после существующих элементов с такими же зна- чениями) и вывести указатель на последний элемент преобразованного списка. Dynamic39. Дан указатель P 1 на первый элемент непустого двусвязного спис- ка. Продублировать в списке все элементы с нечетными значениями (но- вые элементы добавлять перед существующими элементами с такими же значениями) и вывести указатель на первый элемент преобразованного списка. Dynamic40. Дан указатель P 1 на первый элемент непустого двусвязного спис- Динамические структуры данных 119 ка. Продублировать в списке все элементы с нечетными значениями (но- вые элементы добавлять после существующих элементов с такими же значениями) и вывести указатель на последний элемент преобразованно- го списка. Dynamic41. Дан указатель P 0 на один из элементов непустого двусвязно- го списка. Удалить из списка данный элемент и вывести два указателя: на элемент, предшествующий удаленному, и на элемент, следующий за удаленным (один или оба этих элемента могут отсутствовать; для отсут- ствующих элементов выводить NIL ). После удаления элемента из списка освободить память, занимаемую этим элементом. Dynamic42. Дан указатель P 1 на первый элемент двусвязного списка, содержа- щего не менее двух элементов. Удалить из списка все элементы с нечетны- ми номерами и вывести указатель на первый элемент преобразованного списка. После удаления элементов из списка освобождать память, кото- рую они занимали. Dynamic43. Дан указатель P 1 на первый элемент непустого двусвязного спис- ка. Удалить из списка все элементы с нечетными значениями и вывести указатель на первый элемент преобразованного списка (если в результате удаления элементов список окажется пустым, то вывести NIL ). После уда- ления элементов из списка освобождать память, которую они занимали. Dynamic44. Дан указатель P 0 на один из элементов непустого двусвязного списка. Переместить данный элемент в конец списка и вывести указате- ли на первый и последний элементы преобразованного списка. Операции выделения и освобождения памяти не использовать, поля Data не изме- нять. Dynamic45. Дан указатель P 0 на один из элементов непустого двусвязного списка. Переместить данный элемент в начало списка и вывести указате- ли на первый и последний элементы преобразованного списка. Операции выделения и освобождения памяти не использовать, поля Data не изме- нять. Dynamic46. Дано число K (> 0) и указатель P 0 на один из элементов непустого двусвязного списка. Переместить в списке данный элемент на K позиций вперед (если после данного элемента находится менее K элементов, то пе- реместить его в конец списка). Вывести указатели на первый и последний элементы преобразованного списка. Операции выделения и освобождения памяти не использовать, поля Data не изменять. 120 М. Э. Абрамян. Электронный задачник Programming Taskbook 4.5 Dynamic47. Дано число K (> 0) и указатель P 0 на один из элементов непустого двусвязного списка. Переместить в списке данный элемент на K позиций назад (если перед данным элементом находится менее K элементов, то пе- реместить его в начало списка). Вывести указатели на первый и последний элементы преобразованного списка. Операции выделения и освобождения памяти не использовать, поля Data не изменять. Dynamic48. Даны указатели P жүктеу/скачать 0,52 Mb. Достарыңызбен бөлісу:
|