1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Hash tables

Discussion in 'C++' started by 1888, Apr 14, 2008.

  1. 1888

    1888 New Member

    Joined:
    Apr 14, 2008
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    Hi there i am a beginner to c++ and i have a coursework due in at uni. one part requires me to make a hash table and i have no idea where to start this is my problem would be great if some1 could help-

    Write your own hash function* that uses the 6 digit grid reference as a key. Using this function and the hill details already generated, add the hill details to another array, this time of 63 elements. This will be your hash table.Test that a user can search the hash table by asking the user to enter a grid reference. The program should either output details of the hill at that grid reference or output that there is no hill at that grid reference.

    This is my program so far -

    Code:
    #include <iostream>
    using namespace std;
    
    struct Node{		//a structure that can be 
    	int data;		//thought of as a simple class
    	Node *link;		//All fields are public
    	int height;
    	int gridReference;
    	int distance;
    	bool climbed;
    };
    
    class LinkedList{
    public:
    	Node *head;		//pointer to the first node
    	Node *last;		//pointer to the last node
    	int count;		//number of nodes
    
    	LinkedList();	//default constructor 
    					//first = NULL
    					//last = NULL
    					//count = 0
    	
    	~LinkedList();	//destructor - deletes all nodes
    					//from the linked list 
    	
    	void insertFirstNode(int newinfo); // inserts a node
    							//at the start of the list
    	void insertLastNode(int newinfo);  // inserts a node
    							//at the end of the list
    	void insertHills(int height, int distance, bool climbed, int gridReference);
    
    	int getNodeCount();  //returns the number of nodes
    	Node* getFirst();	 //returns the pointer to the 
    						 //the first node - the value of "head"
    	void displayData();
    	void initializeHashTable(void);
    };
    
    
    #include "linkedlist.h"
    
    
    LinkedList::LinkedList(){
    	head = NULL;
    	last = NULL;
    	count = 0;
    }
    
    LinkedList::~LinkedList(){
    	Node *temp = head->link;
    	while(temp) {
    		head->link = temp->link;
    		delete temp;
    		temp = head->link;
    	}
    	delete head;
    	cout<<"linked list deleted"<<endl;
    }
    
    void LinkedList::insertFirstNode(int newInfo){
    	Node *newNode;
    	newNode = new Node;
    	newNode->data = newInfo;
    	newNode->link = head; 
    	head = newNode;
    
    	count++;
    
    	if(last == NULL){
    		last = newNode;
    	}
    }
    
    void LinkedList::insertLastNode(int newInfo){
    	Node *newNode;
    	newNode = new Node;
    	newNode->data = newInfo;
    	newNode->link = NULL; 
    
    
    	count++;
    
    	if(head == NULL){
    		head = newNode;
    		last = newNode;
    	}
    	else{
    		last->link = newNode;
    		last = newNode;
    	}
    }
    
    int LinkedList::getNodeCount(){
    	return count;
    }
    
    Node* LinkedList::getFirst(){
    	return head;
    }
    
    void LinkedList::insertHills(int height, int distance, bool climbed, int gridReference){
    
    	Node* current= head;
    	Node* previous= NULL;
    	Node* hills= new Node();
    	count++;
    
    	hills->height= height;
    	hills->distance= distance;
    	hills->climbed= climbed;
    	hills->gridReference= gridReference;
    	hills->link= NULL;
    
    	if(count==1)
    	{          
    		head= hills;
    		last= hills;
    		return;
    	}
    	do{
    		if(current->height<hills->height)
    		{
    			hills->link= current;
    
    			if(current== head)
    			{
    				head= hills;
    				return;
    			}
    			else
    			{
    				previous->link= hills;
    				return;
    			}
    			if(current==last)
    			{
    				current->link=hills;
    				last= hills;
    				return;
    			}
    		}
    		previous=current;
    		current= current->link;
    
    	}          
    	while(current!=NULL);
    }
    
    
    void LinkedList::displayData(){
    	int noOfNodes= getNodeCount();
    	Node *current;
    	current= head;
    
    
    	cout << "Number of Nodes = " << noOfNodes << endl;
    	for(int i=0; i<noOfNodes && current != NULL; i++){
    		cout<<"Hill Number: "<<count--<<endl;
    
    		cout<<"Height: "<<current->height<<endl;
    
    		cout<<"Distance from Home: "<<current->distance<<endl;
    
    		cout<<"Climbed: "<<current->climbed<<endl;
    
    		cout<<"Grid Reference: "<<current->gridReference<<endl;
    
    		cout<<"**************"<<endl;
    		current= current->link;
    
    
    	}
    }
    
    
    #include <cstdlib>
    #include <iostream>
    #include "linkedlist.h"
    
    
    
    
    
    
    
    int main(){
    	LinkedList l;
    
    	unsigned hash ( int );
    	for(int i=1; i<41; i++){
    
    		int randHeight= (rand()%1400)+3000;// generates random number for height of hill
    
    		int randDistance= (rand()%280)+20;// generates random number for distance of hill
    
    		int randGridReference= (rand()%100000)+400000;// generates random number for gridreference of hill
    
    		int randClimbedNumber= (rand()%10)+1;// generates random number to tell user if hill is climbed
    
    		bool randClimbed;
    		if(randClimbedNumber>5)//This takes the random number generated from randClimbedNumber and determines if it has been climbed or not
    		{
    			randClimbed= true;
    		}
    		else
    		{
    			randClimbed= false;
    		}
    		l.insertHills(randHeight, randDistance, randClimbed, randGridReference);
    	}     
    
    	l.displayData();
    
    	cout<<endl;
    
    
    	l.displayData();
    
    
    	return 0;
    }
    THANKS!!
     

Share This Page