顺序存储定义
今天来总结一下线性表的顺序存储结构。首先来看下顺序存储结构的定义。
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
举个简单的例子，蔺老师在给九班学生安排座位之前，会让学生们从矮到高按照身高的高矮升序排列，假如蔺老师的班上只有十个学生，而全班共有50个座位，那蔺老师会把这10个学生，连续的安排在教室的前两排之内，每个人都有自己的同桌，连续的10个座位，那么这10个学生所占用的就是一片连续的座位。相当于内存中有50个数据元素的空间，而10个学生只占用了中间的连续十个大小的空间。
因为线性表中，存储的数据元素的类型都相同，而存储空间又是连续的，那么我们可以用一维数组来实现线性表的存储结构。
因为班上一共有50个座位，所以蔺老师在安排座位时，也没必要一定从第一个座位开始安排，可以从第二排或者第三排来安排座位，选定座位之后，学生一个挨一个的坐进去就可以了。所以选定线性表时，在内存中找一块地，于是这块地的第一个位置就非常关键，它为存储空间的起始位置。
每天放学回家，蔺老师会要求这10个学生排队走出校门，而并不是每个学生每天都会上学，比如彤彤这样的学生，每天放学要去等蔺老师下班，那么队伍里可能只有九个人，而这九个人还是排成了一列，谁在前谁在后关系依旧很明确，只是少了彤彤而已。而这个例子，就表示了线性表一一对应的特点，就像排队，在整队的时候随着每天的放学排队，大家很清楚自己该出现在哪个位置。
顺序存储结构的代码
我们来看线性表顺序存储结构的结构代码：
#define MAXSIZE 10 //存储空间的初始化分配
typedef int ElementType; //定义线性表元素数据类型 这里假设为int
typedef struct
{
ElementType data[MAXSIZE]; //线性表存储数据元素
int length; //线性表的长度
}SqList;
这里我们能看到顺序存储结构所需要的三个属性：
-
存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置
-
线性表的最大容量，数组长度MAXSIZE
-
线性表的当前长度： length
我们对每个线性表位置的存入或取出的数据，对于计算机来说都是相等的时间，也就是一个常数。因此用上一次讨论的算法时间复杂度的概念来说，线性表的时间复杂度为O(1)。我们通常把具有这一特点的存储结构称为随机存储结构。
顺序存储结构的插入或删除
在讨论顺序存储结构的实现方式之前，我们先来定义一下函数运行的状态代码，用来返回线性表运行的状态。
/**
* 函数运行的状态代码
*
*
*/
#define SUCCESS 1
#define ERROR 0
typedef int Status; //状态代码的类型
这段代码我们定义了Status为状态代码的类型，返回SUCCESS代表1，返回ERROR代表0。本文之后的所有状态代码就不再详述了。
创建线性表（初始化）
在上面我们已经定义好了线性表的属性，并确定了线性表的最大存储容量，那么我们在刚开始时，对线性表进行初始化，创建一个线性表。
/**
线性表的初始化 并分配存储单元
- returns: SqList*
*/
SqList * initSqList()
{
SqList * list = (SqList *)malloc(sizeof(SqList));
list->length = 0 ;
return list;
}
在这里我们还是用C语言来操作，创建了一张线性表，用malloc分配存储空间，定义当前线性表长度为0，最后返回值为本张线性表。
获得元素操作
//获取线性表中的元素
Status GetElem (SqList * L , int i , ElementType e)
{
if (L->length == 0 || i < 1 || i > L->length ) {
return ERROR;
}
e = L->data[i-1];
return SUCCESS;
}
在获取元素的操作中呢，我们定义了一个e，用来返回L中第i个元素的值。
插入操作
在这里先不放代码，先来讨论一下线性表的插入概念。比如我在火车站排队等着取票，排了很久的队终于快轮到我了，这时候有一个很漂亮的姑娘过来，可怜兮兮的对我说：帅哥，我的车还有几分钟 就开了，能让我先取一下么。可能我会“以貌取人”，答应了这个漂亮姑娘的要求，于是这个姑娘排到了我的前面，可是我毕竟有女朋友，再加上男女授受不亲，我又不想回家跪键盘，于是我得往后退一步，让出一个空间给姑娘排在我前面，我后面的人也得跟着我的步伐往后退一步。这时候，就类似于线性表的插入算法的思路：
-
如果插入的位置不合理，抛出异常
-
如果线性表的长度大于数组长度，抛出异常或者动态增加存储空间
-
从最后一个元素，向前遍历到第i个位置，分别将它们都向后移动一个位置。
-
将要插入的元素插入到位置i
-
表长+1
代码的话，我用了两种方式，一种是线性表以栈的方式加入数据元素，即为每一次都加在队列的最后面，一种是按照要求，添加到指定的位置中。
栈的方式插入数据元素的实现代码：
//线性表以栈的方式加入数据
Status pushElement(ElementType e, SqList * list)
{
int length = list->length;
if (length < 0 || length > MAXSIZE) {
return ERROR;
}
list->data[length] = e;
list->length++;
return SUCCESS;
}
在指定位置插入数据元素的代码实现如下：
/**
* 在线性表中的第i个位置插入之前新的元素数据e，线性表的长度+1
*
*/
Status insertElementWithLocation(ElementType e, SqList * list, int i)
{
int k;
//判断线性表的存储空间是否已满
if (list->length == MAXSIZE) {
return ERROR;
}
//判断i的合理性
if (i < 1 || i > list->length) {
return ERROR;
}
//将要插入的位置后面的数据向后移动一位
if (i <= list->length) {
for (k = list->length - 1; k >= i-1; k--) {
list->data[k+i] = list->data[k];
}
}
list->data[i-1] = e; //插入新元素
list->length++;
return SUCCESS;
}
删除操作
讲完了插入的概念以及实现，应该对删除操作的行为也有了理解，即为从指定位置，删除需要删除的元素。
所以删除算法的思路：
-
如果删除位置不合理，抛出异常
-
取出删除元素
-
从删除元素开始，之后的元素至最后一个元素的存储位置向前挪动一个位置
-
表长-1
我们同样用栈的删除模式和指定位置删除的模式来实现代码。
栈的方式删除元素，即为每次都删除最后一个元素的代码实现：
/**
* 按照栈的方式删除元素 e用来接收删除出来的值
*/
Status popElement(ElementType e, SqList *list)
{
int length = list->length;
//判断线性表的合法性
if (length < 0 || length > MAXSIZE) {
return ERROR;
}
e = list->data[length - 1];
list->length -- ;
return SUCCESS;
}
在指定位置删除元素的代码实现如下:
/**
* 在线性表中的第i个位置删除元素 线性表的长度减一
*/
Status deleteElementWithLocation(ElementType e, int i , SqList * list)
{
//判断线性表的合法性
if (list->length < 0 || list->length > MAXSIZE ) {
return ERROR;
}
//判断删除位置的合法性
if (i < 1 || i > list->length) {
return ERROR;
}
e = list->data[i-1];
if (i < list->length) {
//将删除位置的后继元素前移
for (int k = i; k < list->length; k++) {
list->data[k-1] = list->data[k];
}
}
list->length -- ;
return SUCCESS;
}
遍历线性表
最后为了方便我们等下来验证代码的正确性，我们写一个函数来遍历线性表，代码如下：
/**
* 遍历线性表
*/
Status displayList(SqList * list)
{
if (list->length < 0 || list->length > MAXSIZE) {
return ERROR;
}
printf("***************************\n");
for (int i = 0; i < list->length; i++) {
printf("数值 = %d , 地址 = %p\n",list->data[i], &list->data[i]);
}
printf("***************************\n");
return SUCCESS;
}
验证代码正确性
在验证代码的正确性时，我用了Objective-C语言来写，大体思路如果是使用C语言的程序员，也是能完全看懂的。
我先创建了一个线性表，并且遍历它，打印地址来验证顺序结构存储空间的连续性。
//把1-8按顺序入栈
SqList * list = initSqList();
NSLog(@"把1-8按顺序入栈");
int j = 1;
for (int i = 0; i <8 ; i++) {
pushElement(j, list);
++j;
}
displayList(list);
因为存储空间总大小为10个元素单位，而我要求把1-8共8个数按顺序存入线性表中。打印结果如下：
***************************
数值 = 1 , 地址 = 0x1002014d0
数值 = 2 , 地址 = 0x1002014d4
数值 = 3 , 地址 = 0x1002014d8
数值 = 4 , 地址 = 0x1002014dc
数值 = 6 , 地址 = 0x1002014e0
数值 = 7 , 地址 = 0x1002014e4
数值 = 8 , 地址 = 0x1002014e8
***************************
我们可以看到，数值以及存储空间都是连续的，说明我们用栈的方式插入线性表是创建成功的。
我又要求往第八个位置插入724这个数字
//往第8个位置插入724;
insertElementWithLocation(724, list, 8);
运行结果如下，可以清楚的看到第八位是724，而原先的元素后移一位。
第八位增加724
***************************
数值 = 1 , 地址 = 0x100101320
数值 = 2 , 地址 = 0x100101324
数值 = 3 , 地址 = 0x100101328
数值 = 4 , 地址 = 0x10010132c
数值 = 5 , 地址 = 0x100101330
数值 = 6 , 地址 = 0x100101334
数值 = 7 , 地址 = 0x100101338
数值 = 724 , 地址 = 0x10010133c
数值 = 8 , 地址 = 0x100101340
***************************
验证删除操作的时候，我们命令把第五位的数据删除（以原始数据为例）
// 把第五位的数据删除
deleteElementWithLocation(0, 5, list);
得到结果如下:
删除第五位
***************************
数值 = 1 , 地址 = 0x1002014d0
数值 = 2 , 地址 = 0x1002014d4
数值 = 3 , 地址 = 0x1002014d8
数值 = 4 , 地址 = 0x1002014dc
数值 = 6 , 地址 = 0x1002014e0
数值 = 7 , 地址 = 0x1002014e4
数值 = 8 , 地址 = 0x1002014e8
***************************
至此，我们可以得出结论我们创建的线性表是正确的，连续的，具备线性表的属性的。而我们在对线性表的顺序存储结构的插入和删除的操作也是正确的，实现了功能。所以今天的线性表的顺序存储结构，就讲到这里，以上代码我已经上传到Github上，若有讲的不清楚的地方，也可以下载Github上的代码来参考。