Бинарный поиск в двусвязном списке

#ifndef STUDENT_H_INCLUDED
#define STUDENT_H_INCLUDED
 
#include <iostream>
#include <string>
#include <iterator>
#include <iomanip>
 
using namespace std;
 
class Student
{
 
private:
 
    int gender;         // Пол ученика
    string fio;         // Фамилия ученика
    double mass;       // Масса ученика
    double growth;    // Рост ученика
 
bool init( int Gender, string Fio, double Mass, double Growth );  // Проверка исходных данных
 
public:
 
void SetGender( int Gender )
{
    gender = Gender;
}
 
void SetFio( string Fio )
{
    fio = Fio;
}
 
void SetMass( double m )
{
    mass = m;
}
 
void SetGrowth( double g )
{
    growth = g;
}
 
int GetGender() const
{
    return gender;
}
 
string GetFio() const
{
    return fio;
}
 
double GetMass() const
{
    return mass;
}
 
double GetGrowth() const
{
    return growth;
}
 
void Read();        // Ввод исходных данных: ФИО, масса, рост
 
void Display();    // Вывод данных на экран
 
double AvarageMassBoys(list<Student>&);              // Вычисление средней массы мальчиков
double AvarageGrowthGirls(list<Student>&);              // Вычисление среднего роста девочек
double StudentMaksGrowth(list<Student>&);    // Нахождение самого высокого роста
};
 
#endif // STUDENT_H_INCLUDED

#include <iostream>
#include <windows.h>
#include <list>
#include <iterator>
#include <fstream>
#include "student.h"
#include "bubblesort.h"
#include "insertionsort.h"
#include "mergesort.h"
#include "klasscpp.cpp"
 
using namespace std;
 
const string FB[10] = { "Куашев", "Иванов", "Петров", "Сидоров", "Смирнов", "Кузнецов", "Попов", "Морозов", "Новиков", "Алексеев" };
const string IB[10] = { "Астемир", "Артем", "Иннокентий", "Сергей", "Иван", "Кирилл", "Фома", "Василий", "Захар", "Петр" };
const string OB[10] = { "Никитич", "Геннадьевич", "Ильич", "Александрович", "Сергеевич", "Романович", "Владимирович", "Викторович", "Алексеевич", "Андреевич" };
const string FG[10] = { "Степанова", "Козлова", "Орлова", "Андреева", "Макарова", "Зайцева", "Яковлева", "Полякова", "Виноградова", "Медведева" };
const string IG[10] = { "Ульяна", "Анастасия", "Ева", "Евгения", "Эмилия", "Татьяна", "Ирина", "Полина", "Елена", "Анна" };
const string OG[10] = { "Денисовна", "Ивановна", "Евгеньевна", "Максимовна", "Антоновна", "Витальевна", "Игоревна", "Сергеевна", "Дмитриевна", "Александровна" };
 
 
void Student_Gournal_Read(int&Number,list<Student>&Gournal)  // Функция для заполнения данных обо всех учениках через цикл
{
    Student a;
    int i = 0;           // итератор
    while ( i < Number )
    {
         a.Read();        // Заполняем данные об ученике
        Gournal.push_back(a);    // Добавляем в список обьект в котором содержится инф-я об ученике
        i++;
    }
}
 
void Student_Gournal_Read_Random(int&Number,list<Student>&Gournal) // Функция для заполнения списка случайными данными
{
    int gend = 0, index = 0;
    string f = "" ,i = "" ,o = "",fios = "";
    double m = 0.0,g = 0.0;
    Student a;
    int h = 0;     // итератор
    while ( h < Number )
    {
        gend = 1 + rand() % 2;   // получаем случайно какой пол у студента
        a.SetGender(gend);
        index = 0 + rand() % 9;
        if ( a.GetGender() == 1 )  // если пол мужской, то данные будут браться из массивов с мужскимим данными
        {
            f = FB[index];
            i = IB[index];
            o = OB[index];
            fios = f + " " + i + " " + o;
            a.SetFio(fios);
        }
        else if ( a.GetGender() == 2 )    // если пол женский берем из соответсвующих массивов
        {
            f = FG[index];
            i = IG[index];
            o = OG[index];
            fios = f + " " + i + " " + o;
            a.SetFio(fios);
        }
 
        m = 55 + rand() % 50;
        a.SetMass(m);
 
        g = 165 + rand() % 30;
        a.SetGrowth(g);
 
        Gournal.push_back(a);
 
      h++;
    }
 
}
 
