数组和广义表

数组和广义表第1页，课件共59页，创作于2023年2月5.1数组的定义一维数组定长的线性表，数据元素是原子类型二维数组定长的线性表，每个数据元素也是一个定长线性表A=(a1,a2,a3,…,an)A=(a1,a2,…am)第2页，课件共59页，创作于2023年2月5.1数组的定义数组的逻辑结构特点：结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。比如：一维数组可以看作一个线性表；二维数组可以看作“数据元素是一维数组”的一维数组；三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。第3页，课件共59页，创作于2023年2月5.1数组的定义n维数组A(0..b1-1,0..b2-1,…,0..bn-1)n维数组中共含有个数据元素每个数据元素都受着n个关系的约束数组一旦被定义，维数、维界就不再改变操作：存取，修改第4页，课件共59页，创作于2023年2月5.2数组的顺序表示和实现一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动采用顺序存储结构表示数组存储单元是一维的：存放一维数组：按下标顺序分配；存放多维数组，则用一组连续存储单元存放数组的数据元素就有一个次序约定问题第5页，课件共59页，创作于2023年2月5.2数组的顺序表示和实现1．以行为主序（或先行后列）的顺序存放如BASIC、PASCAL、C等2．以列为主序（先列后行）的顺序存放如FORTRAN语言第6页，课件共59页，创作于2023年2月5.2数组的顺序存储结构次序约定以行序为主序以列序为主序

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l

按行序为主序存放

amn

……..

am2

am1

……….

a2n

……..

a22

a21

a1n

…….

a12

a1101n-1m*n-1n

按列序为主序存放01m-1m*n-1m

amn

……..

a2n

a1n

……….

am2

……..

a22

a12

am1

…….

a21

a11

a11

a12

……..

a1n

a21

a22……..

a2n

am1

am2

……..amn

….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l

第7页，课件共59页，创作于2023年2月

5.2数组的顺序表示和实现分配规律：以行为主序的分配规律：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。以列为主序分配的规律：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。第8页，课件共59页，创作于2023年2月寻址运算：设有m×n二维数组Amn，按元素的下标求其地址以“以行为主序”寻址：设数组的基址为LOC(a11)，每个数组元素占据l个地址单元，则aij的物理地址

LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*l在C语言中，数组中每一维的下界定义为0，则：LOC(aij)=LOC(a00)+(i*n+j)*l第9页，课件共59页，创作于2023年2月推广到一般的二维数组：A[c1..d1][c2..d2]，则aij的物理地址计算函数为：LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*l自己考虑一下以列序为主序存放时的寻址运算第10页，课件共59页，创作于2023年2月同理对于三维数组Amnp，即m×n×p数组，数组元素aijk其物理地址为：LOC(aijk)=LOC(a111)+((i-1)*n*p+(j-1)*p+k-1)*l推广到一般的三维数组：A[c1..d1][c2..d2][c3..d3]，则aijk的物理地址为：LOC(i,j)=LOC(ac1c2c3)+((i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3))*l第11页，课件共59页，创作于2023年2月5.3矩阵的压缩存储矩阵——许多科学与工程计算问题中研究的数学对象用高级语言编程时，一般用二维数组来存储矩阵元素，有些程序设计语言中还提供了各种矩阵运算特殊矩阵：矩阵中有许多值相同的元素或零元素，且分布有一定规律。如：对称矩阵、三角矩阵、对角矩阵等稀疏矩阵：矩阵中有很多零(或值相同的元素)，且分布无规律压缩存储：为多个值相同的元只分配一个存储空间，零元不分配空间第12页，课件共59页，创作于2023年2月5.3.1特殊矩阵对称矩阵n阶矩阵，且aij=aji(1≤i,j≤n)为每一对对称元分配一个存储空间可将n2个元压缩存储在n(n+1)/2个元的空间中上三角下三角行序为主序列序为主序第13页，课件共59页，创作于2023年2月5.3.1特殊矩阵对称矩阵行序为主序存储下三角{a11,

a21,

a22,

a31,

a32,…,

an1,

an2,…,

ann}第14页，课件共59页，创作于2023年2月5.3.1特殊矩阵对称矩阵用一维数组sa[n(n+1)/2]以行序为主序存储下三角{a11,

a21,

a22,

a31,

a32,…,

an1,

…,

ann}01234n(n-1)/2n(n+1)/2-1k第15页，课件共59页，创作于2023年2月5.3.1特殊矩阵对称矩阵用一维数组sa[n(n+1)/2]以行序为主序存储下三角aij123456前i-1行，共i(i-1)/2个元本行共j个元k=i(i-1)/2+j-1aij交换i,j第16页，课件共59页，创作于2023年2月5.3.1特殊矩阵对称矩阵用一维数组sa[n(n+1)/2]以行序为主序存储下三角sa[k]和矩阵元aij之间存在一一对应关系：第17页，课件共59页，创作于2023年2月5.3.1特殊矩阵三角矩阵下三角矩阵：矩阵的上三角(不含主对角线)的矩阵元均为常数c(或零)上三角矩阵：矩阵的下三角(不含主对角线)的矩阵元均为常数c(或零)下(上)三角矩阵，只需存储下(上)三角的元素，再加一个存储常数c的存储空间也有两种存储方式：行序为主序、列序为主序与对称矩阵类似第18页，课件共59页，创作于2023年2月下三角矩阵

