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

6 like 1 dislike
845 views
如果在矩陣中，多數的元素並沒有資料，稱此矩陣為稀疏矩陣（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
[Exam] asked in 2017-1 程式設計(一)AD by (18k points)
ID: 36176 - Available when: 2017-12-08 18:30 - Due to: 2017-12-08 21:00 | 845 views

6 Answers

0 like 0 dislike 
Hidden content!
#include <stdio.h>
int main(void)
{
* ** *****  *  *  *     **   A[m][n];
 *     ****  **     ***  *    *          * * *  ** *** *     **
 *** *** ** *      ******* **   *  *     ***  *** ***  ** **
  ** *** *   *   *  * **** * *
 **  *  *  *    *  *** *
 ** *********** *** **  *   * ** 
**  **    * *    **  ***   
***  **   *** *  **   *   *   *  ** *     * * **   ** **
 *  *  ** ***   *** ** ***   *  
*  **** *  **        *     * ** * * *****  ***    *
*   *    *  *     * * *
    
    return 0;   ** * *  * * * **       *  *   ** *    ***    **** 
 }
answered by (144 points)
0 0
prog.c: In function 'main':
prog.c:4:11: error: 'm' undeclared (first use in this function)
     int A[m][n];
           ^
prog.c:4:11: note: each undeclared identifier is reported only once for each function it appears in
prog.c:4:14: error: 'n' undeclared (first use in this function)
     int A[m][n];
              ^
prog.c:11:23: error: expected expression before ')' token
     printf("%d%d%d\n",)
                       ^
commented by (4.3k points)
0 0
prog.c: In function 'main':
prog.c:4:11: error: 'm' undeclared (first use in this function)
     int A[m][n];
           ^
prog.c:4:11: note: each undeclared identifier is reported only once for each function it appears in
prog.c:4:14: error: 'n' undeclared (first use in this function)
     int A[m][n];
              ^
prog.c:11:23: error: expected expression before ')' token
     printf("%d%d%d\n",)
                       ^
commented by (4.3k points)
0 like 0 dislike 
Hidden content!
#include<stdio.h>

