第2章 线性表[视频讲解]
2.1 线性表的类型定义
视频二维码（扫码观看）
一、线性表的定义
线性表（Linear List）：是由n（n≥0）个数据元素（结点）a1，a2，…，an组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。
当n＝0时，称为空表。当n＞0时，将非空的线性表记作：（a1，a2，…，an）。
a1称为线性表的第一个（首）结点，an称为线性表的最后一个（尾）结点。a1，a2，…，ai－1都是ai（2≤i≤n）的前驱，其中ai－1是ai的直接前驱；ai＋1，ai＋2，…，an都是ai（1≤i≤n－1）的后继，其中ai＋1是ai的直接后继。
二、线性表的逻辑结构
线性表中的数据元素ai所代表的具体含义随具体应用的不同而不同，在线性表的定义中，ai只不过是一个抽象的表示符号。
①线性表中的结点可以是单值元素（每个元素只有一个数据项）。
【例1】26个英文字母组成的字母表：（A，B，C、…、Z）
【例2】某校从1978年到1983年各种型号的计算机拥有量的变化情况：（6，17，28，50，92，188）
【例3】一副扑克的点数：（2，3，4，…，J，Q，K，A）
②线性表中的结点可以是记录型元素，每个元素含有多个数据项，每个项称为结点的一个域。每个元素有一个可以唯一标识每个结点的数据项组，称为关键字。
【例4】某校2001级同学的基本情况：{（‘2001414101’，‘张里户’，‘男’，06/24/1983），（‘2001414102’，‘张化司’，‘男’，08/12/1984），…，（‘2001414102’，‘李利辣’，‘女’，08/12/1984）}。
③若线性表中的结点是按值（或按关键字值）由小到大（或由大到小）排列的，称线性表是有序的。
④线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。
⑤对线性表的数据元素可进行访问、插入和删除操作。
三、线性表的抽象数据类型定义
【例5】假设：有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A＝A∪B。要求对线性表作如下操作：扩大线性表LA，将存在于LB中而不存在于LA中的数据元素插入到LA中去。
操作步骤：
1．从线性表LB中依次查看每个数据元素；
2．依值在线性表LA中进行查访；
3．若不存在，则插入之。
若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即ai≥ai－1或ai≤ai－1（i＝2，3，…，n），则称该线性表为有序表（Ordered List）。
【例6】假设：LA＝（3，5，8，11），LB＝（2，6，8，9，11，15，20）。对集合LA和LB而言，值相同的数据元素必定相邻。
要求生成一个新表LC，使LC中的数据元素仍按值非递减有有序排列。
