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

6 like 1 dislike
2.8k 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 | 2.8k 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:104.23.197.65
©2016-2026

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 | 2.6k 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 | 3.2k 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 | 8.2k views
12,783 questions
183,442 answers
172,219 comments
4,824 users