数据结构线性表A.ppt

《数据结构线性表A.ppt》由会员分享，可在线阅读，更多相关《数据结构线性表A.ppt（54页珍藏版）》请在第壹文秘上搜索。

1、Recap: 数据结构的定位第二章：线性表1介于数学、计算机硬件和计算机软件三者之间的一门核心课程大数据时代的核心问题Recap: 什么是数据结构？第二章：线性表2问题分类：数值问题、非数值问题问题分类：数值问题、非数值问题 数 值 问 题数学方程 非数值问题数据结构数据结构学号学号姓名姓名性别性别出生日期出生日期二外二外10001王王 军军男男1993/09/02法语20003李李 明明男男1992/12/25西语Recap: 什么是数据结构？第二章：线性表3Data_Structure=（D, S）元素有限集关系有限集 相互之间存在一种或多种特定相互之间存在一种或多种特定关系关系的的数据元

2、素数据元素的集合，表示为：的集合，表示为：程序设计好算法好结构程序设计好算法好结构Recap: 基本概念第二章：线性表4数据数据 (data)：所有能所有能输入输入到计算机中并能被计算机程序到计算机中并能被计算机程序识别和识别和处理处理的符号集合。的符号集合。数据元素数据元素 (data element)：数据的数据的基本基本单位，在计算机程单位，在计算机程序中通常作为一个序中通常作为一个整体整体进行考虑和处理。进行考虑和处理。 数据项数据项 (data item)：构成数据元素的不可分割的最小单位。构成数据元素的不可分割的最小单位。三者之间的关系：三者之间的关系：数据数据 数据元素数据元素

3、数据项数据项Recap: 数据结构主要内容第二章：线性表5Recap: 逻辑结构第二章：线性表6集合结构集合结构： 仅同属一个集合线性结构线性结构: 一对一 (1:1) 树结构树结构: 一对多 (1:n) 图结构图结构: 多对多 (m:n)非线性线 性指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关与数据的存储无关，是，是独立于计算机独立于计算机的。的。Recap: 存储结构第二章：线性表7 数据元素之间的关系在计算机中通常有以二种不同的表示方法，对应二种不同的存储结构 顺序映象顺序映象 顺序存储结构 非顺序映象非顺序映象

4、 链式存储结构复数复数的两种存储方式：的两种存储方式：2.303023.0030003023.0030004152.3 地址地址 内容内容 地址地址 内容内容2字节字节2字节字节Recap:抽象数据类型的定义第二章：线性表8ADT = ADT = （D D，S S，P P） 数据对象数据对象 D D上的关系集上的关系集 D D上的操作集上的操作集 ADTADT抽象数据类型名抽象数据类型名 数据数据对象对象： 数据数据关系关系： 基本操作基本操作 ： ADTADT抽象数据类型名抽象数据类型名第二章：线性表9Recap:抽象数据类型定义定义并实现定义并实现复数抽象数据类型复数抽象数据类型（定义定义

