Hash Table Problem.

This is a discussion on Hash Table Problem. within the C Programming forums, part of the General Programming Boards category; Hey, it's me again. Sorry to be such a bother but this should be the last time for a little ...

  1. #1
    Registered User
    Join Date
    Jul 2005
    Posts
    21

    Hash Table Problem.

    Hey, it's me again. Sorry to be such a bother but this should be the last time for a little while, I assure you.

    The program I've been working on the past week or so is a hash table, using an array of linked lists to do various functions using an input file and an output file. I've been cobbling the program together from notes, a textbook, and several basic functions already written out. The problem is that now that I've written the code, the compiler has found a large number of errors, stemming from the fact that I stupidly assumed there was some kind of string variable in C that didn't exist. So now I've tried to fix the problem but I don't know how to make the errors stop. I'm totally lost.

    So I'm posting my code here, and I'm hoping that somebody can help me iron out at least some of the issues. Thanks for any assistance you guys can give.

    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <ctype.h>
    
    #define MAXSTRING 100
    
    int calcindex(char j[100]);
    struct node* addnode(struct node *j, char k[100], int l);
    int lookup(char j[100], struct node *k);
    void changeref(char j[100], struct node *k);
    int print(struct node *j, FILE *k);
    
    int main(void)
    {
    	/*Necessary variables.*/
    	FILE *ifp, *ofp;
    	char item[MAXSTRING];
    	char command[MAXSTRING];
    	int index;
    	int search;
    	int i;
    	/*Create linked list node structure.*/
    	struct StringNode {
    		char name[MAXSTRING];
    		int refcount;
    		struct node *next;
    	};
    	/*Create array[19] of these nodes.*/
    	struct StringNode strarray[19];
    	/*Open input file.*/
    	ifp = fopen("inputfile.txt", "r");
    	/*Open output file*/
    	ofp = fopen("outputfile.txt", "w");
    	/*Do until command equals end of input file.*/
    	while (fscanf(ifp, "%s", &command) != EOF) {
    		/*Get string from file.*/
    		fscanf(ifp, "%s", &item);
    		/*Print command and string to output file.*/
    		fprintf(ofp, "%s	%s", command, item);
    		/*Check to see if command is Dec or Use.*/
    		/*If the command is Dec:*/
    		if (command == "DEC") {
    			/*Use calculate index function.*/
    			index = calcindex(item);
    			/*Check indexed linked list for name by searching list at specific index*/
    			search = lookup(item, strarray[index]);
    			/*If name exists in list*/
    			if (search == 1){
    				/*Print error message "***Duplicate Name***" to output file*/
    				fprintf(ofp, "	***Duplicate Name***");
    				/*Start a new line.*/
    				fprintf(ofp, "\n");
    			}
    			/*If name does not exist in list*/
    			else {
    				/*Use add node function with proper name, reference count, and pointer.*/
    				strarray[index] = addnode(strarray[index], item, strarray[index].refcount);
    				/*Start new line on output file.*/
    				fprintf(ofp, "\n");
    			}
    		}
    		/*If the command is Use:*/
    		else {
    			/*Use calculate index function.*/
    			index = calcindex(item);
    			/*Check indexed linked list for name by searching list at specific index*/
    			search = lookup(item, strarray[index]);
    			/*If name exists in list*/
    			if (search == 1) {
    				/*Reference count +1*/
    				changeref(item, strarray[index]);
    				/*Start new line on output file.*/
    				fprintf(ofp, "\n");
    			}
    			/*If name does not exist in list*/
    			else {
    				/*Print error message "***Undefined Name***" to output file*/ 
    				fprintf(ofp, "	***Undefined Name***");
    				/*Start a new line.*/
    				fprintf(ofp, "\n");
    			}
    		}
    	}
    	/*Cycle through array.*/
    	for (i = 0; i < 19; i++) {
    		/*If current linked list is empty*/
    		if (strarray[i] == NULL) {
    			/*Continue*/
    			continue;
    		}
    		/*If current linked list has data*/
    		else {
    			/*Print current array field.*/
    			fprintf(ofp, "%d	", i);
    			/*Use print function*/
    			print(strarray[i], *ofp);
    		}
    	}
    	/*Close input file.*/
    	fclose(ifp);
    	/*Close output file.*/
    	fclose(ofp);
    	/*End program.*/
    	return 0;
    }
    
    int calcindex(char value) {
    	int total = 0;
    	int i;
    	/*Until the end of the string*/
    	for (i=0; i<strlen(value); i++) {
    		/*If current character is a letter*/
    		if (isalpha(value[i])) {
    			/*If current character is uppercase*/
    			if (isupper(value[i])) {
    				/*Add to total this value*/
    				total = value[i] - 'A' + 1;
    			}
    			/*If current character is lowercase*/
    			else {
    				/*Add to total this value*/
    				total = value[i] - 'a' + 1;
    			}
    		}
    		/*If current character is a number*/
    		else {
    			/*Add to total this value*/
    			total = value[i] - '0';
    		}
    	}
    	/*Return total*/
    	return total;
    }
    
    struct node* addnode(struct node *list, char n, int rc) {
    	struct node *pNew = NULL;
    	struct node *created_list = NULL;
    	/*Creating default node*/
    	pNew = (struct node*)malloc(sizeof(struct node));
    	pNew.name = n;
    	pNew.refcount = rc;
    	pNew.next = NULL;
    	/*If new node is first node in list*/
    	created_list = list;
    	if (list == NULL)
    		return pNew;
    	/*If otherwise*/
    	while (list.next != NULL)
    		list = list.next;
    	list.next = pNew;
    	/*Return updated list*/
    	return created_list;
    }
    
    int lookup(char value, struct node *head) {
    	/*If list node is empty, return 0*/
    	if (head == NULL)
    		return 0;
    	/*If list node contains the value, return 1*/
    	else if (value == head.name)
    		return 1;
    	/*Otherwise continue down the list*/
    	else
    		return(lookup(value, head.next));
    }
    
    void changeref(char value, struct node *head) {
    	int rc;
    	/*If list node contains the value, raise reference count by 1*/
    	if (value == head->name) {
    		rc = head.refcount;
    		rc += 1;
    		head.refcount = rc;
    	}
    	/*Otherwise continue down the list*/
    	else {
    		changeref(value, head.next);
    	}
    }
    
    int print(struct node *list, FILE *ofp) {
    	struct node current = list;
    	/*While current node is not empty*/
    	while (current != NULL)
    	{
    		/*Print out the node information*/
    		fprintf(ofp, "	%s	%d\n", current.name, current.refcount);
    		/*Continue to the next node*/
    		current = current.next;
    	}
    	return 1;
    }

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Well in the event you get errors, and you want help on them, it's usually a good idea to actually tell us what error you're getting.

    However, at a quick glance:
    Code:
    if (command == "DEC") {
    You cannot compare strings this way. You must use something like strcmp.
    Code:
    int print(struct node *list, FILE *ofp) {
    	struct node current = list;
    	/*While current node is not empty*/
    	while (current != NULL)
    	{
    		/*Print out the node information*/
    		fprintf(ofp, "	%s	%d\n", current.name, current.refcount);
    		/*Continue to the next node*/
    		current = current.next;
    	}
    	return 1;
    }
    This is completely wrong.
    1) Why are you returning anything, when all you ever return is 1? Why not make it void?
    2) You should be using a pointer instead of assigning a pointer to a variable instance incorrectly.
    3) As mentioned above, your assignment, should you wish to use an instance instead of a pointer, is wrong.
    4) Current will never be NULL, because it's an actual instance, and until the function ends, it will always exist.

    Consider:
    Code:
    void listprint(struct node *list, FILE *ofp) {
    	struct node *current = list;
    	/*While current node is not empty*/
    	while (current != NULL)
    	{
    		/*Print out the node information*/
    		fprintf(ofp, "	%s	%d\n", current->name, current->refcount);
    		/*Continue to the next node*/
    		current = current->next;
    	}
    }
    There very well may be more, I just didn't feel like compiling it.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    You have a fundamental misunderstanding of arrays and pointers, you've clearly been weaned on Java, and it looks like you started using StringNode, but changed your mind halfway through writing the program. This compiles, but I didn't run it. Rather than just try and get it to work, I suggest you actually take the time to compare my changes with your code and to figure out why I made those changes:
    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <ctype.h>
    
    #define MAXSTRING 100
    
    /*Create linked list node structure.*/
    struct node {
      char name[MAXSTRING];
      int refcount;
      struct node *next;
    };
    
    int calcindex(char j[100]);
    struct node* addnode(struct node *j, char k[100], int l);
    int lookup(char j[100], struct node *k);
    void changeref(char j[100], struct node *k);
    int print(struct node *j, FILE *k);
    
    int main(void)
    {
      /*Necessary variables.*/
      FILE *ifp, *ofp;
      char item[MAXSTRING];
      char command[MAXSTRING];
      int index;
      int search;
      int i;
    
      /*Create array[19] of these nodes.*/
      struct node *strarray[19] = {0};
      /*Open input file.*/
      ifp = fopen("inputfile.txt", "r");
      /*Open output file*/
      ofp = fopen("outputfile.txt", "w");
      /*Do until command equals end of input file.*/
      while (fscanf(ifp, "%s", &command) != EOF) {
        /*Get string from file.*/
        fscanf(ifp, "%s", &item);
        /*Print command and string to output file.*/
        fprintf(ofp, "%s	%s", command, item);
        /*Check to see if command is Dec or Use.*/
        /*If the command is Dec:*/
        if (strcmp(command, "DEC") == 0) {
          /*Use calculate index function.*/
          index = calcindex(item);
          /*Check indexed linked list for name by searching list at specific index*/
          search = lookup(item, strarray[index]);
          /*If name exists in list*/
          if (search == 1){
            /*Print error message "***Duplicate Name***" to output file*/
            fprintf(ofp, "	***Duplicate Name***");
            /*Start a new line.*/
            fprintf(ofp, "\n");
          }
          /*If name does not exist in list*/
          else {
            /*Use add node function with proper name, reference count, and pointer.*/
            strarray[index] = addnode(strarray[index], item, strarray[index]->refcount);
            /*Start new line on output file.*/
            fprintf(ofp, "\n");
          }
        }
        /*If the command is Use:*/
        else {
          /*Use calculate index function.*/
          index = calcindex(item);
          /*Check indexed linked list for name by searching list at specific index*/
          search = lookup(item, strarray[index]);
          /*If name exists in list*/
          if (search == 1) {
            /*Reference count +1*/
            changeref(item, strarray[index]);
            /*Start new line on output file.*/
            fprintf(ofp, "\n");
          }
          /*If name does not exist in list*/
          else {
            /*Print error message "***Undefined Name***" to output file*/ 
            fprintf(ofp, "	***Undefined Name***");
            /*Start a new line.*/
            fprintf(ofp, "\n");
          }
        }
      }
      /*Cycle through array.*/
      for (i = 0; i < 19; i++) {
        /*If current linked list is empty*/
        if (strarray[i] == NULL) {
          /*Continue*/
          continue;
        }
        /*If current linked list has data*/
        else {
          /*Print current array field.*/
          fprintf(ofp, "%d	", i);
          /*Use print function*/
          print(strarray[i], ofp);
        }
      }
      /*Close input file.*/
      fclose(ifp);
      /*Close output file.*/
      fclose(ofp);
      /*End program.*/
      return 0;
    }
    
    int calcindex(char value[]) {
      int total = 0;
      size_t i;
      /*Until the end of the string*/
      for (i=0; i<strlen(value); i++) {
        /*If current character is a letter*/
        if (isalpha(value[i])) {
          /*If current character is uppercase*/
          if (isupper(value[i])) {
            /*Add to total this value*/
            total = value[i] - 'A' + 1;
          }
          /*If current character is lowercase*/
          else {
            /*Add to total this value*/
            total = value[i] - 'a' + 1;
          }
        }
        /*If current character is a number*/
        else {
          /*Add to total this value*/
          total = value[i] - '0';
        }
      }
      /*Return total*/
      return total;
    }
    
    struct node* addnode(struct node *list, char n[], int rc) {
      struct node *pNew = NULL;
      struct node *created_list = NULL;
      /*Creating default node*/
      pNew = malloc(sizeof(struct node));
      strcpy(pNew->name, n);
      pNew->refcount = rc;
      pNew->next = NULL;
      /*If new node is first node in list*/
      created_list = list;
      if (list == NULL)
        return pNew;
      /*If otherwise*/
      while (list->next != NULL)
        list = list->next;
      list->next = pNew;
      /*Return updated list*/
      return created_list;
    }
    
    int lookup(char value[], struct node *head) {
      /*If list node is empty, return 0*/
      if (head == NULL)
        return 0;
      /*If list node contains the value, return 1*/
      else if (strcmp(value, head->name) == 0)
        return 1;
      /*Otherwise continue down the list*/
      else
        return(lookup(value, head->next));
    }
    
    void changeref(char value[], struct node *head) {
      int rc;
      /*If list node contains the value, raise reference count by 1*/
      if (strcmp(value, head->name) == 0) {
        rc = head->refcount;
        rc += 1;
        head->refcount = rc;
      }
      /*Otherwise continue down the list*/
      else {
        changeref(value, head->next);
      }
    }
    
    int print(struct node *list, FILE *ofp) {
      struct node *current = list;
      /*While current node is not empty*/
      while (current != NULL)
      {
        /*Print out the node information*/
        fprintf(ofp, "	%s	%d\n", current->name, current->refcount);
        /*Continue to the next node*/
        current = current->next;
      }
      return 1;
    }
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    Jul 2005
    Posts
    21
    Actually, yeah, Prelude, I have been weaned on Java so to speak. I'm taking classes in both languages at the same time (out of necessity, not desire) so I guess I've gotten a little scatterbrained.

    Anyway, to Quzah: I forgot about strcmp completely. It's been a while since I've had to do anything with strings at all, so thank you for pointing that out. That got rid of a lot of errors. Also, in reference to the print function, I took that function almost verbatim from some notes of mine, so that's why it returns a 1, but I also thought that didn't make sense when I wrote it to begin with so I took your advice and changed it to a void function that returns nothing.

    To Prelude: All the changes you made make a lot of sense, and yes, I kind of lost track of a lot of things while I was building this code, such as the whole [] thing, and where the pointers had to be, and the position of the node structure code. Thank you so much for all of your help.

    The program compiles fine now, but it also doesn't run. When I run it, it doesn't do anything for a while and then it tells me that it has had an error and has to close. Doesn't specify what the error is at all, but I assume it has to do with the files, possibly?

    I'm going to attach the input file to this post. The output file is just a blank Notepad file. Can someone see if they can get the program to run? Without knowing what's causing the trouble, I don't even know what to change in the code.

    Actually, looking at my folder with the files and program, it seems like my computer tried to add data to the output file and failed in the process, since there's a file with no extension called output in addition to the txt. file.
    Attached Files Attached Files

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    We won't solve all of your problems for you. A huge portion of programming is debugging, and since you have to learn it eventually, it might as well be now.
    My best code is written with the delete key.

  6. #6
    Registered User
    Join Date
    Jul 2005
    Posts
    21
    I wasn't asking for all my problems to be solved, and I'm sorry if I sounded that way. I am trying to solve it on my end. I'm just asking for help, which doesn't necessarily ask for a solution, just for help.

    EDIT: I also don't know how to use the debugger. It's a foreign language to me.
    Last edited by penance; 07-24-2005 at 10:33 AM.

  7. #7
    Registered User
    Join Date
    Jul 2005
    Posts
    21
    I ran the debugger and it says "Unhandled exception in program.exe: 0xC0000005: Access Violation."

    I don't know what that means.

    And then it points to this line:

    strarray[index] = addnode(strarray[index], item, strarray[index]->refcount);

    But as near as I can tell, there's nothing wrong with that line of code.

    I don't understand.

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You are probably running off of the end of an array. Try showing the value of index before the call. Access violations and segmentation faults are you trying to tinker with memory where you don't belong.


    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    Registered User
    Join Date
    Jul 2005
    Posts
    21
    Well, what you said really helped because I realized my calcindex function was totally wrong, as the formula called for all letters to be multiplied by 3, all numbers by 5, both totals added together, and the whole thing modded by 19 to get the hash index. I printed the value of index to the screen after the adjustments and it's getting the right index for everything, so that isn't the problem, unfortunately.

  10. #10
    Registered User
    Join Date
    Jul 2005
    Posts
    21
    Oh holy ........, I figured it out. I never set each node's reference value equal to anything. I changed the addnode function so that it no longer takes in a reference value, it assigns the value to 0 when it creates the node, and now the program works. Works without a hitch.

    Thank you all so much for your assistance in making this beautiful program come to life.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. trying to make a hash table......trouble w/ memory?
    By cuizy in forum C Programming
    Replies: 3
    Last Post: 05-11-2009, 05:47 PM
  2. Hash Table outputting incorrect number
    By Paul Skinner in forum C Programming
    Replies: 4
    Last Post: 11-20-2008, 06:19 AM
  3. Hash Table implementation
    By supaben34 in forum C++ Programming
    Replies: 6
    Last Post: 09-26-2003, 01:48 PM
  4. Problem with Hash Table Linear Probing
    By kirby1024 in forum C Programming
    Replies: 5
    Last Post: 10-23-2002, 07:03 AM
  5. help with creating a hash table
    By newbie40 in forum C++ Programming
    Replies: 3
    Last Post: 08-15-2002, 08:31 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21