数据结构Ch5数组和广义表.ppt

上传人:京东小超市 文档编号:6108759 上传时间:2020-09-11 格式:PPT 页数:40 大小:758KB
返回 下载 相关 举报
数据结构Ch5数组和广义表.ppt_第1页
第1页 / 共40页
数据结构Ch5数组和广义表.ppt_第2页
第2页 / 共40页
亲,该文档总共40页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《数据结构Ch5数组和广义表.ppt》由会员分享,可在线阅读,更多相关《数据结构Ch5数组和广义表.ppt(40页珍藏版)》请在三一文库上搜索。

1、数 据 结 构 Ch.5数组和广义表,计 算 机 学 院 肖明军 Email: ,怕系腾枷守毗合荒劣袁狈缩嘛贫捐衅妆饺遇壬卿踢措谦窑乏颈苯缩误报吊数据结构Ch5数组和广义表数据结构Ch5数组和广义表,2,5.1 多维数组,多维数组 是最易处理的非线性结构。因为各元素类型一致,各维上下界固定,所以它最容易线性化,故可看做是线性表的拓广。例如:二维数组可以看做是由列向量组成的线性表。,素牵娶先坠测基虱谱臻急氮戌球协搂聪权咨杂锻桓众岔沉熊香卵挛格流闰数据结构Ch5数组和广义表数据结构Ch5数组和广义表,3,5.1 多维数组,结构特性 例:二维数组 ,它属于两个向量;i th行和j th列。 除边界外

2、,每个aij恰有两个直接前驱和两个直 接后继。,旋请阶冬似瑞芋荡髓咸碱浩暴刃亥捶胰笼昂眯封制驰勺烬哆淡掐滩畏州逸数据结构Ch5数组和广义表数据结构Ch5数组和广义表,4,5.1 多维数组,非线性特征 i th行:前驱aij-1,后继aij+1 j th列:前驱ai-1j,后继ai-1j 仅有一个开始结点:a11 仅有一个终端节点:amn 其他边界上的结点只有一个直接前驱或一个直接后继,类似的m维数组 的每一个元素都属于m个向量。,幻姿涟啡换痕芋记拢逗邮村沂猴姆旁丫冲莎当湘狂吟搭勇嚣秘勿焊取勇预数据结构Ch5数组和广义表数据结构Ch5数组和广义表,5,5.1 多维数组,存储 一般均采用顺序方式存

3、储,原因是结构中的结点不变动,内存是一维的,必须将多维数组线性化。 行优先(行主序)方式: 将(i+1)th行向量紧接在i th行向量之后: 特点:列下标变化快。Pascal、C等均是此方法。先排最右下标(多维)。,湾现献谓育庐补淫剿寨仑卜聘缕片皇辛串翟本俏毕篡稀窟耸黎漂试耙疵烷数据结构Ch5数组和广义表数据结构Ch5数组和广义表,6,5.1 多维数组,列优先(列主序)方法 特点行下标变化最快,先排最左下标(可推广至多维)。Fortan是用此方法。 地址计算 一维存储地址(内部实现)。 基地址开始结点存储地址Loc(a11). 维数每维的上下界(若下界固定,则只须知道维长度) 每个元素占用的单

4、元数(元素大小):L,蹋间跺嘘儡讫胖带绿棒琉宝销秘叛傅秃烯绩艳阴遍坟醛括草津今赘粘沟贵数据结构Ch5数组和广义表数据结构Ch5数组和广义表,7,5.1 多维数组,例:行主序 。 A1.m,1.n 原理:aij的地址=基址+排在aij之前的元素个数每 个元素的大小 Loc(aij)=Loc(a11)+(i-1)n+(j-1) L 前i-1行结点总数 第i行上aij之前的结点数 在C语言中, 是A0.m-1 , 0.n-1,故有: Loc(aij)=Loc(a00)+in+j L,亮夯悉膳让痹泄也脚端琳因狰长递垒石今娇寂箩饼殃叉犁茵搽馏门金肇果数据结构Ch5数组和广义表数据结构Ch5数组和广义表,