a11

00

……..0

a21a22

0

……..0

an1an2an3……..ann

….

0a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：第19页，课件共59页，创作于2023年2月5.3.1特殊矩阵例题：设有下三角矩阵An×n，以行序为主序存储其下三角元素，基地址为β，每个数据元素占c个存储单元。求aij的地址(i≥j)。第1行存储1个元素…第i-1行存储i-1个元素共(i-1)i/2个元素第i行在aij之前共

j-1个元素β+[(i-1)i/2+j-1]c第20页，课件共59页，创作于2023年2月5.3.1特殊矩阵思考：设有下三角矩阵An×n，以列序为主序存储其下三角元素，基地址为β，每个数据元素占c个存储单元。求aij的地址(i≥j)。aij前j-1列多少个元素?本列(第j列)aij前多少个元素?第21页，课件共59页，创作于2023年2月对角矩阵所有非零元都集中在主对角线为中心的带状区域中

a11

a120

…………….

0

a21

a22a23

0

……………0

0

0

…an-1,n-2an-1,n-1

an-1,n

0

0

……an,n-1ann.

0

a32a33a34

0

………0

……………第22页，课件共59页，创作于2023年2月按行优序为主序来存储。a11a12

a21a22a23a32

……ann-1ann求LOC(i,j)：在aij之前有i-1行,共有3*(i-1)-1个非零元素，在第i行，有j-i+1个非零元素，非零元素aij的地址为：LOC(i,j)=LOC(1,1)+[3*(i-1)-1+(j-i+1)]*d=LOC(1,1)+(2i+j-3)*d

除第1行和第n行是2个元素外，每行的非零元素都是3个，因此，需存储的元素个数为3n-2。K=012345……3n-43n-3第23页，课件共59页，创作于2023年2月5.3.2稀疏矩阵什么是稀疏矩阵？假设在m×n矩阵中，有t个非零元，定义矩阵的稀疏因子δ≤0.05时，矩阵称为稀疏矩阵零非常多，且分布无规律时压缩存储：只存储非零元第24页，课件共59页，创作于2023年2月5.3.2稀疏矩阵示例只存储非零元的值，同时必须记下所在行、列位置一个三元组(i,j,aij)惟一确定了矩阵的一个非零元表示所有非零元的三元组表就确定了整个矩阵×第25页，课件共59页，创作于2023年2月5.3.2稀疏矩阵三元组表的不同表示方法三元组顺序表——顺序存储结构将三元组按行优先的顺序，同一行中列号从小到大的规律排列成一个线性表，称为三元组表，采用顺序存储方法存储该表。行逻辑链接的顺序表——带有附加信息的顺序存储结构十字链表——链式存储结构第26页，课件共59页，创作于2023年2月行序为主序5.3.2稀疏矩阵示例

1234567123456((1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))(6,7,8)第27页，课件共59页，创作于2023年2月一、三元组顺序表要唯一的表示一个稀疏矩阵，需要存储：

1，三元组表；

2，该矩阵的行数、列数；

3，矩阵的非零元素的个数（为了运算方便）第28页，课件共59页，创作于2023年2月存储的思想实现：

