avl-cvs Mailing List for avl (Page 3)
Brought to you by:
hetfield666,
jah2003
Menu
▾
▴
avl-cvs — CVS Commits
You can subscribe to this list here.
| 2004 |
Jan
|
Feb
|
Mar
|
Apr
|
May
(2) |
Jun
(15) |
Jul
(16) |
Aug
(5) |
Sep
(65) |
Oct
|
Nov
|
Dec
|
|---|
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-07 11:53:24
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv6933 Modified Files: avl.cpp bst.cpp Log Message: Index: bst.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/bst.cpp,v retrieving revision 1.11 retrieving revision 1.12 diff -C2 -d -r1.11 -r1.12 *** bst.cpp 6 Sep 2004 14:12:06 -0000 1.11 --- bst.cpp 7 Sep 2004 11:53:10 -0000 1.12 *************** *** 180,187 **** { if ( key == aux1->getValue() ) - { - //printf("The number -> %d is already in the Binary Search Tree\n",key); return; // se il valore si trova già nell'albero si esce ! } aux2 = aux1; //aux2 mantiene il puntatore al nodo al quale si deve appendere il nuovo nodo if ( key < aux1->getValue() ) --- 180,185 ---- { if ( key == aux1->getValue() ) return; // se il valore si trova già nell'albero si esce ! aux2 = aux1; //aux2 mantiene il puntatore al nodo al quale si deve appendere il nuovo nodo if ( key < aux1->getValue() ) *************** *** 192,198 **** // viene istanziato il nuovo nodo e gli viene assegnato key come valore e aux2 come genitore ! aux1 = new Bst; aux1->setParent( aux2 ); ! aux1->setValue( key ); // il nuovo nodo viene appeso a sinistra o a destra di aux2 in base al suo valore --- 190,196 ---- // viene istanziato il nuovo nodo e gli viene assegnato key come valore e aux2 come genitore ! aux1 = new Bst( key ); aux1->setParent( aux2 ); ! // aux1->setValue( key ); // il nuovo nodo viene appeso a sinistra o a destra di aux2 in base al suo valore Index: avl.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avl.cpp,v retrieving revision 1.12 retrieving revision 1.13 diff -C2 -d -r1.12 -r1.13 *** avl.cpp 7 Sep 2004 10:40:17 -0000 1.12 --- avl.cpp 7 Sep 2004 11:53:10 -0000 1.13 *************** *** 29,36 **** for (int i=0;i<1500;i++) { ! bst->insert(i); } } --- 29,37 ---- for (int i=0;i<1500;i++) { ! bst->insert(i); } + } *************** *** 183,187 **** printf("Insert the number of changements you want to do on the tree\n"); scanf("%d",&upperbound); - if (choice==0) { printf("Processing AVL, wait\n"); --- 184,187 ---- *************** *** 216,220 **** GtkWidget *label=NULL; //Test *a=new Test(); ! p(); gtk_init (&argc, &argv); p(); --- 216,220 ---- GtkWidget *label=NULL; //Test *a=new Test(); ! //p(); gtk_init (&argc, &argv); p(); |
|
From: Patrizio B. <het...@us...> - 2004-09-07 10:40:32
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv27121 Modified Files: Makefile avl.cpp test.cpp Log Message: new gtk gui. NOT WORKING! Index: avl.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avl.cpp,v retrieving revision 1.11 retrieving revision 1.12 diff -C2 -d -r1.11 -r1.12 *** avl.cpp 6 Sep 2004 14:12:06 -0000 1.11 --- avl.cpp 7 Sep 2004 10:40:17 -0000 1.12 *************** *** 24,27 **** --- 24,170 ---- using namespace std; + void p(){ + Bst* bst=new Bst(); + + + for (int i=0;i<1500;i++) { + + bst->insert(i); + } + + } + + + int choice=0; + int base_tree=20; + int upperbound=2; + Test *prova=NULL; + Avlt* aux_avl=NULL; + Bst* aux_bst=NULL; + + #ifdef GUI + + GtkWidget *node_list=NULL; + GtkWidget *vpaned1=NULL; + GtkWidget *spinbutton1=NULL; + GtkWidget *spinbutton2=NULL; + + void bst_select() { + choice=1; + } + + void avl_select() { + choice=0; + } + + void comparation_select() { + choice=2; + } + void start() { + + //Test *prova; + //prova= new Test(); + //Avlt* aux_avl=NULL; + //Bst* aux_bst=NULL; + + base_tree=gtk_spin_button_get_value_as_int(GTK_SPIN_BUTTON(spinbutton1)); + upperbound=gtk_spin_button_get_value_as_int(GTK_SPIN_BUTTON(spinbutton2)); + printf("%d %d %d\n", choice,base_tree, upperbound ); + + /* + if (choice==0) { + printf("Processing AVL, wait\n"); + prova = new Test(0,upperbound,base_tree); + aux_avl=prova->getAvlt(); + printf("Processing AVL2, wait\n"); + return; + } + if (choice==1) { + + prova = new Test(1,upperbound,base_tree); + aux_bst=prova->getBst(); + } + if (choice==2) { + prova = new Test(2,upperbound,base_tree); + } + */ + GtkWidget *scrolled_window; + GtkWidget *tree_view; + GtkTreeIter iter1; + GtkTreeStore *store; + GtkCellRenderer *cell; + GtkTreeViewColumn *column; + + //creo una contenitore che sia scrollabile + scrolled_window = gtk_scrolled_window_new (NULL, NULL); + gtk_scrolled_window_set_policy (GTK_SCROLLED_WINDOW (scrolled_window), GTK_POLICY_AUTOMATIC, GTK_POLICY_AUTOMATIC); + + //creo il contenitore dell'albero + store=gtk_tree_store_new(1,G_TYPE_STRING); + + //creo l'albero e lo lego al contenitore + tree_view = gtk_tree_view_new (); + gtk_scrolled_window_add_with_viewport (GTK_SCROLLED_WINDOW (scrolled_window), tree_view); + + //link dell'albero e il suo contenitore + gtk_tree_view_set_model (GTK_TREE_VIEW (tree_view), GTK_TREE_MODEL (store)); + gtk_widget_show (tree_view); + + gtk_tree_store_append (GTK_TREE_STORE (store), &iter1,NULL); + gtk_tree_store_set (GTK_TREE_STORE (store), &iter1, 0, "Prova", -1); + + //finalizzazione: creo una cella e metto in una colonna, che poi metto nell'albero. + cell = gtk_cell_renderer_text_new (); + column = gtk_tree_view_column_new_with_attributes ("AVL Tree",cell,"text", 0, NULL); + gtk_tree_view_append_column (GTK_TREE_VIEW (tree_view), GTK_TREE_VIEW_COLUMN (column)); + + gtk_widget_destroy(node_list); + node_list=scrolled_window; + + //if (choice==0) node_list = aux_avl->print_best_look(); + // if (choice==1) node_list = aux_bst->print_best_look(); + + gtk_paned_add1 (GTK_PANED (vpaned1), node_list); + gtk_widget_show (node_list); + gtk_widget_show (vpaned1); + } + + + GtkWidget* node_list_start() { + + GtkWidget *scrolled_window; + GtkWidget *tree_view; + GtkTreeIter iter1; + GtkTreeStore *store; + GtkCellRenderer *cell; + GtkTreeViewColumn *column; + + //creo una contenitore che sia scrollabile + scrolled_window = gtk_scrolled_window_new (NULL, NULL); + gtk_scrolled_window_set_policy (GTK_SCROLLED_WINDOW (scrolled_window), GTK_POLICY_AUTOMATIC, GTK_POLICY_AUTOMATIC); + + //creo il contenitore dell'albero + store=gtk_tree_store_new(1,G_TYPE_STRING); + + //creo l'albero e lo lego al contenitore + tree_view = gtk_tree_view_new (); + gtk_scrolled_window_add_with_viewport (GTK_SCROLLED_WINDOW (scrolled_window), tree_view); + + //link dell'albero e il suo contenitore + gtk_tree_view_set_model (GTK_TREE_VIEW (tree_view), GTK_TREE_MODEL (store)); + gtk_widget_show (tree_view); + + gtk_tree_store_append (GTK_TREE_STORE (store), &iter1,NULL); + gtk_tree_store_set (GTK_TREE_STORE (store), &iter1, 0, "Empty", -1); + + //finalizzazione: creo una cella e metto in una colonna, che poi metto nell'albero. + cell = gtk_cell_renderer_text_new (); + column = gtk_tree_view_column_new_with_attributes ("AVL Tree",cell,"text", 0, NULL); + gtk_tree_view_append_column (GTK_TREE_VIEW (tree_view), GTK_TREE_VIEW_COLUMN (column)); + + return scrolled_window; //ritorno l'oggetto, nel main viene visualizzato e appeso alla finestra principale. + + } + #endif int main(int argc, char *argv[]) { *************** *** 31,95 **** // 2= test comparativo ! Test *prova=NULL; ! Avlt* aux_avl=NULL; ! Bst* aux_bst=NULL; ! ! int upper_bound=1000; ! int base_tree=10000; printf("Welcome to AVL/BST test program\nYou will be asked for values, no controls on your imput, so be careful!\n"); printf("What do you want to test? AVL=0 BST=1 Comparation=2\n"); - int choice; scanf("%d",&choice); printf("Insert the initial number of items\n"); scanf("%d",&base_tree); printf("Insert the number of changements you want to do on the tree\n"); ! scanf("%d",&upper_bound); if (choice==0) { printf("Processing AVL, wait\n"); ! prova = new Test(0,upper_bound,base_tree); aux_avl=prova->getAvlt(); } if (choice==1) { printf("Processing BST, wait\n"); ! prova = new Test(1,upper_bound,base_tree); aux_bst=prova->getBst(); } if (choice==2) { printf("Comparation on the way, wait\n"); ! prova = new Test(2,upper_bound,base_tree); } ! ! #ifndef GUI ! if (choice==0) aux_avl->print_best_look(); ! if (choice==1) aux_bst->print_best_look(); ! #else ! if (choice==0 || choice==1) { ! GtkWidget *window=NULL; ! GtkWidget *vpaned=NULL; ! GtkWidget *node_list=NULL; ! ! gtk_init (&argc, &argv); ! char* fullname="AVL Tree Visualization"; window = gtk_window_new (GTK_WINDOW_TOPLEVEL); gtk_window_set_title (GTK_WINDOW (window), fullname); ! g_signal_connect (G_OBJECT (window), "destroy", G_CALLBACK (gtk_main_quit), NULL); gtk_container_set_border_width (GTK_CONTAINER (window), 15); - gtk_widget_set_size_request (GTK_WIDGET (window), 500, 450); ! vpaned = gtk_vpaned_new (); ! gtk_container_add (GTK_CONTAINER (window), vpaned); ! gtk_widget_show (vpaned); ! if (choice==0) node_list = aux_avl->print_best_look(); ! if (choice==1) node_list = aux_bst->print_best_look(); ! ! gtk_paned_add1 (GTK_PANED (vpaned), node_list); gtk_widget_show (node_list); --- 174,329 ---- // 2= test comparativo ! #ifndef GUI ! printf("Welcome to AVL/BST test program\nYou will be asked for values, no controls on your imput, so be careful!\n"); printf("What do you want to test? AVL=0 BST=1 Comparation=2\n"); scanf("%d",&choice); printf("Insert the initial number of items\n"); scanf("%d",&base_tree); printf("Insert the number of changements you want to do on the tree\n"); ! scanf("%d",&upperbound); if (choice==0) { printf("Processing AVL, wait\n"); ! prova = new Test(0,upperbound,base_tree); aux_avl=prova->getAvlt(); } if (choice==1) { printf("Processing BST, wait\n"); ! prova = new Test(1,upperbound,base_tree); aux_bst=prova->getBst(); } if (choice==2) { printf("Comparation on the way, wait\n"); ! prova = new Test(2,upperbound,base_tree); } ! if (choice==0) aux_avl->print_best_look(); ! if (choice==1) aux_bst->print_best_look(); ! #else + GtkWidget *window=NULL; + GtkWidget *vpaned2=NULL; + GtkWidget *button=NULL; + GtkWidget *box1=NULL; + GtkWidget *box2=NULL; + GtkWidget *box3=NULL; + GtkWidget *box4=NULL; + GtkWidget *box5=NULL; + GSList *group=NULL; + GtkAdjustment *adj=NULL; + GtkWidget *label=NULL; + //Test *a=new Test(); + p(); + gtk_init (&argc, &argv); + p(); + //Test *a=new Test(); + char* fullname="AVL Tree Visualization"; + window = gtk_window_new (GTK_WINDOW_TOPLEVEL); gtk_window_set_title (GTK_WINDOW (window), fullname); ! gtk_widget_set_usize(window, (int)gdk_screen_width()*0.75, (int)gdk_screen_height()*0.75); ! g_signal_connect (G_OBJECT (window), "destroy", G_CALLBACK (gtk_main_quit), NULL); gtk_container_set_border_width (GTK_CONTAINER (window), 15); ! vpaned1 = gtk_vpaned_new (); ! gtk_container_add (GTK_CONTAINER (window), vpaned1); ! gtk_widget_show (vpaned1); ! vpaned2 = gtk_vpaned_new (); ! gtk_widget_show (vpaned2); ! ! box1 = gtk_vbox_new (FALSE, 0); ! gtk_container_add (GTK_CONTAINER (vpaned2), box1); ! gtk_widget_show (box1); ! ! box2 = gtk_hbox_new (FALSE, 10); ! gtk_container_set_border_width (GTK_CONTAINER (box2), 10); ! gtk_box_pack_start (GTK_BOX (box1), box2, TRUE, TRUE, 0); ! gtk_widget_show (box2); ! ! box3 = gtk_hbox_new (FALSE, 10); ! gtk_container_set_border_width (GTK_CONTAINER (box3), 10); ! gtk_box_pack_start (GTK_BOX (box1), box3, TRUE, TRUE, 0); ! gtk_widget_show (box3); ! ! box4 = gtk_hbox_new (FALSE, 10); ! gtk_container_set_border_width (GTK_CONTAINER (box4), 10); ! gtk_box_pack_start (GTK_BOX (box1), box4, TRUE, TRUE, 0); ! gtk_widget_show (box4); ! ! box5 = gtk_hbox_new (FALSE, 10); ! gtk_container_set_border_width (GTK_CONTAINER (box5), 10); ! gtk_box_pack_start (GTK_BOX (box1), box5, TRUE, TRUE, 0); ! gtk_widget_show (box5); ! ! label = gtk_label_new ("What do you want to test?"); ! gtk_label_set_justify(GTK_LABEL (label),GTK_JUSTIFY_LEFT); ! gtk_box_pack_start (GTK_BOX (box2), label, TRUE, TRUE, 0); ! gtk_widget_show (label); ! ! button = gtk_radio_button_new_with_label (NULL, "AVL"); ! g_signal_connect (G_OBJECT (button), "toggled", G_CALLBACK (avl_select),G_OBJECT (button)); ! gtk_box_pack_start (GTK_BOX (box2), button, TRUE, TRUE, 0); ! gtk_toggle_button_set_active (GTK_TOGGLE_BUTTON (button), TRUE); ! gtk_widget_show (button); ! ! group = gtk_radio_button_get_group (GTK_RADIO_BUTTON (button)); ! button = gtk_radio_button_new_with_label (group, "BST"); ! g_signal_connect (G_OBJECT (button), "toggled", G_CALLBACK (bst_select),G_OBJECT (button)); ! gtk_toggle_button_set_active (GTK_TOGGLE_BUTTON (button), TRUE); ! gtk_box_pack_start (GTK_BOX (box2), button, TRUE, TRUE, 0); ! gtk_widget_show (button); ! ! button = gtk_radio_button_new_with_label_from_widget (GTK_RADIO_BUTTON (button), "Comparation"); ! g_signal_connect (G_OBJECT (button), "toggled", G_CALLBACK (comparation_select),G_OBJECT (button)); ! gtk_box_pack_start (GTK_BOX (box2), button, TRUE, TRUE, 0); ! gtk_widget_show (button); ! ! label = gtk_label_new ("Select the number of nodes of the tree"); ! gtk_label_set_justify(GTK_LABEL (label),GTK_JUSTIFY_LEFT); ! gtk_box_pack_start (GTK_BOX (box3), label, TRUE, TRUE, 0); ! gtk_widget_show (label); ! ! adj = (GtkAdjustment *) gtk_adjustment_new (500, 0, 10000000, 200, 0, 0); ! spinbutton1 = gtk_spin_button_new (adj, 0, 0); ! gtk_spin_button_set_wrap (GTK_SPIN_BUTTON (spinbutton1), FALSE); ! gtk_spin_button_set_numeric(GTK_SPIN_BUTTON (spinbutton1), TRUE); ! gtk_spin_button_set_value(GTK_SPIN_BUTTON (spinbutton1), 10000); ! gtk_box_pack_start (GTK_BOX (box3), spinbutton1, FALSE, TRUE, 0); ! gtk_widget_show (spinbutton1); ! ! label = gtk_label_new ("Select the number of operations on the tree"); ! gtk_label_set_justify(GTK_LABEL (label),GTK_JUSTIFY_LEFT); ! gtk_box_pack_start (GTK_BOX (box4), label, TRUE, TRUE, 0); ! gtk_widget_show (label); ! ! adj = (GtkAdjustment *) gtk_adjustment_new (500, 0, 10000000, 200, 0, 0); ! spinbutton2 = gtk_spin_button_new (adj, 0, 0); ! gtk_spin_button_set_wrap (GTK_SPIN_BUTTON (spinbutton2), FALSE); ! gtk_spin_button_set_numeric(GTK_SPIN_BUTTON (spinbutton2), TRUE); ! gtk_spin_button_set_value(GTK_SPIN_BUTTON (spinbutton2), 1000); ! gtk_box_pack_start (GTK_BOX (box4), spinbutton2, FALSE, TRUE, 0); ! gtk_widget_show (spinbutton2); ! ! button = gtk_button_new_with_label ("start"); ! g_signal_connect_swapped (G_OBJECT (button), "clicked", G_CALLBACK (start), G_OBJECT (window)); ! gtk_box_pack_start (GTK_BOX (box5), button, FALSE, TRUE, 55); ! gtk_widget_show (button); ! ! button = gtk_button_new_with_label ("close"); ! g_signal_connect_swapped (G_OBJECT (button), "clicked", G_CALLBACK (gtk_main_quit), G_OBJECT (window)); ! gtk_box_pack_start (GTK_BOX (box5), button, FALSE, TRUE, 65); ! gtk_widget_show (button); ! ! node_list=node_list_start(); ! ! gtk_paned_add1 (GTK_PANED (vpaned1), node_list); ! gtk_paned_add2 (GTK_PANED (vpaned1), vpaned2); ! gtk_widget_show (node_list); *************** *** 97,102 **** gtk_main (); ! } #endif return EXIT_SUCCESS; } --- 331,338 ---- gtk_main (); ! ! #endif + return EXIT_SUCCESS; } Index: Makefile =================================================================== RCS file: /cvsroot/avl/avl/src/Makefile,v retrieving revision 1.6 retrieving revision 1.7 diff -C2 -d -r1.6 -r1.7 *** Makefile 6 Sep 2004 13:16:33 -0000 1.6 --- Makefile 7 Sep 2004 10:40:17 -0000 1.7 *************** *** 3,6 **** --- 3,7 ---- ifdef gtk_gui CC=g++ -O2 -Wall -W `pkg-config gtk+-2.0 --cflags` -DGUI -g + #CC=g++ `pkg-config gtk+-2.0 --cflags` -DGUI else CC=g++ -O2 -Wall -W Index: test.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/test.cpp,v retrieving revision 1.10 retrieving revision 1.11 diff -C2 -d -r1.10 -r1.11 *** test.cpp 6 Sep 2004 17:03:40 -0000 1.10 --- test.cpp 7 Sep 2004 10:40:17 -0000 1.11 *************** *** 52,61 **** random=rand()%tree_dimensions; avlt=avlt->insert(random); - // insertion_list.push_back(random); } end = clock(); init_timer = ((double) (end - start)) / CLOCKS_PER_SEC; printf("AVL Initialization of %d items tree took %lf seconds\n",base_limit,init_timer); - // getchar(); } --- 52,59 ---- *************** *** 65,74 **** random=rand()%tree_dimensions; bst->insert(random); - // insertion_list.push_back(random); } end = clock(); init_timer = ((double) (end - start)) / CLOCKS_PER_SEC; printf("BST Initialization of %d items tree took %lf seconds\n",base_limit,init_timer); - // getchar(); } } --- 63,70 ---- *************** *** 96,100 **** avlt=avlt->insert(random); insertion_list.push_back(random); - //printf("inserted number %d\n",random); insert_counter++; } --- 92,95 ---- *************** *** 123,128 **** change_timer = ((double) (end - start)) / CLOCKS_PER_SEC; printf("AVL TEST RESULTS:\n%d insertions and %d deletions took %lf seconds.\nTotal of %d cycles, wasted:%d\n",insert_counter,erase_counter,change_timer,upper_limit,waste); ! printf("press Return to exit\n"); ! //getchar(); } --- 118,122 ---- change_timer = ((double) (end - start)) / CLOCKS_PER_SEC; printf("AVL TEST RESULTS:\n%d insertions and %d deletions took %lf seconds.\nTotal of %d cycles, wasted:%d\n",insert_counter,erase_counter,change_timer,upper_limit,waste); ! } *************** *** 147,155 **** random=rand()%tree_dimensions; decision=rand()%2; - //decision=0; if (decision==0) { bst->insert(random); insertion_list.push_back(random); - //printf("inserted number %d\n",random); insert_counter++; } --- 141,147 ---- *************** *** 176,181 **** change_timer = ((double) (end - start)) / CLOCKS_PER_SEC; printf("BST TEST RESULTS:\n%d insertions and %d deletions took %lf seconds.\nTotal of %d cycles, wasted %d\n",insert_counter,erase_counter,change_timer,upper_limit,waste); ! printf("press Return to exit\n"); ! //getchar(); } --- 168,172 ---- change_timer = ((double) (end - start)) / CLOCKS_PER_SEC; printf("BST TEST RESULTS:\n%d insertions and %d deletions took %lf seconds.\nTotal of %d cycles, wasted %d\n",insert_counter,erase_counter,change_timer,upper_limit,waste); ! } *************** *** 234,237 **** --- 225,229 ---- base_tree_size è la dimensione dell'albero */ + bst = avlt = NULL; tree_dimensions=base_tree_size; |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-06 17:03:49
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv5600/src Modified Files: test.cpp Log Message: Index: test.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/test.cpp,v retrieving revision 1.9 retrieving revision 1.10 diff -C2 -d -r1.9 -r1.10 *** test.cpp 6 Sep 2004 16:44:16 -0000 1.9 --- test.cpp 6 Sep 2004 17:03:40 -0000 1.10 *************** *** 202,208 **** sleep(5); Avl_Test(upperbound); ! if ((temp_timer-getInitTimer())>double(0)) printf("***************************\nAVL faster\n***************************\n"); ! if ((temp_timer-getInitTimer())<double(0)) printf("***************************\nBST faster\n***************************\n"); ! if ((temp_timer-getInitTimer())==double(0)) printf("***************************\nNo real differences found\n***************************\n"); int max=bst->max()->getValue(); //caching! --- 202,208 ---- sleep(5); Avl_Test(upperbound); ! if ((temp_timer-getChangeTimer())>double(0)) printf("***************************\nAVL faster\n***************************\n"); ! if ((temp_timer-getChangeTimer())<double(0)) printf("***************************\nBST faster\n***************************\n"); ! if ((temp_timer-getChangeTimer())==double(0)) printf("***************************\nNo real differences found\n***************************\n"); int max=bst->max()->getValue(); //caching! |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-06 16:44:31
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv1892 Modified Files: test.cpp Log Message: Index: test.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/test.cpp,v retrieving revision 1.8 retrieving revision 1.9 diff -C2 -d -r1.8 -r1.9 *** test.cpp 6 Sep 2004 16:03:25 -0000 1.8 --- test.cpp 6 Sep 2004 16:44:16 -0000 1.9 *************** *** 234,238 **** base_tree_size è la dimensione dell'albero */ ! avlt = bst= NULL; tree_dimensions=base_tree_size; switch (kind){ --- 234,238 ---- base_tree_size è la dimensione dell'albero */ ! bst = avlt = NULL; tree_dimensions=base_tree_size; switch (kind){ |
|
From: Patrizio B. <het...@us...> - 2004-09-06 16:03:38
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv26486 Modified Files: test.cpp Log Message: fix Index: test.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/test.cpp,v retrieving revision 1.7 retrieving revision 1.8 diff -C2 -d -r1.7 -r1.8 *** test.cpp 6 Sep 2004 13:16:36 -0000 1.7 --- test.cpp 6 Sep 2004 16:03:25 -0000 1.8 *************** *** 234,238 **** base_tree_size è la dimensione dell'albero */ ! tree_dimensions=base_tree_size; switch (kind){ --- 234,238 ---- base_tree_size è la dimensione dell'albero */ ! avlt = bst= NULL; tree_dimensions=base_tree_size; switch (kind){ |
|
From: Patrizio B. <het...@us...> - 2004-09-06 16:02:05
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv26137/docs Modified Files: relazione.tex Added Files: application.eps application.png application.xmi trees.eps trees.png trees.xmi Log Message: improvement --- NEW FILE: application.eps --- %!PS-Adobe-3.0 EPSF-3.0 %%Creator: ImageMagick 6.0.5 %%Title: application.eps %%CreationDate: Mon Sep 6 17:38:38 2004 %%BoundingBox: 0 0 842 443 %%HiResBoundingBox: 0 0 842 443 %%LanguageLevel: 3 %%Pages: 1 %%EndComments %%BeginProlog /ByteStreamDecodeFilter { /z exch def /r exch def /c exch def z 0 eq { /ASCII85Decode filter } if z 1 eq { << /K -1 /Columns c /Rows r >> /CCITTFaxDecode filter } if z 2 eq { /DCTDecode filter } if z 3 eq { /LZWDecode filter } if z 4 eq { /RunLengthDecode filter } if z 5 eq { /FlateDecode filter } if } bind def /DirectClassImageDict { colorspace 0 eq { /DeviceRGB setcolorspace << /ImageType 1 /Width columns /Height rows /BitsPerComponent 8 /DataSource pixel_stream /MultipleDataSources false /ImageMatrix [columns 0 0 rows neg 0 rows] /Decode [0 1 0 1 0 1] >> } { /DeviceCMYK setcolorspace << /ImageType 1 /Width columns /Height rows /BitsPerComponent 8 /DataSource pixel_stream /MultipleDataSources false /ImageMatrix [columns 0 0 rows neg 0 rows] /Decode compression 2 eq { [1 0 1 0 1 0 1 0] } { [0 1 0 1 0 1 0 1] } ifelse >> } ifelse } bind def /PseudoClassImageDict { % Colors in colormap image. currentfile buffer readline pop token pop /colors exch def pop colors 0 eq { % Depth of grayscale image. currentfile buffer readline pop token pop /bits exch def pop /DeviceGray setcolorspace << /ImageType 1 /Width columns /Height rows /BitsPerComponent bits /Decode [0 1] /ImageMatrix [columns 0 0 rows neg 0 rows] /DataSource pixel_stream >> } { % RGB colormap. /colormap colors 3 mul string def compression 0 eq { currentfile /ASCII85Decode filter colormap readstring pop pop } { currentfile colormap readstring pop pop } ifelse [ /Indexed /DeviceRGB colors 1 sub colormap ] setcolorspace << /ImageType 1 /Width columns /Height rows /BitsPerComponent 8 /Decode [0 255] /ImageMatrix [columns 0 0 rows neg 0 rows] /DataSource pixel_stream >> } ifelse } bind def /NonMaskedImageDict { class 1 eq { PseudoClassImageDict } { DirectClassImageDict } ifelse } bind def /MaskedImageDict { << /ImageType 3 /InterleaveType 3 /DataDict NonMaskedImageDict /MaskDict << /ImageType 1 /Width columns /Height rows /BitsPerComponent 1 /DataSource mask_stream /MultipleDataSources false /ImageMatrix [ columns 0 0 rows neg 0 rows] /Decode [ 0 1 ] >> >> } bind def /ClipImage {} def /DisplayImage { /buffer 512 string def % Translation. currentfile buffer readline pop token pop /x exch def token pop /y exch def pop x y translate % Image size and font size. currentfile buffer readline pop token pop /x exch def token pop /y exch def pop currentfile buffer readline pop token pop /pointsize exch def pop x y scale % Clipping path. currentfile buffer readline pop token pop /clipped exch def pop % EPS. currentfile buffer readline pop token pop /sp exch def pop % Image pixel size. currentfile buffer readline pop token pop /columns exch def token pop /rows exch def pop % Colorspace (RGB/CMYK). currentfile buffer readline pop token pop /colorspace exch def pop % Transparency. currentfile buffer readline pop token pop /alpha exch def pop % Stencil mask? currentfile buffer readline pop token pop /stencil exch def pop % Image class (direct/pseudo). currentfile buffer readline pop token pop /class exch def pop % Compression type. currentfile buffer readline pop token pop /compression exch def pop % Clip and render. /pixel_stream currentfile columns rows compression ByteStreamDecodeFilter def clipped { ClipImage } if alpha stencil not and { MaskedImageDict mask_stream resetfile } { NonMaskedImageDict } ifelse stencil { 0 setgray imagemask } { image } ifelse grestore sp { showpage } if } bind def %%EndProlog %%Page: 1 1 %%PageBoundingBox: 0 0 842 443 /ClipImage {} def userdict begin %%BeginData: 22851 BINARY Bytes DisplayImage 0 0 842 443 12.000000 false false 842 443 0 false false 0 5 xÚí/Í #NDTDTDTDT\ â'8Ñ@ÅK¨x T4PÑÀ7ð#TPñ#TPQHÅA*^HM %T¼B*^¸ÂUTD¨¨¹ßw2¹¹½Íîfó÷ò<|86ÙÙÉîÎçfvvÎÏ |
|
From: Patrizio B. <het...@us...> - 2004-09-06 14:12:16
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv7147/src Modified Files: avl.cpp avlt.cpp avlt.h bst.cpp bst.h Log Message: bug fix and updates Index: bst.h =================================================================== RCS file: /cvsroot/avl/avl/src/bst.h,v retrieving revision 1.5 retrieving revision 1.6 diff -C2 -d -r1.5 -r1.6 *** bst.h 6 Sep 2004 13:16:36 -0000 1.5 --- bst.h 6 Sep 2004 14:12:06 -0000 1.6 *************** *** 39,43 **** void print_ric( int, int ); #ifdef GUI ! void ric(); #else void c_print(char*); --- 39,43 ---- void print_ric( int, int ); #ifdef GUI ! void print_gtk_ric(); #else void c_print(char*); *************** *** 61,85 **** //operazioni sugli alberi Bst *root(); ! bool isLeaf(); //OK ! bool isRoot(); //OK ! int level(); //OK ! int nodes(); //OK int leaves(); int height(); //operazioni tipiche dei BST ! Bst *search(int); //OK ! void insert(int); //OK ! void erase(int); //Non testato ! Bst *max(); //OK ! Bst *min(); //OK ! Bst *predecessor(); //OK ! Bst *successor(); //OK void print(); #ifndef GUI ! void print1(); #else ! GtkWidget* print1(); #endif }; --- 61,85 ---- //operazioni sugli alberi Bst *root(); ! bool isLeaf(); ! bool isRoot(); ! int level(); ! int nodes(); int leaves(); int height(); //operazioni tipiche dei BST ! Bst *search(int); ! void insert(int); ! void erase(int); ! Bst *max(); ! Bst *min(); ! Bst *predecessor(); ! Bst *successor(); void print(); #ifndef GUI ! void print_best_look(); #else ! GtkWidget* print_best_look(); #endif }; Index: bst.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/bst.cpp,v retrieving revision 1.10 retrieving revision 1.11 diff -C2 -d -r1.10 -r1.11 *** bst.cpp 6 Sep 2004 13:16:36 -0000 1.10 --- bst.cpp 6 Sep 2004 14:12:06 -0000 1.11 *************** *** 75,79 **** } ! /** Restituisce la radice dell'albero a cui appartiene il nodo corrente*/ Bst *Bst::root() { --- 75,79 ---- } ! /* Restituisce la radice dell'albero a cui appartiene il nodo corrente*/ Bst *Bst::root() { *************** *** 84,95 **** } ! /** Indica se il nodo corrente è una foglia */ bool Bst::isLeaf() { - //testa (getLeft()==NULL && getRight()==NULL) <==> (!getLeft() && !getRight()) <==> !(getLeft()||getRight()) return !(getLeft()||getRight()); } ! /** Indica se il nodo è la radice dell'albero*/ bool Bst::isRoot() { --- 84,94 ---- } ! /* Indica se il nodo corrente è una foglia */ bool Bst::isLeaf() { return !(getLeft()||getRight()); } ! /* Indica se il nodo è la radice dell'albero*/ bool Bst::isRoot() { *************** *** 97,101 **** } ! /** Calcola il livello del nodo (ovvero la lunghezza del cammino tra il nodo e la radice)*/ int Bst::level() { --- 96,100 ---- } ! /* Calcola il livello del nodo (ovvero la lunghezza del cammino tra il nodo e la radice)*/ int Bst::level() { *************** *** 107,111 **** } ! /** Calcola il numero di nodi dell'albero che ha come radice il nodo*/ int Bst::nodes() { --- 106,110 ---- } ! /* Calcola il numero di nodi dell'albero che ha come radice il nodo*/ int Bst::nodes() { *************** *** 121,125 **** } ! /** Calcola il numero di foglie dell'albero che ha come radice il nodo*/ int Bst::leaves() { --- 120,124 ---- } ! /* Calcola il numero di foglie dell'albero che ha come radice il nodo*/ int Bst::leaves() { *************** *** 135,139 **** } ! /** Calcola l'altezza (lunghezza del ramo più lungo) dell'albero che ha come radice il nodo*/ int Bst::height() { --- 134,138 ---- } ! /* Calcola l'altezza (lunghezza del ramo più lungo) dell'albero che ha come radice il nodo*/ int Bst::height() { *************** *** 151,155 **** } ! /** Ricerca un nodo di valore key in modo iterativo e ne restituisce il puntatore, se la ricerca ha esito negativo restituisce NULL*/ Bst *Bst::search(int key) { --- 150,154 ---- } ! /* Ricerca un nodo di valore key in modo iterativo e ne restituisce il puntatore, se la ricerca ha esito negativo restituisce NULL*/ Bst *Bst::search(int key) { *************** *** 170,174 **** } ! /** Aggiunge un nodo con valore key nell'albero*/ void Bst::insert(int key) { --- 169,173 ---- } ! /* Aggiunge un nodo con valore key nell'albero*/ void Bst::insert(int key) { *************** *** 239,243 **** } ! /** Elimina il nodo di valore key dall'albero*/ void Bst::erase(int key) { --- 238,242 ---- } ! /* Elimina il nodo di valore key dall'albero*/ void Bst::erase(int key) { *************** *** 251,255 **** } ! /** Trova il nodo dell'albero che ha valore massimo e ne restituisce il puntatore*/ Bst *Bst::max() { --- 250,254 ---- } ! /* Trova il nodo dell'albero che ha valore massimo e ne restituisce il puntatore*/ Bst *Bst::max() { *************** *** 260,264 **** } ! /** Trova il nodo dell'albero che ha valore minimo e ne restituisce il puntatore*/ Bst *Bst::min() { --- 259,263 ---- } ! /* Trova il nodo dell'albero che ha valore minimo e ne restituisce il puntatore*/ Bst *Bst::min() { *************** *** 269,273 **** } ! /** Restituisce il puntatore del nodo predecessore (Il nodo che ha valore maggiore tra quelli che hanno valore minore)*/ Bst *Bst::predecessor() { --- 268,272 ---- } ! /* Restituisce il puntatore del nodo predecessore (Il nodo che ha valore maggiore tra quelli che hanno valore minore)*/ Bst *Bst::predecessor() { *************** *** 288,292 **** } ! /** Restituisce il puntatore del nodo successore (Il nodo che ha valore minore tra quelli che hanno valore maggiore)*/ Bst *Bst::successor() { --- 287,291 ---- } ! /* Restituisce il puntatore del nodo successore (Il nodo che ha valore minore tra quelli che hanno valore maggiore)*/ Bst *Bst::successor() { *************** *** 307,326 **** } - /*void Bst::print_ric(Bst* root, int level) - { - int i; - if(root == NULL) - return; - - print_ric(root->left, level+1); - printf("%d[%d],", root->getValue(),level); - print_ric(root->right, level+1); - } - - void Bst::print() - { - print_ric(this, 0); - }*/ - void Bst::print_ric(int lev, int tab) --- 306,309 ---- *************** *** 383,391 **** printf("[%i;%i;40m",format,color); } ! else if(*string=='b'){//BLUE color=BLUE; printf("[%i;%i;40m",format,color); } ! else if(*string=='y'){//BLUE color=YELLOW; printf("[%i;%i;40m",format,color); --- 366,374 ---- printf("[%i;%i;40m",format,color); } ! else if(*string=='b'){// blue color=BLUE; printf("[%i;%i;40m",format,color); } ! else if(*string=='y'){// yellow color=YELLOW; printf("[%i;%i;40m",format,color); *************** *** 399,403 **** } // usa c_print per stampare a colori. Funzione ricorsiva ! void Bst::print1() { char buffer[50]; --- 382,386 ---- } // usa c_print per stampare a colori. Funzione ricorsiva ! void Bst::print_best_look() { char buffer[50]; *************** *** 426,432 **** } if( getLeft() ) ! getLeft()->print1(); if( getRight() ) ! getRight()->print1(); } --- 409,415 ---- } if( getLeft() ) ! getLeft()->print_best_look(); if( getRight() ) ! getRight()->print_best_look(); } *************** *** 439,443 **** GtkTreeStore *store; ! void Bst::ric() { --- 422,426 ---- GtkTreeStore *store; ! void Bst::print_gtk_ric() { *************** *** 455,459 **** iter2=iter1; ! getRight()->ric(); } iter2=aux; //riprende dopo aver appeso i rami destri, e termina con i rami sinistri --- 438,442 ---- iter2=iter1; ! getRight()->print_gtk_ric(); } iter2=aux; //riprende dopo aver appeso i rami destri, e termina con i rami sinistri *************** *** 467,471 **** iter2=iter1; ! getLeft()->ric(); } --- 450,454 ---- iter2=iter1; ! getLeft()->print_gtk_ric(); } *************** *** 474,478 **** ! GtkWidget* Bst::print1() { GtkWidget *scrolled_window; --- 457,461 ---- ! GtkWidget* Bst::print_best_look() { GtkWidget *scrolled_window; *************** *** 505,510 **** //prendo la root e stampo tutto l'albero, appendo il primo valore e poi ricorsivamente tutti gli altri ! if (this->root() != NULL) root=this->root(); ! else root=this; msg = g_strdup_printf ("%d", root->getValue()); gtk_tree_store_append (GTK_TREE_STORE (store), &iter2,&iter1); --- 488,493 ---- //prendo la root e stampo tutto l'albero, appendo il primo valore e poi ricorsivamente tutti gli altri ! root=this->root(); ! msg = g_strdup_printf ("%d", root->getValue()); gtk_tree_store_append (GTK_TREE_STORE (store), &iter2,&iter1); *************** *** 512,516 **** g_free(msg); ! root->ric(); //finalizzazione: creo una cella e metto in una colonna, che poi metto nell'albero. --- 495,499 ---- g_free(msg); ! root->print_gtk_ric(); //finalizzazione: creo una cella e metto in una colonna, che poi metto nell'albero. Index: avl.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avl.cpp,v retrieving revision 1.10 retrieving revision 1.11 diff -C2 -d -r1.10 -r1.11 *** avl.cpp 6 Sep 2004 13:16:36 -0000 1.10 --- avl.cpp 6 Sep 2004 14:12:06 -0000 1.11 *************** *** 26,129 **** int main(int argc, char *argv[]) { - #if 0 - // Bst a(1 ), *b; - - Avlt *a, *b; - /* a.insert(3); - a.insert(5); - a.insert(4); - a.insert(2); - a.insert(10); - a.insert(-10); - a.insert(-1); - a.insert(20); - a.insert(-20); - a.insert(-25); - a.insert(-15); - a.insert(-6); - a.insert(-200); - a.insert(-300); - a.insert(-400); - a.insert(-500); - a.insert(-600); - a.insert(-700); - */ - /* a.insert(6); - - - a.insert(3); - // a.insert(-3); - */ - - Avlt *a = new Avlt(0,1); - - for (int i=0;i<567;i++) - { - int aaa=(rand()%1000)-500; - a = a->insert( aaa ); - //if(i>=19) - { - /* printf("%d->%d\n",i,aaa); - if(!a->checkBalance()) - { - a->print(); - printf("\n-------------------------------------------------------------\n"); - }*/ - } - } - a->print(); - - // a->search(-8)->print1(); - /* printf("%d\n",a->nodes()); - a = a->erase(277); - a = a->erase(3); - a = a->erase(-3); - a = a->erase(-8); - a = a->erase(-165); - a = a->erase(190); - a = a->erase(415); - a = a->erase(a->root()->getValue()); - // a = a->erase(-7); - printf("\n%d\n",a->nodes()); - - printf("\n%d",a->checkBalance());*/ - //a->print1(); - // a->search(3)->print1(); - //a->print(); - /* - a = a->insert(-98); - a = a->insert(100); - a = a->insert(-1000); - a = a->insert(-10); - a = a->insert(50); - a = a->insert(102); - a = a->insert(1000); - - a->print(); - - a->erase(50); - a->print1();*/ - // a->print(); - /*vector<Avlt *> v; - v = a->getWrongs(); - - for (int i=0; i<v.size(); i++) - cout << (v[i])->getValue() << endl; - */ - // printf("%d",a->getFdb()); - // a->print(); - // b = (a.getLeft())->getLeft()->getRight(); - // printf("%d",b->getValue()); - #endif - - - - - - /* // 0= test avl // 1= test bst ! Test *prova_avl, *prova_bst; int upper_bound=1000; int base_tree=10000; --- 26,38 ---- int main(int argc, char *argv[]) { // 0= test avl // 1= test bst ! // 2= test comparativo ! ! Test *prova=NULL; ! Avlt* aux_avl=NULL; ! Bst* aux_bst=NULL; ! int upper_bound=1000; int base_tree=10000; *************** *** 136,200 **** printf("Insert the number of changements you want to do on the tree\n"); scanf("%d",&upper_bound); if (choice==0) { printf("Processing AVL, wait\n"); ! prova_avl = new Test(0,upper_bound,base_tree); } if (choice==1) { printf("Processing BST, wait\n"); ! prova_bst = new Test(1,upper_bound,base_tree); } if (choice==2) { printf("Comparation on the way, wait\n"); ! prova_bst = new Test(2,upper_bound,base_tree); } - */ - //Test *prova; - //prova = new Test(1,5,1); - //prova->getBst()->print1(); - //not a good thing...for testing purpose only - //prova->getAvlt()->print1(); - - /*Bst a(1 ); - a.insert(3); - a.insert(5); - a.insert(4); - a.insert(2); - a.insert(10); - a.insert(-10); - a.insert(-1); - a.insert(20); - a.insert(-20); - a.insert(-25); - a.insert(-15); - a.insert(-6); - a.insert(-200); - a.insert(-300); - a.insert(-400); - a.insert(-500); - a.insert(-600); - a.insert(-700); - a.erase(1);*/ - Bst a(1); - - /* for (int i=0;i<500000;i++) - { - int aaa=(rand()%1000000)-500000; - a.insert( aaa ); - } - for (int i=0;i<1000000;i++) - { - int aaa=(rand()%1000000)-500000; - a.erase( aaa ); - }*/ - Test t(0,10,100000); - a=*(t.getBst()); #ifndef GUI ! a.print1(); #else ! GtkWidget *window; ! GtkWidget *vpaned; ! GtkWidget *node_list; gtk_init (&argc, &argv); --- 45,73 ---- printf("Insert the number of changements you want to do on the tree\n"); scanf("%d",&upper_bound); + if (choice==0) { printf("Processing AVL, wait\n"); ! prova = new Test(0,upper_bound,base_tree); ! aux_avl=prova->getAvlt(); } if (choice==1) { printf("Processing BST, wait\n"); ! prova = new Test(1,upper_bound,base_tree); ! aux_bst=prova->getBst(); } if (choice==2) { printf("Comparation on the way, wait\n"); ! prova = new Test(2,upper_bound,base_tree); } #ifndef GUI ! if (choice==0) aux_avl->print_best_look(); ! if (choice==1) aux_bst->print_best_look(); #else ! if (choice==0 || choice==1) { ! GtkWidget *window=NULL; ! GtkWidget *vpaned=NULL; ! GtkWidget *node_list=NULL; gtk_init (&argc, &argv); *************** *** 215,220 **** gtk_widget_show (vpaned); ! node_list = a.print1(); ! gtk_paned_add1 (GTK_PANED (vpaned), node_list); gtk_widget_show (node_list); --- 88,94 ---- gtk_widget_show (vpaned); ! if (choice==0) node_list = aux_avl->print_best_look(); ! if (choice==1) node_list = aux_bst->print_best_look(); ! gtk_paned_add1 (GTK_PANED (vpaned), node_list); gtk_widget_show (node_list); *************** *** 223,226 **** --- 97,101 ---- gtk_main (); + } #endif return EXIT_SUCCESS; Index: avlt.h =================================================================== RCS file: /cvsroot/avl/avl/src/avlt.h,v retrieving revision 1.8 retrieving revision 1.9 diff -C2 -d -r1.8 -r1.9 *** avlt.h 6 Sep 2004 13:16:36 -0000 1.8 --- avlt.h 6 Sep 2004 14:12:06 -0000 1.9 *************** *** 42,46 **** ~Avlt(); - // void setFdb( int ); void setFdb(); void setFdb(Avlt *, Avlt *); --- 42,45 ---- Index: avlt.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avlt.cpp,v retrieving revision 1.7 retrieving revision 1.8 diff -C2 -d -r1.7 -r1.8 *** avlt.cpp 6 Sep 2004 13:16:36 -0000 1.7 --- avlt.cpp 6 Sep 2004 14:12:06 -0000 1.8 *************** *** 32,42 **** } ! /** Imposta il Fattore di Bilanciamento a s*/ ! /*void Avlt::setFdb( int s ) ! { ! setHeight(s); ! } ! */ ! /** Calcola il FdB del nodo corrente*/ void Avlt::setFdb() { --- 32,36 ---- } ! /* Calcola il FdB del nodo corrente*/ void Avlt::setFdb() { *************** *** 56,60 **** } ! /** Calcola il fattore di bilanciamento a di tutti i nodi del cammino da start a end*/ void Avlt::setFdb( Avlt * start , Avlt * end) { --- 50,54 ---- } ! /* Calcola il fattore di bilanciamento a di tutti i nodi del cammino da start a end*/ void Avlt::setFdb( Avlt * start , Avlt * end) { *************** *** 91,95 **** } ! /** Effettua una rotazione verso sinistra e restituisce il nuovo nodo genitore*/ Avlt *Avlt::leftRotate() //dd { --- 85,89 ---- } ! /* Effettua una rotazione verso sinistra e restituisce il nuovo nodo genitore*/ Avlt *Avlt::leftRotate() //dd { *************** *** 125,129 **** } ! /** Effettua una rotazione verso destra e restituisce il nuovo nodo genitore*/ Avlt *Avlt::rightRotate() //ss { --- 119,123 ---- } ! /* Effettua una rotazione verso destra e restituisce il nuovo nodo genitore*/ Avlt *Avlt::rightRotate() //ss { *************** *** 159,163 **** } ! /** Inserisce un nuovo nodo con valore key utilizzando un algoritmo ricorsivo*/ Avlt *Avlt::insert(int key) { --- 153,157 ---- } ! /* Inserisce un nuovo nodo con valore key utilizzando un algoritmo ricorsivo*/ Avlt *Avlt::insert(int key) { *************** *** 217,221 **** } ! /** Inserisce un nuovo nodo con valore key utilizzando un algoritmo iterativo*/ Avlt *Avlt::insert_iter(int key) { --- 211,215 ---- } ! /* Inserisce un nuovo nodo con valore key utilizzando un algoritmo iterativo*/ Avlt *Avlt::insert_iter(int key) { *************** *** 321,325 **** } ! /** Elimina il nodo di valore key dall'albero*/ Avlt *Avlt::erase(int key) { --- 315,319 ---- } ! /* Elimina il nodo di valore key dall'albero*/ Avlt *Avlt::erase(int key) { *************** *** 421,425 **** } ! /** Verifica se l'albero è bilanciato*/ bool Avlt::checkBalance() { --- 415,419 ---- } ! /* Verifica se l'albero è bilanciato*/ bool Avlt::checkBalance() { *************** *** 437,441 **** } ! /** Restituisce un vettore di nodi che hanno FdB diverso da -1,0,+1*/ vector<Avlt *> Avlt::getWrongs() { --- 431,435 ---- } ! /* Restituisce un vettore di nodi che hanno FdB diverso da -1,0,+1*/ vector<Avlt *> Avlt::getWrongs() { |
|
From: Patrizio B. <het...@us...> - 2004-09-06 14:12:14
|
Update of /cvsroot/avl/avl In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv7147 Modified Files: ChangeLog TODO Log Message: bug fix and updates Index: TODO =================================================================== RCS file: /cvsroot/avl/avl/TODO,v retrieving revision 1.5 retrieving revision 1.6 diff -C2 -d -r1.5 -r1.6 *** TODO 4 Sep 2004 15:30:39 -0000 1.5 --- TODO 6 Sep 2004 14:12:05 -0000 1.6 *************** *** 1,7 **** - Controllare e fixare i punti in cui freeza. dovrebbe essere in bst. non è solo quando l'albero è vuoto. - Finire di mettere i commenti in avlt.cpp ! - Quando chiudo la GUI va in segmentatio fault. ! - A volte mi da un sacco di errori di segmentation fault all'interno di funzioni GTK --- 1,12 ---- + Codice: - Controllare e fixare i punti in cui freeza. dovrebbe essere in bst. non è solo quando l'albero è vuoto. - Finire di mettere i commenti in avlt.cpp ! - controllare dove la stampa GTK perde i nodi (certe volte...) ! Documentazione: ! ! - ripulire e impaginare ! ! - aggiungere documentazione codice Index: ChangeLog =================================================================== RCS file: /cvsroot/avl/avl/ChangeLog,v retrieving revision 1.7 retrieving revision 1.8 diff -C2 -d -r1.7 -r1.8 *** ChangeLog 21 Jul 2004 16:58:19 -0000 1.7 --- ChangeLog 6 Sep 2004 14:12:05 -0000 1.8 *************** *** 1,2 **** --- 1,13 ---- + --==06.09.2004==-- + <hetfield666>: + - Updated Test Class and client usage + - General Code cleaning and restyle + - fixed 2 warnings in avlt.cpp + - fixed a weird but in tree print + - completed relation (need review) + - Fixed Makefile for new Test class + - Added debug flags to CFLAGS + - Updated license and copyright + --==21.07.2004==-- <jah2003>: |
|
From: Patrizio B. <het...@us...> - 2004-09-06 13:17:12
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv28685/docs Modified Files: relazione.tex Log Message: fixes 2 warning some code cleaning in avl.cpp comment and code cleaning in test.* updated comment and license in all files updated Makefile for shared build updated Makfile for debug build updated relation for Makefile explaination some check to track seg fault. (still useless) Index: relazione.tex =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.tex,v retrieving revision 1.5 retrieving revision 1.6 diff -C2 -d -r1.5 -r1.6 *** relazione.tex 4 Sep 2004 14:09:43 -0000 1.5 --- relazione.tex 6 Sep 2004 13:16:32 -0000 1.6 *************** *** 167,171 **** --- 167,182 ---- Le altre due parti sono un "client" per generare gli alberi, fare dei test di inserimento e cancellazione, e un programma in GTK per la grafica a video degli alberi tramite una gradevole GUI. Il linguaggio utilizzato è il C++, che permette di sfruttare le nozioni di ereditarietà tra i BST e gli AVL. + Attraverso il Makefile (chi è familiare con l'ambiente UNIX conosce le potenzialità di scripting che offre) è stata prevista la scelta della compilazione della GUI e della compilazione in modalità libreria condivisa: quest'ultima permette di sfruttare gli algoritmi implementati in qualunque applicazione C++. + Opzioni Makefile: + \begin {itemize} + \item make -> compila l'applicazione implementando la visualizzazione su shell. + \item make gui -> compila l'applicazione implementando la visualizzazione tramite interfaccia grafica scritta in + GTK. E' necessaria la presenza dei pacchetti devel della libraria GTK. + \\item make shared -> la compilazione è divisa in due: una parte riguarda il client, l'altra riguarda gli algoritmi, + che vengono linkati come "shared". in questo modo è possibile utilizzarli in tutte le altre applicazioni necessarie e + il file binario è di dimensioni più contenute. + \end{itemize} + \chapter{Conclusioni}\label{Conclusioni} |
|
From: Patrizio B. <het...@us...> - 2004-09-06 13:16:47
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv28685/src Modified Files: Makefile avl.cpp avlt.cpp avlt.h bst.cpp bst.h test.cpp test.h Log Message: fixes 2 warning some code cleaning in avl.cpp comment and code cleaning in test.* updated comment and license in all files updated Makefile for shared build updated Makfile for debug build updated relation for Makefile explaination some check to track seg fault. (still useless) Index: test.h =================================================================== RCS file: /cvsroot/avl/avl/src/test.h,v retrieving revision 1.8 retrieving revision 1.9 diff -C2 -d -r1.8 -r1.9 *** test.h 4 Sep 2004 15:30:40 -0000 1.8 --- test.h 6 Sep 2004 13:16:36 -0000 1.9 *************** *** 1,2 **** --- 1,21 ---- + /*************************************************************************** + * Copyright (C) 2004 by Patrizio Bassi && Gianlorenzo D'Angelo * + * * + * This program is free software; you can redistribute it and/or modify * + * it under the terms of the GNU General Public License as published by * + * the Free Software Foundation; either version 2 of the License, or * + * (at your option) any later version. * + * * + * This program is distributed in the hope that it will be useful, * + * but WITHOUT ANY WARRANTY; without even the implied warranty of * + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * + * GNU General Public License for more details. * + * * + * You should have received a copy of the GNU General Public License * + * along with this program; if not, write to the * + * Free Software Foundation, Inc., * + * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * + ***************************************************************************/ + #ifndef TEST_H #define TEST_H Index: bst.h =================================================================== RCS file: /cvsroot/avl/avl/src/bst.h,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 *** bst.h 4 Aug 2004 15:31:36 -0000 1.4 --- bst.h 6 Sep 2004 13:16:36 -0000 1.5 *************** *** 2,6 **** * Copyright (C) 2004 by Patrizio Bassi && Gianlorenzo D'Angelo * * * - * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * --- 2,5 ---- *************** *** 18,21 **** --- 17,21 ---- * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * ***************************************************************************/ + #ifndef BST_H #define BST_H *************** *** 28,34 **** #include "stdio.h" - /** - @authors Patrizio Bassi && Gianlorenzo D'Angelo - */ class Bst { --- 28,31 ---- Index: avlt.h =================================================================== RCS file: /cvsroot/avl/avl/src/avlt.h,v retrieving revision 1.7 retrieving revision 1.8 diff -C2 -d -r1.7 -r1.8 *** avlt.h 21 Jul 2004 16:58:20 -0000 1.7 --- avlt.h 6 Sep 2004 13:16:36 -0000 1.8 *************** *** 1,5 **** /*************************************************************************** ! * Copyright (C) 2004 by Gianlorenzo D'Angelo * ! * jah@notebook0 * * * * This program is free software; you can redistribute it and/or modify * --- 1,4 ---- /*************************************************************************** ! * Copyright (C) 2004 by Patrizio Bassi && Gianlorenzo D'Angelo * * * * This program is free software; you can redistribute it and/or modify * *************** *** 18,21 **** --- 17,21 ---- * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * ***************************************************************************/ + #ifndef AVLT_H #define AVLT_H *************** *** 26,32 **** using namespace std; ! /** ! @author Gianlorenzo D'Angelo ! */ class Avlt : public Bst { --- 26,30 ---- using namespace std; ! class Avlt : public Bst { Index: avlt.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avlt.cpp,v retrieving revision 1.6 retrieving revision 1.7 diff -C2 -d -r1.6 -r1.7 *** avlt.cpp 21 Jul 2004 16:58:20 -0000 1.6 --- avlt.cpp 6 Sep 2004 13:16:36 -0000 1.7 *************** *** 1,5 **** /*************************************************************************** ! * Copyright (C) 2004 by Gianlorenzo D'Angelo * ! * jah@notebook0 * * * * This program is free software; you can redistribute it and/or modify * --- 1,4 ---- /*************************************************************************** ! * Copyright (C) 2004 by Patrizio Bassi && Gianlorenzo D'Angelo * * * * This program is free software; you can redistribute it and/or modify * *************** *** 18,21 **** --- 17,21 ---- * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * ***************************************************************************/ + #include "avlt.h" *************** *** 444,448 **** { aux = ((Avlt *)getLeft())->getWrongs(); ! for(int i=0;i < aux.size();i++) v.push_back(aux[i]); } --- 444,448 ---- { aux = ((Avlt *)getLeft())->getWrongs(); ! for(uint i=0;i < aux.size();i++) v.push_back(aux[i]); } *************** *** 450,454 **** { aux = ((Avlt *)getRight())->getWrongs(); ! for(int i=0;i<aux.size();i++) v.push_back(aux[i]); } --- 450,454 ---- { aux = ((Avlt *)getRight())->getWrongs(); ! for(uint i=0;i<aux.size();i++) v.push_back(aux[i]); } Index: bst.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/bst.cpp,v retrieving revision 1.9 retrieving revision 1.10 diff -C2 -d -r1.9 -r1.10 *** bst.cpp 4 Aug 2004 15:31:36 -0000 1.9 --- bst.cpp 6 Sep 2004 13:16:36 -0000 1.10 *************** *** 2,6 **** * Copyright (C) 2004 by Patrizio Bassi && Gianlorenzo D'Angelo * * * - * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * --- 2,5 ---- *************** *** 506,510 **** //prendo la root e stampo tutto l'albero, appendo il primo valore e poi ricorsivamente tutti gli altri ! root=this->root(); msg = g_strdup_printf ("%d", root->getValue()); gtk_tree_store_append (GTK_TREE_STORE (store), &iter2,&iter1); --- 505,510 ---- //prendo la root e stampo tutto l'albero, appendo il primo valore e poi ricorsivamente tutti gli altri ! if (this->root() != NULL) root=this->root(); ! else root=this; msg = g_strdup_printf ("%d", root->getValue()); gtk_tree_store_append (GTK_TREE_STORE (store), &iter2,&iter1); Index: avl.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avl.cpp,v retrieving revision 1.9 retrieving revision 1.10 diff -C2 -d -r1.9 -r1.10 *** avl.cpp 4 Sep 2004 15:30:40 -0000 1.9 --- avl.cpp 6 Sep 2004 13:16:36 -0000 1.10 *************** *** 1,5 **** /*************************************************************************** ! * Copyright (C) 2004 by Gianlorenzo D'Angelo * ! * jah@notebook0 * * * * This program is free software; you can redistribute it and/or modify * --- 1,4 ---- /*************************************************************************** ! * Copyright (C) 2004 by Patrizio Bassi && Gianlorenzo D'Angelo * * * * This program is free software; you can redistribute it and/or modify * *************** *** 19,26 **** ***************************************************************************/ - #ifdef HAVE_CONFIG_H - #include <config.h> - #endif - #include "test.h" #include <iostream> --- 18,21 ---- *************** *** 29,79 **** using namespace std; - //era un test con la libreria dotneato, ma non mi compila con l'ultima versione - #if 0 - void print_test(){ - - - Agraph_t *g; - Agnode_t *n, *m; - Agedge_t *e; - Agsym_t *a; - - /*ma serve? no: initialize devi implementarla tu per ripulire la commandline (se vuoi...)*/ - /* argc = initialize( argc, argv ); */ - - /*Prende i parametri -T sul tipo file e -o sull'output file: vedi man dot*/ - dotneato_initialize( argc, argv ); - - /* Crea un semplice digrafo*/ - g = agopen( "g", AGDIGRAPH ); - n = agnode( g, "n" ); - m = agnode( g, "m" ); - e = agedge( g, n, m); - - /* Setto l'attributo di rendering: "colore blu"*/ - a = agnodeattr( g, "color", "blue" ); - agxset( n, a->index, "red" ); - - /* Calcola un layout per il grafo: qui neato*/ - neato_layout( g ); - /* twopi_layout( g );*/ - /* dot_layout( g );*/ - - /* Scrive il grafo, secondo le opzioni -T ed -o della linea di comando.*/ - dotneato_write( g ); - - /* Ripulisce le strutture dati usate per creare il layout*/ - neato_cleanup( g ); - /* twopi_cleanup( g );*/ - /* dot_cleanup( g );*/ - - /* Libera le risorse associate al grafo*/ - agclose( g ); - - - - } - #endif - int main(int argc, char *argv[]) { --- 24,27 ---- *************** *** 229,233 **** a.insert(-700); a.erase(1);*/ ! // Bst a(1); /* for (int i=0;i<500000;i++) --- 177,181 ---- a.insert(-700); a.erase(1);*/ ! Bst a(1); /* for (int i=0;i<500000;i++) *************** *** 241,248 **** a.erase( aaa ); }*/ ! Test t(0,1,100000); ! // a=*(t.getBst()); #ifndef GUI ! //a.print1(); #else GtkWidget *window; --- 189,196 ---- a.erase( aaa ); }*/ ! Test t(0,10,100000); ! a=*(t.getBst()); #ifndef GUI ! a.print1(); #else GtkWidget *window; Index: Makefile =================================================================== RCS file: /cvsroot/avl/avl/src/Makefile,v retrieving revision 1.5 retrieving revision 1.6 diff -C2 -d -r1.5 -r1.6 *** Makefile 4 Aug 2004 15:31:36 -0000 1.5 --- Makefile 6 Sep 2004 13:16:33 -0000 1.6 *************** *** 1,5 **** ! # AVL Project ifdef gtk_gui ! CC=g++ -O2 -Wall -W `pkg-config gtk+-2.0 --cflags` -DGUI else CC=g++ -O2 -Wall -W --- 1,6 ---- ! # AVL Project Makefile ! ifdef gtk_gui ! CC=g++ -O2 -Wall -W `pkg-config gtk+-2.0 --cflags` -DGUI -g else CC=g++ -O2 -Wall -W *************** *** 31,44 **** clean: ! rm *.o -f $(BINARY) shared: make library ! $(CC) avl.cpp -o $(BINARY) libavl.a library: $(CC) -fPIC -c bst.cpp -o bst.o $(CC) -fPIC -c avlt.cpp -o avlt.o ! $(CC) -shared -Wl,-soname,libavl.a -o libavl.a $(LIBS) -lc install: --- 32,46 ---- clean: ! rm *.o -f $(BINARY) libavl.a shared: make library ! $(CC) avl.cpp -o $(BINARY) libavl.a test.o library: $(CC) -fPIC -c bst.cpp -o bst.o $(CC) -fPIC -c avlt.cpp -o avlt.o ! $(CC) -fPIC -c test.cpp -o test.o ! $(CC) -shared -Wl,-soname,libavl.a -o libavl.a bst.o avlt.o -lc install: *************** *** 46,48 **** gui: ! make gtk_gui=true \ No newline at end of file --- 48,50 ---- gui: ! make gtk_gui=true Index: test.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/test.cpp,v retrieving revision 1.6 retrieving revision 1.7 diff -C2 -d -r1.6 -r1.7 *** test.cpp 4 Sep 2004 15:30:40 -0000 1.6 --- test.cpp 6 Sep 2004 13:16:36 -0000 1.7 *************** *** 1,2 **** --- 1,22 ---- + /*************************************************************************** + * Copyright (C) 2004 by Patrizio Bassi && Gianlorenzo D'Angelo * + * * + * This program is free software; you can redistribute it and/or modify * + * it under the terms of the GNU General Public License as published by * + * the Free Software Foundation; either version 2 of the License, or * + * (at your option) any later version. * + * * + * This program is distributed in the hope that it will be useful, * + * but WITHOUT ANY WARRANTY; without even the implied warranty of * + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * + * GNU General Public License for more details. * + * * + * You should have received a copy of the GNU General Public License * + * along with this program; if not, write to the * + * Free Software Foundation, Inc., * + * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * + ***************************************************************************/ + + #include "test.h" *************** *** 4,8 **** //if (avlt) delete avlt; //if (bst) delete bst; - } --- 24,27 ---- *************** *** 21,25 **** return bst; } ! void Test::Test_Init(int base_limit,int kind=0) { --- 40,44 ---- return bst; } ! //inizializza l'albero voluto void Test::Test_Init(int base_limit,int kind=0) { *************** *** 55,59 **** } ! void Test::Avl_Test(int upper_limit){ --- 74,78 ---- } ! //testa un AVL void Test::Avl_Test(int upper_limit){ *************** *** 109,113 **** } ! void Test::Bst_Test(int upper_limit) { --- 128,132 ---- } ! //testa un BST void Test::Bst_Test(int upper_limit) { *************** *** 162,166 **** } ! void Test::comparation(int base_tree_size, int upperbound ) { --- 181,185 ---- } ! //questo metodo fa un confronto delle prestazioni di un AVL e un BST void Test::comparation(int base_tree_size, int upperbound ) { *************** *** 208,211 **** --- 227,238 ---- Test::Test(int kind, int upperbound, int base_tree_size) { + /* 0 testa un albero AVL + 1 testa un albero BST + 2 testa entrambi e fa un confronto + + upperbound è il numero delle modifiche (ins/canc) + base_tree_size è la dimensione dell'albero + */ + tree_dimensions=base_tree_size; switch (kind){ |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-04 15:30:51
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv23151/src Modified Files: avl.cpp test.cpp test.h Log Message: niente di nuov solo qualche test Index: test.h =================================================================== RCS file: /cvsroot/avl/avl/src/test.h,v retrieving revision 1.7 retrieving revision 1.8 diff -C2 -d -r1.7 -r1.8 *** test.h 17 Jul 2004 19:48:28 -0000 1.7 --- test.h 4 Sep 2004 15:30:40 -0000 1.8 *************** *** 7,10 **** --- 7,11 ---- #include <time.h> #include <list> + #include <algorithm> using namespace std; Index: avl.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avl.cpp,v retrieving revision 1.8 retrieving revision 1.9 diff -C2 -d -r1.8 -r1.9 *** avl.cpp 4 Aug 2004 15:31:36 -0000 1.8 --- avl.cpp 4 Sep 2004 15:30:40 -0000 1.9 *************** *** 209,213 **** //prova->getAvlt()->print1(); ! Bst a(1 ); a.insert(3); a.insert(5); --- 209,213 ---- //prova->getAvlt()->print1(); ! /*Bst a(1 ); a.insert(3); a.insert(5); *************** *** 228,233 **** a.insert(-600); a.insert(-700); #ifndef GUI ! a.print1(); #else GtkWidget *window; --- 228,248 ---- a.insert(-600); a.insert(-700); + a.erase(1);*/ + // Bst a(1); + + /* for (int i=0;i<500000;i++) + { + int aaa=(rand()%1000000)-500000; + a.insert( aaa ); + } + for (int i=0;i<1000000;i++) + { + int aaa=(rand()%1000000)-500000; + a.erase( aaa ); + }*/ + Test t(0,1,100000); + // a=*(t.getBst()); #ifndef GUI ! //a.print1(); #else GtkWidget *window; Index: test.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/test.cpp,v retrieving revision 1.5 retrieving revision 1.6 diff -C2 -d -r1.5 -r1.6 *** test.cpp 17 Jul 2004 19:48:28 -0000 1.5 --- test.cpp 4 Sep 2004 15:30:40 -0000 1.6 *************** *** 2,8 **** Test::~Test() { ! ! if (avlt) delete avlt; ! if (bst) delete bst; } --- 2,7 ---- Test::~Test() { ! //if (avlt) delete avlt; ! //if (bst) delete bst; } *************** *** 29,33 **** srand ( time(NULL) ); - if (avlt && kind==0) { start = clock(); --- 28,31 ---- *************** *** 55,59 **** // getchar(); } - } --- 53,56 ---- *************** *** 93,98 **** //printf("x:%d value=%d\n",x,*IT); // printf("erased number %d\n",*IT); ! avlt=avlt->erase(*IT); ! if (IT!=insertion_list.end()) insertion_list.erase(IT); erase_counter++; } --- 90,97 ---- //printf("x:%d value=%d\n",x,*IT); // printf("erased number %d\n",*IT); ! if (IT!=insertion_list.end()){ ! avlt=avlt->erase(*IT); ! insertion_list.erase(IT); ! } erase_counter++; } *************** *** 124,128 **** srand ( time(NULL) ); - if (bst) { start=clock(); --- 123,126 ---- *************** *** 130,133 **** --- 128,132 ---- random=rand()%tree_dimensions; decision=rand()%2; + //decision=0; if (decision==0) { bst->insert(random); *************** *** 139,154 **** random_erase=rand()%insertion_list.size(); ! ! for ( IT=insertion_list.begin(), x=0; x<=random_erase && IT!=insertion_list.end(); ! IT++, x++) { if (x==random_erase) { //printf("x:%d value=%d\n",x,*IT); // printf("erased number %d\n",*IT); ! bst->erase(*IT); ! if (IT!=insertion_list.end()) insertion_list.erase(IT); erase_counter++; } ! } } else waste++; } --- 138,155 ---- random_erase=rand()%insertion_list.size(); ! for ( IT=insertion_list.begin(), x=0; x<=random_erase && IT!=insertion_list.end();IT++, x++) { if (x==random_erase) { //printf("x:%d value=%d\n",x,*IT); // printf("erased number %d\n",*IT); ! if (IT!=insertion_list.end()){ ! //bst->erase(*IT); ! //printf("%d\n",*IT); ! insertion_list.erase(IT); ! } ! erase_counter++; } ! } } else waste++; } |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-04 15:30:48
|
Update of /cvsroot/avl/avl In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv23151 Modified Files: TODO Log Message: niente di nuov solo qualche test Index: TODO =================================================================== RCS file: /cvsroot/avl/avl/TODO,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 *** TODO 4 Aug 2004 15:31:27 -0000 1.4 --- TODO 4 Sep 2004 15:30:39 -0000 1.5 *************** *** 2,3 **** --- 2,7 ---- - Finire di mettere i commenti in avlt.cpp + + - Quando chiudo la GUI va in segmentatio fault. + + - A volte mi da un sacco di errori di segmentation fault all'interno di funzioni GTK |
|
From: Patrizio B. <het...@us...> - 2004-09-04 14:09:55
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv10509 Modified Files: relazione.tex Added Files: ll_rot.eps ll_rot.png lr_rot.eps lr_rot.png Log Message: added simple and double rotations images finished the document. needs a review (of course..), please read it! --- NEW FILE: lr_rot.png --- (This appears to be a binary file; contents omitted.) --- NEW FILE: lr_rot.eps --- %!PS-Adobe-3.0 EPSF-3.0 %%Creator: ImageMagick 6.0.5 %%Title: lr_rot.eps %%CreationDate: Sat Sep 4 15:33:45 2004 %%BoundingBox: 0 0 575 795 %%HiResBoundingBox: 0 0 575 795 %%DocumentProcessColors: Black %%LanguageLevel: 3 %%Pages: 1 %%EndComments %%BeginProlog /ByteStreamDecodeFilter { /z exch def /r exch def /c exch def z 0 eq { /ASCII85Decode filter } if z 1 eq { << /K -1 /Columns c /Rows r >> /CCITTFaxDecode filter } if z 2 eq { /DCTDecode filter } if z 3 eq { /LZWDecode filter } if z 4 eq { /RunLengthDecode filter } if z 5 eq { /FlateDecode filter } if } bind def /DirectClassImageDict { colorspace 0 eq { /DeviceRGB setcolorspace << /ImageType 1 /Width columns /Height rows /BitsPerComponent 8 /DataSource pixel_stream /MultipleDataSources false /ImageMatrix [columns 0 0 rows neg 0 rows] /Decode [0 1 0 1 0 1] >> } { /DeviceCMYK setcolorspace << /ImageType 1 /Width columns /Height rows /BitsPerComponent 8 /DataSource pixel_stream /MultipleDataSources false /ImageMatrix [columns 0 0 rows neg 0 rows] /Decode compression 2 eq { [1 0 1 0 1 0 1 0] } { [0 1 0 1 0 1 0 1] } ifelse >> } ifelse } bind def /PseudoClassImageDict { % Colors in colormap image. currentfile buffer readline pop token pop /colors exch def pop colors 0 eq { % Depth of grayscale image. currentfile buffer readline pop token pop /bits exch def pop /DeviceGray setcolorspace << /ImageType 1 /Width columns /Height rows /BitsPerComponent bits /Decode [0 1] /ImageMatrix [columns 0 0 rows neg 0 rows] /DataSource pixel_stream >> } { % RGB colormap. /colormap colors 3 mul string def compression 0 eq { currentfile /ASCII85Decode filter colormap readstring pop pop } { currentfile colormap readstring pop pop } ifelse [ /Indexed /DeviceRGB colors 1 sub colormap ] setcolorspace << /ImageType 1 /Width columns /Height rows /BitsPerComponent 8 /Decode [0 255] /ImageMatrix [columns 0 0 rows neg 0 rows] /DataSource pixel_stream >> } ifelse } bind def /NonMaskedImageDict { class 1 eq { PseudoClassImageDict } { DirectClassImageDict } ifelse } bind def /MaskedImageDict { << /ImageType 3 /InterleaveType 3 /DataDict NonMaskedImageDict /MaskDict << /ImageType 1 /Width columns /Height rows /BitsPerComponent 1 /DataSource mask_stream /MultipleDataSources false /ImageMatrix [ columns 0 0 rows neg 0 rows] /Decode [ 0 1 ] >> >> } bind def /ClipImage {} def /DisplayImage { /buffer 512 string def % Translation. currentfile buffer readline pop token pop /x exch def token pop /y exch def pop x y translate % Image size and font size. currentfile buffer readline pop token pop /x exch def token pop /y exch def pop currentfile buffer readline pop token pop /pointsize exch def pop x y scale % Clipping path. currentfile buffer readline pop token pop /clipped exch def pop % EPS. currentfile buffer readline pop token pop /sp exch def pop % Image pixel size. currentfile buffer readline pop token pop /columns exch def token pop /rows exch def pop % Colorspace (RGB/CMYK). currentfile buffer readline pop token pop /colorspace exch def pop % Transparency. currentfile buffer readline pop token pop /alpha exch def pop % Stencil mask? currentfile buffer readline pop token pop /stencil exch def pop % Image class (direct/pseudo). currentfile buffer readline pop token pop /class exch def pop % Compression type. currentfile buffer readline pop token pop /compression exch def pop % Clip and render. /pixel_stream currentfile columns rows compression ByteStreamDecodeFilter def clipped { ClipImage } if alpha stencil not and { MaskedImageDict mask_stream resetfile } { NonMaskedImageDict } ifelse stencil { 0 setgray imagemask } { image } ifelse grestore sp { showpage } if } bind def %%EndProlog %%Page: 1 1 %%PageBoundingBox: 0 0 575 795 %%PageProcessColors: Black /ClipImage {} def userdict begin %%BeginData: 7869 BINARY Bytes DisplayImage 0 0 575 795 12.000000 false false 575 795 0 false false 1 3 0 1 |
|
From: Gianlorenzo D'A. <gia...@ti...> - 2004-09-03 17:01:16
|
La situazione =E8 pi=F9 grave di quanto credessi. credo di capire che gli errori ci sono sia in avlt, bst e test. La cosa strana =E8 che capitano solo quando uso la classe di test e pure con input piccoli. Adesso ci penso su e poi vedo di trovare una soluzione |
|
From: Gianlorenzo D'A. <gia...@ti...> - 2004-09-03 15:58:29
|
Ho fatto un po di test sulla cancellazione senza utilizzare la classe test e pare che va. Cancellando un ordine di 1 milione di elementi si coprono tutti i casi (che sono una decina in tutto) e non succede mai niente : ne seg fault ne loop infiniti. Utilizzando la classe test invece gi=E0 a 10 elementi si verificano error= i tipo segmentation fault oppure il famigerato freeze (che non so perch=E9 = a te ti frizza, forse perch=E9 usi il debugger, ma a me corrisponde ad un ciclo infinito che occupa tutta la CPU). La conclusione =E8 che l'errore si trova in test.cpp. Guardando un po il codice velocemente mi pare di vedere qualcosa di poco controllato a livello di iteratori. Adesso ci do uno sguardo. |
|
From: Patrizio B. <het...@us...> - 2004-08-23 13:46:28
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv25179 Modified Files: relazione.tex Log Message: giangi, dacci un'occhiata, manca solo la parte in cui spiego gli avl. non so se la parte applicazione va trattata o no, che ne dici? Index: relazione.tex =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.tex,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** relazione.tex 8 Aug 2004 09:44:09 -0000 1.3 --- relazione.tex 23 Aug 2004 13:46:15 -0000 1.4 *************** *** 50,60 **** In questo ambito è collocato questo lavoro: lo studio e implementazione degli alberi BST (Binary Search Tree) "semplici", e i BST gestiti tramite l'algoritmo AVL (anagramma derivato dal nome dei loro ideatori: Adelson-Velskii and Landis, 1962) per individuare quali sono i vantaggi e svantaggi di entrambe le soluzioni. ! Nel prossimo capitolo verrà illustrato in generale in funzionamento e l'idea alla base delle tecniche, poi verrà ! esaminata in generale l'implementazione proposta e le conclusioni che si possono trarre dopo aver sfruttato ed eseguito il codice prodotto. \chapter{Breve Panoramica} La premessa di questo capitolo è quella di non essere assolutamente un riferimento esaustivo sugli alberi AVL e BST. Il contesto in cui si colloca questo lavoro è quello dei Dizionari. In ogni problema, di qualsiasi tipo esso sia, si ha a che fare con una certa tipologia e quantità di dati; generalmente si può modellare un problema utilizzando un tipo di dato generico, non ben specificato. ! Questo è il caso del Dizionario: un tipo di dato astratto (ADT, Abstract Data Type) che rappresenti un insieme di tipi di oggetti al quale vengono applicate operazioni di inserimento, cancellazione, ricerca. Sarebbe inutile infatti conoscere degli oggetti senza avere possibilità di manipolarli o gestirli. La gestione di un dizionario può chiaramente essere effettuata in una infinità di soluzioni, come array (e qui si potrebbe parlare della disposizione degli oggetti nel contenitore array stesso), liste (con tutti i vari tipi di concatenazione) oppure alberi. Quest'ultima soluzione offre numerose alternative, tra queste ci sono proprio gli alberi BST e AVL. --- 50,61 ---- In questo ambito è collocato questo lavoro: lo studio e implementazione degli alberi BST (Binary Search Tree) "semplici", e i BST gestiti tramite l'algoritmo AVL (anagramma derivato dal nome dei loro ideatori: Adelson-Velskii and Landis, 1962) per individuare quali sono i vantaggi e svantaggi di entrambe le soluzioni. ! Nel prossimo capitolo verrà illustrato in generale il funzionamento e l'idea alla base delle tecniche, poi verrà ! esaminata l'implementazione proposta e le conclusioni che si possono trarre dopo aver sfruttato ed eseguito il codice prodotto. \chapter{Breve Panoramica} La premessa di questo capitolo è quella di non essere assolutamente un riferimento esaustivo sugli alberi AVL e BST. + Il contesto in cui si colloca questo lavoro è quello dei Dizionari. In ogni problema, di qualsiasi tipo esso sia, si ha a che fare con una certa tipologia e quantità di dati; generalmente si può modellare un problema utilizzando un tipo di dato generico, non ben specificato. ! Questo è il caso del Dizionario: un tipo di dato astratto (ADT, Abstract Data Type) che rappresenti un insieme di tipi di oggetti al quale vengono applicate operazioni di inserimento, cancellazione, ricerca. Sarebbe inutile infatti conoscere degli oggetti senza avere la possibilità di manipolarli o gestirli. La gestione di un dizionario può chiaramente essere effettuata in una infinità di soluzioni, come array (e qui si potrebbe parlare della disposizione degli oggetti nel contenitore array stesso), liste (con tutti i vari tipi di concatenazione) oppure alberi. Quest'ultima soluzione offre numerose alternative, tra queste ci sono proprio gli alberi BST e AVL. *************** *** 80,89 **** In questo modo, se l'albero è composto da n elementi, la ricerca nel caso peggiore costerà O(n), quindi un costo lineare, che in alcune circostanze può essere ritenuto troppo elevato. E' sorto quindi il problema di tenere l'albero bilanciato in modo di avere la ricerca più efficente possibile. ! Chiaramente, come già detto in precedenza, avere un costo minore nella ricerca costringerà a performance infariori in altre ! situazioni. ! Il concetto di bilanciamento può essere riassunto nel mantenere un albero i cui rami hanno tutti la stessa lunghezza (con starti di +/-1), in modo da pagare sempre un costo logaritmico per la ricerca. ! Va considerato che questo costo è particolarmente importante, poichè è evidente che anche le operazioni di cancellazione e inserimento contengono sempre una ricerca preliminare (per trovare dove inserire e per trovare il nodo da cancellare). Il bilanciamento di un albero può essere modificato a causa di inserimenti e cancellazioni: durante queste fasi va quindi aggiunta l'attività di ribilanciamento. Nell' implementazione BST il caso peggiore delle due operazioni è uguale a O(n), ancora un costo lineare. Sorge quindi la necessità di mantenere bilanciato l'albero in modo più efficiente: l'implementazione AVL è una buona soluzione. Gli alberi AVL sono degli alberi BST, con associata un'informazione aggiuntiva per tutti i nodi: il fattore di bilanciamento (Fsb). L'Fsb è un intero che può assumere i valori 0 e +/-1 e rappresenta la differenza tra l'altezza del sotto albero sinistro e il sottoalbero destro di ogni nodo. I valori permettono quindi uno "sbilanciamento" di un solo livello. --- 81,90 ---- In questo modo, se l'albero è composto da n elementi, la ricerca nel caso peggiore costerà O(n), quindi un costo lineare, che in alcune circostanze può essere ritenuto troppo elevato. E' sorto quindi il problema di tenere l'albero bilanciato in modo di avere la ricerca più efficente possibile. ! ! Il concetto di bilanciamento può essere riassunto nel mantenere un albero i cui rami hanno tutti la stessa lunghezza (con differenze di +/-1), in modo da pagare sempre un costo logaritmico per la ricerca. ! Va considerato che questo costo è particolarmente importante, poichè è evidente che anche le operazioni di cancellazione e inserimento contengono sempre una ricerca preliminare (per trovare la posizione in cui inserire e per trovare il nodo da cancellare). Il bilanciamento di un albero può essere modificato a causa di inserimenti e cancellazioni: durante queste fasi va quindi aggiunta l'attività di ribilanciamento. Nell' implementazione BST il caso peggiore delle due operazioni è uguale a O(n), ancora un costo lineare. Sorge quindi la necessità di mantenere bilanciato l'albero in modo più efficiente: l'implementazione AVL è una buona soluzione. + Gli alberi AVL sono degli alberi BST, con associata un'informazione aggiuntiva per tutti i nodi: il fattore di bilanciamento (Fsb). L'Fsb è un intero che può assumere i valori 0 e +/-1 e rappresenta la differenza tra l'altezza del sotto albero sinistro e il sottoalbero destro di ogni nodo. I valori permettono quindi uno "sbilanciamento" di un solo livello. *************** *** 99,106 **** \label{fig:avl} \end{figure} ! Oltre al rilassamento del concetto di bilanciamento, gli AVL incorporando anche l'informazione relativa al Fsb e la sua gestione che ovviamente avrà un costo. L'idea è quella di spendere del tempo nel mantenere il bilanciamento dell'albero in modo da avere costi logaritmici per le operazioni fondamentali che interessano. ! \chapter{Applicazione}\label{Applicazione} \chapter{Conclusioni}\label{Conclusioni} \end{document} --- 100,122 ---- \label{fig:avl} \end{figure} ! Oltre al rilassamento del concetto di bilanciamento, gli AVL incorporano anche l'informazione relativa al Fsb e la sua gestione che ovviamente avrà un costo. L'idea è quella di spendere del tempo nel mantenere il bilanciamento dell'albero in modo da avere costi logaritmici per le operazioni fondamentali che interessano. ! INSERIMENTO ! CANCELLAZIONE ! ROTAZIONI + \chapter{Applicazione}\label{Applicazione} + La struttura dell'applicazione è stata divisa in quattro parti fondamentali. + Due sono le parti relative alle strutture dati e agli algoritmi AVL (avl.cpp e avl.h) e BST (bst.cpp e bst.h). + Le altre due parti sono un "client" per generare gli alberi, fare test di inserimento e cancellazione, e un programma in GTK per la grafica a video degli alberi tramite una gradevole GUI. \chapter{Conclusioni}\label{Conclusioni} + Nei test effettuati, ripetendo numerose volte la costruzione di alberi AVL e BST, e poi applicandovi numerose modifiche casuali di tipo inserimento e cancellazione si è notato come la differenza tra le due implementazioni sia davvero minima e praticamente non percettibile. + Se si considera la differenza di costi (uno lineare, l'altro logaritmico) questo risultato appare impossibile. + In realtà il risultato è giustificabile con diversi punti: + \begin{itemize} + \item il generatore di numeri casuali, in realtà non è puramente casuale. E' un limite di quasi tutti i sistemi operativi e processori attuali + \item la misurazione delle prestazione non è accurata, il programma realizzato è soggetto a scheduler e quindi non è detto che il sistema operativo assegni al programma le stesse risorse in ogni momento + \item la quantità di numeri generata e la loro grandezza non è in grado si mettere in seria difficoltà i processori attuali e le differenze di tempo sono minime + \item non è sicuro che l'implementazione proposta sia la più performante in entrambi i casi. L'uso di strutture dati differenti, compilatori e ottimizzazione specifiche per architetture e sistemi operativi potrebbe in qualche modo sbilanciare a favore di una implementazione l'esito dei test. + \end{itemize} \end{document} |
|
From: Patrizio B. <het...@us...> - 2004-08-08 09:44:18
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv17366/docs Modified Files: relazione.tex Added Files: AVL.eps AVL.png BST.eps BST.png Log Message: little improvements --- NEW FILE: AVL.png --- (This appears to be a binary file; contents omitted.) --- NEW FILE: BST.png --- (This appears to be a binary file; contents omitted.) --- NEW FILE: BST.eps --- %!PS-Adobe-3.0 EPSF-3.0 Resource-ProcSet %%Creator: (ImageMagick) %%Title: (BST.eps) %%CreationDate: (Sun Aug 8 10:53:47 2004) %%BoundingBox: 0 0 416 158 %%HiResBoundingBox: 0 0 416 158 %%LanguageLevel: 3 %%%%Pages: 1 %%EndComments %%Page: 1 1 %%PageBoundingBox: 0 0 416 158 currentfile /FlateDecode filter /ReusableStreamDecode filter xÚí±Ü6CpA!8 àBPÁ!( ÎW]º.µç |
|
From: Patrizio B. <het...@us...> - 2004-08-04 15:32:07
|
Update of /cvsroot/avl/avl In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv12343 Modified Files: TODO Log Message: GTK GUI added Index: TODO =================================================================== RCS file: /cvsroot/avl/avl/TODO,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** TODO 18 Jul 2004 16:57:10 -0000 1.3 --- TODO 4 Aug 2004 15:31:27 -0000 1.4 *************** *** 1,5 **** - -Fare funzione (o classe) che visualizzi decentemente un albero binario (anche qualsiasi non per forza bst o avl) - - Controllare e fixare i punti in cui freeza. dovrebbe essere in bst. non è solo quando l'albero è vuoto. ! - Finire di mettere i commenti in avlt.cpp \ No newline at end of file --- 1,3 ---- - Controllare e fixare i punti in cui freeza. dovrebbe essere in bst. non è solo quando l'albero è vuoto. ! - Finire di mettere i commenti in avlt.cpp |
|
From: Patrizio B. <het...@us...> - 2004-08-04 15:31:46
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv12343/src Modified Files: Makefile avl.cpp bst.cpp bst.h Log Message: GTK GUI added Index: bst.h =================================================================== RCS file: /cvsroot/avl/avl/src/bst.h,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** bst.h 25 Jun 2004 16:05:57 -0000 1.3 --- bst.h 4 Aug 2004 15:31:36 -0000 1.4 *************** *** 1,5 **** /*************************************************************************** ! * Copyright (C) 2004 by Gianlorenzo D'Angelo * ! * jah@notebook0 * * * * This program is free software; you can redistribute it and/or modify * --- 1,5 ---- /*************************************************************************** ! * Copyright (C) 2004 by Patrizio Bassi && Gianlorenzo D'Angelo * ! * * * * * This program is free software; you can redistribute it and/or modify * *************** *** 21,28 **** #define BST_H #include "stdio.h" /** ! @author Gianlorenzo D'Angelo */ class Bst { --- 21,33 ---- #define BST_H + #ifdef GUI + #include <gtk/gtk.h> + #include <glib.h> + #endif + #include "stdio.h" /** ! @authors Patrizio Bassi && Gianlorenzo D'Angelo */ class Bst { *************** *** 36,39 **** --- 41,49 ---- void erase(); void print_ric( int, int ); + #ifdef GUI + void ric(); + #else + void c_print(char*); + #endif public: *************** *** 71,75 **** --- 81,89 ---- void print(); + #ifndef GUI void print1(); + #else + GtkWidget* print1(); + #endif }; Index: bst.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/bst.cpp,v retrieving revision 1.8 retrieving revision 1.9 diff -C2 -d -r1.8 -r1.9 *** bst.cpp 18 Jul 2004 16:57:10 -0000 1.8 --- bst.cpp 4 Aug 2004 15:31:36 -0000 1.9 *************** *** 1,5 **** /*************************************************************************** ! * Copyright (C) 2004 by Gianlorenzo D'Angelo * ! * jah@notebook0 * * * * This program is free software; you can redistribute it and/or modify * --- 1,5 ---- /*************************************************************************** ! * Copyright (C) 2004 by Patrizio Bassi && Gianlorenzo D'Angelo * ! * * * * * This program is free software; you can redistribute it and/or modify * *************** *** 18,23 **** * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * ***************************************************************************/ #include "bst.h" - //#include <string.h> Bst::Bst() --- 18,23 ---- * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * ***************************************************************************/ + #include "bst.h" Bst::Bst() *************** *** 356,360 **** } ! int c_print(char *string){ // for colors and style. --- 356,364 ---- } ! // le prossime due funzioni non utilizzano le librerie grafiche GTK ! // ma la semplice stampa a colori con delle printf ! #ifndef GUI ! // funzione di utilità per stampare a colori ! void Bst::c_print(char *string){ // for colors and style. *************** *** 395,399 **** printf("[%i;%i;40m",NORMAL,GRAY); } ! void Bst::print1() { --- 399,403 ---- printf("[%i;%i;40m",NORMAL,GRAY); } ! // usa c_print per stampare a colori. Funzione ricorsiva void Bst::print1() { *************** *** 428,429 **** --- 432,523 ---- } + #else + /* GTK GUI. Utilizza una visualizzazione ad albero + permettendo di espandere e ridurre i vari rami + */ + + GtkTreeIter iter1,iter2; //non si possono utilizzare i puntatori, per problemi di inizializzazione del NULL (il primo) puntatore + GtkTreeStore *store; + + void Bst::ric() + { + + GtkTreeIter aux; + gchar *msg=NULL; + + aux=iter2; //ricorda a che punto stiamo, appende tutti i rami destri e riprende + if( getRight() ) + { + msg=NULL; + msg = g_strdup_printf ("(son of: %d) Right Value: %d", getValue(),getRight()->getValue()); + gtk_tree_store_append (GTK_TREE_STORE (store), &iter1,&iter2); + gtk_tree_store_set (GTK_TREE_STORE (store), &iter1, 0, msg, -1); + if (msg) g_free (msg); + + iter2=iter1; + getRight()->ric(); + } + iter2=aux; //riprende dopo aver appeso i rami destri, e termina con i rami sinistri + if( getLeft() ) + { + msg=NULL; + msg = g_strdup_printf ("(son of: %d) Left Value: %d", getValue(),getLeft()->getValue()); + gtk_tree_store_append (GTK_TREE_STORE (store), &iter1,&iter2); + gtk_tree_store_set (GTK_TREE_STORE (store), &iter1, 0, msg, -1); + if (msg) g_free (msg); + + iter2=iter1; + getLeft()->ric(); + + } + + } + + + GtkWidget* Bst::print1() + { + GtkWidget *scrolled_window; + GtkWidget *tree_view; + + GtkCellRenderer *cell; + GtkTreeViewColumn *column; + + Bst* root; + gchar* msg; + + //creo una contenitore che sia scrollabile + scrolled_window = gtk_scrolled_window_new (NULL, NULL); + gtk_scrolled_window_set_policy (GTK_SCROLLED_WINDOW (scrolled_window), GTK_POLICY_AUTOMATIC, GTK_POLICY_AUTOMATIC); + + //creo il contenitore dell'albero + store=gtk_tree_store_new(1,G_TYPE_STRING); + + //creo l'albero e lo lego al contenitore + tree_view = gtk_tree_view_new (); + gtk_scrolled_window_add_with_viewport (GTK_SCROLLED_WINDOW (scrolled_window), tree_view); + + //link dell'albero e il suo contenitore + gtk_tree_view_set_model (GTK_TREE_VIEW (tree_view), GTK_TREE_MODEL (store)); + gtk_widget_show (tree_view); + + //needed workaround - aggiungo un primo elemento root + gtk_tree_store_append (GTK_TREE_STORE (store), &iter1,NULL); + gtk_tree_store_set (GTK_TREE_STORE (store), &iter1, 0, "Here Begins AVL Tree Diplay", -1); + + //prendo la root e stampo tutto l'albero, appendo il primo valore e poi ricorsivamente tutti gli altri + root=this->root(); + msg = g_strdup_printf ("%d", root->getValue()); + gtk_tree_store_append (GTK_TREE_STORE (store), &iter2,&iter1); + gtk_tree_store_set (GTK_TREE_STORE (store), &iter2, 0, msg, -1); + g_free(msg); + + root->ric(); + + //finalizzazione: creo una cella e metto in una colonna, che poi metto nell'albero. + cell = gtk_cell_renderer_text_new (); + column = gtk_tree_view_column_new_with_attributes ("AVL Tree",cell,"text", 0, NULL); + gtk_tree_view_append_column (GTK_TREE_VIEW (tree_view), GTK_TREE_VIEW_COLUMN (column)); + + return scrolled_window; //ritorno l'oggetto, nel main viene visualizzato e appeso alla finestra principale. + } + #endif Index: Makefile =================================================================== RCS file: /cvsroot/avl/avl/src/Makefile,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 *** Makefile 17 Jul 2004 12:34:55 -0000 1.4 --- Makefile 4 Aug 2004 15:31:36 -0000 1.5 *************** *** 1,5 **** # AVL Project ! CC=g++ -O2 LIBS=avlt.o bst.o test.o avl.o BINARY=avl --- 1,14 ---- # AVL Project ! ifdef gtk_gui ! CC=g++ -O2 -Wall -W `pkg-config gtk+-2.0 --cflags` -DGUI ! else ! CC=g++ -O2 -Wall -W ! endif LIBS=avlt.o bst.o test.o avl.o + ifdef gtk_gui + GTKLIBS=`pkg-config gtk+-2.0 --libs` + else + GTKLIBS= + endif BINARY=avl *************** *** 19,23 **** $(BINARY): $(LIBS) ! $(CC) -o $(BINARY) $(LIBS) clean: --- 28,32 ---- $(BINARY): $(LIBS) ! $(CC) -o $(BINARY) $(LIBS) $(GTKLIBS) clean: *************** *** 32,33 **** --- 41,48 ---- $(CC) -fPIC -c avlt.cpp -o avlt.o $(CC) -shared -Wl,-soname,libavl.a -o libavl.a $(LIBS) -lc + + install: + echo "not yet ready" + + gui: + make gtk_gui=true \ No newline at end of file Index: avl.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avl.cpp,v retrieving revision 1.7 retrieving revision 1.8 diff -C2 -d -r1.7 -r1.8 *** avl.cpp 17 Jul 2004 19:48:27 -0000 1.7 --- avl.cpp 4 Aug 2004 15:31:36 -0000 1.8 *************** *** 23,27 **** #endif - //#include "avlt.h" #include "test.h" #include <iostream> --- 23,26 ---- *************** *** 30,33 **** --- 29,79 ---- using namespace std; + //era un test con la libreria dotneato, ma non mi compila con l'ultima versione + #if 0 + void print_test(){ + + + Agraph_t *g; + Agnode_t *n, *m; + Agedge_t *e; + Agsym_t *a; + + /*ma serve? no: initialize devi implementarla tu per ripulire la commandline (se vuoi...)*/ + /* argc = initialize( argc, argv ); */ + + /*Prende i parametri -T sul tipo file e -o sull'output file: vedi man dot*/ + dotneato_initialize( argc, argv ); + + /* Crea un semplice digrafo*/ + g = agopen( "g", AGDIGRAPH ); + n = agnode( g, "n" ); + m = agnode( g, "m" ); + e = agedge( g, n, m); + + /* Setto l'attributo di rendering: "colore blu"*/ + a = agnodeattr( g, "color", "blue" ); + agxset( n, a->index, "red" ); + + /* Calcola un layout per il grafo: qui neato*/ + neato_layout( g ); + /* twopi_layout( g );*/ + /* dot_layout( g );*/ + + /* Scrive il grafo, secondo le opzioni -T ed -o della linea di comando.*/ + dotneato_write( g ); + + /* Ripulisce le strutture dati usate per creare il layout*/ + neato_cleanup( g ); + /* twopi_cleanup( g );*/ + /* dot_cleanup( g );*/ + + /* Libera le risorse associate al grafo*/ + agclose( g ); + + + + } + #endif + int main(int argc, char *argv[]) { *************** *** 123,126 **** --- 169,177 ---- // printf("%d",b->getValue()); #endif + + + + + /* // 0= test avl *************** *** 148,152 **** printf("Comparation on the way, wait\n"); prova_bst = new Test(2,upper_bound,base_tree); ! }*/ //Test *prova; //prova = new Test(1,5,1); --- 199,206 ---- printf("Comparation on the way, wait\n"); prova_bst = new Test(2,upper_bound,base_tree); ! } ! */ ! ! //Test *prova; //prova = new Test(1,5,1); *************** *** 156,160 **** Bst a(1 ); - a.insert(3); a.insert(5); --- 210,213 ---- *************** *** 175,179 **** a.insert(-600); a.insert(-700); a.print1(); ! return EXIT_SUCCESS; } --- 228,264 ---- a.insert(-600); a.insert(-700); + #ifndef GUI a.print1(); ! #else ! GtkWidget *window; ! GtkWidget *vpaned; ! GtkWidget *node_list; ! ! gtk_init (&argc, &argv); ! ! char* fullname="AVL Tree Visualization"; ! ! window = gtk_window_new (GTK_WINDOW_TOPLEVEL); ! ! gtk_window_set_title (GTK_WINDOW (window), fullname); ! ! g_signal_connect (G_OBJECT (window), "destroy", G_CALLBACK (gtk_main_quit), NULL); ! ! gtk_container_set_border_width (GTK_CONTAINER (window), 15); ! gtk_widget_set_size_request (GTK_WIDGET (window), 500, 450); ! ! vpaned = gtk_vpaned_new (); ! gtk_container_add (GTK_CONTAINER (window), vpaned); ! gtk_widget_show (vpaned); ! ! node_list = a.print1(); ! ! gtk_paned_add1 (GTK_PANED (vpaned), node_list); ! gtk_widget_show (node_list); ! ! gtk_widget_show (window); ! ! gtk_main (); ! #endif ! return EXIT_SUCCESS; } |
|
From: Patrizio B. <het...@us...> - 2004-08-04 15:31:45
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv12343/docs Modified Files: relazione.tex Log Message: GTK GUI added Index: relazione.tex =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.tex,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** relazione.tex 18 Jul 2004 10:40:15 -0000 1.1 --- relazione.tex 4 Aug 2004 15:31:28 -0000 1.2 *************** *** 30,34 **** Tuttavia, è noto che l'hardware a sè stante è inutile. E' (e sarà) sempre necessario del software per comandare tutte le varie periferiche in questione; ! questa cosa fa capire quanto una macchian di per sè velocissima possa essere inutilizabile se il software che la comanda contiene errori o è lento. --- 30,34 ---- Tuttavia, è noto che l'hardware a sè stante è inutile. E' (e sarà) sempre necessario del software per comandare tutte le varie periferiche in questione; ! questa cosa fa capire quanto una macchina di per sè velocissima possa essere inutilizabile se il software che la comanda contiene errori o è lento. *************** *** 73,76 **** --- 73,82 ---- Il concetto di bilanciamento può essere riassunto nel mantenere un albero i cui rami hanno tutti la stessa lunghezza (con starti di +/-1), in modo da pagare un costo logaritmico per la ricerca. Va considerato che questo costo è particolarmente importante, poichè è evidente che anche le operazioni di cancellazione e inserimento contengono una ricerca priliminare (per trovare dove inserire e per trovare il nodo da cancellare). + Il bilanciamento di un albero può essere modificato a causa di inserimenti e cancellazioni: durante queste fasi va quindi aggiunta l'attività di ribilanciamento. Nell' implementazione BST il caso peggiore delle due operazioni è uguale a O(n), lineare. + Sorge quindi la necessità di mantenere bilanciato l'albero in modo più efficiente. + Gli alberi AVL sono degli alberi BST, con associata un'informazione aggiuntiva per tutti i nodi: il fattore di bilanciamento (Fsb). + L'Fsb è un intero che può assumere i valori 0 e +/-1 e rappresenta la differenza tra l'altezza del sotto albero sinistro e il sottoalbero destro di ogni nodo. I valori permettono quindi uno "sbilanciamento" di un solo livello. + Quando un Fsb diventa di +/-2 l'albero si è sbilanciato e va corretto. + E' chiaro che si sta usando una nozione di bilanciamento un po' meno restrittiva, dato che si permette la differenza di un livello al massimo. Questo implica complicazioni dal punto dell'analisi del caso peggiore, tuttavia gli autori dell'AVL han dimostrato che |
|
From: Gianlorenzo D'A. <gia...@ti...> - 2004-07-21 17:04:29
|
Ho cambiato il modo di calcolare il fdb per il fatto che mi avevi detto della velocit=E0 negli avl. In effetti questa dovrebbe essere un'operazione secondaria ma in realt=E0 risulta praticamente predominante= =2E Ho fatto degli esperimenti su 100.000 1.000.000 di inserimenti (a mano per=F2 senza utilizzare la tua classe perch=E9 non mi andava di vedere co= me funziona) e la differenza si vede ad occhio. Ci poche frazioni di secondo per gli Avl e circa di 1 o 2 secondi per i bst mentre prima ci metteva un eternit=E0 (anche mezzo minuto). Fai qualche prova con la classe che hai fatto tu che ti misura bene il tempo. Quando ho un po di tempo mi dedico all'errore nella cancellazione dei bst. Mi puoi fare una lista di operazioni che devo fare per farlo capitare? Io ho fatto delle prove a caso ma non mi si =E8 mai verificato (non =E8 che ci ho dedicato troppo tempo) |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-07-21 16:58:30
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv1178/src Modified Files: avlt.cpp avlt.h Log Message: changed fdb handling Index: avlt.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avlt.cpp,v retrieving revision 1.5 retrieving revision 1.6 diff -C2 -d -r1.5 -r1.6 *** avlt.cpp 18 Jul 2004 16:57:10 -0000 1.5 --- avlt.cpp 21 Jul 2004 16:58:20 -0000 1.6 *************** *** 29,52 **** : Bst(val) { ! setFdb( s ); } /** Imposta il Fattore di Bilanciamento a s*/ ! void Avlt::setFdb( int s ) { ! fdb = s; } ! /** Calcola il FdB del nodo corrente*/ void Avlt::setFdb() { //Il fattore di bilanciamento è la differenza tra l'altezza del sottoallbero di destra e quella del sottoalbero di sinistra ! int l, r; ! l = r = 0; ! if( getLeft() ) ! l = getLeft()->height() + 1; //Altezza del sottoalbero di sinistra ! if( getRight() ) ! r = getRight()->height() + 1; //Altezza del sottoalbero di destra ! setFdb( l-r ); } --- 29,57 ---- : Bst(val) { ! setHeight( s ); } /** Imposta il Fattore di Bilanciamento a s*/ ! /*void Avlt::setFdb( int s ) { ! setHeight(s); } ! */ /** Calcola il FdB del nodo corrente*/ void Avlt::setFdb() { //Il fattore di bilanciamento è la differenza tra l'altezza del sottoallbero di destra e quella del sottoalbero di sinistra ! if(isLeaf()) ! setHeight(0); ! else ! { ! int l, r; ! l = r = 0; ! if( getLeft() ) ! l = ((Avlt *)getLeft())->getHeight(); // l contiene l'altezza del sottoalbero sinistro ! if( getRight() ) ! r = ((Avlt *)getRight())->getHeight(); // r contiene l'altezza del sottoalbero destro ! setHeight( 1 + ( l>r ? l : r ) ); // viene restituita l'altezza del sottoalbero più lungo incrementata di 1 ! } } *************** *** 67,71 **** int Avlt::getFdb() { ! return fdb; } --- 72,92 ---- int Avlt::getFdb() { ! int l, r; ! l = r = 0; ! if( getLeft() ) ! l = ((Avlt *)getLeft())->getHeight() + 1; //Altezza del sottoalbero di sinistra ! if( getRight() ) ! r = ((Avlt *)getRight())->getHeight() + 1; //Altezza del sottoalbero di destra ! return l-r; ! } ! ! int Avlt::getHeight() ! { ! return h; ! } ! ! void Avlt::setHeight(int he) ! { ! h = he; } *************** *** 96,99 **** --- 117,121 ---- ((Avlt *)(aux->getLeft()))->setFdb(); + aux->setFdb(); return aux; *************** *** 129,132 **** --- 151,155 ---- ((Avlt *)(aux->getRight()))->setFdb(); + aux->setFdb(); return aux; *************** *** 163,166 **** --- 186,190 ---- getLeft()->setParent(this); getLeft()->setValue(key); + ((Avlt *)getLeft())->setHeight(0); setFdb(); } *************** *** 186,189 **** --- 210,214 ---- getRight()->setParent(this); getRight()->setValue(key); + ((Avlt *)getRight())->setHeight(0); setFdb(); } Index: avlt.h =================================================================== RCS file: /cvsroot/avl/avl/src/avlt.h,v retrieving revision 1.6 retrieving revision 1.7 diff -C2 -d -r1.6 -r1.7 *** avlt.h 18 Jul 2004 16:57:10 -0000 1.6 --- avlt.h 21 Jul 2004 16:58:20 -0000 1.7 *************** *** 32,36 **** { private: ! int fdb; //Fattore di Bilanciamento Avlt *rightRotate(); Avlt *leftRotate(); --- 32,37 ---- { private: ! // int fdb; //Fattore di Bilanciamento ! int h; Avlt *rightRotate(); Avlt *leftRotate(); *************** *** 43,50 **** ~Avlt(); ! void setFdb( int ); void setFdb(); void setFdb(Avlt *, Avlt *); int getFdb(); bool checkBalance(); --- 44,53 ---- ~Avlt(); ! // void setFdb( int ); void setFdb(); void setFdb(Avlt *, Avlt *); int getFdb(); + void setHeight(int); + int getHeight(); bool checkBalance(); |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-07-21 16:58:28
|
Update of /cvsroot/avl/avl In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv1178 Modified Files: ChangeLog Log Message: changed fdb handling Index: ChangeLog =================================================================== RCS file: /cvsroot/avl/avl/ChangeLog,v retrieving revision 1.6 retrieving revision 1.7 diff -C2 -d -r1.6 -r1.7 *** ChangeLog 18 Jul 2004 16:57:10 -0000 1.6 --- ChangeLog 21 Jul 2004 16:58:19 -0000 1.7 *************** *** 1,2 **** --- 1,6 ---- + --==21.07.2004==-- + <jah2003>: + -changed fdb handling. + --==18.07.2004==-- <jah2003>: |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-07-18 16:57:20
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv20402/src Modified Files: avlt.cpp avlt.h bst.cpp Log Message: added comments Index: avlt.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avlt.cpp,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 *** avlt.cpp 25 Jun 2004 16:05:57 -0000 1.4 --- avlt.cpp 18 Jul 2004 16:57:10 -0000 1.5 *************** *** 32,35 **** --- 32,36 ---- } + /** Imposta il Fattore di Bilanciamento a s*/ void Avlt::setFdb( int s ) { *************** *** 37,51 **** } void Avlt::setFdb() { int l, r; l = r = 0; if( getLeft() ) ! l = getLeft()->height() + 1; if( getRight() ) ! r = getRight()->height() + 1; setFdb( l-r ); } void Avlt::setFdb( Avlt * start , Avlt * end) { --- 38,55 ---- } + /** Calcola il FdB del nodo corrente*/ void Avlt::setFdb() { + //Il fattore di bilanciamento è la differenza tra l'altezza del sottoallbero di destra e quella del sottoalbero di sinistra int l, r; l = r = 0; if( getLeft() ) ! l = getLeft()->height() + 1; //Altezza del sottoalbero di sinistra if( getRight() ) ! r = getRight()->height() + 1; //Altezza del sottoalbero di destra setFdb( l-r ); } + /** Calcola il fattore di bilanciamento a di tutti i nodi del cammino da start a end*/ void Avlt::setFdb( Avlt * start , Avlt * end) { *************** *** 66,70 **** } ! Avlt *Avlt::leftRotate() //dd { --- 70,74 ---- } ! /** Effettua una rotazione verso sinistra e restituisce il nuovo nodo genitore*/ Avlt *Avlt::leftRotate() //dd { *************** *** 99,102 **** --- 103,107 ---- } + /** Effettua una rotazione verso destra e restituisce il nuovo nodo genitore*/ Avlt *Avlt::rightRotate() //ss { *************** *** 131,134 **** --- 136,140 ---- } + /** Inserisce un nuovo nodo con valore key utilizzando un algoritmo ricorsivo*/ Avlt *Avlt::insert(int key) { *************** *** 186,189 **** --- 192,196 ---- } + /** Inserisce un nuovo nodo con valore key utilizzando un algoritmo iterativo*/ Avlt *Avlt::insert_iter(int key) { *************** *** 289,292 **** --- 296,300 ---- } + /** Elimina il nodo di valore key dall'albero*/ Avlt *Avlt::erase(int key) { *************** *** 388,391 **** --- 396,400 ---- } + /** Verifica se l'albero è bilanciato*/ bool Avlt::checkBalance() { *************** *** 403,406 **** --- 412,416 ---- } + /** Restituisce un vettore di nodi che hanno FdB diverso da -1,0,+1*/ vector<Avlt *> Avlt::getWrongs() { Index: bst.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/bst.cpp,v retrieving revision 1.7 retrieving revision 1.8 diff -C2 -d -r1.7 -r1.8 *** bst.cpp 17 Jul 2004 19:48:27 -0000 1.7 --- bst.cpp 18 Jul 2004 16:57:10 -0000 1.8 *************** *** 75,91 **** value = val; } ! Bst *Bst::root() { Bst *aux; for( aux=this; aux->getParent(); aux=aux->getParent() ); return aux; } bool Bst::isLeaf() { return !(getLeft()||getRight()); } bool Bst::isRoot() { --- 75,96 ---- value = val; } ! ! /** Restituisce la radice dell'albero a cui appartiene il nodo corrente*/ Bst *Bst::root() { Bst *aux; + //scorre l'albero dal basso verso l'alto a partire dal nodo corrente fino a che non trova un nodo che non ha genitore for( aux=this; aux->getParent(); aux=aux->getParent() ); return aux; } + /** Indica se il nodo corrente è una foglia */ bool Bst::isLeaf() { + //testa (getLeft()==NULL && getRight()==NULL) <==> (!getLeft() && !getRight()) <==> !(getLeft()||getRight()) return !(getLeft()||getRight()); } + /** Indica se il nodo è la radice dell'albero*/ bool Bst::isRoot() { *************** *** 93,130 **** } int Bst::level() { Bst *aux; int count; for( count=0,aux=this; aux->getParent(); aux=aux->getParent(),count++ ); return count; } int Bst::nodes() { if( isLeaf() ) return 1; ! int node = 1; if( getLeft() ) ! node += getLeft()->nodes(); if( getRight() ) ! node += getRight()->nodes(); return node; } int Bst::leaves() { if( isLeaf() ) return 1; ! int node = 0; if( getLeft() ) ! node = getLeft()->leaves(); if( getRight() ) ! node += getRight()->leaves(); ! return node; } int Bst::height() { if( isLeaf() ) return 0; --- 98,143 ---- } + /** Calcola il livello del nodo (ovvero la lunghezza del cammino tra il nodo e la radice)*/ int Bst::level() { Bst *aux; int count; + //scorre l'albero dal basso verso l'alto a partire dal nodo corrente fino a che non trova un nodo che non ha genitore e conta i passi che compie attraverso la variabile cont for( count=0,aux=this; aux->getParent(); aux=aux->getParent(),count++ ); return count; } + /** Calcola il numero di nodi dell'albero che ha come radice il nodo*/ int Bst::nodes() { + //Il numero di nodi è pari a 1 se il nodo è una foglia oppure al numero di nodi del sottoalbero di sinistra + il numero di nodi del sottoalbero di destra + 1 (se stesso) ovvero node = 1 + getLeft()->nodes() + getRight()->nodes() if( isLeaf() ) return 1; ! int node = 1; // node = 1 if( getLeft() ) ! node += getLeft()->nodes(); // node = 1 + getLeft()->nodes() if( getRight() ) ! node += getRight()->nodes(); // node = 1 + getLeft()->nodes() + getRight()->nodes() return node; } + /** Calcola il numero di foglie dell'albero che ha come radice il nodo*/ int Bst::leaves() { + //Il numero di foglie è pari a 1 se il nodo è una foglia oppure al numero di foglie del sottoalbero di sinistra + il numero di foglie del sottoalbero di destra ovvero leave = getLeft()->leaves() + getRight()->leaves() if( isLeaf() ) return 1; ! int leave = 0; if( getLeft() ) ! leave = getLeft()->leaves(); // leave = getLeft()->leaves() if( getRight() ) ! leave += getRight()->leaves(); // leave = getLeft()->leaves() + getRight()->leaves() ! return leave; } + /** Calcola l'altezza (lunghezza del ramo più lungo) dell'albero che ha come radice il nodo*/ int Bst::height() { + // L'altezza di un nodo è pari all'altezza del sottoalbero più lungo incrementata di 1 (il nodo corrente) if( isLeaf() ) return 0; *************** *** 132,142 **** l = r = 0; if( getLeft() ) ! l = getLeft()->height(); if( getRight() ) ! r = getRight()->height(); ! return 1 + ( l>r ? l : r ); } Bst *Bst::search(int key) { --- 145,156 ---- l = r = 0; if( getLeft() ) ! l = getLeft()->height(); // l contiene l'altezza del sottoalbero sinistro if( getRight() ) ! r = getRight()->height(); // r contiene l'altezza del sottoalbero destro ! return 1 + ( l>r ? l : r ); // viene restituita l'altezza del sottoalbero più lungo incrementata di 1 } + /** Ricerca un nodo di valore key in modo iterativo e ne restituisce il puntatore, se la ricerca ha esito negativo restituisce NULL*/ Bst *Bst::search(int key) { *************** *** 146,160 **** while( aux ) { ! if( aux->getValue() == key ) return aux; ! if( key < aux->getValue() ) aux = aux->getLeft(); ! else ! aux = aux->getRight(); } ! return NULL; } void Bst::insert(int key) { --- 160,175 ---- while( aux ) { ! if( aux->getValue() == key ) //Si è trovato il nodo cercato: si restituisce il puntatore e si esce return aux; ! if( key < aux->getValue() ) //Se il valore di aux è < di quello di key si cerca a sinistra aux = aux->getLeft(); ! else //altrimenti si cerca a destra ! aux = aux->getRight(); } ! return NULL; //Si arriva a questo punto solo se il valore non è stato trovato } + /** Aggiunge un nodo con valore key nell'albero*/ void Bst::insert(int key) { *************** *** 164,175 **** aux2 = NULL; ! while( aux1 ) { if ( key == aux1->getValue() ) { //printf("The number -> %d is already in the Binary Search Tree\n",key); ! return; } ! aux2 = aux1; if ( key < aux1->getValue() ) aux1 = aux1->getLeft(); --- 179,190 ---- aux2 = NULL; ! while( aux1 ) //ricerca del nodo { if ( key == aux1->getValue() ) { //printf("The number -> %d is already in the Binary Search Tree\n",key); ! return; // se il valore si trova già nell'albero si esce } ! aux2 = aux1; //aux2 mantiene il puntatore al nodo al quale si deve appendere il nuovo nodo if ( key < aux1->getValue() ) aux1 = aux1->getLeft(); *************** *** 178,185 **** --- 193,202 ---- } + // viene istanziato il nuovo nodo e gli viene assegnato key come valore e aux2 come genitore aux1 = new Bst; aux1->setParent( aux2 ); aux1->setValue( key ); + // il nuovo nodo viene appeso a sinistra o a destra di aux2 in base al suo valore if ( key < aux2->getValue() ) aux2->setLeft( aux1 ); *************** *** 189,192 **** --- 206,210 ---- } + void Bst::erase() { *************** *** 222,229 **** } ! void Bst::erase(int val) { Bst *aux; ! aux = search( val ); if( aux ) { --- 240,248 ---- } ! /** Elimina il nodo di valore key dall'albero*/ ! void Bst::erase(int key) { Bst *aux; ! aux = search( key ); if( aux ) { *************** *** 233,255 **** --- 252,281 ---- } + /** Trova il nodo dell'albero che ha valore massimo e ne restituisce il puntatore*/ Bst *Bst::max() { Bst *aux; + // Si scorre l'albero verso il figlio di destra a partire dal nodo corrente fino ad arrivare ad una foglia for( aux=this; aux->getRight(); aux=aux->getRight() ); return aux; } + /** Trova il nodo dell'albero che ha valore minimo e ne restituisce il puntatore*/ Bst *Bst::min() { Bst *aux; + // Si scorre l'albero verso il figlio di sinistra a partire dal nodo corrente fino ad arrivare ad una foglia for( aux=this; aux->getLeft(); aux=aux->getLeft() ); return aux; } + /** Restituisce il puntatore del nodo predecessore (Il nodo che ha valore maggiore tra quelli che hanno valore minore)*/ Bst *Bst::predecessor() { + //Se il nodo corrente ha un figlio sinistro allora il predecessore è il massimo del sottoalbero di sinistra if ( getLeft() ) return getLeft()->max(); + //Altrimenti si risale l'albero fino ad arrivare al nodo che è il più basso antenato il cui figlio destro è un antenato. Si risale l'albero fino ad arrivare alla radice oppure alla prima svolta a sinistra Bst *aux1, *aux2; aux1 = getParent(); *************** *** 263,271 **** } Bst *Bst::successor() { if ( getRight() ) return getRight()->min(); ! Bst *aux1, *aux2; aux1 = getParent(); --- 289,300 ---- } + /** Restituisce il puntatore del nodo successore (Il nodo che ha valore minore tra quelli che hanno valore maggiore)*/ Bst *Bst::successor() { + //Se il nodo corrente ha un figlio destro allora il successore è il minimo del sottoalbero di destra if ( getRight() ) return getRight()->min(); ! ! //Altrimenti si risale l'albero fino ad arrivare al nodo che è il più basso antenato il cui figlio sinistro è un antenato. Si risale l'albero fino ad arrivare alla radice oppure alla prima svolta a destra Bst *aux1, *aux2; aux1 = getParent(); Index: avlt.h =================================================================== RCS file: /cvsroot/avl/avl/src/avlt.h,v retrieving revision 1.5 retrieving revision 1.6 diff -C2 -d -r1.5 -r1.6 *** avlt.h 25 Jun 2004 16:05:57 -0000 1.5 --- avlt.h 18 Jul 2004 16:57:10 -0000 1.6 *************** *** 32,36 **** { private: ! int fdb; Avlt *rightRotate(); Avlt *leftRotate(); --- 32,36 ---- { private: ! int fdb; //Fattore di Bilanciamento Avlt *rightRotate(); Avlt *leftRotate(); |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-07-18 16:57:20
|
Update of /cvsroot/avl/avl In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv20402 Modified Files: ChangeLog TODO Log Message: added comments Index: TODO =================================================================== RCS file: /cvsroot/avl/avl/TODO,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** TODO 17 Jul 2004 17:05:54 -0000 1.2 --- TODO 18 Jul 2004 16:57:10 -0000 1.3 *************** *** 2,3 **** --- 2,5 ---- - Controllare e fixare i punti in cui freeza. dovrebbe essere in bst. non è solo quando l'albero è vuoto. + + - Finire di mettere i commenti in avlt.cpp \ No newline at end of file Index: ChangeLog =================================================================== RCS file: /cvsroot/avl/avl/ChangeLog,v retrieving revision 1.5 retrieving revision 1.6 diff -C2 -d -r1.5 -r1.6 *** ChangeLog 17 Jul 2004 17:05:54 -0000 1.5 --- ChangeLog 18 Jul 2004 16:57:10 -0000 1.6 *************** *** 1,12 **** --- 1,19 ---- + --==18.07.2004==-- + <jah2003>: + -added comments in bst.cpp and avlt.cpp + --==17.07.2004==-- <hetfield666>: - Test class completed, with bst, avl and comparation - Added Timing support in Test class + --==15.07.2004==-- <hetfield666>: - first Test class implementation + --==24.06.2004==-- <hetfield666>: - first Makefile implementation + --==24.06.2004==-- <jah2003>: |
