第二次期中考補考-第一題

Question

930 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

輸出範例：

[Exam] asked Dec 23, 2017 in 2017-1 程式設計(一)AD by 楊修俊 (30k points)
ID: 38938 - Available when: 2017-12-23 09:00 - Due to: 2017-12-23 12:10 | 930 views

12 Answers

Page:

s410535044 · Answer 1 · 2017-12-23 10:48:35

Hidden content!
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i,j,x,y;
    while(scanf("%d %d",&x,&y)!=EOF)
    {
 **** *  ** ** *** ***   ** *     * * *******     array[x][y],non[x*y][3],count=0;
 * * *  *   *   ***  * ****** ****** * *  *  ***** ***   * *** *  *  *
   *        ***** ***      ** * ***     * **  ***** **  **    * **    ** ** * ** ***** *** ***  * *  *****
    ****  *    *   * **  *   *       ** ***  * ***   **  *  **   ** *     ***  **    ***  * ***    *      **   * * **  ** * * 
 ** ** *** * * **  **  ****   * *   **** ****     ****  * ******* *   **
**** *   ***    **   * ***   * *** *  * * * *    ***   ** * * *   ***  *   *****   ***  **  *  ***  
 ****** **  ***** * **  **   * *   *** * ****    * ***  * **  **** *  ***** * * ***    *  **   ***  ** * ** *  ***  * *  *   **  * * * ** *  * *
* **  *  **   ** ***    ***   ********* ****  *** * *  *  **** *  
        {
* * *** * ****  *  * **   * *    *   **** **  *** * **       ** *   *  ** **  ***  ** * **      
 ***** * ****  * * *** **  * ***        *   * ***** * *   **  *       
    ****   **  ***   * ** * **  *** *  *  * * ** *******    *  **  *** ***   ***   * ****  *  **  *  ******  *** *     *  **
*** *  *  *   ***   *** * ** ** **   ** * * ** * *  * ** *    *        **  * ** *  *** **   *   **      * **   
 *****  * ** ****   *  ** **   **  ***        **     * ****** * ***     * ** ***  * ** *** *  ****  **  ** *  *    * ** * * ** ****** *  * * *  
 **  * ******  **       *   * ** * ** *  ** * **  *     **    *  *    ***** ***  *  *  ** ****  ** *  **   ** *   ***  **    ***           *******
*** * *** ** **    *  *    *    *****   * *    **  * *  *   * * *****  *     *       *   * * * ** ****  *   *** **     *       **   *  *  *
* ** ** * * *** ** ****  * ** *         ** *         ***  *  **    ****** *** *   * * ** *  *  ***** **  ***      * *   * **  ***        * ** *
***  ** * *   ** ** * * *   *   ****   *  *   **  *  *****  * *    *** ***    *  **  *  **** * *    * * **** * 
 *   *   *      ** ***  *  ** *** *   * *   ** ***      ***     **   ****
*  ***       * *     ** *  *** *****  *** ** ***** *      **** 
 ** *  *** ** *  *** **  **    ** ***   **  * **  * ***   ***** ***  ** * %d %d\n",x,y,count);
 **   ***    ** * ********** ***** ***   *  *****    * ** *  *  * 
        {
** *** ***** ***  **  ***  * *****   *** ***  ***   ***  *    ** ***   * *  ***      ****** ** * **  * ***    *   ** %d %d\n",non[i][0],non[i][1],non[i][2]);
 * *  *  * * *   ** **  *  **  ** * *   * ** *   *   * ***

    }

    system("pause");
    return 0;
}

answered Dec 23, 2017 by s410535044 (114 points)

linda · Answer 2 · 2017-12-23 10:45:55

Hidden content!
#include<stdio.h>
int main(void)
{
   int a,b,i,j,num=0;
   int ch[a][b];
**    **  *    ** *  ****    *****    * *   ** 
*******  *  **  ** * *   *** *** 
   {
  **   * * *   *  *  ** *  *    **    ***  * **  *   ***   *   *
* *  **   *  ** *     ** ****       * *  *    *
 *   **  * ****    *  ***  * ** ** *       *   *  **** *  *    **
***  * *  ***  *** * ****** *  **   *  *** *  *      *** **   *
*** * ***    **     ******        *** * **  ***    **  ** **  *  ****  *  ** * ** * **
**      *** *** *   *** * *** * ***      *  **   ** * * 
*        * *  * **  ** *   * *** **  *  * 
   }
**  **  *** *  * *  ** *  *  * *  * %d %d",a,b,num);
 ****    * ** ** * **** * *    ** 
*****   *** *  ** *  ** * **    
*   *   *  *  **       **** **     *   **  *  * *  * 
 **   *** *  **  *** * ***  ** *****    
* ** ** * ***** ****    *  *  *     **  *  * ****   *   **   *
 *** ***    * * * **  *   **   * *    * *    *    * * *    *** * * **    *  *  * *    *   *** ***  %d %d\n",i,j,ch[i][j]);
 ****  *  ** **  * *  *   * 
 * *    **  * ***    * * * 

   return 0;
}

answered Dec 23, 2017 by linda (162 points)

zxcv1025 · Answer 3 · 2017-12-23 10:34:20

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 Dec 23, 2017 by zxcv1025 (196 points)

風暴死神Nasus · Answer 4 · 2017-12-23 10:31:06

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 Dec 23, 2017 by 風暴死神Nasus (131 points)

r8804023 · Answer 5 · 2017-12-23 10:30:43

Hidden content!
#include<stdio.h>

int main()
{
*  ** * * **   *      **   a, b, i, j,num=0;
  *   * *** ***   *** *     *    * **    *** ****** *** *
** *    *** * * ***  *******    *     * **** * * **    *
    int ch[a][b];
 ** *** **      ***** * * *** ***  **   *** *
 *    ** * **** * **      ** ***** ****
* * ** * **  ***       * * *    * ** * ** **  *   * * *   
   *** ** ***  **    ** *    * *    * 
 *    *   **  * * ****  * ++;
}
}
}
    ** *      * *  *** *   *   *    *  *  %d %d\n",a,b,num);
 *****  *** *     * * *   *  ****  **  *** *      *  
