数据结构——线性表（顺序表）_顺序表的结构体定义图

顺序表的定义

顺序表就是把线性表中的所有元素按照其逻辑顺序，依次存储到从指定的存储位置开始的一块连续的存储空间中。这样线性表中第一个元素的存储位置就是指定的存储位置，第i+1个元素的存储位置紧接在第i个元素的存储位置的后面。

顺序表就像如下图中的房子，每个房间左边的数字就是该房间离0点的距离，同时也代表了房间号，房间的长度为1，因此，只要知道0点的位置，然后通过房间号就马上可以找到任何一个房间的位置，这就是顺序表的第一个特性——随机访问特性.

由图中我们可以看出5个房间所用的地皮是紧挨着的，即连续地占用了一片空间，并且地皮的块数6是确定的，若在地皮上布置新的房间或者拆掉老的房间，（对顺序表的操作过程中），地皮的块数不会增加，也不会减少，这就是顺序表的第二个特性，即顺序表要求占用连续的存储空间。存储分配只能预先进行，一旦分配好了，在对其操作的过程中，始终不变。

如图所示的顺序表中最右边的一个表结点空间代表没有被利用（顺序表还有剩余空间来注入新数据），如果想要在1号房间和2号房间插入一个房间，则必须将2号以后的房间都往后移动一个位置，（假设房间是可以随意搬动的），即顺序表做插入操作的时候要移动多个元素

顺序表的结构体定义

#define maxsize 100
typedef struct
{
	int data[maxsize];//存放顺序表元素的数组，（默认是int型，可根据题目要求将int换成其他类型）
	int length;//存放顺序表的长度
}Sqlist；
1
2
3
4
5
6

结构体示意图：

如上图所示，一个顺序表包括一个存储表中元素的数组data[ ]和一个指示元素个数的变量length。

有时候我们可以把上面的结构体定义写成如下

int  A[maxsize]；
int  n;
1
2

这两句就定义了一个长度为n，表内元素为整数的顺序表。

顺序表的操作

1、按元素值得查找算法

在顺序表中查找第一个值等于e的元素，并返回其下标。代码如下

int findElem (sqlist L ,int e)
{
	int i;
	for(i=0; i<L.length, ++i)
	if(e == L.data[i])
	return 1;//若找到则返回下标
	
	return -1;//若没找到，返回-1，作为失败标记
}
1
2
3
4
5
6
7
8
9

2、插入数据元素的算法

在顺序表L的第p（0<=p<=length)个位置上插入新的元素e。如果p的输入不正确，则返回0，代表插入失败；如果p的输入正确，则将顺序表第p个元素及以后元素右移一个位置，腾出一个空位置，插入新元素，顺序表长度增加1，插入操作成功，返回1.
插入操作代码如下：

int insertElem(sqlist &L， int p， int e）//L本身要发生改变，所以用引用型
{
	int i;
	if(p<0 || p>L.length ||L.length ==maxsize)//位置错误或者表长已经达到
	return 0;//顺序表的最大允许值，此时插入不成功，返回0
	for(i=L.length-1, i>=p; --i)
	L.data[i+1] = L.data[i];//从后往前，逐个将元素往后移动一个位置，
	L.data[p]=e;//将e放在插入位置p上
	++(L.length);//表内元素多了一个，因此表长自增1
	return 1;//插入成功，返回1
	
1
2
3
4
5
6
7
8
9
10
11

3、删除数据元素的算法
删除顺序表L中下标为p （0<=p<=length-1)的元素，成功返回-1，否则返回0，并将被删除元素的值赋给e
代码如下

int deletElem( sqlist &L, int p, int &e)//需要改变的变量用引用型
{
	int i;
	if( p<0 || p>length-1)
	return 0;//位置不对返回0，代表删除不成功/
	e=L.data[p];//将被删除元素赋值给e
	for( i=p; i<L.length-1; ++i)//从p位置开始，将其后边的元素逐个前移一个位置
	L.data[i]=L.data[i+1];
	--(L.length);//表长减1
	return 1;//删除成功，返回1
1
2
3
4
5
6
7
8
9
10

顺序表中还剩下两个比较简单的算法在这里稍做介绍

（1）初始化顺序表的算法
只需将length设置为0，代码如下：

void initList（sqlist &L）//L本身要发生变化，所以要用引用型
{
		L.length=0；
}
1
2
3
4

（2）求指定位置元素的算法
用e返回L中p（0<=p<=length-1)位置上的元素，代码如下：

int getElem(sqlist &L int p， int &e)//要改变，所以要用引用型
{
	if（p<0 ||p>L.length-1)//p值越界，返回0
	return 0;
	e=L.data[p];
	return 1;
}
1
2
3
4
5
6
7