用C++ DIY自己的线性存储的线性表

转载请注明出处，谢谢~http://blog.csdn.net/hongkangwl/article/details/21802073

线性表可以说是最简单的数据结构，它的描述为：n个数据元素的有限序列。

记为：L=(a1,a2,...,an)

按照存储结构它又可以分为顺序存储结构和链式存储结构。

而其中线性表的顺序存储结构是最简单最常用的数据结构：用一段连续地址依次存储表中的数据元素。

看到这里，我们会自然的联想到C语言中的数组。

下面我要实现的是线性表中的元素为整型的顺序存储结构，及它的主要运算：增删查。

线性存储有个很大的问题，就是在头部插入元素需要把所有的元素往后移动，非常的消耗资源。

这个问题可以通过链式存储解决。

首先，建立线性表的类

class seqlistclass
{
private:
	static int num;  //线性表元素的个数
	static int capacity;//线性表的容量
	int *ptr_member;//指向线性表中用来存储数据的数组的指针
public:
	seqlistclass() //默认构造函数
	{
		ptr_member = NULL;
		num = 0;
		capacity = 0;
	}
	seqlistclass(int n)//带参数的构造函数
	{
		ptr_member = new int[n];
		num = 0;
		capacity = n;
	}
	~seqlistclass()//析构函数，不知道delect为什么不成功，擦
	{
		//delect []  ptr_member;
	}
	void seqlist_setnum(seqlistclass* ptrclass, int pos,int member);//对某个位置上的节点赋值
	int seqlist_getnum(seqlistclass* ptrclass);//得到线性表的元素个数
	int seqlist_getcapacity(seqlistclass* ptrclass);//得到线性表的容量
	int seqlist_getpos(seqlistclass* ptrclass, int pos);	//得到某个位置上的元素
	int seqlist_erasepos(seqlistclass* ptrclass, int pos);//删除某个位置上的元素
	int seqlist_insertmember(seqlistclass* ptrclass, int pos,int member);//在某个位置上插入元素
	void seqlist_display(seqlistclass* ptrclass);//输出线性表中的所有元素
//	void seqlist_setcapacity(seqlistclass* ptr,int capacity);
};

上面的几种成员函数式我们对基本线性表的操作，当然，我们还可以对其进行封装成STL中的push_back 、push_front，如下：

void seqlistclass::pop_back(seqlistclass* ptrclass)
{
	ptrclass->seqlist_erasepos(ptrclass,ptrclass->seqlist_getnum(ptrclass)-1);
}
void seqlistclass::pop_front(seqlistclass* ptrclass)
{
	ptrclass->seqlist_erasepos(ptrclass,0);
}
void seqlistclass::push_front(seqlistclass *ptrclass,int num)
{
	ptrclass->seqlist_insertmember(ptrclass,0,num);
}
void seqlistclass::push_back(seqlistclass *ptrclass,int num)
{
	ptrclass->seqlist_insertmember(ptrclass,ptrclass->seqlist_getnum(ptrclass),num);
}

实际上，他们只是披着别的操作的马甲而已，他们更像是适配器，而不是算法。

几种基本操作里面，最难的就是插入和删除了，代码分别如下：

//插入元素，需要判断几种情况
int seqlistclass::seqlist_insertmember(seqlistclass* ptrclass, int pos,int member)
{
	if(pos > ptrclass->capacity - 1)
	{
		cout<<"位置超出容量，放在顺序表的末尾"<<endl;
		pos = ptrclass->seqlist_getcapacity(ptrclass) - 1;
		seqlist_insertmember(ptrclass,pos,member);
		return 0;
	}
	else
		if(ptrclass->num == ptrclass->capacity)
		{
			cout<<"线性表已满，返回"<<endl;
			return -1;
		}
		else
		{  
			if(pos >= ptrclass->seqlist_getnum(ptrclass))
			{
				pos = ptrclass->num;
				ptrclass->ptr_member[pos] = member;
				ptrclass->num++;
				return 0;
			}
			else
			{
				for(int i = ptrclass->seqlist_getnum(ptrclass); i >pos; i--)
				{
					ptrclass->seqlist_setnum(ptrclass,i,ptrclass->seqlist_getpos(ptrclass,i-1));
				}
				ptrclass->ptr_member[pos] = member;
				ptrclass->num++;
			}
		}

}

