第二次期中考補考題庫 -3 稀疏矩陣

3 like 0 dislike

如果在矩陣中，多數的元素並沒有資料，稱此矩陣為稀疏矩陣（sparse matrix），由於矩陣在程式中常使用二維陣列表示，二維陣列的大小與使用的記憶體空間成正比，如果多數的元素沒有資料，則會造成記憶體空間的浪費，為 此，必須設計稀疏矩陣的陣列儲存方式，利用較少的記憶體空間儲存完整的矩陣資訊。

在這邊所介紹的方法較為簡單，陣列只儲存矩陣的行數、列數與有資料的索引位置及其值，在需要使用矩陣資料時，再透過程式運算加以還原，例如若矩陣資料如下 ，其中0表示矩陣中該位置沒有資料：

0 0 0 0 0 0
0 3 0 0 0 0
0 0 0 6 0 0
0 0 9 0 0 0
0 0 0 0 12 0

這個矩陣是5X6矩陣，非零元素有4個，您要使用的陣列第一列記錄其列數、行數與非零元素個數：

5 6 4

陣列的第二列起，記錄其位置的列索引、行索引與儲存值：

1 1 3
2 3 6
3 2 9
4 4 12

所以原本要用30個元素儲存的矩陣資訊，現在只使用了15個元素來儲存，節省了不少記憶體的使用。

 

請寫一個程式用上列的方法壓縮稀疏矩陣。

 

輸入說明：

一開始會輸入兩個正整數M N，代表矩陣的大小。接下來會有M行，每行N個數字。

 

輸出說明：

請輸出壓縮過的矩陣

 

輸入範例：
 

5 6
0 0 0 0 0 0
0 3 0 0 0 0
0 0 0 6 0 0
0 0 9 0 0 0
0 0 0 0 12 0



 

輸出範例：

 

5 6 4
1 1 3
2 3 6
3 2 9
4 4 12

 

[Normal] Coding (C) - asked in 2017-1 程式設計(一)AD by (30k points)
Available when: Unlimited - Due to: Unlimited | 63 views

5 Answers

0 like 0 dislike 
Hidden content!
#include<stdio.h>

int main(){
    int a,b,i,j,num=0;
****  * * *   **   ******  * *  *   ***** ** ** **  **
* *   * **  * *  *** **    *     **       * ** * ****** * 
    int ch[a][b];
* * * *   ** *   **** *  ****    ****   *    *
 ** ** *   **     ** ** * ***** **  *  * **  * *  *** **  *  ***  ** *  
   *  * ***  *  *   ***   **   * * **  *     *   ***  *** ** *  *** ** **  **  * * ** ** ** * *  *  *  ** ** 
* *    ******* **  * * ** *  **** ***    *** *** ** **        *  ** *   *   *     ** **  ******
* *    **    ***   **    *** **   * *    ** *  ****   ** ** * ****   *  *  ****      * *** * **    ** *** *****  *   
 *   **  * *  **  *  ***       ******  * * ** **    ***   *  **  ** *   **  *  
*** *********** *** * ***** *  * **  ***    **  ***    * *
    }
    printf("%d %d %d\n",a,b,num);
***   * ** **** *  ***  ****     * ******
 *   ** * *******   **** * *     *  *  * ** * ** *  * **   * ***  ***
**  * *** *** *   ** **   ***  * *  * * ***  *** *  ****  **       ** * * ***  * ** **** ****
  * * ** *   ** ****  ** **     * *   * *   ** ** * * *  **     *** *  ** *  ***    *    **  ** * *  ****       ** ** *** %d %d\n",i,j,ch[i][j]);
   ****     * *      * *    *   ****      *****     ****  * *   *   *    * ** 
**   **   ** *    *   *   ******  ***** * *   ** *  * *
    }
}
answered
0 0
Case 0: Correct output
Case 1: Correct output
commented by (4.3k points)
0 like 0 dislike 
Hidden content!
#include<stdio.h>