bool Student_Gournal_Read_File(list<Student>&Gournal)       // Функция для заполнения списка из файла
{
  Student a;
    string f = "",i = "",o = "", fios = "" ;
    int m = 0, g = 0, gend = 0;
 
    ifstream file;
    file.open("Input.txt");  //открываем файд для чтения указав к нему путь
 
    if ( !file )          // проверяет был ли открыт файл
    {
        cout << "Файл не открыт!" << endl;
        return 1;
    }
 
    while ( file >> gend >> f >> i >> o >> m >> g )
    {
        string fios = f + " " + i + " " + o;
        a.SetGender(gend);
        a.SetFio(fios);
        a.SetMass(m);
        a.SetGrowth(g);
        Gournal.push_back(a);
    }
 
        file.close();
 
        return 0;
}
 
void Student_Gournal_Display(list<Student>&Gournal)   // Функция для вывода данных обо всех учениках через цикл
{
    Student a;
    int m = 1;
    for( auto it = Gournal.begin(); it != Gournal.end(); it++ )
    {
        a = *it;  // Присваиваем пустому обьекту экземпляр класса из списка который содержит информация об ученке
        cout << setw(3) << m << "|";
        a.Display();  // Выводим данные об ученике на экран
        m++;
    }
 
}
 
void Student_Quantity(int &Num)   // функция для ввода количества учеников
{
    int Numbers;     // количество учеников
 
    cout << "Введите количество учеников: ";
    cin >> Numbers;
 
    if ( Numbers <= 0 )
    {
        throw "неправильный ввод";
    }
 
        Num = Numbers;
}
 
void menu()    // меню программы где выбиратся пособы заполнения и сортировки
{
    Student a;                              // Создание обьекта
    list<Student> Gournal;               // Содержит n-ое количество экземпляров класса
    int zapolnenie,sortirovka,Numbers;
 
    cout << "Выберите способ заполнени: \n1) - вручную\n2) - случайными данными\n3 - из файла ";
 
    cin >> zapolnenie;
 
    if( zapolnenie < 1 || zapolnenie > 3 )
    {
        throw "неправильный ввод данных!!!";
    }
 
    switch (zapolnenie)
    {
        case 1:
            {
                Student_Quantity(Numbers);
                Student_Gournal_Read(Numbers,Gournal);   // Функция для заполнения данных
                cout << "\n###################################################" << endl;
            } break;
        case 2:
           {
                Student_Quantity(Numbers);
                Student_Gournal_Read_Random(Numbers,Gournal);  // Заполняем список случайнми данными
                cout << "#######################################################" << endl;
           } break;
        case 3:
            {
                Student_Gournal_Read_File(Gournal);
                cout << "#######################################################" << endl;
            } break;
    }
 
    Student_Gournal_Display(Gournal);         // Функция для вывода данных
    cout << "----------------------------------------------------" << endl;
    cout << "Средняя масса мальчиков: " << a.AvarageMassBoys(Gournal) << endl;
    cout << "Средний рост девочек: " << a.AvarageGrowthGirls(Gournal) << endl;
    cout << "Максимальный рост среди учеников: " << a.StudentMaksGrowth(Gournal) << endl;
    cout << "######################################################" << endl;
 
    cout << "Выберите способ сортировки: \n1 - Сортировка методом пузырька\n2 - Сортировка вставками\n3 - Сортировка слиянием\n4 - Быстрая сортировка\n5 - Бинарный поиск ";
    cin >> sortirovka;
 
    if ( sortirovka < 1 || sortirovka > 5 )
    {
        throw "неправильный ввод!!!";
    }
 
    cout << "######################################################" << endl;
 
    switch (sortirovka)
    {
        case 1:
            {
                BubbleSort(Gournal);                      // Функция для сортировки по росту
            } break;
        case 2:
            {
                InsertSort(Gournal);     // Функция для сортировки методом вставок
            } break;
        case 3:
            {
                MergeSort(Gournal);      // Функция для сортировки методом слияния
            } break;
        //case 4:{} break;
        //case 5:{} break;
    }
 
    Student_Gournal_Display(Gournal); // Функция для вывода отсортированных данных
}
 
 
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    cout << "Куашев А.А ДИБББ 21/1 Вариант 13.\nПостановка задачи: Имеются сведения об учениках класса. Определить среднюю массу мальчиков и средний рост девочек.\nКто из учеников класса самый высокий? Упорядочить по росту." << endl;
    cout << "--------------------------------------------------" << endl;
    try
    {
        menu();
    }
    catch ( char const *str )
    {
        cout << str << endl;
    }
 
    system("pause");
    return 0;
}

