Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma warning(disable:4996)
- // C program to implement basic operations (search, insert and delete)
- // on a BST that handles duplicates by storing count with every node
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #define MAX_STRING_SIZE 100
- #define HASHSIZE 101 /* comment here */
- #define FILE_OUTPUT "calendar.txt"
- #define ALLOCSIZE 1000 /*size of available space*/
- #define N 1000 // max number of lines to be read
- #define VALLEN 100 //max number of chars for description
- static char allocbuf[ALLOCSIZE]; /* storage for alloc*/
- static char *allocp = allocbuf; /* next free position*/
- static struct map *hashtab[HASHSIZE]; /* pointer table */
- unsigned hash(char *); /* hashing function: form hash value for string s. used by both lookup and install*/
- char *strdup(char *);
- char *alloc(int n) { /* return a pointer to n characters*/
- if (allocbuf + ALLOCSIZE - allocp >= n) { /*it fits*/
- allocp += n;
- return allocp - n; /*old p*/
- } else /*not enough room*/
- return 0;
- }
- typedef struct map { /* creating a map structure */
- struct map *next;
- char *value;
- char *KEY;
- } map;
- typedef struct node {
- int KEY;
- char *value;
- int node_count;
- struct node *left, *right;
- int unique_count;
- } node;
- // A utility function to create a new BST node
- node *newNode(int KEY, char *value) {
- //Allocate a new overall structure
- node *temp = (node *) malloc(sizeof (node));
- //Copy the integer key
- temp->KEY = KEY;
- temp->value = value;
- temp->left = temp->right = NULL;
- temp->node_count = 1;
- return temp;
- }
- // A utility function to do inorder traversal of BST
- void inorder(node *root, int *pin_count) {
- if (root != NULL) {
- inorder(root->left, pin_count);
- //printf("%d(%d)\n", root->KEY, root->node_count);
- inorder(root->right, pin_count);
- }
- }
- /* A utility function to find deepest keys of BST */
- /* This is done by extracting the key with the lowest count,
- since count member of node struct gets incremented each time it is read. */
- void unique_key(node *root, int *p_unique_count, int p_unique_key_arr[], char *p_value_arr[]) {
- int count = 0;
- char *p;
- if (root != NULL) {
- unique_key(root->left, p_unique_count, p_unique_key_arr, p_value_arr);
- if (root->node_count == 1) {
- if ((p = alloc(strlen(root[count].value) + 1)) == NULL) {
- return;
- } else {
- root[count].unique_count = *p_unique_count;
- p_unique_key_arr[*p_unique_count] = root[count].KEY;
- strcpy(p, root[count].value);
- p_value_arr[*p_unique_count] = p;
- //printf("%s\n",p_value_arr[*p_unique_count][*p_unique_count]);
- //printf("%d(%d) -> %s %d\n", root->KEY, root->node_count, root->value, root->unique_count);
- (*p_unique_count)++;
- count++;
- }
- }
- unique_key(root->right, p_unique_count, p_unique_key_arr, p_value_arr);
- }
- }
- /* A utility function to insert a new node with given key in BST */
- node* insert_node(node* node, int key, char *value) {
- /* If the tree is empty, return a new node */
- if (node == NULL)
- return newNode(key, value);
- // If key already exists in BST, icnrement count and return
- if (key == node->KEY) {
- (node->node_count)++;
- // return node;
- }
- /* Otherwise, recur down the tree */
- if (key < node->KEY)
- node->left = insert_node(node->left, key, value);
- else
- node->right = insert_node(node->right, key, value);
- /* return the (unchanged) node pointer */
- return node;
- }
- /* lookup function takes a pointer to char - s as an argument and returns a pointer to map structure */
- map *lookup(char *s) {
- map *np;
- for (np = hashtab[hash(s)]; np != NULL; np = np->next) {
- if (strcmp(s, np->KEY) == 0) {
- return np;
- }
- }
- return NULL;
- }
- /* insert function takes a pointer to a char - KEY, value and returns a pointer to map structure */
- map *insert_map(char* KEY, char* value) {
- /* install: put (name, defn) in */
- /* Install uses lookup to determine whether the KEY being installed
- is already present. Proceeds to create a new entry or update*/
- map *np;
- unsigned hashval;
- if ((np = lookup(KEY)) == NULL) {
- np = (map *) malloc(sizeof (*np));
- if (np == NULL || (np->KEY = strdup(KEY)) == NULL) {
- return NULL;
- }
- hashval = hash(KEY);
- np->next = hashtab[hashval];
- hashtab[hashval] = np;
- } else {
- free((void *) np->value);
- }
- if ((np->value = strdup(value)) == NULL) { //map has no field value
- return NULL;
- }
- return np;
- }
- /* uninstall function removes a key and calendar from table maintained by lookup and install */
- map *remove_map(char *KEY) {
- map *found;
- found = lookup(KEY);
- if (found == NULL) /* not found and nothing to do */ {
- printf("%s - Nothing to delete.\n", KEY);
- return NULL;
- } else {
- if (found->next != NULL) {
- found->next = found->next->next;
- found = found->next;
- } else {
- hashtab[hash(KEY)] = NULL;
- free((void *) found);
- }
- }
- return found;
- }
- /* simple implementation of strdup*/
- char *strdup(char *s) {
- char *d = malloc(strlen(s) + 1); // Space for length plus null
- if (d == NULL) return NULL; // No memory
- strcpy(d, s); // Copy the characters
- return d; // Return the new string
- }
- unsigned hash(char *s) {
- /* hashing function: form hash value for string s */
- /* used by both lookup and install*/
- unsigned hashval;
- for (hashval = 0; *s != '\0'; s++) {
- hashval = *s + 31 * hashval;
- }
- return hashval % HASHSIZE;
- }
- // Driver Program to test above functions
- int main() {
- FILE *f_cal;
- //FILE *outp;
- int total_unique = 0;
- int in_count, count_create = 0;
- int count_delete = 0;
- int unique_key_arr[10]; // Make dynamic
- char *value_arr[10];
- char *VAL_arr_create[10]; // an array of pointers [unique][chars]
- char *VAL_arr_delete[10];
- char *KEY_arr_create[10];
- char *KEY_arr_delete[10];
- f_cal = fopen("calendar.txt", "r+");
- int key_arr[N], a, count = 0;
- char val_arr[N][VALLEN], b[10], c[10], d[10];
- if (f_cal) {
- printf("Processing file...\n");
- int ret = fscanf(f_cal, "%d %s %s %s", &a, b, c, d);
- printf("%d\n", ret);
- if (ret == 4) {
- while (fscanf(f_cal, "%d %s %s %s", &a, b, c, d) == 4) {
- if (count < N) {
- key_arr[count] = a;
- snprintf(val_arr[count++], VALLEN, "%s %s %s", b, c, d);
- }
- }
- for (int i = 0; i < count; ++i)
- printf("key=%d, val = %s\n", key_arr[i], val_arr[i]);
- } else {
- printf("File is empty.\n");
- }
- fclose(f_cal);
- } else {
- printf("no file found.\n");
- }
- //unique *data = NULL;
- /* READ CALENDER_OPERATIONS*/
- /* Pass all operations down to BST*/
- /* Let us create following BST. Passing values along with key */
- node *root = NULL;
- //node *root = (node*)malloc(sizeof(node));
- node *test = (node*) malloc(sizeof (node));
- //this is for storing commands
- root = insert_node(root, 2082018, "C 1200 79 Meeting");
- root = insert_node(root, 3082018, "C 1300 60 Lunch");
- root = insert_node(root, 4082018, "C 1400 30 Dinner");
- root = insert_node(root, 5082018, "C 0600 90 Work");
- root = insert_node(root, 16082018, "D 4300 30 Diy");
- root = insert_node(root, 7082018, "C 5608 30 Dinner");
- root = insert_node(root, 18082018, "C 1409 35 to");
- root = insert_node(root, 29082018, "C 1600 60 play");
- root = insert_node(root, 9082018, "U 1800 88 e");
- root = insert_node(root, 9082018, "D 1800 88 e");
- printf("Inorder traversal of the given tree \n");
- inorder(root, &in_count);
- printf("\nDeepest unique keys of the given tree \n");
- unique_key(root, &total_unique, unique_key_arr, value_arr);
- printf("\n");
- printf("\nDeepest unique keys of the given tree in main\n");
- for (int i = 0; i < total_unique; i++) {
- printf("%d [%s]\n", unique_key_arr[i], value_arr[i]);
- if (*value_arr[i] == 'C') { //Compare first char of pointer type
- } else if (*value_arr[i] == 'U') { //Compare first char of pointer type
- } else if (*value_arr[i] == 'D') { //Compare first char of pointer type
- }
- }
- printf("\n");
- /* Map is for storing calendar. This should contain the unique elements
- * from the BST above. Based on the first char inside `value_arr`, we
- * should insert or delete a map. Number of operations to perform
- depends on variable `unique_count`. Use strcpy()*/
- printf("\nDeepest unique keys to map structure: %d\n", total_unique);
- for (int unique_count = 0; unique_count < total_unique; unique_count++) {
- char* p_val; //pointer to char for value
- char* p_key; //pointer to char for key
- p_key = malloc(sizeof (char) + 1); //this is malloced to access different memory each time.
- if (*value_arr[unique_count] == 'C' || *value_arr[unique_count] == 'U') { //Compare first char of pointer type
- if ((p_val = alloc(strlen(value_arr[unique_count]) + 1)) == NULL) {
- return -1;
- } else {
- strcpy(p_val, value_arr[unique_count]); //copying value to pointer to char
- VAL_arr_create[count_create] = p_val; //p passed to value array
- }
- //Convert integer to pointer to char
- sprintf(p_key, "%d", unique_key_arr[unique_count]);
- KEY_arr_create[count_create] = p_key; //array containing all create/updates
- printf("I am here %s, %s\n", KEY_arr_create[count_create], VAL_arr_create[count_create]);
- count_create++;
- } else { //must be a delete
- if ((p_val = alloc(strlen(value_arr[unique_count]) + 1)) == NULL) {
- return -1;
- } else {
- strcpy(p_val, value_arr[unique_count]); //copying value to pointer to char
- VAL_arr_delete[count_delete] = p_val; //p passed to value array
- }
- //Convert integer to pointer to char
- sprintf(p_key, "%d", unique_key_arr[unique_count]);
- KEY_arr_delete[count_delete] = p_key; //array containing all deletes
- printf("I am here2 %s, %s\n", KEY_arr_delete[count_delete], VAL_arr_delete[count_delete]);
- count_delete++;
- }
- }
- map * table[10]; //pointer to type map structure
- printf("\nBefore insert CREATE %d\n", count_create);
- for (int i = 0; i < count_create; i++) {
- printf("CREATE %s, %s\n", KEY_arr_create[i], VAL_arr_create[i]);
- /* Here I need to remove leading operation letter to display*/
- char *p;
- char *copy_val_create = strchr(VAL_arr_create[i], ' ');
- if (copy_val_create)
- printf("COPY: %s\n", copy_val_create + 1);
- else
- printf("Could not find a space\n");
- table[i] = insert_map(KEY_arr_create[i], copy_val_create + 1);
- }
- printf("\nBefore insert DELETE %d\n", count_delete);
- for (int i = 0; i < count_delete; i++) {
- printf("DELETE %s, %s\n", KEY_arr_delete[i], VAL_arr_delete[i]);
- remove_map(KEY_arr_delete[i]);
- }
- printf("\nUPDATED CALENDAR\n");
- for (int i = 0; i < count_create; i++) {
- printf("%s->%s \n", table[i]->KEY, table[i]->value);
- fprintf(f_cal, "%s %s\n", table[i]->KEY, table[i]->value);
- }
- fclose(f_cal);
- printf("\n");
- //remove_map("4082018");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment