Program - algoritm de explorare in largime
functie, declarare matrice, citire arce, construire matrice, apelare functie de exploorare in largime

void largime(int a[][100],int n,int s)
{
    int viz[n],coada[n],i,k=0,j,ct;
    coada[0]=s;
    for (i=1;i<=n;i++)
        viz[i]=0;
    viz[k]=1;
    k++;

    while (k<n)
    {
        ct=0;
        for (i=ct;i<k;i++)
        {
            for (j=1;j<=n;j++)
                if (a[coada[i]][j] && viz[j]==0)
                {
                    viz[j]=1;
                    coada[k]=j;
                    k++;
                }
            ct++;
        }
    }
    for (i=0;i<n;i++)
        printf("%d ",coada[i]);
    printf("\n");
}

Conspect ALGORITMI PENTRU PRELUCRAREA GRAFURILOR

si primul algoritm (Algoritmul lui Dijkstra)

void dijkstra (int n,int a[][100])
{
    int tata[n],cost[n][n],dist[n],s[n],i,j,pas,k,q,minim;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            if (i==j)
                cost[i][j]=0;
            else
                if (a[i][j])
                    cost[i][j]=a[i][j];
                else
                    cost[i][j]=100000;
    for (i=1;i<=n;i++)
    {
        s[i]=0;
        dist[i]=cost[1][i];
        if (dist[i]<100000)
            tata[i]=1;
        else
            tata[i]=0;
    }
    s[1]=1;
    tata[1]=0;
    for (i=1;i<n;i++)
    {
        minim=100000;
        for (q=1;q<=n;q++)
            if (dist[q]<minim && dist[q])
            {
                minim=dist[q];
                k=q;
            }

        if (k==100000)
            return;
        s[k]=1;
        for (j=1;j<=n;j++)
            if (s[j]==0 && dist[k]+cost[k][j]<dist[j])
            {
                dist[j]=dist[k]+cost[k][j];
                tata[j]=k;
            }
    }
    for (i=2;i<=n;i++)
        printf("%d - %d\n",dist[i],tata[i]);

}

Main

int main()
{
    int a[100][100],n,m,i,x,y,c,j;
    FILE *f;
    f=fopen("in.txt","r");

    fscanf(f,"%d %d\n",&n,&m);
    for (i=0;i<m;i++)
    {
        fscanf(f,"%d %d %d\n",&x,&y,&c);
        a[x][y]=c;
    }

    largime(a,n,1);

    dijkstra(n,a);
    return 0;
}

Lab 8 - prob. 3.2

Să se implementeze algoritmii prezentaţi aferenţi unei tabele de dispersie. Înregistrarea va conţine datele aferente unui student. Cheia va fi numele şi prenumele studentului. Scrieţi în plus
faţă de cele prezentate o funcţie de ştergere a unei înregistrări de cheie dată.
// nu chiar toti studentii sunt gasiti

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define M 27
typedef struct Nod{
    char nume[50];
    char facult[50];
    int an;
    struct nod *st,*dr;
    } nod;
