多维数组和广义表

,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,多维数组和广义表,要 求,2,第,6,章 目 录,6-1 多维数组,6-2 特殊矩阵的压缩存储,6-3 稀疏矩阵,6-4 广义表,小 结,验证性实验：,稀疏矩阵和广义表子系统,自主性实验6：稀疏矩阵十字链表的存储,单元练习,6,3,6-1,多维数组,6.1.1 逻辑构造,数组作为一种数据构造，其特点是构造中的元素可以是具有某种构造的数据，但属于同一数据类型。比方，一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组的一维数组，三维数组可以看作“数据元素是二维数组的一维数组。一般把三维以上的数组称为多维数组，n维的多维数组可以视为n1维数组元素组成的线性构造。其中每一个一维数组又由m个单元组成。,图6-1是一个n行m列的数组。,4,5,在二维数组中的每一个元素最多可以有两个直接前驱和两个直接后继边界除外，在n维数组中的每一个元素最多可以有n个直接前驱和n个直接后继。所以多维数组是一种非线性构造。,数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，通常在很多高级语言中数组一旦被定义，每一维的大小与上下界都不能改变。因此，在数组上一般不做插入或删除数据元素的操作。在数组中经常做的两种操作如下。,1取值操作：给定一组下标，读取其对应的数据元素。 2赋值操作：给定一组下标，存储或修改与其相对应的数据元素。,6,6.1.2 存储构造,通常，数组在内存被映象为向量，即用向量作为数组的一种存储构造，这是因为在计算机内存储构造是一维的。数组的行列固定后，通过一个映象函数，就可以根据数组元素的下标得到它的存储地址。对于一维数组只要按下标顺序分配即可；对多维数组分配时，要把它的元素映象存储在一维存储器中。,1存储方式,1以行为主row major order,以行为主的存储方式也称为按行优先顺序方式，实现时按行号从小到大的顺序，先存储第0行的全部元素，再存放第1行的元素、第2行的元素,一个23二维数组的逻辑构造如图6-2所示，以行为主的内存映象如图6-3a所示，其分配顺序为：a00，a01，a02，a10 ，a11，a12。,7,8,以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，从右向左，最后是左下标。,2以列为主序column major order,以列为主的存储方式也称为按列优先顺序方式，实现时按列号从小到大的顺序，先存储第0列的全部元素，再存储第1列的元素、第2 列的元素,图6-2所示的逻辑构造，以列为主的内存映象如图6-3b所示，其分配顺序为：a00，a10，a01，a11，a02，a12 。,以列为主分配的规律恰好与以行为主次序相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，从左向右，最后是右下标。,9,2存储地址,“以行为主次序分配存储单元为例看其地址的计算,1二维数组中aij的地址,在C语言中数组中每一维的下界定义为0，数组的基址为LOC(a00)，每个数组元素占据d个字节，那么aij 的物理地址可用一个线性寻址函数计算：,LOC(aij) = LOC(a00) + ( in + j ) d 0下标起始的语言,2三维数组中aijk的地址,同理对于三维数组元素aijk的物理地址为：,LOC(aijk)=LOC(a000)+( (inp+ jp +k) d 0下标起始的语言,10,【例6-1】设二维数组A56，每个元素占4个字节Byte，存储器按字节编址。A的起始地址为2000。计算,1数组的大小,nmd=564=120 Byte,2数组结点a45的存储地址,LOC(aij)=LOC(a00)+(i*n+j)*d / n为总列数,LOC(a45)=2000+(46+5)4=2116,3按行为主存储，计算a32的存储地址,LOC(aij)=LOC(a00)+(i*n+j)*d / n为总列数,LOC(a32)=2000+(36+2)4=2080,4按列为主存储，计算a32的存储地址,LOC(aij)=LOC(a00)+(j*m+i)*d / m为总行数,LOC(a32)=2000+(25+3)4=2052,11,【例6-2】假设矩阵Anm 中存在某个元素aij，满足：aij是第i行中最小值且是第j列中的最大值，那么称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。,根本思想：在矩阵A中求出每一行的最小值元素，然后判断该元素是否是它所在列中的最大值。如果是那么打印输出，接着处理下一行。,设矩阵A用一个二维数组表示，其算法如下：,void saddle(int A,int n,int m), int i,j,min;,for(i=0;in;i+) / 按行处理, min=Ai0,for(j=1;jm;j+),if(Aijmin),min=Aij; / 找第i行最小值,12,for (j=0;jm;j+),/,检测最小值是否是鞍点,if(Aij=min), k=j;,p=0;,while(pn & Apj=n),printf(,%d,%d,%dn,i,k,min);,算法的时间复杂度为,O,(,n,(,m,+,n m,),。,13,6-2,特殊矩阵的压缩存储,矩阵是一个二维数组，是众多科学与工程计算问题中研究的数学对象。在矩阵中非零元素或零元素的分布有一定规律的矩阵称为特殊矩阵，如三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等。当矩阵的阶数很大时，用普通的二维数组存储这些特殊矩阵将会占用很多的存储单元。从节约存储空间的角度考虑，下面来考虑这些特殊矩阵的存储方法。,14,6.2.1 对称矩阵,对称矩阵是一种特殊矩阵，n阶方阵的元素满足性质：aij=aji 0=i , j=n1。,如图6-4所示是一个阶对称矩阵。对称矩阵是关于主对角线的对称，因此只需存储上三角或下三角局部的数据即可。比方，只存储下三角中的元素aij，其特点是中j=i且0=i=n1，对于上三角中的元素aij ，它和对应的aji相等，因此当访问的元素在上三角时，直接去访问和它对应的下三角元素即可，这样，原来需要nn个存储单元，现在只需要n(n+1)/2个存储单元了，节约了n(n1)/2个存储单元。,15,图,6-4 5,阶对称方阵与它的压缩存储,16,如何只存储下三角局部呢？将下三角局部以行序为主序顺序存储到一个向量SA中去。在下三角中共有n(n+1)/2个元素，存储到一个向量空间SA0至SAn(n+1)/2-1中，存储顺序可用图6-5示意。,图,6-5,对称矩阵下三角压缩存储,17,原矩阵下三角中的某一个元素aij具体对应一个sak，用“以行优先存放下三角局部的元素时，a00存入sa0，a10存入sa1，a11存入sa2。sak与aij的一一对应关系为：,k=j(j +1)/2+i 0=k n (n+1)/21,当ij时，在下三角局部aij前有i行，共有1+2+3+i个元素，而aij是第i行的第j个元素，即有k=1+2+3+i+j =i(i+1)/2+j。,当ij时，aij是上三角中的元素，因为aij=aji ，这样，访问上三角中的元素aij时那么去访问和它对应的下三角中的aji即可，因此将上式中的行列下标交换就是上三角中的元素在SA中的对应关系：,k=j(j +1)/2+i 0=krow=m;,H-col=n;,hd0=H;,for(i=1; irow=0; p-col=0;,p-right=p; p-down=p;,hdi=p; hdi-1-v_next.next=p; ,32,hdS-v_next.next=H; / 将头结点们形成循环链表,for(k=1;krow=i; p-col=j; p-v_next.v=v,q=hdi;,while(q-right!=hdi&(q-right-col)right;,p-right=q-right; / 插入,q-right=p; q=hdi;,while(q-down!=hdj&(q-down-row)down;,p-down=q-down; / 插入,q-down=p;,return H;,33,上述算法中，建立头结点循环链表时间复杂度为O(S)，插入每个结点到相应的行表和列表的时间复杂度是O(tS)，这是因为每个结点插入时都要在链表中寻找插入位置，所以总的时间复杂度为O(tS)。该算法对三元组的输入顺序没有要求。如果我们输入三元组时是按以行为主序或列输入的，那么每次将新结点插入到链表的尾部的，改进算法后，时间复杂度为O(S+t)。,34,2稀疏矩阵的加法,两个十字链表存储的稀疏矩阵A和B，计算C=A+B，C也采用十字链表方式存储，并且在A的根底上形成C。,由矩阵的加法规那么知，只有A和B行列对应相等，二者才能相加。C中的非零元素cij只可能有3种情况：或者是aij+bij，或者是aijbij=0，或者是bijaij=0，因此当B加到A上时，对A十字链表的当前结点来说，对应以下四种情况：或者改变结点的值aij+bij0，或者不变bij0，或者插入一个新结点aij0，还可能是删除一个结点aij+bij0。整个运算从矩阵的第一行起逐行进展。对每一行都从行表的头结点出发，分别找到A和B在该行中的第一个非零元素结点后开场比较，然后按4种不同情况分别处理。设pa和pb分别指向A和B的十字链表中行号一样的两个结点，4种情况如下：,35,1假设pa-col=pb-col且pa-v+pb-v0，那么只要用aij+bij的值改写pa所指结点的值域即可。,2假设pa-col=pb-col且pa-v+pb-v=0，那么需要在矩阵A的十字链表中删除pa所指结点，此时需改变该行链表中前趋结点的right域，以与该列链表中前趋结点的down域。,3假设pa-col col且pa-col0即不是表头结点，那么只需要将pa指针向右推进一步，并继续进展比较。4 假设pa-col pb-col或pa-col0即是表头结点，那么需要在矩阵A的十字链表中插入一个pb所指结点。,由前面建立十字链表算法知，总表头结点的行列域存放的是矩阵的行和列，而各行列链表的头结点其行列域值为零，当然各非零元素结点的行列域其值不会为零，下面分析的4种情况利用了这些信息来判断是否为表头结点。,36,MLink AddMat(Ha,Hb),MLink Ha,Hb;, Mnode *p,*q,*pa,*pb,*ca,*cb,*qa;,if(Ha-row!=Hb-row|Ha-col!=Hb-col),return NULL;,ca=Ha-v_next.next; / ca初始指向A矩阵中第一行表头结点,cb=Hb-v_next.next; / cb初始指向B矩阵中第一行表头结点,do pa=ca-right; / pa指向A矩阵当前行中第一个结点,qa=ca; / qa是pa的前驱,pb=cb-right; / pb指向B矩阵当前行中第一个结点,while(pb-col!=0) / 当前行没有处理完, if(pa-colcol & pa-col!=0), qa=pa; pa=pa-right;,else,if(pa-colpb-col|pa-col=0), p=new MNode;,p-row=pb-row;,p-col=pb-col;,p-v=pb-v;,p-right=pa;,qa-right=p; / 新结点插入*pa的前面,pa=p; / 新结点还要插到列链表的适宜位置，先找位置，再插入,q=Find_JH(Ha,p-col); / 从列链表的头结点找起,while(q-down-row!=0&q-down-rowrow),q=q-down;,p-down=q-down; / 插在*q的后面,q-down=p;,pb=pb-right;,else / 第一、二种情况, x=pa-v_next.v+pb-v_next.v;,if(x=0) / 第二种情况, qa-right=pa-right; / 从行链中删除，,/ 要从列链中删除，找*pa的列前驱结点,q=Find_JH(Ha,pa-col); / 从列链表的头结点找起,while(q-down-row row),q=q-down;,q-down=pa-down;,delete pa;,pa=qa;,else / 第一种情况, pa-v_next.v=x; qa=pa; ,pa=pa-right;,pb=pb-right;,ca=ca-v_next.next; / ca指向A中下一行的表头结点,cb=cb-v_next.next; / cb指向B中下一行的表头结点,while(ca-row=0)/ 当还有未处理完的行那么继续,return Ha;,为了保持算法的层次，在上面的算法中用到了一个函数Find_JH()，其功能是：返回十字链表H中第j列链表的头结点指针。,37,3 矩阵的转置,设SPMatrix A; 表示一m*n的稀疏矩阵，其转置B那么是一个n*m的稀疏矩阵，因此也有SPMatrix B; 由稀疏矩阵A求它的转置B只要将A的行、列转化成B的列、行。,将中每一三元组的行列交换后转化到后，似乎已完成了转置，其实不然。A的转置B如下图，图是它对应的三元组存储。也就是说，在A的三元组存储根底上得到B的三元组表存储。,38,转置算法的实质是将矩阵A,的行和列转化成矩阵,B,的列和行。,sparmatrix Trans(sparmatrix A) / 调用稀疏矩阵A, sparmatrix B; / 定义稀疏矩阵B,B.rows=A.cols;,B.cols=A.rows;,B.terms=A.terms;,for (int n=0;ntag=0;,gh-node.data=*s;,gh-link=NULL;,else, gh=new linknode;,gh-tag=1;,p=gh;,s+;,strncpy(subs,s,len-2);,subslen-2=0;,50,do, Disastr(subs,hstr);,r=CreateGL(hstr);,p-node.sublist=r;,q=p;,len=strlen(subs);,if (len0), p=new linknode;,p-tag=1;,q-link=p;,while (len0);,q-link=NULL;,return gh;,创立广义表算法的时间复杂度为O(n)。,51,2广义表取头算法,假设广义表GL=a1，a2，an，那么headGL=a1 。取表头运算的结果可以是原子，也可以是一个子表。,例如，heada1，a2，a3，a4，a5，a6=a1，a2。,Head(linknode *GL),if GL-tag=1,p=GL-hp;,return p;,52,3. 广义表取尾算法,假设广义表GL=a1，a2，an，那么tailGL=a2，an 。取表尾运算的结果是取出除表头以外的所有元素。,例如，taila1，a2，a3，a4，a5，a6=a3，a4，a5，a6。,Tail(linknode *GL),if GL-tag=1,p=GL-tp;,return p;,53,4. 求广义表深度算法,int Depth(linknode *GL), int max=0;,while (GL!=NULL), if (GL-tag=0),/ 有子表, int dep=Depth(GL-sublit),if (depmax),max=dep;,GL=GL-link;,return max+1;,/ 非空表的深度是各元素的深度的最大值加1,求广义表深度算法的时间复杂度为O(n)。,54,1 数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，在数组上不太适宜做插入、删除数据元素的操作。,2二维数组中aij的地址为：,LOC(aij) = LOC(a00) + ( in + j ) d 0下标起始的语言,3三维数组中aijk的地址为：,LOC(aijk)=LOC(a000)+( (inp+ jp +k) d 0下标起始的语言,4对称矩阵是一种特殊矩阵，n阶方阵的元素满足性质：,aij=aji 0i , jn-1。对称矩阵是关于主对角线的对称，因此只需存储上三角或下三角局部的数据即可。,小 结,55,5三角矩阵的特殊性是以主对角线划分矩阵。主对角线任意一侧不包括主对角线中的元素均为常数C。下三角矩阵，主对角线以上均为同一个常数；上三角矩阵，主对角线以下均为同一个常数，均可以采用压缩存储。,6在m*n的矩阵中有t个非零元素，且t远小于m*n，这样的矩阵称稀疏矩阵。稀疏矩阵常用的有：三元组表存储、带行指针的链表存储、十字链表存储等存储方法。,7 广义表是nn0个数据元素的有序序列，广义表的元素可以是单元素，也可以是一个广义表。,8 由于广义表的元素有两种形式，所以其结点的存储形式也有两种：表结点由标志域、表头指针域、表尾指针域组成；而原子结点由标志域和值域组成。,56,1实验目的,1 掌握稀疏矩阵三元组表的存储方法。,2掌握稀疏矩阵三元组表创立、显示、转置和查找等算法。,3掌握广义表的存储方法。,4掌握广义表的新建、显示和查找等算法。,5掌握稀疏矩阵三元组表和广义表的算法分析方法。,2实验内容,1编写稀疏矩阵三元组表的存储程序；,2编写疏矩阵三元组表创立、显示、转置和查找程序；,3编写建立广义表的程序；,4编写广义表的显示和查找程序；,5设计选择式菜单，其一级菜单形式如下：,验证性实验,6,: 稀疏矩阵和广义表子系统系统,57,稀疏矩阵和广义表子系统,*,* 1-稀 疏 矩 阵 *,* 2-广 义 表 *,* 0-退 出 *,*,请输入菜单号0-2:,稀疏矩阵二级菜单形式如下：,稀疏矩阵的三元组存储,*,* 1-新 建 *,* 2-转 置 *,* 3-查 找 *,* 4-显 示 *,* 0-返 回 *,*,请输入菜单号0-4:,58,广义表二级菜单形式如下：,广 义 表,*,* 1-新 建 *,* 2-查 找 *,* 3-显 示 *,* 0-返 回 *,*,请输入菜单号0-3:,59,谢谢欣赏,60,谢谢观赏！,61,2020/11/5,