binindex.cpp

使用索引实现快速查找

//	Author:		Mohammed Ali Akbani
//	Level :		Intermediate
//	E-mail:		[e-mail]
//	MSN ID:		[e-mail]		
//		Please do not repost it in you name, and vote for me.
	
#include <conio.h>
#include <string.h>
#include <stdlib.h>
#include <iomanip.h>
#include <fstream.h>

/*
This file is in c:\borlandc\classlib\include. substitute c:\borlandc where
your c++ compiler is. add include and lib directory in Options|Directories.
the file has been included with the zip file.
*/

#include <Timer.h>


char item_code[5000][7] = { '\0' }; //array to hold codes
int indexes[16] = { -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 };

int  items=0;
char code[7] = { '\0' };

Timer time1;	//stopwatch


//LOAD DATA INTO MEMORY
void initialise()
{
	int last_index = 0;
	char cat_code[3] = { '\0' };
	int category;

	ifstream codefile("C:\\mydocu~1\\ali\\codes.txt");


	//read in data from file
	for( int i=0; i<5000; i++ )
	{
		codefile >> item_code[items];

		strncpy( cat_code, item_code[items], 2);

		category = atoi(cat_code);

		//Stores the indexx into the array
		if( category - last_index != 0)
		{
			indexes[ category ] = items;
			last_index = category;
		}
		items++;
	 }
	 codefile.close();
}



//CALCULATES THE INDEX OF THE CODE PASSED TO IT
void index(int &n1, int &n2, int &bool)
{
	char code2[3] = { '\0' };
	int  code1=0, code3 = 0;

	//Finds the category
	strncpy(code2,code,2);

	code1 = atoi(code2);

	//Check if category is valid and any data exists for it
	if( code1 > 15 || indexes[code1] == -1 )
	{
		bool = 0;
		return;
	}

	//Return the location where the codes category starts
	n1 = indexes[code1];

	//Find the higher of the index
	code3 = code1;

	//If last code
	if(code3 == 15)
		n2 = items;
	else{
		do
		{
			code3++;

		}while( (indexes[code3] == -1) && (code3 < 16) );


		n2 = indexes[code3];
		bool = 1;
	}
}



//PERFORMS LINEAR SEARCH
void linear()
{
	long  icode,item_codel;
	int   bool=0;

	time1.reset();
	time1.start();

	for( int i=0; i<items; i++ )
	{
		icode = atol( code );

		item_codel = atol ( item_code[i] );

		if( item_codel == icode )
		{
			bool=1;
			break;
		}
	}

	if(bool==0)
		cout<<"\a\n\n\t\tItem not found";

	time1.stop();

	cout << "\n\t\tTime ( Normal Linear )  : " << time1.time();

}



//PERFORMS LINEAR SEARCH USING INDEXES
void index_linear()
{
	int   n1, n2;
	long  icode,item_codel;
	int   bool=0;

	time1.reset();
	time1.start();

	index(n1,n2,bool);

	if( bool == 1 )
	{
		bool = 0;

		for( int i=n1; i<n2; i++ )
		{
			icode = atol( code );

			item_codel = atol ( item_code[i] );

			if( item_codel == icode )
			{
				bool=1;
				break;
			}
		}
	}

	if(bool==0)
		cout<<"\a\n\n\t\tItem not found";

	time1.stop();

	cout << "\n\t\tTime ( Indexed Linear ) : " << time1.time();

}



//PERFORMS BINARY SEARCH
void binary()
{
	long  icode,item_codel;
	int   low = 0, high = items-1, mid_pt;
	int   bool;

	bool = 0;


	time1.reset();
	time1.start();

	icode = atol( code );

	while( low <= high && bool == 0)
	{
		mid_pt = ( low + high ) / 2;

		item_codel = atol ( item_code[mid_pt] );

		if( item_codel == icode )
		{
			bool=1;
			break;
		}

		if( low == high || (high - low) == 1 )
			break;

		if( icode < item_codel )
		{
			high = mid_pt;
		}
		else if( icode > item_codel )
		{
			low = mid_pt;
		}

	}


	if(bool==0)
		cout<<"\a\n\n\t\tItem not found";

	time1.stop();

	cout << "\n\t\tTime ( Normal Binary )  : " << time1.time();
}



//PERFORMS BINARY SEARCH USING INDEXES
void index_binary()
{
	int   n1, n2;
	long  icode,item_codel;
	int   low=0, high, mid_pt;
	int  bool;


	bool = 0;

	time1.reset();
	time1.start();

	index(n1, n2, bool);

	if( bool ==  1 )
	{

		bool = 0, low = n1, high = n2, mid_pt = 0;

		icode = atol( code );

		while( low <= high && bool == 0)
		{
			mid_pt = ( low + high ) / 2;

			item_codel = atol ( item_code[mid_pt] );

			if( item_codel == icode )
			{
				bool=1;
				break;
			}

			if( low == high || (high - low) == 1 )
				break;

			if( icode < item_codel )
			{
				high = mid_pt;
			}
			else if( icode > item_codel )
			{
				low = mid_pt;
			}

		}

	}

	if(bool==0)
		cout<<"\a\n\n\t\tItem not found";

	time1.stop();

	cout << "\n\t\tTime ( Indexed Binary ) : " << time1.time();
}



void main()
{
	char  choice = '\0';

	cout.setf( ios :: fixed );
	cout.setf( ios :: showpoint );
        cout.precision( 5 );

	initialise();

	clrscr();

	while( choice != 27 )
	{
		clrscr();

		cout << "\n\t\tItems in list : " << items;

		cout << "\n\n\t\tItem Code: ";
		cin >> code;

		index_binary();
		binary();

		index_linear();
		linear();

		cout << "\n\n\nPress any key to continue (ESC to quit): ";
		choice = getch();
	}
}