Newsgroup: it.comp.lang.c
Titolo: Ordine alfabetico delle lettere in una stringa

Dunque, ho codesto problema:
ho una stringa alfanumerica _senza_caratteri_ripetuti di lunghezza NON
prefissata, un array di int di lunghezza uguale a quella della stringa.
Ho bisogno di memorizzare nell'array le posizioni dei caratteri della
stringa in ordine crescente. Mi spiego meglio con un esempio:
char stringa[] = "pluto"
int posizioni[5] (questa verra' ovviamente allocata in base alla 		 
dimensione della stringa)
il risultato della funzione che cerco deve essere quindi:
posizioni[0] = 1  (ossia l)
posizioni[1] = 4  (  "   o)
posizioni[2] = 0  (  "   p)
posizioni[3] = 3  (  "   t)
posizioni[4] = 2  (  "   u)
L'unica soluzione che mi e' venuta in mente e' di confrontare ogni
carattere con tutti gli altri e vedere quanti sono minori di quello che
prendo in considerazione, ma cosi' facendo ho una complessita' di
O(n^2), che mi fa un po' schifo ;-), anche se cmq non lavorerei su piu'
di 26*2+10=62 caratteri, facciamo magari un centinaio aggiungendo
caratteri di punteggiatura e simili.
Nessuno ha in mente qualcosa di meglio, vale ha dire con complessita'
O(n*log n)?
Gia' che si sono, un'altra domanda, di tipo diverso: in un array
bi-dimensionale, posso identificare una intera riga usando solo il primo
indice, es:
int buffer[j][k];
la i-esima riga e' buffer[i] ed ha dimensione k*sizeof(int)
se volessi invece indicare una colonna come potrei fare?
buffer[][n]  indica la n-esima colonna ed ha dimensione j oppure e' una
             stupidata frutto del mio neurone zoppo?!?
Grazie per la pazienza e il tempo concessomi, e scusate la lunghezza del
post, ma il problema mi assilla da qualche giorno...
-- 
 Ciao, Luca.
 Reply to 
luca....@tiscalinet.it

              stupidata frutto del mio neurone zoppo?!?
Non e' una stupidata, ma gli elementi non sono contigui.
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Univ. of Padova, Dept. of Physics - Padova, Italy            
lor...@pd.infn.it

Bianco wrote:
** 
** Dunque, ho codesto problema:
** ho una stringa alfanumerica _senza_caratteri_ripetuti di lunghezza
NON
** prefissata, un array di int di lunghezza uguale a quella della
stringa.
** Ho bisogno di memorizzare nell'array le posizioni dei caratteri della
** stringa in ordine crescente. Mi spiego meglio con un esempio:
** 
** char stringa[] = "pluto"
** int posizioni[5] (questa verra' ovviamente allocata in base alla
** dimensione della stringa)
** 
** il risultato della funzione che cerco deve essere quindi:
** 
** posizioni[0] = 1  (ossia l)
** posizioni[1] = 4  (  "   o)
** posizioni[2] = 0  (  "   p)
** posizioni[3] = 3  (  "   t)
** posizioni[4] = 2  (  "   u)
** 
** L'unica soluzione che mi e' venuta in mente e' di confrontare ogni
** carattere con tutti gli altri e vedere quanti sono minori di quello
che
** prendo in considerazione, ma cosi' facendo ho una complessita' di
** O(n^2), che mi fa un po' schifo ;-), anche se cmq non lavorerei su
piu'
** di 26*2+10=62 caratteri, facciamo magari un centinaio aggiungendo
** caratteri di punteggiatura e simili.
** Nessuno ha in mente qualcosa di meglio, vale ha dire con complessita'
** O(n*log n)?
** 
** Gia' che si sono, un'altra domanda, di tipo diverso: in un array
** bi-dimensionale, posso identificare una intera riga usando solo il
primo
** indice, es:
** 
** int buffer[j][k];
** 
** la i-esima riga e' buffer[i] ed ha dimensione k*sizeof(int)
** 
** se volessi invece indicare una colonna come potrei fare?
** 
** buffer[][n]  indica la n-esima colonna ed ha dimensione j oppure e'
una
**              stupidata frutto del mio neurone zoppo?!?
** 
** Grazie per la pazienza e il tempo concessomi, e scusate la lunghezza
del
** post, ma il problema mi assilla da qualche giorno...
** --
** 
**  Ciao, Luca.
** 
**  Reply to 
luca....@tiscalinet.it
**
A parte le soluzioni scolastiche come quiksort, mergesort, heapsort o
alberi,
Partendo dalle considerazioni che hai fatto sulla UNICITA' di ogni
carattere
nella stringa e la LIMITATEZZA della cardinalita' del carattere, prova a
sviluppare un metodo che fa uso del carattere come indice di un array
lungo
quanto l' alfabeto che usi (spero non maggiore di 256). Potresti
sviluppare
un metodo di costo anche migliore di quello sperato considerando
stringhe
medio-lunghe. per stringhe corte un algoritmo di costo logaritmico non
si
apprezza. Del resto con la premessa fatta una stringa non puo' essere
piu'
lunga dell' alfabeto senza ripetere un carattere.
Il costo che puoi ottenere e' minore di
LUNGHEZZAALFABETO+LUNGHEZZASTRINGA,
non necessariamente migliore di brutesort, solo per stringhe lunghe,
cioe'
per quelle per cui n^2 > LUNGHEZZAALFABETO
(Ma a cosa puo' servire?)
P.S. buffer[][n] per me non puo esistere, o comunque non indica una
     colonna. Prova ad immaginare: la memoria si indirizza usualmente
     con una dimensione e l' effetto 2, 3,..n D si ottiene con metodi di
     accesso base + spostamento. se le linee sono memorizzate in modo
     continuo, per forsa le colonne sono memorizzate in modo
discontinuo:
 
     linea1
     linea2
     linea3
     linea4
  linea1linea2linea3linea4
    ^     ^     ^     ^  la terza colonna, dove sono le 'n'
ciao.

             stupidata frutto del mio neurone zoppo?!?
Il tuo neurone va proprio sostituito, tuttavia puoi estrarre la
colonna, riscrivendola in un vettore.
#include <stdio.h>
main()
{
    int mat[3][3] =
    {   { 3, 2, 1 },
        { 1, 5, 6 },
        { 8, 4, 3 } } ;
    int vet[3] ;
    int i, j = 1 ;
    for ( i = 0 ; i < 3 ; i++ )
        vet [i] = mat [i][j] ;
}
--
Andrea Laforgia        (
andrea_...@bigfoot.com
)

 colonna, riscrivendola in un vettore.
[...]
Si', a questo ci ero arrivato anch'io, il fatto e' che non sapevo se
potevo usare una notazione come quella che avevo indicato (evidentemente
no) per riferirmi ad una colonna, come si fa con le righe. L'unico modo
per riferirsi ad una colonna di un array a 2 dimensioni e' quindi
ricopiare un elemento alla volta di ogni riga appartenente a quella
colonna in un altro vettore e usare questo vettore :-(


La libreria dove è implementato il QuickSort è standard ?
--
________________________________
Togliete NoSpaM per rispondermi
bye Brain

no) per riferirmi ad una colonna, come si fa con le righe.
No, non si puo'.
Immagina, tra l'altro, che l'array sia definito come :
int *array[10] ;
anche in questo caso si tratta di array bidimensionale, ma si perde la
struttura reale righe x colonne come entita' contigue in memoria.
--
Andrea Laforgia        (
andrea_...@bigfoot.com
)

 wrote:
B>La libreria dove è implementato il QuickSort è standard ?
[root@fokhouse /root]# man qsort | col -b | grep -A 1 ^CONFORMING
CONFORMING TO
       SVID 3, POSIX, BSD 4.3, ISO 9899
[root@fokhouse /root]#
Ciao ciao,
Andrea
-- 
"...Unix, MS-DOS, and Windows NT (also known as the Good, the Bad, and 
 the Ugly)."
(by Matt Welsh)