据结构》Word格式文档下载.docx
《据结构》Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《据结构》Word格式文档下载.docx（12页珍藏版）》请在冰点文库上搜索。
即只对被转置矩阵的三元组表A扫描一次，就使A中所有非零元的三元组“一次定位”直接放到三元组表B的位置上。
为了能将被转至三元组表A中的元素一次定位到三元组表B的正确位置上，需要预先计算以下数据：
待转职矩阵三元组表A每一列中非零元素的总个数（即转置后矩阵三元组B的每一行中非零元素的总个数）
待转置矩阵每一列中每一个非零元素在三元组表B中的正确位置（即转置后矩阵每一行中第一个非零元素在三元组B中正确位置。
二、1）问题求解思路（算法思想）
首先需创建一个稀疏矩阵，然后按照上面所提思路，在稀疏矩阵转置算法中加设两个数组，分别为num[]和position[]，其中num[col]用来存放三元组表Av中第col列中非零元素总个数（三元组表B中第col行中非零元素的总个数），position[]用来存放转置前三元组表A中第col列（转置后B中第col行）黄总第一个非零元素在三元组表B中的存储位置。
进而写出稀疏矩阵快速转职的算法。
2）主要函数：
CreatSMatrix（Tabletype*）;
/*生成矩阵*/
voidDestroySMatrix（Tabletype*）;
/*销毁矩阵*/
voidout_matrix（Tabletype*）;
/*打印矩阵*/
intFastTransposeSMatrix（Tabletype*,Tabletype*）;
/*快速转置算法*/
三、测试及结果
1、测试情况
输入126237318这样一组数据，测试其结果
2、测试结果
三、源程序
/*矩阵的快速转置*/
#include<
stdio.h>
stdlib.h>
process.h>
#defineMAXSIZE200/*矩阵中最大非零元的个数*/
typedefstructtriple
{
inti;
/*行标,本程序中从1开始的*/
intj;
/*列标，本程序中从1开始的*/
inte;
/*非零元*/
}Triple;
/*三元组定义*/
typedefstructtabletype
intmu;
/*矩阵的行数*/
intnu;
/*列数*/
inttu;
/*非零元个数*/
Tripledata[MAXSIZE];
/*非零元的三元组表,本程序中是从data[1]开始使用的*/
}Tabletype;
/*三元组线性表*/
/*以下为函数声明，注意和书本上的参数类型不同，我用的形参全为指针*/
voidCreatSMatrix（Tabletype*）;
intmain（void）/*主函数*/
charch;
Tabletypea={0,0,0,{0,0,0}};
/*初始化为0，便于输入数据时的无效检测*/
Tabletypeb;
/*声明矩阵b*/
while
（1）
printf（"
@@@@@@@@@@@@@@本程序的功能是实现稀疏矩阵的快速转置@@@@@@@@@@@@@@@\n"
）;
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n"
CreatSMatrix（&
a）;
ThesourceMatrix:
\n"
out_matrix（&
if（FastTransposeSMatrix（&
a,&
b））/*若a不为零矩阵则转置a，存入b中*/
{printf（"
AfterTransposeSMatrix:
\n"
b）;
}
else
{
Thematrixiszeros:
/*以下为程序控制*/
Input'
q'
toquitand'
c'
runagain:
"
do{
if（（ch=getchar（））=='
||ch=='
Q'
）
DestroySMatrix（&
exit（0）;
}while（（ch!
='
C'
）&
&
（ch!
））;
system（"
cls"
}
return1;
voidCreatSMatrix（Tabletype*a）//创建矩阵
printf（"
请输入矩阵的行数、列数和非零元个数，用空格间隔:
scanf（"
%d%d%d"
&
（a->
mu）,&
nu）,&
tu））;
for（i=1;
i<
=a->
tu;
请输入矩阵中第%d个非零元（按行标、列标、值的顺序，空格间隔）:
i）;
scanf（"
data[i].i）,&
data[i].j）,&
data[i].e））;
if（a->
data[i].i<
1||a->
data[i].i>
a->
mu||a->
data[i].j<
data[i].j>
nu）/*下标越界*/
注意：
下标越界输入数据无效!
\n请重新输入:
行标范围：
1--%d,列标范围1--%d!
!
a->
mu,a->
nu）;
continue;
}
if（（（a->
data[i].i）<
（a->
data[i-1].i））||
（（（a->
data[i].i）==（a->
data[i-1].i））&
（（a->
data[i].j）<
=（a->
data[i-1].j））））/*非按行顺序输入*/
{
输入数据无效!
\n请按照按行存储的顺序输入数据!
i++;
voidDestroySMatrix（Tabletype*a）//销毁矩阵
{/*销毁稀疏矩阵a*/
（*a）.mu=0;
（*a）.nu=0;
（*a）.tu=0;
voidout_matrix（Tabletype*a）/*打印矩阵*/
inti,j,k=1;
for（i=1;
i<
mu;
i++）
for（j=1;
j<
nu;
j++）
{/*判断是否为非零元*/
if（（a->
data[k].i==i）&
data[k].j==j））
%4d"
data[k].e）;
k++;
0）;
intFastTransposeSMatrix（Tabletype*a,Tabletype*b）//稀疏矩阵的快速转置
intp,q,col;
int*num;
int*cpot;
b->
mu=a->
/*原矩阵的行数为新矩阵的列数，原列数为新行数，非零元个数不变*/
nu=a->
tu=a->
num=（int*）malloc（（b->
nu+1）*sizeof（int））;
/*生成两个辅助数组*/
cpot=（int*）malloc（（b->
if（b->
tu）/*若a不为零矩阵*/
for（col=0;
col<
a->
col++）/*初始化矩阵a的每列中非零元的个数均为0*/
num[col]=0;
col<
=a->
tu;
col++）/*统计每列中非零元的个数*/
num[a->
data[col].j]++;
cpot[1]=1;
/*确定每列中第一个非零元的位置*/
for（col=2;
col++）
cpot[col]=num[col-1]+cpot[col-1];
for（p=1;
p<
p++）/*p为a-data的下标*/
col=a->
data[p].j;
/*交换元素*/
q=cpot[col];
data[q].i=a->
data[q].j=a->
data[p].i;
data[q].e=a->
data[p].e;
q++;
cpot[col]++;
free（num）;
/*释放两个辅助数组*/
free（cpot）;
/*转置成功*/
else/*a为零矩阵*/
return0;
}
二、测试及结果
三、总结
通过本次实验我对数组存储有了更进一步的了解，并且通过实验又想到了快速转置的改进方法，思想是按照以下步骤计算position[col]的值：
一、初始化各position[col]的值为1，即出事家丁A中各类第一个非零元素均从B的第一个下表位置开始存放
二、循环扫描一遍矩阵A的三元组表，没遇到一个列号为col的元素，就将对应的从position[col]开始的其余元素值增1，
三、对矩阵A的三元组表到买哦一遍完成转置，当A中第col列有一个元素加入三元组表B时，则对应position[col]的值加1，是position[col]始终指向三元组表A第col列中下一个非零元素在三元组表B中的正确位置。
另外，通过编程，使我掌握稀疏矩阵的特点，存储方法和基本原理，认识到算法不再会就可以，还得会灵活运用，从而培养了我运用C语言正确编程及调试的能力，运用数据结构解决简单的实际问题的能力，为后继计算机专业课程的学习打下基础。
通过这次的实验，我学习了很多知识，也认识到了自己的不足，那就是缺乏相应的知识和经验，调试程序能力还有所欠缺，所以在运用和操作方面体现了不足。
所以在今后的学习中我会努力取得更大的进步。
出师表
两汉：
诸葛亮
先帝创业未半而中道崩殂，今天下三分，益州疲弊，此诚危急存亡之秋也。
然侍卫之臣不懈于内，忠志之士忘身于外者，盖追先帝之殊遇，欲报之于陛下也。
诚宜开张圣听，以光先帝遗德，恢弘志士之气，不宜妄自菲薄，引喻失义，以塞忠谏之路也。
宫中府中，俱为一体；
陟罚臧否，不宜异同。
若有作奸犯科及为忠善者，宜付有司论其刑赏，以昭陛下平明之理；
不宜偏私，使内外异法也。
侍中、侍郎郭攸之、费祎、董允等，此皆良实，志虑忠纯，是以先帝简拔以遗陛下：
愚以为宫中之事，事无大小，悉以咨之，然后施行，必能裨补阙漏，有所广益。
将军向宠，性行淑均，晓畅军事，试用于昔日，先帝称之曰“能”，是以众议举宠为督：
愚以为营中之事，悉以咨之，必能使行阵和睦，优劣得所。
亲贤臣，远小人，此先汉所以兴隆也；
亲小人，远贤臣，此后汉所以倾颓也。
先帝在时，每与臣论此事，未尝不叹息痛恨于桓、灵也。
侍中、尚书、长史、参军，此悉贞良死节之臣，愿陛下亲之、信之，则汉室之隆，可计日而待也
。
臣本布衣，躬耕于南阳，苟全性命于乱世，不求闻达于诸侯。
先帝不以臣卑鄙，猥自枉屈，三顾臣于草庐之中，咨臣以当世之事，由是感激，遂许先帝以驱驰。
后值倾覆，受任于败军之际，奉命于危难之间，尔来二十有一年矣。
先帝知臣谨慎，故临崩寄臣以大事也。
受命以来，夙夜忧叹，恐托付不效，以伤先帝之明；
故五月渡泸，深入不毛。
今南方已定，兵甲已足，当奖率三军，北定中原，庶竭驽钝，攘除奸凶，兴复汉室，还于旧都。
此臣所以报先帝而忠陛下之职分也。
至于斟酌损益，进尽忠言，则攸之、祎、允之任也。
愿陛下托臣以讨贼兴复之效，不效，则治臣之罪，以告先帝之灵。
若无兴德之言，则责攸之、祎、允等之慢，以彰其咎；
陛下亦宜自谋，以咨诹善道，察纳雅言，深追先帝遗诏。
臣不胜受恩感激。
今当远离，临表涕零，不知所言。
升级会员 