ASD-31.10.17

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <string.h>
#include <stdlib.h>

typedef struct celula_lista
	{
	    int k;
		struct celula_lista *next;
	}
	LIST;

typedef struct coada
	{
	    LIST *front,*rear;
	}
	QUEUE;

struct lista
	{
	    int k;
        struct lista *next,*prev;
    };

typedef struct stiva
    {
        int k;
        struct stiva *next;
    }
    STIVA;

LIST *cons_lsi(int k,LIST *l);
LIST *init_l(LIST *l);
void tipar(LIST *l);
int maxim(LIST *l);
void aparitii_x(LIST *l);
void citire_matrice(int M[10][10],int *m,int *n);
LIST *liniarizare_matrice(LIST *l,int M[10][10],int m,int n);
LIST *suma_liste(LIST *l1,LIST *l2);
LIST *multime_lista(LIST *l);
void ordonare_lista(LIST *l);
LIST *inversare_lista(LIST *l);
LIST *interclasare_liste(LIST *l1,LIST *l2);
LIST *stergere_element_lista(LIST *l,int poz);
LIST *inserare_element_lista(LIST *l,int poz,int x);
LIST *stergere_elemente_pare_lista(LIST *l);
LIST *initializare_lista_crescatoare(LIST *l);
QUEUE *newq(QUEUE *q);
int emptyq(QUEUE *q);
QUEUE *addq(QUEUE *q,int e);
QUEUE *initializare_coada_cu_header();
void printq(QUEUE *q);
QUEUE *remq(QUEUE *q);
int frontq(QUEUE *q);
int prim(int x);
QUEUE *numere_prime_lista_in_coada(LIST *l,QUEUE *q);
struct lista *cons_ldi(int k,struct lista *l);
struct lista *init_ldi(struct lista *l);
void tipar_ldi(struct lista *l);
struct lista *stergere_element_ldi(struct lista *l,int poz);
struct lista *inserare_element_ldi(struct lista *l,int poz,int x);
STIVA *push(STIVA *vf, int x);
STIVA *creare();
void afisare(STIVA *vf);
STIVA *pop(STIVA *vf);
STIVA *mutare_prime_lista_in_stiva(LIST *l,STIVA *vf);
int main()
{
    /*
    struct lista *ldi;
    ldi=init_ldi(ldi);
    tipar_ldi(ldi);
    */
    LIST*l,*l1,*ls,*lm,*li;
    STIVA *s=NULL;
    /*
    QUEUE *q;
    q->front=q->rear=NULL;
    int M[10][10],m,n;
    */

    l=initializare_lista_crescatoare(l);
    printf("\n\nlista deja introdusa este:\n\n");
    tipar(l);

    s=mutare_prime_lista_in_stiva(l,s);
    afisare(s);
    /*
    q=numere_prime_lista_in_coada(l,q);
    printq(q);
    l=stergere_elemente_pare_lista(l);
    tipar(l);
    l=inversare_lista(l);
    printf("\nLista introdusa inversata este:\n");
    tipar(l);
    ordonare_lista(l);
    printf("\nLista introdusa ordonate este:\n");
    tipar(l);
    printf("\nMaximul elementelor din lista este %d.",maxim(l));
    aparitii_x(l);
    citire_matrice(M,&m,&n);
    l1=liniarizare_matrice(l1,M,m,n);
    printf("\nAceasta este liniarizarea matricei pe linii:\n");
    tipar(l1);
    ls=suma_liste(l,l1);
    printf("\nAceasta este suma listelor precedente:\n");
    tipar(ls);
    lm=multime_lista(lm);
    printf("\n\nLista multime introdusa este:\n\n");
    tipar(lm);
    li=interclasare_liste(l,lm);
    printf("\nAceasta este interclasarea listei initiale ordonate cu lista multime:\n");
    tipar(li);
    */



    return 0;
}
LIST *cons_lsi(int k,LIST *l)
{   LIST *aux;
    aux=(LIST *)malloc(sizeof(LIST));
    aux->k=k;
    aux->next=l;
    return(aux);
}
LIST *init_l(LIST *l)
{
    int ci,k;
    char c,ck,cc[5];
    l=NULL;

    printf("Doriti sa incepeti initializarea listei [n pentru terminare]?");
    scanf("%c",&c);
    if (c!='n')
       k=1;
    else
       k=-1;
    while (k!=-1)
    {
        printf(" Introduceti o cheie : ");
        scanf("%s",cc);
        if (strcmp(cc,"n"))
           k=1;
        else
           k=-1;
        ci=atoi(cc);
        if(k!=-1)
           l=cons_lsi(ci,l);
    }
    return(l);
}

