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

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