int main(){
    int a,b,i,j,num=0;
  *    *   * * **   **   *   * * * *** * * *   **  *
**    * * **  * **  * * *  **  **   ** **** * ** ** *  ****
    int ch[a][b];
  *** *** *  ** **  * * *  *   **** *  
 ***  *   * *   ******* *  *****  **  ***  * * ** ** *   ********  * **  
  *   *** *  ** ***      *** *   * *     *   ****   *       * *    ** ****  * ****** *  *      *****   *   * *  
** **   ** * ** ** * ***  **   ** * ** * *** * **** ** **       *    **    ** *
**    * ** * *  **    ** **  **   **  *  *       *    ****** **  * ** **  *******   *********    **  * * * *  *
* **** *** *****  * * **  **** *  ***  **    *      *** *****   * **  *** ** 
*  ** * ** ** * * * **     *  *  ** * * **** **   **
    }
    printf("%d %d %d\n",a,b,num);
** **   ***    **  * ******   *****     ***   *
   ** ** ** * * * * **  ** * *  *  *  *** *  * **     * *   *** * *   **     
 *       *  *** **  ** ****   * ** *  * * * ***  * **    *     *** * ****  ***** ** 
 *  *** *  *    * ****     **   * *  *  **  * **  * *  ***   * **    * *  **  ****   * ** ***  **   *** *   * **  **  %d %d\n",i,j,ch[i][j]);
***  ** **    * * *** *** *   *  *  *   * *  ***  **  **  * ****         **  ** * 
 * *** *** ** *  **** *** ***   *  **** * * * *
    }
}
answered by (190 points)
0 0
Case 0: Correct output
Case 1: Correct output
commented by (4.3k points)
0 like 0 dislike 
Hidden content!
 *** **** * ***   * *

int main(){
**    *   **  *  int *  ** ** ** 
 * * **  *  **     *  ** *  * * * **   * ** **     
* ******  **  *  * * *  ** **   ** * ** ***
    *  *     * int ch[a][b];
 *      *     * * **  *   **  ***** 
     *  **** * *  **** **   *      *** **** *  
 * *** * ** * **  *    **  ***     *          * * ****    ***   **   ** *  ***
* *****   **    *****  *** *     * **   * ** * *  *
**  **               num++;
    **  **  *  ** *       * ** ** }
   * * ** **  **  **  *   *  * }
* * * *  *  ** }
  * **** *   **     **  *     * %d  **   *  *    ***  
   *   **  * *  *  ** *  *
* ***  *  ** * * * ** *  *   * *  *  *      * * * * *
*******   ** *        ** ****   * *         ** * *   ****
 *  ***      ** ** *        **  * **** *  **  * ** * *  *** ***  ***  *    * %d   * *  * *   *** ** 
**  *  * **  * ** *  ****** **** *    }
  ** * *  *  *     ** * ***  *  }
*   *  *  **** }
}
answered by (192 points)
0 0
Case 0: Correct output
Case 1: Correct output
commented by (4.3k points)
0 like 0 dislike 
Hidden content!
#include<stdio.h>
int main()
{

 *  * ** ** *   **     *   r[1000][3]={0};

***    **   *   *****  *  *  M,N,j,k,count=0,temp;
*** *   * **    **  * ** **     *** %d",&M,&N);

* **    ***** ***  *    *** * * *    **  * 
 *** ** * *** *  ** ***
 *     *  *     * *  **     *****     * * * **** *  * *
 ***  *  *  *  * *  * * *** **  * *    *  * 
* * *  * ** ****  **    * *** * *   *** *  **  ***   ******   ****  *  *    *  *     *  * 
*   **** *  * *  ***** *  **     * ****** *  *** *  **  *      *
* *    *** **    * * *  *  ** * * **   ********    *  
* **    ** *    **   * * ** * **** * **** **   ** **  ** *   *****  *    *  ** 
 *  * *  ***** *** *        *****  *  * * * *  ** **  **  ***** *** ****  **** ******
 * *** ** **   ***   **  **  *    * *   *  * *  *   *** ** *  ** **  * **  *  *  **  ** ** *
*****    ** * *** **  * * *****  * ***********   *** ** * **        ** ** *  ** *   *  ** *   

 * *   * *  ****  * *   **  **  **** **  * * *   **  **
* **    **  ** *    * ***        ** *  
  *   ** *  *  ***  * *  *    **
r[0][0]=M;
r[0][1]=N;
r[0][2]=count;
for(j=0;j<count+1;j++)
{
printf("%d %d %d \n",r[j][0],r[j][1],r[j][2]);
}
return 0;

}
answered by (174 points)
edited by
0 0
Case 0: Wrong output
Case 1: Wrong output
commented by (4.3k points)
0 0
Case 0: Wrong output
Case 1: Wrong output
commented by (4.3k points)
0 0
Case 0: Wrong output
Case 1: Wrong output
commented by (4.3k points)
0 0
Case 0: Wrong output
Case 1: Wrong output
commented by (4.3k points)
0 like 0 dislike 
Hidden content!
* **** *   *   *     

