Lista z zamianą

#include <iostream>
using namespace std;

//===========================
//JEDNOKIERUNKOWA
//===========================
struct wezel{
    wezel *next;
    int key;
};

void print(wezel *head)
{
    cout<<"[LISTA] ";
    if(head==NULL)
        cout<<"Lista jednokierunkowa pusta";
    else
        while(head!=NULL)
        {
            if(head->next!=0)
                cout<<head->key<<" -> ";
            else
                cout<<head->key;
            head = head->next;
        }
    cout<<endl;
}

//DODAWANIE ELEMENTOW WEDLUG WARTOSCI, CZYLI SORTOWANIE
void add(wezel *&head, int key)
{
    wezel * n = new wezel;
    n->key = key;
    if(head == NULL)
    {
        head = n;
        n->next = 0;
    }
    else
    {
        if(head->key > key)
        {
            n->next = head;
            head = n;
        }
        else
        {
            wezel *p = head;
            wezel *x = head->next;
            while(x != NULL && x->key <= key)
            {
                p = x;
                x = x->next;
            }
            n->next = x;
            p->next = n;
        }
    }
}

void search(wezel* head,int key)
{
    while(head!=NULL && key != head->key)
        head= head->next;
    if(head!=0)
        cout<<"Element o kluczu: "<<key<< " istnieje i znajduje sie pod adresem: "<<head<<endl;
    else
        cout<<"Element o kluczu: "<<key<< " nie istnieje"<<endl;
}

void usun(wezel *& head, int key)
{
    if(head == NULL)
        cout<<"Lista pusta"<<endl;
    else if(head->key > key)
    {
        cout<<"Nie ma takiego elementu"<<endl;
    }
    else if(head->key == key)
    {
        wezel *p = head->next;
        delete head;
        head = p;
        cout<<"Usunieto head o kluczu: "<<key<<endl;
    }
    else
    {
        wezel *p, *n;
        p = head;
        n = head->next;
        for( ; n != 0; n = n->next)
        {
            if(key == n->key)
            {
                p->next = n->next;
                delete n;
                cout<<"Usunieto element o kluczu: "<<key<<endl;
            }
            else
                p = n;
        }
    }
}

void usun_liste(wezel * & head)
{
    wezel *p;
    while(head!=0)
    {
        p = head->next;
        delete head;
        head = p;
    }
    cout<<"Usunieto liste jednokierunkowa"<<endl;
}

void poprzedni(wezel * head, int x){
    wezel *p = head;
    wezel *poprzedni = head;
    for(p, poprzedni; p != NULL && poprzedni != NULL; p = p->next){
        if(x == head->key){
            cout << "To jest pierwszy element, przed nim nic nie ma" << endl;
            break;
        }
        if(p->key == x)
            cout << "Poprzednik "<< x<< " to "<<poprzedni->key << endl;
        if(p != head)
            poprzedni = poprzedni->next;
    }
}


//===========================
//DWUKIERUNKOWA
//===========================

struct wezel2{
    wezel2 *next;
    wezel2 *prev;
    int key;
};


void print2(wezel2 *head)
{
    cout<<"[LISTA] ";
    if(head==NULL)
        cout<<"Lista dwukierunkowa pusta";
    else
        while(head!=NULL)
        {
           if(head->next!=0)
                cout<<head->key<<" <-> ";
            else
                cout<<head->key;
            head = head->next;
        }
    cout<<endl;
}

void print2_from_end(wezel2 *head)
{
    cout<<"[LISTA - od konca] ";
    if(head==NULL)
        cout<<"Lista dwukierunkowa pusta";
    else
        while(head->next!=NULL)
            head = head->next;
        while(head!=NULL)
        {
            if(head->prev!=0)
                cout<<head->key<<" <-> ";
            else
                cout<<head->key;
            head = head->prev;

        }
    cout<<endl;
}

void poprzedni2(wezel2 * head, int x){
    wezel2 *p = head;
    for(p; p != NULL ; p = p->next){
        if(x == head->key){
            cout << "To jest pierwszy element, przed nim nic nie ma" << endl;
            break;
        }
        if(p->key == x)
            cout << "Poprzednik "<< x<< " to "<<p->prev->key << endl;
    }
}

void add2(wezel2 *&head, int key)
{
    wezel2 * n = new wezel2;
    n->key = key;
    if(head == NULL)    //jesli pusta
    {
        head = n;
        n->next = 0;
        n->prev = 0;
    }
    else
    {
        if(head->key > key) //jesli dodajemy przed head
        {
            n->next = head;
            n->prev = 0;
            head->prev = n;
            head = n;
        }
        else    //dodajemy za head
        {
            wezel2 *p = head;
            wezel2 *x = head->next;
            while(x != NULL && x->key <= key)
            {
                p = x;
                x = x->next;
            }
            if(x==NULL)
                n->next = 0;
            else
            {
                x->prev = n;
                n->next = x;
            }
            n->prev = p;
            p->next = n;
        }
    }
}

