编写将十字链表表示的矩阵A转置的程序算法,转置结果为另一个十字链表,并将该转置矩阵以三元组(i,j,value)的形式输出。
1
#include<iostream>
2
using namespace std;
3
#define MAX 100
4![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
5
struct Node
6![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
7
int i,j; //
8
int e; //element
9
Node *right,*down;
10
};
11![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
12
struct CrossList
13![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
14
int r,c,nz;
15
Node **rhead,**chead;
16
};
17![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
18![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
19
int row,rowt;
20
int col,colt;
21
int nz; //not zore
22
CrossList M,MT;
23![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
24
void creatcrosslist(CrossList & M,int row,int col)
25![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
26
int i,j,e;
27
Node *p,*q;
28![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
29
M.r=row; M.c=col;
30![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
31
if(M.rhead==NULL)
32
M.rhead=new Node*[M.r+1];
33
for(i=1;i<=row;i++)
34
M.rhead[i]=NULL;
35![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
36
if(M.chead==NULL)
37
M.chead=new Node*[M.c+1];
38
for(j=1;j<=col;j++)
39
M.chead[j]=NULL;
40![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
41
for(i=1;i<=M.r;i++)
42
for(j=1;j<=M.c;j++)
43![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
44
scanf("%d",&e);
45
if(e)
46![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
47
nz++;
48
p=new Node;
49
p->i=i;
50
p->j=j;
51
p->e=e;
52
if(M.rhead[i]==NULL || M.rhead[i]->j > j)
53![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
54
p->right=M.rhead[i];
55
M.rhead[i]=p;
56![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
57
for(q=M.rhead[i];q->right!=NULL && q->right->j < j;q=q->right);
58
p->right=q->right;
59
q->right=p;
60
}//end if
61
if(M.chead[j]==NULL || M.chead[j]->i > i)
62![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
63
p->down=M.chead[j];
64
M.chead[j]=p;
65![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
66
for(q=M.chead[j];q->down!=NULL && q->down->i < i;q=q->down);
67
p->down=q->down;
68
q->down=p;
69
}//end if
70
}//end if
71
}
72
M.nz=nz;//not zero
73![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
74
}//end creat
75![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
76
void T()
77![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
78
Node *p,*q,*s;
79
int i,j;
80![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
81
MT.r=rowt; MT.c=colt;MT.nz=nz;
82![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
83
if(MT.rhead==NULL)
84
MT.rhead=new Node*[MT.r+1];
85
for(i=1;i<=row;i++)
86
MT.rhead[i]=NULL;
87![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
88
if(MT.chead==NULL)
89
MT.chead=new Node*[MT.c+1];
90
for(j=1;j<=col;j++)
91
MT.chead[j]=NULL;
92![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
93
for(i=1;i<=M.r;i++)
94
for(s=M.rhead[i];s!=NULL;s=s->right)
95![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
96
p=new Node;
97
p->i=s->j;
98
p->j=s->i;
99
p->e=s->e;
100
if(MT.rhead[p->i]==NULL || MT.rhead[p->i]->j > p->j)
101![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
102
p->right=MT.rhead[p->i];
103
MT.rhead[p->i]=p;
104![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
105
for(q=MT.rhead[p->i];q->right!=NULL && q->right->j < p->j;q=q->right);
106
p->right=q->right;
107
q->right=p;
108
}//end if
109![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
110
if(MT.chead[p->j]==NULL || MT.chead[p->j]->i > p->i)
111![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
112
p->down=MT.chead[p->j];
113
MT.chead[p->j]=p;
114![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
115
for(q=MT.chead[p->j];q->down!=NULL && q->down->i < p->i;q=q->down);
116
p->down=q->down;
117
q->down=p;
118
}//end if
119
}
120
}
121![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
122
void travelcrosslist(CrossList M)
123![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
124
Node *p;
125
int i;
126
for(i=1;i<=M.r;i++)
127
for(p=M.rhead[i];p!=NULL;p=p->right)
128
printf("(%d,%d,%d)\n",p->i,p->j,p->e);
129
}
130![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
131
void free(CrossList &M)
132![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
133
Node *p,*q;
134
int i;
135
for(i=1;i<=M.r;i++)
136
for(p=M.rhead[i];p!=NULL;)
137![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
138
q=p->right;
139
delete p;
140
p=q;
141
}
142
M.r=0;
143
M.c=0;
144
M.nz=0;
145
delete []M.rhead;
146
M.rhead=NULL;
147
delete []M.chead;
148
M.chead=NULL;
149
}
150![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
151
int main()
152![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
153
scanf("%d%d",&row,&col);
154
rowt=col;
155
colt=row;
156![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
157
creatcrosslist(M,row,col);
158
printf("M:\n");
159
travelcrosslist(M);
160![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
161
T();//转置
162
printf("MT:\n");
163
travelcrosslist(MT); //遍历输出
164![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
165
free(M); //delete M
166
free(MT);//delete MT
167
return 0;
168
}
posted on 2009-05-13 17:06
wyiu 阅读(952)
评论(0) 编辑 收藏 引用 所属分类:
数据结构