void tipar(LIST *l)
{ LIST *p;
     for(p=l;p;p=p->next) printf("%d->",p->k);
     printf("NULL\n");
}

int maxim(LIST *l)
{
    LIST *p;
    int Max=l->k;
    for(p=l->next;p;p=p->next)
        if(p->k>Max)
        Max=p->k;
    return Max;
}

void aparitii_x(LIST *l)
{
    LIST *p;
    int x,nr=0;
    printf("\n\nIntroduceti numarul pe care doriti sa-l cautati in lista: ");
    scanf("%d",&x);
    for(p=l;p;p=p->next)
        if(p->k==x)
        nr++;
    if(!nr)
        printf("\nNumarul cautat nu se afla in lista.");
    else
        printf("\nNumarul cautat apare de %d ori in lista.",nr);
}

void citire_matrice(int M[10][10],int *m,int *n)
{
    int i,j;
    printf("\n\nIntroduceti numarul de linii, numarul de coloane\nsi apoi elementele matricei.\n");
    scanf("%d%d",m,n);
    for(i=0;i<*m;i++)
        for(j=0;j<*n;j++)
        scanf("%d",&M[i][j]);
}

LIST *liniarizare_matrice(LIST *l,int M[10][10],int m,int n)
{
    int i,j;
    l=NULL;
    for(i=m-1;i>=0;i--)
        for(j=n-1;j>=0;j--)
        l=cons_lsi(M[i][j],l);
    return l;
}

LIST *suma_liste(LIST *l1,LIST *l2)
{
    LIST *l=NULL,*ll=NULL,*p,*p1=l1->next,*p2=l2->next;
    l=cons_lsi(l1->k+l2->k,l);
    p=l;
    while(p1&&p2)
    {
        ll=cons_lsi(p1->k+p2->k,ll);
        p->next=ll;
        p=ll;
        p1=p1->next;
        p2=p2->next;
    }
    while(p1)
    {
        ll=cons_lsi(p1->k,ll);
        p->next=ll;
        p=ll;
        p1=p1->next;
    }
    while(p2)
    {
        ll=cons_lsi(p2->k,ll);
        p->next=ll;
        p=ll;
        p2=p2->next;
    }
    p->next=NULL;
    return l;
};

LIST *multime_lista(LIST *l)
{
    LIST *p1,*p2,*ll;
    int ci,k;
    char c,cc[5];
    l=NULL;
    printf("Doriti sa incepeti initializarea listei de tip multime[n pentru terminare]?\n");
    scanf("%c",&c);
    if (c!='n')
       k=1;
    else
       k=-1;
    while (k!=-1)
    {
        printf("Introduceti o cheie : ");
        scanf("%s",cc);
        if (strcmp(cc,"n"))
           k=1;
        else
           k=-1;
        ci=atoi(cc);
        if(k!=-1)
        {
            p1=NULL;
            for(p2=l;p2&&ci>p2->k;p2=p2->next)
                    p1=p2;
            ll=cons_lsi(ci,ll);
            if(!p1&&!p2)
            {
                l=ll;
                l->next=NULL;
            }

            if(!p1&&p2)
                if(ci!=p2->k)
                {
                    l=ll;
                    l->next=p2;
                }
            if(p1&&!p2)
            {
                p1->next=ll;
                ll->next=p2;
            }
            if(p1&&p2)
                if(ci!=p2->k)
                {
                    p1->next=ll;
                    ll->next=p2;
                }

        }
    }
    return(l);
};
void ordonare_lista(LIST *l)
{
    LIST *p,*q;
    int aux;
    for(p=l;p->next;p=p->next)
        for(q=p->next;q;q=q->next)
        if(p->k>q->k)
        {
            aux=p->k;
            p->k=q->k;
            q->k=aux;
        }
};

