数据结构数组和广义表

数据结构数组和广义表1第一页，共三十三页，编辑于2023年，星期三数组描述设二维数组: 其中:m、n为行列数,aij为第i行、第j列的元素,0≤i≤m-1,0≤j≤n-1;元素个数为m×n。二维数组可用形式化语言描述，即：

A(2)=(D,R)其中：D={aij|aij∈datatype,0≤i≤m-1,0≤j≤n-1};R={Row,Col}行关系：Row={<aij,aij+1>|aij,aij+1∈D,0≤i≤m-1,0≤j≤n-2}列关系：Col={<aij,ai+1j>|aij,ai+1j∈D,0≤i≤m-2,0≤j≤n-1}

a00a01

……a0j……

a0n-1………………….ai0ai1

……aij….…

ain-1………….am-10am-11

…am-1j…

am-1n-1A(2)=A[m][n]=2第二页，共三十三页，编辑于2023年，星期三数组描述 关系集Row和Col表明：除数组A(2)周边元素外的其它任一个元素aij，有两个直接前驱ai-1j，aij-1,和两个直接后继ai+1j，aij+1(周边元素的前驱或后继可不足两个)。n维数组也可按上述方法类似定义。 二维数组可如下描述:

多维数组是线性表的推广，而线性表是多维数组的特例。A[0]…A[i]

…A[m-1]=(A[0]………A[i]…….…A[m-1])-----线性表形式a00a01

……a0j……

a0n-1………………….ai0ai1

……aij….…

ain-1………….am-10am-11

…am-1j…

am-1n-1A(2)=A[m][n]=3第三页，共三十三页，编辑于2023年，星期三5.1.1数组的抽象数据类型 在算法语言中，数组一旦生成，其元素的存储空间就固定下来，故数组的运算一般不包括插入和删除这样的操作。ADTArray{D={aj1j2…jn|aj1j2…jn∈datatype，ji=0,…,bi-1其中i=1,2,…,n}n(n>0)为数组维数，bi是第i维长度，ji是数组元素第i维下标。 R={R1,R2,…,Rn} 其中：Ri={<aj1…ji…jn,aj1…ji+1…jn>|0≤jk≤bk-1，1≤k≤n且k≠i，0≤ji≤bi-2，aj1…ji…jn,aj1…ji+1…jn∈D，i=1,2,…,n} PArrayInit(&A,n,d1，d2,......dn) 操作结果：若维数n和各维长度合法，则生成一个n维数组A[d1][d2].....[dn]（C语言中，1≤n≤8）。ArrayDestroy(&A) 初始条件：数组A存在。操作结果：撤销数组A。ArrayGet(A,i1,...,in,&e) 初始条件：数组A存在，e∈datatype。操作结果：若各下标合法，则将元素A[i1][i2],...,[in]的值传给变量e。4第四页，共三十三页，编辑于2023年，星期三数组的抽象数据类型ArrayAssign(&A,i1,...,in,e) 初始条件：数组A存在，e∈datatype。 操作结果：若各下标合法，则将变量e的值传给数组元素A[i1][i2],...,[in]。}ADTArray；5.2数组的存储结构由于计算机的存储空间是一维的（或线性的），所以存储数组时，要将多维数组中的元素按某种次序映象到一维存储空间，即解决“降维”问题。5.2.1数组的静态存储方式1．数组的静态存储映像

在PASCAL和C等语言中，是按低维下标优先变化（或按行优先）的方式，存储数组中的元素。如在C语言中，二维数组的映像如图5.1所示。但在FORTRAN语言中，数组元素是按高维下标优先变化或按列优先方式，存储数组中的元素。 5第五页，共三十三页，编辑于2023年，星期三数组的存储映像

a00…a0,n-1…ai0…ai,n-1……am-1,n-1映像

（存储器）a00a01

……a0j……

a0n-1………………….ai0ai1

……aij….…

ain-1………….am-10am-11

…am-1j…

