《数据结构》课件-项目五 数组与广义表

在前序课程中我们学习了，线性表、栈、队列和串等经典的线性结构，这些结构的数据元素都是原子类型，其元素的值是不能再进行分解的，但在实际的开发系统中并不都是这样简单的线性结构，如三维空间中的位置信息，个性化推荐系统中的用户评分表等，本章将学习两种新的数据结构，数组和广义表。它们可以看作是对经典线性结构的一种扩展，这种扩展不是体现在数据的操作方面，而是体现在数据元素的构成上。数组和广义表中的数据元素，可以是一个简单的原子类型的元素，也可以是一个复杂的线性或非线性的数据结构。从数据元素之间的关系来看，多维数组和含有子表的广义表，已经不属于线性结构范畴。加一些视频或图片芜湖职业技术学院在前面学习数据结构的过程中，总是使用数组作为顺序表的底层实现，给我们一种“数据结构中，数组的作用就是实现顺序表”的错误认识。其实，数组的作用远不止于此，数学问题中的矩阵问题在计算机中就用数组来处理。（加一些视频或图片）我们的祖先最早使用矩阵模型并有矩阵理论的初步发展。这从公公元前1世纪左右成书的《九章算术》更可窥见一斑。《九章方程》第一题“今有上禾三秉,中禾二秉﹐下禾一秉,实三十九斗;上禾二秉,中禾三秉,下禾一秉,实三十四斗;上禾一秉,中禾二秉，下禾三秉,实二十六斗。问上、中、下、禾实一秉各几何?”答曰:上禾一秉九斗四分斗之一，中禾一秉四斗四分斗之一，下禾一秉二斗四分斗之三。术曰:置上禾三秉，中禾二秉，下禾一秉，实三十九斗，于右方。中、左行列如左方。”按算筹模块排列如图1,若用阿拉伯数字代替筹码即为图2.可以看到，我国古代的数学发展已经达到一个很高的水平，体现了古代数学家的聪明智慧。如在全国智能车比赛中，通过摄像头对赛道信息进行采集处理，将赛道转换成由像素组成的二维排列的数字图像。一般采用120×188的分辨率，这样就得到一个行120，列188的二维数组，若采用彩色图像，一个像素点需要3个字节，这样数据量太大一般采用灰度图，这样一个像素点占一个字节，再通过类似差比和等算法将图像转换为二进制图像，这样1个字节就可以存储8个像素，数据量大大减少。对此黑白的二进制图，我们可以继续寻找特征点，找到小车的最佳运行路线。矩阵广泛运用于各个领域，如数学建模、密码学、化学、通信和计算机科学等，解决了大量的实际问题。加一些视频或图片芜湖职业技术学院本章我们要解决的问题：一、多维数组的概念及存储

二、特殊矩阵的特点，存储形式及基本运算。三、稀疏矩阵的特点，存储形式及基本运算。四、广义表的概念与基本运算。芜湖职业技术学院本章我们要解决的问题：二维数组的行优先和列优先两种存储结构及求址方法。特殊矩阵的特点，存储形式及基本运算。对程矩阵与三角矩阵稀疏矩阵广义表的概念及相关术语。广义表的取表头和取表尾的基本运算。数组的概念与结构5.1数据结构第五章数组与广义表5.1.1数组的定义及操作数组的定义数组，就是相同数据类型的元素按一定顺序排列的集合，就是把有限个类型相同的变量用一个名字命名，然后用编号区分他们的变量的集合，这个名字称为数组名，编号称为下标。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。75.1.2二维数组的逻辑结构数组是一种数据结构，可以把数组看做是线性表的推广数组的特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。一维数组可以看做是一个线性表；（a0,a2...ai...an-1）二维数组可以看做是“数据元素是一维数组”的一维数组。看成n个列向量的线性表。也可看成m个行向量的线性表。Am*n=a0,0a0,1...

a0,n-1a1,0a1,1.a1,n-1am-1,0am-1,1...

