16.24

#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;

struct node
{
    int data;
    node * next;
};
void setNull(node *&p)
{
    p = NULL;
}
void createElement(node *&p, int y)
{
    p = new node;
    p->data = y;
    p->next = NULL;
}
void addFirst(node *&head1, node *p)
{
    p->next = head1;
    head1 = p;
}
void addLast(node *&head1, node *&tail, node *p)
{
    tail->next = p;
    tail = p;
}
void setHead(node *head1, node *&p)
{
    p = head1;
}
bool nodeIsNull(node *p)
{
    return p == NULL;
}
bool nextNodeIsNull(node *p)
{
    return p->next == NULL;
}
bool next2NodeIsNull(node *p)
{
    return p->next->next == NULL;
}
void showNode(node *p)
{
    cout << p->data << ' ';
}
void move(node *&p)
{
    p = p->next;
}
bool compareData(node *p1, node *p2)
{
    return p1->data == p2->data;
}
void nextNull(node *d)
{
    d->next = NULL;
}
void nextNode(node *&p, node *d)
{
    p->next = d;
}
void nodeNext(node *&p, node *d)
{
    p = d->next;
}
bool listIsEmpty(node *head1)
{
    return head1 == NULL;
}

void createListFromFile(node * &head1, ifstream &f)
{
    node * q; int x;
    setNull(head1);
    while (f.peek()!=EOF)
    {
        f >> x;
        createElement(q, x);
        addFirst(head1, q);
    }
}
void createListFromFileTail(node * &head1, ifstream &f)
{
    head1 = new node;
    head1->next = NULL;
    node * tail = head1;
    node * q;
    int x;
    while (f.peek() != EOF)
    {
        f >> x;
        createElement(q, x);
        addLast(head1, tail, q);
    }
    setHead(head1, q);
    move(head1);
    delete q;
}
void showList(node * head1)
{
    if (head1) {
        node * q;
        setHead(head1, q);
        while (!nodeIsNull(q))
        {
            showNode(q);
            move(q);
        }
        cout << endl;
    }
    else cout << "Список пустой" << endl;
}
bool point_A(node *head, int x) // входит ли элемент Х в список
{
    node *p, *q = new node;
    q->data = x;
    setHead(head, p);
    while (p)
    {
        if (compareData(p, q))
            return true;
        else {
            if (nextNodeIsNull(p))
            {
                return false;
                break;
            }
            else
            {
                move(p);
                point_A(p, x);
            }
        }
    }
}
int point_B(node *head, int x) // подсчитывает кол-во вхождений Х в список
{
    node *p, *q = new node;
    q->data = x;
    setHead(head, p);
    int k = 0;
    bool t = false;
    while (p)
    {
        if (compareData(p, q))
        {
            t = true;
            k++;
            move(p);
            point_B(p, x);
        }
        else {
            if (!nextNodeIsNull(p))
            {
                move(p);
                point_B(p, x);
            }
            else break;
        }
    }
    return k;
}
int point_V(node *head) // макс элемент в списке
{
    node *p;
    setHead(head, p);
    int max = head->data;
    if (p->data > max)
    {
        max = p->data;
        move(p);
    }
    else {
        if (!nextNodeIsNull(p))
        {
            move(p);
            point_V(p);
        }
        return max;
    }
}
void point_G(node *&head1) // печатает в обратном порядке
{
    if (nextNodeIsNull(head1))
        cout << head1->data << " ";
    else
    {
        point_G(head1->next);
        cout << head1->data << " ";
    }
}
void point_D(node *&head1, int x, int y) // заменяет все вхождения X на Y
{
    node *q, *p = new node;
    p->data = y;
    setHead(head1, q);
    while (q)
    {
        if (q->data == x)
        {
            q->data = p->data;
            move(q);
        }
        else {
            if (!nextNodeIsNull(q))
            {
                move(q);
                point_D(q, x, y);
            }
            else break;
        }
    }
}
node* prev(node* head, node* p)
{
    node* pr, *q;
    q = head;
    pr = NULL;
    while (q != p && q)
    {
        pr = q;
        q = q->next;
    }

    if (q == p) return pr;
    return NULL;
}
void point_E(node*&head, int x) // удаляет первое вхождение эл-та Х
{
    node*q, *p;
    setHead(head, q);
    setNull(p);
    if (head->data == x)
    {
        head = head->next;
        q->next = NULL;
        delete q;
    }
    else
        if (!nextNodeIsNull(q))
            if (head->next->data == x)
            {
                nodeNext(p, q);
                q->next = q->next->next;
                delete p;
            }
            else point_E(q->next, x);
}
void point_J(node*&head, int x) // удаляет все вхождения эл-та Х
{
    node *p, *q = new node, *r;
    q->data = x;
    setHead(head, p);
    while (p)
    {
        if (compareData(p, q))
        {
            node * w = p;
            r = prev(head, p);
            r->next = p->next;
            delete w;
            move(p);
            point_J(p, x);
        }
        else {
            if (!nextNodeIsNull(p))
            {
                move(p);
                point_J(p, x);
            }
            else break;
        }
    }
}
void point_Z(node *&head1, node *&head2) // строит копию списка
{
    node *q1, *q2;
    setHead(head1, q1);
    setNull(head2);
    while (q1) {
        createElement(q2, q1->data);
        addFirst(head2, q2);
        move(q1);
        point_Z(q1, q2);
    }
    point_G(head2);
}
void point_I(node *&head, int x) // удваивает каждое вхождение элемента Х
{
    if (head)
    {
        node *q, *p;
        setHead(head, q);
        if (q)
        {
            if (q->data == x)
            {
                p = new node;
                p->data = x;
                nextNode(p, q->next);
                nextNode(q, p);
                move(q);
            }
            if (q)
                point_I(q->next, x);
        }
    }
}
int point_K(node *head) // находит сред ариф значение всех элементов
{
    int sum = 0, c = 0;
    double n;
    while (head)
    {
        sum = sum + head->data;
        c += 1;
        if (!nextNodeIsNull(head))
        {
            move(head);
            point_K(head);
        }
        else break;
    }
    n = sum / c;
    return n;
}
int main()
{
    setlocale(LC_ALL, "Russian");

    ifstream f("Text.txt");
    node *head1 = NULL;
    createListFromFileTail(head1, f);
    cout << "Ваш список А: " << endl;
    showList(head1);
    cout << endl;

    if (head1) {
        //cout << "Входит ли элемент в список?: " << point_A(head1, 2) << endl; // А
        //cout << "Максимальный элемент в списке = " << point_V(head1) << endl; // В
        //cout << "Среднее ариф-е элементов списка = " << point_K(head1) << endl; // K

        //cout << "Переворачивает список: "; // Г
        //point_G(head1); cout << endl;

        node *head2;
        //cout << "Копия списка: "; point_Z(head1, head2); showList(head2); // З

        if (point_A(head1, 1))
        {
            //cout << "Сколько раз входит Х в список?: " << point_B(head1, 1) << endl; // Б
            //cout << "Заменяет все вхождения Х на Y: "; point_D(head1, 1, 3); showList(head1); // Д
              cout << "Удаляет первое вхождение Х: "; point_E(head1, 1); showList(head1); // Е
            //cout << "Удваивает каждое вхождение Х: "; point_I(head1, 1); showList(head1); // И
        }
        else cout << "Нет такого элемента" << endl;
    }
    else cout << "Список пустой" << endl;

    system("pause");
    return 0;
}