[AiSD] 3. Listy

#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;
}

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       //jesli cos jest
        n->next = head;
    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)
    {
        cout<<"Nie ma takiego elementu"<<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;
}

int main(){
    wezel *head = 0;
    add(head, 5);
    add(head, -2);
    add(head, 7);
    add(head, 3);
    add(head, 1);
    add(head, 10);
    add(head, 8);
    print(head);
    search(head,-1);
    usun(head, -2);
    usun(head, 8);
    print(head);
    usun_liste(head);
    print(head);
    add(head, 3);
    add(head, 1);
    add(head, 10);
    add(head, 8);
    add(head, 5);
    add(head, 8);
    print(head);
    poprzedni(head, 8);
    cout<<endl<<endl<<endl;
    //============

    wezel2 *head2 = 0;
    add2(head2, 1);
    add2(head2, 8);
    add2(head2, 4);
    add2(head2, -4);
    add2(head2, 5);
    add2(head2, 3);
    add2(head2, 1);
    print2(head2);
    usun2(head2, 3);
    print2(head2);
    usun_liste2(head2);
    print2(head2);
    add2(head2, -4);
    add2(head2, 5);
    add2(head2, 5);
    add2(head2, 4);
    add2(head2, 3);
    add2(head2, 1);
    add2(head2, 1);
    add2(head2, 1);
    poprzedni2(head2, 5);
    print2_from_end(head2);


    print2(head2);
    return 0;
}