1991人阅读
〖10级大二课堂习题〗数据结构（12）
&&源代码：// 4_a1.cpp -- 下三角矩阵的压缩存储定义
* -& 题目要求：
* 1.已知矩阵A[5][5]是一个下三角矩阵，如下图
* 2.要求编写算法把矩阵A采用压缩存储，存储到一维数组B[16]中;
* 3.能依次输出B中各元素的值以验证该算法功能已实现。
* 4.此题的源程序保存为4_a1.cpp。
* -& 题目及相关知识点分析：
* 1. 所用知识：本次题目，要求用到的知识有数组的定义和压缩存储的方法。
* 2. 数组的定义：对于数组定义，实际上最原始的是将[n][n]的数组展开为一个n*n的一维数组。
* 3. 数组的定义：如果想用更符合思路的定义，减少计算量，还可以使用嵌套存放数据的方式来定义二维数组，
不过估计这样的效率不会很高，所以在各教材上才没有说。
* 4. 压缩存储的思路：
01.目的：实质上，题目就是要将a[5][5]每一个元素在b[16]中找到一个个相对应的元素；调用a[][]，存放b[].
02.需求：需要知道a[i][j]跟b[n]之间的逻辑关系；
03.为什么题目给出16 ？
在a中，现在可以知道的是 0 & i &= 5, 0 & j &= 5;
04. 下三角矩阵中，右上角的元素全为零，可以放在同一个地址中，这就是所谓的压缩了。
05. 这样一来，5*5=25, 5*5/2+5/2+1=15个有元素的地址，再另加上一个存放0的地址，刚刚好，15+1=16。
06. 我想，这就是为什么题目要求将a[5][5]存放在b[16]中的原因了。
07. 注意，刚刚 5*5/2+5/2+1=15的原因是：
08. 先计算5*5一共有多少个元素，再除以2,取得半个矩阵的个数，然后再加上5/2，获得左上角与右上角的连线的元素个数的一半，
此时，在n为偶数的矩阵中，刚刚好可以计算出有元素的地址是多少。
假如，n为奇数的矩阵，因为刚刚用了两次除以2的取整除法，都会有一个余数，最后一步+1实际上就是将两次余数0.5+0.5相加。
09.矩阵中零元素的存放特性：可以看出，当i&j时，a[i][j]存放的就是零元素了，也就是说，这是判断存放时if-else里面的条件之一。
10.矩阵中下三角元素的存放特性：
11.b[k]-a[i][j], 0-[1][1], 1-[2][1], 2-[2][2], 3-[3][1], 4-[3][2], 5-[3][3], 6-[4][1], 7-[4][2], 8-[4][3], 9-[4][4]
可以看出，在每一行中，当j从0递增到i时，即停止，进入i递增，实际上，我们要算出的就是从上面数下来，数了多少个数。
先观察k与i的规律，可以看出，k = k-1+i，仔细列出表可以看出0+1+2+3+4+...i = k，即该式为一次方求和公式，i(i-1)/2,0&i&n
以前数学没学好，费了N大的功夫，终于把一次方求和的公式推出来了，最后，只差一步，j，整个完整的公式就是i(i-1)/2+j-1
晕：做数据结构的题目简直就是在做数学题目啊~
附：一次方求和公式推导过程：1+2+3+...n = s, s = n(n-1)/2，图表
数值：1 2 3 4 5 6，下面将数值以列的方式1+1+1＝数值的方式排列出来
1 1 1 1 1 1
0 1 1 1 1 1
0 0 1 1 1 1
0 0 0 1 1 1
0 0 0 0 1 1
0 0 0 0 0 1
假如将1加到6就是将第1列的1移到第5列中，第2列中的1移到第4列中，这样刚刚可以看出，在这个一矩阵中，6*6，
而满1的位置刚刚占了整个矩阵的一半，跟刚刚所说的原理一样，6*6/2+(对角线)6/2=6*(6+1)/2, 即n(n+1)/2
由于这时需要用到的情况是下标从零开始的，所以，n = n - 1, 式子就变为 (n-1)n/2，于是i(i-1)/2就出来啦。
12.这样一来，总结一下下三角矩阵算法中b[k]与a[i][j]之间的关系：
i &= j 时，k = i(i-1)/2 +j-1
时，k = n-1最后一位存放0
#include &iostream&
using std::
using std::
using std::
class TwiArr
// 存放顺序表的数组
// 记录矩阵行列长度
// 记录顺序表总长度
enum a{defaultsize = 5};// 默认矩阵行列长度
// 记录现在的位置
// 构造、析构
void init(int ms)
int judgejo(ms % 2); // 用于判断奇偶
if (judgejo == 0)
maxsize = ms * ms / 2 + ms / 2;
maxsize = ms * ms / 2 + ms / 2 + 2;
ta = new double[maxsize]; // 将数组中的数将被初始化为零
for (int i = 0; i != ++i)
ta[i] = 0;
leftsize = 0;
void removeall()
leftsize = 0;
maxsize = 0;
// 构造，析构
TwiArr(int ms = defaultsize){init(ms);}
~TwiArr(){removeall();}
// 修改距阵中的值
void changeelem(const double &, int vi, int vj);
// 显示距阵
void display();
* 函数名称：TwiArr::display
* 函数功能：将两种形式显示TwiArr.ta里面的值。
* 函数参数：无。
void TwiArr::display()
cout && &-& 以下数组以b[k]的顺序显示：& &&
for (int i = 0; i != ++i)
if (i != maxsize - 1)
cout && & | &;
cout && &-& 以下数组以a[i][j]的顺序显示：& &&
for (int i = 1; i &= ++i)
for (int j = 1; j &= ++j)
if ( i & j)
cout && ta[(maxsize - 1)] ;
cout && ta[(i*(i-1)/2 + j-1)];
* 函数名称：TwiArr::changeelem
* 函数功能：将单个元素的值赋入TwiArr中的数据成员*ta里面存储。
* 函数参数：该函数有三个形参，第一个为double形用于修改二维数组里面值的参数
第二个与第三个为用于用户调用的二维数组的行与列。
void TwiArr::changeelem(const double & value,int vi, int vj)
if ( vi & vj)
// 因为这个为下三角矩阵，所以当vi&vj时，直接返回，如果程序再完善，这里还应出现错误信息。
ta[(vi*(vi-1)/2 + vj-1)] =
// --------------------------------------------------------- main start -----------------------------------------------
int main()
cout && &----------------------- 现在开始二维数组的顺序表测试 ---------------------------\n&;
cout && & -& 刚开始测试时，未赋值的数组:\n\n&;
test.display();
cout && endl && & -& 现开始赋值后的测试:\n\n&;
void giveValue(TwiArr &);
giveValue(test);
test.display();
system(&pause&);
void giveValue(TwiArr & test)
/* 给二维数组初始化下面的值
test.changeelem(1, 1, 1);
test.changeelem(4, 2, 1);
test.changeelem(7, 2, 2);
test.changeelem(6, 3, 1);
test.changeelem(9, 3, 2);
test.changeelem(5, 3, 3);
test.changeelem(1, 4, 1);
test.changeelem(8, 4, 2);
test.changeelem(4, 4, 3);
test.changeelem(1, 4, 4);
test.changeelem(2, 5, 1);
test.changeelem(3, 5, 2);
test.changeelem(0, 5, 3);
test.changeelem(9, 5, 4);
test.changeelem(6, 5, 5);
运行结果：
----------------------- 现在开始二维数组的顺序表测试 ---------------------------
-& 刚开始测试时，未赋值的数组:
-& 以下数组以b[k]的顺序显示：
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
-& 以下数组以a[i][j]的顺序显示：
-& 现开始赋值后的测试:
-& 以下数组以b[k]的顺序显示：
1 | 4 | 7 | 6 | 9 | 5 | 1 | 8 | 4 | 1 | 2 | 3 | 0 | 9 | 6 | 0
-& 以下数组以a[i][j]的顺序显示：
请按任意键继续. . .
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：561901次
积分：6853
积分：6853
排名：第2936名
原创：175篇
转载：21篇
评论：428条
一. 建博原因：
1. 记录大学期间学习历程
2. 方便整理归纳回顾知识
3. 受自身历程及众人的监督
4. 认识志同道合的朋友
5. 一起学习交流成长
&&&&&&&&生活上，学习上的点点滴滴总是那么的神奇，过去未知答案时所走出的道路，在未来的这天，发觉还真的能将它的点点滴滴串连起来，现在所走之路，未知是何路，但必是通向未来之路~
&&&&&&& 因为不满足于现状，觉得可以做得更好，所以，常常不断地在寻找着出路，不愿做一只井底之蛙，通过不断努力去改变现状，学习如此，生活亦是如此。不知是何时起，有这么一股想法，这么一股劲，不断寻求，相信总有一天苗子会长大成参天大树。
&&&&&&& 假如抛开了一切外在负担，你最在乎的是什么？或者说，你最想做的事情是什么？ 燃起你的激情，为之奋斗~& 梦&想，梦非仅是梦，想非仅空想，梦想并非遥不可及~& 用这燃烧不尽的激情，追随着它，Achieve it ~ 不要让自己迷失方向，不要让一切邪恶的东西将其覆盖，将其浇灭。
&&&&&&&&不要冷漠了任何一件事物，它们总是会有这么神奇的一个地方，不断地挖掘挖掘，你会懂得更多，获得更多~好奇心是充满魔力的东西~
(2)(1)(1)(4)(1)(2)(4)(1)(2)(1)(2)(8)(17)(14)(8)(10)(6)(24)(20)(17)(18)(33)君，已阅读到文档的结尾了呢~~
三角矩阵的存储映射
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
三角矩阵的存储映射
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口>> 上三角矩阵压缩存储类，用c++描写的，数据结构中的
上三角矩阵压缩存储类，用c++描写的，数据结构中的
所属分类：
下载地址：
Uppertriangularmatri文件大小：6.91 kB
分享有礼！ 》
请点击右侧的分享按钮，把本代码分享到各社交媒体。
通过您的分享链接访问Codeforge，每来2个新的IP，您将获得0.1 积分的奖励。
通过您的分享链接，每成功注册一个用户，该用户在Codeforge上所获得的每1个积分，您都将获得0.2 积分的分成奖励。
上三角矩阵压缩存储类，用c++描写的，数据结构中的-Upper triangular matrix stored compression type, using c++ description, data structure
Sponsored links
源码文件列表
温馨提示： 点击源码文件名可预览文件内容哦 ^_^
533.00 B05-11-08 08:26
0.00 B05-11-08 08:58
2.50 kB05-11-08 09:28
上三角矩阵压缩存储类.dsp4.45 kB05-11-08 09:28
上三角矩阵压缩存储类.dsw565.00 B05-11-08 08:58
上三角矩阵压缩存储类.ncb33.00 kB05-11-08 09:28
上三角矩阵压缩存储类.opt47.50 kB05-11-08 09:28
&Debug&0.00 B06-12-08 18:48
&上三角矩阵压缩存储类&0.00 B06-12-08 18:48
（提交有效评论获得积分）
评论内容不能少于15个字，不要超出160个字。
评价成功，多谢！
下载Uppertriangularmatri
CodeForge积分（原CF币）全新升级，功能更强大，使用更便捷，不仅可以用来下载海量源代码马上还可兑换精美小礼品了
您的积分不足，优惠套餐快速获取 30 积分
10积分 / ￥100
30积分 / ￥200原价 ￥300 元
100积分 / ￥500原价 ￥1000 元
订单支付完成后，积分将自动加入到您的账号。以下是优惠期的人民币价格，优惠期过后将恢复美元价格。
支付宝支付宝付款
微信钱包微信付款
更多付款方式：、
您本次下载所消耗的积分将转交上传作者。
同一源码，30天内重复下载，只扣除一次积分。
鲁ICP备号-3 runtime:Elapsed:173.892ms - init:0.2;find:3.0;t:2.0;tags:0.3;related:123.6;comment:0.1; 27.69
登录 CodeForge
还没有CodeForge账号？
Switch to the English version?
^_^"呃 ...
Sorry!这位大神很神秘，未开通博客呢，请浏览一下其他的吧