am-1,n-15.1.2二维数组的逻辑结构通常在数组上不能做插入，删除数据元素的操作。一般在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。操作：取值操作：给定一组下标，读取对应的数据元素。赋值操作：给定一组下标，存储或修改对应的数据元素。对于每一个数组元素aij在第i-1行，第j-1列受到两个线性关系的约束，就是行和列的关系。Am*n=a0,0a0,1...

a0,n-1a1,0a1,1.a1,n-1am-1,0am-1,1...

am-1,n-15.1.2二维数组的逻辑结构由于对数组一般不做插入，删除操作，一旦建立了数组，数组元素个数和元素之间的关系就不再发生变动。因此，采用顺序存储结构表示数组由于存储单元是一维的结构，而数组是多维的结构，则采用一组连续存储单元存放数组元素就有个次序约定问题两种方式：一是以行为主序的顺序存放，一行存储完了接着存储下一行。二是以列为主序的顺序存放，一列存储完了接着存储下一列。数组A在计算机中的存储形式如图所示：a0,0a0,1...a0,n-1a1,0a1,1...a1,n-1...Am-1,0Am-1,1...Am-1,n-1第一行第二行第m行a0,0a1,0...Am-1,0a0,1a1,1...Am-1,1...A0,n-1A1,n-1...Am-1,n-1第一列第二列第n列Am*n=a0,0a0,1...

a0,n-1a1,0a1,1.a1,n-1am-1,0am-1,1...

am-1,n-111（1）以行序为主序的存储分配Am*n=a0,0a0,1...

a0,n-1a1,0a1,1...

a1,n-1am-1,0am-1,1...

am-1,n-112数组的顺序存储是一种随机存取的结构，根据数组的下标，可以计算数组中某个数组元素在存储器中的位置（求址）。设有m*n二维数组Amn，假设下标从0开始，“以行序为主序”的分配设数组中的a00的存储地址为LOC(a00)，每个数组元素占d个地址单元，aij的地址：LOC(aij)=LOC(a00)+(i*n+j)*d=A+(i*n+j)*d（2）以列序为主序的存储分配13设有m*n二维数组Amn，假设下标从0开始，“以列序为主序”的分配设数组中的a00的存储地址为LOC(a00)，每个数组元素占d个地址单元，aij的地址：LOC(aij)=LOC(a00)+(j*m+i)*d=A+(j*m+i)*dAm*n=a0,0a0,1...

a0,n-1a1,0a1,1...

a1,n-1am-1,0am-1,1...

am-1,n-1课程思政点：温故而知新,可以为师矣！矩阵的压缩-特殊矩阵5.2数据结构第五章数组与广义表5.2矩阵的压缩存储矩阵是很多科学与工程计算问题中研究的数学对象。如利用矩阵的方法求线性规划问题中的最优解，求解企业生产哪一种类型的产品，获得的利润最大。在高级语言中，通常使用二维数组来存储矩阵。矩阵可以用行优先或列优先方法顺序存放到内存中，但是，当矩阵的阶数很大时将占用较多存储单元。如3*3的整型矩阵需要36B，而300*300的整型矩阵需要360000B。课程思政点：我们的生活中，我们要时时刻刻保持“努力建设人与自然和谐共生的现代化”，对资源进行保护，保持可持续发展，共建美好家园。我们保护自己的家园需要我们人人都行动起来，树立保护意识。加一些图片或视频5.2矩阵的压缩存储如果矩阵中数组元素分布呈现某种规律时，可考虑将若干数组元素共用一个存储单元，即进行压缩存储。所谓压缩存储，是指为多个值相同的数组元素只分配一个存储空间，值为零的数组元素不分配空间。如果值相同的元素或者零元素在矩阵中的分布有一定规律，称此类矩阵为特殊矩阵。如果矩阵中非零的数据元素个数很少称为稀疏矩阵。首先来讨论特殊矩阵的压缩存储5.2矩阵的压缩存储对特殊矩阵的压缩存储方法：1.确定存储矩阵所需的空间的大小；2.确定矩阵元素aij在压缩存储区域中的位置。5.2特殊矩阵的压缩存储1.对称矩阵满足下述性质：aij=aji，其中1<=i<=n对称矩阵关于主对角线对称，因此只需存储上三角或下三角即可A=36478628424816982957746055.2特殊矩阵的压缩存储

