数据结构--线性表之顺序表

本篇主要整理介绍数据结构--线性表的使用，持续更新中。

老铁们，整理不易，创作不易，先赞后看养成习惯，你的支持是对我更新最大的鼓励！

线性表 知识框架

线性表概念：线性表 （ linear list ） 是n（n>=0）个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，其中n为表长，若用L命名线性表，则有L=（a 1，a 2，......,a i,a i+1,...,a n）,其中a1为表头元素，an为表尾元素。

线性表特点：

1.表中元素个数有限

2.表中元素具有逻辑上的顺序性，表中元素有先后次序

3.表中元素都是数据元素，每个元素都是单个元素

4.表中元素的数据类型都相同，每个元素占用相同大小的存储空间

5.表中元素具有抽象性，仅讨论元素之间的逻辑关系，而不考虑元素究竟表示什么内容

常见的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

1. 顺序存储

1.1 顺序表（线性表的顺序表示）

顺序表定义：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组 上完成数据的增删查改。

1.2 顺序表分类

一般可以分为：

1.静态顺序表：使用定长数组存储元素。

2.动态顺序表：使用动态开辟的数组存储。

1.2.1 静态顺序表：

静态顺序表只适用于确定知道需要存多少数据的场景。

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

注：一维数组可以是静态分配，也可以是动态分配。在静态分配时，由于数组的大小和空间事先已经固定，定长数组导致MaxSize定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

1.2.2 动态顺序表：

#define InitSize 100   //表长度的初始定义
tyepdef struct{
ElemTyepe *data;       //动态分配数组的指针
int MaxSize,length;    //数组的最大容量和当前个数
}SeqList;              //d冬天分配数组顺序表的类型定义

C语言的初始动态分配语句为：

L.data=(ElemType*)malloc(sizeof(Elemtype)*InitSize);

C++的初始动态分配语句为：

L.data=new ElemType[InitSize];

注：动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化，依然是随机存取的方式，只是分配的空间大小可以在运行时动态决定。

1.3 顺序表的特点

最主要的特点是 随机访问 ，即通过首地址和元素序号可在时间O（1）内找到指定的元素。

此外还有，存储密度高，每个节点只存储数据元素，逻辑上相邻的元素物理上也相邻，所以插入删除操作需要大量移动元素。（弊端）

1.4 顺序表基本操作实现

这里重点讨论实现相对繁琐的插入删除和按值查找算法，其他操作比较简单。

（1）插入操作

在顺序表L第i个位置插入新元素e，若i输入不合法，则返回false，表示插入失败；否则，将第i个元素及其往后的所有元素依次往后移动一个位置并插入e元素，顺序表的长度加1，插入成功，返回true。

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--)
    {
        L.data[j]=L.data[j-1]//将第i个元素及之后的元素后移
    }
        L.data[i-1]=e;       //在第i位插入e
        L.length++;          //线性表长度加1
        return true; 
}

注：时间复杂度

最好情况：在表尾插入，时间复杂度 O（1）

最坏情况：在表头插入，元素向后移动n次，时间复杂度O（n）

未完待续，下节预告，顺序表删除操作，查找操作，单链表的实现，参考下方下节目录。
（2）删除操作

（3）查找操作

2. 链式存储

2.1 单链表    （指针实现）

2.2 双链表    （指针实现）

2.3 循环链表 （指针实现）

2.4 静态链表 （数组实现）

持续更新中，未完待续..

老铁们觉得对你有帮助还请点赞收藏转发评论，你的支持是对我最大的鼓励