首页 > 代码库 > 三元组(课下总结)

三元组(课下总结)

 在讲三元组之前,让我回忆一下,正常情况下该如何存储一个矩阵呢?话不多说,看下面的代码

1 void save_Matrix() {2     int row,col;3     cin >> row >> col;4     for (int i = 0;i < row;i++) {5         for (int j = 0;j < col;j++) {6             cin >> a[i][j];7         }8     }9 }

估计不用我多说,大家肯定知道这是什么,对,就是正常情况下的二维数组存储。那么问题来了,我让你存储一个10000 × 10000的矩阵,你在机器上试试,看看能不能开的下这样一个二维数组(不要往下看了,试试,你会受益无穷的),是不是编译器报错了,这就对了。让我们来分析一下,首先如果要开一个这样的数组,那么需要多少byte呢,让我来告诉你一个int 类型的字符占用4byte,那么10^8个int类型占用多少个字节,答案很显然,是4 × 10^8;好,那么我们再来算一下,4 × 10^8 / 1024 KB = 4*10^8/1024/1024MB 大约在381MB,很大吧。那么我们该怎么存储呢?忘了告诉你一件事了,在这个矩阵中,非0元素很少,大约1个,10个,100个,1000个,反正不会很多,所以呢?我们只需开a[1000]的数组来存储这些非0数就可以了。那么现在你应该产生疑问了,那我怎么知道你存的数在什么位置呢?好,这个问题问的好,那接下来,就是重点了。请继续往下看。。。。。

 

如果要存储这些元素,一个数组肯定是不可以的,那么我们就来借助一下结构体(这里我没用struct,用class也是可以的),

