e-commerce84
07-11-2009, 15:49
Ciao,
ho un problema con un metodo ricorsivo, l'errore che mi dàè il seguente:
Parse error: parse error in C:\xampp\htdocs\PHPEsempi\algoritmiOrdinamento\Heap.php on line 43
Il codice per intero della mia classe è il seguente:
<?php
/* Classe che implementa la struttura dati HEAP e la sua funzionalità per
l'ordinamento di una collezione mediante l'algoritmo di ordinamento
Heap Sort */
class Heap{
/* Variabile di istanza che implementa la struttura dati ad albero
dell'heap per mezzo di un array */
private $heap = array();
private $heapSize = 0; // Numero di elementi correntemente dentro l'HEAP
/* Costruttore: Crea un nuovo oggetto istanza di Heap. Riceve un qualunque
array come parametro di input, lo copia dentro alla
variabile di istanza heap[] (mettendoli dentro l'array Heap
a partire dalla posizione 1) e su di esso richiama ilmetodo
di classe heapify per trasformarlo in loco in un heap */
public function __construct($arr=array()){
/* Scorre l'array ricevuto come parametro e lo copia nel'array heap
traslando gli elementi una posizione in avanti (per farli partire dalla
posizione 1 e non 0) */
foreach($arr as $chiave => $valore){
$heap[$chiave+1] = $arr[chiave]; // Copia gli elementi traslandoli
$heapSize ++; //Incrementa di 1 il numero elementi inseriti nell'heap
}
/* Invoca il metodo heapify sull'array partendo dalla prima posizione che
sarà trasformato in un HEAP */
$this->heap = $this->heapify($heap, 1);
}
/* Metodo che dato un qualsiasi array lo riarrangia trasformandolo in una
struttura dati HEAP memorizzata sempre nello stesso array di partenza */
private function heapify($heap, $nodo_i){
echo "heapify è stata chiamata<br />";
/* CASO BASE: Se heap è vuoto ritorna al chiamante */
if(sinistro($nodo_i) > this->$heapSize) return;
/* Altrimenti procedi ricorsivamente nel seguente modo */
else{
$sin = sinistro($nodo_i); // Posizione della radice del sottoalbero sinistro
$des = destro($nodo_i); // Posizione della radice del sottoalbero destro
$nodoCorrente = $sin;
heapify($heap, $nodoCorrente); // Chiama ricorsivamente sul sottoalbero sinistro
$nodoCorrente = $des;
heapify($heap, $nodoCorrente); // Chiama ricorsivamente sul sottoalbero destro
fixHeap($nodoCorrente, $heap);
}
}
/* Metodo che prende in input un quasi heap (cioè un heap con al più
un'anomalia) ed un indice nodo_i e restituisce un heap corretto */
private function fixHeap($nodo_i, $quasiHeap[]){
$sin; // Conterrà l'indice del figlio sinistro
$des; // Conterrà l'indice del figlio destro
$max; // Conterrà l'indice del figlio avente valore massimo
/* Se nodo_i è una foglia allora ritorna al chiamante (caso base)*/
if(sinistro($nodo_i) > this->$heapSize) return;
/* Se nodo_i non è una foglia */
else{
$sin = sinistro($nodo_i); // Posizione del figlio sinistro
$des = destro($nodo_i); // Posizione del figli destro
/* Trova il massimo tra il figlio sinistro e destro di nodo_i */
if($quasiHeap[sin] >= $quasiHeap[$des]) $max = $sin;
else $max = $des;
/* Se il valore in posizione nodo_i è MINORE del valore del figlio
massimo */
if(quasiHeap[$nodo_i] < quasiHeap[$max]){
$tmp = $quasiHeap[$nodo_i]; // Salva il valore in posizione i
/* Scambia il valore in posizione nodo_i con il valore in
posizione max */
$quasiHeap[$nodo_i] = $quasiHeap[max];
$quasiHeap[$max] = $tmp;
/* Invoca ricorsivamente il metodo fixHeap() passandogli come
parametro lo stesso array e la posizione max */
fixHeap($max, $quasiHeap);
}
}
}
/* Metodo che dato l'indice di un elemento dell'heap calcola l'indice del
suo figlio sinistro nell'heap */
private function sinistro(indicePadre){
$sin = $indicePadre*2; // Calcola l'indice del figlio sinistro
return $sin; // Ritorna il valore di sin al chiamante
}
/* Metodo che dato l'indice di un elemento dell'heap calcola l'indice del
suo figlio destro nell'heap */
private function destro(indicePadre){
$des = $indicePadre*2 + 1; // Calcola l'indice del figlio destro
return $padre; // Ritorna il valore di des al chiamante
}
/* Metodo che dato un elemento dell'heap calcolal'indice del padre */
pruvate function padre(indiceNodo){
$padre = floor(i/2); // Calcola la parte intera
return $padre; // Ritorna al chiamante la posizione del padre
}
}
?>
Ma ovviamente il problema in questione dovrebbe essere causato solo dal metodo ricorsivo heapify(), la linea di codice incriminata è la seguente:
if(sinistro($nodo_i) > this->$heapSize) return;
A naso credo che non gli piaccia quel return senza niente dopo...di fatto il metodo ricorsivo non deve ritornare alcun valore ma semplicemente quando raggiunge il caso base deve ritornare il controllo alla precedente invocazione...
Se dipendesse da ciò come posso gestire tale situazione? se invece non c'entra niente da cosa dipende questo errore?
Grazie
ho un problema con un metodo ricorsivo, l'errore che mi dàè il seguente:
Parse error: parse error in C:\xampp\htdocs\PHPEsempi\algoritmiOrdinamento\Heap.php on line 43
Il codice per intero della mia classe è il seguente:
<?php
/* Classe che implementa la struttura dati HEAP e la sua funzionalità per
l'ordinamento di una collezione mediante l'algoritmo di ordinamento
Heap Sort */
class Heap{
/* Variabile di istanza che implementa la struttura dati ad albero
dell'heap per mezzo di un array */
private $heap = array();
private $heapSize = 0; // Numero di elementi correntemente dentro l'HEAP
/* Costruttore: Crea un nuovo oggetto istanza di Heap. Riceve un qualunque
array come parametro di input, lo copia dentro alla
variabile di istanza heap[] (mettendoli dentro l'array Heap
a partire dalla posizione 1) e su di esso richiama ilmetodo
di classe heapify per trasformarlo in loco in un heap */
public function __construct($arr=array()){
/* Scorre l'array ricevuto come parametro e lo copia nel'array heap
traslando gli elementi una posizione in avanti (per farli partire dalla
posizione 1 e non 0) */
foreach($arr as $chiave => $valore){
$heap[$chiave+1] = $arr[chiave]; // Copia gli elementi traslandoli
$heapSize ++; //Incrementa di 1 il numero elementi inseriti nell'heap
}
/* Invoca il metodo heapify sull'array partendo dalla prima posizione che
sarà trasformato in un HEAP */
$this->heap = $this->heapify($heap, 1);
}
/* Metodo che dato un qualsiasi array lo riarrangia trasformandolo in una
struttura dati HEAP memorizzata sempre nello stesso array di partenza */
private function heapify($heap, $nodo_i){
echo "heapify è stata chiamata<br />";
/* CASO BASE: Se heap è vuoto ritorna al chiamante */
if(sinistro($nodo_i) > this->$heapSize) return;
/* Altrimenti procedi ricorsivamente nel seguente modo */
else{
$sin = sinistro($nodo_i); // Posizione della radice del sottoalbero sinistro
$des = destro($nodo_i); // Posizione della radice del sottoalbero destro
$nodoCorrente = $sin;
heapify($heap, $nodoCorrente); // Chiama ricorsivamente sul sottoalbero sinistro
$nodoCorrente = $des;
heapify($heap, $nodoCorrente); // Chiama ricorsivamente sul sottoalbero destro
fixHeap($nodoCorrente, $heap);
}
}
/* Metodo che prende in input un quasi heap (cioè un heap con al più
un'anomalia) ed un indice nodo_i e restituisce un heap corretto */
private function fixHeap($nodo_i, $quasiHeap[]){
$sin; // Conterrà l'indice del figlio sinistro
$des; // Conterrà l'indice del figlio destro
$max; // Conterrà l'indice del figlio avente valore massimo
/* Se nodo_i è una foglia allora ritorna al chiamante (caso base)*/
if(sinistro($nodo_i) > this->$heapSize) return;
/* Se nodo_i non è una foglia */
else{
$sin = sinistro($nodo_i); // Posizione del figlio sinistro
$des = destro($nodo_i); // Posizione del figli destro
/* Trova il massimo tra il figlio sinistro e destro di nodo_i */
if($quasiHeap[sin] >= $quasiHeap[$des]) $max = $sin;
else $max = $des;
/* Se il valore in posizione nodo_i è MINORE del valore del figlio
massimo */
if(quasiHeap[$nodo_i] < quasiHeap[$max]){
$tmp = $quasiHeap[$nodo_i]; // Salva il valore in posizione i
/* Scambia il valore in posizione nodo_i con il valore in
posizione max */
$quasiHeap[$nodo_i] = $quasiHeap[max];
$quasiHeap[$max] = $tmp;
/* Invoca ricorsivamente il metodo fixHeap() passandogli come
parametro lo stesso array e la posizione max */
fixHeap($max, $quasiHeap);
}
}
}
/* Metodo che dato l'indice di un elemento dell'heap calcola l'indice del
suo figlio sinistro nell'heap */
private function sinistro(indicePadre){
$sin = $indicePadre*2; // Calcola l'indice del figlio sinistro
return $sin; // Ritorna il valore di sin al chiamante
}
/* Metodo che dato l'indice di un elemento dell'heap calcola l'indice del
suo figlio destro nell'heap */
private function destro(indicePadre){
$des = $indicePadre*2 + 1; // Calcola l'indice del figlio destro
return $padre; // Ritorna il valore di des al chiamante
}
/* Metodo che dato un elemento dell'heap calcolal'indice del padre */
pruvate function padre(indiceNodo){
$padre = floor(i/2); // Calcola la parte intera
return $padre; // Ritorna al chiamante la posizione del padre
}
}
?>
Ma ovviamente il problema in questione dovrebbe essere causato solo dal metodo ricorsivo heapify(), la linea di codice incriminata è la seguente:
if(sinistro($nodo_i) > this->$heapSize) return;
A naso credo che non gli piaccia quel return senza niente dopo...di fatto il metodo ricorsivo non deve ritornare alcun valore ma semplicemente quando raggiunge il caso base deve ritornare il controllo alla precedente invocazione...
Se dipendesse da ciò come posso gestire tale situazione? se invece non c'entra niente da cosa dipende questo errore?
Grazie