int *  * *
{
 **   ***    * *   *  int n,m;
** *  ** *   ***  ****** ****** *     * * *** *   ***** != EOF )
 ***** ** *   * {
* *  **  *  **  *  * *    int ** * ****
***   *    *     *         ** int i,j;
*** ****      *   *   int count=0;
*** *  **    **  ** **  **** 
*****  * ** ***    * **  ***  *      ** ******   
*  * ** *****     *  *    {
   *      * * **    * *   **     * *    * *
 ** **  ** * **   ** * *   **   *   * ** ** ** {
**  *  ***   ** * *       * *  *  *    * * ***  ** **** *    * ****   * *****   **** * 
* ***     ***  *    **     *  *    ***  **   }
*****   *  *  * *  * *    *   * * }
**  *  **** *  * *  **   * *  ** *** **  **   *  
* ** * *     * *      ** **  
     *  *** *   *  * **  **   ** *** ***     **
********  ***  * * *     **    {
 **** ** *** *   * *****   *****   **  **   *   * *  ** *  **
 *** *  *           {
** *** **                * ** ** *    
   ** **     ****   * *    * * ** * ** *     * *    {
 ** *   * **  * *   *  *  * * * *  *                 ******* **
  * * *   **  *   *  *  * *  *** ** *  *     **    * }
* ****     **  *     *** *  * *    *   *    *  }
* * **  *  *  * *   *  *  **   * **   }
  *   *     **    ******* * * * *    * ** ** ** %d *  ** **    *   *
  *  *   ** ** *  * * ** **** 
 *  *     ***  * *      *** *            * *   
 ***** *  ****  *  *  *       **** {
**  *   * * *    **    **  *   *** *   *** *   ***  **** 
 **     ***     *****       * *   * * **    {
*    * * ** ***    * *  * * *  *     * *** *     ** **  * * ****   
*   ** *   * *  *    * *  *** **  * *   *  * *   *** {
  *   ******* * **      * **     ** **  **  * ** *      ** ** * * ****  **    *    * *   %d * *** * **  **** ***
  ****  *** * *  * *   ** * **  *  *  * * *  * ***   * *   *  ** *  * * ****** *  ** *  * * *    *  
 *  *    **  ***  * ***    * **     **  ** * **  **** *  }
 ** **   **  ***  *   * * * ***     * ** *  **  }
*** *    *  *      * *    *   * }
*    *  **  * }
   ***  * ****  return 0;
}
answered by (160 points)
0 0
Case 0: Wrong output
Case 1: Wrong output
commented by (4.3k points)
Get it on Google Play Welcome to Peer-Interaction Programming Learning System (PIPLS) LTLab, National DongHwa University
English 中文 Tiếng Việt
IP:162.158.79.107
©2016-2019

Related questions

6 like 1 dislike
6 answers
第二次期中考 -3 稀疏矩陣
[Exam] asked Dec 8, 2017 in 2017-1 程式設計(一)AD by Shun-Po (18k points)
Available when: 2017-12-08 18:30 - Due to: 2017-12-08 21:00 | 27 views
2 like 0 dislike
3 answers
第二次期中考補考題庫 -10 唐．喬凡尼
[Normal] Coding (C) - asked Dec 20, 2017 in 2017-1 程式設計(一)AD by 楊修俊 (30k points)
Available when: Unlimited - Due to: Unlimited | 48 views
2 like 0 dislike
5 answers
第二次期中考補考題庫 -9 骰子遊戲
[Normal] Coding (C) - asked Dec 20, 2017 in 2017-1 程式設計(一)AD by 楊修俊 (30k points)
Available when: Unlimited - Due to: Unlimited | 81 views
8,963 questions
76,076 answers
51,674 comments
2,195 users