数据结构（第二篇：顺序表）

顺序表是最简单的一种线性结构，逻辑上相邻的数据在计算机内的存储位置也是相邻的，数组就是顺序表。可以快速定位第几个元素，中间不允许有空，所以插入、删除时需要移动大量元素。

顺序表有两个长度，一个是记录分配的连续内存长度，而另一个记录已使用的长度。如下所示：
在这里插入图片描述
下面整理一下顺序表的运算结构。
顺序表的存储空间记为Maxsize，用elem记录基地址，用length记录实际的元素个数，即顺序表的长度：

#define MaxSize 10

struct SqList
{
ElemType* elem;	//元素类型指针
int length;		//顺序表的长度
}

1、顺序表的创建

创建就是给顺序表分配一个预定义大小的连续内存，用基地址elem记录这段空间的首地址。

bool CreateList(SqList& list)
{
	list.elem = new int[MaxSize];	//为顺序表分配Maxsize个空间
	if ( list.elem == nullptr )		//存储分配失败
	{
		return false;
	}

	list.length = 0;				//空表已使用0个
	return true;
};

2、顺序表销毁

释放创建时申请的内存。

void DestroyList(SqList &L)
{
	if (L.elem) 
		delete[] L.elem;    //释放存储空间
}

3、顺序表取值

顺序表是可随机存取的，任何一个元素都可立即找到。我们取第i个元素，只要i合理，那么就可立即找到元素。

bool GetElem(SqList& list, int i, int& e)
{
	//判断i是否合理
	if ( i < 1 || i > list.length )
	{
		return false;
	}

	e = list.elem[i - 1];
	return true;
};

4、顺序表查找

在顺序表中查找一个元素e，查到返回元素位置，若无返回-1。

int FindElem(SqList& list, int e)
{
	for (int i = 0; i<list.length; i++ )
	{
		if ( list.elem[i] == e )
		{
			return i + 1;
		}
	}
	return -1;
};

最好情况：如果元素正好在第一个位置，一次比较成功；时间复杂度为O(1)
最坏情况：如果元素正好在最后一个位置；时间复杂度为O(n)

5、顺序表插入元素

在顺序表中第i个位置之前插入一个元素e，需要从最后一个元素开始后移，直到把第i个元素也后移一位，然后把e放入第i个位置。时间复杂度为O(n)

bool ListInsert(SqList& list, int i, int e)
{
	if ( i < 1 || i > list.length + 1)
	{
		return false;
	}

	if ( list.length == MaxSize )
	{
		return false;
	}

	for (int j = list.length - 1; j >= i-1; j-- )
	{
		list.elem[j + 1] = list.elem[j];
	}

	list.elem[i - 1] = e;
	list.length++;
	return true;
}

6、顺序表删除元素

在顺序表中删除第i个元素，需要把该元素暂存到变量e，然后从i+1个元素开始前移。时间复杂度为O(n)。

bool ListDelete(SqList& list, int i, int& e)
{
	if ( i < 1 || i > list.length )
	{
		return false;
	}

	e = list.elem[i - 1];

	for (int j = i; j < list.length-1; j++ )
	{
		list.elem[j - 1] = list.elem[j];
	}

	list.length--;

	return true;
}

整体的测试用例：

void print(SqList L)
{
	cout << "输出顺序表" << endl;
	for (int j = 0; j <= L.length - 1; j++)
		cout << L.elem[j] << "  ";
	cout << endl;
}

int main(int argc, char** argv)
{
	SqList myL;
	int i, e, x;

	cout << "1. 初始化\n";
	cout << "2. 取值\n";
	cout << "3. 查找\n";
	cout << "4. 插入\n";
	cout << "5. 删除\n";
	cout << "6. 输出\n";
	cout << "7. 销毁\n";
	cout << "0. 退出\n";

	int choose = -1;
	while (choose != 0)
	{
		cout << "请选择:";
		cin >> choose;
		switch (choose)
		{
		case 1://初始化顺序表
			cout << "顺序表初始化..." << endl;
			if (CreateList(myL))
				cout << "顺序表初始化成功！" << endl;
			else
				cout << "顺序表初始化失败！" << endl;
			break;
		case 2://取值
			cout << "输入整型数i，取第i个元素输出" << endl;
			cin >> i;
			if (GetElem(myL, i, e))
				cout << "第i个元素是： " << e << endl;
			else
				cout << "顺序表取值失败！" << endl;;
			cout << "第i个元素是： " << e << endl;
			break;
		case 3://查找
			cout << "请输入要查找的数x:";
			cin >> x;				
			if (FindElem(myL, x) == -1)
				cout << "查找失败！" << endl;
			else
				cout << "查找成功！" << endl;
			break;
		case 4://插入
			cout << "请输入要插入的位置和要插入的数据元素e:";
			cin >> i >> e;
			if (ListInsert(myL, i, e))
				cout << "插入成功！" << endl;
			else
				cout << "插入失败！" << endl;
			break;
		case 5://删除
			cout << "请输入要删除的位置i:";
			cin >> i;
			if (ListDelete(myL, i, e))
				cout << " 删除成功！" << endl;
			else
				cout << "删除失败！" << endl;
			break;
		case 6://输出
			print(myL);
			break;
		case 7://销毁
			cout << "顺序表销毁..." << endl;
			DestroyList(myL);
			break;
		}
	}

	getchar();
	return 0;
}

顺序表，在C++中可以看成数组、array。vector是高级一点的顺序表，它的大小可以动态变化。

感谢大家，我是假装很努力的YoungYangD（小羊）。

参考资料：
https://blog.csdn.net/rainchxy/article/details/77946835