staticlist.h

链表容器：静态链表：链表容量确定

//StaticList.h
#ifndef STATIC_LIST
#define STATIC_LIST

#include <iostream>
#include <memory.h>
using namespace std;

template <class T,int N>
class StaticList
{
public:
	//默认构造函数
	//后置条件:生成一个空表
	StaticList();

	//构造函数：以连续空间中的值建立链表
	StaticList(const T *begin,const T *end,int select=0);
	
	//内部元素排序
	void Rank();

	//在适当位置处插入新元素,使表从小到大有序
	void Insert(const T& value);

	//删除第一个等于指定值的元素
	//后置条件:若没有找到目标值,则什么也不做
	void Del(const T& target);

	//删除指定位置元素
	//前置条件:pos大于0且pos不大于表的长度
	void Erase(int pos);

	//查找等于指定值的元素，返回其位置
	//若表中无此值，返回0
	int Locate(const T &target);

	//查找指定位置的元素，返回其值
	//前置条件：pos不小于1且不大于表长
	T At(int pos);

	//计算表的大小
	int Size() const {return m_size;}

	//清空表
	void Destroy();

	//检验表是否为空
	bool Empty() const{return m_avail==1;}

	//检验表是否为满
	bool Full() const{return m_avail>N;}

	//顺序显示表中所有元素
	void Display()const;
private:
	struct  
	{
		T data;
		int next;
	}m_node[N+1];
	int m_avail;
	int m_size;
};

template <class T,int N>
StaticList<T,N>::StaticList():m_avail(1),m_size(0)
{
	memset(m_node,0,sizeof(m_node));
	m_node[0].next = -1;
}

template <class T,int N>
StaticList<T,N>::StaticList(const T *begin,const T *end,int select)
{
	if (end-begin>N)
		throw overflow_error("StaticList<T,N>::StaticList():overflow_error");

	memset(m_node,0,sizeof(m_node));					//公共初始化
	m_size = end-begin;
	const T *p=begin,*q=end;

	if (select==1)
	{
		//头插法
		m_avail=1;
		m_node[0].next = -1;
		while(p!=end)
		{
			m_node[m_avail].data = *p;					//准备新节点
			m_node[m_avail].next = m_node[0].next;
			
			m_node[0].next = m_avail;					//挂链
			m_avail++;									//重置分配指针
			p++;										//源数据读取指针后移
		}
	}
	else if (select==2)
	{
		//尾插法
		m_avail=1;
		int tail=0;										//尾指针
		//while(m_node[tail].next!=-1)					//寻找尾节点
		//	tail = m_node[tail].next;
		while(p!=end)
		{
			m_node[m_avail].data = *p;					//准备新节点
			
			m_node[tail].next = m_avail;				//挂链
			tail = m_avail;								//重置尾指针
			m_avail++;									//重置分配指针
			p++;										//源数据读取指针后移
		}
		m_node[tail].next = -1;
	}
	else
	{
		//数组赋值法
		int i;
		for (i=0,p=begin; p!=end; i++,p++)				//遍历源数组
		{
			m_node[i+1].data = *p;						//复制
			m_node[i].next = i+1;						//修改指针
		}
		m_node[i].next = -1;							//修改尾指针
		m_avail = i+1;									//更新空间分配指针
	}
}

template <class T,int N>
void StaticList<T,N>::Rank()
{
	if (Size()<2)
		return;
	for (int i=1; i<Size(); i++)						//冒泡排序法
	{
		int pre=0,p=m_node[pre].next,q=m_node[p].next;	//工作指针
		for (int j=0; j<Size()-i; j++)					//遍历未排序的链表部分
		{
			if (m_node[p].data>m_node[q].data)			//判断条件
			{
				m_node[p].next = m_node[q].next;		//交换指针
				m_node[q].next = p;
				m_node[pre].next = q;
			}

			pre = m_node[pre].next;									//工作指针后移
			p = m_node[pre].next;
			q = m_node[p].next;
		}
	}
}

template <class T,int N>
void StaticList<T,N>::Insert(const T &value)
{
	if (Full())
		throw overflow_error("StaticList<T,N>::Insert():overflow_error");

	//查找位置
	int p=0,post=m_node[0].next,i=1;				//初始化工作指针
	while (post!=-1 && m_node[post].data<value)		//寻找目标位置
	{
		p = post;
		post = m_node[p].next;
	}

	//插入节点
	m_node[m_avail].data = value;					//收拾新节点
	m_node[m_avail].next = post;
	m_node[p].next = m_avail;						//挂链
	m_size++;										//表长加一
	while (m_node[m_avail].next!=0)					//重置空间分配指针
		m_avail++;
}

template <class T,int N>
void StaticList<T,N>::Del(const T &target)
{
	if (Empty())
		throw exception("StaticList::Del():data to delete is not in the
 list");

	//查找位置
	int p=0,post=m_node[0].next;					//初始化工作指针
	while (post!=-1 && m_node[post].data!=target)	//寻找目标值或到表尾
	{
		p = post;
		post = m_node[p].next;
	}

	//删除节点
	if (post!=-1)
	{
		m_node[p].next = m_node[post].next;			//摘链
		m_node[post].next = 0;						//释放空间
		m_size--;									//表长减一
		m_avail = m_avail<post?m_avail:post;		//重置空间分配指针
	}
	else
	{
		throw exception("StaticList::Del():data to delete is not in the
 list");
	}
}

template <class T,int N>
void StaticList<T,N>::Erase(int pos)
{
	//抛掷异常
	if (pos<1)
		throw underflow_error("StaticList::Erase():underflow_error");
	else if (pos>Size())
		throw overflow_error("StaticList::Erase():overflow_error");

	//查找位置
	int p=0,post=m_node[0].next,i=1;				//初始化工作指针
	while (i<pos)									//寻找目标位置
	{
		p = post;
		post = m_node[p].next;
		i++;
	}

	//删除节点
	m_node[p].next = m_node[post].next;				//摘链
	m_node[post].next = 0;							//释放空间
	m_size--;										//表长减一
	m_avail = m_avail<post?m_avail:post;			//重置空间分配指针
}
template <class T,int N>
int StaticList<T,N>::Locate(const T &target)
{
	int p=m_node[0].next,pos=1;

	//查找位置
	while(p!=-1 && m_node[p].data!=target)
	{
		p = m_node[p].next;
		pos++;
	}

	//返回位置信息
	if (p!=-1)
		return pos;
	else
		return 0;
}
template <class T,int N>
T StaticList<T,N>::At(int pos)
{
	//抛掷异常
	if (pos<1)
		throw underflow_error("StaticList::At():underflow_error");
	else if (pos>Size())
		throw overflow_error("StaticList::At():overflow_error");

	//查找位置
	int p=m_node[0].next,i=1;						//初始化工作指针
	while (i<pos)									//寻找目标位置
	{
		p = m_node[p].next;
		i++;
	}

	//返回目标值
	return m_node[p].data;
}

template <class T,int N>
void StaticList<T,N>::Destroy()
{
	m_avail = 1;
	m_size = 0;
	memset(m_node,0,sizeof(m_node));
	m_node[0].next = -1;
}

template <class T,int N>
void StaticList<T,N>::Display() const
{
	int p=0,post=m_node[0].next;
	while (post!=-1)								//遍历链表
	{
		cout<<m_node[post].data<<"  ";
		p = post;
		post = m_node[p].next;
	}
	cout<<endl;
}

#endif //STATIC_LIST