defineSMAX1024/*一个足够大的数*/typedefstruct{inti,j;/*非零元素的行、列*/datatypev;/*非零元素值*/}Triple;/*三元组类型*/typedefstruct{intmu,nu,tu;/*矩阵的行、列及非零元素的个数*/Tripledata[SMAX];/*三元组表*/}TSMatrix;/*三元组表的存储类型*/第29页，课件共59页，创作于2023年2月压缩存储下矩阵的转置转置矩阵的定义：对于一个m×n的矩阵M,它的转置矩阵T是一个n×m的矩阵，且T[i][j]=M[j][i],(1<=i<=n，1<=j<=m)。请看下面具体示例。第30页，课件共59页，创作于2023年2月矩阵转置rowcole12616-234-842346751-12539rowcole15-1221624335943-861-2647第31页，课件共59页，创作于2023年2月矩阵转置求一个矩阵的转置矩阵可以经过下列步骤来完成：将矩阵的行列值互换；

对每个三元组所表示的非零元，将该元素的行、列值互换；按行序重排三元组。

第32页，课件共59页，创作于2023年2月三元组表的矩阵转置运算rowcole12616-234-842346751-12539rowcole15-1221624335943-861-26471234567第33页，课件共59页，创作于2023年2月矩阵转置/TSMatrixTransMatrix(TSMatrixA,TSMatrixB){∥采用三元组表方式存储，实现矩阵的转置

B.mu=A.nu;B.nu=A.mu;B.tu=A.tu;if(B.tu){q＝l;for(j＝1;j＜＝A.n;j++)for(p＝1;p＜＝A.len;++p)if(A.data[p]．col==j){B.data[q]．row=A.data[p]．col;B.data[q]．col=A.data[p]．row;B.data[q]．e=A.data[p]．e;

q++;}}returnB;}∥TransMatrix

第34页，课件共59页，创作于2023年2月算法分析时间复杂度为：nu*tu对于mu*nu矩阵，一般算法的时间复杂度为：O(mu*nu)。当非零元个数tu和mu*nu同数量级时，该算法的时间复杂读为：O(mu*nu2);这里每次找第j列的元素时，必须从头开始遍历。若知道T的每一行的非零元素的开始位置，就可把算法的时间复杂度降低。第35页，课件共59页，创作于2023年2月矩阵的快速转置思想：一遍扫描三元组表A.data，将每个元素放到转置后的三元组表B.data的正确位置上。因此，需求出矩阵A中每列第一个非零元的位置和每列非零元素的个数。为此，增加存放每列非零元素个数的一维数组number[]和每列第一个非零元素在B中位置的一维数组position[]。并有以下公式：。position[1]=1position[j]=position[j-1]+number[j-1]2≤j≤A.tu

