1、定义

    线性表是具有相同数据类型的n个数据元素的有限序列。

2、特点


  • 表中元素个数有限。
  • 表中元素具有逻辑上的顺序性。
  • 表中元素都是数据元素，每个元素都是单个元素。
  • 表中的元素数据类型相同，即每个元素占用的相同的存储空间。 

3、线性表的基本操作 

InitList(&L);//初始化表
Length（L）;//求表长，返回线性表的长度。
LocateElem(L,e);//按值查找。在表中找到具有给定关键字的元素。
GetElem(L,i);//按位查找，获取表中第i个位置的元素的值。
ListInsert（&L,i,e）;//插入操作，在表中第i个位置上插入元素e。
ListDelete（&L,i,e）;//删除操作，删除表中第i个位置上的元素，并用e返回删除元素的值。
PrintList（L）;//输出操作，按顺序输出线性表中的值。
Empty（L）;//判空操作。
DestroyList（&L）//销毁操作。

4、顺序表示

  • 它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
  • 顺序表的特点就是表中元素的逻辑顺序与其物理顺序相同。
  • 假定线性表的数据类型为Elemtype，则线性表的顺序存储类型描述为: 
    #define MaxSize 50   //定义线性表的最大长度
typedef struct{
    ElemType date[MaxSize];   //顺序表的元素
    int length;      //顺序表当前长度
}SqList;             //顺序表的类型定义
  • 一维数组可以静态分配，也可以动态分配。动态分配的语句为： 
    L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize)；
  • 顺序表的最主要特点是随机访问。
  • 顺序表在逻辑上相邻的元素物理上也相邻，所以删除和插入操作需要移动大量元素。

顺序表上基本操作的实现

（1）插入操作： 
bool ListInsert(SqList &L,int i,ElemType e){
    if(i<1||i>L.length+1){     //判断i的范围是否有效
        return false;
    }
    if(L.length>=MaxSize){    //当前存储空间已满，不能插入
        return false;
    }
    for(int j=L.length;j>=i;j++){   //将第i个以后的元素向后移动
        L.data[j] = L.data[j-1];
    }
    L.data[i-1] = e;     //第i个位置放入e
    L.length++;         //线性表的长度+1
    return true;
}
线性表插入算法的平均时间复杂度为O（n）