4 Replies - 6705 Views - Last Post: 14 October 2010 - 12:13 AM Rate Topic: -----

#1 Cancos  Icon User is offline

  • D.I.C Head

Reputation: 8
  • View blog
  • Posts: 66
  • Joined: 04-February 09

Quadratic Probing

Posted 12 October 2010 - 04:42 PM

Anyone got a nice guide or introduction to Quadratic Probing? Thank you in advance!
Is This A Good Question/Topic? 0
  • +

Replies To: Quadratic Probing

#2 Salem_c  Icon User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 1654
  • View blog
  • Posts: 3,131
  • Joined: 30-May 10

Re: Quadratic Probing

Posted 13 October 2010 - 12:42 AM

http://www.google.co...adratic+Probing
Now tell us which you've read, and which you consider "too hard" or "too easy".

Only then would we have a chance of providing a "just right" (for you) resource.

This post has been edited by Salem_c: 13 October 2010 - 12:44 AM

Was This Post Helpful? 0
  • +
  • -

#3 Cancos  Icon User is offline

  • D.I.C Head

Reputation: 8
  • View blog
  • Posts: 66
  • Joined: 04-February 09

Re: Quadratic Probing

Posted 13 October 2010 - 11:47 AM

http://www.cplusplus...C++/code53.html

this is the link to the quadratic probing that is in my book. I can follow it for the most part, but dont know how to implement it into my previously created hash table.

Would you like to see some code?
Was This Post Helpful? 0
  • +
  • -

#4 Cancos  Icon User is offline

  • D.I.C Head

Reputation: 8
  • View blog
  • Posts: 66
  • Joined: 04-February 09

Re: Quadratic Probing

Posted 13 October 2010 - 07:19 PM

I figured out how to do the quadratic probing, now I face another issue.

Once my table is half full, I want to resize the table by a prime number that is bigger(preferably 2x bigger) than my current tableSize.

Every time I seem to try and implement the resize for my table, the program crashes. Any suggestions/ideas out there?


#include <iostream>
#include <string>
using namespace std;

int main()
{
	class student
	{
		public:
			string lname;
			string fname;
			int id;
			double gpa;
			int info;
			
			student(){}

			student(string l, string f, int i, double g)			
			{
				lname = l;
				fname = f;
				id = i;
				gpa = g;
			}
	};

	class hashTable
	{
	private:
		student *table;
		int tableSize;
		int filled;
		int ACTIVE;
		int EMPTY;


	public:
		hashTable()
		{
			table = new student[0];
			tableSize = 0;
		}

		hashTable(int size)
		{
			EMPTY = -1;
			ACTIVE = 0;
			tableSize = size;
			table = new student[tableSize];

			for(int i = 0; i < tableSize; i++)
			{		
				table[i].info = EMPTY;			
			}
			filled = 0;
			

		}

		int hash(int id)
		{
			return(id%tableSize);
		}

		int rehash(int id)
		{
			return ((id+1)%tableSize);
		}

		bool insert(student s)
		{
		int current = hash(s.id);

		if(filled >= tableSize)
		{
			cout << "Cannot insert student, table is full!" << endl;
			return false;
		}

		for(int i = 1; table[current].info != EMPTY; i++)
		{
				current = (current + (i * i - i)/2)% tableSize;
		}
		
		if(table[current].info == EMPTY && current < tableSize)
			{
				table[current].lname = s.lname;
				table[current].fname = s.fname;
				table[current].id = s.id;
				table[current].gpa = s.gpa;
				table[current].info = ACTIVE;
				filled++;
			}
		if(filled >= (tableSize/2))
		{
			//Need to resize the table!!             <-------------Table Resize
		}
		return true;
		}
		
		void display()
		{
			for(int i = 0; i < tableSize; i++)
			{
				cout << table[i].lname << endl;
			}
		}
	};


	hashTable table(3);
	
	table.insert(student("Johnson", "Randall", 12340, 3.0));
	table.insert(student("Medina", "William", 12340, 3.0));
	table.insert(student("Cortez", "Xiao", 12340, 3.0));
	table.insert(student("Pancho", "Villa", 12340, 3.0));
	//table.insert(student("Testing", "Number", 12340, 3.0));
	//table.insert(student("Alaniz", "Shorty", 12340, 3.0));
	//table.insert(student("Beava", "Fire", 12340, 3.0));
	//table.insert(student("Worked", "Out", 12340, 3.0));
	//table.insert(student("Calculator", "TI", 12340, 3.0));
	//table.insert(student("Griffin", "Peter", 12340, 3.0));
	//table.insert(student("Betty", "Cow", 12340, 3.0));
	//table.insert(student("Tuscan", "Turkey", 12340, 3.0));

	table.display();
	return 0;
}


Was This Post Helpful? 0
  • +
  • -

#5 Salem_c  Icon User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 1654
  • View blog
  • Posts: 3,131
  • Joined: 30-May 10

Re: Quadratic Probing

Posted 14 October 2010 - 12:13 AM

Yes, post ONE of your attempts at solving the resize problem.

Posting "well I tried", and then an "insert code here" comment doesn't really show us what sort of attempt you made, or precisely what kind of difficulty you're having.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1