am-1n-1A[m][n]=图5.1思考：1.三维以上数组如何映像? 2.“按列优先”如何映像?6第六页，共三十三页，编辑于2023年，星期三2.静态数组元素的地址计算以C语言为例。设数组元素的起始地址为b,每个元素占用L个单元（元素所占单元量由元素的类型而定），元素a的地址用Loc(a)表示。1）一维数组： 即:Loc(a0)=b; Loc(a1)=b+L;

Loc(ai)=b+i×L;

规律：任一元素ai的地址:

a0a1

…ai-1ai…an-1A[n]=(

a0,

a1,……ai

,……an-1)

起始地址b+(ai前的元素个数i)×L

起址b:b+L:……b+i•L:L图5.27第七页，共三十三页，编辑于2023年，星期三数组元素的地址计算2）二维数组：a00…a0,n-1…ai0…aij……am-1,n-1由图5.3知：Loc(a00)=b Loc(ai0)=b+(ai0前元素个数)•L=b+(i•n)•L

Loc(aij)=b+(aij前元素个数)•L=b+[i×n+j]×L例5-1设二维数组A[7][8]，起始地址b=1000，每个元素所占单元量L=3，则Loc(a5,6)=1000+(5•8+6)3=1138。

inj映像

起址b:b+L:……b+[i×n]×L:…b+[i•n+j]•L:图5.3a00a01

……a0j……

a0n-1………………….ai0ai1

……aij….…

ain-1………….am-10am-11

…am-1j…

am-1n-1A[m][n]=8第八页，共三十三页，编辑于2023年，星期三数组元素的地址计算3）三维数组：

由图5.5可知： Loc(a000)=b图5.5 Loc(ai00)=b+(i•n•p)•L Loc(aij0)=b+(i•n•p+j•p)•L

Loc(aijk)=b+(i×n×p+j×p+k)×Laijk前的元素个数。a000ai00aij0aijk9第九页，共三十三页，编辑于2023年，星期三数组元素的地址计算4）n维数组从以上的地址公式推导中得出这样一条规律：数组中任一元素的地址=起址b+该元素前的个数×元素单元量L。故n维数组A[u1][u2]…..[un]中任一元素ai1....in的地址为：Loc(ai1i2……in)=b+(i1•u2•u3•

…

•un+i2•u3•u4•

…un+…+in-1•un+in)•L

=b+()×L 元素按“列优先”方式存储时，地址计算方法类似，不再赘述。 有了数组元素的地址计算公式，给出相应参数后，能够很快求出任一元素的地址，然后按地址存取相应元素，故对数组的存取是随机存取（或按公式存取）。5.2.2数组的动态存储方式（略）10第十页，共三十三页，编辑于2023年，星期三5.2矩阵的压缩存储 信息的压缩存储是一项专业技术，在当今的多媒体应用中显得尤为重要。但本节只是讨论矩阵（或二维数组）中元素的压缩存储。 在矩阵中，往往会出现许多值相同的元素或０元素，为节省存储空间，可以采用某些技术对这类矩阵进行压缩存储。压缩存储的原则是：对多个值相同的元素只存储其中之一，对０元素甚至不分配存储空间。5.3.1特殊矩阵的压缩存储特殊矩阵：值相同的元素或０元素在矩阵中的分布遵循一定规律。1.对称矩阵：

满足aij=aji，(1≤i,j≤n)a11a22

aii…

ann

An×n=

aijaji11第十一页，共三十三页，编辑于2023年，星期三特殊矩阵的压缩 aij与aji对称相等，二者只需分配一个存储单元，即只存储包括主对角线的下三角(或上三角)元素。于是An×n所需单元数为n(n+1)/2，而不压缩存储需要n2个单元。当n很大时，几乎能压缩原存储空间的一半。 具体做法：设置数组S[n(n+1)/2+1]作为An.n的存储空间，且按行的次序存放An×n中包括主对角线的下三角元素，如图5.5所示。a11a21a22…aij…annS[n(n+1)/2+1]:123…..….….k………..n(n+1)/2 图5.5其中aij存入S[k]单元，下标（i,j）与k的关系为：

i(i-1)/2+j当i≥j时；S[i(i-1)/2+j]当i≥j时；k=即：aij=

