[C] che struttura uso?

[diego86]

Buongiorno a tutti... dovrei implementare una struttura dati che mi permetta di ottenere una scacchiera rettangolare di dimensioni r × c dentro la quale posizionare delle pedine colorate numerate. Le operazioni che poi posso fare saranno di inserire nuove pedine o di eliminarne e di verificare se esiste un gruppo di pedine dello stesso colore che sono adiacenti.
A questo punto io utilizzerei una lista che permette di salvare dentro ogni oggetto la sua posizione, il colore e il suo valore.
Il problema è che poi devo riuscire a risalire a queste pedine in base alla colonna in cui sono inserite, perchè devo poterle spostare da una colonna all'altra ed eliminarle solo se appartengono a una determinata colonna.
Questo sarebbe ancora fattibile con una lista, ma dovendola scorrere tutta ogni volta, mi sembra poco efficace come metodo..
Voi cosa consigliate? Mi conviene usare più matrici? Grazie..

[amedeoviscido]

In C puro io farei una matrice di puntatori a struttura, secondo me è la cosa più naturale che si possa fare!

PS Modifica il titolo della discussione, c dev'essere scritto fra parentesi quadre [C]

[diego86]

come faccio a editare il titolo?

poi la matrice di puntatori dovrebbe puntare alle singole pedine?
perchè la dimensione della scacchiera non è nota a priori ma solo run-time.. inoltre se l'utente vuole inserire una pedina in una qualsiasi posizione deve poterlo fare

[ramarromarrone]

io ti consiglio una lista di liste..

struct pedina {
char *colore;
};
typedef struct pedina pedina;

struct asse_x {
int x;
pedina *p;
struct asse_x *next;
};
typedef struct asse_x asse_x;

struct asse_y {
int y;
asse_x *a;
struct asse_y *next;
};
typedef struct asse_y asse_y;

è meglio di una matrice perchè è una struttura dinamica e cresce al crescere dei dati in input senza spreco di memoria (al contrario della matrice)...per cercare una pedina in una coordinata (x1,y1) dovrai prima scorrere l'asse_y finchè y == y1 e poi scorrere l'asse_x relativo finchè x == x1.

[ramarromarrone]

la tua richiesta è molto simile al progetto di algoritmi e strutture dati dell'università di milano...

a seconda poi di quello ce effettivamente queste pedine colorate dovranno fare invece potresti optare per strutture dati più complesse.
per esempio se ti servirà trovare pedine di ugual colore vicine potresti decidere di creare diversi grafi, che contengono pedine dello stesso colore (è abbastanza semplice, ogni vlta che devi inserire una nuova pedina colorata selezioni tutti i grafi di quel colore e vedi se in uno di questi c'è una casella "vicina" a quella che devi inserire, se non c'è crei un altro grafo con la pedina)

se hai bisogno chiedi pure

[diego86]

ok...grazie mille...intanto mi installo il mio caro vecchio borland c che pensavo non mi sarebbe più servito....e invece...
poi ramarro posso contattarti se ho bisogno? da quanto ho capito sei un mio predecessore nella carriera scolastica

[ramarromarrone]

Originariamente inviato da diego86

ok...grazie mille...intanto mi installo il mio caro vecchio borland c che pensavo non mi sarebbe più servito....e invece...
poi ramarro posso contattarti se ho bisogno? da quanto ho capito sei un mio predecessore nella carriera scolastica

contattami pure quando vuoi
oggi pomeriggio non sarò connesso fino alle 17.30-18 circa quindi se lasci messaggi o post non ti potrò rispondere fino a quell'ora
ciao

PS:come compiler ti consiglio gcc e come editor ccy

[gugoXX]

Ciao.
Se la dimensione della scacchiera fosse fissa, e se non fosse sparsa, allora io userei il matricione, che ti permetterebbe di inserire, cancellare e calcolare
le adiacenze in poco piu' di O(1).
Se invece la dimensione fosse variabile e se il contenuto fosse sparso, al posto che una soluzione a liste io preferirei una soluzione ad hastable.
Una Hahtable di.. Hashtable.
Anche questo caso gli inserimenti, cancellazioni e calcolo delle adiacenze sarebbero in poco piu' di O(1).
Tale soluzione e' molto simile alla lista di liste, che se ordinata darebbe O(log N)*O(log N), e se invece non ordinata sarebbe O(N 2)

