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
___________________________________________