j(j-1)/2+i当i<j时。S[j(j-1)/2+i]当i<j时。a11a22

…aii

annAn×n=

aij12第十二页，共三十三页，编辑于2023年，星期三特殊矩阵的压缩2．三角矩阵：

（下三角矩阵）（上三角矩阵）

a11a22

…aii

annAn×n=

aijCa11a22

aii…

annCaijCa11a12…aij…annS[n(n+1)/2+1]:012…..….….k………..n(n+1)/2

K=—+=(i-1)n–(i-1)(i-2)/2+(j-i+1)=(i-1)(2n-i)/2+j(i≤j)

图5.6

而当(i>j)时，K=0.对于下三角矩阵，类似于对称矩阵，即只存储包括主对角线的下三角元素。而当i<j时，aij取C即可。对于上三角矩阵，压缩方法如图5.6所示。13第十三页，共三十三页，编辑于2023年，星期三特殊矩阵的压缩3．对角线矩阵（三对角线）：按行顺序压缩于S中，如图5.7所示。

Ca11a12…aij…annS[3n-1]:012…..….….k………..3n-2a11a12a21a22a23..…..…

aii-1aiiaii+1..…..…

ann-1annAn×n=

CC图5.7

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=20其他。k=14第十四页，共三十三页，编辑于2023年，星期三5.3.1稀疏矩阵的压缩存储 特殊矩阵中同值元素的分布有一定的规律可循，而有的矩阵，０元素很多（如同一个画面上有几个亮点，其余全是空白），但分布无规律，称这类矩阵为稀疏矩阵。例5-2设一个6×7的矩阵如下： 则A6×7可以视为一个稀疏矩阵。对于矩阵Am×n，设非0元素个数为t，若δ=t/(m×n)≤0.2，则可以将其视为稀疏矩阵。显然，为节省存储空间，须对这类矩阵压缩存储空间，原则是只存储非0元素。一般有“三元组表”和“十字链表”的压缩存储方法。010200000000003000040005000006000007008000

A6×7

=

15第十五页，共三十三页，编辑于2023年，星期三

1.三元组表 三元组：（i,j,v），其中i,j分别为非0元素的行、列号，v存放非0元的数值。以行优先的顺序将矩阵中非0元以三元组形式存入一数组，即所谓的三元组表。三元组表的存储结构的描述：#definemaxsize64//最大非0元个数typedefstruct//三元组类型{inti,j;datatypev;}tritype;//三元组说明符typedefstruct{tritypedata[maxsize+1];//三元组表intmu,nu,tu;//原矩阵的行、列、非0元个数}Tsmtype,*Tsmlink;//三元组表说明符若说明：TsmlinkA;A=(Tsmlink)malloc(sizeof(Tsmtype));则指针变量A指向一个如图5.8所示的三元组表。 对例5-2中A6×7，设每个元素占16个字节，若不压缩存储，需6×7×16=672（字节），而压缩成三元组表时，i,j为整型，故共需：2×16+8×16=160（字节）。ijv121142313364435526617648A->data[1]………………A->data[tu]

图5.816第十六页，共三十三页，编辑于2023年，星期三三元组表的转置 然而，稀疏矩阵的压缩存储会给矩阵运算带来一些不便，算法要复杂些。这里的运算指求矩阵的转置，两矩阵相加和相乘等。我们只讨论矩阵的转置的算法。未压缩前，求矩阵A的转置矩阵B，算法很简单：for(col=1;col<=nu;col++)for(row=1;row<=mu;row++)B[col][row]=A[row][col];例5-3：02004608000900030000

A4×5=

ijv12215421623832941306032090080000004000

B5×4=

现在，要通过A的三元组表求其转置矩阵B的三元组表。ijv12614321223932851417第十七页，共三十三页，编辑于2023年，星期三三元组表的转置算法思路：1)矩阵A的所有列转化成B的所有行； 2)

