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*/
- 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 *KEY;
- char *duration;
- char *time;
- char *description;
- //struct Value value;
- }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
- struct node *temp = (struct node *)malloc(sizeof(struct 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_arr[], char *p_value_arr[]) {
- int count = 0;
- //unique *temp = (unique *)malloc(n * sizeof(unique));
- char *p;
- if (root != NULL)
- {
- unique_key(root->left, p_unique_count, p_unique_arr, p_value_arr);
- if (root->node_count == 1) {
- p = alloc(strlen(root[count].value) + 1);
- root[count].unique_count = *p_unique_count;
- p_unique_arr[*p_unique_count] = root[count].KEY;
- //printf("%s %d\n ", root[count].value, strlen(root[count].value));
- strcpy(p, root[count].value);
- p_value_arr[*p_unique_count] = p;
- //strcpy(p_value_arr[*p_unique_count],root[count].value);
- 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_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;
- }
- /* install function takes a pointer to a char - KEY, calendar and returns a pointer to map structure */
- map *insert_map(char *KEY, char *time, char *duration, char *description) {
- /* 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->time); //type cast cannot convert from 'Value' to 'Value*'
- free((void *)np->description);
- free((void *)np->duration);
- }
- if ((np->time = strdup(time)) == NULL) { //map has no field value
- return NULL;
- }
- if ((np->description = strdup(description)) == NULL) { //map has no field value
- return NULL;
- }
- if ((np->duration = strdup(duration)) == 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("Nothing to delete.");
- 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 *output_stream;
- output_stream = fopen("calendar.txt", "w+");
- int unique_count = 0;
- int in_count =0;
- int *data;
- int unique_arr[7]; //dynamic
- char *value_arr[10]; // an array of pointers
- //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 Worko");
- root = insert_node(root, 6082018, "D 4300 30 Diy");
- root = insert_node(root, 7082018, "C 5608 30 Dinner");
- root = insert_node(root, 8082018, "C 1409 35 to");
- root = insert_node(root, 9082018, "C 1600 60 play");
- root = insert_node(root, 9082018, "U 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, &unique_count, unique_arr, value_arr);
- printf("\n");
- for(int i = 0; i < 9; i++) {
- printf("%d [%s]\n", unique_arr[i], value_arr[i]); // EXECUTION stops after this for loop
- }
- printf("THIS DOESNT PRINT\n");
- //Map is for storing calendar
- map *table[8] = {
- //This is equivalent to create
- (insert_map("2082018", "1200", "79", "Meeting")), /* No leading 0's*/
- (insert_map("3082018", "1300", "60", "Lunch" )),
- (insert_map("4082018", "1400", "30", "Dinner")),
- (insert_map("5082018", "0600", "90", "Work" )),
- (insert_map("6082018", "1200", "79", "Party")),
- (insert_map("7082018", "1300", "60", "Event")),
- (insert_map("8082018", "1400", "30", "Training")),
- (insert_map("9082018", "0600", "90", "Study"))
- };
- int i;
- for (i = 0; i < 8; i++) {
- printf("%s->%s %s %s\n", table[i]->KEY, table[i]->time, table[i]->duration, table[i]->description);
- }
- printf("\n");
- remove_map("4082018");
- //uninstall("key3");
- map *result;
- char *keys[8] = {
- "3082018",
- "4082018",
- "5082018",
- "6082018",
- "7082018",
- "8082018",
- "9082018",
- "10082018"
- };
- for (i = 0; i < 8; i++) {
- if ((result = lookup(keys[i])) == NULL) {
- printf("key not found\n");
- }
- else {
- printf("%s->%s %s %s\n", result->KEY, result->time, result->duration, result->description);
- fprintf(output_stream, "%s->%s %s %s\n", result->KEY, result->time, result->duration, result->description);
- }
- }
- printf("\n");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment