第8讲数组、广义表讲述.ppt

回顾 数据、数据元素、数据对象、数据结构及其种类、抽象数据类型 算法及其特性，算法的描述，算法效率的度量 线性表及其特点，线性表的顺序表示和链式表示 栈的逻辑结构与存储，递归，栈的应用 队列的逻辑结构与存储 串及其模式匹配 第八讲 数组与广义表 主讲： 朱郑州 主要内容 主要内容 主要内容 主要内容 A ＝( ) B ＝(e) C ＝(a, (b，c，d)) D ＝(A, B, C) E ＝(a, E) F ＝(( )) A ＝( ) B ＝(e) C ＝(a, (b，c，d)) D ＝(A, B, C) E ＝(a, E) F ＝(( )) A ＝( ) B ＝(e) C ＝(a, (b，c，d)) A ＝( ) B ＝(e) C ＝(a, (b，c，d)) D ＝(A, B, C) E ＝(a, E) F ＝(( )) 2.数组的存储方式及寻址方法 1.数组的逻辑结构特征 3.矩阵的压缩存储方法 4.广义表的基本概念和存储结构 广义表：n（n≥0）个数据元素的有限序列，记作： LS＝(a1，a2，……，an) 其中：LS是广义表的名称，ai（1≤i≤n）是LS的成员（或直接元素），它可以是单个的数据元素，也可以是一个广义表，分别称为LS的单元素（或原子）和子表。 广义线性表——广义表 广义表的逻辑结构：直接元素之间是线性关系。 广义表的基本概念 通常用大写字母表示广义表，用小写字母表示单元素。 长度：广义表LS中的直接元素的个数； 深度：广义表LS中括号的最大嵌套层数。 表头：广义表LS非空时，称第一个元素为LS的表头； 表尾：广义表LS中除表头外其余元素组成的广义表。 广义线性表——广义表 广义表( )和广义表(( ))不同？ 广义表的基本概念 广义线性表——广义表 广义表的示例 长度？深度？表头？表尾？ 广义线性表——广义表 广义表的图形表示 A B e C a b c d D 广义线性表——广义表 广义表可以采用顺序存储结构吗？ 由于广义表中的数据元素的类型不统一，因此难以采用顺序存储结构来存储。 若广义表不空，则可分解为表头和表尾；反之，一对确定的表头和表尾可唯一地确定一个广义表。 采用头尾表示法存储广义表 如何采用链接存储结构存储广义表？ 广义表的存储结构——头尾表示法 广义线性表——广义表 广义表中的数据元素既可以是广义表也可以是单元素 头尾表示法中的结点结构？ 表结点——存储广义表；元素结点——存储单元素 tag=1 hp tp tag=0 data 表结点 元素结点 tag：区分表结点和元素结点的标志； hp：指向表头结点的指针； tp：指向表尾结点的指针； data：数据域，存放单元素。 广义表的存储结构——头尾表示法 广义线性表——广义表 结点结构 enum Elemtag {Atom, List}; struct GLNode { Elemtag tag; union { T data; struct { struct GLNode *hp, *tp; } ptr; }; }; 广义线性表——广义表 广义表的存储结构——头尾表示法 定义结点结构 tag=1 hp tp tag=0 data 广义线性表——广义表 广义表的存储结构——头尾表示法 NULL A 1 B 0 e ∧ 1 C 0 a ∧ 1 1 0 b 1 0 c ∧ 1 0 d 广义线性表——广义表 广义表的存储结构——头尾表示法 1 B 0 e ∧ 1 C 0 a ∧ 1 1 0 b 1 0 c ∧ 1 0 d 1 D ∧ 1 1 ∧ 稀疏矩阵的压缩存储 15 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 0 0 0 0 0 A= 如何只存储非零元素？ 矩阵的压缩存储 注意：稀疏矩阵中的非零元素的分布没有规律。 struct element { int row, col; //行号，列号 T item //非零元素值 }; 将稀疏矩阵中的每个非零元素表示为： (行号，列号，非零元素值)