[C++] Problema con LCS

**stevefox87** · 29-12-2008, 16:03

Salve ragazzi, ho un problema con il seguente codice c++.
All'università il prof ci ha proprosto questa implementazione della più lunga sottosequenza comune usando l'allocazione dinamica delle matrici. Lui per il progetto d'esame non vuol vedere malloc e calloc, ma esige l'uso di new e delete per allocare dinamicamente. Ora vi posto sia il codice con calloc e free, sia quello che ho "aggiustato" io usando new e delete(che al momento dell'esecuzione non va bene e non capisco il perchè), sperando che qualcuno di voi risolva questo problema. Grazie in anticipo.

codice:

#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef int ** MatriceInt;
typedef char ** MatriceChar;

string LCS(string X, string Y, MatriceInt &C, MatriceChar &B) {
	int X_len = X.length() + 1; int Y_len = Y.length() + 1; int i,j;
	string lcs =" ";
	C = (MatriceInt) calloc(X_len, sizeof(int*));       
        // Alloca la matrice per memorizzare la lunghezza  devi vari sottoproblemi LCS
          B = (MatriceChar) calloc(X_len, sizeof(char*));
	for (i =0; i< X_len; i++)
	{ C[i] = (int *)calloc(Y_len, sizeof(int)); B[i] = (char *)calloc(Y_len, sizeof(char));}
	B[0][0] = '\\';
	for (i = 1; i< X_len; i++) {
	  for (j = 1; j< Y_len; j++) {
	           if (X[i-1] == Y[j-1])
		     { C[i][j] = 1 + C[i-1][j-1];  B[i][j] = '\\';}
	              else if(C[i-1][j] >= C[i][j-1])
		                  { C[i][j] = C[i-1][j]; B[i][j] = '|';}
		          else {C[i][j]=C[i][j-1]; B[i][j] = '-';}
		}
	         }
	for(i = 1; i< Y_len; i++)                  // Costruisce la stringa di lunghezza LCS
	{ if(C[X_len-1][i] > C[X_len-1][i-1])  lcs = lcs + Y[i-1];}
	return lcs;
}
int main(){
	string X = "FRANCESCO"; string Y = "FWANCICO";
        int X_len = X.length() + 1; int Y_len = Y.length() + 1; int i,j;
	MatriceInt C = NULL; MatriceChar B = NULL;	
	string lcs = LCS(X, Y, C, B);
        cout << "LCS = " << C[X_len-1][Y_len-1] << lcs <<endl<< endl << "   ";
         // Stampa la matrice C che contiene le soluzioni dei vari sottoproblemi
	for(i = 0; i< Y_len;i++)   cout << " " << Y[i];
	for (i =0; i< X_len; i++){
		cout << endl;
		if (i >= 1)    cout << X[i-1] << " ";
		else            cout << "  ";
		for (j = 0; j< Y_len; j++)   {  cout << C[i][j] << " "; }
	}
	cout << endl << endl << "   ";     
 // Stampa la matrice B che contiene i percorsi  dei vari sottoproblemi	
	for(i = 0; i< Y_len; i++)     cout << " " << Y[i];
	for (i =0; i< X_len; i++){
	cout << endl;
	   if (i >= 1)    cout << X[i-1] << " ";
	    else           cout << "  ";
		for (j = 0; j< Y_len; j++) {cout << B[i][j] << " ";}
	}
	if (C != NULL)  // Delloca le matrici
	{
	 for (i=0;i<X.length();i++)  { free(C[i]); free(B[i]);}
	free(C); free(B);
	}
	cout << endl;
	return 0;
}

codice:

#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef int ** MatriceInt;
typedef char ** MatriceChar;

string LCS(string X, string Y, MatriceInt &C, MatriceChar &B) {
	int X_len = X.length() + 1; int Y_len = Y.length() + 1; int i,j;
	string lcs =" ";
	C = new int*[X_len];       
        // Alloca la matrice per memorizzare la lunghezza  devi vari sottoproblemi LCS
          B = new char*[X_len];
	for (i =0; i< X_len; i++)
	{ C[i]=new int[Y_len]; B[i]=new char[Y_len];}
	B[0][0] = '\\';
	for (i = 1; i< X_len; i++) {
	  for (j = 1; j< Y_len; j++) {
	           if (X[i-1] == Y[j-1])
		     { C[i][j] = 1 + C[i-1][j-1];  B[i][j] = '\\';}
	              else if(C[i-1][j] >= C[i][j-1])
		                  { C[i][j] = C[i-1][j]; B[i][j] = '|';}
		          else {C[i][j]=C[i][j-1]; B[i][j] = '-';}
		}
	         }
	for(i = 1; i< Y_len; i++)                  // Costruisce la stringa di lunghezza LCS
	{ if(C[X_len-1][i] > C[X_len-1][i-1])  lcs = lcs + Y[i-1];}
	return lcs;
}
int main(){
	string X = "FRANCESCO"; string Y = "FWANCICO";
        int X_len = X.length() + 1; int Y_len = Y.length() + 1; int i,j;
	MatriceInt C = NULL; MatriceChar B = NULL;	
	string lcs = LCS(X, Y, C, B);
        cout << "LCS = " << C[X_len-1][Y_len-1] << lcs <<endl<< endl << "   ";
         // Stampa la matrice C che contiene le soluzioni dei vari sottoproblemi
	for(i = 0; i< Y_len;i++)   cout << " " << Y[i];
	for (i =0; i< X_len; i++){
		cout << endl;
		if (i >= 1)    cout << X[i-1] << " ";
		else            cout << "  ";
		for (j = 0; j< Y_len; j++)   {  cout << C[i][j] << " "; }
	}
	cout << endl << endl << "   ";     
 // Stampa la matrice B che contiene i percorsi  dei vari sottoproblemi	
	for(i = 0; i< Y_len; i++)     cout << " " << Y[i];
	for (i =0; i< X_len; i++){
	cout << endl;
	   if (i >= 1)    cout << X[i-1] << " ";
	    else           cout << "  ";
		for (j = 0; j< Y_len; j++) {cout << B[i][j] << " ";}
	}
	if (C != NULL)  // Delloca le matrici
	{
	 for (i=0;i<X.length();i++)  { delete(C[i]); delete(B[i]);}
	delete(C); delete(B);
	}
	cout << endl;
	return 0;
}

**oregon** · 29-12-2008, 16:08

"Non va bene" in che senso ? Hai errori ? Di compilazione ? A runtime ?

**stevefox87** · 29-12-2008, 16:21

Non ci sono errori di compilazione, ma al momento dell'esecuzione escono una serie di numeri strani che non dovrebbero uscire.

**shodan** · 29-12-2008, 16:30

Intanto puoi correggere i delete che sono sbagliati. Se usi un new[] per allocare qualcosa, devi usare un delete [] per deallocarlo.

codice:

for (i=0;i<X.length();i++)  { 
   delete[] C[i]; 
   delete[] B[i];
}
delete[] C; delete[] B;

**stevefox87** · 30-12-2008, 17:07

Originariamente inviato da shodan
Intanto puoi correggere i delete che sono sbagliati. Se usi un new[] per allocare qualcosa, devi usare un delete [] per deallocarlo.

codice:

for (i=0;i<X.length();i++)  { 
   delete[] C[i]; 
   delete[] B[i];
}
delete[] C; delete[] B;

Si, questo è un errore cretino che ho modificato...ma il resto non capisco perchè non va.
Quando lo mando in esecuzione escono dei numeri strani quando dovrebbe apparire una matrice.

**shodan** · 30-12-2008, 17:59

Attento che stai utilizzando la matrice C senza averla inizializzata ad un valore noto e new non la iniziallizza a zero come la calloc

codice:

string LCS(string X, string Y, MatriceInt &C, MatriceChar &B) {
	int X_len = X.length() + 1; int Y_len = Y.length() + 1; int i,j;
	string lcs =" ";
	C = new int*[X_len]; // qui istanzi la matrice      
        // Alloca la matrice per memorizzare la lunghezza  devi vari sottoproblemi LCS
          B = new char*[X_len];
	for (i =0; i< X_len; i++)
	{ C[i]=new int[Y_len]; B[i]=new char[Y_len];}
	B[0][0] = '\\\';
	for (i = 1; i< X_len; i++) {
	  for (j = 1; j< Y_len; j++) {
	           if (X[i-1] == Y[j-1])
		     { C[i][j] = 1 + C[i-1][j-1]; // e qui sommi 1 alla porcheria che contiene
// dal momento che non avendo inizializzato la matrice 
// ad un valore noto, i valori contenuti sono causali.
                        B[i][j] = '\\\';}
	              else if(C[i-1][j] >= C[i][j-1])
		                  { C[i][j] = C[i-1][j]; B[i][j] = '|';}
		          else {C[i][j]=C[i][j-1]; B[i][j] = '-';}
		}
	         }
	for(i = 1; i< Y_len; i++)                  // Costruisce la stringa di lunghezza LCS
	{ if(C[X_len-1][i] > C[X_len-1][i-1])  lcs = lcs + Y[i-1];}
	return lcs;
}

**stevefox87** · 30-12-2008, 18:45

Originariamente inviato da shodan
Attento che stai utilizzando la matrice C senza averla inizializzata ad un valore noto e new non la iniziallizza a zero come la calloc

codice:

string LCS(string X, string Y, MatriceInt &C, MatriceChar &B) {
	int X_len = X.length() + 1; int Y_len = Y.length() + 1; int i,j;
	string lcs =" ";
	C = new int*[X_len]; // qui istanzi la matrice      
        // Alloca la matrice per memorizzare la lunghezza  devi vari sottoproblemi LCS
          B = new char*[X_len];
	for (i =0; i< X_len; i++)
	{ C[i]=new int[Y_len]; B[i]=new char[Y_len];}
	B[0][0] = '\\\';
	for (i = 1; i< X_len; i++) {
	  for (j = 1; j< Y_len; j++) {
	           if (X[i-1] == Y[j-1])
		     { C[i][j] = 1 + C[i-1][j-1]; // e qui sommi 1 alla porcheria che contiene
// dal momento che non avendo inizializzato la matrice 
// ad un valore noto, i valori contenuti sono causali.
                        B[i][j] = '\\\';}
	              else if(C[i-1][j] >= C[i][j-1])
		                  { C[i][j] = C[i-1][j]; B[i][j] = '|';}
		          else {C[i][j]=C[i][j-1]; B[i][j] = '-';}
		}
	         }
	for(i = 1; i< Y_len; i++)                  // Costruisce la stringa di lunghezza LCS
	{ if(C[X_len-1][i] > C[X_len-1][i-1])  lcs = lcs + Y[i-1];}
	return lcs;
}

E quindi come posso aggiustare tutto ciò?

**shodan** · 30-12-2008, 19:01

codice:

	for (i =0; i< X_len; i++) { 
             C[i]=new int[Y_len]; 
             memset(C[i],0,sizeof(int)*Y_len);
             B[i]=new char[Y_len];
        }

Discussione: [C++] Problema con LCS

Strumenti discussione

Ricerca discussione

Visualizza

[C++] Problema con LCS

Permessi di invio