顺序表的简单实现
写在前面
数据结构是一个数据对象，同时这个对象的实例以及构成实例的元素都存在着联系，而且这些联系是由相关函数来规定的。
研究数据结构，关心的是数据对象（实际上是实例）的描述以及相关函数的具体实现。数据对象描述得好，函数的实现就会高效。
最常用的数据对象以及操作都已经在C++中作为基本数据类型而实现，如整数对象，布尔对象等。其他数据对象均可以用基本数据类型以及由C++的类、数组和指针所提供的组合功能来实现。
1.线性表的数据结构
线性表（linear list)也称有序表，它的每一个实例都是元素的一个有序集合。
对线性表实施的操作有：
- 创建一个线性表
- 撤销一个线性表
- 确定线性表是否为空
- 确定线性表的长度
- 按给定的索引查找一个元素
- 按一个给定的元素查找其索引
- 按一个给定的索引删除一个元素
- 按一个给定的索引插入一个元素
- 从左至右顺序输出线性表元素
用顺序存储结构存储的表称为顺序表（sequent list）。顺序表中任意数据元素的存取和访问都可以通过它的位置指针来（即数组下标）进行访问。对顺序表中元素访问的效率是一个比较重要的问题。通常情况下，有序顺序表的访问效率大大高于无序顺序表的访问效率。
2.顺序表的类定义
typedef int Seqlist_Entry;
const int maxsize = 10;
class Seqlist
{
public:
Seqlist();//构造函数
~Seqlist();//析构函数
int listsize()const;//返回元素的个数
bool listempty() const;//判断表是否为空
int find(const Seqlist_Entry &item);//返回元素item在表中的位置
Seqlist_Entry getdata(int pos) const;//返回位置pos的元素
void insert(const Seqlist_Entry &item, int pos);//在位置pos处插入元素item
Seqlist_Entry Delete(const int pos);//删除位置pos的元素并返回
void clearlist();//清空表
void showall() const;//输出表
private:
Seqlist_Entry data[maxsize];
int size;//数据元素的个数
};
3.顺序表的类实现
//构造函数
Seqlist::Seqlist()
{
size = 0;
}
//析构函数
Seqlist::~Seqlist() {}
//返回顺序表元素的个数
int Seqlist::listsize() const
{
return size;
}
//判断顺序表是否为空
bool Seqlist::listempty() const
{
return (size == 0);
}
//查找item，并返回位置索引
int Seqlist::find(const Seqlist_Entry & item)
{
if (size == 0)
{
cout << "list is empty " << endl;
}
int i = 0;
while (i < size&&item != data[i])
{
i++;
}
if (i < size)
return i;
else
cout << "illegal operator" << endl;
}
//取出pos位置上的元素
Seqlist_Entry Seqlist::getdata(int pos) const
{
if (pos<0 || pos>size - 1)
{
cout << "illegal operator" << endl;
exit(1);
}
return data[pos];
}
//在pos位置插入元素item
void Seqlist::insert(const Seqlist_Entry & item, int pos)
{
if (size == maxsize)
{
cout << "list is full" << endl;
return;
}
if (pos<0 || pos>size )
{
cout << "illegal operator" << endl;
return;
}
for (int i = size; i > pos; i--)
{
data[i] = data[i - 1];
}
data[pos] = item;
size++;
}
//删除pos位置的元素
Seqlist_Entry Seqlist::Delete(const int pos)
{
Seqlist_Entry tmp=data[pos];
if (size == 0)
{
cout << "list is empty" << endl;
exit(1);
}
if (pos<0 || pos>size - 1)
{
cout << "illegal operator" << endl;
exit(1);
}
for (int i = pos; i < size-1; i++)
{
data[i] = data[i + 1];
}
size--;
return tmp;
}
//置顺序表为空
void Seqlist::clearlist()
{
size = 0;
cout << "已清空" << endl;
}
//输出顺序表中所有元素
void Seqlist::showall() const
{
if (size == 0)
{
cout << "list is empty" << endl;
}
for (int i = 0; i < size; i++)
{
cout <<i<<"号元素:"<< data[i] << endl;
}
}
4.测试主函数
void test()
{
Seqlist list;
for (int i = 0; i < 10; i++)
{
list.insert(i * 12, i);
}
for (int i = 0; i < 10; i++)
{
cout << list.getdata(i) << endl;
}
int tmp = list.Delete(2);
cout << "元素" << tmp << "已经被删除了" << endl;
list.showall();
cout<<"84在顺序表的"<<list.find(84)<<"号位置"<<endl;
list.clearlist();
list.showall();
}
int main()
{
test();
}
输出结果如下图：
