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

6 like 1 dislike
838 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 | 838 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:108.162.216.238
©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