1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | /*BFS sub routine*/ bool printtree(NODE* node, int target, int level) { int i; bool returnval=false; if (target > level) { for(i=0;i<CCOUNT;i++) if(printtree(node->child+i,target,level+1) ) returnval=true; } else { printf("%c",(node->data)); if(node->child != NULL) returnval=true; } return returnval; } /*BFS routine*/ void printbfstree(NODE* root) { if(root == NULL) return; int target=0; while(printtree(root,target++,0)) { printf("\n"); } } |
1 2 3 4 5 6 7 8 9 | --------------- >a.out -l3 -c7 queue based, allocated for queue size 50 ,each node size 4 bytes printing queue based a0123456ABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFG printing stack based a0123456ABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFG printing done --------------- |
1 2 3 4 5 6 7 8 9 10 11 12 | ---------------- >gcc -DLPRINT -lm stackbasedBFS.c >./a.out -l3 -c7 queue based, allocated for queue size 50 ,each node size 4 bytes printing queue based a0123456ABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFG printing stack based a 0123456 ABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFG printing done ---------------- |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | --------------- >./a.out -l5 -c2 queue based, allocated for queue size 17 ,each node size 4 bytes printing queue based a01ABABabababab0101010101010101 queue based, queue usage size 16 diff time 0 sec 26 micro printing stack based a01ABABabababab0101010101010101 stack used 128 diff time 0 sec 14 micro printing done --------------- |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | -------------- > cc -DNOPRINT -DSPACEDATA -DTIMEDATA -lm stackbasedBFS.c > ./a.out -l10 -c10 queue based, allocated for queue size 1000000001 ,each node size 4 bytes > ./a.out -l10 -c9 queue based, allocated for queue size 387420490 ,each node size 4 bytes printing queue based Segmentation fault > ./a.out -l9 -c10 queue based, allocated for queue size 100000001 ,each node size 4 bytes printing queue based queue based, queue usage size 100000000 diff time 28 sec 490083 micro printing stack based stack used 256 diff time 1 sec 469060 micro printing done > ./a.out -l5 -c10 queue based, allocated for queue size 10001 ,each node size 4 bytes printing queue based queue based, queue usage size 10000 diff time 0 sec 2891 micro printing stack based stack used 128 diff time 0 sec 164 micro printing done > ./a.out -l10 -c7 queue based, allocated for queue size 40353608 ,each node size 4 bytes printing queue based queue based, queue usage size 40353607 diff time 11 sec 874163 micro printing stack based stack used 288 diff time 0 sec 788580 micro printing done > ./a.out -l20 -c2 queue based, allocated for queue size 524289 ,each node size 4 bytes printing queue based queue based, queue usage size 524288 diff time 0 sec 333929 micro printing stack based stack used 608 diff time 0 sec 40476 micro printing done > ./a.out -l25 -c2 queue based, allocated for queue size 16777217 ,each node size 4 bytes printing queue based queue based, queue usage size 16777216 diff time 10 sec 635081 micro printing stack based stack used 768 diff time 1 sec 482634 micro printing done > ./a.out -l30 -c2 queue based, allocated for queue size 536870913 ,each node size 4 bytes allocation failed, exiting > ./a.out -l28 -c2 queue based, allocated for queue size 134217729 ,each node size 4 bytes allocation failed, exiting > ./a.out -l27 -c2 queue based, allocated for queue size 67108865 ,each node size 4 bytes printing queue based queue based, queue usage size 67108864 diff time 43 sec 22479 micro printing stack based stack used 832 diff time 5 sec 773319 micro printing done ----------------- |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | ---------------- > gdb GNU gdb 6.3 Copyright 2004 Free Software Foundation, Inc. GDB is free software, covered by the GNU General Public License, and you are welcome to change it and/or distribute copies of it under certain conditions. Type "show copying" to see the conditions. There is absolutely no warranty for GDB. Type "show warranty" for details. This GDB was configured as "i686-pc-linux-gnu". (gdb) file a.out Reading symbols from /home/pravinsi/a.out...done. Using host libthread_db library "/lib/tls/libthread_db.so.1". (gdb) b printtree Breakpoint 1 at 0x8048802: file stackbasedBFS.c, line 79. (gdb) run Starting program: /home/pravinsi/a.out queue based, allocated for queue size 50 ,each node size 4 bytes printing queue based a0123456ABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFG queue based, queue usage size 49 diff time 0 sec 82 micro printing stack based Breakpoint 1, printtree (node=0x804b008, target=0, level=0) at stackbasedBFS.c:79 79 __asm__("movl %%ebp, %0;" : "=r" ( i)); (gdb) c Continuing. Breakpoint 1, printtree (node=0x804b008, target=1, level=0) at stackbasedBFS.c:79 79 __asm__("movl %%ebp, %0;" : "=r" ( i)); (gdb) bt #0 printtree (node=0x804b008, target=1, level=0) at stackbasedBFS.c:79 #1 0x080488d6 in printbfstree (root=0x804b008) at stackbasedBFS.c:99 #2 0x08048f51 in main (argc=1, argv=0xbffff894) at stackbasedBFS.c:216 (gdb) c Continuing. Breakpoint 1, printtree (node=0x804b018, target=1, level=1) at stackbasedBFS.c:79 79 __asm__("movl %%ebp, %0;" : "=r" ( i)); (gdb) bt #0 printtree (node=0x804b018, target=1, level=1) at stackbasedBFS.c:79 #1 0x0804886c in printtree (node=0x804b008, target=1, level=0) at stackbasedBFS.c:84 #2 0x080488d6 in printbfstree (root=0x804b008) at stackbasedBFS.c:99 #3 0x08048f51 in main (argc=1, argv=0xbffff894) at stackbasedBFS.c:216 (gdb) f 1 #1 0x0804886c in printtree (node=0x804b008, target=1, level=0) at stackbasedBFS.c:84 84 for(i=0;i<CCOUNT;i++) if(printtree(node->child+i,target,level+1) ) returnval=true; (gdb) info reg ebp ebp 0xbffff7a8 0xbffff7a8 (gdb) f 0 #0 printtree (node=0x804b018, target=1, level=1) at stackbasedBFS.c:79 79 __asm__("movl %%ebp, %0;" : "=r" ( i)); (gdb) info reg ebp ebp 0xbffff788 0xbffff788 (gdb) x/10x 0xbffff788 0xbffff788: 0xbffff7a8 0x0804886c 0x0804b018 0x00000001 0xbffff798: 0x00000001 0x08048d5b 0x000490cf 0x00000000 0xbffff7a8: 0xbffff7c8 0x080488d6 (gdb) x 0x0804886c 0x804886c <printtree+112>: 0x8410c483 (gdb) x 0x08048d5b 0x8048d5b <BFS+413>: 0xc910c483 ----------------- |
1 2 3 | 0xbffff788: 0xbffff7a8 0x0804886c 0x0804b018 0x00000001 0xbffff798: 0x00000001 0x08048d5b 0x000490cf 0x00000000 0xbffff7a8: 0xbffff7c8 |
欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/) | Powered by Discuz! 7.0.0 |