合工大计算机专业相关课件数据结构

数据结构（第十一章

数组与广义表）

DataStructures胡学钢张晶计算机与信息学院2009年2月1数组－定义和运算1、定义：数组：有限个相同类型的变量组成的序列。若每个变量是一维数组，则为二维数组；若每个变量是n-1维数组，则为n维数组。2、运算：给定一组下标，存/取数组元素的值；

——计算元素的地址a11,a12,…,a1na21,a22,…,a2na31,a32,…,a3n…………am1,am2,…,amnm×n（a1,a2,a3,…,an)2数组－顺序存储(行优先)1、行优先存储：a11,a12,…,a1na21,a22,…,a2na31,a32,…,a3n…………am1,am2,…,amnm×na1n…a11a12…a21a22a2n…amnam1am2…aij序号num=aij:(i-1)*n+j地址:addr=addr0+(num-1)*c(其中c是元素的长度)32、列优先存储：a11,a12,…,a1na21,a22,…,a2na31,a32,…,a3n…………am1,am2,…,amnm×nam1…a11a21…a21a22am2…amna1na2n…aij序号num=aij:(j-1)*m+i地址:addr=addr0+(num-1)*c(其中c是元素的长度)数组－顺序存储(列优先)4数组－对称矩阵的压缩存储（一）特殊矩阵的压缩存储（行优先）：1、对称矩阵aij=ajia11,a12,a13,…,a1na21,a22,a23,…,a2na31,a32,a33,…,a3n………am1,am2,am3,…,amnm×na11a21a22…amnam1am2…aija31a32a33序号num=aij:1+2+3+…+(i-1)+j地址:addr=addr0+(num-1)*c(其中c是元素的长度)下三角i>j5数组－三角矩阵的压缩存储对称矩阵的求解方法同样使用于三角矩阵。a11,a21,a22,a31,a32,a33,………am1,am2,am3,…,amnm×n06数组－对角矩阵的压缩存储对角矩阵a11,a12a21,a22,a23a32,a33,a34……ann-1,annn×n00a11a12a21a33anna34ann-1…aija22a23a32序号num=(3(i-1)-1)+(j-i+2)=2i+j-2|i-j|<=1

7数组－稀疏矩阵的压缩存储（二）稀疏矩阵的压缩存储：数组中非零元素非常少，称为稀疏矩阵。00010201000000003006000005×5(1,4,1)(2,1,2)(2,3,1)(4,2,3)(4,5,6)(5,5,5)三元组8广义表

广义表

一、广义表的定义

二、广义表的运算

三、广义表的示例

9一、广义表的定义定义：L是由n个元素a1,a2…an组成的有限序列，其中ai：是原子或者是一个广义表；记作：L=(a1,a2…an)(n>=0)。 N=0时L为空表，记作：L=()。 线性表的推广； 每个元素可以是一个不可分割的原子，也可以是一个表。10二、运算head(A)——取表头：返回表A中第一个元素的值。tail(A)——取表尾：返回表A中删除第一个元素后所得的表。11三、示例—广义表长度、图形化A=(a,b,c) n=3B=(a,(b,c)) n=2C=(A,B) n=2D=(d,D) n=2CABabcabcDd12三、示例—运算例：A=(a,b,c)n=3B=(a,(b,c))n=2C=(A,B)n=2D=(d,D)n=2head(A)=a;tail(A)=(b,c)tail(B)=((b,c))tail(C)=(B)tail(D)=D如何求表中第二个、第三个元素？head(tail(A))head(tail(tail(A)))区分：广义表()、(())不同。取出下面广义表中的y：L=((x，(a，b))，((x，(a，b))，y))head(tail(head(tail(L))))13广义表

广义表