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

6 like 1 dislike
842 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 | 842 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.58.159
©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 | 831 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