Newsgroup: it.comp.lang.c++
Titolo: stack in VC++ 4 per w95

Ciao a tutti,
intanto grazie per i preziosi consigli dei giorni scorsi, vi prometto che
fra un po' non disturberò più con cose "scolastiche" per almeno un anno...
Come ultimo esercizio per l'esame di Fondamenti di Informatica 1, dovevo
realizzare il radix-sort come applicazione ricorsiva del bucket-sort. Le
stringhe da ordinare dovevano "pescare" i caratteri fra i primi 8
dell'alfabeto.
L'algoritmo che ho fatto funziona perfettamente con 5 stringhe di lungheza 3
caratteri pescati fra i primi 3, ma aumentando uno qualsiasi dei valori si
blocca, immagino per esaurimento dello stack.
Ho visto che di default, il VC++4 per W95 riserva 1Mb di stack, io ho
provato (da "Settings...") a metterlo al massimo, cioè 4Mb: francamente, non
mi sembra una quantità piccola, tuttavia il programma si blocca comunque!
Chi mi sa dire se posso aumentarlo ulteriormente "a mano" (tenendo conto che
dispongo al max di 24Mb di memoria fisica)?
Grazie - saluti :-)
Marco Zanon (
m.z...@usa.net
)
http://www.geocities.com/SiliconValley/Peaks/6455
(BUY CDS AT THE LOWEST PRICES through my site!!!
Zamorano fan page, free MIDI mailing list, Music db...)

blocca, immagino per esaurimento dello stack.
Ma quanta recursione c'e`...?!  Sospetto qualche "debordamento di
un indice di un array" che causa recursione infinita...
Alex

 wrote in message F6J66...@cadlab.it...

perché dici "recursione infinita"? Con 3 caratteri funziona...
Comunque, il listato è questo (eventualmente, il problema dovrebbe essere
solo in "bucket-sort", le stringhe mi sembrano proprio ok ora...).
Dimenticavo: LIST_S sono liste sequenziali (elemento e puntatore all'anello
successivo), anche quelle dovrebbero andare benone!
Ciao e grazie :-)
**** BEGIN CODICE ***
#include <fi1libl2.h>
#include <iostream.h>
#include <afxwin.h>
#include <afxext.h>
#define	CHARACTERS_NUMBER		3
#define	STRING_LENGTH			4
#define	MAX_STRINGS_NUMBER		20
CString generatecharacter(void)
{
	unsigned int	character=rand()*CHARACTERS_NUMBER/RAND_MAX+1;
	CString			c="";
	switch (character)
	{
	case 1:
		c="a";
		break;
	case 2:
		c="b";
		break;
	case 3:
		c="c";
		break;
	};
	return(c);
};
CString generatestring(void)
{
	CString			s="";
	for(unsigned int i=0;i<STRING_LENGTH;i++)
	{
		s+=generatecharacter();
	}
	return(s);
};
LIST_S bucket_sort(LIST_S l, unsigned int startchar)
{
	if (startchar==CHARACTERS_NUMBER+1) return(l);
	else
	{
		LIST_S	startletter[CHARACTERS_NUMBER];
		for (unsigned int j=0; j<CHARACTERS_NUMBER; j++)
			startletter[j]=NULL;
		// inserisce in startletter[i] tutte le parole il cui
		// startchar sia la (i+1)-esima lettera dell'alfabeto
		while (!(lss_null(l)))
		{
			CString	s=lss_car(l);
			unsigned int i=s.GetAt(startchar-1)-'a';
			lss_cons(s,&startletter[i]);
			l=lss_cdr(l);
		};
		LIST_S	reslist[CHARACTERS_NUMBER],
				res=NULL;
		for (j=0; j<CHARACTERS_NUMBER; j++)
		{
			// applicazione di bucket_sort alla sottolista
			reslist[j]=bucket_sort(startletter[j],startchar+1);
		};
		for (j=0; j<CHARACTERS_NUMBER; j++)
		{
			// creazione della lista di ritorno
			while (!(lss_null(reslist[j])))
			{
				CString r=lss_car(reslist[j]);
				reslist[j]=lss_cdr(reslist[j]);
				lss_cons(r,&res);
			};
		};
		return(res);
	};
};
LIST_S radix_sort(LIST_S l)
{
	return(bucket_sort(l,1)); // comincia ad ordinare dal primo carattere
};
int main(void)
{
	srand((unsigned)time(NULL));	// seme per i numeri casuali
	LIST_S	startlist=NULL,
			reslist=NULL;
	for (unsigned int j=0;j<MAX_STRINGS_NUMBER;j++)
		lss_cons(generatestring(),&startlist);
	cout << "*** RADIX-SORT ***" << "\n\n";
	// stampa delle liste
	cout << "Lista disordinata" << "\n";
	lss_print(startlist);
	reslist=radix_sort(startlist);
	cout << "\n";
	cout << "Lista ordinata" << "\n";
	lss_print(reslist);
	return(0);
};
*** END CODICE ***