*****  **  **  *  * **  *      *** * **   *****
 **** **  ** *  **  *** ***   **  * ** * *   ****
 **  **  *  *     *   ****    * *  *   * **  *  %d %d\n",i,j,ch[i][j]);
}
}
}
}

answered Dec 23, 2017 by r8804023 (164 points)
edited Dec 23, 2017 by r8804023

0TXT · Answer 6 · 2017-12-23 10:13:34

Hidden content!
#include<stdio.h>

int main()
{
    int a,b,i,j,num=0;
    
* *     *** ****  * **** * ****  *    * *  *** **  ***** ***
*   * *    **  *  **  **    ** * **  *  **   **  * *** ****
    
    int ch[a][b];
    for(i=0;i<a;i++)
    {
* **** * * * ****   * **   ** *** **   **     *** *       ** * * * ** *     ***** *    ***  * ***   * *   **  ***  * * **  ****  *  * *    *   *  **   * 
*** *    *** *    **  * ***  *     *      **     *  * **  ***    ***    * ****  ** ** **** **     *   *       **** *    *  * ** ****
  *  ** *****  *  **  * ** ** *** *** **     *  * * * ***  *  *   **  * * *** *  ***    *  **** *   *****  **   * *   *** ** *    * *  ****    * *** **   **  * *** *    **   * ***   *   ***  *****    * *  * * * ** ***  ***** *   ** ***  *   *    ** **   *** * ********** ***
 **** ***  *           * **  *   * ******  ** *   * **  **  *   * * *  ** *** ** *  * ******* ********    *   ***  **** *   ** **  *** ** **    *** *   *  * ****  * * **   * * * **** *****   ********  **     **   ***  * *   * **   *    * * (ch[i][j]!=0)
 *    * *  *  *  *  * *    *** **  ***  *** *  **** ** ** * **** * **** ***   * * *   * * ***    * ** ****  *   * *** **  ** *     ** *** ***** ** * **  * ****  *  * **  ******* ****  ***        *  **  * *  ** ***   ** **    *** *    ** * * * * * *
 ** *   **  * * *  * * ** ****  ****     * *** *    **  *   * ***** * **** *  *  **   ***   ***  ***   ** *** * ****  * * *  * *   **  *    
    }
    
    printf("%d %d %d\n",a,b,num);
    
    for(i=0;i<a;i++)
    {
  * *  ** ** ******  *  ** **   **** * *       * ** * *  * **  *   * *   ** **     *****  * *  ***** ****   *     *  **** * * **  *****  * * *
***   *  *   **  *  ******* ** **   **   *** **     * **  *  *   *    ****     * *** * *    ***      ** *  *     ** * ***  * *     *
 * *** *  **    **       *    * **** **    ******* * * * **   **   ** ** ** * *      *** **** * ** * *   ****   ******    *    ** * * *  **  *  *****      *      ** *** ** ***  * ** *** **  *        **  ** ** ** *   *  *      ** * *  *    ** ****  ****  * (ch[i][j]!=0)
** *  * *  ** * **    * * *  * *     ***** ** *   ** ***    * *  *** * *  ***   * **   *     *   * *  **********  ** * ******     * ***      * ***  * **  **  * ** ** **     *** **  * ***   **   *  *  ** *  ****** ***  **  ******** *   **   ** * ** %d %d\n",i,j,ch[i][j]);
*  *  ** *   *  **  *   *     * **  *  **  *   *  ***  **  *   ** **  * *  *   **    **       *  ** * * ***  **      ** ** * ***   *      
    }
}

