【Ⅱ线性表】1.线性表的定义和基本操作

线性表】1.线性表的定义和基本操作"/>

【Ⅱ线性表】1.线性表的定义和基本操作

本篇文章我们将学习第一个数据结构——线性表。

每当学习新的数据结构时，大家一定要清楚地认识每个数据结构的三要素，在头脑里有一个良好的框架。

逻辑结构	首先需要知道该数据结构的逻辑关系（比如线性还是非线性）以及逻辑之间的数学特性（比如栈的先进先出、完全二叉树的父子关系计算等）
存储（物理）结构	选择一个好的存储结构（顺序存储、链式存储等）将数据存储到计算机中，对每一种存储方式熟练掌握并深刻体会该存储方式的优缺点（比如是否支持随机存取，增删是否需要大量挪动元素等）
数据运算	熟练掌握每种存储方式的运算代码实现（比如初始化，销毁，增删查改等）

一、线性表的定义

1、引例

引例1：英文字母（A,B,……,Z）	引例2：排队

2、定义

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列

3、非空的线性表或线性结构的特点

<1>存在唯一的一个被称作“第一个”的数据元素

<2>存在唯一的一个被称作“最后一个”的数据元素

<3>除第一个之外，结构中的每个数据元素均只有一个前驱

<4>除最后一个之外，结构中的每个数据元素均只有一个后继

4、注解

①线性表的表示：	若用L命名，表示为L=(，，，……，，，，……，an)
②元素：	这里的元素是抽象的，在具体实现时可以具体确定下来；可以是整数、学生信息等
③线性表的逻辑特性：	：唯一的表头元素 ：唯一的表尾元素 除去：每个元素有且仅有一个直接前驱   除去：每个元素有且仅有一个直接后继

①线性表的表示：若用L命名，表示为L=(a1,a2,a3,a4,a5,···,a(i-1),ai,a(i+1),···,an)

②元素：这里的元素是抽象的，在具体实现时可以具体确定下来；可以是整数、学生信息等

③线性表的逻辑特性：

a1：唯一的表头元素

an：唯一的表尾元素

除去a1：每个元素ai有且仅有一个直接前驱a(i-1)

除去an：每个元素ai有且仅有一个直接后继a(i+1)

④线性表的长度：线性表中所含元素的个数；n=0表示元素个数为0，是空表

⑤线性表的特点：

表中元素是有限个

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

表中元素的数据类型都相同（表中每个元素占用相同大小的存储空间；表中元素都是数据元素，每一个元素都是单个元素）

表中元素具有抽象性。线性表仅讨论元素间的逻辑关系，不讨论元素的具体内容

⑥位序：ai是第i个数据元素，称i为数据元素ai在线性表中的位序；数组下标是从0开始的，位序是从1开始的

⑦线性表、顺序表、链表：

线性表是逻辑结构，表示一对一的相邻关系

顺序表是采用顺序存储对线性表的实现，是指存储结构

链表是采用链式存储对线性表的实现，是指存储结构

⑧判断给定的某个例子是不是线性表：一对一？类型相同？有限序列？逻辑结构？

5.例子

例子1：班级同学之间的友谊

不是线性表，不是一对一线性关系

例子2：点名册

是线性表，满足一对一、类型相同、有限序列、逻辑结构

同学的姓名、性别、出生年月什么的，这其实是数据项；一个数据元素可以由若干个数据项组成

例子3： 一群人线性排队，中间用了个洋娃娃占位

不是线性表，类型不相同

二、线性表的存储结构

这里只是简单的引入一下，不用太纠结，后面文章会具体深入下去学习线性表的存储结构

线性表的存储结构：顺序存储结构（顺序表）、链式存储结构（链表）

1.顺序表、链表

顺序表

定义：把线性表中所有元素按照逻辑顺序，依次存储到从指定位置开始的一块连续存储空间

特点：第一个元素的存储位置就是指定的存储位置；第i+1个元素的存储位置紧接在第i个元素的存储位置后面

例子：

链表

每个节点内容：所存储的元素的信息；元素之间的逻辑关系信息(指针)

例子：

2.顺序存储与链式存储的比较

顺序表

可以随机访问

占用存储空间连续

顺序表的插删，需要移动多个元素

链表

只能顺序访问

占用额外的存储空间存储元素间关系，空间利用率更低

存储空间不一定要连续

链表的插删不需要移动多个元素

三、线性表的基本操作

1.基本操作

InitList(&L)：初始化表。构造一个空的线性表

Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值e的元素

GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值

ListInsert(&L,i,e)：插入操作。在表L中第i个位置上插入指定元素e

ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置上的元素，并用e返回删除元素的值

Printlist(L)：输出操作。按前后顺序输出线性表的所有元素值

Empty(L)：判空操作。若L为空表，则返回true，否则返回false

DestroyList(&L)：销毁操作。销毁线性表一并释放线性表L所占用的内存空间

2.注解

(1)对这些基本操作的具体实现要依赖于具体的存储结构

(2)基本操作的使用：在我们做代码题的时候，某道题里涉及到线性表的基本操作时可以直接使用，不必去实现完整函数

(3)这里的&是引用

注：引用&只出现在C++中，C中无【使用时不必考虑，C++兼容C】；使用指针也可以达到相同效果，但更麻烦【不推荐使用】

引用&使用场景：

①当需要对传入值本身修改时，可选择使用

②当数据本身较大时，为避免复制开销，可使用（普通方式为值的复制，把实参内存中的内容复制到形参内存中去，但时间消耗很大，下面运行例子可以证明）