I need help~~Hash~~THX!

This is a discussion on I need help~~Hash~~THX! within the C Programming forums, part of the General Programming Boards category; Write a program that uses a hashing algorithm to create a list of inventory parts and their quantities sold... Hash ...

  1. #1
    Registered User
    Join Date
    Apr 2004
    Posts
    2

    Unhappy I need help~~Hash~~THX!

    Write a program that uses a hashing algorithm to create a
    list of inventory parts and their quantities sold...

    Hash Method: Modulo Division
    Collision Resolution Method: Linked Lists (sorted by key: part code)

    use the following linked list functions:
    insertNode, searchList, printList, destroyList.
    Define similar hash functions: insertHash, searchHash, printHash, destroyHash.

    Get the hash size (10) from the user and then dynamically allocate the hash array.
    Load the hash array from a text file: PARTS.TXT.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <crtdbg.h>
    
    typedef struct{
    	int code;
    	int qty;
    	/* more fields */
    } PART;
    
    typedef struct nodeTag{
    	PART            part;
    	struct nodeTag *link;
    } NODE;
    
    
    /* one more typedef is to be added here */
    
    
    
    
    void  welcome  ( void );
    void  farewell ( void );
    
    int main (void)
    {
    /*  Local Definitions */
      
    
    /*  Statements */
    	welcome();
      
    	
    	 
    	farewell();
        printf( _CrtDumpMemoryLeaks() ? "Memory Leak\n" : "No Leak\n");
    
    	return 0;
    
    }
    
    
    /* ============================== welcome ==============================
    	Prints a welcome message.
    	   PRE  : nothing
    	   POST : welcome message printed
    */
    void welcome (void)
    {
    /*  Local Definitions */
    
    /*  Statements */
    	printf("\n\n\t\tHASHING\n\n");
    	printf("\tThis program builds and processes a hash array of parts \n"
               "\tusing the linked list collision resolution method.\n\n");
    
    	return;
    
    } /* welcome */
    
    /* ============================== farewell ==============================
    	Prints a farewell message.
    	   PRE  : nothing.
    	   POST : farewell message printed
    */
    void farewell (void)
    {
    	printf("\n\t\tThank you for using the program,"
    		   "\n\t\tHave a great day!\n");
    
    	return;
    
    } /* farewell */
    
    
    /*=========================================================================
                                
    						BASIC LINKED LIST FUNCTIONS
    
      ========================================================================= */
    
    /* ============================== searchList ==============================
    	Given key value, finds the location of a node in a sorted list.
    	   PRE  : pList - a pointer to the first node of a linked list
    	   	      pPre points to variable to receive predecessor
    		      pCur points variable to receive current node
    		      target is key being searched
    	   POST : pCur points to first node with equal/greater key 
                       -or- null if target > key of last node
    		      pPre points to largest node smaller than key 
                       -or- null if target > key of first node
    		      function returns 1 if found, 0 if not found
    */
    int searchList (NODE *pList, NODE **pPre, NODE	**pCur, int targetCode)
    {
    /*  Local Definitions */
    	int found = 0;
    
    /*  Statements */
    	*pPre = NULL;
    	*pCur = pList;
    
    	while(*pCur != NULL && targetCode > (*pCur)->part.code)
        {
    		*pPre = *pCur;
    		*pCur = (*pCur)->link;
    	} /* while */
    
    	if(*pCur && targetCode == (*pCur)->part.code)
    		found = 1;
    
    	return found;
    
    } /* searchList */
    
    /* ============================== insertNode ==============================
    	Inserts a node into a linked list.
           PRE  : pList - a pointer to the first node of the linked list; may be NULL
    	   	      pPre points to new node's logical predecessor
    		      item contains data to be inserted
    	   POST : returns pList
    */
    NODE *insertNode (NODE *pList, NODE *pPre, PART *part)
    {
    /*  Local Definitions */
    	NODE *pNew;
    
    /*  Statements */
    	if(!(pNew = (NODE *)malloc(sizeof(NODE))))
    		printf("\aMemory overflow in inser\n"),exit(100);
    
    	pNew->part = *part;
    	if(pPre == NULL)
        {
    		pNew->link = pList;
    		pList	   = pNew;
    	} 
    	else 
        {
    		pNew->link = pPre->link;
    		pPre->link = pNew;
    	} 
    
    	return pList;
    
    } /* insertNode */
    
    /* ============================== deleteNode ==============================
    	Deletes a node from a linked list.
    	   PRE  : pList - a pointer to the first node of a linked list
    	  	      pPre points to node before the delete node
    	 	      pCur points to the node to be deleted
    	   POST : deletes and recycles pCur
    		      returns pList
    */
    NODE *deleteNode (NODE *pList, NODE *pPre, NODE *pCur)
    {
    /*  Local Definitions */
    
    /*  Statements */
    	if(pPre == NULL)
    		pList = pCur->link;
    	else
    		pPre->link = pCur->link;
    
    	free (pCur);
    
    	return pList;
    
    } /* deleteNode */
    
    /* ============================== printList ==============================
    	Prints a linked list.
    	   PRE  : pList - a pointer to the first node of a linked list
    	   POST : List has been printed.
    */
    void printList (NODE *pList)
    {
    /*  Local Definitions */
    	NODE *pWalker;
    
    /*  Statements */
    	pWalker = pList;
    	while(pWalker)
    	{
    		printf("%4d", pWalker->part.code); /* some changes needed here */
    		pWalker = pWalker->link;
    	} 
    	printf("\n");
    
        return;
    
    } /* printList */
    
    /* ============================== destroyList ==============================
    	Free the memory after being used by linked list.
    	   PRE  : pList - a pointer to the first node of a linked list
    	   POST : linked list destroyed; returns NULL
    */
    NODE *destroyList (NODE *pList)
    {
    /*  Local definitions */
    	NODE *pDel;
    	NODE *pCur;
    
    /*  Statements */
    	pCur = pList;
    	while(pCur != NULL)
    	{
    		pDel = pCur;
    		pCur = pCur->link;
    		free(pDel);
    	} 
    	
    	return NULL;
    
    } /* destroyList */
    _________________________________________
    PARTS.TXT
    112 12
    130 30
    156 56
    173 17
    197 19
    150 50
    166 66
    113 13
    123 12
    143 14
    167 16
    189 18
    193 19
    117 11
    176 76
    ___________________________________________
    Last edited by Salem; 04-22-2004 at 02:43 AM. Reason: Code tagging

  2. #2
    Ultraviolence Connoisseur
    Join Date
    Mar 2004
    Posts
    472
    i hope you're not asking us to finish this for you? try asking WHAT EXACTLY you need help with.

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    1) Use code tags. Indent while you do it also.
    2) What is it exactly you need help with? No one here is going to read your entire program just to guess what it is you're having problems with.

    [edit]3) Curses, foiled again![/edit]

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

  4. #4
    Registered User
    Join Date
    Apr 2004
    Posts
    2

    Unhappy I dunno how to build a hash list&how to use calloc

    pls help~
    thx~

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    pls learn to read~
    thx~


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

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Hash Method: Modulo Division
    Well, that leaves...just about everything, doesn't it?

    >Collision Resolution Method: Linked Lists (sorted by key: part code)
    Also known as separate chaining.

    >use the following linked list functions:
    >insertNode, searchList, printList, destroyList.
    Okay, I'll have to now assume that the code you've posted was given to you, not written by you.

    >Define similar hash functions: insertHash, searchHash, printHash, destroyHash.
    Insert isn't difficult; you just need to hash the key, search the list there to see if the item already exists and if it doesn't, insert the item in that list.

    Searching is even easier, just remove the insertion into the list step.

    Printing is easy as well. Walk down the array printing lists.

    Destroying the hash table is just a variant of printing; all you need to do is walk down the array destroying lists.

    So what was your question?
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

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