int ff(char cuv[])
{
    return cuv[0]-'A';
}
// antete functii tabela
void adaug(nod *ht[],char nume[],char facult[],int an);
void afis(nod *ht[]);
nod* caut(nod *ht[],char nume[]);
void stergere(nod *ht[],char nume[]);
// antete functii arbore
nod* adaug_arbore(nod *r, char nume[],char facult[],int an);
void afisIN(nod *r);
nod* caut_arbore(nod *r,char nume[]);
nod* stergere_arbore(nod *r,char nume[]); // functia lunga din laborator
// functii tabela
void adaug(nod *ht[],char nume[], char facult[],int an)
{
    int i=ff(nume);
    ht[i]=adaug_arbore(ht[i],nume,facult,an);
}
void afis(nod *ht[])
{
    int i=0;
    for(i=0; i<M; i++)
    {
        nod *rad=ht[i];
        afisIN(rad);
    }
}
//functii arbore
nod* caut_arbore(nod *r,char nume[])
{
    nod *p=NULL;
    if(r!=0)
    {
        if(strcmp(nume,r->nume)==0)
            p=r;
        else if(strcmp(nume,r->nume)<0)
            p=caut_arbore(r->st,nume);
        else caut_arbore(r->dr,nume);
    }
    return p;
}
nod* adaug_arbore(nod *p, char nume[50],char facult[50],int an)
{
    if(p==NULL)
    {
        p=(nod *)malloc(sizeof(nod));
        p->st=p->dr=NULL;
        strcpy(p->nume,nume);
        strcpy(p->facult,facult);
        p->an=an;
    }
    else if(strcmp(p->nume,nume)>0)
            p->st=adaug_arbore(p->st,nume,facult,an);
    else if(strcmp(p->nume,nume)<0)
            p->dr=adaug_arbore(p->dr,nume,facult,an);
    else if(strcmp(p->nume,nume)==0)
            return p;
}
void afisIN(nod *r)
{
    if(r)
    {
        afisIN(r->st);
        printf("%s %s %d \n",r->nume,r->facult,r->an);
        afisIN(r->dr);
    }
}
int main()
{
    FILE *f;
    nod *rad=0;
    nod* ht[M];
    int i=0,an;
    char nume[50],facult[50];
    for(i=0; i<M; i++)
        ht[i]=0;
    f=fopen("date.txt","r");
    if(f==NULL)
    {
        printf("error");
        return -1;
    }
    while(!feof(f))
    {
        fscanf(f,"%s %s %d",nume,facult,&an);
        rad=adaug_arbore(rad,nume,facult,an);
        //adaug(ht[ff(nume)],nume,facult,an);
    }
    afisIN(rad);
    //printf("\n\n");
    //afis(ht[i]);
    char nume_cautare[40];
    printf("\nCautare student (nume): ");
    scanf("%s",nume_cautare);
    nod *p=caut_arbore(rad,nume_cautare);
    if(p!=NULL)
    {
        printf("%s %s %d\n",p->nume,p->facult,p->an);
    }
    else printf("Nu exista studentul cu numele introdus\n\n");
    printf("Apasati o tasta pentru terminare");
    getch();
    return 0;
}

Pro's

#include <stdio.h>
#include <stdlib.h>

typedef struct nodtype
{
    char nume[20];
    struct nod *dr,*st;
}nod;

void inserare(char nume[20],nod **rad)
{
    nod *p,*q;
    p=(nod *)malloc(sizeof(nod));
    p->st=NULL;
    p->dr=NULL;
    strcpy(p->nume,nume);
    q=*rad;

    if (*rad)
    {
        for (;;)
        {
            if (strcmp(nume,q->nume)<0)
            {
                if (q->st==0)
                {
                    q->st=p;
                    return;
                }
                else
                    q=q->st;
            }
            else
                if (strcmp(nume,q->nume)>0)
                {
                    if (q->dr==0)
                    {
                        q->dr=p;
                        return;
                    }
                    else
                        q=q->dr;
                }
                else
                {
                    return;
                }
        }
    }
    else
        (*rad)=p;
}

void afisare(nod *rad)
{
    if (rad)
    {
        afisare(rad->st);
        printf("%s\n",rad->nume);
        afisare(rad->dr);
    }
}

nod *cautare(nod *rad,char nume[])
{
    nod *p=NULL;
    if (rad)
    {
        if (!strcmp(rad->nume,nume))
            p=rad;
        else
            if (strcmp(rad->nume,nume)<0)
                p=cautare(rad->st,nume);
            else
                 p=cautare(rad->dr,nume);
    }
    return p;
}

void stergere(nod **rad,char nume[20])
{
    nod *p,*q,*tp,*tq;
    int directie=0;
    p=(*rad);
    tp=0;
    while (p && strcmp(p->nume,nume))
        if (strcmp(p->nume,nume)>0)
        {
            tp=p;
            p=p->st;
            directie=1;
        }
        else
            if (strcmp(p->nume,nume)<0)
            {
                tp=p;
                p=p->dr;
                directie=2;
            }
    if (p==0)
        return 0;
    if (p->st==0)
        q=p->dr;
    else
    {
        if (p->dr==0)
        {
            q=p->st;
        }
        else
        {
            tq=p;
            q=p->dr;
            while (q)
            {
                tq=q;
                q=q->st;
            }
            q->st=p->st;
            if (tq!=p)
            {
                tq->st=q->dr;
                q->dr=p->dr;
            }
        }
    }
    if (p==(*rad))
        (*rad)=q;
    free(p);
    if (tp)
    {
        if (directie==1)
            tp->st=q;
        else
            tp->dr=q;
    }
}