#ifndef MYLIST_H_INCLUDED
#define MYLIST_H_INCLUDED
 
#include "student.h"
 
struct Node                             //Структура, являющаяся звеном списка
 {
     Student x;                             //Значение x будет передаваться в список
     Node *Next, *Prev;                 //Указатели на адреса следующего и предыдущего элементов списка
 };
 
 class MyList                              //Создаем тип данных Список
 {
     Node *Head, *Tail;                 //Указатели на адреса начала списка и его конца
 public:
     MyList():Head(NULL),Tail(NULL){};    //Инициализируем адреса как пустые
     ~MyList();                           //Прототип деструктора
     void Show();                       //Прототип функции отображения списка на экране
     void Add(Student x);                   //Прототип функции добавления элементов в список
 };
 
MyList::~MyList()                           //Деструктор
 {
     while (Head)                       //Пока по адресу на начало списка что-то есть
     {
         Tail = Head->Next;             //Резервная копия адреса следующего звена списка
         delete Head;                   //Очистка памяти от первого звена
         Head = Tail;                   //Смена адреса начала на адрес следующего элемента
     }
 }
 
 void MyList::Add(Student x)
 {
   Node *temp = new Node;               //Выделение памяти под новый элемент структуры
   temp->Next = NULL;                   //Указываем, что изначально по следующему адресу пусто
   temp->x = x;                         //Записываем значение в структуру
 
   if (Head != NULL)                    //Если список не пуст
   {
       temp->Prev = Tail;               //Указываем адрес на предыдущий элемент в соотв. поле
       Tail->Next = temp;               //Указываем адрес следующего за хвостом элемента
       Tail = temp;                     //Меняем адрес хвоста
   }
   else //Если список пустой
   {
       temp->Prev = NULL;               //Предыдущий элемент указывает в пустоту
       Head = Tail = temp;              //Голова=Хвост=тот элемент, что сейчас добавили
   }
 }
 
 /*
 
 void MyList::Show()
 {
//ВЫВОДИМ СПИСОК С КОНЦА
     Node *temp=Tail;                   //Временный указатель на адрес последнего элемента
 
     while (temp != NULL)               //Пока не встретится пустое значение
     {
         cout << temp->x << " ";        //Выводить значение на экран
         temp = temp->Prev;             //Указываем, что нужен адрес предыдущего элемента
     }
     cout << "\n";
 
 //ВЫВОДИМ СПИСОК С НАЧАЛА
     temp = Head;                       //Временно указываем на адрес первого элемента
      while (temp != NULL)              //Пока не встретим пустое значение
     {
         cout << temp->x << " ";        //Выводим каждое считанное значение на экран
         temp = temp->Next;             //Смена адреса на адрес следующего элемента
     }
     cout << "\n";
 }
   */
 
#endif // MYLIST_H_INCLUDED

    for( auto* it = Gournal.Head; it != Gournal.Tail; it = it->Next )
    {
        a = *it;  // Присваиваем пустому обьекту экземпляр класса из списка который содержит информация об ученке
        cout << setw(3) << m << "|";
        a.Display();  // Выводим данные об ученике на экран
        m++;
    }

#include "iostream"
#include "list"
#include "iterator"
#include "student.h"
 
