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

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

 

輸出範例：

 

5 6 4
1 1 3
2 3 6
3 2 9
4 4 12

Answer 1

Hidden content!
#include<stdio.h>

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

Comments

Case 0: Correct output
Case 1: Correct output
Case 2: Correct output

Answer 2

Hidden content!
#include<stdio.h>

int main()
{
** * ******  * *** ** *    r[1000][3];
* *   ** ******  *    *  *   ** M,N,j,k,temp=0,count=0;
    
**** * * ***** *      *  *  **    *  %d",&M,&N);
    
** ***  *    ******    * *** *      * *   
 *** *   **   **  ****   *
   ** **** *   **     * *   *  **     *    ***** ** ** *  ** * **
**  ** *** *   *   *   * *  ****         ** * 
 *****  *  * *** * ****  ** * * *** * ****** ****** ** *  *  *** **   ***  *** *****  * ***  * ****  **
*   *  *   ** *  ******* ** ******  ****** * *  *       ***** * ** * *  * 
       ***  **** *      * *  ** *  *   ** ***  * ******** ***  * 
* ** *****  ** **   * * ***  **  ** *** * *   *  **   *  ***  *** *  * *  ** ***** ** *** *  ** 
 * *  **   *     *** ****         *   * * ** ** * *  *** * *  ** * * * *     ***** *** *
*  *   *    * **    * ** **   **   *    **    *** *  * ****  * **  * ** * *  * *** *  *   * 
 **  *  * ***       **** *** ****  **     * *   * **  ****    * ** * * **     * * *****  *  ** *  *  *   **  *** * * ***     ***  * * * *****    *   *  ****** *** * *
*    **** **     **** **   ***** *   *****   **  *  * * *  *** *** * *  *******  *  *** *** *  ****  **  *   * ***  * ** ** **   ****** ** ***  *   *   **    **  ** *    *** *   *    *   *    *  * * **** *  * *  *    * *   * *** *       **     ** * ***
   * **      *********  *   *** *      *  *    *     * *  ** * * * ***  ** *  **   **     ** ***  ** *****   *  * ***  ** * * 
    }
   
   r[0][0]=M;
   r[0][1]=N;
* * *   **   * *** ***********   *
   
** *  ** ***   * ** ** * **  *  ******** * 
   {
**   ******** * **  *     ***  * ****   **  **** %d %d\n",r[j][0],r[j][1],r[j][2]); *   *   *  ***  *** ***   *** ***** *  *   *  *** *    *    ** *  *   **  **   ** **   *    * *      * ****  *  **  *  **   * **  *  *  * 
   }
    
}

Comments

Case 0: Wrong output
Case 1: Wrong output
Case 2: Wrong output

---

Case 0: Wrong output
Case 1: Wrong output
Case 2: Wrong output

---

Case 0: Wrong output
Case 1: Wrong output
Case 2: Wrong output

---

Case 0: Wrong output
Case 1: Wrong output
Case 2: Wrong output

---

Case 0: Wrong output
Case 1: Wrong output
Case 2: Wrong output

---

Case 0: Wrong output
Case 1: Wrong output
Case 2: Wrong output

---

Case 0: Wrong output
Case 1: Wrong output
Case 2: Wrong output

---

Case 0: Correct output
Case 1: Correct output
Case 2: Correct output