编写将十字链表表示的矩阵A转置的程序算法，转置结果为另一个十字链表，并将该转置矩阵以三元组(i，j，value)的形式输出。
1
#include<iostream>
2using namespace std;
3#define MAX 100
4
5struct Node
6
{
7
int i,j; //
8 int e; //element
9 Node *right,*down;
10
};
11
12struct CrossList
13{
14 int r,c,nz;
15 Node **rhead,**chead;
16};
17
18
19int row,rowt;
20int col,colt;
21int nz; //not zore
22CrossList M,MT;
23
24void creatcrosslist(CrossList & M,int row,int col)
25{
26 int i,j,e;
27 Node *p,*q;
28
29 M.r=row; M.c=col;
30
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
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
41 for(i=1;i<=M.r;i++)
42 for(j=1;j<=M.c;j++)
43
{
44 scanf("%d",&e);
45 if(e)
46 {
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 {
54 p->right=M.rhead[i];
55 M.rhead[i]=p;
56 }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 {
63 p->down=M.chead[j];
64 M.chead[j]=p;
65 }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
74}//end creat
75
76void T()
77{
78 Node *p,*q,*s;
79 int i,j;
80
81 MT.r=rowt; MT.c=colt;MT.nz=nz;
82
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
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
93 for(i=1;i<=M.r;i++)
94 for(s=M.rhead[i];s!=NULL;s=s->right)
95 {
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 {
102 p->right=MT.rhead[p->i];
103 MT.rhead[p->i]=p;
104 }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
110 if(MT.chead[p->j]==NULL || MT.chead[p->j]->i > p->i)
111 {
112 p->down=MT.chead[p->j];
113 MT.chead[p->j]=p;
114 }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
122void travelcrosslist(CrossList M)
123{
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
131void free(CrossList &M)
132{
133 Node *p,*q;
134 int i;
135 for(i=1;i<=M.r;i++)
136 for(p=M.rhead[i];p!=NULL;)
137 {
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
151int main()
152{
153 scanf("%d%d",&row,&col);
154 rowt=col;
155 colt=row;
156
157 creatcrosslist(M,row,col);
158 printf("M:\n");
159 travelcrosslist(M);
160
161 T();//转置
162 printf("MT:\n");
163 travelcrosslist(MT); //遍历输出
164
165 free(M); //delete M
166 free(MT);//delete MT
167 return 0;
168}
posted on 2009-05-13 17:06
wyiu 阅读(940)
评论(0) 编辑 收藏 引用 所属分类:
数据结构