删除的代码如下：

//删除后需要把后面的元素往前移动
int seqlistclass::seqlist_erasepos(seqlistclass* ptrclass, int pos)
{
	if(pos > ptrclass->capacity)
	{
		cout<<"越界"<<endl;
		return -1;
	}
	else
	{
		if(pos > ptrclass->seqlist_getnum(ptrclass))
		{
			cout<<"此位置没有放置"<<endl;
			return -1;
		}
		else
		{
			for(int i = pos; i < ptrclass->seqlist_getnum(ptrclass)-1; i++ )
			{
				ptrclass->seqlist_setnum(ptrclass,i,ptrclass->seqlist_getpos(ptrclass,i+1));
			}
			ptrclass->num = ptrclass->num - 1 ;
			return 0;
		}
	}
}

全部的实现代码及其测试代码如下：

#include <iostream>
using namespace std;
class seqlistclass
{
private:
	static int num;  //线性表元素的个数
	static int capacity;//线性表的容量
	int *ptr_member;//指向线性表中用来存储数据的数组的指针
public:
	seqlistclass() //默认构造函数
	{
		ptr_member = NULL;
		num = 0;
		capacity = 0;
	}
	seqlistclass(int n)//带参数的构造函数
	{
		ptr_member = new int[n];
		num = 0;
		capacity = n;
	}
	~seqlistclass()//析构函数，不知道delect为什么不成功，擦
	{
		//delect []  ptr_member;
	}
	void seqlist_setnum(seqlistclass* ptrclass, int pos,int member);//对某个位置上的节点赋值
	int seqlist_getnum(seqlistclass* ptrclass);//得到线性表的元素个数
	int seqlist_getcapacity(seqlistclass* ptrclass);//得到线性表的容量
	int seqlist_getpos(seqlistclass* ptrclass, int pos);	//得到某个位置上的元素
	int seqlist_erasepos(seqlistclass* ptrclass, int pos);//删除某个位置上的元素
	int seqlist_insertmember(seqlistclass* ptrclass, int pos,int member);//在某个位置上插入元素
	void seqlist_display(seqlistclass* ptrclass);//输出线性表中的所有元素
	void push_back(seqlistclass* ptrclass,int num);
	void push_front(seqlistclass* ptrclass,int num);
	void pop_back(seqlistclass* ptrclass);
	void pop_front(seqlistclass* ptrclass);
//	void seqlist_setcapacity(seqlistclass* ptr,int capacity);
};
int seqlistclass::capacity = 0;
int seqlistclass::num = 0;
void seqlistclass::pop_back(seqlistclass* ptrclass)
{
	ptrclass->seqlist_erasepos(ptrclass,ptrclass->seqlist_getnum(ptrclass)-1);
}
void seqlistclass::pop_front(seqlistclass* ptrclass)
{
	ptrclass->seqlist_erasepos(ptrclass,0);
}
void seqlistclass::push_front(seqlistclass *ptrclass,int num)
{
	ptrclass->seqlist_insertmember(ptrclass,0,num);
}
void seqlistclass::push_back(seqlistclass *ptrclass,int num)
{
	ptrclass->seqlist_insertmember(ptrclass,ptrclass->seqlist_getnum(ptrclass),num);
}
//void seqlistclass::seqlist_setcapacity(seqlistclass* ptrclass , int capacity)
//{
//	ptrclass->capacity = capacity;
//}
void seqlistclass::seqlist_display(seqlistclass *ptrclass)
{
	for(int i = 0; i < ptrclass->seqlist_getnum(ptrclass); i++)
	{
		cout<<ptrclass->seqlist_getpos(ptrclass,i)<<" ";
	}
	cout<<endl;
}
int seqlistclass::seqlist_getpos(seqlistclass* ptrclass, int pos)
{
	return ptrclass->ptr_member[pos];
}

