fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. typedef struct NodeType *Node;
  6. struct NodeType {
  7.     int value;
  8. 	Node left;
  9. 	Node right;
  10. };
  11.  
  12. Node nodeInit(int v) {
  13. 	Node n = malloc(sizeof(struct NodeType));
  14. 	n->value = v;
  15. 	n->left = NULL;
  16. 	n->right = NULL;
  17. 	return n;
  18. }
  19.  
  20. Node nodeAdd(Node n, int v) {
  21. 	if (n == NULL) {
  22. 		return nodeInit(v);
  23. 	} else {
  24. 		if (v < n->value) {
  25. 			n->left = nodeAdd(n->left, v);
  26. 		} else {
  27. 			n->right = nodeAdd(n->right, v);
  28. 		}
  29. 		return n;
  30. 	}
  31. }
  32.  
  33. void nodeAdd2(Node *n, int v) {
  34. 	if (*n == NULL) {
  35. 		*n = nodeInit(v);
  36. 	} else {
  37. 		if (v < (*n)->value) {
  38. 			nodeAdd2(&(*n)->left, v);
  39. 		} else {
  40. 			nodeAdd2(&(*n)->right, v);
  41. 		}
  42. 	}
  43. }
  44.  
  45. void nodeDump(Node n, int c) {
  46. 	int i;
  47. 	if (n == NULL) {
  48. 		return;
  49. 	}
  50. 	nodeDump(n->right, c + 1);
  51. 	for (i = 0; i < c; i++) {
  52. 		printf(" ");
  53. 	}
  54. 	printf("%d\n", n->value);
  55. 	nodeDump(n->left, c + 1);
  56. }
  57.  
  58. int main(void) {
  59. 	int i;
  60. 	int c = 10000;
  61. 	clock_t start;
  62. 	clock_t end;
  63. 	Node n1;
  64. 	Node n2;
  65.  
  66. 	start = clock();
  67. 	n1 = NULL;
  68. 	for (i = 0; i < c; i++) {
  69. 		n1 = nodeAdd(n1, i);
  70. 	}
  71. 	end = clock();
  72. 	printf("nodeAdd1 : %f\n", (double)end - start);
  73.  
  74. 	start = clock();
  75. 	n2 = NULL;
  76. 	for (i = 0; i < c; i++) {
  77. 		nodeAdd2(&n2, i);
  78. 	}
  79. 	end = clock();
  80. 	printf("nodeAdd2 : %f\n", (double)end - start);
  81.  
  82. 	return EXIT_SUCCESS;
  83. }
Success #stdin #stdout 0.71s 2148KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
nodeAdd1 : 510000.000000
nodeAdd2 : 180000.000000
https://ideone.com/DmuaH6
language:
C (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!