一、顺序表的定义
它是一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表的特点就是逻辑顺序与物理顺序相同

线性表的顺序存储就称为顺序表，也就是说顺序表是数据结构

线性表中元素的第一个位置序号是从1开始的，而数组中元素的下标是从0开始

（一）顺序表静态分配定义

#define MaxSize 50             //顺序表的最大长度
typedef struct
{
    ElemType data[MaxSize];    //顺序表的元素
    int length;                //顺序表当前长度
}SqList;                        //顺序表的类型定义

（二）顺序表的动态分配定义

#define InitSize 100       //表长度的初始定义
typedef struct
{
    ElemType *data;        //指示动态分配数组的指针
    int MaxSize,length;    //数组的最大容量和当前个数
}SeqList;   


L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize); //C的初始动态分配

L.data=new ElemType[InitSize];                       //C++的初始动态分配

二、顺序表上基本操作的实现

（一）插入操作

插入操作思路：

先看给的位置i是否有效，即判断i是否小于1或者大于最大长度
判断当前存储空间是否已满
将第i个元素及之后的元素全部后移
在i位置放入e，然后线性表的长度加1

bool ListInsert(SqList &L,int i,ElemType e)
{
    if(i<1||i>L.length+1)
        return false;
    if(L.length>=MaxSize)
        return false;
    for(int j=L.length;j>=i;j--)
        L.data[j]=L.data[j-1];

    L.data[i-1]=e;
    L.length++;
    return true;
}

（二）删除操作

先判断删除位置是否有效，即i是否在1到length这个范围内
将删除元素赋给e
将i个位置后的元素全部前移
线性表长度减1

删除意味着还需要前移

bool ListDelte(SqList &L,int i,Elemtype &e)
{
    if(i<1||i>L.length)
        return false;
    e=L.data[length-1];
    for(int j=i;j 
（三）按值查找 
        按值查找操作思路：直接一个for循环顺序查找看有无匹配的值即可 
int LocateElem(SqList L,ElemType e)
{
    int i;
    for(i=0;i 
 

三、经典例题 
（一）选择题 
 1.若长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，则i的合法值应该是（） 
        A.1≤i≤n                B.1≤i≤n+1                C.0≤i≤n-1                B.0≤i≤n 
        插入操作输入的i，意思是插入的那个值顶替这个位置，也就是说表尾元素后面也能插入的，而表头元素之前插入就是输入表头元素的位置即可。因此i的最大合法值是n+1  
（二）应用题 
2.从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。 
        算法思路： 
        （1）先判断表是否为空 
        （2）首先要进行一个for循环，找出最小值元素的位序 
        （3）然后进行删除操作，即找到数组[位序-1]返回，并将最后一个元素的值赋给他 
        （4）最后再将最后一个元素删除,即线性表的长度减1 
bool DeleteMin(sqList &L,ElemType &e)
{
    if(L.length==0)
        return false
    else
    {
        int Min=1000000;
        int Key=-1;
        int i,j;
        for(i=0,i 
3.设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1) 
        算法思路： 
        扫描顺序表L的前半部分元素，对于元素L.data[i](0<=i 
void ChangeList(SqList &L)
{
    for(int i=0;i 
4.对长度为n的顺序表L,编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素 
        算法思路： 
（1）先判断表是否为空 
（2）用变量k记录表中值不等于x的个数，k作为顺序表新的数组下标 
（3）当值不等于x的时，data[k]保存原来的数值，然后k自增；当值等于x的时候，直接不作处理 
（4）新的表长为k+1 
bool Del_X(SqList &L,Elemtype x)
{
    if(n==0)
    return false;
    else
    {
        int k=0;
        for(int i=0;i

数据结构第二章——线性表的顺序表示

（一）顺序表静态分配定义 #define MaxSize 50 //顺序表的最大长度 typedef struct { ElemType data[MaxSize]; //顺序表的元素 int length; //顺序表当前长度 }SqList; //顺序表的类型定义

二、顺序表上基本操作的实现

三、经典例题

C/C++/C#相关栏目本月热门文章

（一）顺序表静态分配定义
#define MaxSize 50 //顺序表的最大长度 typedef struct { ElemType data[MaxSize]; //顺序表的元素 int length; //顺序表当前长度 }SqList; //顺序表的类型定义