第十一章高级线性表.ppt
《第十一章高级线性表.ppt》由会员分享,可在线阅读,更多相关《第十一章高级线性表.ppt(108页珍藏版)》请在三一文库上搜索。
1、第十一章 高级线性表,任课教员:张 铭 http:/ 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究,北京大学信息学院 版权所有,转载或翻印必究 Page 2,主要内容,11.1 多维数组 11.2 广义表 11.3 存储管理技术,北京大学信息学院 版权所有,转载或翻印必究 Page 3,11.1 多维数组,数组(Array)是数量和元素类型固定的有序序列 静态数组必须在定义它的时候指定其大小和类型 动态数组可以在程序运行才分配内存空间 多维数组(Multi-array)是向量的扩充 向量的向量就组成了多维数组 可以表示为: ELEM Ac1d1c2d2cndn
2、ci和di是各维下标的下界和上界。所以其元素个数为:,北京大学信息学院 版权所有,转载或翻印必究 Page 4,数组的空间结构,左边是二维数组的空间结构,右边是三维数组的空间结构,d113,d215,d315分别为3个维。,北京大学信息学院 版权所有,转载或翻印必究 Page 5,数组的存储,内存是一维的,所以数组的存储也只能是一维的 以行为主序(也称为“行优先”) 以列为主序(也称为“列优先”) 一个3 3的数组X的行优先表示: 内存中的存放是:1,2,3,4,5,6,7,8,9,北京大学信息学院 版权所有,转载或翻印必究 Page 6,数组的存储(续),一个二维m n数组中元素Xij(第i
3、行第j列元素)的内存地址可以这样来计算: X00(数组首地址)+(ni+j) 元素的长度(如C+中int型为4字节) 例如,我们已知一个数组的A00元素在内存的644的位置,假设元素的长度为8,那么我们就可以求得其他任意元素Axy的位置,为644+len(nx + y)。 例如,n = m = 3,由上面公式得到A23元素的地址:644 + 8(32+2)= 708,北京大学信息学院 版权所有,转载或翻印必究 Page 7,Pascal语言的存储实现是按行优先处理的,先排最右的下标,从右向左,最后最左的下标。 例如对于三维数组a1k,1m,1n的元素axyz可以如下排列:,北京大学信息学院 版
4、权所有,转载或翻印必究 Page 8,Pascal语言的行优先存储,a111 a112 a113 a11n a121 a122 a123 a12n a1m1 a1m2 a1m3 a1mn a211 a212 a213 a21n a221 a222 a223 a22n a2m1 a2m2 a2m3 a2mn ak11 ak12 ak13 ak1n ak21 ak22 ak23 ak2n akm1 akm2 akm3 akmn,北京大学信息学院 版权所有,转载或翻印必究 Page 9,FORTRAN语言采用列优先存储。先排最左的下标,从左向右,最后最右的下标。 例如对于三维数组a1k, 1m, 1
5、n的元素axyz可以如下排列:,北京大学信息学院 版权所有,转载或翻印必究 Page 10,FORTRAN语言的列优先存储,a111 a211 a311 ak11 a121 a221 a321 ak21 a1m1 a2m1 a3m1 akm1 a112 a212 a312 ak12 a122 a222 a322 ak22 a1m2 a2m2 a3m2 akm2 a11n a21n a31n ak1n a12n a22n a32n ak2n a1mn a2mn a3mn akmn,北京大学信息学院 版权所有,转载或翻印必究 Page 11,行优先存储公式,设数组元素占d个存储单元, 3维矩阵行优
6、先存储公式为:,北京大学信息学院 版权所有,转载或翻印必究 Page 12,n维矩阵行优先存储公式为:,北京大学信息学院 版权所有,转载或翻印必究 Page 13,C+多维数组ELEM Ad1 d2dn;,北京大学信息学院 版权所有,转载或翻印必究 Page 14,数组的声明,在编译的时候如果已经知道数组每一维的大小: 声明一个10 10的整型数组:int num1010; 只知道数组一个维的大小,那么也可以动态地创建一个二维数组。例如我们只要一个组有10个整数,但是不知道有多少个组:int (*num)10; 最后在程序运行的时候,可以计算出或者由用户指定它的第一个维数是n: num= ne
7、w intn10;,北京大学信息学院 版权所有,转载或翻印必究 Page 15,数组的声明:动态的声明,int *X; int row=3; int col=3; try /创建行指针,即指向整型的指针 X= new int*row; /然后再为每一行分配地址 for(int i=0; irow;i+) Xi=new intcol; catch(xalloc),北京大学信息学院 版权所有,转载或翻印必究 Page 16,数组的声明:动态的声明,这里要注意的是,内存被分配出去也必须加以回收,否则会造成内存泄漏(memory leak) for(int i=0;irow;i+) delete Xi
8、; delete X; 对于3维或者更高维的数组,过程是类似的,北京大学信息学院 版权所有,转载或翻印必究 Page 17,用数组表示特殊矩阵,二维数组可以被看作是矩阵,所以它也经常被用来表示矩阵 三角矩阵可以被分为上三角矩阵和下三角矩阵,它是指n阶矩阵中的下(上)三角的元素都是0或者一个常数 在上三角矩阵中,当数组的下标ij时,数组元素aij=c; 而在下三角矩阵中,当下标i=j),北京大学信息学院 版权所有,转载或翻印必究 Page 18,下三角矩阵图例,北京大学信息学院 版权所有,转载或翻印必究 Page 19,用数组表示特殊矩阵(续),对称矩阵指的是一个n阶矩阵,它的元素满足性质ai,
9、j=aj,i,0=(i, j)n。在用数组存储的时候,元素aij=aji,北京大学信息学院 版权所有,转载或翻印必究 Page 20,为了节省空间,存储其下三角的值,而对角线之上的值通过对称关系映射过去。 以一维数组sa0n(n+1)/2作为n阶对称矩阵A的存储结构,则sak和矩阵元ai,j之间存在着一一对应的关系 :,北京大学信息学院 版权所有,转载或翻印必究 Page 21,用数组表示特殊矩阵(续),对角矩阵是指所有的非零元素都集中在主对角线及以它为中心的其他对角线上。如果|i-j|1,那么数组元素aij=0。 下面是一个3对角矩阵:,北京大学信息学院 版权所有,转载或翻印必究 Page
10、22,稀疏矩阵,稀疏矩阵中的非零元素非常少,而且分布也不规律 稀疏因子 用来描述稀疏矩阵的非零元素情况,它定义为在m n的矩阵中,有t个非零元素,则稀疏因子为: 通常当这个值小于0.05时,可以认为是稀疏矩阵 一般使用三元组(i, j, aij )来顺序存储稀疏矩阵,其中i是该元素的行号,j是该元素的列号,aij是该元素的值,北京大学信息学院 版权所有,转载或翻印必究 Page 23,稀疏矩阵的十字链表,十字链表有两组链表组成 行和列的指针序列 链表中的每一个结点都包含两个指针,一个指向它的同一行的下一个元素,一个指向它的同一列的下一个元素,北京大学信息学院 版权所有,转载或翻印必究 Page
11、 24,十字链表的ADT,template class OLNode private: int row,col;/矩阵的行和列 T element;/矩阵中存储的数据 OLNode* right,*down;/指向下一个结点的指针 public: OLNode()right=NULL;down=NULL; ;,北京大学信息学院 版权所有,转载或翻印必究 Page 25,十字链表的建立,建立矩阵的算法如下: 首先为行头结点和列头结点申请空间,大小分别为矩阵的行列数 将三元组根据情况分别加入到链表中 如果三元组中的行列号错误,则退出,否则继续 先处理行链表的问题 如果该行头结点为空,则建立一个新的
12、头结点,内容为该三元组 如果不为空则从头结点开始查找,找到该三元祖的正确位置如果该位置已经存在数据,则修改之,否则生成相应的结点插入进去 类似地处理列链表头,北京大学信息学院 版权所有,转载或翻印必究 Page 26,矩阵乘法,=,北京大学信息学院 版权所有,转载或翻印必究 Page 27,经典矩阵乘法,Ac1d1 c3d3,Bc3d3 c2d2, Cc1d1c2d2。 d3 CAB (CijAik Bkj) k=c3 for (i=c1; i=d1; i+) for (j=c2; j=d2; j+) sum = 0; for (k=c3; k=d3; k+) sum = sum + Ai,k
13、*Bk,j; Ci,j = sum; ,北京大学信息学院 版权所有,转载或翻印必究 Page 28,p=d1-c1+1,m=d3-c3+1,n=d2-c2+1; A为pm的矩阵,B为mn的矩阵,乘得的结果C为pn的矩阵 经典矩阵乘法所需要的时间代价为O(pmn),北京大学信息学院 版权所有,转载或翻印必究 Page 29,稀疏矩阵乘法,template SMatrix*SMatrix:MatrixMutil(SMatrix*left,SMatrix*right) if(left-GetColnum()!=right-GetRownum() return NULL;/行列不匹配不能相乘 int
14、I=0; /第一个矩阵的行数 int J=0; /第二个矩阵的列数 SMatrix *ResultMatrix=new SMatrix();/结果矩阵 ResultMatrix-MallocMem(left-GetRownum(),right-GetColnum();/为结果矩阵分配空间 for(I=1;IGetRownum();I+) /开始相乘 OLNode* RowNext=ResultMatrix-rowheadI;,北京大学信息学院 版权所有,转载或翻印必究 Page 30,for(J=1;JGetColnum();J+) /扫描所有的列 OLNode* ColNext=Result
15、Matrix-colheadJ; int result=0; OLNode * rows=left-rowheadI; OLNode* cols=right-colheadJ; if(rows=NULL)|(cols=NULL) break;/新行没有非零元素 while(rows!=NULL) ,北京大学信息学院 版权所有,转载或翻印必究 Page 31,else /都有元素可以相乘 result=result+cols-element*rows-element; cols=cols-down; rows=rows-right; if(result=0) continue; /插入到结果矩阵
16、中 OLNode* temp=new OLNode(); temp-row=I; temp-col=J; temp-element=result; if(RowNext=NULL)/加入行向量中 /每行第一个元素 ResultMatrix-rowheadI=temp; RowNext=ResultMatrix-rowheadI; else /加入一个新的元素到下一个位置 RowNext-right=temp; RowNext=RowNext-right; ,北京大学信息学院 版权所有,转载或翻印必究 Page 32,if(ColNext=NULL)/加入到列向量 /列结点第一次使用,加入新的结
17、点 ResultMatrix-colheadJ=temp; ColNext=ResultMatrix-colheadJ; else /调转到合适的位置,插入 while(ColNext-down!=NULL) ColNext=ColNext-down; ColNext-down=temp; ColNext=ColNext-down; /完成放入ResultMatrix /乘法做完,返回新的矩阵 return ResultMatrix; ,北京大学信息学院 版权所有,转载或翻印必究 Page 33,稀疏矩阵乘法时间代价,若矩阵A中行向量的非零元素个数最多为ta 矩阵B中列向量的非零元素个数最多为
18、tb 矩阵C中列向量的非零元素个数最多为tc 假设C矩阵中非0元素的个数总和为Nc,北京大学信息学院 版权所有,转载或翻印必究 Page 34,每计算一个 cij的时间 主要用于顺着行I和列J寻找的过程 其循环次数最多为ta+tb 每次循环所花时间是一个常量,记为k 计算一个cij的时间为k(ta+tb) 计算全部cij的时向为k(ta+tb)pn。,北京大学信息学院 版权所有,转载或翻印必究 Page 35,生成乘积矩阵的时间 计算出来的结果在行向量里面插入的时间是常数 在列向量上插入需要每次定位到合适的位置, 所花时间为O(tc),插入操作的总时间为O(Nc tc ) 因此稀疏矩阵乘法的总
19、执行时间上界为 O(ta+tb)pn)+ O(Nc tc ) 如果修改此算法 保留乘积C矩阵的当前列指针向量位置,指向已插入到C中各列最新的非零元素 可使每次插入的时间为一常数 总执行时间降低为O(ta+tb)pn),北京大学信息学院 版权所有,转载或翻印必究 Page 36,11.2 广义表,回顾线性表 由n(n0)个数据元素组成的有限有序序列 线性表的每个元素都具有相同的数据类型,通常为同一某种类型的数据记录 如果一个线性表中还包括一个或者多个子表,那就称之为广义表(Generalized Lists,也称Multi-list)一般记作: L(x0,x1,xi,xn-1),北京大学信息学院
20、 版权所有,转载或翻印必究 Page 37,L(x0,x1,xi,xn-1) L是广义表的名称 n为长度 每个xi(0in-1)是L的成员 可以是单个元素,即原子(也称“单元素”,atom ) 也可以是一个广义表,即子表(sublist) 广义表的深度:表中元素都化解为原子后的括号层数,北京大学信息学院 版权所有,转载或翻印必究 Page 38,广义表的各种类型,纯表(pure list) 从根结点到任何叶结点只有一条路径 也就是说任何一个元素(原子、子表)只能在广义表中出现一次,北京大学信息学院 版权所有,转载或翻印必究 Page 39,广义表的各种类型(续),可重入表( reentrant
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十一 高级 线性
链接地址:https://www.31doc.com/p-2584321.html