двунаправленный кольцевой список

Question

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

добавление элемента после последнего;

добавление элемента перед первым;

добавление элемента по порядку (предполагается, что элемент в динамической структуре отсортированы, и необходимо, чтобы добавление нового элемента не нарушило упорядоченности);

удаление элемента с указанной информационной частью; поиск элемента;

удаление всех элементов.

сортировка элементов;

упорядочение текущего элемента (предполагается, что все остальные элементы упорядочены);

перегруженный оператор !, определяющий существование элементов в структуре данных;

копирование структуры данных с помощью перегруженного оператора присваивания;

При разработке класса для работы со списками также должны быть реализованы следующие поля и методы:

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

получение копии информационной части текущего элемента (возвращает удачность операции);

перегруженный оператор ++ (префиксный) для перехода к следующему элементу;

перегруженный оператор -- (префиксный) для перехода к предыдущему элементу (для двунаправленного списка);

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

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

В качестве алгоритма сортировки при работе со списками использовать сортировки, не требующие доступа к произвольному элементу списка (например эффективные разновидности алгоритма вставки и т.п.), а при работе с массивом − быструю сортировку (сортировку Хоара).

При разработке класса в его методах НЕ ДОЛЖНЫ использоваться функции ввода/вывода для работы с консолью.

Помогите реализовать оставшиеся методы выделил их жирным

#include<cstdio>
#include<cstdlib>
using namespace std;

//структура узла

struct node
{
    int info;
    struct node* next;
    struct node* prev;
}*start, * last;
int counter = 0;
//объявление класса
class double_clist
{
public:
    node* create_node(int);
    void push_front(int value);
    void push_back(int value);
    void pop_front();
    void pop_back();
    void insert_pos(int value, int pos);
    void delete_pos(int pos);
    void search(int value);
    void update(int value, int pos);
    void display();
    void reverse();
    void sort();
    void clear();
    double_clist()
    {
        start = NULL;
        last = NULL;
    }
};

//главная функция
int main()
{
    double_clist cdl;
 
    cdl.push_back(4);
    cdl.push_back(4);


    return 0;
}

//создание узла
node* double_clist::create_node(int value)
{
    counter++;
    struct node* temp;
    temp = new(struct node);
    temp->info = value;
    temp->next = NULL;
    temp->prev = NULL;
    return temp;
}
//добавление элемента в начало
void double_clist::push_front(int value)
{
    struct node* temp;
    temp = create_node(value);
    if (start == last && start == NULL)
    {
        start = last = temp;
        start->next = last->next = NULL;
        start->prev = last->prev = NULL;
    }
    else
    {
        temp->next = start;
        start->prev = temp;
        start = temp;
        start->prev = last;
        last->next = start;
    }
}

//добавление элемента в конец
void double_clist::push_back(int value)
{

    struct node* temp;
    temp = create_node(value);
    if (start == last && start == NULL)
    {
        start = last = temp;
        start->next = last->next = NULL;
        start->prev = last->prev = NULL;
    }
    else
    {
        last->next = temp;
        temp->prev = last;
        last = temp;
        start->prev = last;
        last->next = start;
    }
}
//удаление элемента с начала
void double_clist::pop_front()
{
    node* ptr = nullptr, * s;
    if (start == last && start == NULL)
    {
        return;
    }
    s = start;
    counter--;
    last->next = s->next;
    s->next->prev = last;
    start = s->next;
    free(s);
    return;
}
//удаление элемента с конца
void double_clist::pop_back()
{
    node* ptr = nullptr, * s;
    if (start == last && start == NULL)
    {
        return;
    }
    s = start;
    for (int i = 0; i < counter - 1; i++)
    {
        s = s->next;
        ptr = s->prev;
    }
    ptr->next = s->next;
    s->next->prev = ptr; 
    last = ptr;
    counter--;
    free(s);
}
//добавление элемента по индексу
void double_clist::insert_pos(int value, int pos)
{
    struct node* temp, * s, * ptr;
    temp = create_node(value);
    if (start == last && start == NULL)
    {
        if (pos == 1)
        {
            start = last = temp;
            start->next = last->next = NULL;
            start->prev = last->prev = NULL;
        }
        else
        {
            counter--;
            return;
        }
    }
    else
    {
        if (counter < pos)
        {
            counter--;
            return;
        }
        s = start;
        for (int i = 1; i <= counter; i++)
        {
            ptr = s;
            s = s->next;
            if (i == pos - 1)
            {
                ptr->next = temp;
                temp->prev = ptr;
                temp->next = s;
                s->prev = temp;
                break;
            }
        }
    }
}
//удаление элемента из указанной позиции
void double_clist::delete_pos(int pos)
{
    node* ptr=nullptr, * s;
    if (start == last && start == NULL)
    {
        return;
    }
    if (counter < pos)
    {
        return;
    }
    s = start;
    if (pos == 1)
    {
        counter--;
        last->next = s->next;
        s->next->prev = last;
        start = s->next;
        free(s);
        return;
    }
    for (int i = 0; i < pos - 1; i++)
    {
        s = s->next;
        ptr = s->prev;
    }
    ptr->next = s->next;
    s->next->prev = ptr;
    if (pos == counter)
    {
        last = ptr;
    }
    counter--;
    free(s);
}
//обновление данных в указанном узле
void double_clist::update(int value, int pos)
{
    if (start == last && start == NULL)
    {
        return;
    }
    struct node* s;
    if (counter < pos)
    {
        return;
    }
    s = start;
    if (pos == 1)
    {
        s->info = value;
        return;
    }
    for (int i = 0; i < pos - 1; i++)
    {
        s = s->next;
    }
    s->info = value;
}
//поиск элемента в списке
void double_clist::search(int value)
{
    int pos = 0;
    bool flag = false;
    struct node* s;
    if (start == last && start == NULL)
    {
        return;
    }
    s = start;
    for (int i = 0; i < counter; i++)
    {
        pos++;
        if (s->info == value)
        {
            flag = true;
        }
        s = s->next;
    }
}
//сортировка списка
void double_clist::sort()
{
    struct node* temp, * s;
    int value, i;
    if (start == last && start == NULL)
    {
        return;
    }
    s = start;
    for (i = 0; i < counter; i++)
    {
        temp = s->next;
        while (temp != start)
        {
            if (s->info > temp->info)
            {
                value = s->info;
                s->info = temp->info;
                temp->info = value;
            }
            temp = temp->next;
        }
        s = s->next;
    }
}
//очистка всего списка
void double_clist::clear()
{
    if (start == last && start == NULL)
    {
        return;
    }
    while (counter > 0)
    {
        pop_back();
    }
}
//вывод на экран
void double_clist::display()
{
    int i;
    struct node* s;
    if (start == last && start == NULL)
    {
        return;
    }
    s = start;
    for (i = 0; i < counter - 1; i++)
    {
        cout << s->info << "<->";
        s = s->next;
    }
    cout << s->info << endl;
}
//перевернуть список наоборот
void double_clist::reverse()
{
    if (start == last && start == NULL)
    {
        return;
    }
    struct node* p1, * p2;
    p1 = start;
    p2 = p1->next;
    p1->next = NULL;
    p1->prev = p2;
    while (p2 != start)
    {
        p2->prev = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = p2->prev;
    }
    last = start;
    start = p1;
}```

БЛОГ НА HUSL

двунаправленный кольцевой список

Ответы (0 шт):