第36页，课件共59页，创作于2023年2月number和position向量实例rowcole12616-234-842346751-12539rowcole15-1221624335943-861-2647j123456number[j]121102position[j]124566矩阵A的number和position向量的值:第37页，课件共59页，创作于2023年2月TSMatrixFastTransMatrix(TSMatrixA,TSMatrixB){∥三元组表上实现矩阵的快速转置的算法

B.mu=A.nu;B.nu=A.mu;B.tu=A.tu;if(A.tu){for(j=1;j<=A.nu;j++)∥矩阵A每一列非零元初始化为零

number[j]=0;for(t=1;t<=A.tu;t++)∥求矩阵A每一列得非零元个数

number[A.data[t].col]++;position[1]=1;for(j=2;j<=A.nu;j++；∥求A.data第j列第一个非零元在B.data中的序号

position[col]=position[col-1]+number[col-1];

三元组表的矩阵快速转置(1)第38页，课件共59页，创作于2023年2月

for(p=1;p<=A.tu;p++)∥求转置矩阵B的三元组表

{j=A.data[p].col;q=position[j];B.data[q].row=A.data[p].col;

B.data[q].col=A.data[p].row;B.data[q].e=A.data[p].e;

position[j]++;}}//ifreturnB;}//算法结束时间复杂度为：O(nu+tu);三元组表的矩阵快速转置(2)第39页，课件共59页，创作于2023年2月第40页，课件共59页，创作于2023年2月第41页，课件共59页，创作于2023年2月二、十字链表每一个非零元用一个结点表示每个结点含5个域：i,j,e三个域分别表示该非零元所在的行、列、值指针域down用以指向同一列中下一个非零元指针域right用以指向同一行中下一个非零元同一行的非零元通过right域链接成一个线性链表同一列的非零元通过down域链接成一个线性链表每个非零元的结点既是某个行链表中的结点，又是某个列链表中的结点

j

e

rightdown

i第42页，课件共59页，创作于2023年2月5.3.2稀疏矩阵2-4∧∧2515∧∧11-2∧4621∧∧41714-1∧∧3∧

7000150

0-40000

-2000021

000-100M=第43页，课件共59页，创作于2023年2月5.3.2稀疏矩阵三、十字链表

7000150

0-40000

-2000021

000-100M=用一个数组M.rhead存储行链表的头指针用一个数组M.chead存储列链表的头指针M.mu，M.nu，M.tu第44页，课件共59页，创作于2023年2月稀疏矩阵的十字链表存储表示：TypedefstructOLNode{inti,j;Elemtypee;structOLNode*right,*down;}OLNode*Olink;Typedefstruct{Olinkrhead,chead;intmu,nu,tu;}CrossList;第45页，课件共59页，创作于2023年2月5.4广义表的定义广义表中的元素既可以是原子(单个元素)，也可以是子表(另一个广义表)广义表，也称为列表(lists)，是n≥0个元素α1,α2,…,αn的有限序列;每一个αi或者是原子，或者是一个子表广义表通常记为LS=(α1,α2,…,αn)，其中LS为广义表的名字，n为广义表的长度，每一个αi为广义表的元素一般用大写字母表示广义表，小写字母表示原子第46页，课件共59页，创作于2023年2月5.4广义表的定义当广义表LS=(α1,α2,…,αn)非空时，称第1个元素α1为LS的表头(head)，称其余元素组成的表(α2,…,αn)是LS的表尾(tail)广义表的定义是递归的。示例：A=()B=(e)C=(a,(b,c,d))D=(A,B,C)E=(a,E)长度每一个元素表头表尾A长度为0空表B长度为1第1个元素e表头e表尾()C长度为2第1个元素a第2个元素(b,c,d)表头a表尾((b,c,d))D长度为3第1个元素A第2个元素B第3个元素C表头A表尾(B,C)E长度为2第1个元素a第2个元素E表头a表尾(E)第47页，课件共59页，创作于2023年2月5.4广义表的定义广义表的性质:列表的元素可以是子表，而子表的元素还可以是子表，…因此，列表是一个多层次的结构.列表可以为其它列表所共享列表可以是一个递归表DABCeabcdA=()B=(e)C=(a,(b,c,d))D=(A,B,C)E=(a,E)第48页，课件共59页，创作于2023年2月5.4广义表的定义广义表的深度：广义表展开成原子后，所含括号的层数A=()B=(e)C=(a,(b,c,d))D=(A,B,C)E=(a,E)A=()B=(e)C=(a,(b,c,d))D=((),(e),(a,(b,c,d)))E=(a,(a,(a,(a,…))))1123∞第49页，课件共59页，创作于2023年2月

2广义表基本运算CreateLists(ls)：根据广义表的书写形式创建一个广义表ls。IsEmpty(ls)：若广义表ls空，则返回True；否则返回False。Length(ls)：求广义表ls的长度。第50页，课件共59页，创作于2023年2月

2广义表基本运算Locate(ls，x)：在广义表ls中查找数据元素x。Merge(ls1，ls2)：以ls1为头、ls2为尾建立广义表。CopyGList(ls1，ls2)：复制广义表，即按ls1建立广义表ls2。Head(ls)：返回广义表ls的头部。Tail(ls)：返回广义表的尾部。Depth(ls)：求广义表ls的深度。……

第51页，课件共59页，创作于2023年2月5.5广义表的存储结构广义表的数据元素不同构(或是原子，或是子表)，通常采用链式存储结构，每个数据元素用一个结点表示.原理：广义表除空表外，可分成表头、表尾，表尾一定是广义表广义表由若干个元素组成，每个元素既可以是原子，又可以是子表结点分为两类：原子结点、表结点按结点形式的不同，广义表的链式存储结构又可以分为:

头尾表示法，孩子兄弟表示法。第52页，课件共59页，创作于2023年2月5.5广义表的存储结构第一种存储结构——头尾链表存储表示原理：广义表除空表外，可分成表头、表尾，表尾一定是广义表tag=1hptp表结点指向表尾指向表头标志域tag=0data标志域原子结点值域第53页，课件共59页，创作于2023年2月其形式定义说明如下：typedefenum{ATOM,LIST}Elemtag;/*ATOM=0：单元素；LIST=1：子表*/typedefstructGLNode{Elemtagtag;/*标志域，用于区分元素结点和表结点*/union{/*元素结点和表结点的联合部分*/datatypedata;/*data是原子结点的值域*/struct{structGLNode*hp,*tp；

}ptr;