数据结构第5章数组广义表课件.ppt

1、数组描述数组描述二维数组可用形式化语言描述，即：A(2)=(D,R)其中：D=aij|aijdatatype,0im-1,0jn-1;R=Row,Col 行关系：Row=|aij,aij+1D,0im-1,0jn-2 列关系：Col=|aij,ai+1jD,0im-2,0jn-1 关系集Row和Col表明：除数组A(2)周边元素外的其它任一个元素aij，有两个直接前驱ai-1j，aij-1,和两个直接后继ai+1j，aij+1(周边元素的前驱或后继可不足两个)。n维数组也可按上述方法类似定义。二维数组还可以用如下形式描述:A0 Ai Am-1=(A0AiAm-1)-线性表形式线性表形式a00

2、a01 a0j a0n-1.ai0 ai1 aij.ain-1.am-10 am-11 am-1j am-1n-1A(2)=Amn=2.数组的基本运算数组的基本运算 多维数组是线性表的推广，而线性表是多维数组的特例。在算法语言中，数组一旦生成，其元素的存储空间就固定下来，故数组的运算一般不包括插入和删除这样的操作。对数组运算有：(1)构造一个n维数组：Setarray(A,n,d1d2,.dn)，即生成：Ad1d2.dn（C语言中，1n8）。(2)撤消一个数组：Dearray(A)，释放数组A的存储空间。(3)取值：Aget(A,i1,.,in,x)，将Ai1i2,.,in的值传给变量 x。(

3、4)赋值：Assign(A,i1,.,in,x)，将变量 x的值传给Ai1i2.in。5.2 数组的存储映像数组的存储映像 由于计算机的存储空间是一维的（或线性的），所以存储数组时，要将多维数组中的元素按某种次序映象到一维存储空间，即解决“降维”问题。在PASCAL和C等语言中，是按低维下标优先变化（或按行优先）的方式，存储数组中的元素。如在C语言中，二维数组的映像如图5.1所示。但在FORTRAN语言中，数组元素是按高维下标优先变化或按列优先方式，存储数组中的元素。数组的存储映像数组的存储映像 a00a0,n-1ai0ai,n-1am-1,n-1映像映像 （存储器）存储器）a00 a01 a

4、0j a0n-1.ai0 ai1 aij.ain-1.am-10 am-11 am-1j am-1n-1 Amn=图图5.1思考：思考：1.三维以上数组如何映像三维以上数组如何映像?2.“按列优先按列优先”如何映像如何映像?5.2.1数组元素的地址计算数组元素的地址计算v以C语言为例。设数组元素的起始地址为b,每个元素占用L个单元（元素所占单元量由元素的类型而定），元素a的地址用Loc(a)表示。1.一维数组：一维数组：即即:Loc(a0)=b;Loc(a1)=b+L;Loc(ai)=b+iL;规律：任一元素规律：任一元素ai的地址的地址:a0a1 ai-1aian-1An=(a0,a1,ai

5、,an-1)起始地址起始地址b+(ai前的元素个数前的元素个数i)L 起址起址 b:b+L:b+iL:L图图5.3数组元素的地址计算数组元素的地址计算2.二维数组：二维数组：a00a0,n-1ai0aijam-1,n-1映像映像 （存储器）存储器）起址起址 b:b+L:b+inL:b+in+jL:由图由图5.4知：知：Loc(a00)=b Loc(ai0)=b+(ai0前元素个数前元素个数)L=b+(in)L Loc(aij)=b+(aij前元素个数前元素个数)L=b+in+jL例例5-1 设二维数组设二维数组A78，起始地址，起始地址b=1000，每个元素所占单元量，每个元素所占单元量L=3

6、，则则Loc(a5,6)=1000+(58+6)3=1138。inj图图5.4a00 a01 a0j a0n-1.ai0 ai1 aij.ain-1.am-10 am-11 am-1j am-1n-1 Amn=数组元素的地址计算数组元素的地址计算3三维数组三维数组：由图5.5可知：Loc(a000)=b 图图5.5 Loc(ai00)=b+(inp)L Loc(aij0)=b+(inp+jp)L Loc(aijk)=b+(inp+jp+k)L可以看出，inp，inp+jp，inp+jp+k分别为ai00，aij0，aijk前的元素个数。a000ai00aij0aijk数组元素的地址计算数组元素

