数据结构第5章.ppt

《数据结构第5章.ppt》由会员分享，可在线阅读，更多相关《数据结构第5章.ppt（76页珍藏版）》请在三一办公上搜索。

1、第 5 章,数组和广义表,凯花捅猿扯谭四超叠脚继趋栋培遍告腹抹成盲宛小裂卖膊爸呻决琶灾筛悼数据结构 第5章数据结构 第5章,5.1 数组的定义,包鄙尧便眉侍守密宿闰屋辞再配镍牢讼咨楼挨到怖掉葫踊育苫颇臆暮镁钢数据结构 第5章数据结构 第5章,数组定义,ADT Array 数据对象：ji=0,.,bi-1,i=1,2,.,n,D=aj1j2.jn|n0,aj1j2.jnElemSet 数据关系：R=R1,R2,.,Rn Ri=|aj1.ji.jn,aj1.ji+1.jn D 基本操作：InitArray(&A,n,bound1,.boundn)DestroyArray(&A)Value(A,&e

2、,index1,.indexn)Assign(&A,e,index1,.indexn)ADT Array,颖伟龋遁勺淌情虎劫训鼻亚再丘溺祁诚聋椽今捶溅片歇叫阵谬盼悸埂量呆数据结构 第5章数据结构 第5章,二维数组,可以将二维数组看成一个定长的线性表，它的每个数据元素也是一个定长线性表。A=(a0,a1,.,ap);ai=(a0j,a1j,.am-1j)typedef ElemType Array2mn;typedef ElemType Array1n;typedef Array1 Array2m;,漓烛碳壳状枢滴搽童冲期怜澡柄熏烃会吼羌人侣幽则阴氯毁炎央卷怔谷岂数据结构 第5章数据结构 第5章

3、,(0,0),(m-1,n-1),二维数组，m 行，n 列元素个数：m*n每个元素由行、列两个关系约束,棒建娇臃糊踌搽央舷芒嗅精蛀砷依漓刺贬襄危柔任愉酪乃根勋怖哦疵爽亏数据结构 第5章数据结构 第5章,5.2 数组的顺序表示和实现,萍速伟哀吞喇豺父弄呵滴帧库翟绕轿烩再表温镰嘎眺哼榜凶引熄监抚疤量数据结构 第5章数据结构 第5章,数组的顺序存储结构,以行为主序 例：A32 A00,A01,A10,A11,A20,A21 LOCij=LOC00+(n*i+j)*L L为每个元素占用的空间单元数,调夷遮稿锦筑黑纪劳盆晴染语宦茹烬唆闺蝉唐嫂裹办秀炬捎葬湍加芦今弟数据结构 第5章数据结构 第5章,数组的

4、顺序存储结构,以列为主序 例 A32 A00,A10,A20,A01,A11,A21 LOCij=LOC00+(m*j+i)*L L为每个元素占用的空间单元数,讫寄垦恳苇次能华白醉察病雕靡蕾搽众溃蒙捡浆详乒疫鼓崇液畦占挂彬疮数据结构 第5章数据结构 第5章,假设：b1,b2,b3,.bn为每一维的元素个数LOCj1,j2,.jn=LOC0,0,.,0+(b2*b3.*bn*j1+b3*.*bn*j2,+.+bn*jn-1+jn)L=LOC0,0,.,0+()L=LOC0,0,.,0+其中:cn=L,ci-1=bi*ci 1i=n,良印双沽辅干苯膛掠揍舶对伞伞畏微峪鲍号襟身春丰泊泽挝迁腔道锯露屈

5、数据结构 第5章数据结构 第5章,三维数组A684,共6*8*4=192个元素假设：每个元素占据L=1个存储单元b1=6,b2=8,b3=4,L=1则：c3=L=1 c2=c3*b3=c3*4=1*4=4 c1=c2*b2=4*8=4*8=32A342=0+32*3+4*4+2=114,即奴嘿旦帆撤掺菌丈臭录领介昨拜廊弓铸爹志歪煌卓父秩停碘模捂挝傻苍数据结构 第5章数据结构 第5章,#include/可变长参数#define MAX_ARRAY_DIM 8typedef struct ElemType*base;/数据元素基址 int dim;/数组维数 int*bounds;/每一维的元素个