Ladifferenza tra le 2, a parte la complessita' realizzativa, sta appunto nella memoria occupata. Si puo' sicuramente calcolare un rapporto "CelleOccupate"/"CelleDellaScacchiera" oltre il quale conviene la prima al posto della seconda.

Ovviamente se e' un esercizio la prima soluzione e' troppo banale e verrebbe rifiutata se non debitamente argomentata (appunto la % di spazio occupato).
Per quanto riguarda la seconda che ritengo comunque elegante, se non devi/puoi farlo in C# posso postarti le 10 righe di codice che servirebbero.

[k0nt3]

se la grandezza è nota e di dimensioni ragionevoli senza dubbio userei una matrice (o semplicemente un array lungo r*c) di puntatori a pedine.
a meno che non stiamo parlando di una scacchiera 1000*1000.. in quel caso prenderei in considerazione una struttura più dinamica.
ad esempio se si utilizza una struttura dati come quella proposta da ramarromarrone è vero che si occupa memoria solo quando è necessario (ottimo nel caso di matrici sparse), ma è anche vero che se ne occupa il triplo per ogni cella (in pratica nel caso in cui più di 1/3 delle celle contiene una pedina è sconveniente), e che tutte le operazioni sulla scacchiera sono più complesse.

ps. per denotare il colore userei delle costanti

[diego86]

Originariamente inviato da gugoXX

Ciao.
Se la dimensione della scacchiera fosse fissa, e se non fosse sparsa, allora io userei il matricione, che ti permetterebbe di inserire, cancellare e calcolare
le adiacenze in poco piu' di O(1).
Se invece la dimensione fosse variabile e se il contenuto fosse sparso, al posto che una soluzione a liste io preferirei una soluzione ad hastable.
Una Hahtable di.. Hashtable.
Anche questo caso gli inserimenti, cancellazioni e calcolo delle adiacenze sarebbero in poco piu' di O(1).
Tale soluzione e' molto simile alla lista di liste, che se ordinata darebbe O(log N)*O(log N), e se invece non ordinata sarebbe O(N 2)

Ladifferenza tra le 2, a parte la complessita' realizzativa, sta appunto nella memoria occupata. Si puo' sicuramente calcolare un rapporto "CelleOccupate"/"CelleDellaScacchiera" oltre il quale conviene la prima al posto della seconda.

Ovviamente se e' un esercizio la prima soluzione e' troppo banale e verrebbe rifiutata se non debitamente argomentata (appunto la % di spazio occupato).
Per quanto riguarda la seconda che ritengo comunque elegante, se non devi/puoi farlo in C# posso postarti le 10 righe di codice che servirebbero.

Potrebbe essere un'ottima idea...se mi posti il codice mi faresti un grandissimo favore

[k0nt3]

una soluzione con la tabella di hash può essere la seguente (nella fattispecie si tratta di double hashing):

#include <stdio.h>
#include <stdlib.h>

#define MAX_PEDINE 20
#define NUM_ROWS 15
#define NUM_COLS 15

//#define DEBUG

typedef struct Pedina {
  int colore;
  int x, y;
} Pedina;

int hashFunction(int x, int y);
int probeFunction(int x, int y, int i);
int insertPedina(int x, int y, Pedina* ht[]);
void printScacchiera(Pedina* ht[]);

int main(int argc, char* argv[])
{
  Pedina* hashTable[MAX_PEDINE];

  int i=0;
  for(i; i<MAX_PEDINE; ++i)
    hashTable[i] = NULL;

  insertPedina(1, 1, hashTable);
  insertPedina(2, 2, hashTable);
  insertPedina(4, 4, hashTable);
  printScacchiera(hashTable);
  return EXIT_SUCCESS;
}

int hashFunction(int x, int y)
{
  return (x*NUM_ROWS + y*NUM_COLS)%MAX_PEDINE;
}

