Newsgroup: it.comp.lang.pascal
Titolo: [Half-OT] Matrici sparse e metodo dei tre vettori

Scusate per il topic non del tutto inerente al ng, ma mi son trovato a 
dover sviluppare questo algoritmo:
memorizzazione di matrici sparse tramite il metodo dei tre vettori (e 
procediemento inverso).
Qualcuno di voi lo conosce? o magari sa dirmi in rete dove reperire 
qualcosa che spieghi il tutto e magari faccia pure un abbozzo di pseudo-
codice?
Sperando in un vostro aiuto, vi ringrazio.
-- 
Kaioh - lurker

Il metodo dei tre vettori funziona così :
data una matrice[NxM] che può contenere elementi nulli, memorizzi gli
elementi in 3 vettori , riga, colonna, elemento di dimensione massima NxM.
l'algoritmo di memorizzazione è facile facile
j:=0;
for r:=1 to N do
  for c:=1 to M do
     if M[r,c]<>0 then (* ho messo 0 ma potrebbe essere qualsiasi valore
ritenutto nullo dal tuo programma *)
        begin
            j:=j+1;
           elem[j]:=M[r,c];
           riga[j]=r;
           colonna[j]=c;
        end;
in questo modo hai nell'array elementi tutti i valori non nulli  e negli
array riga colonna le posizioni nella matrice
quindi se elem[1]:=10; riga[1]=30; colonna[1]=1   sai che nella matrice alla
posizione[30,1] c'è elemento 100
per ricostruire la matrice effettui il procedimento inverso
for i:=1 to j do
   M[riga[j],colonna[j]]=elem[j]
Questo metodo non è conveniente per matrici di grosse dimensioni
Ciao ReDiCuori
------------------------------------------
pascal su IRC : #turbopascal
pascal sul web : 
www.pascallike.cjb.net
------------------------------------------
"Kaioh" <ka...@kaioh.ka> ha scritto nel messaggio
news:MPG.15873e3f...@news.libero.it...


grazie re di cuori hai fatto felice l'intero corso di programmazione della
federico II di napoli :-)

 ha scritto nel messaggio
news:P9bT6.2275$7F4....@news.infostrada.it...


Ops mi so confuso sarà che sono le 6.44 e devo correre alla FII
"ReDiCuori" <redicu...@NOSPAMlibero.it> ha scritto nel messaggio
news:EziT6.4180$7F4.1...@news.infostrada.it...


 posizione[30,1] c'è elemento 100
Come hai strutturato tu l'algoritmo tutti e tre i vettori avrebbero lo 
stesso numero di elementi (o altrimenti, se non è così, sono fuori! :))
Da quello che ricordavo io (lo conosco, ma non bene):
Il primo vettore conterrà tutti gli elementi non nulli della matrice.
Il secondo vettore conterrà gli indici di colonna dei suddetti elementi.
Per il terzo vettore, sorge il problema.
E' ovvio che serva ad individuare la riga originaria su cui giaceva 
l'elemento nella matrice.
Ricordo, però, che ha lunghezza minore ai precedenti, e che l'ultimo 
elemento rapprensentava, o il numero di righe + 1, o quello di colonne + 
1.
Pian, piano comincio a pensare che, detto N il numero di righe della 
matrice, il terzo vettore sia lungo N+1.
Le "i" celle da 1..N dovrebbero puntare al primo elemento sulla riga 
"iesima"
es di terzo vettore generato da matrice di tre righe: 
[1, 3, 5] (per adesso ometto l'(N+1)esima cella)
l'elemento 1 del "vettore 1" è il primo elemento sulla riga 1
l'elemento 3 del "vettore 1" è il primo elemento sulla riga 2
l'elemento 5 del "vettore 1" è il primo elemento sulla riga 3
Pero' non sono ancora sicuro, visto che non mi spiego il contenuto 
dell'(N+1)esima cella del "vettore 3" (sia essa il numero di righe o di 
colonne incrementato di un'unità)
Inoltre, in questo modo, il primo elemento del "vettore 3" sarebbe sempre 
1.
Se qualcun altro sa, è invitato a intromettersi!:)
--
Kaioh

 l'elemento 5 del "vettore 1" è il primo elemento sulla riga 3
Primo elemento non nullo

La posto perchč avevo visto che interessava (almeno cosě mi pareva ;))
------------------------------------------------------------------------
Il primo vettore (A)contiene tutti gli elementi non nulli
Il secondo (J) gli indici di colonna degli elementi non nulli
Il terzo vettore (I):
Allora la sua lunghezza č pari al numero di righe+1, e l'elemento i-esimo
rappresenta l'indice dell'elemento del primo vettore che a sua volta 
risulta essere il primo elemento non nullo della i-esima riga.
L'ultimo elemento č la lunghezza del primo vettore +1.
Es:
Sia data tale matrice:
1    0    0    0    5
0    0    2    0    9
7    8    0    0    0
0    3    0    0    0
A=(1,5,2,9,7,8,3) 
J=(1,5,3,5,1,2,2) 
[spiegazione approfondita terzo vettore]
nella 1° riga il primo elemento non nullo č 1=A[1]
nella 2° riga il primo elemento non nullo č 2=A[3]
nella 3° riga il primo elemento non nullo č 7=A[5]
nella 4° riga il primo elemento non nullo č 3=A[7]
A ha lunghezza 7 (che č anche il numero di elementi non nulli) + 1=8
Allora costruiamo il terzo vettore:
I=(1,3,5,7,8).
------------------------------------------------------------------------

 A ha lunghezza 7 (che è anche il numero di elementi non nulli) + 1=8