successivo), anche quelle dovrebbero andare benone!
Ho esaminato un po' il codice e non ci vedo errori; ho quindi fatto un copy
and paste, aggeggiato le LIST_S in termini di std::list, sostituito le CString
con std::string, e il tutto funziona senza riempire lo stack con numeri assai
piu` grandi di quelli che tu riporti.  Le CString e` difficile che siano rotte (non
ricordo se c'era un bug nella specifica, antica versione di MFC che tu usi,
ma non mi pare), quindi non sarei tanto sicuro sulle LIST_S.  Comunque,
ecco il codice che funziona senza troppi problemi, praticamente pari pari
il tuo con le modifiche suddette (vabbe`, ammetto che ho tolto alcuni vezzi
che detesto, come le parentesi attorno al valore di ritorno, ma quelli sono
innocui:).
#include <iostream>
#include <list>
#include <string>
#include <time.h>
using namespace std;
#define CHARACTERS_NUMBER 6
#define STRING_LENGTH 8
#define MAX_STRINGS_NUMBER 20
char generatecharacter(void)
{
    unsigned int character=rand()*CHARACTERS_NUMBER/RAND_MAX;
    return 'a'+character;
};
string generatestring(void)
{
    string s;
    for(unsigned int i=0;i<STRING_LENGTH;i++)
    {
        s+=generatecharacter();
    }
    return s;
};
typedef list<string> LIST_S;
inline bool lss_null(const LIST_S& l) { return l.empty(); }
inline string lss_car(const LIST_S& l) { return l.front(); }
inline void lss_cdr(LIST_S &l) { l.pop_front(); }
inline void lss_cons(string s, LIST_S& l) { l.push_back(s); }
void lss_print(const LIST_S &l) {
    LIST_S::const_iterator it;
    for(it=l.begin(); it!=l.end(); ++it)
        cout << *it << '\n';
}
LIST_S bucket_sort(LIST_S l, unsigned int startchar)
{
    if (startchar==CHARACTERS_NUMBER+1) return(l);
    else
    {
        LIST_S startletter[CHARACTERS_NUMBER];
        // inserisce in startletter[i] tutte le parole il cui
        // startchar sia la (i+1)-esima lettera dell'alfabeto
        while (!(lss_null(l)))
        {
            string s=lss_car(l);
            unsigned int i=s[startchar-1]-'a';
            lss_cons(s,startletter[i]);
            lss_cdr(l);
        };
        LIST_S reslist[CHARACTERS_NUMBER],
            res;
        for (int j=0; j<CHARACTERS_NUMBER; j++)
        {
            // applicazione di bucket_sort alla sottolista
            reslist[j]=bucket_sort(startletter[j],startchar+1);
        };
        for (j=0; j<CHARACTERS_NUMBER; j++)
        {
            // creazione della lista di ritorno
            while (!(lss_null(reslist[j])))
            {
                string r=lss_car(reslist[j]);
                lss_cdr(reslist[j]);
                lss_cons(r,res);
            };
        };
        return res;
    }
};
LIST_S radix_sort(LIST_S l)
{
    return bucket_sort(l,1); // comincia ad ordinare dal primo carattere
};
int main(void)
{
    srand((unsigned)time(NULL)); // seme per i numeri casuali
    LIST_S startlist,reslist;
    for (unsigned int j=0;j<MAX_STRINGS_NUMBER;j++)
        lss_cons(generatestring(),startlist);
    cout << "*** RADIX-SORT ***" << "\n\n";
    // stampa delle liste
    cout << "Lista disordinata" << "\n";
    lss_print(startlist);
    reslist=radix_sort(startlist);
    cout << "\n";
    cout << "Lista ordinata" << "\n";
    lss_print(reslist);
    return 0;
};
Alex

 wrote in message F6L86...@cadlab.it...