Lezione 16: Liste, Code reengineering.

  • Liste
  • Modifica del codice per WordStat senza cambiare la main.

WordStat

Implementazione del Dizionario per il programma WordCount (calcolo della frequenza delle parole di un file di testo), questa implementazione è basata su liste di strutture Parola.

// Dizionario.c: Implementazione con liste.

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

#include "dizionario.h"

Parola *Dizionario;
int listlen = 0;

int Dizionario_size(void) { return listlen; }

Parola *
Dizionario_insert(Parola *diz, wchar_t *word, int counter)
{
    Parola *new = (Parola *) malloc(sizeof(Parola));

    new->parola = (wchar_t *) malloc(sizeof(wchar_t) * wcslen(word) + 1);
    wcscpy(new->parola,word);
    new->contatore = counter;
    new->next = diz;
    listlen++;

    return new;
}

void Dizionario_destroy(Parola *diz)
{
    while (diz != NULL)
    {
        free(diz->parola);
        Parola *p = diz->next;
        free(diz);
        diz = p;
    }
}

Parola *Dizionario_search(Parola *diz, wchar_t *word)
{
    for (; diz; diz = diz->next)
        if (wcscmp(diz->parola,word) == 0)
            return diz;
    return NULL;
}

void Dizionario_IncreaseCounter(Parola *pos)
{
    pos->contatore++;
}

void Dizionario_print(Parola *diz)
{
    for (; diz; diz = diz->next)
        wprintf(L"%d %lsn",diz->contatore, diz->parola);
}
#ifndef DIZIONARIO
#define DIZIONARIO 1

#include <wchar.h>

typedef struct _a {
   wchar_t *parola;
   int contatore;
   struct _a *next;
} Parola;

Parola *Dizionario_search(Parola diz[], wchar_t *word);
Parola *Dizionario_insert(Parola diz[], wchar_t *word, int counter);
void Dizionario_destroy(Parola diz[]);
void Dizionario_print(Parola diz[]);
void Dizionario_IncreaseCounter(Parola *pos);
int Dizionario_size(void);

#endif

Programma principale, usa un ADT Dizionario (un tipo di dato astratto), tutte le operazioni avvengono attraverso chiamate di funzioni, non si fanno assunzioni sulla natura dell'implementazione di Dizionario.
Il codice della funzione getword è stato presentato nella lezione precedente.

// WordCount: programma principale

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

#include "dizionario.h"
#include "word.h"

#define MAXWORDS 5000
extern Parola* Dizionario;

#define MAXWORD  200

int main(int argc, char *argv[])
{
    setlocale(LC_CTYPE, "it_IT.UTF-8");

    wchar_t buffer[MAXWORD+1];
    int N = 0;
    while (getword(buffer,MAXWORD)>0)
    {
        N++;
        Parola* pos;
        if (pos = Dizionario_search(Dizionario, buffer))
        {
            Dizionario_IncreaseCounter(pos);
        } else
        {
            Dizionario = Dizionario_insert(Dizionario,buffer,1);
        }
    }
    Dizionario_print(Dizionario);

    wprintf(L"n");
    wprintf(L"N = %d, n = %dn", N, Dizionario_size());

    Dizionario_destroy(Dizionario);
    return 0;
}

Dizionario implementato con un vettore statico.
L'interfaccia (le funzioni, i loro tipi e la loro semantica) resta
invariata, infatti si può compilare il programma principale senza dover cambiare una riga, rispettivamente con questa implementazione o con quella con le liste.

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

#include "dizionario.h"

#define MAXWORDS 5000

static Parola d[MAXWORDS];
static int top = 0;

// Questo serve per poter aggiornare la variabile dizionario nella versione con vettore
// Non posso semplicemente esportare il nome del vettore, perche sarebbe un puntatore costante
// e la funzione dizionario_insert nn funzionerebbe.

Parola *Dizionario = d;

int Dizionario_size(void)
{
    return top;
}

void Dizionario_IncreaseCounter(Parola *pos)
{
    pos->contatore++;
}

Parola *Dizionario_search(Parola diz[], wchar_t *word)
{
    for (int i=0; i<top; i++)
        if (wcscmp(diz[i].parola,word) == 0)
            return &diz[i];
    return NULL;
}

Parola *Dizionario_insert(Parola diz[], wchar_t *word, int counter)
{
    if (top == MAXWORDS) {
        printf("Error: dizionario troppo piccolon");
        exit(1);
    }
    diz[top].parola = (wchar_t *) malloc(sizeof(wchar_t) * wcslen(word) + 1);
    wcscpy(diz[top].parola,word);
    diz[top].contatore = counter;
    top++;
    return diz;
}

void Dizionario_print(Parola diz[])
{
    for (int i=0; i<top; i++)
        wprintf(L"%d %lsn",Dizionario[i].contatore, Dizionario[i].parola);
}

void Dizionario_destroy(Parola diz[])
{
    for (int i=0; i<top; i++)
        free(diz[i].parola);
}

Esercizi

  • Riscrivere dizionario, usando un vettore "dinamico", cioè, la funzione insert non deve restituire errore se il vettore viene riempito completamente, ma provvedere a riallocare un vettore di dimensioni maggiori.
  • Riscrivere la funzione insert nella versione con le liste, in mdo da mantenere la lista ordinata per il campo contatore (quindi, in base alla frequenza delle parole).
  • Alla fine del programma, inserite un menu interattivo con l'utente, il menu deve consentire di svolgere le seguenti operazioni:
    1. Stampa le k parole con frequenza maggiore (k = 20). Invece di stampare il valore assoluto del contatore, stampare la frequenza della parola come percentuale sul totale. Il totale deve essere sempre riportato in fondo all'elenco, i.e. (Nota, l'elenco per comodità andrebbe quindi ordinato).
    2. Cambia il valore di k.
    3. Elimina una parola dall'elenco. La parola è inserita dall'utente e viene cancellata.

2 thoughts on “Lezione 16: Liste, Code reengineering.

  1. Pingback: Lezione 18 |

  2. Pingback: Lezione 21 |

Lascia un commento