单链表的创建和一些操作

个人创建的一个类，实现单链表的基本操作，算是对数据结构知识的一点温习...

#ifndef TEMPLIST_H
#define TEMPLIST_H

#include <math.h>
#include<stdio.h>

template <class T>
class Node
{
public:
	T mydata;
	Node<T>* next;

	Node()                   //构造节点
	{
		next=NULL;   //data域尚未初始化
	}
	Node(T data,Node<T>* next1=NULL)      //构造节点，指定元素和后继结点
	{
		mydata=data;
		next=next1;
	}
};

template <class T>
class SingleLinkedList             //单链表类
{
public:
	Node<T>* head;             //头指针

	SingleLinkedList();        //构造空单链表         
	SingleLinkedList(T value[],int n);//构造由指定数组提供元素的单链表
	~SingleLinkedList();    //析构

	bool isEmpty();       //判断单链表是否为空
	void concat(SingleLinkedList<T> &list);       //将list链接在当前单链表之后
	void clear();            //清空单链表
	bool remove(int i);

	Node<T>* insert(int i,T x);
	Node<T>* getNode(int i);
	T get(int i);
	int length();            //获取链表长度
	T update(int i,T a);    //更新元素值
};

template <class T>
SingleLinkedList<T>::SingleLinkedList()
{
	this->head=NULL;
}

template <class T>
SingleLinkedList<T>::SingleLinkedList(T value[],int n)
{
	head=NULL;
	if(n>0)
	{
		head=new Node<T>(value[0]);
		Node<T>* rear = head;
		int i=1;
		while(i<n)            //将数组元素逐个链接到单链表上
		{
			rear->next = new Node<T>(value[i++]);
			rear = rear->next;
		}
	}
}

template <class T>
SingleLinkedList<T>::~SingleLinkedList()
{
	clear();
}

template <class T>
int SingleLinkedList<T>::length()
{
	int i=0;
	Node<T>* p=head;
	while(p!=NULL)
	{
		i++;
		p=p->next;
	}
	return i;
}

template <class T>
Node<T>* SingleLinkedList<T>::insert(int i,T x)
{
	Node<T>* q=NULL;
	if(head==NULL||i<=0)
	{
		q=new Node<T>(x,head);
		head=q;
	}
	else
	{
		int j=0;
		Node<T>* p=head;
		while(p->next!=NULL&&j<i-1)
		{
			j++;
			p=p->next;
		}
		q=new Node<T>(x,p->next);
		p->next=q;
	}
	return q;
}

template <class T>
bool SingleLinkedList<T>::remove(int i)      //在i位置删除元素
{
	if(head!=NULL&&i>=0)
	{
		if(i==0)
		{
			Node<T>* q=head;
			head=head->next;
			delete q;
			return true;
		}
		else
		{
			Node<T>* p=getNode(i-1);
			if(p!=NULL&&p->next!=NULL)
			{
				Node<T>* q=p->next;
				p->next=q->next;
				delete q;
				return true;
			}
		}

	}
	return false;
}

template <class T>
T SingleLinkedList<T>::update(int i,T a)
{
	Node<T>* p=getNode(i);
	p->mydata+=a;
	return p->mydata;
}

template <class T>
Node<T>* SingleLinkedList<T>::getNode(int i)
{
	if(i<0)
		return NULL;
	int j=0;
	Node<T>* p=head;                //获取结点指针
	while(p!=NULL&&j<i)
	{
		j++;
		p=p->next;
	}
	return p;
}

template <class T>
T SingleLinkedList<T>::get(int i)
{
	Node<T>* p=getNode(i);

	if(p!=NULL)
		return p->mydata;         //查找元素
	throw"指定元素序号无效";
}


template <class T>
void SingleLinkedList<T>::clear()
{
	Node<T>* p=head;
	while(p!=NULL)
	{
		Node<T>* q = p;
		p=p->next;                   //逐个删除表元素
		delete q;
	}
	head=NULL;
}

template <class T>
bool SingleLinkedList<T>::isEmpty()
{
	return head==NULL;
}

template <class T>
void SingleLinkedList<T>::concat(SingleLinkedList<T> &list)
{
	if(this->head==NULL)
		this->head=list.head;
	else{
		Node<T>* p = head;
		while(p->next!=NULL)          //找到最后一个节点
		{
			p=p->next;
		}
		p->next=list.head;             //连接两条单链表
	}
	list.head=NULL;             //设置单链表为空，否则运行错
}

#endif