《数据结构》课程PPT教学课件（2012）第2章 线性表 2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现

目大录 第1章 绪论 第2章 线性表 3章 栈和队列 4章 串 数组和广义表 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序 1

1 第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序 目 录

数据结构课程的起点： 线性结构 (线性表、找、队、串、数组) 逻辑结构 树结构 非线性结构 图结构 颜序结构 什么是 链式结构 线性结构 数据结构：】 物理（存储)结构 索引结构 散列结构 插入运算 翻除运算 数据运算 修改运算 查找运算 排序运算

数据结构课程的起点： 什么是 线性结构？

线性结构的定义： 若结构是非空有限集，则有且仅有一个开始结点和一个 终端结点，并且所有结点都最多只有←个直接前趋和一个直 接后继。→可表示为：(a1,a2 an) 特点①只有一个首结点和尾结点： 特点②除首尾结点外，其他结点只有一个直接前驱和一个直 接后继。 简言之，线性结构反映结点间的逻辑关系是一对二(1：1)的。 线性结构包括：线性表、堆栈、队列、字符串、数组 等，其中最典型、最常用的是-”线性表 0

3 线性结构的定义： 若结构是非空有限集，则有且仅有一个开始结点和一个 终端结点，并且所有结点都最多只有一个直接前趋和一个直 接后继。 →可表示为：（a1 , a2 , ., an） 简言之，线性结构反映结点间的逻辑关系是 的。 特点① 只有一个首结点和尾结点； 特点② 除首尾结点外，其他结点只有一个直接前驱和一个直 接后继。 线性结构包括：线性表、堆栈、队列、字符串、数组 等，其中最典型、最常用的是- 线性表 一对一 (1:1)

第2章线性表 2.1线性表的逻辑结构 2.2线性表的顺序表示和实现 2.3线性表的链式表示和实现 2.4应用举例

4 第2章 线性表 2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 应用举例

2.1线性表的逻辑结构 线性表的定义：用数据元素的有限序列表示 a,3a1.70 数据元素 线性起点 a的直接前趋a的直接后继 线性终点 n为元素总 下标，是元素的 序号，表示元素 n=0时称为 空表 个数，即表 在表中的位置 长。n≥0

5 （a1 , a2 , . ai-1， ai , ai＋1 ，., an） 2.1 线性表的逻辑结构 线性表的定义：用数据元素的有限序列表示 n=0时称为 数据元素 线性起点 ai的直接前趋 ai的直接后继 下标，是元素的 序号，表示元素 在表中的位置 n为元素总 个数，即表 长。n≥0 空表 线性终点

例1分析26个英文字母组成的英文表是什么结构。 (A,B,C,D,.,Z) 分析：数据元素都是同类型（字母） 元素间关系是线性的。 例2分析学生情况登记表是什么结构。 学号 姓名 性别 年龄 班级 012007010622 陈建武 男 19 2007级计科0301班 012007010704 赵玉凤 女 18 2007级计科0302班 012007010813 王泽 男 19 2007级计科0303班 012007010906 薛荃 男 19 2007级计科0304班 012007011018 王春 男 19 2007级计科0305班 分析：数据元素都是同类型（记录），元素间关系是线性的

6 （ A, B, C, D, . , Z） 学号 姓名 性别 年龄 班级 012007010622 陈建武 男 19 2007级计科0301班 012007010704 赵玉凤 女 18 2007级计科0302班 012007010813 王 泽 男 19 2007级计科0303班 012007010906 薛 荃 男 19 2007级计科0304班 012007011018 王 春 男 19 2007级计科0305班 ： ： ： ： ： 例2 分析学生情况登记表是什么结构。 分析：数据元素都是同类型（记录），元素间关系是线性的。 分析： 数据元素都是同类型（字母）， 元素间关系是线性的。 例1 分析26 个英文字母组成的英文表是什么结构

2.2线性表的顺序表示和实现 2.2.1 顺序表的表示 2.2.2 顺序表的实现 2.2.3 顺序表的运算效率分析 7

7 2.2 线性表的顺序表示和实现 2.2.1 顺序表的表示 2.2.2 顺序表的实现 2.2.3 顺序表的运算效率分析

2.2.1 顺序表的表示 线性表的顺序表示又称为顺序存储结构或顺序映像。 顺序存储定义：把逻辑上相邻的数据元素存储在物 理上相邻的存储单元中的存储结构。 特点：逻辑上相邻的元素，物理上也相邻 顺序存储方法：用一组地址连续的存储单元依次 存储线性表的元素。 可以利用数组V[n]来实现 注意：在C语言中数组的下标是从0开始，即： V[n]的有效范围是从V[0]~V[n-1] 8

8 2.2.1 顺序表的表示 用一组地址连续的存储单元依次 存储线性表的元素。 把逻辑上相邻的数据元素存储在物 理上相邻的存储单元中的存储结构。 线性表的顺序表示又称为顺序存储结构或顺序映像。 顺序存储定义： 顺序存储方法： 特点：逻辑上相邻的元素，物理上也相邻 可以利用数组V[n]来实现 注意：在C语言中数组的下标是从0开始，即： V[n]的有效范围是从 V[0]～V[n-1]

线性表顺序存储特点： 1.逻辑上相邻的数据元素，其物理上也相邻 2.若已知表中首元素在存储器中的位置，则其他元 素存放位置亦可求出（利用数组V[n]的下标）。 设首元素a的存放地址为OC(a)(称为首地址)， 设每个元素占用存储空间（地址长度）为L字节 则表中任一数据元素的存放地址为： LOC (a)=LOC()+L L0C(a;)=L0C(a1)+L*(i-1) 对上述公式的解释如图所示 9

9 1. 逻辑上相邻的数据元素，其物理上也相邻； 2. 若已知表中首元素在存储器中的位置，则其他元 素存放位置亦可求出（利用数组V[n]的下标）。 设首元素a1的存放地址为LOC(a1 )（称为首地址）， 设每个元素占用存储空间（地址长度）为L字节， 则表中任一数据元素的存放地址为： LOC ( ai+1 ) = LOC( ai ) + L LOC ( ai ) = LOC( a1 ) + L *（i -1） 对上述公式的解释如图所示 线性表顺序存储特点：

线性表的顺序存储结构示意图 地址 内容 元素在表中的位序 b=LOC(a) ar 1 b+L a2 。中●。 b+(i-1)L ai ai+1 i+1 .o. b+(n-1)L an 空闲区 b +(max- L0C(a)=L0C(a1)+L*(i-1) 10

10 a1 a2 . ai ai+1 . an 地址 内容 元素在表中的位序 1 i 2 n 空闲区 i+1 b=LOC(a1 ) L b + L b +(i-1)L b +(n-1)L b +(max- 1)L LOC ( ai ) = LOC( a1 ) + L *（i -1） 线性表的顺序存储结构示意图