answered Dec 23, 2017 by 0TXT (215 points)

410536026 · Answer 7 · 2017-12-23 09:36:09

Hidden content!
#include<stdio.h>
int main()
{
    int i ,j,a,b,num=0,x=1;
 * *   * *        *   *    * *     *  *  **  * ***** * *    ***      *
    int arr[i][j];
    int m[1000][3];
** **** **    *** * * * ***  * *  
*** *     *  * **  *  *  *       
 ***   *  * * *** * **  * ***** *  
    {
 **** * * ****  *  *** **** * **  * ******* * *       * **  ** *
* ** * **   ****   * **** *******   **    *  * *  ** * 
     * *       *  *  * ** *   ***   **** ** * *  *   *  **   ** *****   * * ** * * **   **  ** * *    **   * *
********   **   *  *   ****  * * *****   *   * ** *    ****  *****      * *  *  * 
   **   *** ***  **  * *********     ***   *  * * * **  **  *      *    m[x][0]=a;
**** ****         *** *  ***** * * * *     ** * ****   *  *    *      ***  *   **** *  ** * **** *  
**** *  *  ** *  * ****   *  ** *  **  * * ** * ** * *    ***  *  *** *  ******  ** * **** * ***   **     * ***  
* *   *** ***     ***    *    ***     ***   **** *     ** * *    *   ** **** *******    **   ****  ***  *    ***** 
  ** * ** * * * *  ** *********   *** *    * * **  **** *  ****  * * *    * *  *** * **  * *  ** *  * 
   ** **** **  **    ***    *    *   **  *** ***** **  ***      *   **    
 *** *    * *    *    ****  *****  **** ***   ***
    }
 ***  ****  *  *** *  * ***   **   
* ***  *****    ****  * **   * *  * **  ** **
    {
 *  **** **      * ** ***  ** *  **** ***** ** * *  **** ***  
  *** **** * *  * **   *** * *   *  *   **** **  *   **    ** *** ** *  * *  ** ",m[a][b]);
  ******* * *  *     **  * **  *******  **** *  *   ******  ** *  * *
    }
}

answered Dec 23, 2017 by 410536026 (172 points)
edited Dec 23, 2017 by 410536026

郭建志 · Answer 8 · 2017-12-23 09:34:00

Hidden content!
#include<stdio.h>
int main()
{
    int array[1000][1000];
    int m, n, i, j, count=0;
*  * **  ************ * **  ** **           ***   ***  *  ***  *  ***  
*  *** **  ********     ***  ** *   * *
            ***   **  * ** **  *   *   * * * ***    * * *** 
*  * *   * **   ** *****   ****** * ** ****** *   * *** **  *** * *  **** * * * ******      * *     
    }
 *        *  ** *   *****  *  ***  * *** * * *
** *    * ****** * * *    **  ***    * ** ** * *  * *  **
*  *      ** **   ***  *   ******** * * **** *  *****     * *******   *  *
*    ***  *  * **  *  *    * **      *  ** **  * *  *  *  *****  **   **  ** * 
****    * * **** ** ** ****** **  ***  *  *   ** 
    }
** * ** ** * * * *** * * *   ************* *     *     
*  ** *             ******  ****  * * *
 *  * *  * * *    * **   * **  ***  *******  ****  * * * *** * *   ** *
  * *   *  *  * ** * **          * * **   * **** **** *  **** ** * * *******
****      * * * *  *** **    ***      ** * *   **** * *****  * *** **** ** * ***** ***  *  *** * *      ** ***  **  *   
 * ** ** **  **  *** ** ***  **  * *   *  *****   **** *   ** ****   * *** **  *  ***  **   ***** * *
* ***  *   **    ***  * *   * * ****  *****  **** **   *  * ** * ***   
    } * * *  *** **    *  ***   ***    **
    return 0;
}

answered Dec 23, 2017 by 郭建志 (144 points)
edited Dec 23, 2017 by 郭建志

prog.c: In function 'main':
prog.c:5:5: error: expected ',' or ';' before 'int'
     int m, n, i, j, count;
     ^~~
prog.c:6:19: error: 'm' undeclared (first use in this function)
     scanf("%d%d",&m,&n);
                   ^
prog.c:6:19: note: each undeclared identifier is reported only once for each function it appears in
prog.c:6:22: error: 'n' undeclared (first use in this function)
     scanf("%d%d",&m,&n);
                      ^