void seqlistclass::seqlist_setnum(seqlistclass* ptrclass,int pos, int member)
{
	ptrclass->ptr_member[pos] = member;
}
//删除后需要把后面的元素往前移动
int seqlistclass::seqlist_erasepos(seqlistclass* ptrclass, int pos)
{
	if(pos > ptrclass->capacity)
	{
		cout<<"越界"<<endl;
		return -1;
	}
	else
	{
		if(pos > ptrclass->seqlist_getnum(ptrclass))
		{
			cout<<"此位置没有放置"<<endl;
			return -1;
		}
		else
		{
			for(int i = pos; i < ptrclass->seqlist_getnum(ptrclass)-1; i++ )
			{
				ptrclass->seqlist_setnum(ptrclass,i,ptrclass->seqlist_getpos(ptrclass,i+1));
			}
			ptrclass->num = ptrclass->num - 1 ;
			return 0;
		}
	}
}
//插入元素，需要判断几种情况
int seqlistclass::seqlist_insertmember(seqlistclass* ptrclass, int pos,int member)
{
	if(pos > ptrclass->capacity - 1)
	{
		cout<<"位置超出容量，放在顺序表的末尾"<<endl;
		pos = ptrclass->seqlist_getcapacity(ptrclass) - 1;
		seqlist_insertmember(ptrclass,pos,member);
		return 0;
	}
	else
		if(ptrclass->num == ptrclass->capacity)
		{
			cout<<"线性表已满，返回"<<endl;
			return -1;
		}
		else
		{  
			if(pos >= ptrclass->seqlist_getnum(ptrclass))
			{
				pos = ptrclass->num;
				ptrclass->ptr_member[pos] = member;
				ptrclass->num++;
				return 0;
			}
			else
			{
				for(int i = ptrclass->seqlist_getnum(ptrclass); i >pos; i--)
				{
					ptrclass->seqlist_setnum(ptrclass,i,ptrclass->seqlist_getpos(ptrclass,i-1));
				}
				ptrclass->ptr_member[pos] = member;
				ptrclass->num++;
			}
		}

}


int seqlistclass::seqlist_getcapacity(seqlistclass* ptrclass)
{
	return ptrclass->capacity;
}
int seqlistclass::seqlist_getnum(seqlistclass* ptrclass)
{
	return ptrclass->num;
}

int main()
{
	cout<<"请输入线性表的容量"<<endl;
	int m ;
	cin>>m;
	seqlistclass *seq =new seqlistclass(m);
	
	
//	seq->seqlist_setcapacity(seq,m);
	int *seqlist = new int[m];
	int n;
	cout<<"请输入你想要插入线性表的元素的个数"<<endl;
	cin>>n;
	cout<<"请输入线性表的元素"<<endl;
	for(int i = 0; i < n ; i++)
	{
		cin>>seqlist[i];
	}
	for(int i =0 ; i < n ; i++)
	{
		seq->seqlist_insertmember(seq,i,seqlist[i]);
	}  
	seq->seqlist_display(seq);	
	seq->seqlist_insertmember(seq,1,8);
	seq->seqlist_display(seq);
	seq->seqlist_erasepos(seq,3);
	seq->seqlist_display(seq);
	seq->push_front(seq,44);
	seq->seqlist_display(seq);
	seq->push_back(seq,22);
	seq->seqlist_display(seq);
	seq->pop_back(seq);
	seq->seqlist_display(seq);
	seq->pop_front(seq);
	seq->seqlist_display(seq);
	seq->~seqlistclass();
	return 0;
}

输出结果如下：

比较完整的实现了用C++实现了线性了线性表的顺序存储，当然了，现在还只能存储整形元素，晚上加上泛型编程，让她更完整的跑起来~~嘎嘎，当然了，限于个人水平，有问题的话请留言~~饿死了，先吃饭去了。