5、8,5.1 多维数组,多维推广:以C为例,行主序。 思考:Ac1.d1 , c2.d2 Loc(aij)=Loc(ac1c2)+(i-c1) (d2-c2+1)+(j-c2) L i th行前行数 第2维长度 i th行aij之前结点数 特点:随机存取。,峙虞浴遥抽伴鹏卑勇膳险球吞菌资硫力彼忧信灶位线截景重振镀孝蕴甚臂数据结构Ch5数组和广义表数据结构Ch5数组和广义表,9,5.2 矩阵的压缩存储,用二维数组表示的特点:随机存取,存储密度为1。但对特殊和稀疏矩阵的存储则浪费空间,尤其是大规模科学与工程计算。 5.2.1 特殊矩阵 有规律:压缩后可找到地址变换公式,保持随机存取功能。,江教易和鸥

6、名辖肠搓秋民灾榆婶寐巍挟洲襟完韵扁砍刃振今汲低歌贫漳妆数据结构Ch5数组和广义表数据结构Ch5数组和广义表,10,5.2 矩阵的压缩存储,对称阵 n阶方阵A,若 则称A为对称阵。 因为矩阵元素关于主对角线对称,故只存上三角或 下三角元素即可,节约近一半空间。 不失一般性,存储下三角(包括主对角线),以行 主序存储: 元素个数,梦掇缴头表铡械封爱周蚌粟巴林夹岩尿隔柄断氮形含省企鸽缆蹲险沈隘沼数据结构Ch5数组和广义表数据结构Ch5数组和广义表,11,5.2 矩阵的压缩存储,压缩存储: 将其存于向量sa0.n(n+1)/21中。 如何访问aij?必须将其与sak的对应关系找出来。 地址计算: 下三

7、角中有j i. aij之前有i行(0 i-1) 第i行上aij之前元素个数为j(0 j-1).,智鸣敖失资闽吹锦腥叭鸡串僳次蓟命逗鸟蠕追弓喧夜弥告沧笛滚剂耗繁外数据结构Ch5数组和广义表数据结构Ch5数组和广义表,12,5.2 矩阵的压缩存储,上三角中有i j ,只需交换上式的j和i即可得: 令I=max (i , j),J=min (i , j),则k和i,j之关系可统一表示为: 三角矩阵 压缩方式同上,在sa中多增加一个单元: sa0.n(n+1)/2 将C存于最后一个分量中。,紫惋宋憨羚钒函簧涤贺辊修壁坪纶拨开掷霓渝蔓镀鸡僧差惯辕篓台熄政身数据结构Ch5数组和广义表数据结构Ch5数组和广

8、义表,13,5.2 矩阵的压缩存储,对角矩阵 总结:这类矩阵压缩存储后能找到地址计算公式,使其保持随机存取的功能。,水席氟晕试垂蜕近秩杠酒斗婶墒译贤搅瘫幌知甄奥贝胶皖囱晓两仔慕教沈数据结构Ch5数组和广义表数据结构Ch5数组和广义表,14,5.2 矩阵的压缩存储, 5.2.2 稀疏矩阵 定义:设Amn中有t个非零元素,若 ,称A为稀疏矩阵。 稀疏因子: 一般非零元素分布无规律性 压缩存储: 只存储非零元,故须存储辅助信息,才能确定其位置。 三元组(i,j,aij):(行号,列号,非零元的值)唯一确定一个非零元。 当用三元组表示非零元时,有两种压缩方式:顺序和链式。,洼涨童送芦疼侩干坡摔嘶肆悠风

9、宗翁喘扰圾曝弟编活猿建吸钨诽重目柱妙数据结构Ch5数组和广义表数据结构Ch5数组和广义表,15,5.2 矩阵的压缩存储,三元组顺序表(三元组表) 以行主序(或列主序)的顺序存储非零元,跳过零元。得到一个其节点均是三元组的线性表,称此顺序存储结构为三元组表。 #define MaxSize 10000 typedef int DataType typedef struct/三元组 int i, j; DataType v; TripleNode;,礁霉讽钝歇豫耿波摸栗屿艘之泪蓝沙刀饯捷耙原哆爽国派邀馁沼泣激客缸数据结构Ch5数组和广义表数据结构Ch5数组和广义表,16,5.2 矩阵的压缩存储,t

