《广义表总结》由会员分享，可在线阅读，更多相关《广义表总结（164页珍藏版）》请在金锄头文库上搜索。
1、增长型发展策略与集团公司手机上网意见PPT培训课件关于大数据时代的大数据产品解析思考PPT培训课件婴儿喂养母乳缺点课件理疗仪器操作说明 第五章 数组和广义表本章主要介绍数组的概念及在计算机中的存放，特殊矩阵 的压缩存储及相应运算，广义表的概念和存储结构及其相 关运算的实现。通过本章学习，要求掌握如下内容: 1数组的定义及在计算机中的存储表示； 2对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机 中的压缩存储表示及地址计算公式； 3稀疏矩阵的三元组表示； 4广义表存储结构表示。【知识点】数组的类型定义、数组的存储表示、特殊矩阵 的压缩存储表示方法、稀疏矩阵的压缩存储表示方法5.1 数组的基本概念
2、5.2 数组的存储结构 5.3 特殊矩阵及其压缩存储 5.4 稀疏矩阵5.5 广义表 5.6 小结 5.7 练习增长型发展策略与集团公司手机上网意见PPT培训课件关于大数据时代的大数据产品解析思考PPT培训课件婴儿喂养母乳缺点课件理疗仪器操作说明5.1 数组的基本概念 一、数组的定义 数组是大家都已经很熟悉的一种数据类型，几乎所有高 级语言程序设计中都设定了数组类型。 数组（Array）：是由一组类型相同的数据元素构成的有 限序列，且该有限序列存储在一块地址连续的内存单元 中。数据元素可以是整数、实数等简单类型，也可以是 数组等构造类型。数据元素在数组中的相对位置是由其 下标来确定的。 1一维
3、数组 若数组只有一个下标，这样的数组称为一维数组。一维 数组可以看成是一个线性表或一个向量，它在计算机内 是存放在一块连续的存储单元中，适合于随机查找。这 在第2章的线性表的顺序存储结构中已经介绍。增长型发展策略与集团公司手机上网意见PPT培训课件关于大数据时代的大数据产品解析思考PPT培训课件婴儿喂养母乳缺点课件理疗仪器操作说明2二维数组 二维数组可以看成是向量的推 广，即当一个数组的每一个数 组元素都含有两个下标时，该 数组称为二维数组。例如，设 A是一个有m行n列的二维数组 ，则A可以表示为：在此，可以将二维数组看成一个 线性表：A=（0， 1， ，p) (p=m-1或n-1)。其中，每
4、个数据 元素j是一个列向量形式的线性 表j = (a0j, a1j, ,am-1j)，0jn-1 ；或者j是一个行向量形式的线 性表 i=(ai0, ai1, .,ain-1)， 0im -1 。由此可知二维数组中的每一个元素最多可有两个直接前驱和两个直 接后继（边界除外），故是一种典型的非线性结构。增长型发展策略与集团公司手机上网意见PPT培训课件关于大数据时代的大数据产品解析思考PPT培训课件婴儿喂养母乳缺点课件理疗仪器操作说明二、数组的4个性质：1.数组中的数据元素数目固定。一旦定义了一个数组 ，它的维数和维界就不能再改变，只能对数组进行 存取元素和修改元素值的操作了。2.数组中的数据元
5、素具有相同的数据类型。3.数组中的每个数据元素都和一组唯一的下标值对应 。4.数组是一种随机存储结构，可随机存取数组中的任 意数据元素。增长型发展策略与集团公司手机上网意见PPT培训课件关于大数据时代的大数据产品解析思考PPT培训课件婴儿喂养母乳缺点课件理疗仪器操作说明 5.2 数组的存储结构 由于数组一般不作插入或删除操作，也就是说，一旦建 立了数组，则结构中的数组元素个数和元素之间的关系 就不再发生变动，即它们的逻辑结构就固定下来了，不 再发生变化。因此，采用顺序存储结构表示数组是顺理 成章的事了。 数组的顺序存储结构：数组元素顺序地存放在一片连续 的存储单元中。 数组的顺序存储有两种形式
6、：以列序为主序的存储方式 和以行序为主序的存储方式。增长型发展策略与集团公司手机上网意见PPT培训课件关于大数据时代的大数据产品解析思考PPT培训课件婴儿喂养母乳缺点课件理疗仪器操作说明 一、行优先顺序（以行序为主序的存储方式）： 1存放规则 行优先顺序也称为低下标优先或左边下标优先于右边下标 。具体实现时，按行号从小到大的顺序，先将第一行中元 素全部存放好，再存放第二行元素，第三行元素，依次类 推 在BASIC语言、PASCAL语言、C/C+语言等高级语言程序设 计中，都是按行优先顺序存放的。例如，对刚才的Amn二 维数组，可用如下形式存放到内存：a00，a01,a0n-1，a10 ，a11
7、，.， a1 n-1，am-1 0 ， am-1 1，am-1 n-1。即 二维数组按行优先存放到内存后，变成了一个线性序列（ 线性表）。 因此，可以得出多维数组按行优先存放到内存的规律：最 左边下标变化最慢，最右边下标变化最快，右边下标变化 一遍，与之相邻的左边下标才变化一次。因此，在算法中 ，最左边下标可以看成是外循环，最右边下标可以看成是 最内循环。增长型发展策略与集团公司手机上网意见PPT培训课件关于大数据时代的大数据产品解析思考PPT培训课件婴儿喂养母乳缺点课件理疗仪器操作说明2地址计算 由于多维数组在内存中排列成一个线性序列，因此，若知 道第一个元素的内存地址，如何求得其他元素的内
8、存地址 ？我们可以将它们的地址排列看成是一个等差数列，假设 每个元素占L个字节，元素aij 的存储地址应为第一个元素 的地址加上排在aij 前面的元素所占用的单元数，而aij 的前 面有i行(0i-1)共in个元素，而本行前面又有j个元素，故 aij的前面一共有in+j个元素，设a00的内存地址为LOC(a00) ，则aij的内存地址按等差数列计算为LOC(aij)=LOC(a00)+（ in+j）L。同理，三维数组Amnp按行优先存放的地址计 算公式为：LOC(aijk)=LOC(a000)+(inp+jp+k)L。增长型发展策略与集团公司手机上网意见PPT培训课件关于大数据时代的大数据产品
9、解析思考PPT培训课件婴儿喂养母乳缺点课件理疗仪器操作说明增长型发展策略与集团公司手机上网意见PPT培训课件关于大数据时代的大数据产品解析思考PPT培训课件婴儿喂养母乳缺点课件理疗仪器操作说明 二、列优先顺序（以列序为主序的存储方式）： 1存放规则 列优先顺序也称为高下标优先或右边下标优先于左边下标。具体实现 时，按列号从小到大的顺序，先将第一列中元素全部存放好，再存放 第二列元素，第三列元素，依次类推 在FORTRAN语言程序设计中，数组是按列优先顺序存放的。例如， 对前面提到的Amn二维数组，可以按如下的形式存放到内存：a00， a10， am-10， a01，a11， ， am-1 1，
10、 a0 m-1，a1m-1，.， am-1 n-1 。 即二维数组按列优先存放到内存后，也变成了一个线性序列（线性 表）。 因此，可以得出多维数组按列优先存放到内存的规律：最右边下标变 化最慢，最左边下标变化最快，左边下标变化一遍，与之相邻的右边 下标才变化一次。因此，在算法中，最右边下标可以看成是外循环， 最左边下标可以看成是最内循环。 2地址计算 同样与行优先存放类似，若知道第一个元素的内存地址，则同样可以 求得按列优存放的某一元素aij的地址。 对二维数组有：LOC(aij)=LOC(a00)+(jm+i)L 对三维数组有： LOC(aijk)=LOC(a000)+(kmn+jm+i)L
11、增长型发展策略与集团公司手机上网意见PPT培训课件关于大数据时代的大数据产品解析思考PPT培训课件婴儿喂养母乳缺点课件理疗仪器操作说明增长型发展策略与集团公司手机上网意见PPT培训课件关于大数据时代的大数据产品解析思考PPT培训课件婴儿喂养母乳缺点课件理疗仪器操作说明 三、数组的顺序存储表示和实现的算法/*stdarg.h为标准头文件*/ #include #define MAXDIM 10 /徦设数组维数最大值为10 typedef struct ElemType *base;/数组元素初始地址 intdim;/数组的维数 int*bounds;/数组各维的长度 int *constants
12、; /数组的初始地址 Array; 增长型发展策略与集团公司手机上网意见PPT培训课件关于大数据时代的大数据产品解析思考PPT培训课件婴儿喂养母乳缺点课件理疗仪器操作说明 基本操作：InitArray( /*非零元行、列号*/ ElemType e; /*非零元值*/ Triple; typedef struct /*定义稀疏矩阵*/ int rows,cols ; /*稀疏矩阵行、列数*/ int terms; /*稀疏矩阵非零元个数*/ triple data maxsize; /*三元组表*/ Tabletype;增长型发展策略与集团公司手机上网意见PPT培训课件关于大数据时代的大数据产
13、品解析思考PPT培训课件婴儿喂养母乳缺点课件理疗仪器操作说明三元组:(0,1,12),(0,2,9),(2,0,- 3),(2,5,14),(3,2,24), (4,1,18),(5,0,15),(5,3,-7) 增长型发展策略与集团公司手机上网意见PPT培训课件关于大数据时代的大数据产品解析思考PPT培训课件婴儿喂养母乳缺点课件理疗仪器操作说明 2带行指针的链表 把具有相同行号的非零元用一个单链表连接起来，稀疏矩 阵中的若干行组成若干个单链表，合起来称为带行指针的 链表。例如，上图的稀疏矩阵M的带行指针的链表描述形 式见下图所示。增长型发展策略与集团公司手机上网意见PPT培训课件关于大数据时
14、代的大数据产品解析思考PPT培训课件婴儿喂养母乳缺点课件理疗仪器操作说明5.5 广义表一、 基本概念 广义表是第2章提到的线性表的推广。线性表中的元素仅 限于原子项，即不可以再分，而广义表中的元素既可以 是原子项，也可以是子表（另一个线性表）。1广义表的定义 广义表（List）是n0个元素d1，d2，dn的有限序列 ，其中每一个di或者是原子，或者是一个子表。广义表 通常记为LS=(d1,d2,dn)，其中LS为广义表的名字，n 为广义表的长度， 每一个di为广义表的元素。但在习惯 中，一般用大写字母表示广义表，小写字母表示原子。 当广义表LS非空时，把第一个元素d1称为LS的表头（ head
15、），其余元素组成的表(d2,d3,dn)称作LS的表尾 （tail）。增长型发展策略与集团公司手机上网意见PPT培训课件关于大数据时代的大数据产品解析思考PPT培训课件婴儿喂养母乳缺点课件理疗仪器操作说明2广义表举例 （1）A=( )，A为空表，长度为0。 （2）B=(a,(b,c)，B是长度为2的广义表，第一项 为原子，第二项为子表。 （3）C=(x,y,z)，C是长度为3的广义表，每一项 都是原子。 （4）D=(B,C)，D是长度为2的广义表，每一项 都是上面提到的子表。即D=(a,(b,c), (x,y,z) （5）E=(a,E)，是长度为2的广义表，第一项为原 子，第二项为它本身。这是
16、一个递归的表。增长型发展策略与集团公司手机上网意见PPT培训课件关于大数据时代的大数据产品解析思考PPT培训课件婴儿喂养母乳缺点课件理疗仪器操作说明 3广义表的表示方法 （1）用LS=(d1，d2，dn)形式，其中每一个 di为原子或广义表。 例如：A=(b,c) B=(a,A)C=(A,B)E=(a,E)都是广义表。 （2）将广义表中所有子表写到原子形式，并利 用圆括号嵌套。 例如，上面提到的广义表A、B、C、E可以描述 为： A(b,c)B(a,A(b,c) C(A(b,c),B(a,A(b,c) E(a,E(a,E() （3）将广义表用树和图来描述增长型发展策略与集团公司手机上网意见PPT培训课件关于大数据时代的大数据产品解析思考
