fork(1) download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <stdio.h>
  4. #include <string.h>
  5. #define size 26
  6.  
  7. struct Node {
  8. 	bool isLeaf;
  9. 	Node *next[size];
  10. 	Node *parent;
  11. 	int wordCount, id;
  12. 	Node() {
  13. 		isLeaf = false;
  14. 		parent = NULL;
  15. 		wordCount = 0;
  16. 		id = -1;
  17. 		for (int i = 0; i < size; i++)
  18. 			next[i] = NULL;
  19. 	}
  20. } *root;
  21.  
  22. struct Lookup {
  23. 	bool isAvailable;
  24. 	Node *lookedupNode;
  25. 	Lookup(bool available, Node *ins) {
  26. 		isAvailable = available;
  27. 		lookedupNode = ins;
  28. 	}
  29. };
  30.  
  31. Lookup search(char *str) {
  32. 	Node *curr = root;
  33. 	for (int i = 0; str[i]; i++) {
  34. 		int id = str[i] - 'a';
  35. 		if (curr->next[id] == NULL) {
  36. 			return Lookup(false, NULL);
  37. 		}
  38. 		curr = curr->next[id];
  39. 	}
  40. 	if (curr->isLeaf) return Lookup(true, curr);
  41. 	else              return Lookup(false, NULL);
  42. }
  43.  
  44. void insert(char *str) {
  45. 	Lookup var = search(str);
  46. 	if (var.isAvailable) {
  47. 		printf("Already Exist\n");
  48. 		return;
  49. 	}
  50.  
  51. 	Node *curr = root;
  52. 	for (int i = 0; i < str[i]; i++) {
  53. 		Node *temp = curr;
  54. 		int id = str[i] - 'a';
  55. 		if (curr->next[id] == NULL)
  56. 			curr->next[id] = new Node;
  57. 		curr->wordCount++;
  58. 		curr = curr->next[id];
  59. 		curr->parent = temp;
  60. 		curr->id = id;
  61. 	}
  62. 	curr->isLeaf = true;
  63. 	curr->wordCount++;
  64. 	printf("New Entry\n");
  65. }
  66.  
  67. void remove(Node *&curr) {
  68. 	if (curr->parent) {
  69. 		Node *temp = curr->parent;
  70. 		if (curr->wordCount > 1) {
  71. 			curr->wordCount--;
  72. 		}
  73. 		else {
  74. 			temp->next[curr->id] = NULL;
  75. 			delete curr;
  76. 			curr = NULL;
  77. 		}
  78. 		remove(temp);
  79. 	}
  80. 	else {
  81. 		curr->wordCount--;
  82. 		if (curr->wordCount == 0) {
  83. 			delete curr;
  84. 			curr = NULL;
  85. 		}
  86. 	}
  87. }
  88.  
  89. void findRemoveItem(char *str) {
  90. 	Lookup var = search(str);
  91. 	if (var.isAvailable) {
  92. 		var.lookedupNode->isLeaf = false;
  93. 		remove(var.lookedupNode);
  94. 	}
  95. 	else {
  96. 		printf("Not a word\n");
  97. 	}
  98. }
  99.  
  100. void traceParent(Node *curr) {
  101. 	if (curr->parent) {
  102. 		traceParent(curr->parent);
  103. 		printf("%c", curr->id + 'a');
  104. 	}
  105. }
  106.  
  107. void print(Node *curr) {
  108. 	if (!curr) return;
  109. 	//printf("wordcount = %d %c\n", curr->wordCount, curr->id + 'a');
  110. 	for (int i = 0; i < size; i++) {
  111. 		if (curr->next[i]) {
  112. 			if (curr->next[i]->isLeaf) {
  113. 				traceParent(curr->next[i]);
  114. 				printf("\n");
  115. 			}
  116. 			print(curr->next[i]);
  117. 		}
  118. 	}
  119. }
  120.  
  121. void del(Node *&cur) {
  122. 	if (!cur) {
  123. 		return;
  124. 	}
  125. 	for (int i = 0; i < size; i++)
  126. 		if (cur->next[i])
  127. 			del(cur->next[i]);
  128. 	delete cur;
  129. 	cur = NULL;
  130. }
  131.  
  132. int main() {
  133. 	root = new Node;
  134. 	char arr[][10] = { "single", "sing", "singleton", "singer", "tree", "try", "trie", "sign", "sing" };
  135. 	for (int i = 0; i < 9; i++)
  136. 		insert(arr[i]);
  137. 	print(root);
  138.  
  139. 	char str[10] = "sign";
  140. 	search(str).isAvailable ? printf("Found\n") : printf("Not Found\n");
  141. 	strcpy(str, "trye");
  142. 	search(str).isAvailable ? printf("Found\n") : printf("Not Found\n");
  143. 	strcpy(str, "tree");
  144. 	search(str).isAvailable ? printf("Found\n") : printf("Not Found\n");
  145.  
  146.  
  147. 	findRemoveItem(arr[0]);
  148. 	print(root);
  149. 	printf("\n----------------after removing %s----------------\n", arr[0]);
  150. 	findRemoveItem(arr[2]);
  151. 	print(root);
  152. 	printf("\n----------------after removing %s----------------\n", arr[2]);
  153. 	findRemoveItem(arr[3]);
  154. 	print(root);
  155. 	printf("\n----------------after removing %s----------------\n", arr[3]);
  156. 	findRemoveItem(arr[6]);
  157. 	print(root);
  158. 	printf("\n----------------after removing %s----------------\n", arr[6]);
  159. 	findRemoveItem(arr[4]);
  160. 	print(root);
  161. 	printf("\n----------------after removing %s----------------\n", arr[4]);
  162. 	findRemoveItem(arr[1]);
  163. 	print(root);
  164. 	printf("\n----------------after removing %s----------------\n", arr[1]);
  165. 	findRemoveItem(arr[5]);
  166. 	print(root);
  167. 	printf("\n----------------after removing %s----------------\n", arr[5]);
  168. 	findRemoveItem(arr[7]);
  169. 	root == NULL ? printf("root = NULL\n") : printf("root = instance %p\n", root);
  170. 	print(root);
  171. 	printf("\n----------------after removing %s----------------\n", arr[7]);
  172.  
  173.  
  174. 	del(root);
  175. 	root == NULL ? printf("root = NULL\n") : printf("root = instance %p\n", root);
  176. 	return 0;
  177. }
Runtime error #stdin #stdout 0s 4352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hsUr8C
language:
C++14 (gcc 8.3)
created:
6 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!