double_list.cpp

这是双向链表的实现,适合数据结构初学者.希望能给大家带来帮助 !

#include "stdafx.h"
#include "double_list.h"

//node
node::node()
{
	next = 0;
	front = 0;
}

node::node(record n_item, node *n_front, node *n_next)
{
	item = n_item;
	front = n_front;
	next = n_next;
}
//end

//d_list
d_list::d_list()
{
	head = NULL;
	rear = NULL;
	length = 0;
}

d_list::d_list(d_list &from)
{
	node *p1 = from.rear;

	length = 0;
	head = NULL;
	rear = NULL;

	while (p1 != NULL)
	{
		insert(0, p1->item);
		p1 = p1->front;
	}
}

d_list::~d_list()
{
	clear();
}

int d_list::size()
{
	return length;
}

bool d_list::empty()
{
	return length == 0;
}

void d_list::clear()
{
	node *p1 = head, *p2;

	while (p1 != NULL)
	{
		p2 = p1;
		p1 = p2->next;
		delete p2;
	}

	length = 0;
	head = NULL;
	rear = NULL;
}

error_code d_list::insert(int position, record &n_item)
{
	node *n_node, *p1, *p2;

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

	set_position(position - 1, p1);
	if (p1 != NULL) p2 = p1->next;
	else if (head != NULL) p2 = head;
	else p2 = NULL;

	n_node = new node(n_item, p1, p2);

	if (n_node == NULL) return overflow;

	if (p1 != NULL) p1->next = n_node;
	else head = n_node;

	if (p2 != NULL) p2->front = n_node;
	else rear = n_node;

	length ++;

	return success;
}

error_code d_list::remove(int position)
{
	node *p1;

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

	set_position(position, p1);

	if (p1->front != NULL) p1->front->next = p1->next;
	else head = p1->next;

	if (p1->next != NULL) p1->next->front = p1->front;
	else rear = p1->front;

	length --;

	return success;
}

error_code d_list::replace(int position, record &n_item)
{
	node *p1;

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

	set_position(position, p1);

	p1->item = n_item;

	return success;
}

error_code d_list::retrieve(int position, record &r_item)
{
	node *p1;

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

	set_position(position, p1);

	r_item = p1->item;

	return success;
}

d_list& d_list::operator = (d_list &sec)
{
	d_list *p_list = new d_list(sec);

	clear();

	head = p_list->head;
	rear = p_list->rear;
	length = p_list->length;

	return *p_list;
}

error_code d_list::set_position(int position, node *&p_node)
{
	if (position < -1 || position > length) return range_err;

	if (position == -1 || position == length) p_node = NULL;
	else for (p_node = head; position != 0; position --) p_node = p_node->next;

	return success;
}
//end