sahil <ja*********@gm ail.comwrites:
Hello frends i am learning c language, I want to make a program which
count occurence of each element in an array .I write following code
for it but ity is not giving me desired result.pls help me.
So, let's take an example.
You have something like:
typedef int element_type;
typedef struct
unsigned int size;
element_type elements[];
} element_vector;
/* element_vector data={9,{1,2,3, 1,2,3,1,2,1}}; */
and you want to get something like:
typedef struct {
element_type element;
unsigned int count;
} unique_element;
typedef struct {
unsigned int size;
unique_element elements[];
} unique_element_ vector;
/* unique_element_ vector counts[]={3,{{1,4},{2,3 },{3,2}}}; */
This will be a simple iterative processus.
Assume that you have processed data[] from 0 to i-1, and therefore
you have a vector counts filled from 0 to number_of_uniqu e_elements-1
with unique elements, and their counts.
The iteration step will consist in processing data[i]. You have
basically two cases: either data[i] is already in counts[], then you
will have to find where, and increment counts[w].count, or it is not,
and then you will have to add it to counts. This is an alternative
processus:
unsigned int w=findInUniqueE lements(counts, data.elements[i]);
if(w<counts.siz e){
/* already in */
counts.elements[w].count++;
}else{
/* insert the first one */
w=counts.size;
counts.size++;
counts.elements[w].element=data.e lements[i];
counts.elements[w].count=1;
}
and finally we increment the index:
i++;
Now the question is what will be the stop condition of this loop.
Obviously, when we've processed all the data, that is, the stop
condition is:
i>=data.size
Finally, what will be the initial conditions? When we've not
processed anything, and therefore the counts vector is empty:
i=0;
counts.size=0;
Now, since you've not specified any limit for the vector sizes, and
we're programming in C, we will have to allocate them space for the
elements dynamically, and therefore use pointers:
typedef int element_type;
typedef struct
unsigned int size;
element_type* elements;
} element_vector;
typedef struct {
element_type element;
unsigned int count;
} unique_element;
typedef struct {
unsigned int size;
unique_element* elements;
} unique_element_ vector;
The maximum number of unique elements is actually the number of input
elements, so we can preallocate this space:
counts.elements =malloc(data.si ze * sizeof(counts.e lements[0]));
And finally we can wrap the iterative processus up:
initialization
while(not(stop_ condition)){
iteration;
}
which gives the following function:
unique_element_ vector* countElements(e lement_vector* data){
unique_element_ vector* counts=check_ma lloc_result(mal loc(sizeof(uniq ue_element_vect or)));
unsigned int i=;
counts->size=0;
counts->elements=check _malloc_result( malloc(data.siz e * sizeof(counts.e lements[0])));
while(not(i>=da ta->size)){
unsigned int w=findInUniqueE lements(counts, data->elements[i]);
if(w<counts->size){
/* already in */
counts->elements[w].count++;
}else{
/* insert the first one */
w=counts->size;
counts->size++;
counts->elements[w].element=data->elements[i];
counts->elements[w].count=1;
}
}
return(counts);
}
Of course, now you have to implement
unsigned int findInUniqueEle ments(unique_el ement_vector* counts,element_ type element);
but this is a simplier problem.
--
__Pascal Bourguignon__
