Untitled

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>



typedef struct Node
{
    int data; // поле данных
    struct Node* next; // указатель на следующий элемент списка
} Node;

//
int Menu();

void Append( Node** lst, int value ); // Swap( int* a, int* b )  Print( int val ); .... Print(a);
//
void InsertHead( Node** lst, int value );
//
void Print( Node* lst );
//
void DeleteTail( Node** lst );
//
int InList( Node* lst, int value );
// удалить элемент с начала списка
void DeleteHead( Node** lst );
// вставить новый элемент val после первого найденного значения sought
void InsertAfter( Node* lst, int sought, int val );

// вставить новый элемент val перед первым найденным значением sought
void InsertBefore( Node** lst, int sought, int val );

void Destroy( Node** lst );
//
void DeleteAfter( Node* lst, int sought );
//
void DeleteBefore( Node** lst, int sought );
// функция удаляет все чётные элементы из списка
void DeleteEven( Node** lst );
// функция меняет местами первый нечётный и последний чётный элементы 1 3 2 4 7 6 11
void SwapOddEven ( Node* lst );
//
void SwapMinMax( Node* lst );
//
int DeleteElem( Node** lst, Node* elem );
// функция возвращает указатель на последний чётный элемент
Node* GetLastEven( Node* lst );

int main()
{

    SetConsoleCP( 1251 );
    SetConsoleOutputCP( 1251 );

    Node* head = NULL;

    int key;
    do
    {
        key = Menu();

        switch ( key )
        {
        case 1:
        {
            int val;
            printf( "Введите элемент: " );
            scanf( "%d", &val );
            Append( &head, val );
            break;
        }
        case 2:
        {
            int val;
            printf( "Введите элемент: " );
            scanf( "%d", &val );
            InsertHead( &head, val );
            break;
        }

        case 3:
        {
            DeleteTail( &head );
            break;
        }

        case 4:
        {
            DeleteHead( &head );
            break;
        }

        case 5:
        {
            int val;
            printf( "Введите элемент: " );
            scanf( "%d", &val );
            if ( InList( head, val ) )
                puts( "Элемент в списке" );
            else
                puts( "Элемент НЕ найден" );
            break;
        }

        case 6:
        {
            Print( head );
            break;
        }

        case 7:
        {
            Destroy ( &head );
            break;
        }

        case 8:
        {
            int sought, val;
            printf( "\nВыберете элемент для поиска " );
            scanf( "%d", &sought );
            printf( "\nВведите элемент для вставки " );
            scanf( "%d", &val );
            InsertAfter( head, sought, val );
            break;
        }
        case 9:
        {
            int sought, val;
            printf( "\nВыберете элемент для поиска " );
            scanf( "%d", &sought );
            printf( "\nВведите элемент для вставки " );
            scanf( "%d", &val );
            InsertBefore( &head, sought, val );
            break;
        }
        case 10:
        {
            int sought;
            printf( "\nВыберете элемент, после которого удалить элемент " );
            scanf( "%d", &sought );
            DeleteAfter( head, sought );
            break;
        }
        case 11:
        {
            int sought;
            printf( "\nВыберете элемент, перед которым удалить элемент " );
            scanf( "%d", &sought );
            DeleteBefore( &head, sought );
            break;
        }
        case 12:
        {
            DeleteEven( &head );
            break;

        }
        case 13:
        {
            SwapOddEven ( head );
            break;
        }
        case 14:
        {
            SwapMinMax( head );
            break;
        }
        case 15:
        {
            Node* el = GetLastEven( head );
            if ( DeleteElem( &head, el ) )
                puts( "Последний чётный элемент успешно удалён" );
            else
                puts( "Чётных элементов в списке не найдено" );
            break;
        }

        }
    }
    while ( key != 0 );

    if ( NULL != head )
        Destroy ( &head );

    return 0;
}


int Menu()
{
    puts( "\n\nВыберете пункт меню" );
    puts( "1 - Добавить в конец списка" );
    puts( "2 - Добавить в начало списка" );
    puts( "3 - Удалить с конца списка" );
    puts( "4 - Удалить с начала списка" );
    puts( "5 - Найти элемент в списке" );
    puts( "6 - Распечатать весь список" );
    puts( "7 - Очистить список" );
    puts( "8 - Вставить после" );
    puts( "9 - Вставить до" );
    puts( "10 - Удалить после" );
    puts( "11 - Удалить до" );
    puts( "12 - Удалить все четные элементы" );
    puts( "13 - Поменять местами первый нечетный и последний четный элементы" );
    puts( "14 - Поменять местами min и max" );
    puts( "15 - Удалить последний четный элемент" );
    puts( "0 - Выход из программы" );

    int key;
    printf( "\nВыбор: " );
    scanf( "%d", &key );

    return key;
}

