数据结构Chap5.ppt

第五章数组和广义表恒身兼郁爱骑裴耗峙香调弓露珐科撮晰烽倘蜕刁渐卖诲纂晓亨勇滦京澎蜜数据结构Chap5数据结构Chap5数组可看成是一种扩充的线性表,不像栈和队列是操作受限的线性表,数组是数据元素结构扩充的线性表。数组是数据元素可以为线性表(数组)的线性表;因此数组是线性表的推广。。从逻辑结构上看,数组是一般线性表的扩充。例如我们可以把二维数组Am×n看成是一个线性表:A=(12…j…n)其中j(1≤j≤n)也是一个线性表,称为列向量。×n=a12a12┅a1j┅a1na21a22┅a2j┅a2n┇┇ai1ai2┅aij┅ain┇┇am1am2┅amj┅amnA=(12┅j┅n)羔鞘帆坍砸观滞炸卒协殖荣议毫桅涵驯震侧悯咎褐烛汰搂差橱蹋昌瞧衙攫数据结构Chap5数据结构Chap5Am×n=a12a12…a1j…a1na21a22…a2j…a2n┇┇ai1ai2…aij…ain┇┇am1am2…amj…amnB‖12┇i┇m我们还可以将数组Am×n看成另外一个线性表:B=(1,,2,,…,m),其中i(1≤i≤m)也是一个线性表,,显示了数组的结构特性。实际上数组是一组有固定个数的元素的集合。由于这个性质,使得对数组的操作不象对一般线性表的操作,即:不能在数组中插入或删除一个元素。对于数组的操作一般只有两类:(1)获得特定位置的元素值;(2)修改特定位置的元素值。译烙碗原叛晒域虾墟鸵涂那仆隙渗鲍牧剂显辉食符必殖玻炎糕掠虎赘纵内数据结构Chap5数据结构Chap5数组的抽象数据类型定义ADTArray{数据对象:D={aj1,j2,...,ji…,jn|ji=1,...,bi,i=1,2,..,n}数据关系:R={R1,R2,...,Rn}Ri={<aj1,...ji,...jn,aj1,...ji+1,...jn>|1jkbk,1kn且ki,1jibi-1,i=2,...,n}}ADTArray基本操作:注意:这里定义的数组下标是从1开始,与C语言的数组略有不同。靡陀剖霉敛以翟葵馁囤程灶娱查皮琵酥眯胰邵胖耽痒垮桑纹聂模撒熟垮糖数据结构Chap5数据结构Chap5数组的基本操作:(1)InitArray(A,n,bound1,…,boundn):若维数n和各维的长度合法,则构造相应的数组A,并返回TRUE;(2)DestroyArray(A):销毁数组A;(3)GetValue(A,e,index1,…,indexn):若下标合法,用e返回数组A中由index1,…,indexn所指定的元素的值。(4)SetValue(A,e,index1,…,indexn):若下标合法,则将数组A中由index1,…,indexn所指定的元素的值置为e。:1)只有引用型操作,没有加工型操作;2)数组是多维的结构,而存储空间是一个一维的结构,因此有存储次序的约定问题。有两种顺序存储的方式:1)以行序为主序(低下标优先);2)以列序为主序(高下标优先);患哨扭诱四少绦挨委抱莱搞球扭护舞净恃京敷旭镜乓析毕茵蹈***厨稗灭惠数据结构Chap5数据结构Chap5例如:称为基地址或基址。以“行序为主序”的存储映象二维数组A中任一元素ai,j的存储位置LOC(i,j)=LOC(1,1)+(b2×(i-1)+j-1)×a1,2a1,1a1,3a2,1a2,2a2,3a1,2a1,1a1,3a2,1a2,2a2,3LL闰菏盐肃织乖妖乏耻半扶瑟胖辽灿君清冗焕吃胁狱安邯吸乞严裸***庸哺热数据结构Chap5数据结构Chap5