int dispersie(char nume[20])
{
    return (nume[0]-'A');
}

int main()
{
    FILE *f;
    int n,k,i;
    char nume[20];
    f=fopen("in.txt","r");
    fscanf(f,"%d\n",&n);
    nod *ht[27];

    for (i=0;i<27;i++)
        ht[i]=NULL;

    for (i=0;i<n;i++)
    {
        fgets(nume,20,f);
        strcpy(nume+strlen(nume)-2,nume+strlen(nume));
        k=dispersie(nume);
        inserare(nume,&ht[k]);
    }

    for (i=0;i<27;i++)
    {
        afisare(ht[i]);
    }

    /*char caut[20];
    scanf("%s",caut);
    nod *p;
    p=cautare(ht[caut[0]-'A'],caut);
    printf("%s\n",p->nume);
    */
    char sterg[20];
    scanf("%s",sterg);
    stergere(&ht[sterg[0]-'A'],sterg);

    afisare(ht[sterg[0]-'A']);
    return 0;
}

Numărător - Active HDL

library    IEEE;
use IEEE.STD_LOGIC_1164.all;
use IEEE.STD_LOGIC_UNSIGNED.all; 

entity ent_numarator is
    Port (CLK: in STD_LOGIC;
    R:in STD_LOGIC;
    L:in std_logic;   
    INPUT: std_logic_vector (3 downto 0);
    Q:out STD_LOGIC_VECTOR (3 downto 0)); 
end ent_numarator;

