#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <string>
using namespace std;
const unsigned NMAX=100;
typedef unsigned adresa;
struct nod {int info; adresa urm;};
nod lista[NMAX+1];
int nr_el,liber[NMAX];

int este_plina()
{
    return nr_el==NMAX;
}
int este_vida(adresa prim)
{
    return prim==NULL;
}
void init()
{
    nr_el=0;
    for (adresa p=1; p<=NMAX; p++)
        liber[p]=1;
}
adresa aloc_mem()
{
    adresa p; for (p=1; !liber[p];p++)
    liber[p]=0; nr_el++;
    return p;
}
void adaug_prim(adresa &prim, int n)
{
    prim=aloc_mem();
    lista[prim].info=n; lista[prim].urm=NULL;
}
void adauga_ultim(adresa q, int n)
{
    adresa p=aloc_mem();
    lista[p].info=n; lista[q].urm=p; lista[p].urm=NULL;
}
adresa cauta(adresa prim, int n)
{
    adresa p=prim;
    while(lista[p].info<n && lista[p].urm!=NULL) p=lista[p].urm;
    return p;
}
void adauga_in_fata(adresa q, int n)
{
    adresa p=aloc_mem();
    lista[p].urm=lista[q].urm; lista[q].urm=p;
    lista[p].info=lista[q].info; lista[q].info=n;
}
void creare(adresa &prim)
{
    adresa q; int n; init(); cout<<"Numar "; cin>>n;
    adaug_prim(prim,n);
    cout<<"Numar "; cin>>n;
    while (n!=0&& !este_plina())
    {
        q=cauta(prim,n);
        if (lista[q].info<n)
            adauga_ultim(q,n);
        else adauga_in_fata(q,n);
        cout<<"Numar "; cin>>n;
    }
}
void afiseaza (adresa prim)
{
    for (adresa p=prim; p!=NULL; p=lista[p].urm)
        cout<<lista[p].info<<" ";
}
int main()
{
    adresa prim; creare(prim);
    afiseaza(prim);
    getch();
    if (!este_vida) afiseaza(prim);
    else cout<<"Nu exista elemente";
}