Решение задач на динамические структуры данных

Цель лекции: изучить алгоритмы и приемы работы с динамическими структурами данных, научиться решать задачи с использованием динамических структур данных и алгоритмов работы с ними на языке C++.

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

Используя структурные типы, указатели и динамические переменные, можно создавать разнообразные динамические структуры памяти. Особенности указателей в языке С++ позволяют строить динамические структуры памяти на основе статически объявленных переменных или на смеси статических и динамических переменных. Идея организации всех динамических структур одна и та же. Определяется некоторый структурный тип S, одно или несколько полей которого объявлены указателями на тот же или некоторый другой структурный тип. В программе объявляется переменная d типа S или переменная типа указатель на S в случае полностью динамического создания структуры. Имя этой переменной при выполнении программы используется как имя "корня" (родительское имя) динамической структуры. При выполнении программы по мере построения динамической структуры запрашиваются динамические переменные соответствующих типов и связываются ссылками, начиная с переменной d или первой динамической переменной, указатель на которую содержится в переменной d. Этот подход позволяет создать динамическую структуру с любой топологией.

Циклические (кольцевые) списки

Циклический (кольцевой) список – это структура данных, представляющая собой последовательность элементов, последний элемент которой содержит указатель на первый элемент списка, а первый (в случае двунаправленного списка) – на последний.

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

Циклические списки, так же как и линейные, бывают однонаправленными и двунаправленными.

).

Для полного обхода такого списка достаточно иметь указатель на произвольный элемент, а не на первый, как в линейном однонаправленном списке. Понятие "первого" элемента здесь достаточно условно и не всегда требуется. Хотя иногда бывает полезно выделить некоторый элемент как "первый" путем установки на него специального указателя. Это требуется, например, для предотвращения "зацикливания" при просмотре списка.

Основные операции, осуществляемые с циклическим однонаправленным списком:

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

Приведем функции перечисленных основных операций при работе с циклическим однонаправленным списком.

//создание циклического однонаправленного списка 
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);
  } 
}

).

Основные операции, осуществляемые с циклическим двунаправленным списком:

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

Приведем функции перечисленных основных операций при работе с циклическим двунаправленным списком.

//создание циклического двунаправленного списка 
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);
  }
}

Деки

Дек является особым видом очереди.

). Первый и последний элементы дека соответствуют входу и выходу дека.

Частные случаи дека – это ограниченные деки:

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

Однако применительно к деку целесообразно говорить не о начале и конце как в очереди, а о левом и правом конце.

Описание элементов дека аналогично описанию элементов линейного двунаправленного списка. Поэтому объявим дек через объявление линейного двунаправленного списка:

Реализацию этих операций приведем в виде соответствующих функций, которые, в свою очередь, используют функции операций с линейным двунаправленным списком.

//создание дека
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);  
}

Красно-черные деревья

Бинарные деревья работают лучше всего, когда они сбалансированы, когда длина пути от корня до любого из листьев находится в определенных пределах, связанных с числом вершин. Красно-черные деревья являются одним из способов балансировки деревьев. Название происходит от стандартной раскраски узлов таких деревьев в красный и черный цвета. Цвета вершин используются при балансировке дерева.

):

Количество черных вершин на ветви от корня до листа называется черной высотой дерева. Перечисленные свойства гарантируют, что самая длинная ветвь от корня к листу не более чем вдвое длиннее любой другой ветви от корня к листу.

Над красно-черными деревьями можно выполнять все те же основные операции, что и над бинарными деревьями.

Приведем функции следующих операций над красно-черными деревьями: создание дерева, печать (просмотр) дерева, обход дерева, проверка пустоты дерева и удаление дерева.

//создание красно-черного дерева
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);
  }
}

Ключевые термины

Циклический (кольцевой) список – это структура данных, представляющая собой последовательность элементов, последний элемент которой содержит указатель на первый элемент списка, а первый (в случае двунаправленного списка) – на последний.

Дек – это структура данных, представляющая собой последовательность элементов, в которой можно добавлять и удалять в произвольном порядке элементы с двух сторон.

Дек с ограниченным входом – это дек, из конца которого можно только извлекать элементы;

Дек с ограниченным выходом – это дек, в конец которого можно только добавлять элементы.

Красно-черное дерево (Red-Black-Tree, RB-Tree) – это бинарное дерево со следующими свойствами:

Черная высота дерева – это количество черных вершин на ветви красно-черного дерева от корня до листа.

Краткие итоги

Лабораторная работа 32. Решение задач на динамические структуры данных

Цель работы: изучить алгоритмы и приемы работы с динамическими структурами данных, научиться решать задачи с использованием динамических структур данных и алгоритмов работы с ними на языке C++.

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

Теоретические сведения.

Ознакомьтесь с материалом лекции 32.

Задания к лабораторной работе.

Выполните приведенные ниже задания.

Указания к выполнению работы.

Выполнение работы следует начать с решения задачи 1, реализовав алгоритмы основных операций над красно-черным деревом. Каждое из заданий необходимо решить в соответствии с изученными методами и реализованными алгоритмами формирования, вывода и обработки данных динамических структур в языке С++. Обработку динамических структур следует выполнить на основе базовых алгоритмов: поиск структуре, вставка элемента в структуру, балансировка красно-черного дерева, удаление элемента из структуры, удаление всей динамической структуры. При объявлении динамических структур выполните комментирование используемых полей. Задача 2 носит исследовательский характер, поэтому следует отразить в отчете подробное описание предлагаемого метода определения максимального размера дека и выводы по сравнению с размерами стека и очереди. Программу для решения каждого задания необходимо разработать методом процедурной абстракции, оформив комментарии к коду.

Следует реализовать каждое задание в соответствии с приведенными этапами:

Требования к отчету.

Отчет по лабораторной работе должен соответствовать следующей структуре.

Контрольные вопросы