7、的地址计算4n 维数组维数组 从以上的地址公式推导中得出这样一条规律：任意维数组中任一元素的地址任意维数组中任一元素的地址=起址起址b+该元素前的个数该元素前的个数元素单元量元素单元量L。故n维数组Au1u2.un，其中任一元素ai1.in的地址为：Loc(ai1i2in)=b+(i1u2u3 un+i2u3u4 un+in-1un+in)L =b+()L元素按“列优先”方式存储时，地址计算方法类似，不再赘述。有了数组元素的地址计算公式，给出相应参数后，能够很快求出任一元素的地址，然后按地址存取相应元素，故对数组的存取是随机存取（或按公式存取）。5.2.2数组空间的动态生成（略）数组空间的动态

8、生成（略）nnjkknjjiui1115.3矩阵的压缩存储矩阵的压缩存储 信息的压缩存储是一项专业技术，在当今的多媒体应用中显得尤为重要。但本节只是讨论矩阵（或二维数组）中元素的压缩存储。在矩阵中，往往会出现许多值相同的元素或元素，为节省存储空间，可以采用某些技术对这类矩阵进行压缩存储。压缩存储的原则是：对多个值相同的元素只存储其中之一，对元素甚至不分配存储空间。5.3.1特殊矩阵的压缩存储特殊矩阵的压缩存储 特殊矩阵，指的是值相同的元素或元素在矩阵中的分布遵循一定规律的矩阵。1.对称矩阵对称矩阵：满足aij=aji，(1i,jn)a11 a22 aii ann Ann=aijaji特殊矩阵的

9、压缩特殊矩阵的压缩 显然，aij与aji对称相等，二者只需分配一个存储单元，即只存储矩阵中包括主对角线的下三角(或上三角)元素。于是Ann所需的存储单元数为n(n+1)/2，而不压缩存储需要n2个存储单元。当n很大时，几乎能压缩原存储空间的一半。具体做法是：设置一个一维数组Sn(n+1)/2+1作为An.n的存储空间，且按行的次序存放Ann中包括主对角线的下三角元素，如图5.7所示。a11a21a22aijann Sn(n+1)/2+1:1 2 3 .k.n(n+1)/2图图5.7a11 a22 aii ann Ann=aij其中aij存入Sk单元，下标（i,j）与k的关系为：i(i-1)/2

10、+j 当ij 时；Si(i-1)/2+j 当ij 时；k=即：即：aij=j(j-1)/2+i 当ij时。Sj(j-1)/2+i 当ij时。特殊矩阵的压缩特殊矩阵的压缩三角矩阵：三角矩阵：（下三角矩阵）(上三角矩阵）显然，对于下三角矩阵，类似于对称矩阵的压缩存储，即只存储包括主对角线的下三角元素。而当ij)时，K=0.图图5.8 特殊矩阵的压缩特殊矩阵的压缩3对角线矩阵（对角线矩阵（三对角线）：按行顺序压缩于S中，如图5.9所示。Ca11a12aijann S3n-1:0 1 2 .k .3n-2a11 a12 a21 a22 a23 .aii-1 aii aii+1 .ann-1 ann A

11、nn=CC图图5.9 3(i-1)当i=j+1时；3i-2 当i=j时；归纳为：k=2i+j-2 当i=j+1,i=j,i+1=j时。3i-1 当i+1=j时；如将i=1,j=2代入,k=2 0 其他。k=5.3.2稀疏矩阵的压缩存储稀疏矩阵的压缩存储 特殊矩阵中同值元素的分布有一定的规律可循，而有的矩阵，元素很多（如同一个画面上有几个亮点，其余全是空白），但分布无规律，称这类矩阵为稀疏矩阵。例例5-2 设一个67的矩阵如下：则A67可以视为一个稀疏矩阵。对于矩阵Amn，设非0元素个数为t，若=t/(mn)0.2，则可以将其视为稀疏矩阵。显然，为节省存储空间，须对这类矩阵压缩存储空间，原则是只