prog.c:7:9: error: 'i' undeclared (first use in this function)
     for(i=0;i<m;i++){
         ^
prog.c:8:12: error: 'j' undeclared (first use in this function)
        for(j=0;j<n;j++)
            ^
prog.c:14:11: error: 'count' undeclared (first use in this function)
           count++;
           ^~~~~
prog.c:25:5: error: 'returm' undeclared (first use in this function)
     returm 0;
     ^~~~~~
prog.c:25:12: error: expected ';' before numeric constant
     returm 0;
            ^

commented Dec 23, 2017 by The Judge (4.3k points)

s410535043 · Answer 9 · 2017-12-23 09:28:34

Hidden content!
#include<stdio.h>
int main()
{
    int x,y;
***  *** ***** *   *** *   *   *  ** * **  %d",&x,&y);
    int i,j,arr[x][y],count=0;
 *  ** **  ** * *  ***  ** ** * * *   * *
 *  *** ** ***  *    *  * *  *   *   ***** *** ****    *   ** * *  * *   
 **  *  **     **    * ** * ** **   * * ** *  * ***
** * * **     *    ** *** *     ****      ** *   * ** *******  * ** * ***  *  ****  * ******** ** *  * * *****  * ****   *
 *** **** ****    *  ** *   * **  * *** **  ** *      *      **    *  *  ** *** *  ***** *   ** 
     *   *  *** **   **** * *** ***** ***  * ******        ** **      **       **  **  *  ** *   *****    **** *  *** *
* ****  ***  *        **  *   **  * *   ** * **   *******
*    ***** ***     *** * *** ********  * *  %d %d\n",x,y,count);
* *  * ** ****** **   ******  *****   * **   * 
 **   *** *  *  ***  *   * *     * * *   ** *   * * * *  * *   * 
** **   * *   * * *  ******   ** **  **      *  *  **** 
* **** *  *     *       **     *** * ******** **    ** *** * * * * * * * *   **  *  * ****** 
* * *  *  * *    * *  ** ** *     ** * ******** ***      *      ** **    *** * *  *  ***  * ****   *    * * ***** ** *  * %d %d\n",i,j,arr[i][j]);
***** **   * * ** * *****    ** *     * ** * * *  *  ** 
    return 0;
}

answered Dec 23, 2017 by s410535043 (100 points)

黃建淳 · Answer 10 · 2017-12-23 09:27:34

Hidden content!
#include <stdio.h>

int main ()
{
    int sum=0,a,b,x,y;
  * *     ***     *****   *  * * ***  *** **    * **    
* * * **  *  * *  * *    **   *  *** * **** *** **  * 
    int arr[a][b];
    for (x=0;x<a;x++)
***    ****   * * ** *  *** * *  ***   *** *   * **  = 0;y<b;y++)
   * **  ** *  *** ***  * **  ** *  *** ***  ** **   ***  ***  * *    
     *  ** ** **  *   * * * *  * *   * *  *        **  **  ***  *  *     * *** * * *** **    *    *    *  * **      ******   
 * ***  *****  * * * ***  *  **   * * ****** ***** *    **** * * * ***  ** *  *
    for (x=0;x<a;x++)
 ** * ****  * ****** ***   * *****  ****** **** *  = 0;y<b;y++)
*** *  * ** *  * *      ** *   * *       ** * *** * *****   *** *  *****  *  
*      *   *** * * * ***** *** **  *   * ****  ** *  ** ***** *  *     * ******  ** *  **  *   ** * *  ( arr[x][y] != 0 )
*  * *****  ** * **      * *** ** *  * ****     *  *** * *  *** ** ****   *      **** * *  *** ** *    * = sum + 1;
* * ** ** * ****   **  ****** * ** * *    *  ****** *      *     *   
* * ** *  *  *  * *  * * *** ** *   * *  %d %d\n",a,b,sum);
** *  **** ** **   *  ** *    (x=0;x<a;x++)
  ******* *** ** * ** ** ***  *    * **  *   * = 0;y<b;y++)
     * * * ****  ** *  **  * *  **** *** ***  * *    * **  **   ** * ***   * * 
* * *     ***   * * * *      ***  ** * *  *    *  ****     * **    * ** ** *   ****   *   * * **    ( arr[x][y] != 0 )
 *  ** ***  *** * * * * **   * *  ** * * *  * *  * **   * *  *  **  ** **** *** * ** *   * ****  ****     **  **   * ** ** * %d %d\n",x,y,arr[x][y]);
  ***  *  **  **     **  *    *** *       ***  **  **   ** **  * **** **   * * 

 **  ***  * *  ********    0;
}

answered Dec 23, 2017 by 黃建淳 (209 points)

第二次期中考補考-第一題

Please log in or register to add a comment.

12 Answers

Please log in or register to add a comment.

Please log in or register to add a comment.

Please log in or register to add a comment.

Please log in or register to add a comment.

Please log in or register to add a comment.

Please log in or register to add a comment.

Please log in or register to add a comment.

Please log in or register to add a comment.

Please log in or register to add a comment.

Please log in or register to add a comment.

Related questions