clinkedlist.cpp

一个可以存放任何数据类型的链表类

#include "CLinkedList.h"

template <class T>
void Node<T>::SetNext(Node<T> * node)
{
	this->next = node;
}

template <class T>
Node<T> * Node<T>::GetNext()
{
	return this->next;
}

template <class T>
T Node<T>::GetData()
{
	return this->data;
}

template <class T>
CLinkedList<T>::CLinkedList()
{
	this->CreateLinkedList();
}

template <class T>
CLinkedList<T>::~CLinkedList()
{
	this->DestoryLinkedList();
}

template <class T>
bool CLinkedList<T>::CreateLinkedList()
{
	this->head = new Node<T>;
	this->head->SetNext(NULL);
	this->tail = this->head;

	return true;
}

// 在链尾插入数据
template <class T>
bool CLinkedList<T>::AddElement(Node<T> * node)
{
	this->tail->SetNext(node);
	this->tail = node;
	node->SetNext(NULL);
	return true;
}

// 在第index个元素之后插入
template <class T>
bool CLinkedList<T>::InsertElement(Node<T> * node,int index)
{
	if (index > this->GetLinkedListLength() || index < 1)
		return false;
	Node<T> * temp = this->head;
	for (int i = 0;i < index;i++,temp = temp->GetNext());
	node->SetNext(temp->GetNext());
	temp->SetNext(node);
	temp = temp->GetNext();
	if (index == this->GetLinkedListLength())
	{
		this->tail->SetNext(node);
		node->SetNext(NULL);
	}
	return true;
}

//　返回链表的长度，包括链表头
template <class T>
int CLinkedList<T>::GetLinkedListLength()
{
	Node<T> * temp = this->head;
	for (int i = 0;temp;temp = temp->GetNext(),i++);
	return i;
}

// 取得第index个元素
template <class T>
T CLinkedList<T>::GetElement(int index)
{	
	Node<T> * temp = this->head;
	
	for (int i = 0;i < index;i++,temp = temp->GetNext());
	
	return temp->GetData();
}

// 删除第index个元素
template <class T>
bool CLinkedList<T>::DeleteElement(int index)
{
	if (index > this->GetLinkedListLength() || index < 1)
		return false;
	Node<T> * temp = this->head;
	if (index == 1)
	{
		for (int i = 0;i < index;i++,temp = temp->GetNext());
		delete this->head;
		this->head = temp;
	}
	else if (index == this->GetLinkedListLength())
	{
		for (int i = 0;i < index - 1;i++,temp = temp->GetNext());
		delete this->tail;
		this->tail = temp;
		this->tail->SetNext(NULL);
	}
	else
	{
		for (int i = 0;i < index - 1;i++,temp = temp->GetNext());
		Node<T> * tmp = temp->GetNext()->GetNext();
		delete temp->GetNext();
		temp->SetNext(tmp);
	}
	return true;
}

// 删除链表中所有元素，但是链表任然存在
template <class T>
bool CLinkedList<T>::DeleteAll()
{
	Node<T> * temp = this->head->GetNext();
	Node<T> * tmp = temp;
	for (int i = 0;temp;i++,tmp = temp,temp = temp->GetNext(),delete tmp);
	this->tail = this->head;
	this->tail->SetNext(NULL);

	return true;
}

template <class T>
bool CLinkedList<T>::DestoryLinkedList()
{
	if (!this->DeleteAll())
		return false;
	if (this->head)
		delete this->head;
	this->head = this->tail = NULL;

	return true;
}

///////////////////////////////////////////////////////////////////////

/*
 *
 *   测试代码
 *
 */

class Student
{
	public:
		char * id;
		char * name;
};
int main()
{
	// 创建链表
	CLinkedList<Student> * list = new CLinkedList<Student>;

	//　加入元素
	// 第１个学生的信息
	Student s1;
	s1.id = "12345";
	s1.name = "wanghan";
	Node<Student> * stu = new Node<Student>;
	stu->data = s1;
	stu->next = NULL;
	list->AddElement(stu);

	// 第２个学生的信息
	Student s2;
	s2.id = "12345";
	s2.name = "lihan";
	Node<Student> * stu1 = new Node<Student>;
	stu1->data = s2;
	stu1->next = NULL;
	list->AddElement(stu1);

	// 第３个学生的信息
	Student s3;
	s3.id = "12345";
	s3.name = "liuio";
	Node<Student> * stu2 = new Node<Student>;
	stu2->data = s3;
	stu2->next = NULL;
	list->InsertElement(stu2,1); // 插入在第一个学生信息之后
	
	printf("学生信息：\n");

	// 打印链表
	printf("%s,%s\n",list->GetElement(1).id,list->GetElement(1).name);
	printf("%s,%s\n",list->GetElement(2).id,list->GetElement(2).name);
	printf("%s,%s\n",list->GetElement(3).id,list->GetElement(3).name);

	// 打印链表长度
	printf("链表长度：%d\n",list->GetLinkedListLength() - 1);

	printf("删除第２个元素．．．．．．\n");
	// 删除第２个元素
	list->DeleteElement(2);
	printf("%s,%s\n",list->GetElement(1).id,list->GetElement(1).name);
	printf("%s,%s\n",list->GetElement(2).id,list->GetElement(2).name);

	// 打印链表长度
	printf("链表长度：%d\n",list->GetLinkedListLength() - 1);

	printf("删除所有元素．．．．．．．．\n");

	// 删除所有的元素
	list->DeleteAll();

	// 打印链表长度
	printf("链表长度：%d\n",list->GetLinkedListLength() - 1);

	// 删除链表
	delete list;

	getchar();
	return 0;
}