 |
|
 |
| Precedente :: Successivo |
Autore |
Messaggio |
|
|
garfa
Bravino
Registrato: 09/06/09 15:48
Messaggi: 14
|
 Inviato: Mar Giu 09, 2009 3:59 pm Oggetto: Progetto in C per risoluzione di un Hitori (simile al sudoku |
|
|
Ciao ragazzi!!!!!! mi servirebbe una mano per capire come poter memorizzare una griglia di numeri esempio:
1 1 1 2 3
5 4 2 3 1
1 5 3 4 3
2 4 4 1 4
1 2 1 5 4
in questo caso di dimensione 5x5 , ma può essere anche più grande!!!
scopo del gioco è annerire le caselle in modo che ogni numero compaia una volta per ogni riga e per ogni colonna, 2 caselle nere possono avere al amssimo un vertice in comune, le caselle non annerite devono formare una sola componente connessa verticalmente e orizzontalmente ovvero non devono esserci gruppi di caselle isolate.
Qiundi soluzione:
0 1 0 2 0
5 4 2 3 1
1 5 0 4 3 soluzione ottenuta tramite implementazione delle tecniche
2 0 4 1 0 che sono da implementare!!!
0 2 1 5 4
Dovrei farlo tramite una struttura dati tipo albero, albero red-black, grafo, come faccio a passare i valori letti in input e memorizzarli nell'albero red-black????? |
|
Top |
|
 |
cali1981
Site Admin
Registrato: 16/01/06 22:01
Messaggi: 836
|
| Inviato: Mer Giu 10, 2009 8:27 am Oggetto: |
|
|
Ciao, innanzitutto hai già implementato (o trovato implementato) l'albero red-black? Poi, dai valori originali, come fai a salvarli in un albero binario, mantenendo la posizione?
_________________
Visita anche il sito Agriturismo Umbria per maggiori informazioni sull'Umbria!
Realizzazione siti web e applicazioni ASp.NEt, C/C++, C# |
|
Top |
|
|
garfa
Bravino
Registrato: 09/06/09 15:48
Messaggi: 14
|
| Inviato: Mer Giu 10, 2009 11:54 am Oggetto: |
|
|
I valori della griglia li leggo dallo standard input (stdin) e mantengo la posizione attraverso un indice,ogni casella è rappresentata da una coppia (i,j), dove i>=0 e j<=n-1
la struttura per l'albero red-black è una cosa del genere :
| Codice: |
/***********************
* rbtree.h *
***********************/
#include <stdio.h>
#include <stdlib.h>
typedef int key;
typedef enum { red, black } color;
struct rbnode {
key v;
color c;
struct rbnode *left, *right, *up;
};
typedef struct rbnode rbnode;
typedef struct {
rbnode *root, *nil;
} rbtree;
rbtree *createrbtree(void);
void inorder(rbtree *p, void (*op)(rbnode *));
rbnode *search(rbtree *p, key k);
rbnode *treemin(rbtree *p);
rbnode *treemax(rbtree *p);
rbnode *treesucc(rbtree *r, rbnode *q);
rbnode *treepred(rbtree *r, rbnode *q);
void rbinsert(rbtree *p, key k);
void rbdelete(rbtree *r, rbnode *q);
/* end of file rbtree.h */
/*************************
* rbtree.c *
*************************/
#include "rbtree.h"
rbtree *createrbtree(void)
{
rbtree *t = malloc(sizeof(rbtree));
if(!t) {
fprintf(stderr,"Errore di allocazione A\n");
exit(-1);
}
if(!(t->root = malloc(sizeof(rbnode)))) {
fprintf(stderr,"Errore di allocazione B\n");
exit(-2);
}
t->nil = t->root;
t->nil->left = t->nil->right = t->nil->up = t->nil;
t->nil->c = black;
return t;
}
void inord(rbnode *p, rbnode *nil, void (*op)(rbnode *))
{
if(p != nil) {
inord(p->left,nil,op);
(*op)(p);
inord(p->right,nil,op);
}
}
void inorder(rbtree *p, void (*op)(rbnode *))
{
inord(p->root, p->nil, op);
}
rbnode *search(rbtree *r, key k)
{
rbnode *p = r->root;
while(p != r->nil && k != p->v)
p = k < p->v ? p->left : p->right;
return p == r->nil ? NULL : p;
}
rbnode *rbtmin(rbnode *p, rbnode *nil)
{
for(;p->left != nil;p = p->left);
return p;
}
rbnode *rbtmax(rbnode *p, rbnode *nil)
{
for(;p->right != nil;p = p->right);
return p;
}
rbnode *treemin(rbtree *r)
{
return rbtmin(r->root,r->nil);
}
rbnode *treemax(rbtree *r)
{
return rbtmax(r->root,r->nil);
}
rbnode *treesucc(rbtree *r, rbnode *q)
{
rbnode *qq;
if(q->right != r->nil)
return rbtmin(q->right,r->nil);
qq = q->up;
while(qq != r->nil && q == qq->right) {
q = qq;
qq = qq->up;
}
return qq == r->nil ? NULL : qq;
}
rbnode *treepred(rbtree *r, rbnode *q)
{
rbnode *qq;
if(q->left != r->nil)
return rbtmax(q->left,r->nil);
qq = q->up;
while(qq != r->nil && q == qq->left) {
q = qq;
qq = qq->up;
}
return qq == r->nil ? NULL : qq;
}
void leftrotate(rbtree *r, rbnode *x)
{
rbnode *y = x->right;
x->right = y->left;
if(y->left != r->nil)
y->left->up = x;
y->up = x->up;
if(x->up == r->nil)
r->root = y;
else
if(x == x->up->left)
y->up->left = y;
else
y->up->right = y;
y->left = x;
x->up = y;
}
void rightrotate(rbtree *r, rbnode *x)
{
rbnode *y = x->left;
x->left = y->right;
if(y->right != r->nil)
y->right->up = x;
y->up = x->up;
if(x->up == r->nil)
r->root = y;
else
if(x == x->up->right)
y->up->right = y;
else
y->up->left = y;
y->right = x;
x->up = y;
}
rbnode *simpleinsert(rbtree *tree, key k)
{
rbnode *q = malloc(sizeof(rbnode));
rbnode *r = tree->root;
rbnode *s = tree->nil;
if(!q) {
fprintf(stderr,"Errore di allocazione C\n");
exit(-4);
}
q->v = k;
q->left = q->right = tree->nil;
q->c = red;
while(r != tree->nil) {
s = r;
r = k < r->v ? r->left : r->right;
}
q->up = s;
if(s == tree->nil)
return tree->root = q;
if(k < s->v)
s->left = q;
else
s->right = q;
return q;
}
void rbinsert(rbtree *tree, key k)
{
rbnode *x = simpleinsert(tree, k);
rbnode *y;
while(x != tree->root && x->up->c == red) {
if(x->up == x->up->up->left) { /* caso L */
y = x->up->up->right;
if(y->c == red) {
x->up->c = black; /* caso 1L */
y->c = black; /* caso 1L */
x->up->up->c = red; /* caso 1L */
x = x->up->up; /* caso 1L */
} else {
if(x == x->up->right) /* caso 2L */
leftrotate(tree,x = x->up); /* caso 2L */
x->up->c = black; /* caso 3L */
x->up->up->c = red; /* caso 3L */
rightrotate(tree,x->up->up); /* caso 3L */
}
} else { /* caso R */
y = x->up->up->left;
if(y->c == red) {
x->up->c = black; /* caso 1R */
y->c = black; /* caso 1R */
x->up->up->c = red; /* caso 1R */
x = x->up->up; /* caso 1R */
} else {
if(x == x->up->left) /* caso 2R */
rightrotate(tree,x = x->up); /* caso 2R */
x->up->c = black; /* caso 3R */
x->up->up->c = red; /* caso 3R */
leftrotate(tree,x->up->up); /* caso 3R */
}
}
}
tree->root->c = black;
}
void fixup(rbtree *tree, rbnode *x)
{
rbnode *w;
while(x != tree->root && x->c == black) {
if(x == x->up->left) { /* caso L */
if((w = x->up->right)->c == red) {
w->c = black; /* caso 1L */
x->up->c = red; /* caso 1L */
leftrotate(tree,x->up); /* caso 1L */
w = x->up->right; /* caso 1L */
}
if(w->left->c == black && w->right->c == black) {
w->c = red; /* caso 2L */
x = x->up; /* caso 2L */
} else {
if(w->right->c == black) {
w->left->c = black; /* caso 3L */
w->c = red; /* caso 3L */
rightrotate(tree,w); /* caso 3L */
w = x->up->right; /* caso 3L */
}
w->c = x->up->c; /* caso 4L */
x->up->c = black; /* caso 4L */
w->right->c = black; /* caso 4L */
leftrotate(tree,x->up); /* caso 4L */
x = tree->root; /* caso 4L */
}
} else { /* caso R */
if((w = x->up->left)->c == red) {
w->c = black; /* caso 1R */
x->up->c = red; /* caso 1R */
rightrotate(tree,x->up); /* caso 1R */
w = x->up->left; /* caso 1R */
}
if(w->right->c == black && w->left->c == black) {
w->c = red; /* caso 2R */
x = x->up; /* caso 2R */
} else {
if(w->left->c == black) {
w->right->c = black; /* caso 3R */
w->c = red; /* caso 3R */
leftrotate(tree,w); /* caso 3R */
w = x->up->left; /* caso 3R */
}
w->c = x->up->c; /* caso 4R */
x->up->c = black; /* caso 4R */
w->left->c = black; /* caso 4R */
rightrotate(tree,x->up); /* caso 4R */
x = tree->root; /* caso 4R */
}
}
}
x->c = black;
}
void rbdelete(rbtree *tree, rbnode *q)
{
rbnode *r, *s;
if(q->left == tree->nil || q->right == tree->nil)
r = q;
else
r = treesucc(tree,q);
s = r->left != tree->nil ? r->left : r->right;
s->up = r->up;
if(r->up == tree->nil)
tree->root = s;
else
if(r == r->up->left)
r->up->left = s;
else
r->up->right = s;
if(r != q)
q->v = r->v;
if(r->c == black)
fixup(tree, s);
free(r);
}
|
|
|
Top |
|
|
cali1981
Site Admin
Registrato: 16/01/06 22:01
Messaggi: 836
|
|
Top |
|
|
garfa
Bravino
Registrato: 09/06/09 15:48
Messaggi: 14
|
| Inviato: Mer Giu 10, 2009 1:56 pm Oggetto: |
|
|
Se metto nella struttura della cella sia le coordinate che il numero?!!
| Codice: |
typedef struct rbnode{
int numero; //numero reale della casella
int x,y; // coordinate i,j
color colore_nodo;
struct cella *left, *right, *up;
}rbnode;
|
|
|
Top |
|
|
cali1981
Site Admin
Registrato: 16/01/06 22:01
Messaggi: 836
|
|
Top |
|
|
garfa
Bravino
Registrato: 09/06/09 15:48
Messaggi: 14
|
| Inviato: Mer Giu 10, 2009 2:26 pm Oggetto: |
|
|
Non è che mi puoi dare una mano per la lettura dei numeri
devo metterli in una matrice, una lista o qualcosa del genere o li leggo e li inserisco nell'albero....come faccio a metterli nella struttura dell'albero???? |
|
Top |
|
|
cali1981
Site Admin
Registrato: 16/01/06 22:01
Messaggi: 836
|
| Inviato: Mer Giu 10, 2009 2:32 pm Oggetto: |
|
|
Il problema è il cin? Per la struttura, devi crearla e cambiare il typedef come ti dicevo, ma poi dovresti andare a controllare dentro ogni funzione quando usa k, oppure creare gli operatori < > = per la struttura.
_________________
Visita anche il sito Agriturismo Umbria per maggiori informazioni sull'Umbria!
Realizzazione siti web e applicazioni ASp.NEt, C/C++, C# |
|
Top |
|
|
garfa
Bravino
Registrato: 09/06/09 15:48
Messaggi: 14
|
| Inviato: Mer Giu 10, 2009 2:36 pm Oggetto: |
|
|
non ho capito questa domanda.........Il problema è il cin? |
|
Top |
|
|
cali1981
Site Admin
Registrato: 16/01/06 22:01
Messaggi: 836
|
|
Top |
|
|
garfa
Bravino
Registrato: 09/06/09 15:48
Messaggi: 14
|
| Inviato: Mer Giu 10, 2009 3:18 pm Oggetto: |
|
|
se mi aiuti su entrambi mi faresti un gran favore..
per leggere l'input dell'utente ho scritto
| Codice: |
//==============DATI GLOBALI================
int n; //Per la dimensione della matrice
int *A_p; //Per puntare la matrice
//===============DEFINIZIONI================
void leggi_griglia(int *a,int n) {
int i,j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
scanf("%d",&a[n*i+j]);
}
}
return;
}
int main(void)
{
int i,j;
printf("Dimensione griglia?\n");
scanf("%d",&n);
A_p =(int *) malloc (sizeof(int[n*n]));//Per allocare la memoria per la matrice
leggi_griglia(A_p,n);
return(0);
}
|
per poterli stampare come faccio? e vedere se salvi i dati i dati in modo giusto...non so se in questo modo posso metterli nell'albero poi!!! |
|
Top |
|
|
cali1981
Site Admin
Registrato: 16/01/06 22:01
Messaggi: 836
|
|
Top |
|
|
garfa
Bravino
Registrato: 09/06/09 15:48
Messaggi: 14
|
| Inviato: Mer Giu 10, 2009 3:31 pm Oggetto: |
|
|
così pero invece di stampare i valori inseriti , stampa dei numeri a 7 cifre che penso siano le locazioni di memoria!!!!!
perchè?!  |
|
Top |
|
|
cali1981
Site Admin
Registrato: 16/01/06 22:01
Messaggi: 836
|
|
Top |
|
|
garfa
Bravino
Registrato: 09/06/09 15:48
Messaggi: 14
|
| Inviato: Mer Giu 10, 2009 4:11 pm Oggetto: |
|
|
ok grazie!! per l'inserimento nell'albero rb hai qualche idea? provo a vedere se riesco a tirare fuori qualcosa!!! dovrò fare qualche funzione che mi crea ogni cella con i valori passati dalla matrice....  |
|
Top |
|
|
|
|
|
|
Non puoi inserire nuovi argomenti
Non puoi rispondere a nessun argomento
Non puoi modificare i tuoi messaggi
Non puoi cancellare i tuoi messaggi
Non puoi votare nei sondaggi
|
|
