顺序表

Data Structures Experiment #1 - 搭建实验环境,并实现顺序表的基本操作

实现一个SeqList类。

  • SeqList(const int& listSize);
    构造函数,构建一个SeqList,其中listSize为顺序表最多存放元素的个数。
  • bool isIn(const int& data);
    判断data是否在顺序表中。如果data在顺序表中,返回true,否则返回false
  • int length();
    返回顺序中加入元素的个数。
  • int getData(const int& location);
    返回位置为location的元素。
  • bool insert(const int& data, const int& location);
    data插入location中,其中如果顺序表已经满了,则返回false。其中location的计数从0开始,并且测试时会保证location 小于等于元素的个数。
  • bool remove(const int& location);
    删除位置为location的元素,如果location不合法,则返回false。删除成功则返回true
  • ~SeqList();
    析构函数。

0x01 构造函数

直接分配LIST_SIZE大小的空间。

1
2
3
4
5
6
SeqList::SeqList(const int& listSize) :LIST_SIZE(listSize)
{
seq = new int[LIST_SIZE];
// equal to: seq = (int*) malloc(sizeof(int) * LIST_SIZE);
len = 0;
}

0x02 isIn

默认为元素不在表中,顺序遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool SeqList::isIn(const int& data){
bool defaultOut = false;
for (int i = 0; i < len; i++)
{
if (data == seq[i])
{
defaultOut = true;
break;
}
}
if (defaultOut)
return true;
else
return false;
}

0x03 length

直接返回长度。

1
2
3
int SeqList::length(){
return len;
}

0x04 getData

返回对应位置的数值。

1
2
3
int SeqList::getData(const int& location){
return seq[location];
}

0x05 insert

将该位置后元素整体后移,插入即可。

1
2
3
4
5
6
7
8
9
10
11
12
bool SeqList::insert(const int& data, const int& location){
if (len == LIST_SIZE)
return false;
else
{
for (int i = len - 1; i >= location; i--)
seq[i + 1] = seq[i];
seq[location] = data;
len++;
return true;
}
}

0x06 remove

首先判断位置的合法性。

将该位置后元素整体前移,删除即可。

1
2
3
4
5
6
7
8
9
10
11
bool SeqList::remove(const int& location){
if (location >= len || location < 0 || len == 0)
return false;
else
{
for (int i = location; i < len - 1; i++)
seq[i] = seq[i + 1];
len--;
return true;
}
}

0x07 析构函数

释放内存。

1
2
3
SeqList::~SeqList(){
delete[] seq;
}