1.已知一个稀疏矩阵如下图所示:
0 4 0 0 0 0 0
0 0 0 -3 0 0 1
8 0 0 0 0 0 0
0 0 0 5 0 0 0
0 -7 0 0 0 2 0
0 0 0 6 0 0 0
图3-1 具有6行×7列的一个稀疏矩阵
⑴写出它的三元组线性表；
解：((1,2,4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,,2,-7),(5,6,2),(6,4,6))
⑵给出它的顺序存储表示；
解：
下标 1 2 3 4 5 6 7 8 ... MaxTerms row(行号) 1 2 2 3 4 5 5 6 col(列号) 2 4 7 1 4 2 6 4 val(元素值) 4 -3 1 8 5 -7 2 6
⑶给出它的转置矩阵的三元组线性表和顺序存储表示；
解：((1,3,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5),(4,6,6),(6,5,2),(7,2,1))
⑷给出对它进行快速转置时,num向量中各分量的值；
⑸给出对它进行快速转置前和转置后,pot向量中各分量的值。
解：
Col 1 2 3 4 5 6 7 Num[col] 1 2 0 3 0 1 1 pot[col](前) 1 2 4 4 7 7 8 pot[col](后) 2 4 4 7 7 8 9
2.采用顺序存储方式实现稀疏矩阵M1和M2相加的运算，运算结果由变量M返回。
解：
void Add(SMatrix& M1,SMatrix& M2,SMatrix& M)
//采用顺序存储方式实现稀疏矩阵M1和M2相加的运算，运算结果由变量M返回
{
InitMatrix(M);
//若两个矩阵尺寸不同，则给出错误信息并停止运行
if ((M1.m!=M2.m)||(M1.n!=M2.n)){
cerr<<"tow matrix measurenents are different!"<<end1;
exit(1);
}
M.m=M1.m;M.n=M1.n;
//若两个矩阵均为零矩阵，则无须计算
if(M1.t==0)&&(M2.t==0))
return;
int i=1,j=1; //用i，j 分别指示M1.smt M2.sm数组中待比较元素的下标,初值均
//为1
int k=1; //用k指示M.sm数组中待写入元素的下标，初值为1
while((i<=M1.t)&&(j<=M2.t))
{//把行号较小元素写入到结果矩阵中,若行号相同进行列号的比较,使列号
//较小的元素写入到结果矩阵中,若行、列号均相等，则当相应元素的
//和不为0时才把这个和写入到结果矩阵中
if(M1.sm[i].row<M2.sm[j].row){
M.sm[k]=M1.sm[i];
i++;k++;
}
else
if(M1.sm[i].row>M2.sm[j].row){
M.sm[k]=M2.sm[j];
j++;k++;
}
else{
if(M1.sm[i].col<M2.sm[j].col){
M.sm[k]=M1.sm[i];
i++;k++;
}
else if(M1.sm[i].col>M2.sm[i].col{
M.sm[k]=M2.sm[j];
j++;k++;
}
else{//此时相应元素的行列号必然相等
if(M.sm[i].val+M2.sm[j].val!=0){
M.sm[k].row=M1.sm[i].row;
M.sm[k].col=M1.sm[i].col;
M.sm[k].val=M1.sm[i].val+M2.sm[j].val;
k++;
}
i++;j++;
}
}
}
while(i<=M1.t)
{ //把M1中的剩余元素写入到结果矩阵M中
M.sm[k]=M1.sm[i];
i++;k++;
}
while(j<=M2.t)
{ // 把M2中的剩余元素写入到结果矩阵M中
M.sm[k]=M2.sm[j];
j++;k++;
}
M.t=k-1;//把写入到结果矩阵M中元素的个数赋给M中保存元素个数的
//变量域
return;
}
3.画出下列每个广义表的带表头附加结点的链接存储结构图并分别计算出它们的长度和深度。
⑴ A=(())
⑵ B=(a,b,c)
⑶ C=(a,(b,(c)))
⑷ D=((a,b),(c,d))
⑸ E=(a,(b,(c,d)),(e))
⑹ F=((a,(b,(),c),((d)),e)))
解：每小题的长度和深度如下表示。
题号 1 2 3 4 5 6 长度 1 3 2 2 3 1 深度 2 1 3 2 3 4
4.编写一个建立广义表链接存储结构的算法，假定广义表由字符串值提供。
解：
void Create(GLNode*&GL,char*a)
//根据在字符串a中保存的广义表生成其对应的存储结构
{
static int i=0;//定义静态变量i指示a中待处理的字符串位置，每处理一
//个字符后i值增1
if(a[i]=='\0')
return; //当字符串处理结束后返回
if(a[i]=='#'){
GL=NULL;
i++;
}
else if(a[i]=='('){
GL=new GLNode;
GL->tag=True;
i++;
Create(GL->sublist,a);
}
if(GL=new GLNode;
GL->tag=False;
GL->data=a[i];
i++;
}
else{
GL=new GLNode;
GL->tag=False;
GL->data=a[i];
i++;
}
if(GL==NULL) //此时的a[i]必然为')'字符
i++;
else if(a[i]==','){
i++;
Create(GL->next,a);
}
else if((a[i]==')')||(a[i]==',')){
i++;
GL->next=NULL;
}
}
5.编写一个广义表中查找元素字等于给定值的算法，若查找成功则返回数值1，
否则返回数值0。
解：
int Find(GLNode*GL,char ch)
//从广义表GL中查找单元素字符等于ch的算法，若查找成功，则返回数值1，
//否则返回数值0
{
while(GL!=NULL){
if(GL->tag==0){//处理单元素结点
if(GL->data==ch)
return 1;//查找成功返回1
else
GL=GL->next; //否则继续向后查找
}
else{//处理子表结点
int x=Find(GL->sublist,ch);//向子表中继续查找
if(x)//若在子表中查找成功则返回1，否则继续向后查找
return 1;
else
GL=GL->next;
}
}
return 0； //当查找到表为空时返回0
}
