Лабораторная работа №26
Решение задач на динамические структуры
Структурированные типы данных, такие, как массивы, множества, записи, представляют собой статические структуры, так как их размеры неизменны в течение всего времени выполнения программы. Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. Такие структуры данных называются динамическими, к ним относятся стеки, очереди, списки, деревья и другие. Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти и увеличивает время решения задач.
Используя структурные типы, указатели и динамические переменные, можно создавать разнообразные динамические структуры памяти. Особенности указателей в языке С++ позволяют строить динамические структуры памяти на основе статически объявленных переменных или на смеси статических и динамических переменных. Идея организации всех динамических структур одна и та же. Определяется некоторый структурный тип S, одно или несколько полей которого объявлены указателями на тот же или некоторый другой структурный тип. В программе объявляется переменная d типа S или переменная типа указатель на S в случае полностью динамического создания структуры. Имя этой переменной при выполнении программы используется как имя "корня" (родительское имя) динамической структуры. При выполнении программы по мере построения динамической структуры запрашиваются динамические переменные соответствующих типов и связываются ссылками, начиная с переменной d или первой динамической переменной, указатель на которую содержится в переменной d. Этот подход позволяет создать динамическую структуру с любой топологией.
Циклические (кольцевые) списки
Циклический (кольцевой) список – это структура данных, представляющая собой последовательность элементов, последний элемент которой содержит указатель на первый элемент списка, а первый (в случае двунаправленного списка) – на последний.
Основная особенность такой организации состоит в том, что в этом списке нет элементов, содержащих пустые указатели, и, следовательно, нельзя выделить крайние элементы.
Циклические списки, так же как и линейные, бывают однонаправленными и двунаправленными.
Циклический однонаправленный список похож на линейный однонаправленный список, но его последний элемент содержит указатель, связывающий его с первым элементом (рис. 1).
Для полного обхода такого списка достаточно иметь указатель на произвольный элемент, а не на первый, как в линейном однонаправленном списке. Понятие "первого" элемента здесь достаточно условно и не всегда требуется. Хотя иногда бывает полезно выделить некоторый элемент как "первый" путем установки на него специального указателя. Это требуется, например, для предотвращения "зацикливания" при просмотре списка.
Рис 1. Циклический однонаправленный список
Основные операции, осуществляемые с циклическим однонаправленным списком:
· создание списка;
· печать (просмотр) списка;
· вставка элемента в список;
· удаление элемента из списка;
· поиск элемента в списке;
· проверка пустоты списка;
· удаление списка.
Для описания алгоритмов этих основных операций будем использовать те же объявления, что и для линейного однонаправленного списка.
Приведем функции перечисленных основных операций при работе с циклическим однонаправленным списком.
//создание циклического однонаправленного списка
void Make_Circle_Single_List(int n,
Circle_Single_List** Head,Circle_Single_List* Loop){
if (n > 0) {
(*Head) = new Circle_Single_List();
//выделяем память под новый элемент
if (Loop == NULL) Loop = (*Head);
cout << "Введите значение ";
cin >> (*Head)->Data;
//вводим значение информационного поля
(*Head)->Next=NULL;//обнуление адресного поля
Make_Circle_Single_List(n-1,&((*Head)->Next),Loop);
}
else {
(*Head) = Loop;
}
}
//печать циклического однонаправленного списка
void Print_Circle_Single_List(Circle_Single_List* Head) {
Circle_Single_List* ptr=Head;
//вспомогательный указатель
do {
cout << ptr->Data << "\t";
ptr=ptr->Next;
} while (ptr!=Head);
cout << "\n";
}
/*вставка элемента после заданного номера в циклический однонаправленный список*/
Circle_Single_List* Insert_Item_Circle_Single_List(Circle_Single_List* Head,
int Number, int DataItem){
Circle_Single_List *Current = Head;
//встали на первый элемент
Circle_Single_List *NewItem = new(Circle_Single_List);
//создали новый элемент
NewItem->Data = DataItem;
if (Head == NULL) {//список пуст
NewItem->Next = NewItem;
Head = NewItem;
}
else {//список не пуст
for (int i = 1; i < Number; i++)
Current = Current->Next;
NewItem->Next = Current->Next;
Current->Next = NewItem;
}
return Head;
}
/*удаление элемента с заданным номером из циклического однонаправленного списка*/
Circle_Single_List* Delete_Item_Circle_Single_List
(Circle_Single_List* Head, int Number){
if (Head!= NULL){
Circle_Single_List *Current = Head;
if (Head->Next!= Head){
for (int i = 1; i < Number; i++)
Current = Current->Next;
Circle_Single_List *ptr = Head;
while (ptr->Next!= Current)
ptr = ptr->Next;
//непосредственное удаление элемента
ptr->Next = Current->Next;
if (Head = Current) Head = Current->Next;
delete(Current);
}
else{
Head = NULL;
delete(Current);
}
}
return Head;
}
//поиск элемента в циклическом однонаправленном списке
bool Find_Item_Circle_Single_List(Circle_Single_List* Head,
int DataItem){
Circle_Single_List *ptr = Head;
//вспомогательный указатель
do {
if (DataItem == ptr->Data) return true;
else ptr = ptr->Next;
}
while (ptr!= Head);
return false;
}
//проверка пустоты циклического однонаправленного списка
bool Empty_Circle_Single_List(Circle_Single_List* Head){
return (Head!= NULL? false: true);
}
//удаление циклического однонаправленного списка
void Delete_Circle_Single_List(Circle_Single_List* Head){
if (Head!= NULL){
Head = Delete_Item_Circle_Single_List(Head, 1);
Delete_Circle_Single_List(Head);
}
}
Циклический двунаправленный список похож на линейный двунаправленный список, но его любой элемент имеет два указателя, один из которых указывает на следующий элемент в списке, а второй указывает на предыдущий элемент (рис. 2).
Рис. 2. Циклический двунаправленный список
Основные операции, осуществляемые с циклическим двунаправленным списком:
· создание списка;
· печать (просмотр) списка;
· вставка элемента в список;
· удаление элемента из списка;
· поиск элемента в списке
· проверка пустоты списка;
· удаление списка.
Для описания алгоритмов этих основных операций будем использовать те же объявления, что и для линейного двунаправленного списка.
Приведем функции перечисленных основных операций при работе с циклическим двунаправленным списком.
//создание циклического двунаправленного списка
Circle_Double_List* Make_Circle_Double_List(int n,
Circle_Double_List** Head,Circle_Double_List* Loop){
Circle_Double_List* ptr;//вспомогательный указатель
if (n > 0) {
(*Head) = new Circle_Double_List();
//выделяем память под новый элемент
if (Loop == NULL) Loop = (*Head);
cout << "Введите значение ";
cin >> (*Head)->Data;
//вводим значение информационного поля
(*Head)->Next=NULL;//обнуление адресного поля
ptr = Make_Circle_Double_List(n-1,&((*Head)->Next),Loop);
if ((*Head)->Next!= NULL)
(*Head)->Next->Prior = (*Head);
if ((*Head)->Prior == NULL)
(*Head)->Prior = ptr;
if (ptr == NULL)
return *Head;
else return ptr;
}
else {
(*Head) = Loop;
return NULL;
}
}
//печать циклического двунаправленного списка
void Print_Circle_Double_List(Circle_Double_List* Head) {
Circle_Double_List* ptr=Head;
//вспомогательный указатель
do {
cout << ptr->Data << "\t";
ptr=ptr->Next;
} while (ptr!=Head);
cout << "\n";
}
/*вставка элемента после заданного номера в циклический двунаправленный список*/
Circle_Double_List* Insert_Item_Circle_Double_List
(Circle_Double_List* Head, int Number, int DataItem){
Circle_Double_List *Current = Head;
//встали на первый элемент
Circle_Double_List *NewItem = new(Circle_Double_List);
//создали новый элемент
NewItem->Data = DataItem;
if (Head == NULL) {//список пуст
NewItem->Next = NewItem;
NewItem->Prior = NewItem;
Head = NewItem;
}
else {//список не пуст
for (int i = 1; i < Number; i++)
Current = Current->Next;
NewItem->Next = Current->Next;
Current->Next = NewItem;
NewItem->Prior = Current;
NewItem->Next->Prior = NewItem;
}
return Head;
}
/*удаление элемента с заданным номером из циклического двунаправленного списка*/
Circle_Double_List* Delete_Item_Circle_Double_List(Circle_Double_List* Head,
int Number){
if (Head!= NULL){
Circle_Double_List *Current = Head;
if (Head->Next!= Head){
for (int i = 1; i < Number; i++)
Current = Current->Next;
Circle_Double_List *ptr = Current->Next;
Current->Prior->Next = Current->Next;
Current->Next->Prior = Current->Prior;
if (Head = Current) //удаляем первый
Head = Current->Next;
delete(Current);
}
else{
Head = NULL;
delete(Current);
}
}
return Head;
}
//поиск элемента в циклическом двунаправленном списке
bool Find_Item_Circle_Double_List(Circle_Double_List* Head,
int DataItem){
Circle_Double_List *ptr = Head;
//вспомогательный указатель
do {
if (DataItem == ptr->Data)
return true;
else ptr = ptr->Next;
}
while (ptr!= Head);
return false;
}
//проверка пустоты циклического двунаправленного списка
bool Empty_Circle_Double_List(Circle_Double_List* Head){
return (Head!= NULL? false: true);
}
//удаление циклического двунаправленного списка
void Delete_Circle_Double_List(Circle_Double_List* Head){
if (Head!= NULL){
Head = Delete_Item_Circle_Double_List(Head, 1);
Delete_Circle_Double_List(Head);
}
}
Деки
Дек является особым видом очереди.
Дек (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) – это структура данных, представляющая собой последовательность элементов, в которой можно добавлять и удалять в произвольном порядке элементы с двух сторон (рис.3). Первый и последний элементы дека соответствуют входу и выходу дека.
Рис. 3. Дек и его организация
Частные случаи дека – это ограниченные деки:
· дек с ограниченным входом – из конца дека можно только извлекать элементы;
· дек с ограниченным выходом – в конец дека можно только добавлять элементы.
Данная структура является наиболее универсальной из рассмотренных выше линейных структур. Накладывая дополнительные ограничения на операции с началом и/или концом дека, можно осуществлять моделирование стека и очереди.
Однако применительно к деку целесообразно говорить не о начале и конце как в очереди, а о левом и правом конце.
Описание элементов дека аналогично описанию элементов линейного двунаправленного списка. Поэтому объявим дек через объявление линейного двунаправленного списка:
· создание дека;
· печать (просмотр) дека;
· добавление элемента в левый конец дека;
· добавление элемента в правый конец дека;
· извлечение элемента из левого конца дека;
· извлечение элемента из правого конца дека;
· проверка пустоты дека;
· очистка дека.
Реализацию этих операций приведем в виде соответствующих функций, которые, в свою очередь, используют функции операций с линейным двунаправленным списком.
//создание дека
void Make_Deque(int n, Deque* End_Deque){
Make_Double_List(n,&(End_Deque->Begin),NULL);
Double_List *ptr; //вспомогательный указатель
ptr = End_Deque->Begin;
while (ptr->Next!= NULL){
ptr = ptr->Next;
}
End_Deque->End = ptr;
}
//печать дека
void Print_Deque(Deque* Begin_Deque){
Print_Double_List(Begin_Deque->Begin);
}
//добавление элемента в правый конец дека
void Add_Right_Item_Deque(int NewElem, Deque* End_Deque){
End_Deque->End =Insert_Item_Double_List(End_Deque->End,2,NewElem);
End_Deque->End = End_Deque->End->Next;
}
//добавление элемента в левый конец дека
void Add_Left_Item_Deque(int NewElem, Deque* Begin_Deque){
Begin_Deque->Begin =
Insert_Item_Double_List(Begin_Deque->Begin, 1, NewElem);
}
//извлечение элемента из левого конца дека
int Extract_Left_Item_Deque(Deque* Begin_Deque){
int NewElem = NULL;
if (Begin_Deque->Begin!= NULL) {
NewElem = Begin_Deque->Begin->Data;
Begin_Deque->Begin=Delete_Item_Double_List(Begin_Deque->Begin,0);
//удаляем вершину
}
return NewElem;
}
//извлечение элемента из правого конца дека
int Extract_Right_Item_Deque(Deque* End_Deque){
int NewElem = NULL;
if (End_Deque->End!= NULL) {
NewElem = End_Deque->End->Data;
Delete_Item_Double_List(End_Deque->End, 1);
//удаляем вершину
}
return NewElem;
}
//проверка пустоты очереди
bool Empty_Deque(Deque* Begin_Deque){
return Empty_Double_List(Begin_Deque->Begin);
}
//очистка очереди
void Clear_Deque(Deque* Begin_Deque){
Delete_Double_List(Begin_Deque->Begin);
}
Красно-черные деревья
Бинарные деревья работают лучше всего, когда они сбалансированы, когда длина пути от корня до любого из листьев находится в определенных пределах, связанных с числом вершин. Красно-черные деревья являются одним из способов балансировки деревьев. Название происходит от стандартной раскраски узлов таких деревьев в красный и черный цвета. Цвета вершин используются при балансировке дерева.
Красно-черное дерево (Red-Black-Tree, RB-Tree) – это бинарное дерево со следующими свойствами (рис. 4):
· каждая вершина должна быть окрашена либо в черный, либо в красный цвет;
· корень дерева должен быть черным;
· листья дерева должны быть черными и объявляться как NIL -вершины (NIL -узлы, то есть "виртуальные" узлы, наследники узлов, которые обычно называют листьями; на них "указывают" NULL указатели);
· каждый красный узел должен иметь черного предка;
· на всех ветвях дерева, ведущих от его корня к листьям, число черных вершин одинаково.
Рис.4. Красно-черное дерево
Количество черных вершин на ветви от корня до листа называется черной высотой дерева. Перечисленные свойства гарантируют, что самая длинная ветвь от корня к листу не более чем вдвое длиннее любой другой ветви от корня к листу.
Над красно-черными деревьями можно выполнять все те же основные операции, что и над бинарными деревьями.
Приведем функции следующих операций над красно-черными деревьями: создание дерева, печать (просмотр) дерева, обход дерева, проверка пустоты дерева и удаление дерева.
//создание красно-черного дерева
void Make_RBTree(RBTree** Node, int n){
int Data;
while (n > 0) {
cout << "Введите значение ";
cin >> Data;
Insert_Node(Node, Data);
n--;
}
}
//добавление узла в красно-черное дерево
void Insert_Node(RBTree** Node,int Data) {
RBTree **Curent, *Parent, *New_Node;
Curent = Node;
Parent = NIL;
// Поиск местоположения
while (*Curent!= NIL) {
Parent = (*Curent);
Curent = Data < (*Curent)->Data? &((*Curent)->Left): &((*Curent)->Right);
}
// Создание нового узла
New_Node = new RBTree();
New_Node->Data = Data;
New_Node->Parent = Parent;
New_Node->Left = NIL;
New_Node->Right = NIL;
New_Node->color = RED;
// Вставка элемента в дерево
if(Parent!= NIL){
if (Data < Parent->Data) Parent->Left = New_Node;
else Parent->Right = New_Node;
}
else (*Curent) = New_Node;
Insert_Fixup(Node, New_Node);
}
// Поддержка баланса дерева после вставки нового элемента
void Insert_Fixup(RBTree** Node,RBTree* New_Node){
RBTree* Current = New_Node;
// Проверка свойств дерева
while (Current!= *(Node) && Current->Parent->color == RED){
// если есть нарушение
if (Current->Parent == Current->Parent->Parent->Left) {
RBTree *ptr = Current->Parent->Parent->Right;
if (ptr->color == RED) {
Current->Parent->color = BLACK;
ptr->color = BLACK;
Current->Parent->Parent->color = RED;
Current = Current->Parent->Parent;
}
else {
if (Current == Current->Parent->Right) {
// сделать Current левым потомком
Current = Current->Parent;
Rotate_Left(Node,Current);
}
// перекрасить и повернуть
Current->Parent->color = BLACK;
Current->Parent->Parent->color = RED;
Rotate_Right(Node,Current->Parent->Parent);
}
}
else {
RBTree *ptr = Current->Parent->Parent->Left;
if (ptr->color == RED) {
Current->Parent->color = BLACK;
ptr->color = BLACK;
Current->Parent->Parent->color = RED;
Current = Current->Parent->Parent;
}
else {
if (Current == Current->Parent->Left) {
Current = Current->Parent;
Rotate_Right(Node,Current);
}
Current->Parent->color = BLACK;
Current->Parent->Parent->color = RED;
Rotate_Left(Node,Current->Parent->Parent);
}
}
}
(*Node)->color = BLACK;
}
//поворот узла Current влево
void Rotate_Left(RBTree** Node,RBTree *Current) {
RBTree *ptr = Current->Right;
Current->Right = ptr->Left;
if (ptr->Left!= NIL) ptr->Left->Parent = Current;
if (ptr!= NIL) ptr->Parent = Current->Parent;
if (Current->Parent!= NIL) {
if (Current == Current->Parent->Left)
Current->Parent->Left = ptr;
else
Current->Parent->Right = ptr;
}
else {
(*Node) = ptr;
}
ptr->Left = Current;
if (Current!= NIL) Current->Parent = ptr;
}
//поворот узла Current вправо
void Rotate_Right(RBTree** Node,RBTree *Current) {
RBTree *ptr = Current->Left;
Current->Left = ptr->Right;
if (ptr->Right!= NIL) ptr->Right->Parent = Current;
if (ptr!= NIL) ptr->Parent = Current->Parent;
if (Current->Parent!= NIL) {
if (Current == Current->Parent->Right)
Current->Parent->Right = ptr;
else
Current->Parent->Left = ptr;
}
else {
(*Node) = ptr;
}
ptr->Right = Current;
if (Current!= NIL) Current->Parent = ptr;
}
//печать красно-черного дерева
void Print_RBTree(RBTree* Node, int l){
int i;
if (Node!= NIL) {
Print_RBTree(Node->Right, l+1);
for (i=0; i< l; i++) cout << " ";
if (Node->color == RED)
SetConsoleTextAttribute(hStd,FOREGROUND_RED);
cprintf ("%4ld", Node->Data);
SetConsoleTextAttribute(hStd,atr);
Print_RBTree(Node->Left, l+1);
}
else cout << endl;
}
//прямой обход красно-черного дерева
void PreOrder_RBTree(RBTree* Node){
if (Node!= NIL) {
printf ("%3ld",Node->Data);
PreOrder_RBTree(Node->Left);
PreOrder_RBTree(Node->Right);
}
}
//обратный обход красно-черного дерева
void PostOrder_RBTree(RBTree* Node){
if (Node!= NIL) {
PostOrder_RBTree(Node->Left);
PostOrder_RBTree(Node->Right);
printf ("%3ld",Node->Data);
}
}
//симметричный обход красно-черного дерева
void SymmetricOrder_RBTree(RBTree* Node){
if (Node!= NIL) {
PostOrder_RBTree(Node->Left);
printf ("%3ld",Node->Data);
PostOrder_RBTree(Node->Right);
}
}
//проверка пустоты красно-черного дерева
bool Empty_RBTree(RBTree* Node){
return (Node == NIL? true: false);
}
//освобождение памяти, выделенной под красно-черное дерево
void Delete_RBTree(RBTree* Node){
if (Node!= NIL) {
Delete_RBTree(Node->Left);
Delete_RBTree(Node->Right);
delete(Node);
}
}
| Сформулировать идеально сбалансированное бинарное дерево типа char. Распечатать полученное дерево. Найти количество элементов с заданным ключем. Вывести полученный результат. Преобразовать идеально сбалансированное дерево в дево поиска. Распечатать полученное лерево. | ||||
| Создать стек целочисленных значений, для реализации используя односвязные списки. Реализовать операции добавления (push) и удаления (pop) элемента из стека. Добавьте в стек числа 4, 3, 1, 2, 4 и распечатайте содержимое стека. Удалите один элемент из стека, и распечатайте содержимое стека еще раз. Найдите минимальный элемент, принадлежащий стеку. | ||||
| Даны две непустые очереди; адреса начала и конца первой равны P 1 и P 2, а второй — P 3 и P 4. Элементы каждой из очередей упорядочены по возрастанию (в направлении от начала очереди к концу). Объединить очереди в одну с сохранением упорядоченности элементов. Вывести указатели на начало и конец полученной очереди. Операции выделения и освобождения памяти не использовать, поля с данными (Data) не изменять. | ||||
| Создать линейный однонаправленный список из целых чисел. Определить среднее арифметическое значений элементов списка, кратных 4. | ||||
| Создать линейный однонаправленный список из вещественных чисел. Удалить из списка элемент перед каждым элементом со значением 55. | ||||
| Создать циклический двунаправленный список из вещественных чисел. Удалить из списка элемент перед каждым элементом со значением 3. | ||||
| Сформулировать идеально сбалансированное бинарное дерево типа int. Распечатать полученное дерево. Найти максимальный элемент в дереве. Вывести полученный результат. Преобразовать идеально сбалансированное дерево в дево поиска. Распечатать полученное лерево. | ||||
| Создать очередь вещественных значений, для реализации используя односвязные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь числа: -2.2, 2.3, 2.2, 5.1, 6.7 и распечатайте содержимое очереди. Удалите 3 элемента из очереди, затем добавьте в очередь число 1.9 и распечатайте очередь еще раз. Найдите произведение элементов, принадлежащих очереди. | ||||
| Арифметическое выражение можно представить в обратной польской записи, где знаки операции следуют за операндами (а не ставятся между ними, как в обычной записи выражений). Обратная польская запись не требует скобок. Например, выражению «1 + 2» соответствует запись «1 2 +», выражению «1 + 2 * 3» запись «1 2 3 * +» (вначале умножаются 2 на 3, а потом 1 складывается с результатом), «(2 + 3) * (3 – 1)» записывается как «2 3 + 3 1 – *». Задается строка – выражение в обратной польской записи (числа и знаки +, –, * разделены пробелами). Используя стек, вычислите значение выражения. Подсказка: нужно последовательно перебрать все числа и знаки из строки, числа нужно заносить в стек, а как встретится знак операции, вынимать 2 числа из стека, применять к ним текущую операцию, а результат заносить в стек. | ||||
| Создать линейный однонаправленный список из целых чисел. Определить сумму значений элементов списка, кратных 5. | ||||
| Создать линейный двунаправленный список из вещественных чисел. Удалить из списка элемент после каждого элемента с отрицательным значением. | ||||
| Создать циклический двунаправленный список из целых чисел. Удалить из списка первый элемент со значением 10. | ||||
| Сформулировать идеально сбалансированное бинарное дерево типа char*. Распечатать полученное дерево. Найти количество листьев в дереве. Вывести полученный результат. Преобразовать идеально сбалансированное дерево в дево поиска. Распечатать полученное лерево. | ||||
| Создать стек строковых значений, для реализации используя односвязные списки. Реализовать операции добавления (push) и удаления (pop) элемента из стека. Добавьте в стек строки «abc», «fx», «glc», «hi», «gogo» и распечатайте содержимое стека. Удалите один элемент из стека, затем добавьте строку «the end» и распечатайте содержимое стека еще раз. Найдите количество строк в стеке, состоящих из 2 символов. | ||||
| Дана последовательность скобок вида «(», «)», «[», «]», «{», «}». Правильными скобочными последовательностями называются пустая последовательность, а также «(P)», «[ P ]», «{ P }», где P – некоторая правильная последовательность. Например «{}()[]» и «{[][()()]}()» – правильные скобочные последовательности, а «(]», «[()» и «({)}» – неправильные. Определите является ли заданная строка правильным скобочным выражением. Подсказка: обработайте по очереди все символы входной строки, помещая открывающие скобки в стек, а для закрывающих скобок извле- кайте открывающую скобку из стека и проверяйте, соответствуют ли они друг другу. | ||||
| Создать линейный однонаправленный список из вещественных чисел. Определить количество элементов списка со значениями больше 7. | ||||
| Создать линейный однонаправленный список из вещественных чисел. Вставить в список число 1.5 после каждого элемента с отрицательным значением. | ||||
| Создать циклический двунаправленный список из целых чисел. Удалить из списка последний элемент со значением меньшим 15. | ||||
| Сформулировать идеально сбалансированное бинарное дерево типа double. Распечатать полученное дерево. Найти минимальный элемент в дереве. Вывести полученный результат. Преобразовать идеально сбалансированное дерево в дево поиска. Распечатать полученное лерево. | ||||
| Создать очередь строковых значений, для реализации используя односвязные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь строки «one», «two», «three», «four» и распечатайте содержимое очереди. Удалите 2 элемента из очереди, затем добавьте в очередь строку «inf» и распечатайте очередь еще раз. Найдите суммарную длину строк, принадлежащих очереди, кроме первой строки очереди. | ||||
| Реализуйте очередь, используя два стека. Подсказка: стек инвертирует порядок элементов (т.е. если добавить 1 2 3 4 5, вынимая элементы, получим 5 4 3 2 1), поэтому если элементы пройдут два стека, то восстановится их исходный порядок. При помещении в очередь помещайте элемент в первый стек, при извлечении элемента из очереди, извлекайте элемент из второго стека, а если при этом второй стек окажется пустым, перенесите все элементы из первого стека во второй (доставайте элементы первого стека, пока они есть, и переносите во второй). | ||||
| Создать линейный однонаправленный список из целых чисел. Вставить в список число 10 после первого элемента с отрицательным значением. | ||||
| Создать линейный однонаправленный список из вещественных чисел. Определить сумму элементов списка со значениями больше либо равными 15. | ||||
| Создать циклический однонаправленный список из вещественных чисел. Вставить в список число 2.5 перед каждым элементом с положительным значением. | ||||
| Сформулировать идеально сбалансированное бинарное дерево типа char. Распечатать полученное дерево. Найти высоту дерева. Вывести полученный результат. Преобразовать идеально сбалансированное дерево в дево поиска. Распечатать полученное лерево. | ||||
| Создать стек целочисленных значений, для реализации используя односвязные списки. Реализовать операции добавления (push) и удаления (pop) элемента из стека. Добавьте в стек числа 1, 2, 3, 4, 5 и распечатайте содержимое стека. Удалите 3 элемента из стека, и распечатайте содержимое стека еще раз. Найдите сумму элементов стека. | ||||
| Дано число N (> 0) и две непустые очереди; адреса начала и конца первой равны P 1 и P 2, а второй — P 3 и P 4. Переместить N начальных элементов первой очереди в конец второй очереди. Если первая очередь содержит менее N элементов, то переместить из первой очереди во вторую все элементы. Вывести новые адреса начала и конца первой, а затем второй очереди (для пустой очереди дважды вывести nil). Операции выделения и освобождения памяти не использовать. | ||||
| Создать линейный однонаправленный список из вещественных чисел. Удалить из списка элемент после первого элемента с положительным значением. | ||||
| Создать линейный однонаправленный список из вещественных чисел. Удалить из списка первый элемент меньший по модулю 5. | ||||
| Дан указатель P 1 на начало односвязного линейного списка. Преобразовать исходную (односвязную) цепочку в двусвязную, в которой каждый элемент связан не только с последующим элементом (с помощью поля Next), но и с предыдущим (с помощью поля Prev). Поле Prev первого элемента положить равным nil. Вывести на экран преобразованную цепочку в обратном порядке. | ||||
| Сформулировать идеально сбалансированное бинарное дерево типа int. Распечатать полученное дерево. Найти среднее арифметическое элементов дерева. Вывести полученный результат. Преобразовать идеально сбалансированное дерево в дево поиска. Распечатать полученное лерево. | ||||
| Создать очередь вещественных значений, для реализации используя односвязные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь числа 2.1, 2.1, 5.3 и распечатайте содержимое очереди. Удалите 1 элемент из очереди, затем добавьте в очередь число 4.9 и распечатайте очередь еще раз. Найдите сумму элементов очереди. | ||||
| Дан набор из 10 чисел. Создать две очереди: первая должна содержать числа из исходного набора с нечетными номерами (1, 3, …, 9), а вторая — с четными (2, 4, …, 10); порядок чисел в каждой очереди должен совпадать с порядком чисел в исходном наборе. Вывести указатели на начало и конец первой, а затем второй очереди. | ||||
| Создать линейный однонаправленный список из вещественных чисел. Удалить из списка элемент перед первым элементом со значением 55. | ||||
| Создать линейный однонаправленный список из вещественных чисел. Продублировать в списке первый положительный элемент (если такого нет, оставить список без изменения). | ||||
| Дан указатель P 1 на первый элемент непустого двусвязного списка. Продублировать в списке все элементы с нечетными значениями (новые элементы добавлять перед существующими элементами с такими же значениями) и вывести указатель на первый элемент преобразованного списка. | ||||
| Сформулировать идеально сбалансированное бинарное дерево типа char*. Распечатать полученное дерево. Найти количество элементов дерева, начинающихся с заданного символа. Вывести полученный результат. Преобразовать идеально сбалансированное дерево в дево поиска. Распечатать полученное лерево. | ||||
| Создать очередь вещественных значений, для реализации используя односвязные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь числа 2.2, 1.2, 2.0, 5.2 и распечатайте содержимое очереди. Удалите 2 элемента из очереди, затем добавьте в очередь число 2.9 и распечатайте очередь еще раз. Найдите сумму элементов очереди. | ||||
| Дан набор из 10 чисел. Создать две очереди: первая должна содержать все нечетные, а вторая — все четные числа из исходного набора (порядок чисел в каждой очереди должен совпадать с порядком чисел в исходном наборе). Вывести указатели на начало и конец первой, а затем второй очереди (одна из очередей может оказаться пустой; в этом случае вывести для нее две константы nil). | ||||
| Создать линейный однонаправленный список из целых чисел. Удалить из списка первый элемент со значением 10. | ||||
| Создать линейный однонаправленный список из целых чисел. Удалить из списка первый четный элемент, стоящий на нечетной позиции. | ||||
| Дан указатель P 1 на первый элемент непустого двусвязного списка. Продублировать в списке все элементы с нечетными значениями (новые элементы добавлять после существующих элементов с такими же значениями) и вывести указатель на последний элемент преобразованного списка. | ||||
| Сформулировать идеально сбалансированное бинарное дерево типа char. Распечатать полученное дерево. Найти количество элементов с заданным ключем. Вывести полученный результат. Преобразовать идеально сбалансированное дерево в дево поиска. Распечатать полученное лерево. | ||||
| Создать стек строковых значений, для реализации используя односвязные списки. Реализовать операции добавления (push) и удаления (pop) элемента из стека. Добавьте в стек строки «sdf», «2», «ssd4», «hello» и распечатайте содержимое стека. Удалите 2 элемента из стека, и распечатайте содержимое стека еще раз. Найдите строку минимальной длины, принадлежащую стеку. | ||||
| Даны указатели P 1 и P 2 на начало и конец непустой очереди. Извлекать из очереди элементы, пока значение начального элемента очереди не станет четным, и выводить значения извлеченных элементов (если очередь не содержит элементов с четными значениями, то извлечь все ее элементы). Вывести также новые адреса начала и конца очереди (для пустой очереди дважды вывести nil). После извлечения элементов из очереди освобождать память, которую они занимали. | ||||
| Создать линейный однонаправленный список из вещественных чисел. Вставить в список число 0.99 перед первым элементом со значением 22. | ||||
| Создать линейный двунаправленный список из целых чисел. Вставить в список число 66 после каждого элемента с отрицательным значением. | ||||
| Дан указатель P 1 на первый элемент двусвязного списка, содержащего не менее двух элементов. Удалить из списка все элементы с нечетными номерами и вывести указатель на первый элемент преобразованного списка. После удаления элементов из списка освобождать память, которую они занимали. | ||||
| Сформулировать идеально сбалансированное бинарное дерево типа double. Распечатать полученное дерево. Найти максимальный элемент в дереве. Вывести полученный результат. Преобразовать идеально сбалансированное дерево в дево поиска. Распечатать полученное лерево. | ||||
| Создать очередь строковых значений, для реализации используя односвязные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь строки «one», «two», «three», «four» и распечатайте содержимое очереди. Удалите 1 элемент из очереди, затем добавьте в очередь строку «five» и распечатайте очередь еще раз. * Найдите суммарную длину всех строк, принадлежащих очереди. | ||||
| Даны две очереди; адреса начала и конца первой равны P 1 и P 2, а второй – P 3 и P 4 (если очередь является пустой, то соответствующие адреса равны nil). Переместить все элементы первой очереди (в порядке от начала к концу) в конец второй очереди и вывести новые адреса начала и конца второй очереди. Операции выделения и освобождения памяти не использовать. | ||||
| Создать линейный однонаправленный список из целых чисел. Вставить в список число 10 после каждого элемента с отрицательным значением. | ||||
| Создать линейный однонаправленный список из вещественных чисел. Удалить из списка элемент перед каждым элементом со значением -2. Вставить число 33 в конец списка. | ||||
| Дан указатель P 1 на первый элемент непустого двусвязного списка. Удалить из списка все элементы с нечетными значениями и вывести указатель на первый элемент преобразованного списка (если в результате удаления элементов список окажется пустым, то вывести nil). После удаления элементов из списка освобождать память, которую они занимали. | ||||
| Сформулировать идеально сбалансированное бинарное дерево типа int. Распечатать полученное дерево. Найти количество листьев в дереве. Вывести полученный результат. Преобразовать идеально сбалансированное дерево в дево поиска. Распечатать полученное лерево. | ||||
| Создать стек целочисленных значений, для реализации используя односвязные списки. Реализовать операции добавления (push) и удаления (pop) элемента из стека. Добавьте в стек числа -5, 3, -4, 5 и распечатайте содержимое стека. Удалите один элемент из стека, добавьте число 10 в стек, и напечатайте содержимое стека еще раз. * Найдите сумму всех положительных элементов, принадлежащих стеку. | ||||
| Даны две непустые очереди; адреса начала и конца первой равны P 1 и P 2, а второй – P 3 и P 4. Перемещать элементы из начала первой очереди в конец второй, пока значение начального элемента первой очереди не станет четным (если первая очередь не содержит четных элементов, то переместить из первой очереди во вторую все элементы). Вывести новые адреса начала и конца первой, а затем второй очереди (для пустой очереди дважды вывести nil). Операции выделения и освобождения памяти не использовать. | ||||
| Создать линейный однонаправленный список из вещественных чисел. Удалить из списка элемент после каждого элемента с положительным значением. | ||||
| Создать линейный двунаправленный список из целых чисел. Удалить из списка элемент после каждого элемента, равного 4. Вставить число 0 перед каждым числом 1. | ||||
| Дано число K (> 0) и указатель P 0 на один из элементов непустого двусвязного списка. Переместить в списке данный элемент на K позиций вперед (если после данного элемента находится менее K элементов, то переместить его в конец списка). Вывести указатели на первый и последний элементы преобразованного списка. Операции выделения и освобождения памяти не использовать, поля с данными (Data) не изменять. | ||||
Сформулировать идеально сбалансированное бинарное дерево типа double
Поиск по сайту©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование. Дата создания страницы: 2021-06-10 Нарушение авторских прав и Нарушение персональных данных |
Поиск по сайту: Читайте также: Деталирование сборочного чертежа Когда производственнику особенно важно наличие гибких производственных мощностей? Собственные движения и пространственные скорости звезд |