int main(){
    
***  ** *  *  ****  * ***  *  a,b,x,y,i=0;
** *  ******       *******  **   **  %d",&a,&b);
    
 **   *    *   *   ** *   ** ch[a][b];
    
 ** *    ********* * ** ****    * * *****
**   *  * *****  ** ** ** * *  * * * * ** *    ** * **  **** *  * 
 *  * *** *******  * * *    **** *    ** ****      *  ** * * * ****   *  *   *****  * *    ** **  
**** *     *** * * *  *** ****  ***** *    * * *  * ********  * *    *  **** * ***
 * *** ** *  ****      **  ***   **** ***  **   * *  ** ** * **   *  **  * 
****** *    * ***  ***   **  **** *****   ***    *  * * * *     
         ***    * ** ** **   *** *     *  
*** **** ** ** **   **** ****  *  * *   %d %d\n",a,b,i);
**  * ****** **** **  **  * ** ****** *** **
  * * ** *  *     ****  *  * *    * ***  ** * *****   * * *  * **  * 
      **  * * * * ** *** * ** *** * *     * * *     *  ** *  * ** *  *****  ** **
**  **  **  **  **  *  **   ** ** *******      *   *     ***   * * ** ** * * * %d %d\n",x,y,ch[x][y]);}
 *      * * * **  * * *   ** * * ** * ******  * ** *   * * *  **   
    *  *  ** **** *** ** **  * ** * * **** * ****
 * ***     * **** **  ***  *** *   *    * system("pause");
}
answered by (192 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: Correct output
Case 1: Correct output
commented by (4.3k points)
0 like 0 dislike 
Hidden content!
*** **  **    ** ****
answered by (131 points)
0 0
/usr/lib/gcc/x86_64-linux-gnu/6/../../../x86_64-linux-gnu/Scrt1.o: In function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
commented by (4.3k points)
0 like 0 dislike 
Hidden content!
     * *       ****    
int main ()
{
 **** *  *  ***   *** *    * M,N;
*  * ***     * *  * ** *    ***    ** ***  ** **  *      **  ***
  * **** ***    **  **   ***  ****   ** %d",M,N);
*  ***  **  * *  *  *    
*  ** * *   ****  **  *     *** 0;
}
answered by (215 points)
0 0
Case 0: Wrong output
Case 1: Wrong output
commented by (4.3k points)
0 like 0 dislike 
Hidden content!
#include <stdio.h>

int main()
{
    int row,col;
    while(scanf("%d %d",&row,&col)!=EOF)
    {
 *   *      **         * *   *   ** *** * *    * ***** * array[row][col];
** * **** * *    **** ** * *  ***** *** *****   * save[row*col][3];
****      **    * ***** *** *** ***  ****   * * *****   *   * * i,j,count=0;
 ** * * *   **  **  ***  *   ****** * *    ***    *   *** *   *****
        {
* ** *   * *  * * *  *  *  *   **  ** ****  * * ** *   *** *  *  *    * ***    * * * * ****  *** * 
*     *  *  *      **    ****   ** ****   * * ***** **** *  *** * * ** *     *  *****    **  * *  ***  ***  *   ** *    **  **   *** ***  * *   **   
        }
*  ***  ***  *   * * *   ** * ***    **   * * **  ** *** *   ***   *******  ***
        {
*  *  **  *** *** ** ** * *  ****    *   *   *  *  * * **   *    ** *  ** *******  * *   ***     **  * 
*  *   *** ***   *  ***        * ** *  **     * ** **      * *     *   *   ** *****
          *  *** * *** * ***  ****  **  **  **    * *    ******  ***      **  *    * * * * * *  ******  ***  ** *
** * * * ***   * *  *  ***  ** ** *****   ** ** ***** * * **** *  *** **    ****   *  **** *  **   *    *  *  
* * * * * ** *    ***** ******  *  * *** * *** * * *******  **   *  ** **** ****  ***   ** * ****    *  **   *   ** * *  *** **  *   * ***   
*** ****    **** *  *****   * **   *   ** *  * **  **** *   *   * **   ** **** *  **** ***    ******   **  *** * *  *   ******   * * * *** * **     
**    *** ** *   ****  *    *  ****  *  * * * *  *** ****  **** * *  ***  ***      **  **  *******   ****** *   ****  *    * * *    ** * * *  
*  ** * *    *** *      **   ****   **   *     * *     **     *  * ** * ***  *  *****   *    **** * *  *   ** ** * *   *  *** *** * **
     *** *  ****   *   * **  **  * ********  ** ** *   *  **   ***    * *  ****  *    * ****   * *  * * *  
   ****  ***   * *****  ** ***   ** **    **  *    ****    ****  * * ** * *   **  * * ** 
 ** *   * *  *    ** *** ***** ***  ******** * ***  * *** **
*  **  ***   ***  ****  *  *  * *      * **  **  *** ************ **    %d %d\n",row,col,count);
**** **  ***** * **** * *    **  ******    ****  ***  *  *** *   *  * **** **
        {
        *  *** * ** *     * * ** * * *   * ** ****      * ** * * *     *** * *    ****** * * ** *  **
    *** *** * *    * ******* * ***  *  * *** * *  *   ** * ** ***  * * ** *** **  *  *      **  ***  ** ** *   * * ******** * *** * *** ***** ******     * **   ",save[i][j]);
* **** ****** ****   ******   *** * ***   *  *** ** *  * * ** ******    **  * ***   ****  *      *** **  * * **  
 *     **  *   **** ************  * **** **** *   ***

    }

    return 0;
}
answered by (114 points)
edited by
0 0
prog.c:1:1: error: expected identifier or '(' before numeric constant
 0 0 0 0 0 0
 ^
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 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: Correct output
Case 1: Correct output
commented by (4.3k points)
0 like 0 dislike 
Hidden content!
#include <stdio.h>
int main()
{
* **  * **** * *  * ***  * a,b;
*  ** *** * ** ** * ** **  ***  *** * %d",&a,&b);
 ** *****  **   ** * *  arr[a][b];
    int i,j,count=0;
*   **** * *    * ****      *   ***  * *  ** 
    {
      * *  **     *         ***   ** *   ****  ***   ***    * *   **  *
**  * *** *** * * **  ***  *** *    *  **** *    ***
***    *** ******* * ***   ***    * ****** *  ** ** *   ******* *****  * * ** *   * * ** *  **** 
*****  **** *   **   **  *  ****      *** * *  ****** ** *    *  *   ** * *  *   ** *   * * * * **  *  **  ****   
 * * *  * **** *  *  *  * * * ** *** *****    ****** *   
    }

* * * ****  **    *   ***   *****  *** * *    
    {
**** *  ** *** ** ** **  **      *  *    ***    *  *   * **  
***  *** **  * *** *** * **** *  **** * ****  *   *** 
* *   ** * * **  * **  * *    *  ** ** *** **** ** * * *  **  **  *** **** ** * ****  ** **
*     *    * **   * ***  *  ***** * ** ****** **    * *  *   **   * *  *    ***   **   ****  * * 
 *    ** * * ****    **    **   * **  * **  *** **      * 
    }
* **** * ***  * * * * ** ************       %d %d\n",a,b,count);
**** *     ***  ***** * **  **** ** *        
    {
  **       ** *   * * ***    ** * ** ** ***    ** * **       *    *
** *  *** ***     ***** *  *     **   ****  * 
 ****   *** *** *     * *  *    *******   *  ** *      *   * * * *  ****** *   *  * * ***** 
 *    * ***  ***    **  ****  * *   *** **           *** *    **  **  * *** **   *    *  *   ** * ** *  * *  **   *   * ***   *  *   %d %d\n",i,j,arr[i][j]);
  * *  * ***   ** **  **  * * *   ** * ****   * * ** ** ** *   *** 
    }
***     ** **  ** ** * **     0;
}
answered by (100 points)
1 0
Case 0: Correct output
Case 1: Correct output
commented by (4.3k points)
Welcome to Peer-Interaction Programming Learning System (PIPLS) LTLab, National DongHwa University
English 中文 Tiếng Việt
IP:172.69.59.13
©2016-2024

Related questions

3 like 0 dislike
5 answers
第二次期中考補考題庫 -3 稀疏矩陣
[Normal] Coding (C) - asked Dec 20, 2017 in 2017-1 程式設計(一)AD by 楊修俊 (30k points)
ID: 38153 - Available when: Unlimited - Due to: Unlimited | 692 views
2 like 0 dislike
5 answers
第二次期中考補考-第五題
[Exam] asked Dec 23, 2017 in 2017-1 程式設計(一)AD by 楊修俊 (30k points)
ID: 38942 - Available when: 2017-12-23 09:00 - Due to: 2017-12-23 12:10 | 833 views
2 like 0 dislike
18 answers
第二次期中考補考-第四題
[Exam] asked Dec 23, 2017 in 2017-1 程式設計(一)AD by 楊修俊 (30k points)
ID: 38941 - Available when: 2017-12-23 09:00 - Due to: 2017-12-23 12:10 | 2.2k views
12,783 questions
183,443 answers
172,219 comments
4,824 users