数组和广义表

数组和广义表Tag内容描述：<p>1、第五章数组和广义表,数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表5.1数组的定义和特点定义,数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值,5.2数组的顺序存储结构次序约定以行序为主序以列序为主序,5.3矩阵的压缩存储对称矩阵,三角矩阵,对角矩阵,Loc(aij)=Loc(a11)+2(i-1)+(j-1),M由。</p><p>2、第五章数组和广义表 n教学目的 n通过本章的学习，要求学生了解数组及广义 表的定义，掌握数组的存储结构 n5.1 数组的定义 n5.2 数组的顺序表示和实现 n5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 n重点：数组的两种存储表示方式及元素存储 地址的计算公式；特殊矩阵和稀疏矩阵的压 缩存储方法； n难点：特殊矩阵和稀疏矩阵的压缩存储方法 及运算的实现。 n数组可看成是一种特殊的线性表，其特殊在于，表中的 数据元素本身也是一种线性表。 5.1 数组的定义 数组是我们最熟悉的数据类型，在早期的高级语言 中，数组是唯一可供使用的。</p><p>3、1 第 第5 5 章章 数数组组和和广广义义表表 5.1 5.1 数组的逻辑结构数组的逻辑结构 5.2 5.2 数组的顺序存储结构数组的顺序存储结构 5.3 5.3 矩阵的压缩存储矩阵的压缩存储 5.4 5.4 广义表广义表 5.15.1 数组的逻辑结构数组的逻辑结构 5.25.2 数组的顺序存储结构数组的顺序存储结构 5.35.3 矩阵的压缩存储矩阵的压缩存储 5.45.4 广义表广义表 数组数组 ( (array) array) 是最常用的数据结构之一。几乎所有是最常用的数据结构之一。几乎所有 的程序设计语言都把数组类型设定为固有类型。的程序设计语言都把数组类型设定为固有类型。 数组的。</p><p>4、数据结构 Data Structures 长江大学计算机科学学院 第五章 数组和广义表 F本章内容 5.1 数组的定义 5.2 数组的顺序表示 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构 数据结构 Data Structures 长江大学计算机科学学院 5.1数组的定义 v数组是我们很熟悉的一种数据结构，它可以看 作线性表的推广。数组作为一种数据结构其特 点是结构中的元素本身可以是具有某种结构的 数据，但属于同一数据类型，比如：一维数组 可以看作一个线性表，二维数组可以看作“数 据元素是一维数组”的一维数组，三。</p><p>5、1,第五章数组和广义表,2,作为抽象数据类型的数组,一维数组一维数组的示例,5.1数组的定义,3,一维数组的特点,连续存储的线性聚集（别名向量）除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。,4,数组的定义和初始化,#includeclassszclinte;public:szcl()e=0;szcl(intvalue。</p><p>6、第5章 数组和广义表,5.1 数组的定义和运算 5.2 数组的顺序存储和实现 5.3 特殊矩阵的压缩存储 5.3.1 三角矩阵 5.3.2 带状矩阵 5.3.3 稀疏矩阵 5.4 广义表,返回主目录,5.1 数组的定义和运算,数组是一种数据类型。从逻辑结构上看，数组可以看成是一般线性表的扩充。二维数组可以看成是线性表的线性表。例如：,返回主目录,我们可以把二维数组看成一个线性表： A=( 1 2 j n)，其中j（1j n）本身也是一个线性表，称为列向量。,矩阵Amn看成n个列向量的线性表,即j=(a1j,a2j, ,amj),返回主目录,我们还可以将数组Amn看成另外一个线性表: B=(1，,2,。</p><p>7、5.1 数组的基本概念 5.2 稀疏矩阵的三元组存储 5.3 稀疏矩阵的十字链表存储 5.4 广义表 5.5 迷宫问题,第5章 数组和广义表,返回主目录,第5章数组和广义表,5.1 数组的基本概念 5.1.1 数组的概念 数组是相同类型的数据有序的组合, 数组中的每一个数据通常称为数组元素, 数组元素用下标识别, 下标的个数取决于数组的维数。例如, 一个形式如式（5.1）的m*n阶矩阵是个二维数组, 其中的每个元素都可用下标变量aij来表示, i为元素的行下标, j为元素的列下标:,Amn=,a11 a12 a1n a21 a22 a2n am1 am2 amn (1im, 1jn),类似于线性表, 一个二维数组的逻。</p><p>8、第5章 数组和广义表,5.1 数组的定义和运算 5.2 数组的顺序存储和实现 5.3 特殊矩阵的压缩存储 5.3.1 三角矩阵 5.3.2 带状矩阵 5.3.3 稀疏矩阵 5.4 广义表,5.1 数组的定义和运算,数组是一种数据类型。从逻辑结构上看，数组可以看成是一般线性表的扩充。二维数组可以看成是线性表的线性表。例如：,我们可以把二维数组看成一个线性表： A=( 1 2 j n)，其中j（1j n）本身也是一个线性表，称为列向量。,矩阵Amn看成n个列向量的线性表,即j=(a1j,a2j, ,amj),我们还可以将数组Amn看成另外一个线性表: B=(1，,2,， ，m)，其中i（1i m）本身也是一个。</p><p>9、第5章 数组和广义表,5.1 数组的定义与运算 5.2 数组的顺序存储结构 5.3 矩阵的压缩存储 5.4 广义表 习题,5.1 数组的定义与运算,数组定义：类似于线性表，一个两维数组的逻辑结构可形式地表示为 2_Array=(D,R) 其中D=aij|i=0,1,m-1,j=0,1,n-1，aij是同类型数据元素的集合。 R=ROW,COL是数据元素上关系的集合。 ROW=|0im-1,0jn-2每一行上的列关系。 COL=|0im-2,0jn-1每一个列上的行关系。 行列关系跟线性表已经大不相同了,见图5.1所示。,a01 a02 a0n-1 a11 a12 a1n-1 am-11 am-12 am-1n-1 图5.1 二维数组元素关系 二维数组中的每一个元素aij。</p><p>10、数据结构 第五章 数组与广义表,本章内容 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构,5-3,数组和广义表可看成是一种特殊的线性表。表中的元素本身也是一种数据结构。 数组的的数据元素是数组；广义表的数据元素可以是原子类型，也可以是广义表，分别称为广义表的原子项和子表,数组和广义表简单描述,5-4,数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组。</p><p>11、第五章 数组和广义表重点难点理解数组和广义表两种数据结构的特点，并掌握数组在以行为主的存储表示中的地址计算方法；掌握特殊矩阵的存储压缩表示方法；了解广义表的两种链式存储结构。典型例题 1. 设有三对角矩阵 An*n，将其三条对角线上的元素逐行地存储到向量B0.3n-3中，使得Bk=aij,求：(1)用i , j 表示k的下标变换公式。(2)用 k 表示 i,j 的下标变换公式。【解】(1)要求i,j 到k 的下标变换公式，就是要知道在k之前已有几个非零元素，这些非零元素的个数就是k的值，一个元素所在行为i,所在列为j,则在其前面已有的非零元素个数为：(i*3。</p><p>12、第五章 数组,5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义与存储,5.1 数组的定义,维数和维界 二维数组的类型定义: 等价于 typedef ElemType Array1n; typedef Array1 Array2m; typedef ElemType Array2mn; Array2 A; 二维的数组 = 定长的线性表 a11 a12 a13 . a1n a21 a22 a23 . a2n Amxn= am1 am2 am3 . amn Amxn= (a11,a12,a13,.a1n),(a21,a22,a23,.a2n),.,(am1,am2,am3,.amn),数组的抽象数据类型,ADT Array 数据对象：D = aj1j2.jn | n(0)称为数组的维数,bi是数组第i。</p><p>13、第五章数组和广义表,5.1数组的类型定义,5.3矩阵的压缩存储,5.2数组的顺序表示和实现,5.4广义表的类型定义,5.5广义表的存储结构,学习提要：1.了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。2.掌握对特殊矩阵进行压缩存储时的下标变换公式。3.了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。4.掌握广义表的。</p><p>14、第 4 章 广义线性表多维数组和广义表 课后习题讲解 1. 填空 数组通常只有两种运算：（ ）和（ ），这决定了数组通常采用（ ）结构来实现存储。【解答】存取，修改，顺序存储【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。 二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A105的存储地址是1000，则元素A1510的存储地址是（ ）。【解答】1140【分析】数组A中每行共有6个元素，元素A1510的前面共。</p><p>15、5.1 数组的类型定义,5.3 稀疏矩阵的压缩存储,5.2 数组的顺序表示和实现,5.4 广义表的类型定义,5.5 广义表的表示方法,5.6 广义表操作的递归函数,5.1 数组的类型定义,ADT Array 数据对象： Daj1,j2, .,ji,jn| ji =0,.,bi -1, i=1,2,n 数据关系： RR1, R2, ., Rn Ri | 0 jk bk -1, 1 k n 且k i, 0 ji bi -2, i=2,.,n ADT Array,基本操作:,二维数组的定义:,数据对象: D = aij | 0ib1-1, 0 jb2-1 数据关系: R = ROW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2,基本操作：,InitArray(&A, n, bound1, ., boundn),DestroyArray(&A),Val。</p><p>16、1,第四章 数组、串与广义表,一维数组与多维数组 特殊矩阵 稀疏矩阵 字符串 广义表,2,一维数组,定义 数组是相同类型的数据元素的集合，而一维数组的每个数组元素是一个序对，由下标（index）和值（value）组成。 一维数组的示例 在高级语言中，一维数组只能按元素的下标直接存取数组元素的值。,3,一维数组的定义和初始化,#include main ( ) int a3 = 3, 5, 7 , *elem, i; /静态数组 for (i = 0; i elemi; while (elem) cout *elem endl; elem+; ,4,多维数组,多维数组是一维数组的推广。 多维数组的特点是每一个数据元素可以有多个直接前驱。</p><p>17、第五章 数组与广义表,5.1 数组的定义 5.2 数组的顺序表现和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构 5.6 广义表的递归算法,5.1 数组的定义,数组：按一定格式排列起来的一列同一属性的项目,是相同类型的数据元素的集合。有一维数组A5、二维数组A55、三维数组A555、多维数组等。 二维数组：每一行都是一个线性表，每一个数据元素既在一个行表中，又在一个列表中。,2,5.2 数组的顺序表现和实现,二维数组以行为主的顺序存储 Loc(aij)=Loc(a11)+(i-1)n+(j-1)*L 其中 L=sizeof(datatype),3,2. 二维数组以列为主的顺序存。</p>