LIST *inversare_lista(LIST *l)
{
    LIST *p=l,*q=p->next,*r=q->next;
    while(q)
    {
        q->next=p;
        p=q;
        q=r;
        if(r)
            r=r->next;
    }
    l->next=NULL;
    l=p;
    return l;
};
LIST *interclasare_liste(LIST *l1,LIST *l2)
{
    LIST *l=NULL,*ll=NULL,*p,*p1=l1,*p2=l2;
    if(p1->k<p2->k)
    {
        l=cons_lsi(p1->k,ll);
        p1=p1->next;
    }
    else
    {
        l=cons_lsi(p2->k,ll);
        p2=p2->next;
    }
    p=l;
    while(p1&&p2)
    {
        if(p1->k<p2->k)
        {
            ll=cons_lsi(p1->k,ll);
            p1=p1->next;
        }
        else
        {
            ll=cons_lsi(p2->k,ll);
            p2=p2->next;
        }
        p->next=ll;
        p=ll;
    }
    while(p1)
    {
        ll=cons_lsi(p1->k,ll);
        p->next=ll;
        p=ll;
        p1=p1->next;
    }
    while(p2)
    {
        ll=cons_lsi(p2->k,ll);
        p->next=ll;
        p=ll;
        p2=p2->next;
    }
    p->next=NULL;
    return l;
};
LIST *stergere_element_lista(LIST *l,int poz)
{
    LIST *p=l,*q;
    int pozl=1;
    if(l->next)
    {
        if(poz==1)
            return l->next;
    }
    else
        return NULL;
    while(poz>pozl)
    {
        q=p;
        p=p->next;
        pozl++;
        if(!p&&poz>=pozl)
        {
            printf("Eroare - Lista are mai putine elemente");
            return l;
        }
    }
    q->next=p->next;
    free(p);
    return l;
};

LIST *inserare_element_lista(LIST *l,int poz, int x)
{
    LIST *p=l,*q;
    int pozl=1;
    if(poz==1)
        l=cons_lsi(x,l);
    else
    {
        while(poz>pozl)
        {
            q=p;
            p=p->next;
            pozl++;
            if(!p&&poz>pozl)
            {
                printf("Eroare - Elementul nu poate fi legat de lista");
                return l;
            }
        }
        p=cons_lsi(x,p);
        q->next=p;
    }
    return l;
};

LIST *stergere_elemente_pare_lista(LIST *l)
{
    LIST *p;
    int poz=1;
    for(p=l;p;p=p->next)
        if(p->k%2==0)
            l=stergere_element_lista(l,poz);
        else
            poz++;
    return l;
};

LIST *initializare_lista_crescatoare(LIST *l)
{
    LIST *p1;
    int ci,k,poz;
    char c,ck,cc[5];
    l=NULL;
    printf("Doriti sa incepeti initializarea listei crescatoare[n pentru terminare]?");
    scanf("%c",&c);
    if (c!='n')
       k=1;
    else
       k=-1;
    while (k!=-1)
    {
        printf(" Introduceti o cheie : ");
        scanf("%s",cc);
        if (strcmp(cc,"n"))
           k=1;
        else
           k=-1;
        ci=atoi(cc);
        poz=1;
        if(k!=-1)
            if(!l)
                l=inserare_element_lista(l,poz,ci);
            else
                {
                    for(p1=l;p1&&ci>p1->k;p1=p1->next)
                        poz++;
                    l=inserare_element_lista(l,poz,ci);
                }
    }
    return(l);
}

QUEUE *newq(QUEUE *q)
	{
    q=(QUEUE *)malloc(sizeof(QUEUE));
	q->front=q->rear=NULL;
	return(q);
	}

int emptyq(QUEUE *q)
	{if((q->front==q->rear)&&(q->front==NULL))
		return(1);
	 else return(0);
	 }

QUEUE *addq(QUEUE *q,int e)
	{LIST *aux;
	 aux=(LIST *)malloc(sizeof(LIST));
	 aux->k=e;
	 aux->next=NULL;
	 if ((q->front==NULL)&&(q->rear==NULL)) /* e primul element */
			q->front=q->rear=aux;
	 else
			{
			    q->rear->next=aux;
			    q->rear=aux;
			}
	 return(q);
	 }

QUEUE *initializare_coada_cu_header()
{LIST *aux;
 char c,c1; int k;
 QUEUE *q;
 q=newq(q); /* aux=NULL;q->front=q->rear=aux;*/
 printf(" DORITI SA INCEPETI INITIALIZAREA COZII ? [D/N] ");
 scanf("%c",&c);c1=getchar();
 while ((c=='d') || (c=='D'))
	 {
	     printf(" \n INTRODUCETI O CHEIE : "); scanf("%d",&k); c1=getchar();
		 q=addq(q,k);
		 printf("\n CONTINUATI ? "); scanf("%c",&c); c1=getchar();
	 }
	 return(q);
 }