void BinaryFind(list<Student>&Gournal, double &g)
{
    Student a;
 
    int r = Gournal.size() / 2;
    int j = 0;
 
    if (Gournal.size() == 1 )
    {
        auto it = Gournal.begin();
        a = *it;
        if (a.GetGrowth() == g)
        {
           cout << a.GetFio() << endl;
        }
    }
    else
    {
       for (int i = 0; i < ((int)Gournal.size() / 2) - 1; i++)
       {
            auto it = Gournal.begin();
            a = *it;
            if (a.GetGrowth() == g)
            {
                cout << a.GetFio() << endl;
                j++;
            } break;
 
            it = std::next(it);
       }
 
        if (j == 0)
        {
            for (int k = 0; k < (int)Gournal.size() - r; k++)
            {
                auto it = Gournal.end();
                a = *it;
                if (a.GetGrowth() == g)
                {
                    cout << a.GetFio() << endl;
                    j++;
                } break;
 
                it--;
            }
        }
 
        if (j == 0)
        {
            cout << "В списке не найдено совпадений!" << endl;
        }
}
 
}

#pragma once
list binary_find(double g, MyList &Gournal2)  //Бинарный поиск (работает, когда список отсортирован)
{
    // Р_А и Р_В - указатели на начало и конец списка
    Node *P_A = Gournal2.Head, *P_B = Gournal2.Tail;
 
    if (P_A == P_B)  //Один элемент
    {
        if (g == P_A->x.GetGrowth())
        {
            return P_A;
        }
        else
        {
            return NULL;
        }
    }
 
    if (P_A->Next == P_B)  //Два элемента
    {
        if (g == P_A->Next.x.GetGrowth())
        {
            return P_A;
        }
 
        if (g == P_B->x.GetGrowth())
        {
            return P_B;
        }
 
        return NULL;
    }
 
    list P_C = Get_Middle(P_A, P_B);  //Если элементов больше, то ищем середину
 
    if (g == P_C->x.GetGrowth())  //Если искомое равно середине
    {
        return P_C;
    }
 
    if (g < P_C->x.GetGrowth())  //Если искомое меньше середины
    {
        return Binary_find(g, P_C->Next, P_B);  //Ищем в правой части
    }
    else
    {
        return Binary_find(g, P_A, P_C);  //Иначе ищем в левой
    }
}

#include "student.h"
 
struct Node                             //Структура, являющаяся звеном списка
 {
     Student x;                             //Значение x будет передаваться в список
     Node *Next, *Prev;                 //Указатели на адреса следующего и предыдущего элементов списка
 };
 typedef Node *list;
 
 class MyList                              //Создаем тип данных Список
 {
public:
     Node *Head, *Tail;                 //Указатели на адреса начала списка и его конца
     MyList():Head(NULL),Tail(NULL){};    //Инициализируем адреса как пустые
     ~MyList();                           //Прототип деструктора
     void Show();                       //Прототип функции отображения списка на экране
     void Add(Student x);                   //Прототип функции добавления элементов в список
 };
 
MyList::~MyList()                           //Деструктор
 {
     while (Head)                       //Пока по адресу на начало списка что-то есть
     {
         Tail = Head->Next;             //Резервная копия адреса следующего звена списка
         delete Head;                   //Очистка памяти от первого звена
         Head = Tail;                   //Смена адреса начала на адрес следующего элемента
     }
 }
 
 void MyList::Add(Student x)
 {
   Node *temp = new Node;               //Выделение памяти под новый элемент структуры
   temp->Next = NULL;                   //Указываем, что изначально по следующему адресу пусто
   temp->x = x;                         //Записываем значение в структуру
 
   if (Head != NULL)                    //Если список не пуст
   {
       temp->Prev = Tail;               //Указываем адрес на предыдущий элемент в соотв. поле
       Tail->Next = temp;               //Указываем адрес следующего за хвостом элемента
       Tail = temp;                     //Меняем адрес хвоста
   }
   else //Если список пустой
   {
       temp->Prev = NULL;               //Предыдущий элемент указывает в пустоту
       Head = Tail = temp;              //Голова=Хвост=тот элемент, что сейчас добавили
   }
 }