这样就可以将n2个元素存储在n(n+1)/2的存储单元里。5阶对称矩阵A如图所示A=36478628424816982957746053624817460829575.2特殊矩阵的压缩存储---上下三角阵

三角矩阵分为两种：上三角矩阵和下三角矩阵。其中，下三角元素均为常数c的n阶矩阵称为上三角矩阵，上三角元素均为常数c的n阶矩阵称为下三角矩阵。A=3cccc62ccc481cc829577460cA=36478c2842cc169cccc7ccc0522

如果用一维数组来存储三角矩阵，则需要存储n*(n+1)/2+1个元素。一维数组的下标k与矩阵的下标（i,j）的对应关系为k=（i-1）*(2n-i+2)/2+j-i+10

当i<=j当i>j上三角矩阵23k=i*(i-1)/2+j0当i>=j当i<j下三角矩阵矩阵的压缩-稀疏矩阵5.3数据结构第五章数组与广义表5.3稀疏矩阵的压缩M=0009000030000000720007000-20000470000000500很多科学管理及工程计算中，常会遇到阶数很高的矩阵，通常这样的矩阵里面零元很多，我们称为稀疏矩阵。稀疏矩阵，假设在m×n矩阵中，有t个元素不为零，令δ=t/m*n，δ为矩阵的稀疏因子，如果δ≤0.05，则称矩阵为稀疏矩阵。也就是说，矩阵中存在大多数为零的元素，只有很少的非零元素，这样的矩阵是稀疏矩阵。5.3稀疏矩阵的压缩为了实现压缩存储，可以只存储稀疏矩阵的非零的元素。在存储稀疏矩阵中的非零元素时，还必须存储非零元素对应的行和列的位置(i,j)。也就是说存储一个非零元素需要存储元素的行号、列号和元素值，即通过存储(i,j,aij)唯一确定一个非零的元素。这种存储表示称为稀疏矩阵的三元组表示。jiv如果按顺序存储结构存储，会造成空间的浪费；若仅仅存放非零元素；通常零元素分布没有规律，存储非零元素的值是不够的，5.3稀疏矩阵的压缩在该稀疏矩阵示意图中，非零元素可以用以下三元组表示为：jivk41922333743214754-2354457565123456789M=0009000030000000720007000-200004700000005005.3矩阵的压缩存储三元组表类型定义#defineMAX1000typedefstruct{ inti,j; /*非零元素行、列*/ datatypev; /*非零元素值*/ }SPNode; /*三元组类型*/typestruct{ intmu,nu,tu; /*矩阵的行、列及非零元素的个数*/ SPNodedata[MAX];/*三元组表*/}SPMatrix; /*三元组的存储类型*/SPMatrixa;5.3矩阵的压缩存储三元组表法的优缺点三元组表存储稀疏矩阵，可以节约大量空间，但三元组法适合与稀疏矩阵中非零元素位置固定不变的情况。但当稀疏矩阵的值发生变化时，如，零元素变成非零元素，或非零元素变成零元素时，存储结构修改不是很方便。下面我们来学习十字链表法，可以解决上述问题。2、十字链表矩阵中，每一个矩阵元素aij，受两个线性关系的约束，行关系和列关系；每一个关系都是线性的，我们可以用线性链表来存储行关系和列关系元素aij处于第i行的单链表，也处于第j列的单链表中，就像处于十字路口一样，这种存储结构称之为“十字链表”1

15

2 2-3^1 47

^3 14^ ^2 49^ ^2、十字链表每个结点的结构为：rowcolvaldownrightright：用于连接同一行的下一个非零元素；down：用于连接同一列的下一个非零元素；mu nutuchead

