《数组和广义表.ppt》由会员分享，可在线阅读，更多相关《数组和广义表.ppt（61页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、新联学院数据结构数组和广义表 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望本章内容5.1 数组的定义5.2 数组的顺序表示和实现5.3 矩阵的压缩存储5.4 广义表的定义5.5 广义表的存储结构新联学院数据结构5-3 通过本章学习，要求掌握如下内容：1多维数组的定义及在计算机中的存储表示；2对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式；3稀疏矩阵的三元组表示及转置算法实现；4稀疏矩阵的十字链表表示及相加算法实现；5广义表存储结构表
2、示及基本运算。重点难点新联学院数据结构5-4 数组是我们最熟悉的数据类型，在早期的高级语言中，数组是数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，并且数组元素的下标一般具有固定的上界和下界，因此，数组的因此，数组的处理比其它复杂的结构更为简单。处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，多维数组是向量的推广。例如，二维数组：二维数组：5.1 数组的定义Amn=a11 a12 a1na21 a22 a2n am1 am2
3、 amn新联学院数据结构5-5 5.1 数组的定义 数组可以看成是一种数组可以看成是一种特殊的线性表特殊的线性表，即线性表中数据，即线性表中数据元素本身也是一个线性表。元素本身也是一个线性表。数组是数组是n（n0）个相同数据类型数据元素构成的）个相同数据类型数据元素构成的有限有限序列。序列。新联学院数据结构()()()()()()()()()二维数组同样满足数组的定义。二维数组可以看成一个特殊的二维数组同样满足数组的定义。二维数组可以看成一个特殊的一维数组，其中的每个元素又是一个一维数组一维数组，其中的每个元素又是一个一维数组。5.1 数组的定义新联学院数据结构5-7 数组的特点：数组的特点：
4、数组的特点：数组的特点：数组中的数据元素数目固定数组中的数据元素数目固定数组中的数据元素数目固定数组中的数据元素数目固定(结构固定结构固定结构固定结构固定)；数组中的数据元素具有相同的数据类型数组中的数据元素具有相同的数据类型数组中的数据元素具有相同的数据类型数组中的数据元素具有相同的数据类型(元素同构元素同构元素同构元素同构)；数组中的每个数据元素都与一组数组中的每个数据元素都与一组数组中的每个数据元素都与一组数组中的每个数据元素都与一组唯一的下标值相对应唯一的下标值相对应唯一的下标值相对应唯一的下标值相对应；数组是一种数组是一种数组是一种数组是一种随机存取结构随机存取结构随机存取结构随机存
5、取结构。5.1 数组的定义新联学院数据结构5.1数组的抽象数据类型ADT5-8 新联学院数据结构一维数组存储结构示意图存储地址存储地址 内存空间状态内存空间状态 逻辑地址逻辑地址 Loc(a1)a11 Loc(a1)+(2-1)L a2 2 loc(a1)+(i-1)Lai i loc(a1)+(n-1)L an n 地址映像的计算公式：地址映像的计算公式：假设线性表中假设线性表中每个元素占每个元素占L L个单元个单元，第一个元素的地址为第一个元素的地址为loc(loc(a1)，则第，则第i i个元素的地址为：个元素的地址为：loc(ai)=loc(a1)+(i-1)L 新联学院数据结构5.2
6、 数组的顺序表示和实现p问问 题：计算机的存储结构是一维的，而数组一般是多维的，怎样存题：计算机的存储结构是一维的，而数组一般是多维的，怎样存放？放？p解决办法：事先约定按某种次序将数组元素排成一列序列，然后将这解决办法：事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。个线性序列存入存储器中。p注意：注意：用一组连续的存储单元来表示数组；用一组连续的存储单元来表示数组；若规定好了次序，则数组中任意一个元素的存放地址便有若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；规律可寻，可形成地址计算公式；约定的次序不同，则计算元素地址的公式也有所
7、不同；约定的次序不同，则计算元素地址的公式也有所不同；C C和和PASCALPASCAL中一般采用中一般采用行优先行优先顺序；顺序；FORTRANFORTRAN采用采用列优先列优先5-10 新联学院数据结构5-11 5.2 数组的顺序表示和实现p设一设一3 3维数组维数组A423A423，存贮，存贮在一个顺序线性表在一个顺序线性表S S中，结构如中，结构如下所示：下所示：A312A311A310A302A301A300A212A211A210A202A201A200A112A111A110A102A101A100A012A011A010A002A001A000A312A311A310A302A
8、301A300A212A211A210A202A201A200A112A111A110A102A101A100A012A011A010A002A001A00001234567.2223A000A001A002A010A011A012A100A101.A311A312新联学院数据结构5.2 数组的顺序表示和实现p 以行为主以行为主:对二维数组进行对二维数组进行“按行切分按行切分”，即将数组中的，即将数组中的数据元素数据元素“按行依次排放按行依次排放”在存储器中；在存储器中；p 以列为主：以列为主：对二维数组进行对二维数组进行“按列切分按列切分”，即将数组中，即将数组中的数据元素的数据元素“按列依
9、次排放按列依次排放”在存储器中。在存储器中。5-12 新联学院数据结构 按行序为主序存放LOC(i,j)=LOC(0,0)+(i*n+j)*L新联学院数据结构 按列序为主序存放LOC(i,j)=LOC(0,0)+(j*m+i)*L新联学院数据结构例题 无无论论规规定定行行优优先先或或列列优优先先，只只要要知知道道以以下下三三要要素素便便可可随随时时求求出出任任一元素的地址：一元素的地址：开始结点的存放地址（即基地址）开始结点的存放地址（即基地址）维数和每维的上、下界；维数和每维的上、下界；每个数组元素所占用的单元数每个数组元素所占用的单元数5-15 新联学院数据结构例题【例【例5-15-1】对
10、于给定的二维数组】对于给定的二维数组float a34float a34，计算：计算：(1)(1)数组数组a a中的数组元素上界、下界、元素数目；中的数组元素上界、下界、元素数目；(2)(2)若若数数组组a a的的起起始始地地址址为为10001000，且且每每个个数数组组元元素素长长度度为为3232位位(即即4 4个个字字节节)，数组元素，数组元素a23a23的内存地址。的内存地址。【解解】(1)(1)由由于于C C语语言言中中数数组组的的行行、列列下下标标值值的的下下界界均均为为0 0，该该数数组组行行上上界为界为3-1=23-1=2，列上界为列上界为4-1=34-1=3，所以该数组的元素数
11、目共有，所以该数组的元素数目共有3*4=123*4=12个个。(2)(2)由于由于C C语言采用行序为主序的存储方式，有：语言采用行序为主序的存储方式，有：LOC(aLOC(a2,32,3)=LOC(a)=LOC(a0,00,0)+(i*n+j)*L)+(i*n+j)*L =1000+(2*4+3)*4 =1000+(2*4+3)*4 =1044 =10445-16 新联学院数据结构例题p【例【例5-5-2 2】一个二维数组】一个二维数组A，行下标的范围是，行下标的范围是1到到6，列下标的范围是，列下标的范围是0到到7，每个数组元素用相邻的，每个数组元素用相邻的6个字节存储，存储器按字节编址。
12、个字节存储，存储器按字节编址。那么，这个数组的体积是那么，这个数组的体积是 个字节。个字节。【解】【解】Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=288p【例【例5-5-3 3】设数组设数组a160,170的基地址为的基地址为2048，每个元素占，每个元素占2个存储单元，若以列序为主序顺序存储，则元素个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地的存储地址为址为 。5-17 根据列优先公式根据列优先公式 Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*L得：得：LOC(a32,58)=2048+(58-1)*60+(32-1)*28
13、950想一想：若数组是想一想：若数组是a059,069，结果是否仍为结果是否仍为8950？新联学院数据结构5-18 5.3 矩阵的压缩存储p在高级语言编制程序时，将一个矩阵描述为一个二维数组。在高级语言编制程序时，将一个矩阵描述为一个二维数组。p矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为运算也非常简单，并且存储的密度为1 1。但是在矩阵中非零元素呈。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度
14、仍为密度仍为1 1，但实际上占用了许多单元去存储重复的非零元素或零，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费元素，这对高阶矩阵会造成极大的浪费.新联学院数据结构5.3 矩阵的压缩存储5-19 p 压缩存储压缩存储压缩存储压缩存储 为多个值相同的矩阵只分配一个存储空间；为多个值相同的矩阵只分配一个存储空间；为多个值相同的矩阵只分配一个存储空间；为多个值相同的矩阵只分配一个存储空间；对零元不分配空间。对零元不分配空间。对零元不分配空间。对零元不分配空间。新联学院数据结构5-20 5.3 矩阵的压缩存储5.3.1 特殊矩阵特殊矩阵值相同的元素或者值相同的元素或
15、者0 0元素在矩阵中的元素在矩阵中的分布有一定规律分布有一定规律。新联学院数据结构5-21 5.3 矩阵的压缩存储p对称矩阵对称矩阵 仅存储仅存储下三角下三角新联学院数据结构 下三角矩阵下三角矩阵p5.3 矩阵的压缩存储新联学院数据结构p5.3 矩阵的压缩存储 对角矩阵对角矩阵新联学院数据结构5-24 5.3 矩阵的压缩存储5.3.2 稀疏矩阵稀疏矩阵p定义：设矩阵定义：设矩阵A A中有中有t t个非零元素，若个非零元素，若s s远远小于矩阵元素的总数远远小于矩阵元素的总数（即（即smnsmn），则称），则称A A为为稀疏矩阵稀疏矩阵。设在的矩阵设在的矩阵A A中，有中，有t t个非零元素。令
16、个非零元素。令 e=t/(m*n)e=t/(m*n)，称，称e e为矩阵为矩阵的的稀疏因子稀疏因子。通常认为。通常认为e0.05e0.05时称之为时称之为稀疏矩阵稀疏矩阵。以常规方法，即以二维数组表示的高阶的稀疏矩阵时产生的问题：以常规方法，即以二维数组表示的高阶的稀疏矩阵时产生的问题：1.1.零值元素占的空间很大；零值元素占的空间很大；2.2.计算中进行了很多和零值的运算；计算中进行了很多和零值的运算；新联学院数据结构5.3 矩阵的压缩存储p解决问题的原则解决问题的原则1.尽量少存或不存尽量少存或不存0 0元；元；2.2.尽量减少没有意义的运算；尽量减少没有意义的运算；3.3.运算要方便。运
17、算要方便。能尽可能快地找到与下标值（能尽可能快地找到与下标值（i i，j j）对应的运算；）对应的运算；能尽可能快地找到同一行或同一列的非能尽可能快地找到同一行或同一列的非0 0值元。值元。压缩存储方法：压缩存储方法：三元组顺序表三元组顺序表、行逻辑连接行逻辑连接和和十字链表十字链表。5-25 新联学院数据结构 存储特点存储特点2.三元组顺序表 对于矩阵中每个非对于矩阵中每个非0元素，用它的元素，用它的行号、列号、元素行号、列号、元素值值，即（，即（i,j,aij）表示。）表示。将表示稀疏矩阵的所有非将表示稀疏矩阵的所有非0元素的三元组按行优先顺元素的三元组按行优先顺序排列，则可得到序排列，则
18、可得到一个其结点均是三元组的线性表一个其结点均是三元组的线性表，称为三元组表。称为三元组表。以以顺序存储结构顺序存储结构来表示三元组。来表示三元组。要唯一确定一个稀疏矩阵，还必须要唯一确定一个稀疏矩阵，还必须存储该矩阵的行存储该矩阵的行数和列数数和列数。新联学院数据结构5-27 p三元组法存储三元组法存储0 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0（(1,2,12)(1,2,12)，(1,3,9)(1,3,9)，(3,1,-3)(3,1,-3)，(3,5,14)(3,5,14)，(4,3,2
19、4)(4,3,24)，(5,2,18)(5,2,18)，(6,1,15)(6,1,15)，(6,4,-7)(6,4,-7)6行行6列，列，8个非零元个非零元2.三元组顺序表新联学院数据结构p三元组法存储三元组法存储5-28 8552635531143742551221datacolrow02005000070000011520000000000802.三元组顺序表新联学院数据结构 数据类型定义#define MAXSIZE 12500 三元组结点三元组结点：typedef struct int i,j;/行号，列号行号，列号 ElemType e;Triple;稀疏矩阵：稀疏矩阵：typede
20、f struct Triple dataMAXSIZE+1;int mu,nu,tu;/*行、列、非零元素个数行、列、非零元素个数*/TSMatrix;2.三元组顺序表新联学院数据结构5-30 p例子：三元组法表示的矩阵转置例子：三元组法表示的矩阵转置M T02005000070000011520000000000800000020000000000711005050800200已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表。常规算法：常规算法：for(col=1;col=nu;col+)for(row=1;row=mu;row+)Tcolrow=Mrowcol;时间复杂度：时间复杂度
21、：O(munu)2.三元组顺序表新联学院数据结构5-31 解决思路：解决思路：将矩阵行、列维数互换；将矩阵行、列维数互换；将每个三元组中的将每个三元组中的i i和和j j相互调换；相互调换；重排三元组次序；重排三元组次序；2.三元组顺序表新联学院数据结构5-32 M.data12315-522-131634841-44570300-50-100060080-40007M006-43-10000000080-5007TT.data21351-522-113643814-454721351-522-151-52.三元组顺序表新联学院数据结构5-33 M.data12315-522-13163484
22、1-44570300-50-100060080-40007M006-43-10000000080-5007TT.data21351-522-113643814-45472.三元组顺序表新联学院数据结构5-34 M.data12315-522-131634841-4457T.data21351-522-113643814-4547Col12345NumcPot00000+1+1+1+1+1+1+12.三元组顺序表新联学院数据结构5-35 M.data12315-522-131634841-4457T.data21351-522-113643814-4547Col12345Num22012cPot
23、123455672.三元组顺序表新联学院数据结构5-36 2.三元组顺序表新联学院数据结构 优点：优点：非零元在表中按行序有序存储，便于进行非零元在表中按行序有序存储，便于进行依行依行序处理的矩阵运算序处理的矩阵运算。缺点：缺点：若需按行号存取某一行的非零元，则需从头开若需按行号存取某一行的非零元，则需从头开始查找。始查找。2.三元组顺序表新联学院数据结构 为了便于随机存储任意一行的非零元，需要知为了便于随机存储任意一行的非零元，需要知道每一行的第一个非零元在三元组表中的位置。道每一行的第一个非零元在三元组表中的位置。3.行逻辑连接的顺序表#define MAXSIZE 12500 三元组结点
24、三元组结点：typedef struct int i,j;ElemType e;Triple;稀疏矩阵：稀疏矩阵：typedef struct Triple dataMAXSIZE+1;int rposMAXRC+1;/*各行第一个非零元的位置表各行第一个非零元的位置表 int mu,nu,tu;/*行、列、非零元素个数行、列、非零元素个数*/TSMatrix;新联学院数据结构5-39 3.行逻辑连接的顺序表p带行向量的三元组法的矩阵乘法带行向量的三元组法的矩阵乘法新联学院数据结构5-40 3.行逻辑连接的顺序表020030-15004007600-300M(4,5)032410000-2N(
25、5,2)=423-400-30Q(4,2)M.data12215322-123531434735643-3N.data12321222431152-2新联学院数据结构 问题描述：问题描述：已知两个稀疏矩阵已知两个稀疏矩阵M和和N的三元组表，求两个矩阵的三元组表，求两个矩阵相乘的结果矩阵相乘的结果矩阵Q。常规算法：常规算法：for(i=1;i=m1;i+)for(j=1;j=n2;j+)Qij=0;for(k=1;k=n1;k+)Qij+=Mik*Nkj;1 1、只对、只对M M和和N N的非零元进行计算；的非零元进行计算；2 2、M M中列号与中列号与N N中行号相等的非零元相乘即可；中行号相
26、等的非零元相乘即可；3 3、Q Q与与M M的行号对齐的，且的行号对齐的，且QijQij是累加的结果。是累加的结果。3.行逻辑连接的顺序表新联学院数据结构3.行逻辑连接的顺序表Q初始化；初始化；if（Q是非零矩阵）是非零矩阵）for(arrow=1;arrow=M.mu;arrow+)ctemp=0;计算计算Q中第中第arrow行的积并存入行的积并存入ctemp中；中；将将ctemp中非零元压缩存储到中非零元压缩存储到Q.data；5-42 新联学院数据结构处理M的每一行新联学院数据结构分析上述算法的时间复杂度分析上述算法的时间复杂度例子例子:求矩阵乘法求矩阵乘法1、累加器、累加器ctemp初
27、始化初始化的时间复杂度为的时间复杂度为O(M.muN.nu)2、求、求Q的所有非零元的所有非零元的时间复杂度为的时间复杂度为O(M.tuN.tu/N.mu)3、进行、进行压缩存储压缩存储的时间复杂度为的时间复杂度为O(M.muN.nu)总的时间复杂度总的时间复杂度O(M.muN.nu+M.tuN.tu/N.mu)若若M M是是m m行行n n列的稀疏矩阵，列的稀疏矩阵，N N是是n n行行p p列的稀疏矩阵，则：列的稀疏矩阵，则：M中非零元的个数：中非零元的个数：M.tu=M mn N中非零元的个数：中非零元的个数：M.tu=N np 相乘算法的时间复杂度就是相乘算法的时间复杂度就是O(mn(
28、1+nMN)，当：，当：M 0.05和和N 1000时，时，算法的时间复杂度相当于算法的时间复杂度相当于O(mp)。新联学院数据结构 引入原因引入原因4.4.十字链表十字链表十字链表十字链表 当矩阵的非零元的个数发生变化时，不宜采用三元组当矩阵的非零元的个数发生变化时，不宜采用三元组表。如表。如A=A+B，非零元的插入或删除将会引起，非零元的插入或删除将会引起A.data中的数据移动，这是顺序结构三元组的弱势。中的数据移动，这是顺序结构三元组的弱势。数据类型定义数据类型定义结点结点：typedef struct OLNode int i,j;ElemType e;struct OLNode*r
29、ight，*down；/*该非零元所在行的后继链域该非零元所在行的后继链域*/OLNode;*OLink；稀疏矩阵：稀疏矩阵：typedef struct OLink*rhead，*chead；int mu，nu，tu；Crosslist;ijkdownright新联学院数据结构5-46 4.十字链表p十字链表结点定义：每一个非零元用一个结点表示，结点包括五个十字链表结点定义：每一个非零元用一个结点表示，结点包括五个域：除了表示非零元所在的行、列和值的三元组域：除了表示非零元所在的行、列和值的三元组（i,j,v）外，还需外，还需增加两个链域：行指针域（增加两个链域：行指针域（rightrigh
30、t），用来指向本行中下一个非零），用来指向本行中下一个非零元素；列指针域（元素；列指针域（downdown），用来指向本列中下一个非零元素。），用来指向本列中下一个非零元素。ijrightdownv新联学院数据结构5-47 4.十字链表p十字链表法：十字链表法：为稀疏矩阵中的链接存储中的一种较好的存储方法为稀疏矩阵中的链接存储中的一种较好的存储方法稀疏稀疏矩阵矩阵及其及其十字交叉链表十字交叉链表0 12 0 0 00 0 0 0-40 5 0 0 00 0 3 0 0A=(a)稀疏稀疏矩阵矩阵(b(b)稀疏稀疏矩阵的十字交叉链表矩阵的十字交叉链表A.cheadA.rchead121232525
31、-4433新联学院数据结构5-48 4.十字链表p十字链表类型定义十字链表类型定义稀疏矩阵中同一行的非零元通过向右的稀疏矩阵中同一行的非零元通过向右的rightright指针链接成一个指针链接成一个带表头结点的线性链表。同一列的非零元也通过带表头结点的线性链表。同一列的非零元也通过downdown指针链接成一指针链接成一个带表头结点的线性链表。个带表头结点的线性链表。因此，每个非零元既是第因此，每个非零元既是第i i行循环链表中的一个结点，又是第行循环链表中的一个结点，又是第j j列循环链表中的一个结点，相当于处在一个十字交叉路口，故称链列循环链表中的一个结点，相当于处在一个十字交叉路口，故称
32、链表为十字链表。表为十字链表。可用两个分别存储行链表的头指针和列链表的头指可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。针的一维数组表示之。新联学院数据结构5-49 是线性表的推广是线性表的推广是线性表的推广是线性表的推广，广泛的应用于人工智能等领域。，广泛的应用于人工智能等领域。，广泛的应用于人工智能等领域。，广泛的应用于人工智能等领域。一般记作一般记作一般记作一般记作LS=LS=LS=LS=（1 1 1 1，2 2 2 2，,n n n n）(n0)(n0)(n0)(n0)其中其中其中其中i i i i既既既既可以为单个元素也可以为广义表。可以为单个元素也可以为广义表。可
33、以为单个元素也可以为广义表。可以为单个元素也可以为广义表。名称名称名称名称：LSLSLSLS；长度长度长度长度：n n n n；原子原子原子原子：i i i i是单个元素；是单个元素；是单个元素；是单个元素；子表子表子表子表：i i i i是广义表；是广义表；是广义表；是广义表；表头表头表头表头(Head)(Head)(Head)(Head)：非空广义表：非空广义表：非空广义表：非空广义表LSLSLSLS的第一个数据元素的第一个数据元素的第一个数据元素的第一个数据元素 1 1 1 1；表尾表尾表尾表尾(Tail)(Tail)(Tail)(Tail)：非空广义表除第一个数据元素外的其余数据元：非
34、空广义表除第一个数据元素外的其余数据元：非空广义表除第一个数据元素外的其余数据元：非空广义表除第一个数据元素外的其余数据元素构成的广义表素构成的广义表素构成的广义表素构成的广义表(2 2，,n n）5.4广义表新联学院数据结构5-50 5.4广义表p任意一个非空广义表，均可分解为表头和表尾。任意一个非空广义表，均可分解为表头和表尾。p对于一个非空广义表，其表头可能是对于一个非空广义表，其表头可能是原子原子，也可能是，也可能是子表子表；而表尾；而表尾一定是一定是子表子表。pp广义表举例广义表举例广义表举例广义表举例1.A=（）（）/空表，长度空表，长度n=02.B=（e）/n=1,只有一个原子只
35、有一个原子e3.C=（a,(b,c,d)/n=2,有两个元素，分别为原子有两个元素，分别为原子a和子表和子表(b,c,d)4.D=（A，B，C）/n=3,有有3个元素个元素5.E=(a,E）/n=2,无限循环列表（递归）无限循环列表（递归）新联学院数据结构5-51 5.4广义表p性质性质n n广义表是一个广义表是一个广义表是一个广义表是一个多层次多层次多层次多层次结构结构结构结构;n n广义表的深度广义表的深度广义表的深度广义表的深度 d d 定义为所含括弧的重数（定义为所含括弧的重数（定义为所含括弧的重数（定义为所含括弧的重数（展开后所含展开后所含括号括号括号括号的的层层层层数数数数）;l
36、l“原子原子原子原子”的深度为的深度为的深度为的深度为0 0;l l“空表空表空表空表”的深度为的深度为的深度为的深度为1 1n n 广义表可以广义表可以广义表可以广义表可以共享共享共享共享;也可以是一个也可以是一个也可以是一个也可以是一个递归递归递归递归的表的表的表的表;广广 义义 表表表长表长n表深表深hA=()00B=(e)11C=(a,(b,c,d)22D=(A,B,C)33E=(a,E)2F=()12abecdABCD新联学院数据结构 广广义义表表有有两两个个重重要要的的基基本本操操作作，即即取取头头操操作作（Head）和和取取尾尾操操作作（Tail）。）。根根据据广广义义表表的的表
37、表头头、表表尾尾的的定定义义可可知知，对对于于任任意意一一个个非非空空的的列列表表，其其表头可能是单元素也可能是列表，而表尾必为列表。例如：表头可能是单元素也可能是列表，而表尾必为列表。例如：1.B=（e）Head（B）e Tail（B）（）（）2.C=（a,(b,c,d)Head（C）a Tail（C）（）（b，c，d）3.D=（A，B，C）Head（D）A Tail（D）（）（B，C）4.E=(a,E）Head（E）a Tail（E）（）（E）5.F=()Head（F）（）（）Tail（F）（）（）6.LS=(a,b),(a,b),(u,(x,y,z),()，求，求LS的深度的深度5.4广
38、义表新联学院数据结构5-53 5.5广义表的存储结构pp 广义表的表示有两种结构形式广义表的表示有两种结构形式广义表的表示有两种结构形式广义表的表示有两种结构形式 表结点表结点表结点表结点 原子结点原子结点原子结点原子结点 第一种结构形式第一种结构形式第一种结构形式第一种结构形式1LS表头表头表尾表尾LS=NULL 新联学院数据结构5-54 5.5广义表的存储结构新联学院数据结构5-55 5.5广义表的存储结构typedefenumatom,listelemtag;typedefstructGLnodeElemtagtag;unionunionAtomTypeatom;structGLnode
39、*hp;/表结点的表头指针;structGLnode*tp;/指向下一个元素结点*GListGList;新联学院数据结构5-56 5.5广义表的存储结构p广义表的运算广义表的运算n创建空的广义表创建空的广义表:initGList(&L);n销毁广义表销毁广义表:destroyGList(&L);n复制广义表复制广义表:copyGList(&T,L);n求广义表的长度求广义表的长度:length(L);n求广义表的深度求广义表的深度:depth(L);n求广义表的表头求广义表的表头:getHead(L);n求广义表的表尾求广义表的表尾:getTail(L);n插入一个元素使其成为新的表头插入一个
40、元素使其成为新的表头:insertFirst(&L,e);n删除表头元素删除表头元素:deleteFirst(&L,&e);n判断表是否空判断表是否空:isEmpty(L);新联学院数据结构5-57 5.5广义表的存储结构p广义表作为广义表作为ADTADT Glist 数据对象数据对象:D=ei|i=1,2,n;n 0,ei AtomSet 或或ei Glist 数据关系数据关系:R=(ei-1,ei)|ei D 基本操作基本操作:initGList(&L);操作结果操作结果:创建空表创建空表;destroyGList(&L);初始条件初始条件:广义表广义表L已存在已存在 操作结果操作结果:销
41、毁广义表销毁广义表 ./Glist;新联学院数据结构5-58 5.5广义表的存储结构p求广义表的深度求广义表的深度设：设：LS=(a1,a2,an)，例如，对于广义表例如，对于广义表 E(B(a,b),D(B(a,b),C(u,(x,y,z),A()按递归算法分析：按递归算法分析：Depth(E)=1+Max Depth(B),Depth(D)Depth(B)=1+Max Depth(a),Depth(b)=1 Depth(D)=1+Max Depth(B),Depth(C),Depth(A)新联学院数据结构5-59 5.5广义表的存储结构Depth(C)=1+Max Depth(u),Dep
42、th(x,y,z)Depth(A)=1Depth(u)=0Depth(x,y,z)=1+Max Depth(x),Depth(y),Depth(z)=1 Depth(C)=1+Max Depth(u),Depth(x,y,z)=1+Max 0,1=2 Depth(D)=1+Max Depth(B),Depth(C),Depth(A)=1+Max 1,2,1=3Depth(E)=1+Max Depth(B),Depth(D)=1+Max 1,3=4新联学院数据结构5-60 5.5广义表的存储结构Int depth(GList*ls)/广义表广义表ls 用扩展的线性链表存储，函数返回用扩展的线性链
43、表存储，函数返回ls的深度的深度 if(ls=NULL)return 1;/空表空表 GList*temp=ls;int m=0;/m 表示当前层元素的最大深度表示当前层元素的最大深度 while(temp!=NULL)/横扫广义表的每个元素横扫广义表的每个元素 if(temptag=LIST)/子表深度子表深度 int n=depth(temphp);if(nm)m=n;/不是子表不加深度不是子表不加深度 temp=temptp;/temp指向下一个元素指向下一个元素 return m+1;新联学院数据结构本章小结数组数组数组数组uu数组的定义和特点数组的定义和特点数组的定义和特点数组的定义
44、和特点uu数组的顺序存储（行优先，列优先）数组的顺序存储（行优先，列优先）数组的顺序存储（行优先，列优先）数组的顺序存储（行优先，列优先）uu逻辑地址逻辑地址逻辑地址逻辑地址 物理地址的计算物理地址的计算物理地址的计算物理地址的计算；矩阵的压缩存储矩阵的压缩存储矩阵的压缩存储矩阵的压缩存储uu对称矩阵、上三角或下三角等特殊矩阵压缩存储时对称矩阵、上三角或下三角等特殊矩阵压缩存储时对称矩阵、上三角或下三角等特殊矩阵压缩存储时对称矩阵、上三角或下三角等特殊矩阵压缩存储时的地址转换公式的地址转换公式的地址转换公式的地址转换公式uu稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储：存储特点、：存储特点、：存储特点、：存储特点、三元组表三元组表三元组表三元组表表示表示表示表示广义表广义表广义表广义表uu广义表的定义、特点广义表的定义、特点广义表的定义、特点广义表的定义、特点uu广义表的链式存储结构广义表的链式存储结构广义表的链式存储结构广义表的链式存储结构