PDA

Visualizza la versione completa : C++ Ordinamento Lista doppiamente concatenata


hitman89
11-01-2013, 12:12
Salve, ho un problema con un programma c++ sull'ordinamento di una lista doppiamente concatenata. Il programma esegue varie operazioni su un polinomio. Le varie funzioni non mi danno problemi, a parte quella dell'ordinamento del polinomio secondo il grado dell'esponente. Il programma non da problemi di compilazione, ma di esecuzione. Infatti quando lo eseguo, arrivato alla funzione ordina, il programma si interrompe. Vi posto tutto il codice diviso in tre parti: il main, il file header e il file cpp. Grazie mille per le eventuali risposte.

MAIN.CPP
#include <stdlib.h>
#include "Polinomio.h"
#include <iostream>
using namespace std;
int main()
{
cout<<"\nCreo e inizializzo la lista\n";
polinomio mylist;
polinodo *p;
init_list(&mylist);
insert(&mylist, 2, 3);
insert(&mylist, 2, 1);
insert(&mylist, 3, 5);
insert(&mylist, 3, 7);
insert(&mylist, 0, 9);

//STAMPA
cout<<"\nStampo la lista: \n"<<endl;
cout<<&mylist;

//CERCA NODO DATO L'ESPONENTE
p=search(&mylist,7);
cout<<"\nCerca \n";
cout<<"\nIl polinodo cercato e': "<<p->coeff<<"x^"<<p->espon<<endl;

//VALUTA IL POLINOMIO IN UN PUNTO
cout<<"\nValuto il polinomio in un punto dato: \n";
double v=eval(&mylist,0.9);
cout<<"\nIl valore calcolato e': "<<v<<endl;

//ADDIZIONO UN NODO AL POLINOMIO
cout<<"\n Effettuo la somma tra il polinomio e un polinodo\n";
add(&mylist,4,7);
cout<<"\n Dopo la somma il polinomio e':\n";
cout<<&mylist<<endl;

//GRADO DEL POLINOMIO
cout<<"\nIl grado del polinomio e': ";
int e=degree(&mylist);
cout<<e<<endl;

//DERIVATA
cout<<"\nLa derivata del polinomio e': \n";
derivata(&mylist);
ordina(&mylist);
cout<<&mylist<<endl;
return 0;
}


POLINOMIO.H
#ifndef POLINOMIO_H
#define POLINOMIO_H
#include <iostream>
using namespace std;
typedef struct Polinodo
{
// informazioni contenute nel nodo
double coeff;
unsigned int espon;
// puntatore al nodo precedente
struct Polinodo *prev;
// puntatore al nodo successivo
struct Polinodo *next;
} polinodo;
typedef struct Polinomio
{
// tiene traccia di quanti nodi sono presenti all'interno della lista
int count;
// puntatore al primo nodo della lista
struct Polinodo *header;
// puntatore all'ultimo nodo della lista
struct Polinodo *tailer;
} polinomio;

void init_list(polinomio *);
void delete_list(polinomio *);
void insert(polinomio *, double,unsigned int );
polinodo *search(polinomio* ,unsigned int);
void delete_node(polinomio *, polinodo );
void delete_value(polinomio *, int );
void print_list(polinomio *);
void add(polinomio *,double,unsigned int);
int degree(polinomio *);
void derivata(polinomio *);
double eval(polinomio *,double);
ostream &operator<<(ostream&,polinomio *);
void ordina(polinomio *);
#endif


POLINOMIO.CPP

#include <stdio.h>
#include <stdlib.h>
#include "Polinomio.h"
#include <iostream>
#include <math.h>