architecture arh_numarator of ent_numarator is
begin
process(CLK)      
variable intQ:std_logic_vector(3 downto 0);
    begin
        if (clk'event and R='1') then
            intQ:="0000";
        elsif (clk'event and clk='1') then   
            if(intQ="1111") then
                intQ:="0000";
            else
                intQ:=intQ+'1';
            end if;
        elsif (clk'event and L='1') then
            intQ:=INPUT;
        end if;     
    Q<=intQ;
end process;
end arh_numarator;             

Numărător - Xilinx

library    IEEE;
use IEEE.STD_LOGIC_1164.all;
use IEEE.STD_LOGIC_UNSIGNED.all; 

entity ent_numarator is
    Port (CLK: in STD_LOGIC;
    R:in STD_LOGIC;
    L:in std_logic;   
    INPUT: std_logic_vector (3 downto 0);
    Q:out STD_LOGIC_VECTOR (3 downto 0)); 
end ent_numarator;

architecture arh_numarator of ent_numarator is
begin
process(CLK)      
variable intQ:std_logic_vector(3 downto 0);
    begin
        if (clk='1' and clk'event) then
            if(r='1') then
                intQ:="0000";
            elsif (l='1') then
            intQ:=INPUT;
            else intQ:=intQ+'1';
            end if;
        end if;
       
    Q<=intQ;
end process;
end arh_numarator;

NET "D(3)" LOC = T5;
NET "D(2)" LOC = V8;
NET "D(1)" LOC = U8;
NET "D(0)" LOC = N8;
NET "Reset" LOC = T9;
NET "Load" LOC = T10;
NET "Q(3)" LOC = T11;
NET "Q(2)" LOC = R11;
NET "Q(1)" LOC = N11;
NET "Q(0)" LOC = M11;
NET "CLK" LOC = B8;

Divizor de frecvenţă - nefuncţional (un led se aprinde o dată pe secundă)

library IEEE;
use ieee.std_logic_1164.all;
use ieee.std_logic_arith.all;
use ieee.std_logic_unsigned.all;   

entity numarator is
    port (CLK:in STD_LOGIC;
    CLK1:out STD_LOGIC);
end;

architecture arh1 of numarator is
begin
process(CLK)
    variable K:STD_LOGIC:='0';
    variable X:INTEGER RANGE 0 to 100_000_000;
    begin
        --if (CLK'EVENT and CLK='1') then
        --    X:=X+1;
        --end if;
       
        --if (X=99_999_999) then
        --    K:='1';
        --    X:=0;
        --else K:='0';
        --      X:=X+1;
        --end if;
       
       
        CLK1<=CLK;
    end process;
end arh1;

Reclamă luminoasă - inexistent

Test dupa vacanta: liste, arbori, tabele de dispersie

Se citesc dintr-un fisier cuvinte. Fiecare cuvant citit se va insera intr-o tabela de dispersie. Sa se afiseze cuvintele din fisier in ordine lexico-grafica crescatoare si frecventa lor de aparitie.

Terminare problema + adaugare functie de stergere a cuvintelor care apar o singura data

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define M 27
typedef struct nod{  
    char cuv[20];  // cheia  
    int fr;  //  frecventa cuvantului  
    struct nod *st,*dr;
    } nod;
  
int f(char cuv[20])
{
    return cuv[0]-'a';
}

nod* construire(nod *p, char cuv[20])
{
    if(p==NULL)
    {
        p=(nod *)malloc(sizeof(nod));
        p->st=p->dr=NULL;
        p->fr=1;
        strcpy(p->cuv,cuv);
    }
    else if(strcmp(p->cuv,cuv)>0)      
            p->st=construire(p->st,cuv);
    else if(strcmp(p->cuv,cuv)<0)      
            p->dr=construire(p->dr,cuv);
    else if(strcmp(p->cuv,cuv)==0)      
            p->fr++;
    return p;
}

void adaug_tabela(nod *ht[],char cuv[20])
{
    int i=f(cuv);
    ht[i]=construire(ht[i],cuv);
}

void afisIN(nod *r, int nivel)
{
    if(r)
    {
        afisIN(r->dr,nivel+1);
        int i=0;
        for(i=0; i<nivel; i++)         
            printf(" ");
        printf("%s ",r->cuv);
        printf("%d\n",r->fr);
        afisIN(r->st,nivel+1);
    }
}

void afis(nod *ht[])
{
    int i=0;
    for(i=0; i<M; i++)
    {
        nod *rad=ht[i];
        afisIN(rad,0);
    }
}

int main()
{
    FILE *f;
    int i;
    char a[20];
    f=fopen("date.txt","r");
    nod* ht[M];
    for(i=0; i<M; i++)        ht[i]=0;
    while(!feof(f))
    {
        fscanf(f,"%s",a);
        adaug_tabela(ht,a);
    }
    afis(ht);
    printf("Apasati o tasta pentru terminare");
    getch();
    return 0;
}

Pro's version

#include <stdio.h>
#include <stdlib.h>

typedef struct nodtype
{
    char key[20];
    int fv;
    struct nodtype *st,*dr;
}nod;

int dispersie(char s[])
{
    return (s[0]-'a');
}

void inserare(char x[],nod **rad)
{
    nod *p,*q;
    p=(nod *)malloc(sizeof(nod));
    p->st=0;
    p->dr=0;
    p->fv=1;
    strcpy(p->key,x);
    q=*rad;

    if (*rad)
    {
        for (;;)
        {
            if (strcmp(x,q->key)<0)
            {
                if (q->st==0)
                {
                    q->st=p;
                    return;
                }
                else
                    q=q->st;
            }
            else
                if (strcmp(x,q->key)>0)
                {
                    if (q->dr==0)
                    {
                        q->dr=p;
                        return;
                    }
                    else
                        q=q->dr;
                }
                else
                {
                    q->fv++;
                    return;
                }
        }
    }
    else
        (*rad)=p;
}

void afisare(nod *rad)
{
    if (rad)
    {
        afisare(rad->st);
        printf("%s - %d\n",rad->key,rad->fv);
        afisare(rad->dr);
    }
}

int main()
{
    int n,N=27;
    FILE *f;
    f=fopen("in.txt","r");
    char s[20];
    int i,k;

    nod *ht[N];

    for (i=0;i<N;i++)
        ht[i]=NULL;

    fscanf(f,"%d\n",&n);

    for (i=0;i<n;i++)
    {
        fgets(s,20,f);
        k=dispersie(s);
        inserare(s,&ht[k]);
    }

    for (i=0;i<N;i++)
    {
        afisare(ht[i]);
    }

    return 0;
}

Conspect: REPREZENTAREA ŞI TRAVERSAREA GRAFURILOR

Din fisier se citesc cuvinte (siruri de caractere, cu fscanf). Să se scrie un program care creează un arbore de căutare, care conţine în noduri cuvintele şi frecvenţa lor de apariţie. Să se afişeze apoi cuvintele în ordine lexicografică crescătoare şi frecvenţa lor de apariţie (parcurgere in inordine, S < R < D).

#include <stdio.h>  //  functia de cautare pt cresterea frecventei
#include <stdlib.h>
typedef struct tip_nod
{
    int f;
    char s[20];
    struct tip_nod *st, *dr;
} nod;
nod *rad;
void inserare_nerecursiva(char s[])
{
    nod *p,*q;
    int n;
    n=sizeof (nod);
    p=(nod*)malloc(n);
    strcpy(p->s,s);
    p->st=0;
    p->dr=0;
    if (rad==0)
    {
        rad=p;
        return;
    }
    q=rad;
    for ( ; ; )
    {
        if (strcmp(s,q->s)<0)
        {
            if (q->st==0)
            {
                q->st=p;
                return;
            }
            else q=q->st;
        }
        else if (strcmp(s,q->s)>0)
        {
            if (q->dr==0)
            {
                q->dr=p;
                return;
            }
            else q=q->dr;
        }
        else
        {
            p->f++;
            free (p);
            return;
        }
    }
}

void inordine(nod *p, int nivel)
{
    int i;
    if (p!=0)
    {
        inordine(p->st,nivel+1);
        //for(i=0; i<=nivel; i++) printf("  ");
        printf("%s %d\n",p->s,p->f);
        inordine(p->dr,nivel+1);
    }
}
int main()
{
    FILE *f;
    f=fopen("date.txt","r");
    char s[20];
    while(!feof(f))
    {
        fscanf(f,"%s",s);
        inserare_nerecursiva(s);
    }
    inordine(rad,0);
    printf("\nApasati o tasta pentru terminare");
    getch();
    return 0;
}

Functia sterge_nod

TIP_NOD *stergere_nod(TIP_NOD *rad,int key)
{
    TIP_NOD *p,*tata_p;/* p este nodul de sters, iar tata_p este tatal lui */
    TIP_NOD *nod_inlocuire,*tata_nod_inlocuire;/*nodul care il va inlocui pe p si tatal sau */ 
    int directie; /*stg=1;dr=2*/ 
    if(rad==0) return 0; /*arborele este vid */ 
    p=rad;
    tata_p=0;  /* cautare nod cu cheia key */ 
    while((p!=0)&&(p->cheie!=key))
    {
        if (key<p->cheie)
        {
            /*cautare in stanga */                                                
            tata_p=p;
            p=p->stg;
            directie=1;
        }
        else
        {
            /*cautare in dreapta */                           
            tata_p=p;
            p=p->dr;
            directie=2;
        }
    }
    if(p==0)
    {
        printf("\n NU EXISTA NOD CU CHEIA=%d\n",key);
        return rad;
    }      /* s-a gasit nodul p de cheie key */     
    if(p->stg==0)
        nod_inlocuire=p->dr; /* nodul de sters p nu are fiu sting */
    else if(p->dr==0) nod_inlocuire=p->stg;   /*nodul de sters p  nu are fiu drept*/     
    else
    {
        /* nodul de sters p are fiu stang si fiu drept */              
        tata_nod_inlocuire=p;
        nod_inlocuire=p->dr;        /* se cauta in subarborele drept*/              
        while(nod_inlocuire->stg!=0)
        {
            tata_nod_inlocuire=nod_inlocuire;
            nod_inlocuire=nod_inlocuire->stg;
        }
        if(tata_nod_inlocuire!=p)
        {
            tata_nod_inlocuire->stg=nod_inlocuire->dr;
            nod_inlocuire->dr=p->dr;
        }
        nod_inlocuire->stg=p->stg;
    }
    free(p);
    printf("\nNodul de cheie=%d a fost sters!\n",key);
    if(tata_p==0) 
        return nod_inlocuire; /*s-a sters chiar radacina initiala */      
    else
    {
        if (directie==1)
            tata_p->stg=nod_inlocuire;
        else tata_p->dr=nod_inlocuire;
        return rad;
    }
}

Tema: tabele de dispersie, probl 3.1 si 3.4

3.1 De la tastatură se citesc cuvinte ( şiruri de caractere ). Să se scrie un program care creează un arbore de căutare, care conţine în noduri cuvintele şi frecvenţa lor de apariţie. Să se afişeze apoi cuvintele în ordine lexicografică crescătoare şi frecvenţa lor de apariţie.

3.4 Se consideră două liste liniare simplu înlănţuite cu câmpurile de informaţie utilă conţinând numere întregi. Să se construiască o listă care conţine reuniunea celor două liste şi în care elementele sunt ordonate crescător. Se va folosi o structură intermediară de tip arbore de căutare. Elementele comune vor apare a o singură dată.

#include <stdio.h>
#include <stdlib.h>
typedef struct nodlista
{
    int x;
    struct nod *urm;
} nod;

typedef struct nodarbore
{
    int x;
    struct nod *st,*dr;
} nodarbore;

void inserare_lista(int x,nod **prim, nod **ultim)
{
    nod *p;
    p=(nod *)malloc(sizeof(nod));
    p->x=x;
    p->urm=NULL;

    if (*prim)
    {
        (*ultim)->urm=p;
        (*ultim)=p;
    }
    else
    {
        (*prim)=p;
        (*ultim)=p;
    }
}

void afisare(nod *prim)
{
    for (prim=prim; prim!=NULL; prim=prim->urm)
        printf("%d ",prim->x);
    printf("\n");
}

void creare_arbore(nodarbore **rad,int x)
{
    nodarbore *p,*q;
    p=(nodarbore *)malloc(sizeof(nodarbore));
    p->x=x;
    p->st=NULL;
    p->dr=NULL;
    q=(*rad);

    for (;;)
    {
        if (*rad)
        {
            if (x<q->x)
            {
                if (q->st==NULL)
                {
                    q->st=p;
                    return;
                }
                else
                    q=q->st;
            }
            else if (x>q->x)
            {
                if (q->dr==NULL)
                {
                    q->dr=p;
                    return;
                }
                else
                    q=q->dr;
            }
            else
                return;
        }
        else
        {
            (*rad)=p;
            return;
        }
    }
}

void arbore(nod *prim1,nod *prim2,nodarbore **rad)
{
    nod *p;
    for (p=prim1; p!=0; p=p->urm)
        creare_arbore(rad,p->x);

    for (p=prim2; p!=0; p=p->urm)
        creare_arbore(rad,p->x);
}

nod* lista_noua(nodarbore *a,nod **prim, nod **ultim)
{
    nod *p=NULL,*q;
    if (a)
    {
        p=(nod *)malloc(sizeof(nod));
        p->x=a->x;
        p->urm=NULL;
        q=lista_noua(a->st,prim,ultim);

        inserare_lista(a->x,prim,ultim);

        q=lista_noua(a->dr,prim,ultim);
    }
    return p;
}

void preordine(nodarbore *p, int nivel)
{
    int i;
    if (p!=0)
    {
        for(i=0; i<=nivel; i++)
            printf("  ");
        printf("%2d\n",p->x);
        preordine(p->st,nivel+1);
        preordine(p->dr,nivel+1);
    }
}

int main()
{
    int n,m,i,a;
    nod *prim1=0,*ultim1=0,*prim2=0,*ultim2=0,*prim=0,*ultim=0;
    FILE *f;

    f=fopen("date.txt","r");
    fscanf(f,"%d %d",&n,&m);
    for (i=1; i<=n; i++)
    {
        fscanf(f,"%d",&a);
        inserare_lista(a,&prim1,&ultim2);
    }

    for (i=1; i<=m; i++)
    {
        fscanf(f,"%d",&a);
        inserare_lista(a,&prim2,&ultim2);
    }

    afisare(prim1);
    afisare(prim2);
    printf("\nNoua lista\n");

    nodarbore *rad=NULL;
    arbore(prim1,prim2,&rad);

    //preordine(rad,0);
    lista_noua(rad,&prim,&ultim);
    afisare(prim);
    return 0;

}

Fisier date.txt

4 5
1 5 3 7
2 6 3 9 7