From: 2644danticoj@vms.csd.mu.edu
Newsgroups: comp.lang.c
Subject: Can you program in C?
Date: 17 Nov 1992 17:30:29 GMT
Organization: Marquette University - Computer Services
Reply-To: 2644danticoj@vms.csd.mu.edu
NNTP-Posting-Host: vmsd.csd.mu.edu

Greetings--

My name is Cetera and I am new to this network. I am anxiously awaiting
graduating Marquette this December, but there is an obstacle in my way. I must
first pass this math class in which I must program in C. I don't know this
language, and now must write several programs before the end of the year. The
course teaches data structures, which I have no problems understanding.
However, all homework is programmed in C and because of an adminstrative
loop-hole, I was enrolled in the class with no knowledge of the needed
programming language. So, can you help me write these programs, thereby
allowing me to graduate and go on to serve my country as an officer on a
nuclear submarine? Please???? My future depends on it. By the way, I will be
using a UNIX machine with a STUDSYS compiler. Help!!!!!!!!!!!!!!!!!!!!!

Problem statement
*****************

Implement an open addressing hash table with a HASHSIZE of 17 and strings of 3
(or more) characters as keys. You may use the following hash function or write
you own:

typedef char *Key_type;
#include <stdlib.h>
#include "hash.h"
/* Hash: calculate the hash value of s. */
int Hash(Key_type s)
{
	int h=0;
	while (*s)
		h += *s++;
		return abs(h % HASHSIZE);
}

The file hash.h contains the following:

/* declarations for a chained hash table */
#define HASHSIZE 997
typedef char *Key_type;
typedef struct item_tag {
	Key_type key;
} Item_type;
typedef struct node_tag {
	Item_type info;
	struct node_tag *next;
} Node_type;
typedef Node_type *List_type;
typedef List_type Hashtable_type[HASHSIZE];

***************************************************************************
***************************************************************************

Problem 1
*********

Implement an insert function using linear probing to resolve collisions.

Problem 2 
*********

Implement a retrieve function using linear probing to resolve collisions.

Problem 3
*********

Write a driver that will 1) initialize a hash table, 2) set up keys to insert
and retrieve, 3) insert keys (be sure to illustrate collision), 4) retrieve
keys (be sure to illustrate collision and a key not in the table). Inform the
user of the progress of your testing by writing a stub that shows the contents
of the keys in your hash table (just by walking down the array) when
appropriate. There should be no user input. 

Extra Credit
************

Implement 2 different hash functions for the main part of the assignmant. Use 1
for one  hash table and one for another. Insert the same keys and note the
different locations that the two functions return. You may use the function
above as one, the second would be of your own creation. Your driver should have
2 hash tables (one using one functino, the other using the other) or you can
have 2 versions of the executable.  


*****************************************************************************
*****************************************************************************
******** Can you help? My graduation and future hang in the balance.*********
*****************************************************************************
******************************************************* Cetera **************
*****************************************************************************
Newsgroups: comp.lang.c