对A中的每一列col(1～nu)，扫描所有非0元（1～tu），若有非0元的列号j=当前列col，则将该非0元行列互换，送到目标三元组表。 如例5-3中矩阵A，当前列col=1时，因A->data[3].j=1,故将A->data[3]转置：(1，2，6)=>B->data[1]，又A->data[6].j=1，所以A->data[6]转置：(1，4，3)=>B->data[2]，完成第一列的转换，依此类推。算法描述：voidTransm(TsmtypeA,TsmtypeB){intp,q,col;B->mu=A->nu;B->nu=A->mu;B->tu=A->tu;if(A->tu!=0){q=1;//目标表的序号for(col=1;col<=A->nu;col++)for(p=1;p<=A->tn;p++)

if(A->data[p].j==col){B->data[q].i=A->data[p].j;//行列互换B->data[q].j=A->data[p].i;B->data[q].v=A->data[p].v;q++;}}}18第十八页，共三十三页，编辑于2023年，星期三三元组表的转置

ijv122154216238329413

p

12345602004608000900030000

A4×5=

12345colijv126

q

12345614321223932851406032090080000004000

B5×4=

（矩阵A的三元组表）

图5.10

（转置后的三元组表）算法的时间复杂度：O(t×n)n=列数,t=非0元个数。改进算法的复杂度：O(t+n)（略）19第十九页，共三十三页，编辑于2023年，星期三2.十字链表 十字链表是以链表结构形式存储一个稀疏矩阵。矩阵中非0元设置成如下形式的节点：其中i、j分别存放非0元的行列号，head/data或作为一非0元的值域（data）或作为头节点的链指针(head)；down为指向相同列下一个非0元节点的指针，right为指向相同行下一非0元节点的指针。节点类型描述： typedefstructnode {inti,j; union{structnode*head; datatypedata; }vdata; structnode*down,*right; }nodetype,*tlink;ijhead/datadownright20第二十页，共三十三页，编辑于2023年，星期三十字链表111144222313445004400000000000000L例5-4设稀疏矩阵：1004020030000005

A4×4=

A的十字链表如图5.11：21第二十一页，共三十三页，编辑于2023年，星期三建立十字链表算法思路：先构造空表，其中S取矩阵行列数的最大值，即S=max(m,n)。依次读入每个非0元(i,j,v)，生成一个非0元的节点，对该节点赋读入的值后，将其插入第i行链表和第j列链表的正确位置。算法描述：voidCreattenlink(tlinkL,intm,intn,intt) //L为头指针，m,n,t分别为行列号和非0元个数{tlinkp,q,H[maxsize];inti,j,k,s;datatypev;if(m>n)s=m;elses=n;//确定头节点的个数L=(tlink)malloc(sizeof(nodetype));//申请总的头节点L->i=m;L->j=n;//置行列数H[0]=L;for(i=1;i<=s;i++)//建立头节点链表{p=(tlink)malloc(sizeof(nodetype));p->i=p->j=0;p->down=p->right=p;H[i]=p;H[i-1]->vdata.head=p;}H[s]->vdata.head=L;//构成循环22第二十二页，共三十三页，编辑于2023年，星期三建立十字链表for(k=1;k<=t;k++)//处理t个非0元{scanf(“%d%d%d”,&i,&j,&v);//读入一个非0元（i,j,v）p=(tlink)malloc(sizeof(nodetype));//申请节点存放非0元p->i=i;p->j=j;p->vdata.data=v;//赋值q=H[i]； //取第i行链表头节点指针while((q->right!=H[i])&&(q->right->j<j)) q=q->right;//找当前非0元节点在行链表中的位置 p->right=q->right;q->right=p;//当前非0元节点插入q节点之后 q=H[j]； //取第j列链表头节点指针 while((q->down!=H[j])&&(q->down->i<i)) q=q->down;//找当前非0元节点在列链表中的位置 p->down=q->down;q->down=p;//非0元节点节点插入q节点之后 }}23第二十三页，共三十三页，编辑于2023年，星期三5.4广义表的定义及其操作5.4.1广义表的定义

广义表又称列表(lists),是线型表的推广。在线型表L=(a0……ai……an-1)中，ai是单元素或原子，即ai本身不再是一个DS，而广义表记为： LS=(d0d1……di……dn－1) 其中di（0≤i≤n-1）既可以是一个原子，又可以是另一个表（称为子表），即表中还可以套表。广义表LS的形式化描述为：

LS=(D,R) 其中：D={di|di∈datatypeordi∈LS(递归定义)，i=0,1,.....n-1,n≥0}

R={<di,di+1>|di,di+1∈D,0≤i≤n-2} 式中n为表长（n=0时为空表），若di为原子，则称di为LS的单元素，否则di称为LS的子表（满足递归定义)。对非空广义表定义两个函数：Gethead(LS)=d0； Gettail(LS)=(d1...dn-1)。 即Gethead(LS)是LS的第一元素d0（当然d0可以为子表），而Gettail(LS)是LS中d1...dn-1的一个子表。对广义表的其它运算（如查找，插入和删除等）类似于线性表的运算（见5.4.2）。24第二十四页，共三十三页，编辑于2023年，星期三例5-5

广义表的例子 约定：大写字母A～Z为表名，小写字母a～z为单元素。 A=()或A()——空表，表长=0，无表头，表尾； B=(a,b)或B(a,b)——线性表特例,表长=2,Gethead(B)=a,Gettail(B)=(b)； C=(e,B)或C(e,B)——表长=2，Gethead(C)=e,Gettail(C)=(B)=((a,b)),表C可以表示为：C(e,(a,b))； D=(A,B,C)或D(A,B,C)——表长=3，Gethead(D)=A=(), Gettail(D)=(B,C)=((a,b),(e,(a,b)))； E=(a,E)——表长=2，Gethead(E)=a,Gettail(E)=(E),整个表E为(a,(a,(a,...)))，它为一个特殊的广义表，称为递归表，或无限表。从例5-5可以看出，广义表有如下特点：（1）表可以嵌套——表中元素可以是一个表，称为子表，而子表还可以有子表。如例5-5中表B和表C的结构如图5.13所示。图5.13CeBababB25第二十五页，共三十三页，编辑于2023年，星期三广义表的例子（2）表可以共享——表可以是其它表的子表,或表中的元素可取自其他表。如例5-5中表D包含表A、B、C，或A、B、C为D的子表,如图5.16所示。（3）表可以递归——表中元素可以是表本身。如例5-5中表E。

EaDABCabe^图5.16另外，表中任一单元素可由Gethead(Ls)和Gettail(Ls)函数导出，如取表A=(a,(b,d,e))中单元素d的运算为：

Gethead(Gettail(Gethead(Gettail(A))))

26第二十六页，共三十三页，编辑于2023年，星期三5.5广义表的存储结构 对于广义表LS=(d0…di…dn-1)，由于di可以是单元素或子表，故用顺序存储结构表示LS较为困难，一般采用链表存储，称为广义链表。5.5.1广义表的链式存储1．单链表示法元素di的节点形式：其中：0当di为单元素时；data当atom=0时；atom=data/link=1当di为子表时。link当atom=1时。next意义同线性链表，指向di+1所在节点。节点描述：typedefstructnode {intatom; union{datatypedata;structnode*link; }dtype; structnode*next; }Lsnode;atomdata/linknext27第二十七页，共三十三页，编辑于2023年，星期三广义表的存储 为操作方便，对每一广义表引入头节点，其形式同一般的表节点：

例5-5中广义表A、B、C、D、E的单链表如图5.15所示。1^1^^AA=()图5.150a0b^1^BB=(a，b)0e1^1^CC=(e，B)11^1^1^DD=(A，B，C)0a1^1^EE=(a，E)28第二十八页，共三十三页，编辑于2023年，星期三广义表的存储2．双链表示法元素di的节点形式：其中：指向子表的指针当di为子表时；link1=^当di为原子时。表名当di为子表时；data=link2：指向di+1所在的节点。原子值当di为原子时。例5-5中几个广义表的双链表结构如图5.16：

datalink1link2BA^C^DE^a^EB^e^Cb^^a^A=^B29第二十九页，共三十三页，编辑于2023