using namespace std;
//INIZIALIZZAZIONE DELLA LISTA
void init_list(polinomio *list)
{
// la lista inizialmente non contiene elementi
list->count = 0;
// sia la testa che la coda puntano inizialmente a NULL
list->header = list->tailer = NULL;
}
//CANCELLAZIONE DELL'INTERA LISTA
void delete_list(polinomio *list)
{
polinodo *n1, *n2;
n1 = list->header;
// scorro i nodi della lista e li cancello
// tramite la funzione free() libero la memoria da essi occupata
while (n1 != NULL)
{
n2 = n1->next;
free(n1);
n1 = n2; }
}
//AGGIUNTA DI UN NUOVO NODO ALLA LISTA
void insert(polinomio *list, double new_coeff,unsigned int new_espon)
{
// creo il nuovo nodo e gli alloco uno spazio di memoria
polinodo *new_node;
new_node = (polinodo*)malloc(sizeof(polinodo));
// inizializzo il nuovo nodo e gli inserisco il nuovo dato
new_node->coeff = new_coeff;
new_node->espon=new_espon;
new_node->next = NULL;
// inserisco il nodo all'interno della lista: due casi possibili
// CASO 1: la lista e' vuota (count e' 0)
// il nuovo nodo fara' sia da header che da tailer
if (list->count == 0)
{
new_node->prev = NULL;
list->header = list->tailer = new_node;
}
// CASO 2: la lista contiene gia' almeno un elemento
// aggancio il nuovo nodo alla fine della lista
// dopo l'inserimento, il nuovo nodo sara' quindi il tailer della lista
else
{
new_node->prev = list->tailer;
list->tailer->next = new_node;
list->tailer = new_node;
}
// aumento il contatore dei nodi della lista
list->count++;
}
//RICERCA DI UN VALORE ALL'INTERNO DELLA LISTA
polinodo* search(polinomio *list,unsigned int e)
{
polinodo *tmp;
tmp = list->header;
// scorro la lista cercando value
// ritorno l'indirizzo del primo nodo che contiene value
// altrimenti continuo a scorrere la lista
while (tmp != NULL)
{

if (tmp->espon == e)
return tmp;
tmp = tmp->next;
}
// se non trovo nessun nodo contenente value, ritorno NULL
return NULL;
}
//CANCELLAZIONE DI UN SINGOLO NODO
void delete_node(polinomio *list, polinodo *n)
{
// sgancio il nodo puntato da n dalla lista
n->prev->next = n->next;
if (n->next != NULL) // previene possibili Segmentation Fault
n->next->prev = n->prev;
// libero la memoria allocata
free(n);
list->count--;
return;
}
//CANCELLAZIONE DEI NODI IN CUI è PRESENTE UN VALORE INDICATO
void delete_value(polinomio *list, int value)
{
polinodo *tmp;
while ((tmp = search(list, value)) != NULL)
delete_node(list, tmp);
return;
}
//STAMPA DI TUTTI I NODI DELLA LISTA
void print_list(polinomio *list)
{
polinodo *tmp;
tmp = list->header;
int i;
for (i = 1; i <= list->count; i++)
{
cout<<"nodo "<<i<<":"<< tmp->coeff<<" "<<tmp->espon<<endl;
tmp = tmp->next;
}
return;
}
void add(polinomio *list,double c,unsigned int e) {
polinodo *temp;
temp=list->header;
for(int i=0;i<list->count;i++)
{
if(temp->espon==e)
temp->coeff+=c;
temp=temp->next;
}
}
int degree(polinomio *list) {
unsigned int e=0;
polinodo* temp;
temp=list->header;
for(int i=0;i<list->count;i++) {
if(temp->espon>e && temp->coeff!=0)
e=temp->espon;
temp=temp->next;
}
return e;
}
void derivata(polinomio * list) {
polinodo *temp;
temp=list->header;
for(int i=0;i<list->count;i++) {
temp->coeff*=temp->espon;
temp->espon-=1;
temp=temp->next;
}
}
double eval(polinomio *list,double x) {
polinodo *temp;
temp=list->header;
double v=0;
for(int i=0;i<list->count;i++) {
v=v+pow((temp->coeff)*x,temp->espon);
temp=temp->next;
}
return v;
}
ostream& operator<<(ostream& os,polinomio *list) {
polinodo *temp;
temp=list->header;
cout<<"\nIl polinomio e':\n";
for(int i=0;i<list->count;i++) {
cout<<"+"<<temp->coeff<<"x^"<<temp->espon;
temp=temp->next;
}
return os;
}



void ordina(polinomio *list) {
polinodo *temp;
temp=list->header;
double c;
unsigned int e;

for(int i=0;i<list->count;i++) {

for(int j=0;j<(list->count)-1;j++) {
if(temp->espon<temp->next->espon) {
c=temp->coeff;
e=temp->espon;
temp->espon=temp->next->espon;
temp->coeff=temp->next->coeff;
temp->next->coeff=c;
temp->next->espon=e;
}

}
temp=temp->next;

}
}

YuYevon
11-01-2013, 22:13
La prossima volta posta il codice utilizzando i tag
[/b]][/code], altrimenti si perde l'indentazione e non si capisce nulla.

Ti consiglio comunque di rivedere la funzione "ordina":

[code]
void ordina(polinomio *list)
{
polinodo *temp;
temp=list->header;
double c;
unsigned int e;

for(int i=0;i<list->count;i++) {
for(int j=0;j<(list->count)-1;j++) {
if(temp->espon<temp->next->espon) {
c=temp->coeff;
e=temp->espon;
temp->espon=temp->next->espon;
temp->coeff=temp->next->coeff;
temp->next->coeff=c;
temp->next->espon=e;
}
}
temp=temp->next;
}
}


poiché il for esterno cicla su tutti gli elementi della lista, al momento dell'ultima iterazione "temp" punterà all'elemento in coda che, per definizione, non ha un "nodo prossimo", quindi temp->next risulterà NULL e pertanto la dereferenziazione "temp->next->espon" non sarà lecita.

Non ho controllato il resto del codice. Per adesso correggi questo.

hitman89
12-01-2013, 12:01
Ciao. Innanzitutto grazie per la risposta.
Scusatemi per non aver utilizzato i tag ma non lo sapevo.
Hai ragione quando dici che il problema è sulla funzione ordina, infatti, come dici tu, all'ultima iterazione punta alla coda della lista che non ha un nodo prossimo.
Alla fine ho capito cosa mancava: far partire temp dalla testa della lista all'inizio di ogni iterazione del ciclo for esterno. Inoltre,l'istruzione temp=temp->next andava va messa alla fine del primo ciclo for.
Posto il codice della funzione ordina corretto:


void ordina(polinomio *list) {
polinodo *temp;
temp=list->header;
double c;
unsigned int e;
cout<<list->count<<endl;
for(int i=0;i<(list->count);i++) {
for(int j=0;j<(list->count)-1;j++) {
if(temp->espon<temp->next->espon) {
c=temp->coeff;
e=temp->espon;
temp->espon=temp->next->espon;
temp->coeff=temp->next->coeff;
temp->next->coeff=c;
temp->next->espon=e;
}
temp=temp->next;
}
temp=list->header;
}
}

Loading