🌺线性表的定义

线性表：线性表是由n ( n≥0 ) 个数据特性相同的元素构成的有限序列。n是线性表的表长，当 n=0时线性表是一个空表。若用 L 来命名线性表，则其一般表达式为

L  =  (a1，a2，...... ，an)

图像：

a1是唯一的【第一个】数据元素，又称表头元素。an是唯一的【最后一个】数据元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后续。

以上就是线性表的逻辑特性，这种线性有序的逻辑结构正是线性表名字的由来。

🌺线性表的特点

从线性表的图像和表达式中可以很明显的看出线性表的特点，那就是

存在唯一的“第一元素”，没有前驱；

除第一元素外，其它元素均有唯一的＂前驱＂。

存在唯一的“最后元素”，没有后继；

除最后元素外，其它元素均有唯一的＂后继＂；

🌺 顺序表

      线性表的顺序存储又称为顺序表，它用一组地址连续的存储单元依次存放线性表中的数据元素,从而使得逻辑上相邻的两个元素在物理位置上也相邻。

       第1个元素存储在线性表的起始位置,第i个元素的存储位置后面紧接着存储的是第i+1个元素。当我们知道顺序表的第一位元素的地址时，就很容易就可以推理出剩余元素的地址，因此顺序表是一种随机存取的存储结构。

顺序表的特点：表中元素的逻辑顺序与其物理顺序相同

假设线性表L存储的起始位置是 LOC（A），sizeof（ElemType）是每个数组元素所占用的存储空间的大小，那么线性表L的顺序存储如下图所示。

线性表的顺序存储结构

       每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的常数。因此，线性表中的任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

看到这里不知道大家有没有感觉很熟悉，似曾相识。没错，我们的老朋友——数组也是一种随机存取的存储结构。因此，通常用高级程序设计语言中的数组来描述线性表的顺序存储结构。

注意：线性表中元素的位序是从【1】开始的，而数组中元素的下标是从【0】开始的.

🌷实现原理

首先我们需要定义一下顺序表的长度，也就是最大有多少个元素。我们采用【define】来确定长度，因为使用【define】可以更方便的进行对长度的修改。

#difine        MAXSIZE        ****        //最大长度

下面，我们用结构体，定义一个新的数据类型。

typedef struct
{   ElemType *elem;  //存储空间基地址    
  int length;     //当前长度
}SqList;            //结构类型为SqList

第一数据域：

在结构体中包含了两个数据域，第一个数据域是elem，很明显，elem是一个指针域，它指向了ElemType类型（在真正实现时，是本来的数据类型）

ElemType：它是element type（“元素的类型”）的简化体

【ElemType *elem】代表着连续空间的首地址，也称基地址，elem类似于数组的名字，它也可以当作数组名字使用。

第二数据域：

第二数据域length表示线性表的数据元素的长度

🌷顺序表的初始化

顺序表的初始化就是建立一个新的空的顺序表

🔺实现原理

1️⃣为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址。

2️⃣将表的当前长度设为0。

💬 代码演示

Status InitList(SqList &L)
{//构造一个空的顺序表L 
  L.elem=new ElemType[MAXSIZE];//为顺序表分配一个大小为MAXSIZE的数组空间  
  if(!L. elem) exit(OVERFLOW);//存储分配失败退出 
  L.length=0;                        //空表长度为0 
  return OK; 
}

🌷顺序表的取值

🔺实现原理

1️⃣判断指定位置是否合理，若不合理，则返回 ERROR。

2️⃣若i值合理，则将第i个元素L.elem[i-1]赋值给参数e，通过e返回第i个数据元素的传值。

💬 代码演示

Status GetElem(SqListL, int i,ElemType &e)
{
  if(i<1||i>L. length) //判断是否合理 
  return ERROR;e=L. elem[i-1];    //elem[i-1]存储第i个数据元素 
  return OK;
}

🌷顺序表的查找

🔺实现原理

1️⃣从第一个元素开始，一个一个与e相比较，若查找成功，返回该元素在表中的位置序号。

2️⃣若查找失败，则返回0。

💬 代码演示

int LocateElem(SqList L,ElemType e)
{//在顺序表1中查找值为e的数据元素，返回其序号
  for(i=0;i<L. length;i++)
  {
  if(L. elem[i]==e) 
    return i+1;
  }
  return 0; 
}

🌷顺序表的插入

线性表的插入操作是指在表的第i个位置插入一个新的数据元素e，使得长度为n的线性表变成长度为n+1的线性表。

❓那么问题来了，应该怎么实现呢？

在线性表的顺序存储结构中，由于逻辑上相邻的数据元素在物理位置上也是相邻的，为了在线性表的第i个位置上插入一个数据元素，则需将第i个至最后一个数据元素依次向后移动一个位置。

🔺实现原理

1️⃣判断插入位置i是否合法(i值的合法范围是1≤i≤n+1)，若不合法则返回ERROR。

2️⃣判断顺序表的存储空间是否已满，若满则返回ERROR。

3️⃣将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置(i=n+1时无需移动）

4️⃣将要插入的新元素e放入第i个位置。

5️⃣表长加一。

🔑空间状态

💬 代码演示

Status ListInsert(SqList &L, int i,ElemType e)
{//在顺序表L中第i个位置插入新的元素e，i值的合法范围是1≤i≤L. length+1
  if((i<1)||(i>L. length+1)) 
  return ERROR;//i值不合法
  if(L. length==MAXSIZE) 
  return ERROR;//当前存储空间已满
  for(j=L. length-1;j>=i-1;j--)
  L.elem[j+1]=L.elem[j];
  L.elem[i-1]=e;
  ++L. length;
  return OK;
}

🌷顺序表的删除

和插入同理，在线性表的顺序存储结构中，由于逻辑上相邻的数据元素在物理位置上也是相邻的，为了在线性表的第i个位置上删除一个数据元素，则需将第i个至最后一个数据元素依次向前移动一个位置。

🔺实现原理

1️⃣判断插入位置i是否合法(i值的合法范围是1≤i≤n+1)，若不合法则返回ERROR。

2️⃣将第i+1个至第n个元素依次向前移动一个位置。

3️⃣表长减一。

🔑空间状态

💬 代码演示

Status ListDelete(SqList &L, int i)
{//在顺序表L中删除第i个元素，i值的合法范围是1≤i≤L.1ength 
  if(i<1)||(i>L. length)) 
  return ERROR;//i值不合法
  for(j=i;j<=L. length-1;j++)
  L,elem[j-1]=L,elem[j];//被删除元素之后的元素前移
  --L. length;//表长减1
  return OK;
}

🌷顺序表的优缺点

顺序表的内存连续，支持随机访问,可以高效的按下标进行操作，可以很方便的查找表中任一元素。

然而，通过上文不难发现，在做插入或删除操作时，需移动大量元素。当表中数据元素个数较多且变化较大时，操作过程相对复杂。这些问题，可以通过线性表的另一种表示方法——链式存储结构来解决。