void Append( Node** lst, int value )
{
    Node* elem = ( Node* )malloc( sizeof( Node ) ); // Node* - тип elem - это указатель на новый элемент
    elem->data = value;
    //(* elem).data = value;
    elem->next = NULL;

    // если список пуст
    if ( *lst == NULL )
    {
        *lst = elem;
        return;
    }


    // если список не пустой
    Node* curr = *lst; // lst - адрес головы списка; *lst - адрес первого элемента списка (содержимое головы списка)
    while ( curr->next != NULL ) // curr->next == (*curr).next
        curr = curr->next;

    curr->next = elem;
}

// с правками
void InsertHead( Node** lst, int value )   // ** хотим менять значение, которое содержатся в head
{
    Node* elem = ( Node* )malloc( sizeof( Node ) ); // elem - указатель на новый элемент в списке, который хранит его адрес
    elem->data = value;

    // если список пустой
    if ( *lst == NULL )
        elem->next = NULL;
    else
        // если в спике есть хотябы один элемент
        elem->next = *lst;

    *lst = elem;
}

// 7 6 0 5 --> NULL , 12, 8
// 7 --> NULL, 7, 34
void InsertAfter( Node* lst, int sought, int value )
{

    while ( lst != NULL )
    {
        if ( lst->data == sought )
            break;

        lst = lst->next;
    }

    if ( lst == NULL )
        return;

    Node* elem = ( Node* )malloc( sizeof ( Node ) );
    elem->data = value;

    // Node* curr = lst->next; переписать без curr
    elem->next = lst->next;
    lst->next = elem;



}


void DeleteAfter( Node* lst, int sought )
{

    if ( lst == NULL || lst->next == NULL )
        return;

    Node* curr = lst;
    Node* post = lst->next;
    //1 2 3 4
    while ( post != NULL )
    {
        if ( curr->data == sought )
            break;

        curr = post;
        post = post->next;
    }

    if ( post != NULL )
    {
        curr->next = post->next;
        free( post );
    }
}

// 4
// 1 2 3 4 5
void DeleteBefore( Node** lst, int sought )
{

    if ( *lst == NULL || ( *lst )->next == NULL )
        return;

    // 6
    // 1 2 3 4 5 --> NULL
    Node* post = ( *lst )->next;
    if ( post->data == sought )
    {
        free( *lst );
        *lst = post;
        return;
    }


    post = post->next;
    Node* curr = *lst;
    while ( post != NULL )
    {
        if ( post->data == sought )
            break;

        curr = curr->next;
        post = post->next;
    }

    if ( post != NULL )
    {
        free( curr->next );
        curr->next = post;
    }
}



void DeleteEven( Node** lst )
{
    // 1) удаляем ВСЕ чётные элементы в начале списка
    Node* curr = *lst;
    while ( curr != NULL )
    {

        if ( curr->data % 2 != 0 ) // если встретили нечетный элемент,
            break; // то обрываем цикл, чтобы в голову списка записать адрес этого элемента

        Node* del = curr; // запоминаем в копию адрес элемента, который нужно удалить
        curr = curr->next; // переходим на следующий элемент списка
        free( del ); // удаляем текущий четный элемент
    }
    // на выходе из цикла в указателе curr будет либо NULL, либо адрес первого нечётного элемента в списке
    *lst = curr; // в голову списка запишем адрес из указателя сurr

    if ( *lst == NULL )
        return;


    Node* post = ( *lst )->next;
// 1 2 3 4 5 ->null
    while( post != NULL )
    {
        if ( post->data % 2 == 0 ) {
                 free( post );
            post = post->next;
            curr->next = post;



        }

        curr = curr->next;
        post = post->next;
    }

    if( post == NULL )
        return;

}


// сюда попадаем только тогда когда в голове списка находится нечетный элемент

/*
    if ( ( *lst )->next == NULL && ( *lst )->data % 2 == 0 ) {
        free( *lst );
        *lst = NULL;
        return;
    }

     Node* curr = *lst; // адрес первого элемента списка
       Node* post = ( *lst )->next;
       Node* odd = NULL, *even = NULL;

       while ( curr != NULL ) {

           if ( curr->data % 2 == 0 ) {

               free( curr );
               curr->next = post;
           }

           if ( curr->data % 2 != 0 )
               odd = curr;

           curr->next = post;
           post = post->next;

       }*/





