Pages: [1]   Go Down
Print
Author Topic: Esercitazione del 14/11/2013 - Inserimento ORDINATO in lista semplicemente collegata  (Read 3662 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
corrado santoro
Moderator
Matricola
*****
Offline Offline

Posts: 28


« on: 14-11-2013, 17:01:18 »

Soluzione dell'esercizio svolto oggi in aula:
- Lettura di un file di testo contenente coppie (chiave, valore);
- Inserimento, ordinato per chiave, in una lista semplicemente collegata.

Notare le due versioni dell'inserimento, quella iterativa e quella ricorsiva

Code:
/*
 * lettura_lista_ordinata.c
 */
#include <stdio.h>
#include <stdlib.h>


typedef struct {
    char key[20];
    int value;
} t_element;


typedef struct t_node {
    t_element data;
    struct t_node * next;
} t_node;


typedef struct {
    t_node * head;
} t_list;


void init_list(t_list * l)
{
    l->head = NULL;
}


// ---------------- VERSIONE ITERATIVA --------------------
void insert_in_order(t_list * l, t_element e)
{
    t_node * newnode, * current, * prev;

    newnode = malloc(sizeof(t_node));
    newnode->data = e;

    if (l->head == NULL) {
        newnode->next = NULL;
        l->head = newnode;
        return;
    }

    prev = NULL;
    current = l->head;

    while (current != NULL) {
        if (strcmp(current->data.key, e.key) > 0) {
            // place found; insert element between prev and current
            if (prev == NULL) {
                // no prev here! current is the first element of the list
                newnode->next = l->head;
                l->head = newnode;
            }
            else {
                newnode->next = current;
                prev->next = newnode;
            }
            return ;
        }
        prev = current;
        current = current->next;
    }
    // here, it means that we reached the end of the list; the new element
    // must be placed at the tail

    prev->next = newnode;
    newnode->next = NULL;
}


// ---------------- VERSIONE RICORSIVA --------------------
void do_insert_in_order_with_recursion(t_node ** p_head, t_node * newnode)
{
    if (*p_head == NULL) {
        newnode->next = NULL;
        *p_head = newnode;
        return;
    }

    if (strcmp((*p_head)->data.key, newnode->data.key) > 0) {
        newnode->next = *p_head;
        *p_head = newnode;
    }
    else {
        do_insert_in_order_with_recursion(&((*p_head)->next), newnode);
    }
}


void insert_in_order_with_recursion(t_list * l, t_element e)
{
    t_node * newnode;

    newnode = malloc(sizeof(t_node));
    newnode->data = e;

    do_insert_in_order_with_recursion(&l->head, newnode);
}


void print_list(t_list * l)
{
    t_node * p = l->head;

    while (p != NULL) {
        printf("%s %d\n", p->data.key, p->data.value);
        p = p->next;
    }
}


void load_file(t_list * l, char * fname)
{
    FILE * f;
    t_element e;
    f = fopen(fname, "r");
    if (f == NULL) return;

    while (fscanf(f, "%s %d", e.key, &e.value) != EOF) {
        //insert_in_order(l, e);
        insert_in_order_with_recursion(l, e);
    }

    fclose(f);
}


main()
{
    t_list mylist;
    init_list(&mylist);
    load_file(&mylist, "file_for_list.txt");
    print_list(&mylist);
}

« Last Edit: 14-11-2013, 17:45:36 by ɹǝǝuıƃuǝsɹǝʌǝɹ » Logged
Pages: [1]   Go Up
Print
Jump to: