转载请注明出处，谢谢~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++实现了线性了线性表的顺序存储，当然了，现在还只能存储整形元素，晚上加上泛型编程，让她更完整的跑起来~~嘎嘎，当然了，限于个人水平，有问题的话请留言~~饿死了，先吃饭去了。