12、存储非0元素。一般有“三元组表三元组表”和“十字链表十字链表”的压缩存储方法。0 1 0 2 0 0 00 0 0 0 0 0 0 3 0 0 0 0 4 00 0 5 0 0 0 0 0 6 0 0 0 0 0 7 0 0 8 0 0 0 A67=1三元组表三元组表 三元组：（i,j,v），其中i,j分别为非0元素的行、列号，v存放非0元的数值。以行优先的顺序将稀疏矩阵中非0元以三元组形式存入一数组，即所谓的三元组表。三元组表的存储结构的描述：#define maxsize 64 /最大非0元个数/typedef Struct /三元组类型/int i,j;datatype v;trityp

13、e;/三元组说明符/typedef Struct tritype datamaxsize+1;/三元组表/int mu,nu,tu;/原矩阵的行、列、非0元个数/Tsmtype,*Tsmlink;/三元组表说明符/若说明：Tsmlink A;A=(Tsmlink)malloc(sizeof(Tsmtype);则指针变量A指向一个如图5.10所示的三元组表。对例5-3中A67，设每个元素占16个字节，若不压缩存储，需6716=672（字节），而压缩成三元组表存储时，i,j为整型，故共需：216+816=160（字节）。ijv121142313364435526617648A-data1 A-da

14、tatu 图图5.10三元组表的转置三元组表的转置 然而，稀疏矩阵的压缩存储会给矩阵运算带来一些不便，算法要复杂些。这里的运算指求矩阵的转置，两矩阵相加和相乘等。我们只讨论矩阵的转置的算法。未压缩前，求矩阵A的转置矩阵B，算法很简单：for(col=1;col=nu;col+)for(row=1;rowdata3.j=1,所以将A-data3的转置：（1，2，6）=B-data1，又A-data6.j=1，所以A-data6的转置：(1，4，3)=B-data2，完成第一列的转换，依此类推。算法描述算法描述：void Transm(Tsmtype A,Tsmtype B)int p,q,col

15、;B-mu=A-nu;B-nu=A-mu;B-tu=A-tu;if(A-tu!=0)q=1;/目标表的序号/for(col=1;colnu;col+)/扫描A的所有列/for(p=1;ptn;p+)/扫描所有非0元/if(A-datap.j=col)B-dataq.i=A-datap.j;/行列互换/B-dataq.j=A-datap.i;B-dataq.v=A-datap.v;q+;三元组表的转置三元组表的转置 ijv122154216238329413 p 123456 0 2 0 0 4 6 0 8 0 0 0 9 0 0 0 3 0 0 0 0 A45=1 2 3 4 5 colijv

16、126 q 1234561432122393285140 6 0 3 2 0 9 0 0 8 0 0 0 0 0 0 4 0 0 0 B54=（矩阵（矩阵A 的三元组表）的三元组表）图图5.12（转置后的三元组表）（转置后的三元组表）算法的时间复杂度：算法的时间复杂度：O(tn)n=列数列数,t=非非0元个数。元个数。改进算法的复杂度：改进算法的复杂度：O(t+n)（略）（略）2.十字链表十字链表 十字链表是以链表结构形式存储一个稀疏矩阵。矩阵中非0元设置成如下形式的结点：其中i、j分别存放非0元的行列号，head/data或作为一非0元的值域（data）或作为头结点的链指针(head)；do

17、wn为指向相同列下一个非0元结点的指针，right为指向相同行下一非0元结点的指针。结点类型描述：typedef struct node int i,j;union struct node*head;datatype data;vdata;struct node*down,*right;nodetype,*tlink;ijhead/datadownright十字链表十字链表例例5-4 设稀疏矩阵：1 0 0 40 2 0 03 0 0 00 0 0 5 A44=1 111 442 223 134 450 04 40 00 00 00 00 00 00 0LA的十字链表如图的十字链表如图5.13

18、：十字链表十字链表算法思路算法思路：先构造空表，其中S取矩阵行列数的最大值，即S=max(m,n)。依次读入每个非0元(i,j,v)，生成一个非0元的结点，对该结点赋读入的值后，将其插入第i行链表和第j列链表的正确位置。算法描述算法描述：void Creattenlink(tlink L,int m,n,t)/L为头指针，m,n,t分别为行列号和非0元个数/tlink p,q,Hmaxsize;int i,j,k,s;datatype v;if(mn)s=m;else s=n;/确定头结点的个数/L=(tlink)malloc(sizeof(nodetype);/申请总的头结点/L-i=m;L

19、-j=n;/置行列数/H0=L;for(i=1;ii=p-j=0;p-down=p-right=p;Hi=p;Hi-1-vdata.head=p;Hs-vdata.head=L;/构成循环链表/十字链表十字链表 for(k=1;ki=i;p-j=j;p-vdata.data=v;/赋值/q=Hi；/取第i行链表头结点指针/while(q-right!=Hi)&(q-right-jright;/找当前非0元结点在行链表中的位置/p-right=q-right;q-right=p;/当前非0元结点插入q结点之后/q=Hj；/取第j列链表头结点指针/while(q-down!=Hj)&(q-down

20、-idown;/找当前非0元结点在列链表中的位置/p-down=q-down;q-down=p;/非0元结点结点插入q结点之后/5.4广义表的定义广义表的定义 广义表又称列表(lists),是线型表的推广。在线型表L=(a0aian-1)中，ai是单元素或称原子，即ai本身不再是一个数据结构，而广义表记为：LS=(d0d1didn1)其中di（0in-1）既可以是一个原子，又可以是另一个表（称为子表），即表中还可以套表。广义表LS的形式化描述为：LS=(D,R)其中：D=di|didatatype or diLS(递归定义)，i=0,1,.n-1,n0 R=|di,di+1D,0in-2式中n

21、为表长（n=0 时为空表），若di为原子，则称di为LS的单元素，否则di称为LS的子表（满足递归定义)。当广义表非空时，定义两个函数：head(LS)=d0；tail(LS)=(d1.dn-1)。即head(LS)是LS的第一元素d0（当然d0可以为子表），而tail(LS)是LS中d1.dn-1的一个子表。对广义表的其它运算（如查找，插入和删除等）类似于线性表的运算。广义表广义表例例5-5 广义表的例子。约定：大写字母AZ为表名，小写字母 az为单元素。A=()或A()空表，表长=0，无表头，表尾；B=(a,b)或B(a,b)线性表(广义表特例),表长=2,head(B)=a,tail(B

22、)=(b)；C=(e,B)或C(e,B)表长=2，head(C)=e,tail(C)=(B)=(a,b),表C可以表示为：C(e,(a,b)；D=(A,B,C)或D(A,B,C)表长=3，head(D)=A=(),tail(D)=(B,C)=(a,b),(e,(a,b)；E=(a,E)表长=2，head(E)=a,tail(E)=(E),整个表E为(a,(a,(a,.)，它为一个特殊的广义表，称为递归表，或无限表。从例5-5可以看出，广义表有如下特点：（1）表可以嵌套表中元素可以是一个表，称为子表，而子表还可以有子表。如例5-5中表B和表C的结构如图5.15所示。图图5.15CeBababB广

23、义表广义表（2）表可以共享表可以是其它表的子表，或表中的元素可取自其他的表。如例5-5中表D包含表A、B、C，或A、B、C为D的子表,如图5.16所示。（3）表可以递归表中元素可以是表本身。如例5-5中表E。EaDABCabe图图5.16另外，表中任一单元素可由head(Ls)和tail(Ls)函数导出，如取表A=(a,(b,d,e)中单元素d的运算为：head(tail(head(tail(A)5.5广义表的存储结构广义表的存储结构 对于广义表LS=(d0 didn-1)，由于di可以是单元素或子表，故用顺序存储结构表示一个广义表较为困难，一般采用链表存储结构，称为广义链表。5.5.1单链及

24、双链结构单链及双链结构1单链表示法单链表示法 元素di的结点形式：其中：0 当di为单元素时；data 当atom=0时；atom=data/link=1 当di为子表时。link 当atom=1时。next意义同线性链表，指向di+1所在结点。结点描述：typedef struct node int atom;union datatype data;struct node*link;dtype;struct node*next;Lsnode;atomdata/linknext广义表的存储广义表的存储为了广义表的运算方便，对每一广义表引入头结点，其形式同一般的表结点：例例5-5中广义表A、B、

25、C、D、E的单链表如图5.17所示。11AA=()图图5.170a0b1BB=(a，b)0e11CC=(e，B)1111DD=(A，B，C)0a11EE=(a，E)广义表的存储广义表的存储2双链表示法双链表示法元素di的结点形式：其中：指向子表的指针 当di为子表时；link1=当di为原子时。表名 当di为子表时；data=link2：指向di+1所在的结点。原子值 当di为原子时。例5-5中几个广义表的双链表结构如图图5.18：datalink1link2BACDEaEBeCbaA=B广义表的存储广义表的存储例例5-6 设职工工资的表头H：即H=(A,B,x)，A=(a1，a2，a3)，B

26、=(b1，b2，b3)。H的双链结构如图图5.20：工资收入工资收入A 扣除扣除B基本工资基本工资 岗位津贴岗位津贴 福利福利 房租房租 水电水电 其他其他 实发实发X a1 a2 a3 b1 b2 b3BAHx5.5.2 广义表的生成算法、广义表的生成算法、5.5.3 求广义表深度的算法（略）求广义表深度的算法（略）a1a2a3b1b2b3第五章小结第五章小结 多维数组定义、运算、多维数组定义、运算、存储映像存储映像数组元素地址计算数组元素地址计算:1、2、3、n 维维广义表广义表定义、特点定义、特点存储：单链、双链存储：单链、双链数组数组广义表广义表矩阵压缩存储矩阵压缩存储特殊矩阵：对称、

27、三角、对角线特殊矩阵：对称、三角、对角线稀疏矩阵：三元组表、十字链表稀疏矩阵：三元组表、十字链表第五章习题第五章习题第五章习题第五章习题 1.FORTRAN语言中，数组元素按列优先存放。设每个元素占语言中，数组元素按列优先存放。设每个元素占L个单元，首元个单元，首元素地址素地址=b，试确定：，试确定：一维一维 An=(A1 A2 An);二维二维 Am,n(m行、行、n列列);三维三维 Am,n,p 数组的元素地址计算公式。即数组的元素地址计算公式。即：Loc(Ai)=?Loc(Ai,j)=?Loc(Ai,j,k)=?2.设矩阵设矩阵:若将若将A视为一个上三角矩阵时，请画出视为一个上三角矩阵时

28、，请画出A的的“按行优先存储按行优先存储”的压缩存储表的压缩存储表S，并写出，并写出A中元素之下标中元素之下标i,j与与S中元素之下标中元素之下标k之间的关系；之间的关系；若将若将A视为一个稀疏矩阵时，请画出视为一个稀疏矩阵时，请画出A的三元组表和十字链表结构。的三元组表和十字链表结构。A55=1 0 0 0 20 3 0 0 40 0 0 5 0 (行列下标i、j满足：1i，j5)0 0 0 6 00 0 0 0 7第五章习题第五章习题 3.设设 银行一天营业业务表头银行一天营业业务表头H：试用广义表形式表示试用广义表形式表示H，并用，并用head(H)和和tail(H)函数提取函数提取d2;画出画出H 的单链及双链结构。的单链及双链结构。存款存款A 取款取款B 活期活期 定期定期D 总存款总存款 支取支取 利息利息 总支付总支付 进款进款X a1 a3 b1 b2 b3 1年年 2年年 3年年 d1 d2 d3