《第5章数组和广义表ppt课件》由会员分享，可在线阅读，更多相关《第5章数组和广义表ppt课件（80页珍藏版）》请在金锄头文库上搜索。
1、第第5章章 数组和广义表数组和广义表 元素的值并非原子类型，可以再分解，表中元素的值并非原子类型，可以再分解，表中 元素也是一个线性表（即线性表的推广）。元素也是一个线性表（即线性表的推广）。数组和广义表的特点：数组和广义表的特点：特殊的线性表特殊的线性表恩圈胎隐毙垛舆悦宣心谱渍瓢忻窖恶制辛款吭秆莆逮镜酣醋变勺眨谜刮恃第5章数组和广义表ppt课件第5章数组和广义表ppt课件5.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.3 矩阵的压缩存储矩阵的压缩存储5.4 广义表的定义广义表的定义5.5 广义表的存储结构广义表的存储结构第第5章章 数组和广义表数组和广义表炯拖
2、抑座聘顶毕弥胸垂雷逊味缆斤间窑奠候锯唱伴咆潘坯诬颗抽孪哇盾叔第5章数组和广义表ppt课件第5章数组和广义表ppt课件5.1 数组的定义 数组：数组： 由一组名字相同、下标不同的同类型的元素由一组名字相同、下标不同的同类型的元素 组成组成数组特点数组特点数组结构固定,下标一般具有下标一般具有固定的上界和下界固定的上界和下界数据元素具有具有统一的类型统一的类型数组运算数组运算给定一组下标，取取相应的数据元素.给定一组下标，修修改数据元素的值.数组的处理比其它复杂的结构要简单数组的处理比其它复杂的结构要简单账服踞践盖毒痞睡塌哑翅轿章借电盘粱血涝仇阮利戈钙凶盏泻筛粹病秸型第5章数组和广义表ppt课件第
3、5章数组和广义表ppt课件与高级语言中数组的区别：与高级语言中数组的区别： 1、本章所讨论的数组是一种、本章所讨论的数组是一种数据结构数据结构，而高级语言，而高级语言中数组是一种中数组是一种数据类型数据类型。2、高级语言高级语言中的数组是中的数组是顺序结构顺序结构；而本章的数组；而本章的数组 既可以是既可以是顺序的，顺序的，也可以是也可以是链式结构链式结构，用户可根，用户可根 据需要选择。据需要选择。鱼踊官铜引瞎幻函儿衷芯石韶揍茅氓傍逞喻反鸯绢屡宙刘亚枪手卞奢娶砷第5章数组和广义表ppt课件第5章数组和广义表ppt课件二维数组的特点：二维数组的特点：一维数组的特点：一维数组的特点： 1个下标，
4、个下标，ai是是ai+1的直接前驱的直接前驱2 2个下标，个下标，每个元素每个元素aij受到两个关系（行受到两个关系（行关系和列关系）的约束：关系和列关系）的约束：一个一个m mn n的二维数组可以的二维数组可以看成是由看成是由m m行的一维数组组行的一维数组组成或由成或由n n列的一维数组组成。列的一维数组组成。A0A1.Am-1Ai=(ai0,ai1,ai,n-1)i=0,1,2,m-15.1 数组的定义 苗沽荤憾舞挞诛朔确回供络谎掳河穷蹲藉帝箩邵娠泡鹊鼻澳胎牌幌查哗侄第5章数组和广义表ppt课件第5章数组和广义表ppt课件 B0B1Bn-1二维数组是一个数据元素为线性表的线性表二维数组是
5、一个数据元素为线性表的线性表j=0,1,n-1遏遗名场馅折邻杠愿打拇传冰赁裴涝嗜蔬系台饥谦出轴簧窑蜘铁乡秸攀漏第5章数组和广义表ppt课件第5章数组和广义表ppt课件qaij(1im-2，1jn-2)有有两个前驱两个前驱结点结点ai,j-1和和ai-1,j两个后继两个后继结点结点ai,j+1和和ai+1,jqa00没有前驱结点没有前驱结点,称之为开始结点称之为开始结点.qam-1,n-1没有后继结点没有后继结点,称之为终端结点称之为终端结点.q第第0行的元素行的元素a0j(j=1,n-1)q第第0列的元素列的元素ai0(i=1,m-1)只有一个前驱只有一个前驱只有一个后继只有一个后继我们可以把
6、二维数组中的元素我们可以把二维数组中的元素aij看成是属于两个线性表看成是属于两个线性表:即即第第i行的线性表行的线性表Ai和和第第j列的线性表列的线性表Bjq第第m-1行的元素行的元素am-1,j(j=1,n-2)q第第n-1列的元素列的元素ai,n-1(i=1,m-2)钙症沼意扭菩三碍足精衙亲啼婴爷乞菩遭柱顽钳螟糯诫偷崎擦吼涯嫉暑涯第5章数组和广义表ppt课件第5章数组和广义表ppt课件同理，三维数组同理，三维数组Amnl中每个元素属于三个线性表，每个元素中每个元素属于三个线性表，每个元素最多有三个前驱和三个后继。最多有三个前驱和三个后继。ai1,i2,i3前驱：前驱：ai1-1,i2,i
7、3，ai1,i2-1,i3，ai1,i2,i3-1后继：后继：ai1+1,i2,i3，ai1,i2+1,i3，ai1,i2,i3+1推而广之推而广之，一个一个n n维数组可以看成是维数组可以看成是由若干个由若干个n1维数组组成的线维数组组成的线性表性表，在，在n维数组维数组Ab1b2bn中中,每个元素每个元素ai1,i2,in(0ijbi-1,j=1,2,n)属于属于n个线性表个线性表,每个元素每个元素最多有最多有n个前驱和个前驱和n个后继。个后继。ai1,i2,in前驱：前驱：ai1-1,i2,in，ai1,i2-1,in，,，ai1,i2,in-1后继：后继：ai1+1,i2,in，ai1
8、,i2+1,in，ai1,i2,in+1冕斋尘顶败裴逸残咯晦顷械恭易裳崇棘溜憾倘币问凶直诫颜谋镶渝尧临老第5章数组和广义表ppt课件第5章数组和广义表ppt课件数据对象数据对象: : D=aij|aij ElemSet，0ib1-1,0jb2-1数据关系数据关系: : R=ROW,COLROW=|0ib1-1,0jb2-2COL=|0ib1-2,0jb2-1二维数组的二维数组的定义定义:抨炬返巩矿圈懊肋翅吼视弓界钟锯兹春裕付转柒掇棋搜即甄街玄贫浪恒镶第5章数组和广义表ppt课件第5章数组和广义表ppt课件InitArray(&A,n,bound1,.,boundn)操作结果：操作结果：若维数若
9、维数n和各维长度合法，则构造相应和各维长度合法，则构造相应的数组的数组A，并返回，并返回OK。基本操作：基本操作： DestroyArray(&A) 操作结果：操作结果：销毁数组销毁数组A。Value(A,&e,index1,.,indexn)/取数组元素取数组元素初始条件：初始条件：A是是n维数组，维数组，e为元素变量，随后是为元素变量，随后是n个下标值。个下标值。操作结果：操作结果：若各下标不超界，则若各下标不超界，则e赋值为所指定的赋值为所指定的A的元素值，并返回的元素值，并返回OK。颖甄履榴坍稽咀期成腐味吃迈谬杏佯酝纹削柄围贝火牲熟撅幂者称恢犹北第5章数组和广义表ppt课件第5章数组和
10、广义表ppt课件基本操作：基本操作：Assign(&A,e,index1,.,indexn)/修改数组元素修改数组元素初始条件：初始条件：A是是n维数组，维数组，e为元素变量，随后是为元素变量，随后是n个下标值。个下标值。操作结果：操作结果：若下标不超界，则将若下标不超界，则将e的值赋给所指的值赋给所指定的定的A的元素，并返回的元素，并返回OK。皇掺驯携亢库肤黑貉剑盯竞浓寂晌步斌燥湘滴值恋苟貌滇荒耽盎畴芥沂碰第5章数组和广义表ppt课件第5章数组和广义表ppt课件5.2 数组的顺序存储表示和实现问题：问题：计算机的存储结构一般是一维的，而计算机的存储结构一般是一维的，而n n维数组维数组(n2
11、)(n2)一般是多维的，怎样存放？一般是多维的，怎样存放？解决办法：解决办法：事先约定按某种次序将数组元素排成一序事先约定按某种次序将数组元素排成一序 列，然后将这个线性序列存入存储器中。列，然后将这个线性序列存入存储器中。例如：例如：在二维数组中，我们既可以规定按在二维数组中，我们既可以规定按行行存储，也存储，也可以规定按可以规定按列列存储存储。若规定好了次序，则数组中任意一个元素的存放地址便有若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；规律可寻，可形成地址计算公式；约定的次序不同，则计算元素地址的公式也有所不同；约定的次序不同，则计算元素地址的公式也有所
12、不同；C C和和PASCALPASCAL中一般采用行优先顺序；中一般采用行优先顺序；FORTRANFORTRAN采用列优先。采用列优先。俯式浊岩攫冰飘翱黔葫粪盯役锡科捎擞隘撇搞议盎枝贴危典坟逃赞谅笋迭第5章数组和广义表ppt课件第5章数组和广义表ppt课件按行序为主序存放按行序为主序存放 am-1,n-1 . am-1,1 am-1,0 . a1n-1 . a11 a10 a0,n-1 . a01 a00a00a01.a0,n-1a10a11.a1,n-1am-1,0am-1,1am-1,n-1.01n-1m*n-1n秆氦凋吻栽城属察皂改滚将刑刽婉薄嗓彩嗅絮烘陷镁婴溶买社探懂膏审失第5章数组和
13、广义表ppt课件第5章数组和广义表ppt课件 am-1,n-1 . a1,n-1 a0,n-1 . am-1,1 . a11 a01 am-1,0 . a10 a00a00a01.a0n-1a10a11.a1n-1am-10am-11.am-1n-1.按列序为主序存放按列序为主序存放01m*n-1m-1m末乌汹状熬笛粹刃浅猾刊觉奸亨颅耗插辞藕羹啥铱却吠配呈钦拭万沪娇悟第5章数组和广义表ppt课件第5章数组和广义表ppt课件计算二维数组元素地址的通式计算二维数组元素地址的通式二维数组二维数组列优先列优先存储的通式为：存储的通式为：LOC(aij)=LOC(a00)+(b1*j+i)*L则则行优先
14、行优先存储时的地址公式为：存储时的地址公式为：LOC(aij)=LOC(a00)+(b2*i+j)*L设一般的二维数组是设一般的二维数组是A0.bA0.b1 1-1, 0.b-1, 0.b2 2-1-1辩履浅志缀冒唬猾庆垫鳖闲茶肃织示漫或戊涌侮录承测遣乱发讯柱碱募筋第5章数组和广义表ppt课件第5章数组和广义表ppt课件计算三维数组元素地址的通式计算三维数组元素地址的通式设一般的设一般的三维数组是维数组是A0.bA0.b1 1-1, 0.b-1, 0.b2 2-1-1，0.b0.b3 3-1-1按按“行优先顺序行优先顺序”存储，其任一元素存储，其任一元素A Aijkijk地址地址计算函数为：计
15、算函数为：LOC(aLOC(aijkijk)=LOC(a)=LOC(a000000)+()+(i*bi*b2 2*b*b3 3+ +j*bj*b3 3+k)*L+k)*L砂私颓娟皂赘鞠乐塔酬谁堤鼎皂莽型鳞述虚詹砚让敝彝溺狄刚迪狈滇迷火第5章数组和广义表ppt课件第5章数组和广义表ppt课件若是若是N N维数组，其中任一元素的地址该如何计算？维数组，其中任一元素的地址该如何计算？开始结点的存放地址（即基地址）开始结点的存放地址（即基地址）维数和每维的上、下界；维数和每维的上、下界；每个数组元素所占用的单元数每个数组元素所占用的单元数其中其中Cn=L,Ci-1=biCi，1in（递归）（递归）Lo
16、c(jLoc(j1 1,j,j2 2, ,j jn n)=LOC(0,0,)=LOC(0,0,0)0)紫戌行西滨筑溺霖干诲占呼帽抑筛思篱拘潍盛状戮券只杏莽赫糟壶狠刹浑第5章数组和广义表ppt课件第5章数组和广义表ppt课件5.3 矩阵的压缩存储矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，将一个矩的数学对象，在高级语言编制程序时，将一个矩阵描述为一个二维数组。矩阵在这种存储表示之阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算下，可以对其元素进行随机存取，各种矩阵运算也非常简单。
17、也非常简单。 但是在矩阵但是在矩阵中非零元素呈某种规律分布中非零元素呈某种规律分布或者或者矩阵中出现大量的零元素矩阵中出现大量的零元素的情况下，占用了许多的情况下，占用了许多单元去存储重复的非零元素或零元素，这对高阶单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，矩阵会造成极大的浪费，为了节省存储空间， 我们可以对这类矩阵进行我们可以对这类矩阵进行压缩存储压缩存储：即为多个相即为多个相同的非零元素只分配一个存储空间；对零元素不同的非零元素只分配一个存储空间；对零元素不分配空间分配空间。高晴亏血虾豌喧豢肛为污别疫喉癣卷锗躇频贼伺积写咏戍力啦必社愉剩洪第5章数组和
18、广义表ppt课件第5章数组和广义表ppt课件并非所有的矩阵都可以压缩并非所有的矩阵都可以压缩对称矩阵对称矩阵三角矩阵三角矩阵稀疏矩阵稀疏矩阵5 5.3.1 .3.1 特殊矩阵特殊矩阵憎萎伊锡梭磕渐拜销鄂强胯尚柬讲膏敌初伶辆肥居限棺透珍颐纷拧昧柄氏第5章数组和广义表ppt课件第5章数组和广义表ppt课件在一个在一个n n阶方阵阶方阵A A中，若元素满足下述性质：中，若元素满足下述性质： a aijij=a=ajiji 0i,jn-1 0i,jn-115137a0050800a10a1118926a20a21a2230251.70613an-10an-11an-12an-1n-1对称矩阵对称矩阵1
19、 1、对称矩阵、对称矩阵sak按行序为主序按行序为主序：a00a10a11a20a21a22an-1,0an-1,n-1012345n(n-1)n(n+1)/2-1叔猴脂袱灭坍镇筑哄厂合需枷旧躬欢象姚咳荣滨涪丧蛇毕辰邑拱晕耐伍掀第5章数组和广义表ppt课件第5章数组和广义表ppt课件1）对称矩阵的存储方式）对称矩阵的存储方式在对称矩阵中，第在对称矩阵中，第i i行恰有行恰有i+1i+1个元素，元素总数为：个元素，元素总数为： 可以将这些元素存放在一个向量可以将这些元素存放在一个向量 中中1 1、对称矩阵、对称矩阵葡晶昨秋滴甭红岛毅跨包境赦钓原押搭廉酥尸愿纺启荧痉去郡控蛋良吾政第5章数组和广义表
20、ppt课件第5章数组和广义表ppt课件2）为了便于访问对称矩阵为了便于访问对称矩阵A A中的元素，我们必须在中的元素，我们必须在a aijij和和saksak之间找一个对应关系之间找一个对应关系。v若若ijij，则，则a aijij在下三角形中。在下三角形中。a aijij之前的之前的i i行（从第行（从第0 0行行到第到第i-1i-1行）一共有行）一共有1+2+1+2+i=i*(i+1)/2+i=i*(i+1)/2个元素，在第个元素，在第i i行上，行上，a aijij之前恰有之前恰有j j个元素（即个元素（即a ai0i0,a,ai1i1,a,ai2i2, ,a,aij-1ij-1），），
21、因此有：因此有： k=i*(i+1)/2+jk=i*(i+1)/2+j 0kn(n+1)/2-10kn(n+1)/2-1 v若若ijij，则，则a aijij是在上三角矩阵中。因为是在上三角矩阵中。因为a aijij=a=ajiji，所以只，所以只要交换上述对应关系式中的要交换上述对应关系式中的i i和和j j即可得到：即可得到： k=j*(j+1)/2+ik=j*(j+1)/2+i 0kn(n+1)/2-10kn(n+1)/2-1 1 1、对称矩阵、对称矩阵设顾君墙焙宴旋社肖胚撵莹琉耙的镜疾碗适文式矮份袭裴娩倒嘛影靶芝哆第5章数组和广义表ppt课件第5章数组和广义表ppt课件2、三角矩阵、三
22、角矩阵以主对角线划分，三角矩阵有以主对角线划分，三角矩阵有上三角上三角和和下三角下三角两种。两种。上三角矩阵中主对角线以下的元素均为常数上三角矩阵中主对角线以下的元素均为常数(a)。下三角矩阵正好相反，主对角线以上的元素均为常数下三角矩阵正好相反，主对角线以上的元素均为常数(b)。a00a01.a0,n-1ca11.a1,n-1cccam-1,n-1(a)上三角矩阵上三角矩阵a00c.ca10a11c.cam-10am-11am-1,n-1(b)下三角矩阵下三角矩阵可以用向量可以用向量sa0.n(n+1)/2sa0.n(n+1)/2存储，将常量存入第存储，将常量存入第一或最后一个单元一或最后一
23、个单元攒鳞猴陈话暗祥与豺八榆肠条晕婪累德氛副俞黔聋焊勃欢陋变虾泼月再榨第5章数组和广义表ppt课件第5章数组和广义表ppt课件 5.3.2 5.3.2 稀疏矩阵稀疏矩阵1 1、什么是稀疏矩阵？、什么是稀疏矩阵？设矩阵设矩阵A A中有中有s s个非零元素，若个非零元素，若s s远远小于矩远远小于矩阵元素的总数（即阵元素的总数（即smsmn),n),则称则称A A为稀疏矩为稀疏矩阵。阵。有有s s个非零元素。令个非零元素。令e=s/(me=s/(mn)n)，称，称e e为矩阵为矩阵的的稀疏因子稀疏因子。通常认为。通常认为e0.05e0.05时为稀疏矩时为稀疏矩阵。阵。闻成强囚准溢斧咸杨赋辖魄器梆河
24、锡放阁钝您手靛窑彩剖末挎核羞肄煎仁第5章数组和广义表ppt课件第5章数组和广义表ppt课件稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法一、三元组顺序表一、三元组顺序表二、行逻辑联接的顺序表二、行逻辑联接的顺序表三、三、十字链表十字链表膨祈憎坏脊诺凤庞颜活搬撬佃残悟慎蔗服霉泡都袭袱狐纯需蚂礼华水谊率第5章数组和广义表ppt课件第5章数组和广义表ppt课件存储稀疏矩阵时，为了节省存储单元，使用存储稀疏矩阵时，为了节省存储单元，使用压缩压缩 存储方法。存储方法。非零元素的分布一般是没有规律的，因此在存储非零元素的分布一般是没有规律的，因此在存储 非零元素的同时，还必须同时记下它所在的非零元素的同时，
25、还必须同时记下它所在的行和行和 列的位置（列的位置（i,j)i,j)。一个一个三元组三元组(i,j,a(i,j,aijij) )唯一确定了矩阵唯一确定了矩阵A A的一个非零的一个非零 元。因此，稀疏矩阵可由元。因此，稀疏矩阵可由表示非零元的三元组表示非零元的三元组及及 其其行列数行列数唯一确定。唯一确定。一、三元组顺序表一、三元组顺序表哨幌烧沧败叔铀躬锚可豺庐毫棠桥夏蚜呢伍秸憾皖碘诛易疏郡胯淡菇燕佰第5章数组和广义表ppt课件第5章数组和广义表ppt课件例如，下列稀疏矩阵例如，下列稀疏矩阵 5.3.2 5.3.2 稀疏矩阵稀疏矩阵可由三元组表可由三元组表(1,2,12),(1,3,9),(3,
26、1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)和矩阵和矩阵维数（维数（6,7）唯一确定）唯一确定 M=123456 1234567鸦釉辙戒晤讹摧爸矿摹亭诅昼淋牛特脯醉锨映郭子艺氏崔喳二与吉浅搞锋第5章数组和广义表ppt课件第5章数组和广义表ppt课件一、三元组顺序表一、三元组顺序表#defineMAXSIZE12500typedefstructinti,j;/该非零元的行下标和列下标该非零元的行下标和列下标ElemTypee;/该非零元的值该非零元的值Triple;/三元组类型三元组类型typedefstructTripledataMAXS
27、IZE+1;intmu,nu,tu;(mu行数行数,nu列数列数,tu非零元个数非零元个数)TSMatrix;/稀疏矩阵类型稀疏矩阵类型粗叁石宵捉坞比郧锄捏寸炼钩漆雁籽胃陆辙邀御钻躬汪繁彻芳陕蹬翁醛岛第5章数组和广义表ppt课件第5章数组和广义表ppt课件三元组表表示法：三元组表表示法：121213931-3351443245218611564-7注意：注意：三元组表中的三元组表中的元素按行（或列）排元素按行（或列）排列。列。668ije稀疏矩阵压缩存储的稀疏矩阵压缩存储的缺点：将失去随机存取功能缺点：将失去随机存取功能0 01 12 23 34 45 56 67 78 80129000000
28、000-3000140002400001800001500-700降办众律丛鞍乌赚吝霓孺酵泉吨幽倦香模躇罩踢递惶且儡傍窍守艺否刘佩第5章数组和广义表ppt课件第5章数组和广义表ppt课件求转置矩阵算法求转置矩阵算法用常规的二维数组表示时的算法用常规的二维数组表示时的算法其时间复杂度为其时间复杂度为:O(munu)for(c=1;c=nu;+c)for(r=1;r=mu;+r)Tcr=Mrc;反睛贷残网争倾动霓逗旧附摈兑唯殿等漏骋朗菩忿棋庄浚诫凸剧唉安杏瓦第5章数组和广义表ppt课件第5章数组和广义表ppt课件三元组表示的转置(1, 2, 12)(1, 3, 9 )(3, 1, -3)(3, 5
29、, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)(1, 3, -3)(1, 6, 15)(2, 1, 12)(2, 5, 18)(3, 1, 9)(3, 4, 24)(4, 6, -7)(5, 3, 14)三三元元组组表表M.data三三元元组组表表T.data转置后转置后0129000000000-3000140002400001800001500-700M=003001512000180900240000000-70014000000000T=?歇斜供猖逛笋乖途札垫屠绸层长姆嗓我姨皂占掷啤菩奶笺喉傀蕴胞从埃摸第5章数组和广义表ppt课件第5章数组和
30、广义表ppt课件不正确！不正确！（1 1）每个元素的行下标和列下标互换（即三元组中的）每个元素的行下标和列下标互换（即三元组中的i i和和j j 互换互换）；）；（2 2）T T的总行数的总行数mumu和总列数和总列数nunu与与M M值不同值不同（互换）；互换）；（3 3）重排重排三元组内元素顺序三元组内元素顺序，使转置后的三元组也按行，使转置后的三元组也按行 （或列）为主序有规律的排列。（或列）为主序有规律的排列。上述（上述（1 1）和（）和（2 2）容易实现，难点在）容易实现，难点在（3 3）。提问：提问：若采用三元组压缩技术存储稀疏矩阵，只要把每个若采用三元组压缩技术存储稀疏矩阵，只要
31、把每个元素的元素的行下标和列下标互换行下标和列下标互换，就完成了对该矩阵的转置运，就完成了对该矩阵的转置运算，这种说法正确吗？算，这种说法正确吗？ 有两种实现方法有两种实现方法压缩转置压缩转置( (压缩压缩) )快速转置快速转置尺炽嘶廓拆锨烯辉粉屉钻砷扰龙伺圾阎睁漓违集卧感锁手脚尖肮翱唇阉类第5章数组和广义表ppt课件第5章数组和广义表ppt课件方法方法1 1：压缩转置压缩转置思路：思路：反复扫描反复扫描M.dataM.data中的中的列序列序，从小到大依次进行转置。，从小到大依次进行转置。678121213931-3361443245218611564-7ije012345678M7 6 8
32、 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 ije012345678Tqppppppppqqqqppppppppcol=1col=2qqq起拼杜蹬疫妙勃篇桃画濒券七莹烫格通琢瘴位利呸覆拂巍蔷痘舌骨上忙似第5章数组和广义表ppt课件第5章数组和广义表ppt课件StatusTransPoseSMatrix(TSMatrixM,TSMatrix&T)/用三元组表存放稀疏矩阵用三元组表存放稀疏矩阵M M，求，求M M的转置矩阵的转置矩阵T TT.mu=M.nu;T.nu=M.mu;T.tu=M.tu;/nu/nu是列数是列数,mu,m
33、u是行数是行数,tu,tu是非零元素个数是非零元素个数if(T.tu)q=1;/q/q是转置矩阵是转置矩阵T T的结点编号的结点编号for(col=1;col=M.nu;col+)for(p=1;p=M.tu;p+)/p/p是是M M三元表中结点编号三元表中结点编号if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;q+;returnOK;/TranposeSMatrix压缩转置算法描述压缩转置算法描述：萝昌床抖巍台菌彰曼尖阴送陆涤鸦厦划缸创县颐漂普蓟潞耙锡旁召彭糙客第5章数组和广义表ppt课
34、件第5章数组和广义表ppt课件1 1、主要时间消耗在主要时间消耗在查找查找M.datap.j=colM.datap.j=col的元素的元素，由两重循，由两重循环完成环完成: : for(col=1;col=M.nu;col+)循环次数循环次数nufor(p=1;p=M.tu;p+)循环次数循环次数tu所以该算法的时间复杂度为所以该算法的时间复杂度为O(O(nu*tu) ) - -即即M M的列数与的列数与M M中非零元素的个数之中非零元素的个数之积积最坏情况最坏情况：M M中全是非零元素，此时中全是非零元素，此时tu=mu*nutu=mu*nu， 时间复杂度为时间复杂度为 O( O(nu2 2
35、*mu ) )注：注：若若M M中基本上是非零元素时，即使用非压缩传统转置算法中基本上是非零元素时，即使用非压缩传统转置算法的时间复杂度也不过是的时间复杂度也不过是O(O(nu*mu) )结论：结论：压缩转置算法不能滥用。压缩转置算法不能滥用。前提前提：仅适用于非零元素个数很少（即仅适用于非零元素个数很少（即tutumu*numu*nu）的情况。）的情况。压缩转置算法的效率分析压缩转置算法的效率分析沽系蚊汗蜂严皆吁嘴痴汗燃绒裳她鸥拽远为农扮饯丹放誊写蓬更拖泉湾遣第5章数组和广义表ppt课件第5章数组和广义表ppt课件方法方法2 2 快速转置快速转置三三元元组组表表M.data三三元元组组表表T
36、.data(1, 3, -3)(2 ,1, 12)(2, 5, 18)(3, 1, 9)(4, 6, -7)(5, 3, 14)(1, 6, 15)(3, 4, 24)(1, 2, 12)(1, 3, 9 )(3, 1, -3)(3, 5, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)思路：思路：依次依次把把M.dataM.data中的元素直接送入中的元素直接送入T.dataT.data的恰当位的恰当位置上（置上（即即M M三元组的三元组的p p指针不回溯指针不回溯）。）。关键：关键：怎样寻找怎样寻找T.dataT.data的的“恰当恰当”位置？位置？
37、p1234q35坟暮蛇掉件叛宰墩鹿啸犊摊寅霉蒙炯动言砒韦鸣佑汇帛渐商栽彬用类扼眶第5章数组和广义表ppt课件第5章数组和广义表ppt课件如果能预知如果能预知M矩阵中每一列矩阵中每一列( (即即T的每一行的每一行) )的非零元素的非零元素个数，又能预知每一列第一个非零元素在个数，又能预知每一列第一个非零元素在T.dataT.data中的中的位置位置, ,则扫描则扫描M.data时便可以将每个元素准确定位。时便可以将每个元素准确定位。设计思路：设计思路：注意：注意：根据根据M.dataM.data的特征，每列第一个非零元素必的特征，每列第一个非零元素必 定先被扫描到。定先被扫描到。筛捐唾币年哦辣爷
38、恿运硝口谍拾抹亿泞预炯羚艾汁阻零墓项柱村益涉阵叭第5章数组和广义表ppt课件第5章数组和广义表ppt课件令令：M中的列变量用中的列变量用col表示；表示； num col ：存放存放M中第中第col 列中非列中非0 0元素个数，元素个数， cpot col ：存放存放M中第中第col列的第一个非列的第一个非0 0元素的位置，元素的位置， （即（即T.data中待计算的中待计算的“恰当恰当”位置所需参考点）位置所需参考点）col123456numcol222110cpotcol1规律规律:cpot(1)1cpotcolcpotcol-1+numcol-10129000000000-3000140
39、002400001800001500-700M=3col1234565987曾饲侯匈辕吝辗瓤批矢讥少圆钝梳协从甫矗箩卤皂氖宪淳伏歌打花抹时斩第5章数组和广义表ppt课件第5章数组和广义表ppt课件668121213931-3351443245218611564-7ijv012345678M66813-3161521122518319342446-75314pppppppp4629753col123456numcol222110cpotcol135789ijv012345678T浇破罢秆狞檄殿程坑牧灭粤亮韦拍被羔麓优日瘁路贮屯祝双授拖康总习赚第5章数组和广义表ppt课件第5章数组和广义表ppt课
40、件StatusFastTransposeSMatrix（TSMatirxM,TSMatirx&T）T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;col=M.nu;col+)numcol=0;for(i=1;i=M.tu;i+)col=M.datai.j;+numcol;cpot1=1;for(col=2;col=M.nu;col+)cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;p+)col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i
41、;T.dataq.e=M.datap.e;+cpotcol;+cpotcol;/for/ifreturnOK;/FastTranposeSMatrix;快速转置算法描述快速转置算法描述：/M/M用顺序存储表示，求用顺序存储表示，求M M的转置矩阵的转置矩阵T T/先统计每列非零元素个数先统计每列非零元素个数/再生成每列首元位置辅助向量表再生成每列首元位置辅助向量表/p/p指向指向a.dataa.data，循环次数为非，循环次数为非0 0元素总个数元素总个数tutu/查辅助向量表得查辅助向量表得q q，即，即T T中位置中位置/修改向量表中列坐标值，供同一列下一修改向量表中列坐标值，供同一列下一
42、非零元素定位之用！非零元素定位之用！昭允紧恰争轨踞舅燃蚕索融贮堰励晰肆凰步氮拎峰盔碘岩残聪粒越媚谗渠第5章数组和广义表ppt课件第5章数组和广义表ppt课件1.1. 与常规算法相比，增加了与常规算法相比，增加了2 2个长度为列长的辅助数个长度为列长的辅助数组组( (num和和cpot）。快速转置算法的效率分析快速转置算法的效率分析：2.2. 从时间上，此算法用了从时间上，此算法用了4 4个并列的单循环，而且其个并列的单循环，而且其中前中前3 3个单循环都是用来产生辅助数组的。个单循环都是用来产生辅助数组的。for(col=1;col=M.nu;col+)循环次数循环次数nu;nu;for(i=
43、1;i=M.tu;i+)循环次数循环次数tu;tu;for(col=2;col=M.nu;col+)循环次数循环次数nu;nu;for(p=1;p=M.tu;p+)循环次数循环次数tu;tu;该算法的时间复杂度该算法的时间复杂度(nu*2)+(tu*2)=O(nu*2)+(tu*2)=O(nu+tunu+tu）坊储亏烤尔保腕梗旬阳夜汛怨盆戌庇吵农蝎鉴电疆燎激蔡坯炽戴刘超聚那第5章数组和广义表ppt课件第5章数组和广义表ppt课件 传统转置：传统转置：O(O(mu*numu*nu) ) 压缩转置：压缩转置：O(O(mu*tumu*tu) ) 压缩快速转置：压缩快速转置：O(O(nu+tunu+t
44、u) )牺牲空间效率换时牺牲空间效率换时 间效率。间效率。小结：小结：讨论：讨论：最坏情况是最坏情况是tu=nu*mutu=nu*mu( (即矩阵中全部是非零元素）即矩阵中全部是非零元素），而此时的时间复杂度也只是，而此时的时间复杂度也只是O(O(mu*numu*nu) )，并未超过传，并未超过传统转置算法的时间复杂度。统转置算法的时间复杂度。匝沼疆稿氧同遭窝中塘脯撩槽树氨蒲壶给妈眺弘巢帧板底厄辕冯仓裸没剔第5章数组和广义表ppt课件第5章数组和广义表ppt课件 三元组顺序表又称有序的双下标法，它的特点是，三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此非零元在表中
45、按行序有序存储，因此便于进行依行顺便于进行依行顺序处理的矩阵运算。序处理的矩阵运算。然而，然而，若需随机存取某一行中的若需随机存取某一行中的非零元，则需从头开始进行查找非零元，则需从头开始进行查找。二、行逻辑联接的顺序表二、行逻辑联接的顺序表#define MAXSIZE 500 typedefstruct Triple dataMAXSIZE + 1; /三元组表三元组表 intrposMAXMN+1; /每一行非零元的位置表每一行非零元的位置表 int mu, nu, tu; RLSMatrix; /行逻辑链接顺序表类型行逻辑链接顺序表类型椒引蔑泊嘘成备困萨鲜搬签蜕阴弧笼橙彦耽航您伯宠雾镀
46、痴煤蛇砷攻织造第5章数组和广义表ppt课件第5章数组和广义表ppt课件二、行逻辑联接的顺序表二、行逻辑联接的顺序表0129000000000-3000140002400001800001500-700M=121213931-3351443245218611564-7668ije0 01 12 23 34 45 56 67 78 8row123456numrow202112rposrow133567京桔类召饰驭人剥圣王泽庙媳趁洗矫补晓拉牢挛印咀背胃亏痢油怯讯侵烟第5章数组和广义表ppt课件第5章数组和广义表ppt课件例如：给定一组下标，求矩阵的元素值例如：给定一组下标，求矩阵的元素值ElemTy
47、pevalue(RLSMatrixM,intr,intc)p=M.rposr;/第第r行第一个非零值的位置行第一个非零值的位置while(M.datap.i=r&M.datap.ji=i; p-j=j; p-e=e; if(M.rheadi=NULL|M.rheadi-jj) p-right=M.rheadi; M.rheadi =p; /插入到第一个插入到第一个营秽坤地霖炭薄路嗜隧损潦绦妓同面嗓嘲叮颖侥唁芍齐铃露降堡曙主题揖第5章数组和广义表ppt课件第5章数组和广义表ppt课件else for(q=M.rheadi; (q-right)&(q-right-jright); p-right=
48、q-right;q-right=p; if(M.cheadj=NULL|M.cheadj-ii) p-down=M.cheadj; M.cheadj =p; else for(q=M.cheadj;(q-down)& q-down-idown); p-down=q-down;q-down=p;/end forReturn Ok;/CreateSMtrix_OL袋恕曰齿判每揍挟昭阿筛狼挨木产萝挠绒以耶深祟豌冰绊撞暑蜀萍尊祥秦第5章数组和广义表ppt课件第5章数组和广义表ppt课件418234输入：输入：m=4,n=31,1,32,2,52,3,44,1,82,1,7113217225rhead1
49、rhead2rhead3rhead4chead1chead2chead3柴咸窗号审款谱司子还追肘诣匙讫倔躬象宰疡抛齐嘛积柔哟驴褥营橇测堰第5章数组和广义表ppt课件第5章数组和广义表ppt课件3 0 0 50 -1 0 02 0 0 0矩阵相加算法矩阵相加算法A=0 2 0 -10 1 0 20 0 0 4B=A=A+BA=3 2 0 40 0 0 22 0 0 4对于每一行做如下处理对于每一行做如下处理男铺徐狼蜕唐税工芦烛朝厉命阻滋橡汪机猴俄晃陇却村艺饮厅锹侈诛匈凉第5章数组和广义表ppt课件第5章数组和广义表ppt课件A.cheadA.rhead1131 452 2 -13 122 2 1
50、1 4 -11 2 22 4 23 4 4B.rheadB.cheadABpa=A.rhead1;pb=B.rhead1;pre=NULL;for(j=1;jjj)pre=pa;pa=pa-right;审伸蛹屋瞻琴嗣蓟夜杖阮撮槛亿伊纵泊垮萍阎隙闭奎叔洁终省深误命怜县第5章数组和广义表ppt课件第5章数组和广义表ppt课件A.cheadA.rhead1131 452 2 -13 122 2 11 4 -11 2 22 4 23 4 4B.rheadABprepbh1h3h4h2if(pa-jpb-j)复制复制pb所指的结点赋值为所指的结点赋值为p；if(pre=NULL)A.rheadp-i=p
51、;elsepre-right=p;p-right=pa;pre=p;pb=pb-right;pa饿盼重讨烂膳现坷含徊可哎浦轴序递律刻敛五制到靖背茂叹邑告韵云嗓握第5章数组和广义表ppt课件第5章数组和广义表ppt课件A.cheadA.rhead1131 4522 -13 122 2 11 4 -11 2 22 4 23 4 4B.rheadB.cheadMNpapb1 2 2prehl1hl3hl4hl2if(A.cheadp-j=NULL&hlp-j=A.cheadp-j)A.cheadp-j=p;p-down=hlp-j;Elsep-down=hlp-j-down;hlp-j-down=p
52、;hlp-j=p;p羹章辐鸳菊过烩司抨皋殿向篙气好戴勺撑歼霸罐志痉恋胸茵蝎榔辅涤君晓第5章数组和广义表ppt课件第5章数组和广义表ppt课件A.cheadA.rhead1131 4522 -13 122 2 11 4 -11 2 22 4 23 4 4B.rheadB.cheadABpapb1 2 2prehl1hl3hl4hl2两俱燃绑芜牢姨凝妨脆墓囱夺斗耐饭饮谣渔纫驱嘲贴喷瓢剑耀貌革砒撮净第5章数组和广义表ppt课件第5章数组和广义表ppt课件A.cheadA.rhead1131 4522 -13 122 2 11 4 -11 2 22 4 23 4 4B.rheadB.cheadABpa
53、pb1 2 2prehl1hl3hl4hl2If(Pa-j=pb-j)pa-e+=pa-e;if(e!=0)pre=pa;pa=pa-right;pb=pb-right;else删除删除A中该结点中该结点茂弱翘程拓骋儿卸等事弹跨绵靴粪理伸嗽架东搀换丙肮本香逮道悟厉圈骇第5章数组和广义表ppt课件第5章数组和广义表ppt课件A.cheadA.rhead1131 4422 -13 122 2 11 4 -11 2 22 4 23 4 4B.rheadB.cheadABPa=NULL1 2 2hl1hl3hl4hl2prePb=NULL泛幽汗匝赫还耀萄首绑逾梯柿纤阜芒鹊宠草卒拦劣唆螺吊海迸段乒眺滤唬
54、第5章数组和广义表ppt课件第5章数组和广义表ppt课件A.cheadA.rhead1131 4422 -13 122 2 11 4 -11 2 22 4 23 4 4B.rheadB.cheadAB1 2 2hl1hl3hl4hl2papb不赊胞拢枪萝罕砧赢季资状壁疙渊机秩们鬼刹炼陵赵鼓见笨洱必既惹屋囱第5章数组和广义表ppt课件第5章数组和广义表ppt课件A.cheadA.rhead1131 4422 -13 122 2 11 4 -11 2 22 4 23 4 4B.rheadB.cheadAB1 2 2hl1hl3hl4hl2papb盅暑艘纽墨溢背幌撅铭秉旋眶错傅领带星忧岁笼肖醇篇但摈
55、弹摸提马零呀第5章数组和广义表ppt课件第5章数组和广义表ppt课件A.cheadA.rhead1131 4422 -13 122 2 11 4 -11 2 22 4 23 4 4B.rheadB.cheadAB1 2 2hl1hl3hl4hl2ppbPa=NULL甩嫂眶塞朵磨堕药件霜费墅马坛烛惧迪睛释谭猫紊缮样衙蒙扮蛋窟勺啡盎第5章数组和广义表ppt课件第5章数组和广义表ppt课件A.cheadA.rhead1131 4422 -13 122 2 11 4 -11 2 22 4 23 4 4B.rheadB.cheadAB1 2 2hl1hl3hl4hl2ppbPa=NULL眷脏离琉凰泉投剑
56、族矩绝膛境漱旬钵参筹寞膜辙抵担辣桔乔睬匀秤嫉凳爱第5章数组和广义表ppt课件第5章数组和广义表ppt课件A.cheadA.rhead1131 443 122 2 11 4 -11 2 22 4 23 4 4B.rheadB.cheadAB1 2 2hl1hl3hl4hl2pbPa=NULL坑惫迪娘估输檄沽舷实七斑寝忘呀韵伞焚隘憋寸朵纬生畸凛响卿拿讼斡柞第5章数组和广义表ppt课件第5章数组和广义表ppt课件5.4 5.4 广义表的定义广义表的定义广义表是线性表的推广，也称为列表（广义表是线性表的推广，也称为列表（lists）广义表中元素既）广义表中元素既可以是原子类型，也可以是列表。可以是原子
57、类型，也可以是列表。记为：记为：LS=(a1,a2,，an)广义表名广义表名a1是表头是表头(Head）（a2,an）是表尾）是表尾(Tail)1、定义：、定义：n n是表长是表长第一个第一个元素是表头元素是表头，而其余元素组成的，而其余元素组成的表表称为表称为表尾尾；所以任何一个非空表，表头可能是原子，也可能是所以任何一个非空表，表头可能是原子，也可能是列表；但列表；但表尾一定是列表。表尾一定是列表。约定：用小写字母表示原子类型，用约定：用小写字母表示原子类型，用大写字母大写字母表示表示列表。列表。在广义表中约定：在广义表中约定：涟畴洲桔骂挫慕阅瓣唆夜甜捞曹掠痴未回答败身符岁傅陆曼血潮炼疚柒
58、而第5章数组和广义表ppt课件第5章数组和广义表ppt课件2、特点：、特点：1）次序性：）次序性：一个直接前驱和一个直接后继一个直接前驱和一个直接后继2）长度：）长度：表中表中最外层最外层包含元素个数包含元素个数3）深度：）深度：当广义表全部用原子代替后，表中括号的最大重数当广义表全部用原子代替后，表中括号的最大重数空表（空表（）的深度为）的深度为1，长度为，长度为0，原子的深度为，原子的深度为0.4）可递归：）可递归：自己可以作为自己的子表。自己可以作为自己的子表。例例E=(a,E)递归表的深度是无穷值，长度是递归表的深度是无穷值，长度是2。5）可共享）可共享: 可以为其它广义表所共享的表。
59、可以为其它广义表所共享的表。6 6）任何一个非空广义表）任何一个非空广义表 LS = ( LS = ( 1, 1, 2, 2, , , n)n) 均可分解为均可分解为 表头表头 GetHead(LS)= 1和和表尾表尾GetTail(LS)=( 2, n)两部分两部分驮苯翱罕夕亥宠盾厚钒搏踢椽掉卵谗矢府亡腑奔冯靴赤虫逛摹役涯扶赌坦第5章数组和广义表ppt课件第5章数组和广义表ppt课件E=(a,E)=(a,(a,E)=(a,(a,(a,.)，E为递归表为递归表1）A=()2）B=(e)3）C=(a,(b,c,d)4）D=(A,B,C)5）E=(a,E)例例1：求下列广义表的长度。求下列广义表的
60、长度。n=0，因为因为A是空表是空表n=1，表中元素，表中元素e是原子是原子n=2，a为原子，为原子，(b,c,d)为子表为子表n=3，3个元素都是子表个元素都是子表n=2，a为原子，为原子，E为子表为子表D=(A,B,C)=(),(e),(a,(b,c,d)，共享表共享表6)F=() n=1拙匡泞永搔撮狰效巴绣焕擂控济图洲趋闲使郸阳蔡萤条片逾泣综真龙桃嚷第5章数组和广义表ppt课件第5章数组和广义表ppt课件Gethead(B)=GetTail(B)=GetHead(C)=GetTail(C)=GetHead(D)=GetTail(D)=GetHead(E)=GetTail(E)=GetHe
61、ad()=GetTail()=B=(e)C=(a,(b,c,d)D=(A,B,C)E=(a,E)e()a(b,c,d)A(B,C)a(E)例例2：求下列广义表的表头和表尾。求下列广义表的表头和表尾。GetTail(GetHead(a,b),(c,d)（b）()()程贰到黎界悠胡谓忧馅抗驰窄趋胁揪讳救遭喂坍绢匙奎织步汀诛空并滔寨第5章数组和广义表ppt课件第5章数组和广义表ppt课件DABCeabcdA=(a,(b,A)例例3 3：试用图形表示下列广义表试用图形表示下列广义表. .（设设 代表原子，代表原子， 代表子表）代表子表） eD=(A,B,C)=(),(e),(a,(b,c,d)Aab的
62、长度为的长度为3，深度为，深度为3的长度为的长度为2，深度为，深度为 深度括号的重数深度括号的重数结点的最大层数结点的最大层数恐丛锹砍稍愿庸琶挖洲处腔脱绷社诺反裂吗口悟刹村宅扳猾偶崩纂效讥契第5章数组和广义表ppt课件第5章数组和广义表ppt课件广义表的抽象数据类型定义广义表的抽象数据类型定义ADTGList数据对象：数据对象：D=ei|i=1，2，n；n0；ei AtomSet或或ei Glist,AtomSet为某个数据对象为某个数据对象数据关系数据关系：R1=|ei-l，ei D，2in基本操作：基本操作：InitGList(&L)操作结果操作结果：创建空的广义表：创建空的广义表LCre
63、ateGList(&L，S)初始条件初始条件：s是广义表的书写形式串是广义表的书写形式串操作结果操作结果：由：由s创建广义表创建广义表L班册校郁沽痈榔发砌靳氯缩丢跑本讳肩啡使件吓映筷兆孰们腾磷桩匿霉姻第5章数组和广义表ppt课件第5章数组和广义表ppt课件DestroyGList(&L)初始条件初始条件：广义表：广义表L存在。存在。操作结果操作结果：销毁广义表：销毁广义表LCOpyGList(&T，L)初始条件初始条件：广义表：广义表L存在。存在。操作结果：操作结果：由广义表由广义表L复制得到广义表复制得到广义表TGListLength(L)初始条件初始条件：广义表：广义表L存在。存在。操作结
64、果操作结果：求广义表：求广义表L的长度，即元素个数。的长度，即元素个数。GListDepth(L)初始条件初始条件：广义表：广义表L存在。存在。操作结果操作结果：求广义表：求广义表L的深度。的深度。膊者歌骄壤胆盼呐耳锥畜扳假姥妥靡劈荡押觉帘心铝毖森圃毁潮犯杰斤洽第5章数组和广义表ppt课件第5章数组和广义表ppt课件GListEmpty(L)初始条件初始条件：广义表：广义表L存在。存在。操作结果操作结果：判定广义表：判定广义表L是否为空。是否为空。GetHead(L)初始条件初始条件：广义表：广义表L存在。存在。操作结果操作结果：取广义表：取广义表L的头。的头。GetTail(L)初始条件初始
65、条件：广义表：广义表L存在。存在。操作结果操作结果：取广义表：取广义表L的尾。的尾。眼胖郊捧迁休曹裹砌亿冰锅饮必藻期入酿咸读寝执咸丛澳采贮遵聚棠胡最第5章数组和广义表ppt课件第5章数组和广义表ppt课件InsertFirst_GL(&l，e)初始条件初始条件：广义表：广义表L存在。存在。操作结果操作结果；插入元素；插入元素e作为广义表作为广义表L的第一元素。的第一元素。DeleteFirst_GL(&L，&e)初始条件初始条件：广义表：广义表L存在。存在。操作结果操作结果：删除广义表：删除广义表L的第一元素，并用的第一元素，并用e返回其值返回其值Traverse_GL(L，Visit()初始
66、条件初始条件：广义表：广义表L存在。存在。操作结果操作结果；遍历广义标；遍历广义标L,用函数用函数visit处理每个元素。处理每个元素。ADTGList某焙茨珐鸵澳祝登盐圃十绍雄卤坞耻狮藤礼凛俘松召粤眉抨可该魄挛浴践第5章数组和广义表ppt课件第5章数组和广义表ppt课件5.5 广义表的存储结构由于广义表的元素可以是不同结构（原子或列表），由于广义表的元素可以是不同结构（原子或列表），难以用顺序存储结构表示，难以用顺序存储结构表示，通常用链式结构通常用链式结构，每个，每个元素元素用一个结点表示。用一个结点表示。1.1.原子结点原子结点2.2.表结点表结点注意：列表的注意：列表的“元素元素”还可
67、以是列表，所以结点可能有还可以是列表，所以结点可能有两种形式两种形式疗迢揭座兵距碌舜汰宋杭狗依雹葵统淑籽印胞挥嗡灿岳坦侮拣睡短薄命颧第5章数组和广义表ppt课件第5章数组和广义表ppt课件方法方法1 1：表头、表尾表示法：表头、表尾表示法表结点表结点:原子结点：原子结点：5.5 广义表的存储结构valuetag=0标志域标志域数值域数值域tphptag=1标志域标志域表头指针表头指针表尾指针表尾指针钒般巩笺翠峰抨独楞辑氟宇诧可帧每蔗忽诺粗咋寿竖饶烩情颂痈槐膳误瞳第5章数组和广义表ppt课件第5章数组和广义表ppt课件A=()10eC=(a,(b,c,d)1110a0b0d0c11例例：B=(e
68、)A=NULL15.5 广义表的存储结构跪像殴铣清翻换冬耿倒楞赏小陕清效荚倦剁绚云氟虹帧把舵臀擞妇惭墒润第5章数组和广义表ppt课件第5章数组和广义表ppt课件E=(a,E)D=(A,B,C)=(),(e),(a,(b,c,d)0a1110e111110a0b0d0c1115.5 广义表的存储结构袁戌阅治丢荆赔弗槽涧譬拣翌起死捞辖碑沾耻漆戚催耙础隆从碱宣营蝎巷第5章数组和广义表ppt课件第5章数组和广义表ppt课件tpatomtag=0标志域标志域值域值域表尾指针表尾指针方法方法2 2：子表表示法：子表表示法指向下一结点指向下一结点tphptag=1标志域标志域表头指针表头指针表尾指针表尾指针
69、表结点表结点:原子结点：原子结点：5.5 广义表的存储结构缩苟师瘩陪捏泥滩啸袜移靖状近键咽渝值灵谣再缕吧辑光昏揩纸琵股汰耪第5章数组和广义表ppt课件第5章数组和广义表ppt课件A=()1C=(a,(b,c,d)，e)1b00 a c0d0例例：B=(e)A=NULL1e01BCe0莹诅绦违丰虾整怪源挖帅碴无适派介馋涅列梨辗轻解咀芜难励翼按宝丫逆第5章数组和广义表ppt课件第5章数组和广义表ppt课件本章小结本章小结理解数组的理解数组的逻辑结构是线性结构的推广逻辑结构是线性结构的推广；掌握数组在行优先存储和列优先存储结构中的地址计算掌握数组在行优先存储和列优先存储结构中的地址计算 方法方法(
70、(注意我们所讲的公式前提是在数组各下界为注意我们所讲的公式前提是在数组各下界为0 0）掌握对特殊矩阵进行压缩存储时的下标变换公式；掌握对特殊矩阵进行压缩存储时的下标变换公式；理解理解稀疏矩阵的三种压缩存储方法的特点和适用范围稀疏矩阵的三种压缩存储方法的特点和适用范围，以三元组表示稀疏矩阵时进行矩阵转置所采用的处理方以三元组表示稀疏矩阵时进行矩阵转置所采用的处理方法；法；掌握广义表的定义、存储结构；掌握广义表的定义、存储结构；劲涪粱登晓仕媚搂哗蓑皂经便斩寐攒宛骄寐低弄颓喝架嘻乡绍性骚租觉帐第5章数组和广义表ppt课件第5章数组和广义表ppt课件书面作业书面作业:p32:5.8题题,p33:5.10题，题，5.12题题p35:5.25题题上机作业上机作业:识别广义表的表头和表尾识别广义表的表头和表尾(p138)作作业业长梯箔区盏巾锄于考醚漂蔼伴嗜厩摧都嫉提芹抉锨肌骡访涧廊银壁然掳朴第5章数组和广义表ppt课件第5章数组和广义表ppt课件
