[C/C++]Metodo alternativo per ordinamento alfabetico

[MItaly]

Originariamente inviato da Marco1995
Allora non riesco a capire l'utilità delle liste(concatenate semplici),in programmi che non fanno largo uso di risorse...

Sono comode se devi fare tanti inserimenti "a metà" del contenitore, specie se stai lavorando su un tipo di memoria lenta, o comunque in cui spostare tutti gli elementi è lento o complicato; spesso si usano liste concatenate semplici all'interno di strutture dati salvate su disco (posso aggiungere un record in fondo al file e modificare un paio di puntatori invece di riscrivere tutto da capo). Si fanno poi spesso strutture dati ibride, che sfruttano il "meglio dei due mondi" - un caso classico è una lista di array, ma si possono fare cose più raffinate, come usare una lista linkata per "aggiungere" un certo ordinamento ad una hashtable; in ogni caso, qui trovi una buona panoramica.

Mentre le liste "doppie" se non erro si usano vantaggiosamente per gli alberi binari . .

Be', se sono alberi non sono liste... o meglio, la struttura dati che rappresenta un nodo di albero può essere la stessa di una usata per una lista doppiamente concatenata, ma li usi in maniera diversa.

[Kaamos]

Originariamente inviato da Marco1995
Allora non riesco a capire l'utilità delle liste(concatenate semplici),in programmi che non fanno largo uso di risorse...

Mentre le liste "doppie" se non erro si usano vantaggiosamente per gli alberi binari . .

Per esempio una lista concatenata ti permette di inserire un nuovo elemento sempre in tempo costante, mentre con un array dinamico potrebbe essere necessario riallocare l'array copiando tutti gli elementi; anche la rimozione di un elemento (una volta trovato) risulta costante in una lista concatenata, mentre in un array potresti dover spostare di una posizione tutti gli elementi... dipende tutto dalle proprie necessità.

Riguardo gli alberi, non si tratta esattamente di liste concatenate ma sì, è una cosa simile, di solito si tratta sempre di rappresentazioni collegate, con puntatori insomma.

EDIT: azz anticipato, ho pure guardato prima di postare

[shodan]

Per chi interessa, qui c'è un bel articolo sul tema:
http://www.baptiste-wicht.com/2012/1...ector-vs-list/

[MItaly]

Anche il seguito è interessante:
http://www.baptiste-wicht.com/2012/1...or-list-deque/

e tra l'altro ci ricorda della deque, che è un'ottima struttura dati (di fatto in genere è implementata concettualmente come una lista di vettori) ma per qualche motivo viene sempre ignorata.

[Marco1995]

Grazie delle risposte...come sempre velocissimi.

Finalmente sono riuscito a comprendere i pro e i contro dell'una e dell'altra struttura..ad ogni modo adesso guardo tutti i riferimenti che mi avete dato che saranno sicuramente interessanti

[Marco1995]

Comunque tornando al problema..non so perchè ma alcuni elementi non mi si aggiungono all'intern della lista (mentre altri che dovrebbero stare in prima e in ultima posizione non ci stanno).
Questo è il codice

#include <iostream>
#include <fstream>
#include <string.h>
#include <malloc.h>
using namespace std;
struct nome {
              char *p;
              nome* succ;
};
typedef nome Tnome;
Tnome* CreaLista();
void Inizializza(char array[],int dim);
void Inserisci(Tnome* &lista,char buffer[]);
void StampaLista(Tnome* lista);
void OrdinaLista(Tnome* &lista);
void Scambia(char* str1[],char* str2[]);

int main()
{
    int prova=0;

    char buffer[100];
    char c;
    int contavirgolette = 0;
    int k=0;
    Tnome *nomipropri;
    ifstream testo;
    testo.open("prova.txt",ios::in);
    nomipropri = CreaLista();
    while(!testo.eof())
    {
        while(contavirgolette<2)
        {
           c = testo.get();
             if (c!='"')
                buffer[k++] = c;
             else contavirgolette++;
        }
        buffer[k]=0;
        k = 0;
           prova++;
           contavirgolette = 0;

            Inserisci(nomipropri,buffer);
            Inizializza(buffer,100);
            c = testo.get();


        }
    testo.close();
    StampaLista(nomipropri);



}
Tnome* CreaLista()
{
    return NULL;
}
void Inserisci(Tnome* &lista,char buffer[])
{
    int i;
    Tnome *supporto;

    supporto = (Tnome*) calloc(1,sizeof(Tnome));

    supporto->succ=lista;
    supporto->p = (char*)calloc(strlen(buffer)+1,sizeof(char));

    for(i=0;buffer[i]!='\0';i++)
       supporto->p[i] = buffer[i];
    supporto->p[i] = 0;
    lista=supporto;

}
void Inizializza(char array[],int dim)
{
    int i;
    for(i=0;i<dim;i++)
    array[i]=0;
}
void StampaLista(Tnome* lista)
{
    while(lista!=NULL)
    {
       cout << lista->p << endl;
       lista = lista->succ;
    }
}

Mentre il file di testo è strutturato in questa maniera:

"MARY","PATRICIA","LINDA","BARBARA","ELIZABETH","JENNIFER","MARIA","SUSAN","..."
"EDITH","KIM","SHERRY","SYLVIA","JOSEPHINE","THELMA","SHANNON","...",
"...",
"...",
etc...

[Marco1995]

UP