问题引入

在数据结构中，线性表是一种很重要的线性结构。线性表分为多种类型，常见的如顺序表、链表等，如果此时此刻你对“顺序表（顺序存储）”感到困惑，那就继续看下去，我们一步一步去剖析。

如果你想要进一步了解“链表”——1.“顺序创建（尾插法）”、2.“逆序创建（头插法）”，

请参考文章： 1. “链表（详解）- C++（顺序创建链表-尾插法）”（点击查看）；

2. “链表（详解）- C++（逆序创建链表-头插法）”（点击查看）。

问题分析

如果想要搞明白“线性表”，首先你要明白两个问题：

1.什么是线性表？

答：一个“线性表”（linear list）是n个数据元素的有限序列。

2.“顺序表（顺序存储）”的特点是什么？

答：（1）顺序表顺序存储 可随机存取，即可以任意从任何一个位置插入、删除元素。

（2）用一组连续的存储单元储存线性表的数据元素（这组存储单元必须是连续的）。也即“使用数组对元素进行存储”。

（3）表中元素个数叫表长，元素个数可以有多个，也可以为0。某个元素的上一个元素叫直接前驱元素，下一个元素叫直接后继元素。

（4）优点：可以快速存储表中任意位置的元素的值；无需为表中的逻辑关系增加额外的存储空间。

（5）缺点：插入和删除元素需移动大量的元素；容易生成存储空间"碎片"。

顺序表整体结构分析

顺序表也即线性表的一种顺序存储结构，用一组连续的存储单元储存线性表的数据元素（这组存储单元必须是连续的）。也即“使用数组对元素进行存储”。我们可以借助数组的思想实现顺序表的顺序存储，分配依次存储空间后，接下来我们就可以根据位置插入、删除元素，如下图，如果仍然感到困惑，接下来我们分过程去看元素入“顺序表”和出“顺序表”的过程。

元素入顺序表分析

对于顺序表而言，采用的是“顺序存储”的方式，因此我们只要指定好一定空间，按照位置进行插入元素即可，只要该位置无元素或者顺序表未满，那么就可以在指定位置插入数据，而不用事先设置指针指向该位置。

例如：

在链队列中插入元素33。

分析：首先对顺序表进行“遍历”，查找指定位置或者找到一个空位插入数据，“插入”的实质其实就是先将表长 +1，之后将“指定位置”后的所有元素向后移动一个位置，“从后向前”依次后移，避免数据被前面的元素覆盖，如图1、2。

（务必注意： “表长”的变化和移动的方向。）

图1

图2

元素出顺序表分析

例如：

在链队列中删除元素33。

明白了元素入顺序表，那么元素的出顺序表与入顺序表过程相似。分析：首先对顺序表进行“遍历”，查找指定位置上的元素，“删除”的实质其实就是查找到要删除的元素，然后将“指定位置”后的所有元素向前移动一个位置，即覆盖要删除的元素，最后表长 -1，“从前向后”依次前移，每一个元素覆盖上一个元素，如图1、2。

（务必注意： “表长”的变化和移动的方向。）

图1

图2

代码实现

说明：采用C++语言，编译环境为DevC++。

//导入头文件
#include<malloc.h>
#include<iostream>
using namespace std;//定义线性表
typedef struct{int *elem;//数据元素int length;//当前长度int listsize;//存储容量
}SqList;//初始化线性表
void InitSqList(SqList &L){L.elem=(int *) malloc(50*sizeof(int));L.length=0;//空表L.listsize=50;
}//创建顺序表 
void CreatSqList(SqList &L){int i=0;cout<<"请输入数据，以-10000结束："<<endl;cin>>L.elem[i];while(L.elem[i]!=-10000 && L.length<L.listsize){++L.length;i++;cin>>L.elem[i];}
}//输出
void PrintSqList(SqList &L){int i;cout<<"\n线性表中的全部元素为：\n";for(i=0;i<L.length;i++)cout<<L.elem[i]<<' ';cout<<endl<<endl;
}//查找，若不存在输出0
int LocateSqList(SqList L,int e){int i=0;int *p=L.elem;while(i<L.length){p++;i++;if((*p)==e)return i+1;if(i==L.length) return 0;}
}//插入
int InsertSqList(SqList &L,int i,int h){int *p;int *q;p=&(L.elem[L.length+1]);q=&(L.elem[i-1]);for(p;p>=q;p--)*p=*(p-1);++L.length;//插入前 表长+1 *(q)=h;return 0;//返回0表示成功
}//删除
int DeleteSqList(SqList &L,int m){int *p;int *q;p=&(L.elem[L.length]);q=&(L.elem[m]);for(q;q<p;q++)*(q-1)=*q;--L.length;//删除后 表长-1 return 0;//返回0表示成功
}//主函数
int main(){SqList L;int e;int i;int h;int m;InitSqList(L);CreatSqList(L);PrintSqList(L);cout<<"请输入要查找的数据元素:"<<endl;cin>>e;cout<<"数据"<<e<<"在表中第 "<<LocateSqList(L,e)<<" 个位置。"<<endl;cout<<"请输入第几个位置插入数据元素:"<<endl;cin>>i;cout<<"请输入要插入的新数据元素:"<<endl;cin>>h;cout<<InsertSqList(L,i,h)<<endl;PrintSqList(L);//输出更改后的线性表cout<<"请输入第几个位置删除数据元素:"<<endl;cin>>m;cout<<DeleteSqList(L,m)<<endl;PrintSqList(L);//输出更改后的线性表
}