Creare in linguaggio C (non c++) un generatore di riferimenti incrociati?

Si voglia progettare un generatore di riferimenti incrociati.

Supponiamo di avere un file di testo (una poesia o un discorso famoso, ad esempio).

Vogliamo leggere il file e visualizzare una lista di tutte le parole contenute nel file, usando il seguente formato:

Parola

Numero di ricorrenze

Righe che contengono la parola

Si supponga che il vostro generatore di riferimenti incrociati ignori la differenza tra caratteri

maiuscoli e minuscoli (ad esempio Fai e fai sono due parole uguali). Applicando il generatore di riferimenti incrociati alle prime due righe di una nota poesia di Leopardi, qui riportate,

1

Che fai tu, luna, in ciel? Dimmi, che fai,

2

silenziosa luna

si otterrebbe il seguente prospetto

http://www.allfreeportal.com/imghost2/thumbs/93476...

Aggiornamento:

non sto chiedendo di farmi l'esercizio ma semplicemente un aiuto sulle strutture! so benissimo come so confrontano le parole il problema è che le parole vanno messe in una struttura tipo lista dinamicamente concatenata e questa va rivista per ogn parola del testo e NON confrontando solo 2 parole consecutive!

2 risposte

Classificazione
  • ?
    Lv 7
    1 decennio fa
    Risposta preferita

    Se davvero "Non chiedi di farti l'esercizio, ma un aiuto sulle strutture!" non ti scrivo codice e mi limito a suggerirti strutture e algoritmi.

    La cosa più complicata è spezzare in parole la singola linea letta dal textfile: visto che il testo d'interesse è solo in lingua comune ("poesia o discorso") ti suggerisco di essere drastico e spezzare su ogni carattere che non sia lettera; mentre raccogli le lettere, trasformi in minuscole (aggiungendo 32) le eventuali maiuscole.

    Le strutture che ti suggerisco di usare tengono conto che poi dovrai codificare in C.

    Nota: NUL è il nome ASCII del carattere #0; NULL è il puntatore vuoto.

    1) Un grande spazio 'WORDS' (da allocare staticamente all'inizio) gestito come array di caratteri per tenerci dentro TUTTE le parole che si estraggono dal textfile. Ogni parola si reppresenta col puntatore al primo carattere ed è regolarmente terminata da un carattere nullo (p.es., 'poi' occupa quattro caratteri: ['p', 'o', 'i', NUL]).

    2) Un tipo record 'tipo_2' (in C, 'struct') con due campi [puntatore_al_prossimo, numero_di_linea], da allocare dinamicamente per ciascuna occorrenza di una parola.

    3) Un tipo record 'tipo_3' con quattro campi, tutti puntatori, [al_figlio_sinistro, al_figlio_destro, alla_parola, alla_lista_delle_occorrenze_tipo_2], da allocare dinamicamente per ciascuna occorrenza di una parola nuova.

    4) Un BST (albero binario di ricerca) reppresentato col puntatore al primo record di tipo_3 che viene allocato.

    L'algoritmo che ti suggerisco di usare è qualcosa del genere.

    A) Per ogni linea del textfile in ingresso:

    A1) Incrementare 'lineNo', il numero di linea corrente;

    A2) Per ogni parola 'W' isolata (e minuscolizzata) nella linea:

    A2a) elaborare(W).

    B) Visitare il BST in ordine simmetrico (sottoBST sinistro, radice, sottoBST destro).

    B1) La visita di un nodo consiste nell'emettere, opportunamente separati:

    B1a) la parola W puntata;

    B1b) la lunghezza della lista dei numeri di linea (occorrenze di W);

    B1c) la lista dei numeri di linea;

    B1d) un accapo.

    L'algoritmo di "elaborare(W)" è qualcosa del genere.

    C) Se W è in BST: accodare lineNo alla lista delle occorrenze.

    D) Se W NON è in BST:

    D1) Porre pW = nxtW (il puntatore al primo posto libero in WORDS); copiare W (e un NUL) in WORDS. aggiornando nxtW;

    D2) Allocare un record L di tipo_2, puntato da pL, con [NULL, lineNo] (v. Nota);

    D3) Allocare un record N di tipo_3, puntato da pN, con [NULL, NULL, pW, pL];

    D4) Inserire il nodo N nel BST, assegnando pN come opportuno figlio della foglia F su cui la ricerca è fallita (sinistro se W < F, destro se >).

    Nota: In effetti, date le operazioni da fare, non conviene tenere le liste di occorrenze con NULL in fondo. Conviene che la testa di lista punti l'ultimo nodo e questo punti il primo. Così l'accodamento ha sùbito disponibile il fondo, e la lettura può iniziare dal primo nodo.

    Con tale strategia il record L dev'essere [pL, lineNo].

    PS: ricordati di votare una risposta (se lo fai, Y!A ti dà 3 punti!), possibilmente questa: v. http://www.yanswersblogit.com/b4/2010/01/08/evita-...

  • Gina D
    Lv 5
    1 decennio fa

    ma perche' non cercate di fare i vostri esercizi da soli? come imparerete?

    In pratica devi scandire parola per parole il testo ogni parola devi vedere se e' uguale con la precedente, aumentare il suo contatore, e tenere in memoria le righe dove hai trovato parole uguali

Altre domande? Fai una domanda e ottieni le risposte che cerchi.