int probeFunction(int x, int y, int i)
{
  return (i*(2*x-y))%MAX_PEDINE;
}

int insertPedina(int x, int y, Pedina* ht[])
{
  Pedina* p = (Pedina*)malloc(sizeof(Pedina));
  p->x = x;
  p->y = y;
  int h = hashFunction(x, y);
  #ifdef DEBUG
    printf("hash: %d\n", h);
  #endif
  if(ht[h] == NULL)
  {
    ht[h] = p;
    return 0;
  }
  else
  {
    int i = 1;
    int j = 0;
    h = probeFunction(x, y, i);
    #ifdef DEBUG
      printf("probe(%d): %d\n", i, h);
    #endif
    while(ht[h] != NULL && j++ < MAX_PEDINE)
    {
      h = probeFunction(x, y, ++i);
      #ifdef DEBUG
	printf("probe(%d): %d\n", i, h);
      #endif
    }

    if(j > MAX_PEDINE)
      return -1;

    ht[h] = p;
    return i;
  }
}

void printScacchiera(Pedina* ht[])
{
  int i=0;
  for(i; i<MAX_PEDINE; ++i)
  {
    if(ht[i] != NULL)
      printf("pedina in (%d, %d)\n", ht[i]->x, ht[i]->y);
  }
}

ma secondo me ti complichi la vita e basta. IMHO la matrice rimane la scelta migliore se non stiamo parlando di una scacchiera immensa con pochissime pedine.
tra l'altro non c'è motivo di ottimizzare prima di aver riscontrato un qualsiasi problema prestazionale
un tale di nome Donald diceva: "Early optimisation is the root of all evil"

[diego86]

ho optato per la lista di liste...la hash table è troppo incasinata
mentre per quanto riguarda i grafi? come potrei fare?

[gugoXX]

Scusami, mi ero perso.

Come promesso, ecco un codice della Hashtable di Hashtable in C#.
So che devi farlo in C, e come avrai capito in C e' decisamente piu' complesso.

public class Scacchiera
    {
        private Dictionary<int, Dictionary<int, Color>> Matrix = null;
        public Scacchiera()
        {
            Matrix = new Dictionary<int, Dictionary<int, Color>>();
        }

        public Color GetColor(int x, int y)
        {
            Color ret=Color.Empty;
            if (Matrix.ContainsKey(y))
            {
                if (Matrix[y].ContainsKey(x))
                {
                    ret = Matrix[y][x];
                }
            }
            return ret;
        }

        public void SetColor(int x, int y, Color col)
        {
            Dictionary<int,Color> riga=null;
            if (!Matrix.ContainsKey(y))
            {
                Matrix[y] = riga = new Dictionary<int, Color>();
            }
            riga[x] = col;
        }
    }

Il codice non e' ottimizzato, ma apposta per lasciarlo leggibile
In pratica, una volta instanziata la matrice, puoi accedervi con i semplici metodi GetColor e SetColor.
Da li' in poi, se devi cercare le adiacenze dirette sono 4 (o 8) ricerche.
se devi cercare le adiacenze estese dovrebbe essere possibile con una semplice funzione ricorsiva.
Come detto, sia la get che la set di questa classe sono risolte in poco piu' di O(1)

[diego86]

ho usato questa struttura...

typedef struct scacchiera{
int x;
int y;
int valore biglia;
char * colore biglia;
struct scacchiera *prossx;
struct scacchiera *prossy;
}

l'idea era di ottenere una specie di matrice dinamica, in modo da saltare le caselle vuote e di occupare solo lo spazio dove sono presenti delle pedine. Però mi sto accorgendo che già l'inserimento delle pedine è complicatissimo, bisogna fare un mucchio di controlli e se vado a inserire una nuova pedina è difficilissimo andare a collegarla al resto delle altre pedine (collegandola ovviamente alle pedine della stessa riga e della stessa colonna). Allora poichè questa struttura è anche visibile come un albero (puntatore sinistro figlio sinistro con x maggiore del padre) (puntatore destro figlio destro con y maggiore del padre) è possibile sfruttare questa visione per ottenere un inserimento più efficace?