线性结构的定义 若结构是非空有限集,则有且仅有一个开始结点和一个 终端结点,并且所有结点都最多只有一个直接前趋和一个直 接后继。一→可表示为:(a1,a2 特点①只有一个首结点和尾结点; 特点②除首尾结点外,其他结点只有一个直接前驱和一个直 接后继。 简言之,线性结构反映结点间的逻辑关系是一对二(1:1的。 线性结构包括:线性表、堆栈、队列、字符串、数组 等,其中最典型、最常用的是 线性表
1 线性结构的定义： 若结构是非空有限集，则有且仅有一个开始结点和一个 终端结点，并且所有结点都最多只有一个直接前趋和一个直 接后继。 →可表示为：（a1 , a2 , ……, an） 简言之，线性结构反映结点间的逻辑关系是 的。 特点① 只有一个首结点和尾结点； 特点② 除首尾结点外，其他结点只有一个直接前驱和一个直 接后继。 线性结构包括：线性表、堆栈、队列、字符串、数组 等，其中最典型、最常用的是------ 线性表 一对一 (1:1)
第2章线性表 21线性表的基本概念 22线性表的顺序表示和实现 23线性表的链式表示和实现 24应用举例
2 第2章 线性表 2.1 线性表的基本概念 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 应用举例
2.1线性表的基本概念 1、线性表 它是一种最简单的线性结构。是一种可以在任 意位置进行插入和删除数据元素操作的,由n(n0) 个相同类型数据元素a0,a1,…,an-1组成的线性结 构
3 2.1 线性表的基本概念 １、线性表 它是一种最简单的线性结构。是一种可以在任 意位置进行插入和删除数据元素操作的，由n（n≥0) 个相同类型数据元素a0 , a1 , … , an-1组成的线性结 构
线性表的逻辑结构: a 09a1 a -1,ai9ai+1 数据元素 线性起点 a;的直接前趋a的直接后继线性终点 下标,是元素的 n为元素总 序号,表示元素n=0时称为空表 个数,即表 在表中的位置 长。n≥0
4 （a0 , a1 , … ai-1， ai , ai＋1 ，…, an-1） 线性表的逻辑结构： n=0时称为 数据元素 线性起点 ai的直接前趋 ai的直接后继 下标，是元素的 序号，表示元素 在表中的位置 n为元素总 个数，即表 长。n≥0 空表 线性终点
例1分析26个英文字母组成的英文表是什么结构。 (A, B,C, D Z 分析:数据元素都是同类型(字母),元素间关系是线性的。 例2分析学生情况登记表是什么结构。 学号 姓名性别年龄 班级 012003010622陈建武男 192003级电信0301班 012003010704赵玉凤女 182003级电信0302班 012003010813王泽男 19 2003级电信0303班 012003010906薛荃男 192003级电信0304班 012003011018王春男 192003级电信0305班 分析:数据元素都是同类型(记录),元素间关系是线性的。 注意:同一中的元必定具有同特性!
5 （ A, B, C, D, …… , Z） 学号 姓名 性别 年龄 班级 012003010622 陈建武 男 19 2003级电信0301班 012003010704 赵玉凤 女 18 2003级电信0302班 012003010813 王 泽 男 19 2003级电信0303班 012003010906 薛 荃 男 19 2003级电信0304班 012003011018 王 春 男 19 2003级电信0305班 ： ： ： ： ： 例2 分析学生情况登记表是什么结构。 分析：数据元素都是同类型（记录），元素间关系是线性的。 分析： 数据元素都是同类型（字母）， 元素间关系是线性的。 注意：同一线性表中的元素必定具有相同特性 ！ 例1 分析26 个英文字母组成的英文表是什么结构
2、线性表抽象数据类型 它包括两个方面: 数据集合:{apa1,…,,an1}:1的数据类型为 DataType 操作集合:(1) Listlnitiate(①)初始化线性表 (2) ListInsert(,x)插入数据元素 3) Listlength(L)求当前数据元素个数 (4) ListDelete(L,ix)删除数据元素 (5) Listgete(,x)取数据元素 等
6 ２、线性表抽象数据类型 它包括两个方面： 数据集合：｛ a0 , a1 , … , an-1 ｝ ai的数据类型为 DataType 操作集合：(1)ListInitiate(L) 初始化线性表 (2)ListInsert(L,i,x) 插入数据元素 (3)ListLength(L) 求当前数据元素个数 (4)ListDelete(L,i,x) 删除数据元素 (5)ListGet(L,i,x) 取数据元素 等
3、线性表的存储结构 (1)顺序存储结构:它是使用一片地址连续的有限内存单 元空间存储数据元素的一种计算机存储数据方法。 特点:(任意两个在逻辑上相邻的数据元素在物理位置 上也必然相邻)逻辑上相邻的元素,物理上也相邻。 (2)链式存储结构:它是把数据元素和指针定义成一个存 储体,使用指针把发生联系的数据元素链接起来的 一种计算机存储数据方法。 特点:任意两个在逻辑上相邻的数据元素在物理上不 一定相邻,数据元素的逻辑次序是通过链中的指针 链接实现的
7 3、线性表的存储结构 (1)顺序存储结构:它是使用一片地址连续的有限内存单 元空间存储数据元素的一种计算机存储数据方法。 特点：(任意两个在逻辑上相邻的数据元素在物理位置 上也必然相邻)逻辑上相邻的元素，物理上也相邻。 (2)链式存储结构:它是把数据元素和指针定义成一个存 储体，使用指针把发生联系的数据元素链接起来的 一种计算机存储数据方法。 特点：任意两个在逻辑上相邻的数据元素在物理上不 一定相邻，数据元素的逻辑次序是通过链中的指针 链接实现的
22线性表的顺序表示和实现 顺序表的存储结构 二、顺序表的实现 三、顺序表的运算效率分析
8 2.2 线性表的顺序表示和实现 一 、顺序表的存储结构 二、 顺序表的实现 三、 顺序表的运算效率分析
顺序表的存储结构表示 可以利用数组V[n来实现 1、顺序表:用一组地址连续的存储单元依次存儲线 性表的各个数据元素。即采用顺序存储结构的线性 表。它通常采用静态数组实现数据元素的存储。 注意:在C语言中数组的下标是从0开始,即: V[n]的有效范围是从V[0]~V[n-1]
9 一、 顺序表的存储结构表示 1、顺序表：用一组地址连续的存储单元依次存储线 性表的各个数据元素。即采用顺序存储结构的线性 表。它通常采用静态数组实现数据元素的存储。 可以利用数组V[n]来实现 注意：在C语言中数组的下标是从0开始，即： V[n]的有效范围是从 V[0]～V[n-1]
2、线性表顺序存储特点: (1)逻辑上相邻的数据元素,其物理上也相邻; (2)若已知表中首元素在存储器中的位置,则其他元 素存放位置亦可求出(利用数组V[m]的下标)。 设首元素a0的存放地址为LOC(a0)(称为首地址), 设每个元素占用存储空间(地址长度)为字节, 则表中任一数据元素的存放地址为 LOC (ai+1=LoC( ai)+L LoC( ai)=loc(a0)+L* 对上述公式的解释如图所示
10 (1) 逻辑上相邻的数据元素，其物理上也相邻； (2) 若已知表中首元素在存储器中的位置，则其他元 素存放位置亦可求出（利用数组V[n]的下标）。 设首元素a0的存放地址为LOC(a0 )（称为首地址）， 设每个元素占用存储空间（地址长度）为L字节， 则表中任一数据元素的存放地址为： LOC ( ai+1 ) = LOC( ai ) + L LOC ( ai ) = LOC( a0 ) + L *i 对上述公式的解释如图所示 2、线性表顺序存储特点：