第3章线性表 ◆线性表及逻辑结构 ◆线性表的顺序存储 ◆线性表的链式存储 ◆链式存储结构的应用
第3章 线性表 线性表及逻辑结构 线性表的顺序存储 线性表的链式存储 链式存储结构的应用
线性表及逻辑结构 线性表:由n(n>0)个性质相同的数据元素组成的有限序列。 线性表的长度即为线性表中元素的个数n(0),当 n=0时,称该线性表为空表 线性表举例: 英文字母表就是一个线性表: (A, B, C ◎我国的省、市、自治区,可以组成一个线性表 (北京,天津,上海, ,宁夏,台湾)
线性表及逻辑结构 线性表：由n(n>0)个性质相同的数据元素组成的有限序列。 线性表的长度即为线性表中元素的个数n(0)，当 n＝0时，称该线性表为空表。 线性表举例： 英文字母表就是一个线性表： (A, B, C,······, Z) 我国的省、市、自治区，可以组成一个线性表： (北京, 天津, 上海,······, 宁夏, 台湾）
线性表的有关概念 ●位序在一个非空表 中的每个数据元素都有一个确定的位置,如a1是第 个数据元素,an是最后一个数据元素,a1是第个数据 元素,称i为数据元素a1在线性表中的位序。 前驱/后继元素:若将线性表记为:(a1,,ai-1 ai,ai+1,…,an),则表中ai-1先于ai,a先于ai+1 就称ai-1是ai的直接前驱元素,ai+1是a的直接后继 元素。 注意: 除第一个元素a1元素以外,每一个数据元素有且 仅有一个前趋元素。 o除最后一个元素以外,每个数据元素有且仅有 个后继元素
线性表的有关概念 位序:在一个非空表 (a1 ，a2 ，…，ai，…，an-1 ，an ) 中的每个数据元素都有一个确定的位置，如a1是第一 个数据元素，an是最后一个数据元素，ai是第i个数据 元素，称i为数据元素ai在线性表中的位序。 前驱/后继元素：若将线性表记为：(a1, ..., ai-1 , ai , ai+1 , ..., an )，则表中ai-1先于ai，ai先于ai+1， 就称ai-1是ai的直接前驱元素，ai+1是ai的直接后继 元素。 注意： 除第一个元素a1元素以外，每一个数据元素有且 仅有一个前趋元素。 除最后一个元素以外，每个数据元素有且仅有一 个后继元素
有头线性表的运算 ●初始化:创建一个空的线性表L ●计数:求线性表L的长度。 ●存取:存取第i个数据元素。 ●插入:在第个数据元素之前,插入一个新的数据元 素;或在第个元素后,插入一个新的数据元素
有关线性表的运算 初始化：创建一个空的线性表L。 计数：求线性表L的长度。 存取：存取第i个数据元素。 插入：在第i个数据元素之前，插入一个新的数据元 素；或在第i个元素后，插入一个新的数据元素
●删除:删去第个数据元素。 ●归并:把两个或两个以上的线性表合并在一起,形成 个新的线性表。 ●分拆:把一个线性表拆成两个或多个线性表。 ●查找:按某个特定的值查找线性表中的某个元素。 ●排序:对线性表中的某个元素按某个数据项的值递增 (或递减)的顺序进行重新排序
删除：删去第i个数据元素。 归并：把两个或两个以上的线性表合并在一起，形成 一个新的线性表。 分拆：把一个线性表拆成两个或多个线性表。 查找：按某个特定的值查找线性表中的某个元素。 排序：对线性表中的某个元素按某个数据项的值递增 （或递减）的顺序进行重新排序