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

Question

如果在矩陣中，多數的元素並沒有資料，稱此矩陣為稀疏矩陣（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 楊修俊 (20.8k points)
Available when: 2017-12-23 09:00 - Due to: 2017-12-23 12:10 | 56 views

12 Answers

Page:

s410535044 · Answer 1 · 2017-12-23T02:48:35+0000

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 (154 points)

linda · Answer 2 · 2017-12-23T02:45:55+0000

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-23T02:34:20+0000

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-23T02:31:06+0000

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-23T02:30:43+0000

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-23T02:13:34+0000

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-23T01:36:09+0000

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-23T01:34:00+0000

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 (3.5k points)

s410535043 · Answer 9 · 2017-12-23T01:28:34+0000

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-23T01:27:34+0000

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