1 template <typename T> class Node {2     public:3         int row,col;  // row 表示行号 col 表示列号4         T value; // value 则表示你要存储的元素的值5 };

 

好了,那么我们该怎样做呢,假设样例输入是这样,第一行输入两个数,row,col;接下来row行,每行col个数。(非0元素个数不超过1000个);

那么我们可以这样做,见如下代码:

 1 void input(Node<int>* a) { 2     int value;   pos = 0;//pos 非0元素的个数 3     cin >> row >> col; 4     for (int i = 0;i < row;i++) { 5         for (int j = 0;j < col;j++) { 6             cin >> value; 7             if (value) { 8                 a[pos].row = i; 9                 a[pos].col = j;10                 a[pos++].value =http://www.mamicode.com/ value;11             }12         }13     }14 }

 

如果矩阵是这样

01290000
0000000
-30000140
00240000
01800000
1500-7000

 

 

 

 

 

 

输入结束了,那么接下来,我让你把矩阵恢复原样输出来,你该怎么做?看下面的代码

 1 void output(Node<int>* a) { 2     int num = 0; 3     for (int i = 0;i < row;i++) { 4         for (int j = 0;j < col;j++) { 5             if (a[num].row == i && a[num].col == j) { 6                 cout << a[num++].value << " "; 7             } 8             else cout << 0 << " "; 9         }10         cout << endl;11     }12 }

那么问题又来了,请你把矩阵转置一下,输出来。(这下有点困难哈。。。该怎样实现转置呢?)先来个简单的,看代码

 1 void Trans_1(Node<int>* a,Node<int>* b) { 2     int num = 0; 3     for (int i = 0;i < col;i++) { 4         for (int j = 0;j < pos;j++) { 5             if (a[j].col == i) { // 这里有排序的功能,请自行模拟,你会发现其中的奥秘,O(∩_∩)O哈哈~ 6                 b[num].row = a[j].col; 7                 b[num].col = a[j].row; 8                 b[num].value =http://www.mamicode.com/ a[j].value; 9                 num++;10             }11         }12     }13 }

 主要思想是两层循环,第一层控制列数,第二层控制个数,那么if (a[j].col == i) 就会起到一个排序的作用,(你说啥?没看懂,那接着往下看。。。看我给你模拟出来)

经过上面的代码可以看到a的内容是这样的

rowcolvalue
0112
029
20-3
2514
3224
4118
5015
53-7

 

 

 

 

 

 

 

怎么样,表格出来了,你看懂表格了吧,不要告诉我你不知道表格什么意思,好,知道就接着往下看。。。。

当我转置的时候,我想做到的是,像上面表格row那样从小到大的序列,把col也排好序。(因为在输出的时候,不排序是不太现实还原矩阵的。当然如果你是大牛,但是大牛怎么会看我的博客呢,你还是按着我的来吧。。。O(∩_∩)O哈哈~。。。)

 

接下来程序是这样做的

i控制着col,j控制着pos,从col中先找i==0的,找到了两个对吧,然后再找i==1的又找到了两个,再找i==2的还是两个,就这样循环完就会出现接下来的表格

rowcolvalue
02-3
0515
1012
1418
209
2324
35-7
5214

 

 

 

 

 

 

 

转置成功了。

让我们来看一下时间复杂度怎么样O(col × pos),如果pos太多,col有太大,估计又会超时,怎么办好呢?O(∩_∩)O哈哈~,接下来交给你一个O(pos)的算法,往下看。。。。。。

孟子曰:鱼,我所欲也;熊掌,亦我所欲也。二者不可得兼,舍鱼而取熊掌者也。既然时间短了,那么空间复杂度就要提高。

接下来我们要设两个辅助数组,干嘛用的呢?

设colnum数组记录每列元素的个数, startpos数组来记录每列的初始位置。先看代码。。。

 1 void Trans_2(Node<int>* a,Node<int>* b) { 2     int startpos[col + 1],colnum[col + 1]; 3     memset(startpos,0,sizeof(startpos)); 4     memset(colnum,0,sizeof(colnum)); 5     for (int i = 0;i < pos;i++) { 6         colnum[a[i].col]++; 7     } 8     for (int i = 1;i < col;i++) { 9         startpos[i] = startpos[i - 1] + colnum[i - 1];10     }11     for (int i = 0;i < pos;i++) {12         int num = startpos[a[i].col]++;13         b[num].col = a[i].row;14         b[num].row = a[i].col;15         b[num].value =http://www.mamicode.com/ a[i].value;16     }17 }

为什么这样是对的呢?首先最主要的是startpos数组,因为它记录的是,每一列元素该存储在那个区间,那上面的那个例子来说,

第0列的元素存储在[0..1],第1列的元素存储在[2..3],第2列的元素存储在[4..5], 第3列没有,第4列存在[6,6],第5列在[7,7];现在懂了吧。

 所有的代码

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4  5 using namespace std; 6  7 template <typename T> class Node { 8     public: 9         int row,col;10         T value;11 };12 #define MAXN 100113 int row,col;14 int pos = 0;15 void input(Node<int>* a) {16     int value;pos = 0;17     cin >> row >> col;18     for (int i = 0;i < row;i++) {19         for (int j = 0;j < col;j++) {20             cin >> value;21             if (value) {22                 a[pos].row = i;23                 a[pos].col = j;24                 a[pos++].value =http://www.mamicode.com/ value;25             }26         }27     }28 }29 30 void output(Node<int>* a) {31     int num = 0;32     for (int i = 0;i < row;i++) {33         for (int j = 0;j < col;j++) {34             if (a[num].row == i && a[num].col == j) {35                 cout << a[num++].value << " ";36             }37             else cout << 0 << " ";38         }39         cout << endl;40     }41 }42 43 void Trans_1(Node<int>* a,Node<int>* b) {44     int num = 0;45     for (int i = 0;i < col;i++) {46         for (int j = 0;j < pos;j++) {47             if (a[j].col == i) {48                 b[num].row = a[j].col;49                 b[num].col = a[j].row;50                 b[num].value =http://www.mamicode.com/ a[j].value;51                 num++;52             }53         }54     }55 }56 57 void Trans_2(Node<int>* a,Node<int>* b) {58     int startpos[col + 1],colnum[col + 1];59     memset(startpos,0,sizeof(startpos));60     memset(colnum,0,sizeof(colnum));61     for (int i = 0;i < pos;i++) {62         colnum[a[i].col]++;63     }64     for (int i = 1;i < col;i++) {65         startpos[i] = startpos[i - 1] + colnum[i - 1];66     }67     for (int i = 0;i < pos;i++) {68         int num = startpos[a[i].col]++;69         b[num].col = a[i].row;70         b[num].row = a[i].col;71         b[num].value =http://www.mamicode.com/ a[i].value;72     }73 }
View Code

 

三元组(课下总结)