Writing this program in C. How do I do this exercise? A sparse vector is a vecto

Question

Writing this program in C. How do I do this exercise?

A sparse vector is a vector whose most components are zero. To store a sparse vector efficiently it is enough to store only its non-zero components and their index (position in the vector). The components of a vector are indexed starting from 0, like in C arrays. Precisely, to store a sparse vector with n components, only k of which are non-zero, we can use two arrays: val and pos, each of size k. For example, if the sparse vector x with 8 components is the following 0 0 23 0 7 0 0 48 then k-3 and val contains 23 -7 48 pos contains 2 Notice that the elements of array pos are in increasing order. We will assume that each vector contains at least one non-zero element Write a function efficient) with prototype void efficient( const int source[l, int val, int pos[I, int size) which computes the efficient representation of vector source, by filling the arrays val and pos. Parameter size represents the number of components of vector source (i.e., the size of the array). Assume that the size of arrays pos and val equals the number of non-zero values of vector source. Additionally, write a function reconstruct() with prototype . void reconstruct( int source[, int m, const int val[l, const int pos[l, int n) which reconstructs vector source from the efficient representation stored in arrays val and pos. Parameter n represents the size of arrays val and pos. Parameter m represents the size of array source, which equals the dimension of the vector Write a program to test the two functions.

Explanation / Answer

#include <stdio.h>

// traverse the original array and for values that are non zero
// store the index in pos array and store the values in val array

void efficient( const int source[], int val[], int pos[], int size){
int k =0;
  
for(int i=0;i<size;i++){
if(source[i]!=0){
val[k] = source[i];
pos[k] = i;
k++;
}
}
}

// traverse the new source array and if the value at pos[k] matches
// with the iterator i copy that values in new source array

void reconstruct(int source[],int m, const int val[], const int pos[], int n){
int k = 0;
for(int i=0;i<m;i++){
if(pos[k]==i){
source[i] = val[k];
k++;
}else{
source[i] = 0;
}
}
}

int main(){
  
// take source array size as input
int source_size;
scanf("%d",&source_size);
int source[source_size];
  
//variable to keep track of number of non zero elements
int count_non_zero = 0;
  
//take source array input
for(int i=0;i<source_size;i++){
scanf("%d",&source[i]);
if(source[i]!=0){
count_non_zero++;
}
}
  
//create two arrays val and pos
int val[count_non_zero];
int pos[count_non_zero];
  
// call efficient function to get required val and pos arrays
efficient( source,val,pos,source_size);
  
// checking val and pos array by printing them
for(int i=0;i<count_non_zero;i++){
printf("Position: %d Value: %d ",pos[i],val[i]);
}
  
//new source array
int source1[source_size];
//calling the reconstruct function
reconstruct(source1, source_size, val, pos,count_non_zero);
  
//printing the reconstructed new source array
printf("Recontructed Source Array: ");
for(int i=0;i<source_size;i++){
printf("%d ",source1[i]);
}
  
return 0;
  
}

Input:

9
1 0 0 2 3 0 5 0 7

Output:

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.