1. 线性表引入

线性表的物理结构分为顺序存储结构和链式存储结构

其中线性表的顺序存储结构指的是用一段地址连续的存储单元一次存储线性表的数据元素。

在c语言当中一般是一维数组来实现顺序存储结构，即把第一个数据元素存储到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

下面是线性表的顺序存储的结构代码。

#include 

#define MAXSIZE 20                  /*存储空间初始分配量*/
typedef  int ElemType;              /*ElenType类型根据实际情况而定，这里假设为int*/
typedef struct{
    ElemType data[MAXSIZE];         /*数组存储数据元素，最大值为MAXSIZE*/
    int length;                     /*线性表当前长度*/
}SqList;

可以发现，描述顺序存储需要三个属性：

• 存储空间的起始位置：数组data；
• 线性表的最大存储容量：数组长度MAXSIZE；
• 线性表当前的长度：length。
  

这个地方应该注意“数组的长度”与“线性表的长度”概念的区别：

• 数组的长度指的是存放线性表存储空间的大小，存储分配后一般是不变的；
• 线性表的长度指的是线性表中数据元素的个数，会随着线性表插入和删除 *** 作而变化。
  

应注意的是，线性表的长度应小于等于数组的长度。

用时间复杂度的概念来计算可以发现，他的存储时间性能为O（1），通常，具有这一特点的存储结构称之为随机存取结构。

/*用数组创建线性表*/
void CreateList(SqList *&L, ElemType a[], int n)
{
    int i;
    L=(SqList *)malloc(sizeof(SqList));
    for (i=0; idata[i]=a[i];
    L->length=n;
}


/*初始化线性表InitList(L)*/
void InitList(SqList *&L)   //引用型指针
{
    L=(SqList *)malloc(sizeof(SqList));
    //分配存放线性表的空间
    L->length=0;
}
 
 
/*判定是否为空表ListEmpty(L)*/
bool ListEmpty(SqList *L)
{
    return(L->length==0);
}
 
/*求线性表的长度ListLength(L)*/
int ListLength(SqList *L)
{
    return(L->length);
}
 
/*输出线性表DispList(L)*/
void DispList(SqList *L)
{
    int i;
    if (ListEmpty(L)) return;
    for (i=0; ilength; i++)
        printf("%d ",L->data[i]);
    printf("\n");
}
 

/*销毁线性表DestroyList(L)*/   
void DestroyList(SqList *&L) 
{ 
   free(L); 
   printf("线性表被释放！表长度：%d\n", L->length);
}