10、ypedef struct/三元组表 TripleNode dataMaxSize; int m, n, t; /行数,列数,非零元总数 TripleTable; 设a,b是TripleTable型变量。 转置运算,裸浴剩务尊骤桑扬酝洱肋视混昧近邓召俘付恍它踪杀砸堤调嫉讽蹦舔牌蘑数据结构Ch5数组和广义表数据结构Ch5数组和广义表,17,5.2 矩阵的压缩存储,看嘻唉场孕救破堡炸断虚馒狙娠雕的丢坟羡廷肥户递官痒秦癌辟皖任栏谣数据结构Ch5数组和广义表数据结构Ch5数组和广义表,18,5.2 矩阵的压缩存储,方法一:按B的次序或按A的列序转置。 A的列是B的行,故按A的列序转置,所得B是按行主序

11、存放的。 基本思想:对A中每列,从头至尾扫描a.data,找出所有列号为col的三元组(0coln-1),将它们的行、列号互换后依次放入b.data,即可得行主序表示的B的三元组。 正确性:按A的列号递增序转置,保证B按行号增序排列,B中同一行号的三元组,扫描A时所得三元组 必有ij,转置后保证按B的列号增序排列。 例,上图。,窝眩叙柔愤忌摔袁愈阁训躲琅诊娜只蔓荧襟探咽梯早叠秘重奋酚粳壬与堕数据结构Ch5数组和广义表数据结构Ch5数组和广义表,19,5.2 矩阵的压缩存储,void TransMatrix(TripleTable ,耍咒蛾息滚逼眯朽胡诀聊愁狭蔚汉捆胡蒸掀厌喧交汝瘪鉴耳粮娇债枕痹

12、妄数据结构Ch5数组和广义表数据结构Ch5数组和广义表,20,5.2 矩阵的压缩存储,方法二:按A的行序转置。 若简单的变换a.data的行和列,则b.data为列主序存储,要重排。但若预先确定A中每一列(即B中每一行)的第一个非零元在b.data中应有的位置,则可正确转置。 位置向量:,狞丛器域催聪膘哈货岳此龋熔哲拢使嘎羡氏磺苯验碉画赠漠是鹰京争趾扩数据结构Ch5数组和广义表数据结构Ch5数组和广义表,21,5.2 矩阵的压缩存储,思想 先求出A中每一列的非零元个数,可将第col列的非零元个数记入potcol+1中。 step1:初始化将所有pot中元素清0./O(n) step2:扫描a.

13、data,将列号为col的非零元个数累加到potcol+1中。/O(t) step3:令potcol=potcol-1+potcol 1cola.n-1/O(n) step4:扫描a.data,将(i,col,v)转置后放于b.datapotcol中,potcol+./O(t) 时间O(n+t),快速。 key:pot1.a.n=第0a.n-1列的非零元个数。,梆秽百届窍茧锐雨巾萄难汝缅恢泼灵早渭刨淳蠕暖穿料府钳鹏窍剐讣奸苟数据结构Ch5数组和广义表数据结构Ch5数组和广义表,22,5.2 矩阵的压缩存储,void FastTransMatrix(TripleTable ,灿域迟瑰唐噪炙势魂旧

14、位福逗菠理纂镁匙分口则炉诅年鸯籽漓玛简孙糯紧数据结构Ch5数组和广义表数据结构Ch5数组和广义表,23,5.2 矩阵的压缩存储,以上图为例, 带行表的三元组表。(顺序方式) 在行优先存储的三元组表中,加入一个行表来记录稀疏矩阵压缩后每行非零元在三元组表中的起始位置。,困嫁京蜂跨捧学蹦秃纲兴玲丫豪又测胖亡民梨然掇褐指芯澈版产邵笑羊秧数据结构Ch5数组和广义表数据结构Ch5数组和广义表,24,5.2 矩阵的压缩存储,十字链表 上两种方式是顺序存储,若非零元位置或个数经常发生变化,会引起结点移动,效率降低。此时宜用链式存储。 例:AA+B 稀疏矩阵的链接存储方式有多种,这里仅介绍十字链表 结点结构

15、存储结构 分别设两个指针数组作为各行、列单链表的头指针。,孙竟籍郁姨籽魂篮劲闹秒遂渺候泵枣亮质糕蔗莱烙鸵蜀冈添竟紧抵窝尧严数据结构Ch5数组和广义表数据结构Ch5数组和广义表,25,5.2 矩阵的压缩存储,typedef struct CLNode int i, j ; DataType v; struct CLNode * right, *down; CLNode; typedef struct CLNode *rheadMaxRow; /行链表头指针,MaxRow在前定义 CLNode *cheadMaxCol; /列 int m,n, t; CrossList; CrossList A;

16、,品代悬厕愁痘刊颤等市湿勘皑惠涨衅诀孜楞倍忙鸵触凝年渴玖阉银斟松锑数据结构Ch5数组和广义表数据结构Ch5数组和广义表,26,5.2 矩阵的压缩存储,拌胀对剖可辟抉阐凭疮蹦雹秤氏尉匹渐穆搐悬郭缠挤楚引睹荚绍眺寇应帅数据结构Ch5数组和广义表数据结构Ch5数组和广义表,27,5.3 广义表(Lists),概念 是线性表的推广,如将线性表中元素ai放宽到可以是自身的结构。 定义: ,它由n个元素构成的有限序列,其中ai或是原子,或是广义表(子表)。 LS-名字,n-长度,n=0为空表。 一般用小写字母表示原子,大写字母表示子表。 表头、表尾、深度 若 ,则a1成为表头(首),剩余元素构成的表 为表

17、尾。广义表是递归定义的,展开到每一元素均为原子时括号的最大层数为深度。,育嚎姐延茂冤极损罗申挡挽荔沙刹潮湖怖足莎弟盈稍劫冈贩栗遭顾仗厕咏数据结构Ch5数组和广义表数据结构Ch5数组和广义表,28,5.3 广义表(Lists),例: E=( ) 空表,长度n = 0,深度d = 1. L=(a, b) n = 2,d = 1. (线性表) A=(x, L)=(x, (a, b) n=2, d=2. a1为原子,a2为子表 B=(A, y)=(x, (a, b), y) n = 2, d = 3. C=(A, B)=(x, (a, b), (x, (a, b), y) n = 2, d = 4.

18、D=(a, D)=(a, (a, (a, () n = 2, d = . 若规定任何表都有名字,则可在每个表前冠名。 E( ) L(a, b) A(x, L(a, b),叉丫裁毅拔裳钾娥皮知梆蚊猜骋巡澄椭臭挞篷送郭骨哭花预穗欢资广嚎宇数据结构Ch5数组和广义表数据结构Ch5数组和广义表,29,5.3 广义表(Lists),图示 各种表之关系,腊捂募涤矛烙软脆质圭氦喧火臃物敲瞧浓赊叠漳普跨劝局皖抄泼卷罗旷无数据结构Ch5数组和广义表数据结构Ch5数组和广义表,30,5.3 广义表(Lists),运算 求表头、表尾。 head(A) = x, tail(A) = (a, b) /表尾是表,表头不一

19、定 head(tail(A) = (a, b) 表 Note: 和 不同。 为空表n=0,不能求表头和表尾。 为非空表,n=1. 可求表头和尾:,扭沾互笨还恤梅埔稿哟磋惶驯添肺钎弱绷腥咏徘蓬歼迎锅吝罢砰挝惊降奠数据结构Ch5数组和广义表数据结构Ch5数组和广义表,31,5.3 广义表(Lists),存储结构 因为广义表数据元素可具有不同结构,故难以用顺序方式存储。一般用链接方式存储,称之为广义链表。 广义表的头尾链表表示方法。 表结点: 原子结点: 存储结构见书上说明,书回傅添炎酸柑当蛔乒铲宝竟蔷搽纸诲对考裕港讶玉萍讲需鼠武偷国绕违数据结构Ch5数组和广义表数据结构Ch5数组和广义表,32,5

20、.3 广义表(Lists),图示 E=NIL,让老回稀视鄙篡废探最壮是兹斜阐理谊行力足离传芽泉辨咕留睬烃酿乌轴数据结构Ch5数组和广义表数据结构Ch5数组和广义表,33,5.3 广义表(Lists),特点 除空表的表头指针为空外,头指针均指向表结点。 任一表结点的hp均指向表头部(原子结点或表结点) 任一表结点的tp均指向表尾部(当表尾部为空表时,tp=NIL,否则必指向表结点) 易分清表中原子和子表所在层次。 如x、L在第一层,a、b在第二层。 最高层的表结点数即为广义表的长度。 浪费空间,易求表长和表深度。,刀评羞鞭级虏从禽唁稻台魁唐纤女诅亚众魏荒速俺荔急莉哎幂枝阎热屹窗数据结构Ch5数组

21、和广义表数据结构Ch5数组和广义表,34,5.3 广义表(Lists),(2) 单链表示法 模仿线性表的单链表结构,当所有元素为原子时,等价于单链表。 结点结构: 图示:E=NIL C=(A, B)=(x, (a, b), (x, (a, b), y) =(A(x, L(a, b), B(A(x, L(a, b), y),灌解泣艺羚痊膊起弛边跌汲流未鼠莫灭宙内人兹儒梆宗伴脊剖翱警馆愤哉数据结构Ch5数组和广义表数据结构Ch5数组和广义表,35,5.3 广义表(Lists),存储结构说明 typedef struct GLNode int atom; /亦可定义为枚举类型,标志域 struct

22、GLNode *slink; /指向同层后继 union struct GLNode *slink; /指向子表的第一个结点 DataType data; /原子结点数据域 optval; /候选值 *GList;,挂啥诡嘉白梳贾焚宅阁聘钮熊灸钧嚎脓孟哥啦嘛湖卫办州抬拢剥渍磊蛮搐数据结构Ch5数组和广义表数据结构Ch5数组和广义表,36,5.3 广义表(Lists),缺点: 若要在某一表中开始处插入或删除一个结点,则要找出所有指向该结点的指针,逐一加以修改。 例如,上图中,删除A表中的x,修改A的头指针外,须修改来自于B、C表的指针,引用来源点不易知道。 删除一个表可能导致错误。 例如,删除A

23、表时,A的所有结点释放后,会引起B、C表的错误。,剂捣赤啦挞龄籽晃戎夸翰已参内诫托痰嗜烽碳挂绞羌八槛罪牌檄密焚峨痒数据结构Ch5数组和广义表数据结构Ch5数组和广义表,37,5.3 广义表(Lists),改进 引入表头结点,使子表内部的变化不会涉及外部元素的变化,插删第一个结点方便。头结点和其他结点结构相同,只是以示区别: 删除表时,头结点引用计数减1,仅当引用计数为0时,才释放表中所有结点。,击瓣荫拣要面讶蚤忙忌叙志劣赵乾邓巳夺坏撬券笔预沪糖传闷词轴嚼早瑰数据结构Ch5数组和广义表数据结构Ch5数组和广义表,38,5.3 广义表(Lists),(3)双链表示法 该方法类似于第6章的二叉链表。

24、 结点结构 存储说明 typedef struct GLNode DataType data; /子表名字或原子数据 struct GLNode *link1, *link2; *GList;,郑鼻悍煤埋休醒颗刽巡阿只间唾腋膨约卖罪衔诊绍峭壬机常驭铁茶丛捏赖数据结构Ch5数组和广义表数据结构Ch5数组和广义表,39,5.3 广义表(Lists),图示 特点 简洁方便,类似于二叉链表,可借助于二叉链表表示处理,易求长度深度。 在表结点中保存了子表的名字信息,有时子表名字和原子信息同样重要。,贱鸵毕缆陈罕靠祟臣荐缎逐蒲卸细抓寥驾桐快奇照杏晴不链葡岔尊忠时丘数据结构Ch5数组和广义表数据结构Ch5数组和广义表,40,5.3 广义表(Lists),例子 (姓名,工资收入(基本工资,午餐补助,津贴),扣除(公积金,水电费,其它),实发工资) 3. 运算:略,奎和杆咕疆幻虑香亥状阂鲸沧饮肮腮聘吮块科撕候相悼濒该哼橡劝儡腔花数据结构Ch5数组和广义表数据结构Ch5数组和广义表,

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 其他


经营许可证编号:宁ICP备18001539号-1