Esercizio liste collegate con puntatori in C

di il
1 risposte

Esercizio liste collegate con puntatori in C

Devo fare un programma completo per questo esercizio:

Scrivere la funzione C che riceve in ingresso una lista collegata con puntatori di valori float ed una variabile
target di tipo float ed opera nel modo seguente:
• Cerca gli elementi della lista uguali a target e li duplica (fa seguire all’elemento esistente un nuovo
elemento con valore target);
• Scrive in un vettore di appoggio V gli indirizzi degli elementi inseriti;
• Restituisce l’array V come valore di ritorno della funzione (con istruzione return), ed il numero di
elementi di V tra i parametri formali della funzione.
Scrivere anche l’equazione di costo e la complessità dell’algoritmo. (Nota: la funzione deve eseguire le
operazioni nell’ordine indicato)
(Esempio: lista di ingresso {1,2,3,2,4,5} target = 2, lista di uscita {1,2,2,3,2,2,4,5}).

Il programma che ho scritto io è il seguente:
#include <stdio.h>
#include <stdlib.h>
#include <float.h>
#include <math.h>
#define TRUE 1
#define FALSE 0
typedef unsigned short int boolean;

struct list{
    float value;
    struct list * next_ptr;
};

// prototipi delle funzioni

int main();
boolean isEqual(float a, float b);
void init(struct list ** ptr);
void suf_insert(struct list ** ptr, float value);
void pre_insert(struct list ** ptr, float value);
void visit_list(struct list * ptr);
void visit_array(struct list ** V, int dimension);
struct list ** duplicate_and_copy(struct list ** ptr, float target, int * size);

int main() {
    setbuf(stdout, 0);
    struct list *ptr;
    init(&ptr);
    int choice;
    float value;
    float target;
    int dimension;
    struct list ** V;
    do{
        printf("Selezionare l'operazione da eseguire: \n1) Inserimento (in coda) \n2) Esegui funzione \n3) Uscita dal programma \n");
        scanf("%d", &choice);
        switch(choice) {
            case 1:
            {
                printf("\n Definire valore float da inserire: ");
                scanf("%f", &value);
                suf_insert(&ptr, value);
                printf("L'inserimento e' avvenuto correttamente, la lista e' la seguente: \n");
                visit_list(ptr);
                break;
            }
            case 2:
            {
                printf("\n Definire valore target da cercare per poi essere duplicato: ");
                scanf("%f", &target);
                V = duplicate_and_copy(&ptr, target, &dimension);
                printf("Questo e' l'array finale: \n");
                visit_array(V, dimension);
                printf("Questa e' la lista finale: \n");
                visit_list(ptr);
                break;
            }
            case 3:
                return 0;
            default:
                printf("Errore inserimento, il programma verra' arrestato");
                return 0;
        }
    } while(TRUE);
}

struct list ** duplicate_and_copy(struct list ** ptr, float target, int * size){
    int dimension=0;
    int count=0;
    struct list * tmp_ptr;
    struct list ** ptr1 = ptr;
    struct list ** V;
    while(*ptr!=NULL){
        if(isEqual(target, (*ptr)->value))
            dimension++;
        *ptr=(*ptr)->next_ptr;
    }
    V=(struct list**)malloc(sizeof(struct list)*dimension);
    ptr=ptr1;
    while(*ptr!=NULL){
        if(isEqual((*ptr)->value, target)){
            tmp_ptr=(struct list*)malloc(sizeof(struct list));
            (*size)++;
            tmp_ptr->value=target;
            tmp_ptr->next_ptr=(*ptr)->next_ptr;
            (*ptr)->next_ptr=tmp_ptr;
            V[count]=tmp_ptr;
            count++;
            ptr=&((*ptr)->next_ptr->next_ptr);
        }
        else
            ptr=&((*ptr)->next_ptr);
    }
    return V;
}

boolean isEqual(float a, float b){
    float diff,max;
    diff=fabs(a-b);
    a=fabs(a);
    b=fabs(b);
    max=(a>b)?a : b;
    if(diff<=FLT_EPSILON*max){
        return TRUE;
    }
    else
        return FALSE;
}

void init(struct list ** ptr){
    *ptr = NULL;
}

void pre_insert(struct list ** ptr, float value){
    struct list * tmp;
    tmp =(struct list*)malloc(sizeof(struct list));
    tmp->value=value;
    tmp->next_ptr=*ptr;
    *ptr=tmp;
}

void suf_insert(struct list ** ptr, float value){
    while(*ptr!=NULL){
        ptr=&((*ptr)->next_ptr);
    }
    pre_insert(ptr,value);
}

void visit_list(struct list * ptr){
    printf("[");
    while(ptr!=NULL){
        printf("%f", ptr->value);
        ptr=ptr->next_ptr;
        if(ptr!=NULL){
            printf(",");
        }
    }
    printf("]\n");
}


void visit_array(struct list ** V, int dimension){
    int count;
    for(count=0;count<dimension;count++){
        printf("V[%d]->0x%p\n",count,V[count]);
    }
}
Una volta arrivato alla stampa dell'array finale, il programma stampa una trentina di valori e dà uno strano exit code, qualcuno può darmi una mano?

1 Risposte

  • Re: Esercizio liste collegate con puntatori in C

    Il problema è nella funzione duplicate_and_copy():
    - innanzitutto se gli elementi dell'array devono essere indirizzi di memoria di struct list, non trovi che ci sia qualcosa di sbagliato nella seguente riga di codice?
    V=(struct list**)malloc(sizeof(struct list)*dimension);
    - al termine del seguente frammento di codice a cosa punta la testa della lista?
    int dimension=0;
        int count=0;
        struct list * tmp_ptr;
        struct list ** ptr1 = ptr;
        struct list ** V;
        while(*ptr!=NULL){
            if(isEqual(target, (*ptr)->value))
                dimension++;
            *ptr=(*ptr)->next_ptr;
        }
        V=(struct list**)malloc(sizeof(struct list)*dimension);
        ptr=ptr1;
    - perchè per inserire nuovi elementi nella lista non utilizzi la funzione pre_insert()?
Devi accedere o registrarti per scrivere nel forum
1 risposte