rhead5.3矩阵的压缩存储十字链表类型定义typedefstructmatrixnode{ introw，col；/*矩阵中非零元素的行列号*/ intval；/*矩阵中非零元素的节点值*/Structmatrixnode*down，*right；/*down指向同一列下一个非零元素的节点*/ /*right指向同一行下一个非零元素的节点*/ }MatrixNode; 5.3矩阵的压缩存储十字链表法的优缺点十字链表法采用链表形式，当稀疏矩阵中非零元素变成零，或零元素变成非零时，直接改变链表中指针指向即可增加或删除节点，十字链表法中增加两个指针类型变量，增加了节点的存储空间，如果稀疏矩阵中非零节点多了，十字链表法并不能有效的节约空间。广义表的概念5.4数据结构第五章数组与广义表5.4.1广义表的定义广义表是线性表的推广，也称其为列表线性表是n个数据元素组成的有限序列。其中每个组成元素被限定为单元素。(a0，a2，…，ai，…，an-1)广义表是n(n≥0)个元素a0，a2，…，ai，…，an-1的有限序列，

一般记作：Ls=(a0，a2，…，ai，…，an-1)。数据元素ai或者是原子（单个元素）或者是一个广义表，其中：Ls是广义表的名字，n为它的长度。分别称为广义表Ls的单元素和子表。当广义表Ls非空时，称第一个元素a0为Ls的表头(head)，称其余元素组成的表(a1，…，ai，…，an-1)为Ls的表尾(tail)。5.4.1广义表的定义通常用大写字母表示广义表，用小写字母表示单个数据元素，广义表用括号括起来，括号内的数据元素用逗号分隔开。（1）A=(),广义表A是一个空表，A的长度为零（2）B=（a）,广义表B中只有一个原子a，B的长度为1（3）C=(a,(b,c)),广义表C中有两个元素。其中，第一个元素是原子a，第二个元素是一个子表（b,c）,C的长度为2。（4）D=(A,B,C)，广义表D中有三个元素，这三个元素都是子表，第一个元素是一个空表A，D的长度为三。（5）E=（a,b,E），广义表E中有三个元素，前两个元素是原子，第三个元素是一个子表E。E是一个无穷的表，E=(a,b,(a,b(a,b(a,b(a,b...)))))5.4.2广义表的性质（1）广义表的元素可以是原子，也可以是子表，子表的元素还可以是子表。广义表的结构是一个多层次的结构（2）广义表的元素可以是其它广义表的元素，也就是说，一个广义表可以与其他广义表共享。例如，A、B和C是D的子表，在表D中不需要列出A、B和C的元素。（3）广义表可以是递归的表，即广义表可以是本身的一个子表。例如，D是一个递归的广义表。

(4)任何一个非空的广义表的表头可以是一个原子，也可以是一个广义表，而表尾则一定是一个广义表。广义表 A=(),B=(a)，C=(a,(b,c)),D=(A,B,C)5.4广义表

广义表的运算1、取表头head(Ls)：是表中第一个元素，它可以是原子，也可以是子表。

2、取表尾tail(Ls)：是表中除了第一个元素外其他元素组成的表，而其表尾必定是子表。B=(a)head(B)=atail(B)=()C=(a,(b,c,d))head(C)=atail(C)=((b,c,d))D=(A,B,C)head(D)=Atail(D)=(B,C)5.4广义表的存储结构1.头尾表示法在广义表中，数据元素可以是原子，也可以是广义表，因此，利用定长的顺序存储结构很难表示。通常情况下，广义表采用链式存储结构，即每个数据元素只用一个结点表示。39广义表中的每个元素可以用一个结点表示，表中有两类结点：原子结点和子表结点。广义表可以分解为表头和表尾，一个表头和一个表尾可以唯一确定一个广义表.40表结点和原子结点的存储结构如图所示tag=1hptptag=0data表结点原子结点一个表结点可以由三个域组成：标志域、指向表头的指针域和指向表尾的指针域。一个原子结点一般由两个域组成：标志域和值域.typedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{

ElemTagtag;

union

{

DataTypeatom;