void printq(QUEUE *q)
{ LIST *p;
	p=q->front;
	if(emptyq(q)) printf(" coada vida \n ");
	else
		{ do
				{
				    printf("%d ",p->k);
					p=p->next;
				}
          while (p!=NULL);
		}
	printf(" \n ");
}

QUEUE *remq(QUEUE *q)
	{LIST *out;
	 if(!emptyq(q))
		{out=q->front;
		 if (q->front->next)
					q->front=q->front->next;
		 else q->front=q->rear=NULL;
		 free(out);
         return(q);
		 }
	 else
		 {
		     printf("\n Coada era vida !");
			 return NULL;
		 }
	 }

int frontq(QUEUE *q)
	{if(!emptyq(q))
		return(q->front->k);
	 else
		{printf("\n Coada este vida."); return(-1);}
	 }

int prim(int x)
{
    int i;
    if(x<2)
        return 0;
    for(i=2;i<=x/2;i++)
        if(x%i==0)
            return 0;
    return 1;
}

QUEUE *numere_prime_lista_in_coada(LIST *l,QUEUE *q)
{
    LIST *p;
    for(p=l;p;p=p->next)
        if(prim(p->k))
        {
            if(emptyq(q))
                q=newq(q);
            q=addq(q,p->k);
        }
    return q;
}

struct lista *cons_ldi(int k,struct lista *l)
{ 	struct lista *aux;
	aux=(struct lista *)malloc(sizeof(struct lista));
	aux->k=k;
	aux->next=l;
	aux->prev=NULL;
	if(l) l->prev=aux;
	return(aux);
}

struct lista *init_ldi(struct lista *l)
{
	int ci,k;
	char c,ck,cc[5];
	l=NULL;

	printf("Doriti sa incepeti initializarea listei [n pentru terminare]?");
	scanf("%c",&c);
	if (c!='n')
	   k=1;
	else
	   k=-1;
	while (k!=-1)
	{
		printf(" o cheie : ");
		scanf("%s",cc);
		if (strcmp(cc,"n"))
		   k=1;
		else
		   k=-1;
		ci=atoi(cc);
		if(k!=-1)
		   l=cons_ldi(ci,l);
	}
	return(l);
}

void tipar_ldi(struct lista *l)
{ 	 struct lista *p;
	 printf("NULL");
	 for (p=l;p;p=p->next)printf("<=>%d",p->k);
	 printf("<=>NULL\n");
}

struct lista *stergere_element_ldi(struct lista *l,int poz)
{

};

struct lista *inserare_element_ldi(struct lista *l,int poz,int x)
{

};

STIVA *push(STIVA *vf, int x)
{
    STIVA *aux;
    aux=(STIVA*)malloc(sizeof(STIVA));
    aux->k=x;
    aux->next=vf;
    vf=aux;
    return vf;
}

STIVA *creare()
{
    STIVA *vf,*aux;
    char c;
    int x;

    vf=NULL;
    printf("Doriti sa adaugati nod in STIVA (d/n): ");
    c=getche();
    getchar();
    while(c=='d' || c=='D')
    {
        printf("Info: ");
        scanf("%i",&x);
        getchar();
        vf=push(vf,x);
        printf("\nDoriti sa adaugati nod in STIVA (d/n): ");
        c=getche();
        getchar();
    }
    return vf;
}
void afisare(STIVA *vf)
{
    STIVA *p;

    for(p=vf;p;p=p->next)
        printf("%i->",p->k);
    printf("NULL");
}

STIVA *pop(STIVA *vf)
{
    STIVA *aux;
    aux=vf;
    vf=vf->next;
    free(aux);
    return vf;
}

STIVA *mutare_prime_lista_in_stiva(LIST *l,STIVA *vf)
{
    LIST *p=l;
    int poz=1;
    while(p)
    {
        if(prim(p->k))
        {
            vf=push(vf,p->k);
            p=p->next;
            l=stergere_element_lista(l,poz);
        }
        else
        {
            p=p->next;
            poz++;
        }
    }
    return vf;
}