void InsertBefore( Node** lst, int sought, int value )
{
    // 7 10
    // 5 6 7 11 --> NULL
    if ( *lst == NULL )
        return;

    if ( ( *lst )->data == sought )
    {
        Node* elem = ( Node* )malloc( sizeof ( Node ) );
        if ( elem != NULL )
        {
            elem->data = value;
            elem->next = *lst;
            *lst = elem;
        }
        return;
    }

    Node* curr = *lst, *post = ( *lst )->next;
    while ( post != NULL )
    {
        if ( post->data == sought )
            break;

        curr = post;
        post = curr->next;


    }
    //       10
    // 1 3 5   6 7 -> NULL
    //
    if ( post != NULL )
    {
        Node* elem = ( Node* )malloc( sizeof ( Node ) );
        if ( elem != NULL )
        {
            elem->data = value;
            elem->next = post;
            curr->next = elem;
        }
    }
}

// с правками
void DeleteTail( Node** lst )
{

    if ( *lst == NULL )
        return;

    // lst->next
    //
    if ( ( *lst )->next == NULL )   // если в списке есть один элемент
    {
        free( *lst );
        *lst = NULL;
        return;
    }

    Node *curr = *lst;
    // чтобы удалить элемент в конце списка необходимо пройти циклом до предпоследнего элемента
    // 5 --> 12 --> 15 --> 8 --> NULL
    while ( curr->next->next != NULL )
        curr = curr->next;

    free( curr->next );
    curr->next = NULL;
}

// с правками
void DeleteHead( Node** lst )
{

    if ( *lst == NULL ) // если список пустой
        return;

    if ( ( *lst )->next == NULL )   // если список содержит один элемент
    {
        free( *lst );
        *lst = NULL;
        return;
    }

    // если в списке больше одного элемента
    Node* second = ( *lst )->next; // записываем адрес второго элемента в указатель second
    free( *lst );
    *lst = second;
}

void Print( Node * lst )
{
    if ( lst == NULL )
    {
        puts( "\nСписок пуст" );
        return;
    }

    while ( lst != NULL )
    {
        printf( "%d ", lst->data );
        lst = lst->next;
    }

    return;
}

int InList( Node * lst, int value )
{
    while ( lst != NULL )
    {
        if ( lst->data == value )
            return 1;
        lst = lst->next;
    }

    return 0;
}

void Destroy( Node** lst )
{
    if ( *lst == NULL )
        return;

    if ( ( *lst )->next == NULL )   // если список содержит один элемент
    {
        free( *lst );
        *lst = NULL;

        return;
    }

    Node* curr = *lst; // адрес первого элемента списка
    Node* post = ( *lst )->next; // адрес второго/следующего элемента списка

    //9 --> NULL
    while ( post != NULL  )
    {
        free( curr );
        curr = post;
        post = curr->next;
    }

    free( curr );
    *lst = NULL;
}

void SwapOddEven( Node* lst )
{
    // 2 4 3 6 7 8 11 -> NULL
    // 2

    Node* odd = NULL, *even = NULL;
    while ( lst != NULL )
    {
        if ( lst->data % 2 != 0 && odd == NULL ) // если odd == NULL значит не находили нечетный элемент
            odd = lst; // если встретили первый нечетный элемент, то запоминаем его адрес

        if ( lst->data % 2 == 0 )
            even = lst;

        // 2 2 2 2 2 1
        lst = lst->next; // переход на следующий элемент списка в цикле
    }

    if ( odd != NULL && even != NULL )
    {
        int temp = odd->data;
        odd->data = even->data;
        even->data = temp;

    }

// после выполнения цикла адрес первого нечетного элемента остаётся в odd
}

void SwapMinMax( Node* lst )
{
    // 1 2 4 6 7 9 -> NULL

    if ( lst == NULL || lst->next == NULL )
        return;

    Node* curr = lst->next;
    Node* max = lst, *min = lst;

    while ( curr != NULL )
    {
        if ( curr->data > max->data )
            max = curr;

        if ( curr->data < min->data )
            min = curr;

        curr = curr->next;
    }
    if ( max != min )
    {
        int temp = min->data;
        min->data = max->data;
        max->data = temp;
    }

}

// 1 4 8 9 7 --> NULL

Node* GetLastEven( Node* lst )
{
    Node* elem = NULL;

    while ( lst != NULL )
    {
        if ( lst->data % 2 == 0 )
            elem = lst;

        lst = lst->next;
    }

    return elem;
}

// 3 5 9 4 7
int DeleteElem( Node** lst, Node* elem )
{

    if ( *lst == NULL || elem == NULL )
        return 0; // return 0 - ничего не удалено, а return 1 что-то удалено

    if ( *lst == elem )
    {
        *lst = ( *lst )->next;
        free( *lst ); // free(elem)
        return 1;
    }
    else
    {
        // попадаем в else, если в голове списка нет совпадения
        Node* curr = *lst;
        Node* post = ( *lst )->next;
        while ( post != NULL )
        {
            if ( post == elem )
                break;

            curr = curr->next;
            post = post->next;
        }

        if ( post != NULL )
        {
            curr->next = post->next;
            free( post );
            return 1;
        }
    }

    return 0;
}