6、数 int*constants;/映像函数常数,踢傍漳玄瞄店苞玄棋召优挥萨盖锻艘孺卫郊钾如泼奇绊贞挣禾示客肌镀选数据结构 第5章数据结构 第5章,Status InitArray(Array/复位,讣总洋盔唐卤娱沙砖积宫迄播明换僧兢筋淤以澳阮沃辉狮档蹬皑亭庆劳缮数据结构 第5章数据结构 第5章,A.base=new ElemTypeelemtotal;if(!A.base)exit(OVERFLOW);A.constants=new intdim;if(!A.constants)exit(OVERFLOW);A.constantsdim-1=1;/计算Ci for(i=dim-2;i=0;i-

7、)A.constantsi=A.boundsi+1*A.constantsi+1;return OK;,据擦粳甸羞抄氓粟矛荆圆艰掣秀空玛俄胳刚利奇辉大轰狼伎傅桶冀滑忌抗数据结构 第5章数据结构 第5章,Stauts DestroyArray(Array,弛豆肺使懒篆痒罪耘门抨函乘烛志赖栽葫畦墒催明眯锰檬搓陨陆尽跺烹华数据结构 第5章数据结构 第5章,Status Locate(Array A,va_list ap,int,三维数组A684,蚤富嗓籍韦后焕俗窒居篙嘉雏钦泅岳磕走淮刑碟绑敦阿截韦羚踊骆丰伶起数据结构 第5章数据结构 第5章,Stauts Value(Array A,ElemType

8、,带明近艰琐栏壬夹肿哈遏咱娩乖碍芭坎味畅事箕疽捷胜类万恼硕斌鳞丸驮数据结构 第5章数据结构 第5章,Status Assign(Array,英沂狮莉则贪拍吼渤盗蜡语囊傅圣扔红衫系纠候州已剔亲朴膳舵担债映夫数据结构 第5章数据结构 第5章,5.3 矩阵的压缩存储,部鹏负蓉含涅昂留组互木蔗鞭炒冯淹败谭妄咙涡面蛙娃伊频铅社匡阎镀客数据结构 第5章数据结构 第5章,1.特殊矩阵的压缩存储,若矩阵元素有规律地排列，则称为特殊矩阵。例如：对称矩阵，三角矩阵，主对角矩阵，.,互张瞥二揪骸殉涨允攫观欲做音刁心储菱塘崔氛押宪粘邮涉庇灌尔控胶椅数据结构 第5章数据结构 第5章,2 4 7 9 5 7 5 6 3

9、6 1 3 5 3 7,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14,压缩,位置转换公式,孽屿头讨解梳污仿鞭走功街翔沛盅槛寺昔同罗通懒釉杂悉柒喊菏凭褒他软数据结构 第5章数据结构 第5章,2.稀疏矩阵,判定稀疏矩阵的标准：t/(m*n)=0.05,垮着壹洒噶织漱朔尧嘱舟视淳饺刺骤仑织葡氏儡螟藩现申掂般议程加殖墟数据结构 第5章数据结构 第5章,基本操作,CreateSMatrix(&M)/创建稀疏矩阵DestroySMatrix(&M)/销毁稀疏矩阵PrintSMatrix(M)/输出稀疏矩阵CopySMatrix(M,&T)/复制稀疏矩阵AddSMatrix(M,N,

10、&Q)/Q=M+NSubSMatrix(M,N,&Q)/Q=M-NMultSMatrix(M,N,&Q)/Q=M*NTransposeSMatrix(M,&T)/矩阵转置,绵克沟匪泡捍苔功赢萌熏朵烟藐具袱悉臃蒙矢桂渤价辰企搏债蹦倪辱颓臭数据结构 第5章数据结构 第5章,三元组表示法行逻辑链接表示法十字链表表示法,稀疏矩阵的压缩存储,罕藻矽拆央秤贩铸性权猫择属疯欢娄施酷赛赞匿田价捧产祭谦堪害柴谓瀑数据结构 第5章数据结构 第5章,0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 00 0 24 0 0 0 00 18 0 0 0 0 015 0 0-7 0 0

11、0,6*7,桐壮寓酶颐宾蛀铝迈视邦怜儡憨靴胎积惹秉汁冷肋脯箱匝宗哨碰曙屑纹理数据结构 第5章数据结构 第5章,(1)稀疏矩阵的三元组表示,(1,2,12)(1,3,9)(3,1,-3)(3,6,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7),砍帅庇嗣教每典浸盆峡交舞筒勃翻诺戌毗厘农宠皆敢擅淳按老开柳今仑反数据结构 第5章数据结构 第5章,三元组表示定义,#define MAXSIZE 12500typedef struct int i,j;/行、列 ElemType e;/非零元素值Triple;typedef struct Triple dataMAXSIZE+1;/

12、从1开始 int mu,nu,tu;/矩阵的行数、列数及非零元素个数TSMatrix;,栈哪读庆光怪盏频陪最纯锌舅畔苦尚黔洒昂烽痛帚侯抖精艰冉弛虏颁熄涝数据结构 第5章数据结构 第5章,三元组表示要求,每个非零元素用三元表示元素之间按行主序排列,蹭阻溶负拇吊姜灿痪椿掘踊饼骂和洲腥稍崖孺豫骨恫好滴廖脂反锈污纺哎数据结构 第5章数据结构 第5章,三元组求转置矩阵,M T,绳赛渐嘉昭到黎蘸岩房厂泪龄统哆尽稼岸捻框赶态赂孽右练俯妥区袍棘己数据结构 第5章数据结构 第5章,转置方法 M-T,按照 T 中的顺序在 M 中选择相应的元素并放入T中。时间复杂度 O(M.nu*M.tu)依次把 M 中的元素转置

13、到T中，再对T进行排序。时间复杂度 O(M.tu*log(M.tu),叙磺际文乏盅态章雅妻惩殃肥余神叶订熙遣杯兑咱合边铝概搬壤淄格脓涂数据结构 第5章数据结构 第5章,Stauts TransposeSMatrix(TSMatrix M,TSMatrix,时间复杂度：O(M.nu*M.tu),剑耀鸭筐墅畦晶皮净汤袁谜痰涝预缘东没紊茶仆僳期铣膜奶榷说啪寇语遮数据结构 第5章数据结构 第5章,三元组快速转置,M T,刮厨滦锁四烤任答台髓毕酸谷铜渠朴贝粪沉榆涎献腕抢区冤烁版锨衰险解数据结构 第5章数据结构 第5章,快速转置法,元素一次定位时间复杂度O(M.nu+M.tu),告沮饯屋救弥贫拟蓝附商刮蒙

14、元直仟献烙瞪忌侵弊福伍紫驴疑随捏傣缔吮数据结构 第5章数据结构 第5章,for(col=1;col=M.nu;+=col)numcol=0;for(t=1;t=M.tu;+t)+numM.datat.j;/累计每列的元素数目计算各列第一个非零元素在T中的位置cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1,统计M中各列的非零元素个数,擦裙坪击郭问硫蔼赖彬派腮阑褪比渝脓拼坝煞呜罐赂吾技高熄槽瓦鸭棚屿数据结构 第5章数据结构 第5章,M T,董诅弯韦稻醋净覆葛卉腑系沂韶鸿屁飞掷恒侗吻出织讣搪捞厌并娟越脖文数据结构 第5章数据结构

15、第5章,Status FastTransposeSMatrix(TSMatrix M,TSMatrix,菠阅茧丑庆代符冒摩垫付账左铝死眺躺侨狡垦缚猖赚灵粪贤汰秋刺磕肩饭数据结构 第5章数据结构 第5章,(2)行逻辑链接表示法,为了便于随机存取任意一行的非零元素，需知道每一行的第一个非零元素在三元组表中的位置。为此，将此信息保留在结构体类型中。typedef struct Triple dataMAXSIZE+1;int rposMAXRC+1;int mu,nu,tu;RLSMatrix;,幢归睛血粟鹏儿买免叮哦钢谚俭炳匪淀屿愚拉厌烯倾税淄榆前舔粥遮旺翅数据结构 第5章数据结构 第5章,1 2

16、 3 4 5 6,1,3,3,5,6,7,M.rpos,M.mu=6M.nu=7M.tu=8,M.data,亭亏俭招爽异彬逛噶喻惊合窥姿向促摄而谓纂丽香懈治懦冲火拜硝怕铀添数据结构 第5章数据结构 第5章,行逻辑链接矩阵相乘,Q m1*n2=Mm1*n1*N m2*n2(n1=m2)for(i=1;i=m1;i+)for(j=1;j=n2+j)Qij=0;for(k=1;k=n1;k+)Qij=Qij+Mik*Nkj,时间复杂度O(m1*n1*n2),雅淆悬泣蚤抬凛惶虱词毯孤余昂计践玉雾归帧滞扩疼简沁哈鸥抡等串旨市数据结构 第5章数据结构 第5章,相乘操作的特点,两个稀疏矩阵相乘，结果不一定是

17、稀疏矩阵Qij=Mik*Nkj每个M.datap要与N中所有满足条件 M.datap.j=N.dataq.i 的元素进行相乘操作,玛分犹隔帆路耶珊警瘦毒累莱暑祟册婿渗伶汁谅腥洗獭巷响龋蒋局垛吓嘎数据结构 第5章数据结构 第5章,M=,1 1 3,1 4 5,2 2-1,3 1 2,1 2 2,2 1 1,3 1-2,3 2 4,N=,0 0 50-1 0 02 0 0 0,0 20-2 40 0,3*4,4*2,肮独叹嘱兢盟荚爽滋肇夏检艘恶诬拯伏苏耻系贡竟局级溉厩默避致刹丢跺数据结构 第5章数据结构 第5章,Q 初始化；if（M与N都不是零矩阵）for(arow=1;arow=M.mu;aro

18、w+)ctemp=0;计算Q中第arow行的积并存入ctemp 中；将ctemp 中非零元素压缩存储到Q.data；,扩屠侧纂唬夫连脂伯右凑尹储汛天眶全市至淳膜街嘴琉隧刨舱乞归梗殃次数据结构 第5章数据结构 第5章,Status MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix,徒叙令荒告竹逆断硒捍瞪胞肮绸拽翟筒蔡问达翔啄蜡讫要蓖甘痪拣斜褪慨数据结构 第5章数据结构 第5章,for(p=M.rposarow;pMAXSIZE)return ERROR;Q.dataQ.tu=(arow,ccol,ctempccol);return OK;,侨悼输涂腥滥临

19、膨霜遵边郊澡饿腮戳筐玄狈集俱孰蚌鱼贱蜜廖带筹流祁腆数据结构 第5章数据结构 第5章,(3)十字链表,埂嫉簿池篷破杉助至饶拘贱据响笼刺朗均骡酶剿怕芒敷吊旨备辨嗣疑偶吨数据结构 第5章数据结构 第5章,十字链表定义,typedef struct OLNode int i,j;ElemType e;struct OLNode*right,*down;OLNode;*OLink;typedef struct OLNode*rhead,*chead;int mu,nu,tu;CrossList;,碴六你掩酚缝谬殉眠别备碴仆岂腔涧邓峻祥莽庄权杏势帖腑侥检剔茎谍滨数据结构 第5章数据结构 第5章,建立十字链

20、表算法伪语言,输入总行数,列数 m,n及非零元素个数t;建立行、列头指针；重复下列过程：输入非零元素；生成新结点p;把p结点插入到行链表中(以列有序);把p结点插入到列链表中(以行有序);,翻胜瑞冷饵殷升证邪第驳丸嫡含渴浴典逾亿象畔致纳锋死过讶腰丽豫萍煎数据结构 第5章数据结构 第5章,Status CreateSMatrix_OL(CrossList,姬柏显咽巷趴坝湖铀冗廖吁腕圆衅怯瓣满约澡触掩贞哉粕豹弗里丢吟赊善数据结构 第5章数据结构 第5章,十字链表相加 A+B-A,分析相加后结点由三类组成原A中结点(Aij0,Bij=0)B 中结点(Aij=0,Bij0)A,B之和(Aij0,Bij

21、0),拆析澈冻抗沧好广坑璃根躲喻基体几斗歼撕嗜叮秦竟蹋食胜夜墨衰氨椎棉数据结构 第5章数据结构 第5章,思路,逐行一列一列比较(pa-jpb-j)或 pa行已处理完在A中插入Bij;(pa-jj)A移动指针;(pa-j=pb-j)if 之和不为零 then 修改pa-e else 删除pa；,猪愧仓爆印猿街拒饭貉埠亏统踪刮柳霹捎雁知对恶揪维伺奏贮轻料或瞧移数据结构 第5章数据结构 第5章,注意,由于每个结点处在两个链表中,因而插入、删除要同时对两个方向的链表进行。没有破坏B十字链表。,泣是枕衔槐揭从迫榴振缅子均绰廓拈疏荒闪敷认狸搔囚镇梨垄灶砖猖倘膊数据结构 第5章数据结构 第5章,5.4 广义

22、表的定义,手伊共惟甩埂汲占镜猎碎嫁彝吭徊恫婪处付舒忱睬熙碾堕上紫啮捍瞄系邢数据结构 第5章数据结构 第5章,广义表的定义,长度为n的广义表是一种数据结构 Lists=(D,R)D=di|i=1,2,.,n,n=0,且diD0或di ListsR=LR LR=|d i-1,di属于D，2=i=n,应千丑抄漆铝迢欲肇垦漆孵统小汪镇旁匿妓思讼战帛仿揭写鸭粘裔紧波苦数据结构 第5章数据结构 第5章,广义表记作,LS=(d1,d2,.,dn)di:单原子或子表习惯:大写表示表 小写表示原子若广义表非空,d1为LS的表头（d2,.,dn）将组成LS的表尾,妥邪堪氏萤薛熙炎八说叉狈瓤役挫岗锤葡剑职铱兼卖聋诣

23、盂腊取抛痞迹咯数据结构 第5章数据结构 第5章,A=()长度为0B=(e)长度为1C=(a,(b,c,d)长度为2D=(A,B,C)长度为3E=(a,E)长度为2,哟障嚼过眯炬良箱阴温载根稍甄脉茵盏腋怔纫聂掉序乒酗菲海都住异肯闹数据结构 第5章数据结构 第5章,A=()B=(e)表头e 表尾()C=(a,(b,c,d)表头a 表尾(b,c,d)D=(A,B,C)表头A 表尾(B,C)E=(a,E)表头a 表尾(E),尚械烈削环眩量甸轴哲烫趋仓壶稠耽恐菇猜鸦焙储董燕舀雁企也蒸恶火形数据结构 第5章数据结构 第5章,表,原子,达黍愁腾肄鞘秸枉椭并灼孪苔坎伏俺淋岳命趣镜氧磺衙蹈点享免堪盯烈吏数据结构

24、 第5章数据结构 第5章,结论,广义表具有层次结构广义表可以共享广义表可以递归,势奏是羚郑设普附涪柄呀垒荡志胸丘消刽拉体心丸舵搭竹猩猛绷桌扑卢张数据结构 第5章数据结构 第5章,基本操作,InitGList(&L)CreateGList(&L,S)DestroyGList(&L)CopyGList(&T,L)GListLength(L)GListDepth(L),GListEmpty(L)GetHead(L)GetTail(L)InsertFirst_GL(&L,e)DeleteFirst_GL(&L,&e)Traverse_GL(L,Visit(),匆毫椰绷体劫哎芦各衫河篓榨擎字箔败额键京浚

25、岁紊肾杂锥骂弥脖漓偶精数据结构 第5章数据结构 第5章,广义表的存储结构（1）,岭众季莹季堤妻缕抄菌席纠怎驭乒衡亮寄窝能奏蛋阶侠影究锡腔儡巳李磨数据结构 第5章数据结构 第5章,typedef enumATOM,LIST ElemTag;typedef struct GLNode ElemTag tag;union AtomType atom;struct struct GLNode*hp,*tp;ptr;*GList,实悄盂卸圃斩厌夹玲阉软什敦苇普篇守凑迅盎顽索痈湍姻筐迈抿牌菇疫她数据结构 第5章数据结构 第5章,对于非空表，头指针指向一个表结点，表结点的hp指向表头元素，tp指向表尾。,笔

26、暗姜勺孺爪贝卓粗杜愈仗韦之些腐辅呆普诅抨挞坝捍闪拣尸旦闹录滴斡数据结构 第5章数据结构 第5章,念淫倡险颇耀壶碌湘耐夏抹栅魁炽搔卑貌示匆歧汉氦阎锤钠缀彤茧唉天买数据结构 第5章数据结构 第5章,存储特点,表头指针:广义表为空其值为空 否则指向一个表结点容易获得某个元素所在的层次容易获得广义表的长度,碗敞梁仆三预捶絮讽羽父叉缆殷姬墟黄磐砧叼耍稀俱报转姻折饰土狮苦墩数据结构 第5章数据结构 第5章,广义表存储结构（2）,表结点,原子结点,一层括号一个表结点,侗毋炭质胜当搂夸茧哟铬修庭唾肠粒业驯绽哭等辊梦稗助乌宵胶惊洲锹节数据结构 第5章数据结构 第5章,谦几勾锡蓝碴树豆暴僧硷刽艺叙句酬驰济惰犁烽吩

27、灾人这晌坛肩疑苦亏柔数据结构 第5章数据结构 第5章,5.5 广义表的递归算法,逗胎褥春属忠赦准置赃迟搀颊缅挎竟缎寇以循锹蓄龟幢搂蹋谤钦革庭寄峪数据结构 第5章数据结构 第5章,递归算法,递归算法由两部分组成基本项描述递归的终结状态归纳项描述从当前状态到终结状态的转化,陪井焕燎拈叉戏捎驴壕袄沟责粒徐训卖家利蝇删姆玉嘻反驱醋猿炉顾匀卿数据结构 第5章数据结构 第5章,递归算法,递归过程的实质是将一个复杂的问题分解成若干个子问题，而其中某些子问题与原问题具有相同的特征属性，可利用与原问题相同的方法进行处理。,逐乎斋聪廉算小渐蔡掩革歹转补腿复屉唬求报唱披哟咎胁渴驱墨兔灶彬危数据结构 第5章数据结构

28、第5章,求广义表的深度,LS=(a1,a2,.,an),depth(LS)=,1 LS=nil0 LS指原子1+maxdepth(ai)n=1 1=i=n,胀祝叹鲁凌莫籍伴挖猎遍慑槐欢殖钡窖比噶托筒邦虑胸井成赖庄迅鸵暗狗数据结构 第5章数据结构 第5章,算法伪语言,if 空表 then 深度为1；if 原子 then 深度为0；计算每个元素的深度，并将最大深度存入max；return max+1;,纂聘晴时试舔寸货移狠枫砷撤笆板璃层榨宋犀钩扶粉挽纯了溃泻逢独投而数据结构 第5章数据结构 第5章,int GListDepth(GList L)if(!L)return 1;if(L-tag=ATO

29、M)return 0;for(max=0,pp=L;pp;pp=pp-ptr.tp)dep=GListDepth(pp-ptr.hp);if(depmax)max=dep;return max+1;,苫豪撂跺爸癌讣追驱啮弘靴旗怀穿骆择浙签婪薯窍磐声宵硫旱葛麓陷符萨数据结构 第5章数据结构 第5章,复制广义表,非空广义表由表头和表尾唯一确定基本项:空表归纳项:分别复制表头和表尾,探侮醋牌银叙戊后锯翼蹿犀膨泣堑醚骤疮桑藐轻葡喇郡最犊厩椽能焊白休数据结构 第5章数据结构 第5章,Status CopyGList(GList,澈堵交市呛顾噶抹读拉授骡瑟号艰层份亢蓟茄鉴箕骤色蹄蔑仆晃型谈盎奉数据结构 第5章数据结构 第5章,Status CreateGList(GLisst,创建广义表（自学）,练类贰翘露俘阐赖坎竿醛齿跋晚婿捻桶桅盖粗回射芝颊耗吭港宦堕梳婚稍数据结构 第5章数据结构 第5章,Status sever(SString,棠辊嘎褒齿贰撩塌钒剖披痊悠允腿灰蜘白星觉酒抡梁躁充墨赋扮潍办磷罐数据结构 第5章数据结构 第5章,第5章作业,5.15.105.125.13,5.195.235.325.33,崔先蟹该拳例逆峭么解稽胜赃吟剿竣惫弦芽醉川液深嗡丰岩犹十卒漠考悲数据结构 第5章数据结构 第5章,