order_list.cpp

这是数据结构初学者的极佳参考资料,里面包含有查找和排序的相关方法,如二分查找和快速排序等.

#include "list.h"

//struct define
order_list::order_list(int max)
{
	length = 0;
	max_length = max;
	items = new key[max];
}
//end

//order_list function
error_code order_list::insert_byOrder(key record)
{
	if (length >= max_length) return overflow;

	int position = size();
	while (items[position-1] >= record && position != 0) position--;
	list<key>::insert(position, record);

	return success;
}

error_code order_list::search1_recursive(key &target, int &position, int top, int bottom, order_list &old)
{
	error_code outcome;
	int mid = (top + bottom) / 2;
	key record;
	
	if (top < bottom) return fail;

	old.retrieve(mid, record);

	if (record == target) 
	{
		position = mid;
		return success;
	}

	record > target ? outcome = search1_recursive(target, position, mid -1, bottom, old) : outcome = search1_recursive(target, position, top, mid+1, old);
	return outcome;
}

error_code order_list::search1(key &target, int &position)
{
	return search1_recursive(target, position, size() - 1, 0, *this);
}

error_code order_list::search2(key &target, int &position)
{
	int top = size() - 1, bottom = 0, mid;
	key record;

	while (top >= bottom)
	{
		mid = (top + bottom) / 2;
		retrieve(mid, record);

		if (target == record)
		{
			position = mid;
			return success;
		}

		record > target ? top = mid - 1 : bottom = mid + 1;
	}

	return fail;
}
//end