前言：

顺序表的本质其实就是使用一个数组对数据进行存储，我们在此博客中，基于C++的类与对象来实现顺序表。

一、构成：

顺序表由三个部分组成，一个数组，一个用来表示数组容量的整型和一个表示已存放数据数量的整型。

所以我们的成员变量就如下：

typedef int ElemType;
class SqList
{
private:
	ElemType* data;
	int size;
	int capacity;
};

我们需要实现的功能有：插入，删除，打印，查找，更改。同时，我们对类的内部操作还有初始化，扩容，销毁等操作。

二、包含

在使用C++实现顺序表的时候，我们只需要包含一个头文件<iostream>,但是们可以提前展开命名空间std。

#include<iostream>
using namespace std;

三、函数实现

1）初始化

初始化在此可以作为类的构造函数，其参数可以使用一个缺省参数。

SqList(int n = 4)
{
	data = (ElemType*)malloc(sizeof(ElemType) * n);
	size = 0;
	capacity = n;
}

函数说明：构造函数SqList在对象实例化的时候自动调用，在实例化的时候，缺省参数n可以传值，也可以用默认值，为data开辟一块空间，并且将size初始化为0，容量capacity初始化为n。

2）销毁

销毁在此处可以作为类的析构函数，类生命周期结束时自动调用。

~SqList()
{
	free(data);
	data = nullptr;
	capacity = 0;
	size = 0;
}

函数说明：将data的空间释放，data指向空，容量和大小都设为0.

3）扩容

该函数不被类外调用，所以可将其放在private修饰，其作用时当顺序表满了时，将顺序表扩容一倍。

	void boarden()
	{
		ElemType* tmp = (ElemType*)realloc(data, sizeof(ElemType) * capacity * 2);
		if (tmp)
		{
			data = tmp;
			capacity = capacity * 2;
		}
		else
			perror("boarden error!");
	}

函数说明：要先用tmp储存并且验证是否扩容成功，以免造成扩容失败同时原内存丢失。

4）插入

在数组的第pos个位置插入数据

思路：将pos位置及以后的数据往后推移一个位置，再将数据填到对应位置。但是推移的时候，必须从后面往前面推移，而不是从前往后推，否则会将原来的数据覆盖。

void insert(int pos, int val)
{
	if (size == capacity)
		boarden();

	for (int i = size - 1; i >= pos - 1; i--)
	{
		data[i + 1] = data[i];
	}

	data[pos - 1] = val;
	size++;
}

5）删除

删除pos位置的数据

思路：将pos位置之后的数据往前面运动即可，从pos+1位置到第size个位置。注意此时必须从前往后移动，否则原来数据会被覆盖。

 

void del(int pos)
{
	if (size)
	{
		for (int i = pos - 1; i < size; i++)
		{
			data[i] = data[i + 1];
		}
		size -= 1;
	}
	else
		perror("Delete Fail,Empty List");
}

6）查找

查找并返回第一个大小为val的位置

思路：遍历并比对其值

int find(ElemType val)
{
	for (int i = 0; i < size; i++)
	{
		if (data[i] == val)
			return i + 1;
	}
}

7）打印

将顺序表按序打印出来

思路：遍历并打印其值

void print()
{
	for (int i = 0; i < size; i++)
		cout << data[i] << " ";
	cout << endl;
}

四、源码分享

#include<iostream>
using namespace std;

typedef int ElemType;
class SqList
{
private:
	ElemType* data;
	int size;
	int capacity;

	void boarden()
	{
		ElemType* tmp = (ElemType*)realloc(data, sizeof(ElemType) * capacity * 2);
		if (tmp)
		{
			data = tmp;
			capacity = capacity * 2;
		}
		else
			perror("boarden error!");
	}

public:
	SqList(int n = 4)
	{
		data = (ElemType*)malloc(sizeof(ElemType) * n);
		size = 0;
		capacity = n;
	}

	~SqList()
	{
		free(data);
		data = nullptr;
		capacity = 0;
		size = 0;
	}

	void insert(int pos, int val)
	{
		if (size == capacity)
			boarden();

		for (int i = size - 1; i >= pos - 1; i--)
		{
			data[i + 1] = data[i];
		}

		data[pos - 1] = val;
		size++;
	}

	void del(int pos)
	{
		if (size)
		{
			for (int i = pos - 1; i < size; i++)
			{
				data[i] = data[i + 1];
			}
			size -= 1;
		}
		else
			perror("Delete Fail,Empty List");
	}

	void print()
	{
		for (int i = 0; i < size; i++)
			cout << data[i] << " ";
		cout << endl;
	}

	int find(ElemType val)
	{
		for (int i = 0; i < size; i++)
		{
			if (data[i] == val)
				return i + 1;
		}
	}
};