list.h

这是顺序表的实现代码,适合数据结构初学者参考.

enum error_code {success, overflow , underflow , range_err};

#define key int

template <class entry>
class list
{
public:
	list(int max = 10);
	bool empty();
	bool full();
	int size();
	void clear();
	error_code insert(int, entry &);
	error_code remove(int);
	error_code retrieve(int, entry &);
	error_code remove_retrieve(int, entry &);
	error_code replace(int, entry &);
protected:
	entry *items;
	int length, max_length;
};

//define
template <class entry>
list<entry>::list(int max)
{
	items = new entry[max];
	length = 0;
	max_length = max;
}
//end

//define function
template <class entry>
bool list<entry>::empty()
{
	return length == 0;
}

template <class entry>
bool list<entry>::full()
{
	return length == max_length;
}

template <class entry>
int list<entry>::size()
{
	return length;
}

template <class entry>
void clear()
{
	length = 0;
}

template <class entry>
error_code list<entry>::insert(int position, entry &item)
{
	int count = length-1;

	if (length >= max_length) return overflow;
	if (position > length || position < 0) return range_err;

	while (count >= position)
	{
		items[count + 1] = items[count];
		count --;
	}
	
	items[position] = item;
	length++;

	return success;
}

template <class entry>
error_code list<entry>::remove(int position)
{
	int count;
	if (length == 0) return underflow;
	if (position < 0 || position >= length) return range_err;

	for (count = position; count < length-1; count++) items[count] = items[count + 1];

	length--;

	return success;
}

template <class entry>
error_code list<entry>::retrieve(int position, entry &item)
{
	if (length == 0) return underflow;
	if (position < 0 || position >= length) return range_err;

	item = items[position];

	return success;
}

template <class entry>
error_code list<entry>::remove_retrieve(int position, entry &item)
{
	int count;

	if (length == 0) return underflow;
	if (position < 0 || position >= length) return range_err;

	item = items[position];
	
	for (count = position; count < length-1; count++) items[count] = items[count + 1];

	length--;
	return success;
}

template <class entry>
error_code list<entry>::replace(int position, entry &item)
{
	if (length == 0) return underflow;
	if (position < 0 || position >= length) return range_err;

	items[position] = entry;

	return success;
}
//end

//order_list
class order_list: public list<key>
{
public:
	order_list(int max = 10);
	error_code insert(key);
};