数据结构第4章数组

会计学1数据结构第4章数组2顺序存储方式：按低地址优先（或高地址优先）顺序存入一维数组。（难点是：多维数组与一维数组的地址映射关系）例1：已知二维数组Am,m按行存储的元素地址 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 是：Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K,请问按列存储的公式相同吗答：尽管是方阵，但公式仍不同，要作修改：Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K例2：设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为。根据列优先公式Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K得：LOC(a32,58)=2048+[(58-1)*60+(32-1)]*2＝8950答：请注意审题！想一想：若数组是a[0…59,0…69]，结果是否仍为8950？89504.2数组的顺序 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示和实现第1页/共14页34.3矩阵的压缩存储讨论：1.什么是压缩存储？若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。2.所有二维数组（矩阵）都能压缩吗？未必，要看矩阵是否具备以上压缩条件。3.什么样的矩阵具备以上压缩条件？一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。4.什么叫稀疏矩阵？矩阵中非零元素的个数较少（一般小于5%）重点介绍稀疏矩阵的压缩和相应的操作。第2页/共14页44.4稀疏矩阵的压缩存储问题：如果只存储稀疏矩阵中的非零元素，那这些元素的位置信息该如何表示？解决思路：对每个非零元素增开若干存储单元，用来存放其所在的行号和列号，便可准确反映该元素所在位置。实现方法：将每个非零元素用一个三元组（i，j，aij）来表示，则每个稀疏矩阵可用一个三元组表来表示。二、稀疏矩阵的操作第3页/共14页5例1：三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的、和。行下标列下标元素值例2：写出右图所示稀疏矩阵的压缩存储形式。0129000000000-3000140002400001800001500-700(1,2,12)，(1,3,9)，(3,1,-3)，(3,5,14)，(4,3,24)，(5,2,18)，(6,1,15)，(6,4,-7)解：至少有4种存储形式。法1：用线性表表示：0129000000000-3000140002400001800001500-700()第4页/共14页6法2：用三元组矩阵表示：0129000000000-3000140002400001800001500-700121213931-3351443245218611564-7注意：为更可靠描述，通常再加一行“总体”信息：即总行数、总列数、非零元素总个数668ijvalue稀疏矩阵压缩存储的缺点：012345678将失去随机存取功能！第5页/共14页7法三：用带辅助向量的三元组表示。方法：增加2个辅助向量：①记录每行非0元素个数，用NUM（i）表示；②记录稀疏矩阵中每行第一个非0元素在三元组中的行号，用POS（i）表示。76531211202NUM(i)6543POS(i)21i0129000000000-3000140002400001800001500-700-7461516182524341453-3139311221866vji0123456783用途：便于高效访问稀疏矩阵中任一非零元素。POS(i)如何计算？POS(1)＝1POS(i)＝POS(i-1)+NUM(i-1)第6页/共14页8法四：用十字链表表示用途：方便稀疏矩阵的加减运算方法：每个非0元素占用5个域rightdownvji同一列中下一非零元素的指针同一行中下一非零元素的指针十字链表的特点：①每行非零元素链接成带表头结点的循环链表；②每列非零元素也链接成带表头结点的循环链表。则每个非零元素既是行循环链表中的一个结点；又是列循环链表中的一个结点，即呈十字链状。122100H19311825第7页/共14页9typedefstruct{Tripledata[MAXSIZE+1];//三元组表，以行为主序存入一维向量data[]中intmu;//矩阵总行数intnu;//矩阵总列数inttu;//矩阵中非零元素总个数}TsMatrix;三元组表的顺序存储表示（见教材）对三元组表data[]的整体定义#defineMAXSIZE125000//设非零元素最大个数125000typedefstruct{inti;//元素行号intj;//元素列号ElemTypee;//元素值}Triple;对表中每个结点的结构定义第8页/共14页10二、稀疏矩阵的操作0129000000000-3000140002400001800001500-70000–3001512000180900240000000-70014000000000(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)(1,3,-3)(1,6,15)(2,1,12)(2,5,18)(3,1,9)(3,4,24)(4,6,-7)(5,3,14)三元组表a.data三元组表b.data转置后MT（以转置运算为例）目的：第9页/共14页11答：肯定不正确！除了：（1）每个元素的行下标和列下标互换（即三元组中的i和j互换）；还需要：（2）T的总行数mu和总列数nu也要互换；（3）重排三元组内各元素顺序，使转置后的三元组也按行（或列）为主序有规律的排列。上述（1）和（2）容易实现，难点在（3）。若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法正确吗？有两种实现转置的方法压缩转置快速(压缩)转置提问：第10页/共14页12方法1：压缩转置思路：反复扫描a表（记为a.data）中的列序，从j=1～n依次进行转置。三元组表a.data三元组表b.data①(1,3,-3)②(1,6,15)③(2,1,12)④(2,5,18)⑤(3,1,9)⑥(3,4,24)⑦(4,6,-7)⑧(5,3,14)(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)1122colq1234讨论：每个元素的列分量怎样书写？a.data[p].jp1234......第11页/共14页13StatusTransPoseSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;for(col=1;col<=M.nu;col++){for(p=1;p<=M.tu;p++){if(M.data[p].j==col){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].value=M.data[p].value;q++;}}}}returnOK;}//TranposeSMatrix;压缩转置算法描述：（见教材）//用三元组表存放稀疏矩阵M，求M的转置矩阵T//q是转置矩阵T的结点编号//col是扫描M三元表列序的变量//p是M三元表中结点编号这里的M和T其实都是三元组表形式！第12页/共14页14三元组表a.data三元组表b.data①(1,3,-3)②(1,6,15)③(2,1,12)④(2,5,18)⑤(3,1,9)⑥(3,4,24)⑦(4,6,-7)⑧(5,3,14)(6,4,-7)(6,1,15)(5,2,18)(4,3,24)(3,5,14)(3,1,-3)(1,3,9)(1,2,12)1122colq1234p1234......1、主要时间消耗在查找M.data[p].j=col的元素，由两重循环完成:for(col=1;col<=M.nu;col++)循环次数＝列长度nu{for(p=1;p<=M.tu;p++)循环次数＝非零元素个数tu压缩转置算法的效率 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ：所以该算法的时间复杂度为O(nu*tu)----即M的列数与M中非零元素的个数之积最恶劣情况：M中全是非零元素，此时非零元素总数tu=mu*nu，时间复杂度为O(nu2*mu)注：若M中基本上是非零元素时，即使用传统转置算法的时间复杂度也不过是O(nu*mu)（程序见教材）结论：压缩转置算法不能滥用。前提：仅适用于非零元素个数很少（即tu<<mu*nu）的情况。第13页/共14页