三元组存以及十字链表的创建

  1 #define _CRT_SECURE_NO_WARNINGS
  2 #include <iostream>
  3 #include<fstream>
  4 #define _CRT_SECURE_NO_WARNINGS
  5 using namespace std;
  6 
  7 struct TripleArray
  8 {
  9     int row;//行
 10     int col;//列
 11     int val;//值
 12 };
 13 //三元表
 14 
 15 int row = 1;//记录元数组行数
 16 int col = 0;//记录元数组列数
 17 int arr[11][11];//元数组
 18 int MartNumb = 1;//记录三元组个数=非零元个数
 19 TripleArray MariA[200];//三元组
 20 TripleArray MariB[200];//三元组
 21 
 22 /*十字链表的结构类型定义如下：*/
 23 typedef struct OLNode
 24 {
 25     int row;
 26     int col; 
 27     int value;
 28     OLNode* right; 
 29     OLNode* down;
 30 };
 31 
 32 typedef struct
 33 {
 34     OLNode** row_head;
 35     OLNode** col_head;
 36     int totalrow;
 37     int totalcol;
 38     int NotZeroNumbs;
 39 } CrossList;
 40 
 41 void CreateCrossList(CrossList* M)
 42 {
 43     OLNode* p;
 44     OLNode* q;
 45 
 46     M->totalrow = row;
 47     M->totalcol =col;
 48     M->NotZeroNumbs = MartNumb;
 49 
 50     //开辟空间
 51     if (!(M->row_head = (OLNode**)malloc(row * sizeof(OLNode*))))
 52         exit(OVERFLOW);
 53     if (!(M->col_head = (OLNode**)malloc(col * sizeof(OLNode*))))
 54         exit(OVERFLOW);
 55     /*初始化行、列，头指针指向量，各行、列链表为空的链表*/
 56     for (int h = 1; h <=row; h++)
 57     {
 58         M->row_head[h] = NULL;
 59     }
 60     for (int t = 1; t <=col; t++)
 61     {
 62         M->col_head[t] = NULL;
 63     }
 64 
 65     for (int i=1;i<=row;i++)
 66         for (int j = 1; j <= col; j++)
 67         {
 68             if (arr[i][j] != 0)
 69             {
 70                 if (!(p = (OLNode*)malloc(sizeof(OLNode))))
 71                     exit(OVERFLOW);
 72 
 73                 p->row = i;
 74                 p->col = j;
 75                 p->value = arr[i][j];
 76 
 77                 if (M->row_head[i] == NULL)
 78                 {
 79                     M->row_head[i] = p;
 80                     p->right = NULL;
 81                 }
 82                 else
 83                 {
 84                     /*寻找行表中的插入位置*/
 85                     for (q = M->row_head[i]; q->right && q->right->col < j; q = q->right);
 86                     p->right = q->right;
 87                     q->right = p; /*完成插入*/
 88                 }
 89                 if (M->col_head[j] == NULL)
 90                 {
 91                     M->col_head[j] = p;
 92                     p->down = NULL;
 93                 }
 94                 else
 95                 {
 96                     //寻找列表中的插入位置
 97                     for (q = M->col_head[j]; q->down && q->down->row < i; q = q->down);
 98                     p->down = q->down;
 99                     q->down = p;
100                 }
101             }
102         }
103 }
104 
105 //创建三元组
106 void CreateTripleArray()
107 {
108     for (int i = 1; i <= row; i++)
109     {
110         for (int j = 1; j <= col; j++)
111         {
112             if (arr[i][j] != 0)//如果非零就存进去
113             {
114                 MariA[MartNumb].col = j;
115                 MariA[MartNumb].row = i;
116                 MariA[MartNumb].val = arr[i][j];
117                 MartNumb++;
118             }
119         }
120     }
121 }
122 
123 void SortMartic()
124 {
125     //冒泡排序
126     for (int i = 1; i < MartNumb-1; i++)
127     {
128         for (int j = i + 1; j < MartNumb; j++)
129         {
130             if (MariA[i].row > MariA[j].row)
131             {
132                 int temp;
133                 temp = MariA[i].row;
134                 MariA[i].row = MariA[j].row;
135                 MariA[j].row = temp;
136 
137                 int temp2;
138                 temp2 = MariA[i].col;
139                 MariA[i].col = MariA[j].col;
140                 MariA[j].col = temp2;
141 
142                 int temp3 = MariA[i].val;
143                 MariA[i].val = MariA[j].val;
144                 MariA[j].val = temp3;
145             }
146             //假如行数相同比较列数
147             else if (MariA[i].row == MariA[j].row && MariA[i].col > MariA[j].col)
148             {
149                 int temp2;
150                 temp2 = MariA[i].col;
151                 MariA[i].col = MariA[j].col;
152                 MariA[j].col = temp2;
153 
154                 int temp3 = MariA[i].val;
155                 MariA[i].val = MariA[j].val;
156                 MariA[j].val = temp3;
157             }
158         }
159     }
160 }
161 
162 void OverTurnMart()
163 {
164     int q = 1;
165     for (int k = 1; k <= col; k++)
166     {
167         for (int p = 1; p < MartNumb; p++)
168         {
169             if (MariA[p].col == k)
170             {
171                 MariB[q].row = MariA[p].col;
172                 MariB[q].col = MariA[p].row;
173                 MariB[q].val = MariA[p].val;
174                 q++;
175             }
176         }
177     }
178 }
179 
180 int main()
181 {
182     //文件读取矩阵操作
183     FILE* fp = fopen("datamatrix.txt", "r");
184     if (fp == NULL)
185         return 0;
186     int a = fgetc(fp);
187     while (a != EOF)
188     {
189         //数字操作（可能两位数）
190         if (a - '0' >= 0 && a - '0' <= 9)
191         {
192             int sum = a - '0';
193             a = fgetc(fp);
194             while (a - '0' >= 0 && a - '0' <= 9)
195             {
196                 sum = sum * 10 + a - '0';
197                 a = fgetc(fp);
198             }
199             col++;
200             arr[row][col] = sum;
201         }
202         if (a == '\n')
203         {
204             row++;
205             col = 0;
206         }
207         a = fgetc(fp);
208     }
209 
210     cout << "row:" << row << endl;
211     cout << "col:" << col << endl;
212 
213     cout << "数组是：" << endl;
214     for (int i = 1; i <= row; i++)
215     {
216         for (int j = 1; j <= col; j++)
217             cout << arr[i][j] << " ";
218         cout << endl;
219     }
220 
221     //创建三元组
222     CreateTripleArray();
223 
224     fstream Output1;
225     Output1.open("matrix.txt", ios::out);
226     cout << "三元组是:" << endl;
227     for (int i = 1; i < MartNumb; i++)
228     {
229         cout << MariA[i].row << " " << MariA[i].col << " " << MariA[i].val << endl;
230         Output1<< MariA[i].row << " " << MariA[i].col << " " << MariA[i].val << endl;
231     }
232     Output1.close();
233 
234     cout << "选择转置方式（1或2）" << endl;
235     int choice;
236     cin >> choice;
237    
238     if (choice == 1)
239     {
240         cout << "矩阵转置1" << endl;
241         fstream Output2;
242         Output2.open("matrix-a.txt", ios::out);
243         for (int i = 1; i < MartNumb; i++)
244         {
245             int t = MariA[i].col;
246             MariA[i].col = MariA[i].row;
247             MariA[i].row = t;
248         }
249         cout << "排序" << endl;
250         SortMartic();
251         for (int i = 1; i < MartNumb; i++)
252         {
253             cout << MariA[i].row << " " << MariA[i].col << " " << MariA[i].val << endl;
254             Output2 << MariA[i].row << " " << MariA[i].col << " " << MariA[i].val << endl;
255         }
256         Output2.close();
257     }
258     else if (choice == 2)
259     {
260         cout << "矩阵转置2" << endl;
261         fstream Output3;
262         Output3.open("matrix-b.txt", ios::out);
263         OverTurnMart();
264         for (int i = 1; i < MartNumb; i++)
265         {
266             cout << MariB[i].row << " " << MariB[i].col << " " << MariB[i].val << endl;
267             Output3 << MariB[i].row << " " << MariB[i].col << " " << MariB[i].val << endl;
268         }
269         Output3.close();
270     }
271 
272     //创建十字链表
273     CrossList M;
274     CreateCrossList(&M);
275 
276     fstream Output4;
277     Output4.open("matrix-c.txt", ios::out);
278     cout << "遍历所有行非零元素" << endl;
279     for (int i = 1; i <= row; i++)
280     {
281         OLNode* pCur = M.row_head[i];
282         while (pCur != NULL)
283         {
284             cout << pCur->row << " " << pCur->col << " " << pCur->value << endl;
285             Output4<< pCur->row << " " << pCur->col << " " << pCur->value << endl;
286             pCur = pCur->right;
287         }
288     }
289     Output4.close();
290 
291     return 0;
292 }