linlist.h

数据结构c++-书的一些源代码

template <class T> class LinList;			//前视定义,否则友元无法定义
template <class T>							//模板类型为T
class ListNode
{
	friend class LinList<T>;					//定义类LinList<T>为友元
	friend void LinListSort(LinList<T> &L);
private:
	ListNode<T> *next;	    				//指向下一结点的指针
	T data;								//定义为公有成员方便使用
public:
	//构造函数1,用于构造头结点
	ListNode(ListNode<T> *ptrNext = NULL)
		{next = ptrNext;}

	//构造函数2,用于构造其他结点
	ListNode(const T& item, ListNode<T> *ptrNext = NULL)
		{data = item;	next = ptrNext;}

	~ListNode(void){}				//析构函数
};

//单链表类的定义
template <class T>
class LinList
{
	friend void LinListSort(LinList<T> &L);
private:
	ListNode<T> *head;				//头指针
	int size;							//当前的数据元素个数

	ListNode<T> *Index(int i);			//定位
public:
	LinList(void);						//构造函数
	~LinList(void);					//析构函数

	int ListSize(void) const;				//取当前数据元素个数
	void Insert(const T& item, int i);		//前插
	T Delete(int i);						//删除
	T GetData(int i);					//取元素

	void OrderInsert(T x);
};
 
//单链表类的实现  
template <class T> 
LinList<T>::LinList(void)					//构造函数
{
	head = new ListNode<T>();			//头指针指向头结点
	size = 0;							//size的初值为0
}

template <class T>
LinList<T>::~LinList(void)				//析构函数
{ 
	ListNode<T> *p, *q;
	p = head;						//p指向第一个结点
	while(p != NULL)				//循环释放结点空间直至初始化状态
	{
   		q = p;
		p = p->next;
		delete q;
	}
	size = 0;							//结点个数置为初始化值0
	head = NULL;
}

template <class	T>	
ListNode<T> *LinList<T>::Index(int i)		//定位
//返回指向第i个数据元素结点的指针
//参数i的取值范围为：-1≤i≤size-1；i=-1时返回头指针
{
	if(i < -1 || i > size-1)
	{
		cout << "参数i越界出错！" << endl;
		exit(0);
	}

	if(i == -1) return head;					//i为-1时返回头指针head
	ListNode<T> *p = head->next;			//p指向第一个数据元素结点
	int j = 0;								//从0开始计数
	while(p != NULL && j < i)				//寻找第i个结点
	{
		p = p->next;
		j++;
	}
	return p;								//返回第i个结点的指针
}

template <class T>
int LinList<T>::ListSize(void) const			//取当前数据元素个数并返回
{
	return size;
}

template <class T>
void LinList<T>::Insert(const T& item, int i)				//插入
//在第i个结点后插入一个元素值为item的新结点
//参数i的取值范围为：0≤i≤size
{
	if(i < 0 || i > size)
	{
		cout << "参数i越界出错！"  << endl;
		exit(0);
	}

	ListNode<T> *p = Index(i - 1);			//p为指向第i-1个结点的指针

	//构造新结点p，p的data域值为item，next域值为 p->next
	ListNode<T> *q = new ListNode<T>(item, p->next);

	p->next = q;								//新结点插入第i个结点前
	size++;									//元素个数加1
}

template <class T>
T LinList<T>::Delete(int i)				//删除
//删除第i个数据元素并返回。参数i的取值范围为：0≤i≤size-1
{
	if(size == 0) 
	{
		cout << "链表已空无元素可删！" << endl;
		exit(0);
	}

	if(i < 0 || i > size-1)
	{
		cout << "参数i越界出错！" << endl;
		exit(0);
	}

	
	ListNode<T> *s, *p = Index(i - 1);		//p为指向第i-1个结点指针

	s = p->next;								//s指向第i个结点
	p->next = p->next->next;					//第i个结点脱链
	T x = s->data;
	delete s;								//释放第i个结点空间
	size--;									//结点个数减1
	return x;								//返回第i个结点的data域值
}

template <class T>
T LinList<T>::GetData(int i)				//取数据元素
//取第i个数据元素并返回。参数i的取值范围为：0≤i≤size-1
{
	if(i < 0 || i > size-1)
	{
		cout << "参数i越界出错！" << endl;
		exit(0);
	}

	ListNode<T> *p = Index(i);				//p指向第i个结点
	return p->data;
}

template <class T>
void LinList<T>::OrderInsert(T x)
//数据元素x有序插入
{
	ListNode<T> *curr, *pre;
	//循环初始化
	curr = head->next;					//curr指向第一个数据元素结点
	pre = head;							//pre指向头结点

	//定位插入位置
	while(curr != NULL && curr->data <= x)
	{
		pre = curr;
		curr = curr->next;
	}

	//申请一个结点并赋值
	ListNode<T> *q = new ListNode<T>(x, pre->next);

	pre->next = q;					//把新结点插入pre所指结点后
	size++;
}