Laborator 7 - Tabele de dispersie (8 aprilie)

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