5、）ADT ComplexADT Complex 数据对象：数据对象：D = c1, c2 | c1, c2 D = c1, c2 | c1, c2 R(R R(R为实数集）为实数集） 数据关系：数据关系：S = S = （ c1 c1为实部，为实部，c2c2为虚部）为虚部） 基本操作：基本操作： void Assign(void Assign(* *A, c1, c2A, c1, c2） void Add( void Add(* *A, B)A, B) void Minus( void Minus(* *A, B)A, B) void Multiply( void Multiply(* *A,

6、 B)A, B) void Divide( void Divide(* *A, B)A, B).ADT ComplexADT ComplexRecap:抽象数据类型定义第二章：线性表10定义并实现定义并实现复数抽象数据类型复数抽象数据类型（实现实现/ /类类C C描述描述） typedeftypedef ItemTypeItemTypedouble;double;typedeftypedef structstruct ItemTypeItemTyper ;r ;ItemTypeItemTypev;v;Complex;Complex;/ /* * 复数抽象数据类型复数抽象数据类型 * */ /v

7、oid Assign(Complex void Assign(Complex * *A, A, ItemTypeItemType r, r, ItemTypeItemType v); v); void Add(Complex void Add(Complex * *A, Complex B);A, Complex B);/ /* * A+B A+B * */ /void Minus(Complex void Minus(Complex * *A, Complex B);A, Complex B);/ /* * A-B A-B * */ /void Multiply(void Multiply(

8、CompexCompex * *A, Complex B); /A, Complex B); /* * A A* *B B * */ /void Divide(Complex void Divide(Complex * *A, Complex B);A, Complex B);/ /* * A/B A/B * */ /.Recap:算法分析第二章：线性表11 正确性正确性 时间代价时间代价(时间复杂度时间复杂度) 空间代价空间代价 (空间复杂度空间复杂度) 最优性最优性Recap: 算法效率度量第二章：线性表12O： 当且仅当存在一个正的常数当且仅当存在一个正的常数 C，使得对所有使得对所有的

9、的 n n0 ，有有 f(n) Cg(n)，则则 f(n) = O(g(n)100n+6=O(n) /* 100n+6 101n for n 6 */10n2+4n+2=O(n2) /* 10n2+4n+2 11n2 for n 5 */6*2n+n2=O(2n) /* 6*2n+n2 7*2n for n 4 */面试: 顺序存储还是链式存储？第二章：线性表13学号学号姓名姓名性别性别出生日期出生日期二外二外10001王王 军军男男1993/09/02法语20003李李 明明男男1992/12/25西语反问：操作是什么？14第第1章章 绪论绪论第第2章章 线性表线性表第第3章章 栈和队列栈和

10、队列 第第4章章 串串第第5章章 数组和广义表数组和广义表第第6 6章章 树和二叉树树和二叉树 第第7章章 图图第第9章章 查找查找第第10章章 排序排序目目 录录第二章：线性表什么是什么是线性结构？线性结构？15第二章：线性表16线性结构的定义：线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。接后继。 可表示为：（可表示为：（a a1 1 , a, a2 2 , , , a, an n） 简言之，线性结构反映结点间的逻

11、辑关系是简言之，线性结构反映结点间的逻辑关系是 的。的。特点特点 只有一个首结点和尾结点；只有一个首结点和尾结点；特点特点 除首尾结点外，其他结点只有一个直接前驱和一个除首尾结点外，其他结点只有一个直接前驱和一个直接后继。直接后继。线性结构包括：线性结构包括：线性表、堆栈、队列、字符串、数组线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是等，其中最典型、最常用的是-一对一一对一 (1:1)第二章：线性表17第二章：线性表18（a1, a2, ai-1，ai, ai1 ，, an）2.1 线性表的逻辑结构线性表的逻辑结构 用数据元素的有限序列表示用数据元素的有限序列表示n=0时称为时称

12、为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表个数，即表长。长。空表空表线性终点线性终点2.1 线性表的逻辑结构19 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级U200713569李春元李春元男男19通信工程通信工程200701班班U200713611李煜墉李煜墉男男19通信工程通信工程200701班班U200713537张祺轩张祺轩男男19通信工程通信工程200702班班： ：例例2 分析学生情况登记表是什么结构。分

13、析学生情况登记表是什么结构。分析：分析：数据元素都是同类型（数据元素都是同类型（记录记录），元素间关系是线性的。），元素间关系是线性的。分析：分析： 数据元素都是同类型（数据元素都是同类型（字母字母），）， 元素间关系是线性的。元素间关系是线性的。例例1 分析分析26 个英文字母组成的英文表是什么结构。个英文字母组成的英文表是什么结构。2.1 线性表的逻辑结构20“同一数据逻辑结构中的所有数据元素都具有相同的特性同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。是指数据元素所包含的数据项的个数都相等。试判断下列叙述的正误：试判断下列叙述的正误：2.1 线

14、性表的逻辑结构212.2.1 顺序表的表示顺序表的表示用一组用一组地址连续地址连续的存储单元依次的存储单元依次存储线性表的元素。存储线性表的元素。把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。理上相邻的存储单元中的存储结构。线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或顺序映像。或顺序映像。顺序存储定义：顺序存储定义：顺序存储方法：顺序存储方法：特点：特点：逻辑上相邻的元素，物理上也相邻逻辑上相邻的元素，物理上也相邻可以利用可以利用数组数组VnVn来实现来实现注意：在注意：在C C语言中数组的下标是从语言中数组的下标是从0

15、0开始，即：开始，即： VVn n 的有效范围是从的有效范围是从 VV0 0 VVn-1n-1 2.2.1 顺序表的表示221. 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；2. 若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出素存放位置亦可求出（利用数组利用数组VnVn的的下标下标）。）。设首元素设首元素a1的存放地址为的存放地址为LOC(a1)（称为称为首地址首地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址

16、存放地址为：为： LOC ( ai+1 ) = LOC( ai ) + L 对上述公式的解释如图所示对上述公式的解释如图所示线性表顺序存储特点：线性表顺序存储特点：2.2.1 顺序表的表示23a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 内容内容 元素在表中的位序元素在表中的位序1 1i i2 2n n空闲区空闲区i+1i+1Lb=LOC(a1)b + + L Lb +(i-1)+(i-1)L Lb +(n-1)+(n-1)L Lb +(max-1)+(max-1)L L线性表的顺序存储结构示意图线性表的顺序存储结构示意图下标起下标起点是点是1 12.2.1 顺序表的表示24设有一维数组设有一维数组，下标的范围是，下标的范围是到到，每个数，每个数组元素用相邻的组元素用相邻的个字节个字节存储。存储器按字节编址，存储。存储器按字节编址，设存储数组元素设存储数组元素 的第一个字节的地址是的第一个字节的地址是9898，则，则 的第一个字节的地址是多少？的第一个字节的地址是多少？答案：答案：113但此题要注意下标起点是从但此题要注意下标起点是从0 0开始：开始：L