void dodaj_koniec2(wezel2* &head, int key)
{
    wezel2 * n = new wezel2;
    n->key = key;
    wezel2 *p = head;
    if(head==NULL)  //jesli jest pusta to dodawanie na koniec dodaje nowy head
    {
         head = n;
         n->next = 0;
         n->prev = 0;
    }
    else    //jesli juz cos jest to dodaje na koniec
    {
        while(p->next!=0)
            p = p->next;
        p->next = n;
        n->next = 0;
        n->prev = p;
    }
}

void dodaj_pocz2(wezel2* &head, int key)
{
    wezel2 * n = new wezel2;
    n->key = key;
    if(head==NULL)  //jesli jest pusta
         n->next = 0;
    else
    {
        n->next = head;
        n->next->prev = n;
    }
            //jesli cos jest

    head = n;
    n->prev = 0;
}

void usun2(wezel2 *& head, int key)
{
    //usuwa tylko pierwsze wyst¹pienie
    if(head == NULL)
        cout<<"Lista pusta"<<endl;
    else if(head->key == key)
    {
        wezel2 *p = head->next;
        delete head;
        head = p;
        head->prev = 0;
        cout<<"Usunieto head o kluczu: "<<key<<endl;
    }
    else
    {
        wezel2 *p, *n;
        p = head;
        n = head->next;
        while(n!=0 && key!=n->key)
        {
            p = n;
            n=n->next;
        }
        p->next = n->next;
        if(n->next!=0)
            n->next->prev = p;
        delete n;
        cout<<"Usunieto element o kluczu: "<<key<<endl;
    }
}

void usun_liste2(wezel2 * & head)
{
    wezel2 *p;
    while(head!=0)
    {
        p = head->next;
        delete head;
        head = p;
    }
    cout<<"Usunieto liste dwukierunkowa"<<endl;
}


//ZAMIANA SZUKANEGO ELEMENTU Z NASTEPNIKIEM
void zamien(wezel * & head, int x)
{
    wezel *p = head;    //wskazuje na poczatek listy
    wezel *q;           //wykorzystam do pamiętania poprzednika szukanego
    while(p->key != x && p->next!=NULL)  //szukamy danego x
    {
        q = p;
        p=p->next;
    }
    if(p == NULL)       //jesli nie ma szukanego x to while przejdzie przez cala liste az dojdzie do smieci i null
        cout<<"Nie ma takiego x"<<endl;
    else
    {
        if(p->next == NULL) //jesli jest x, ale nie ma nastepnika to nie mozemy zamienic
            cout<<"Jest taki x, ale nie ma nastepnika"<<endl;
        else    //jesli mozemy zamienic
        {
            //q aktualnie wskazuje poprzednika znalezionego elementu o wartosci x
            //p wskazuje aktualnie znalezniony element o wartosci x
            //w bedzie wskazywac nastepnika p
            //temp - zmienna tymczasowa do przechowania p
            wezel *w = p->next;
            wezel *temp = p;
            p = w;
            w = temp;
            w->next = p->next;
            p->next = w;
            q->next = p;

        }
    }
}

//ZAMIANA SZUKANEGO ELEMENTU Z POPRZEDNIKIEM
void zamien2(wezel * & head, int x)
{
    wezel *p = head;    //wskazuje na poczatek listy
    wezel *q;           //wykorzystam do pamiętania poprzednika szukanego
    while(p->key != x && p != NULL)  //szukamy danego x
    {
        q = p;
        p=p->next;
    }
    if(p == head)       //jesli element do zamiany to head
        cout<<"nie mozna zamienic z poprzednikiem, bo jest to pierwszy element na liscie"<<endl;
    else if(p == NULL)  //jesli nie ma szukanego x to while przejdzie przez cala liste az dojdzie do smieci i null
        cout<<"Nie ma takiego x";
    else    //jesli mozemy zamienic
    {
        if(q == head)   //jesli x jest drugim elementem na liscie to jego poprzednik to head
        {
            head = p;
            wezel *temp = p->next;
            p = q;
            head->next = p;
            p->next = temp;
        }
        else
        {
            //szukamy poprzednika poprzednika znalezionego elementu x
            wezel *pop = head;
            while(pop->next!=q)
                pop = pop->next;
            //temp wskazuje poprzenika elementu o wartosci x
            //tmp wskazuje nastepnika elementu o wartosci x
            //q wskazuje poprzednika elementu o wartosci x
            //p wskazuje element o wartosci x
            //pop wskazuje poprzednika q
            wezel *temp = q;
            wezel *tmp = p->next;
            q = p;
            p = temp;
            pop->next = q;
            q->next = p;
            p->next = tmp;
        }
    }
}

int main(){
    //dodawanie elementow do listy do testowania dzialania zamiany
    wezel *head = 0;
    add(head, 1);
    add(head, 2);
    add(head, 3);
    add(head, 4);
    add(head, 5);
    add(head, 6);
    add(head, 7);
    print(head);
    zamien2(head, 4);
    print(head);





    return 0;
}