c++ program 1. Write a program to simulate an indexed sequence. In an indexed se
ID: 3680029 • Letter: C
Question
c++ program
1. Write a program to simulate an indexed sequence. In an indexed sequence, each item (node) of an unsorted list is paired with an index node), where the indices are organized into a sorted list, as shown in Fig. 1. In Fig. 1, each item is a string, while each index is an int beginning at 0. Note that although the indices are sorted, gaps exist between the values of the indices, enabling one to insert additional items between the existing items. The lists are to be represented by original (written by yourself) lists of said items and indices, both encapsulated in a class cindexed Sea, with member functions to perform the functionally described below. Make my day! 13 Fig. 1. Indexed sequenceExplanation / Answer
Hi below i have given the C++ method for your reference,
void Sequence(int arr[], int n)
{
struct ele element[n];
for (int i = 0; i < n; i++)
{
element[i].index = i; /* Fill Indexes */
element[i].count = 0; /* Initialize counts as 0 */
element[i].val = arr[i]; /* Fill values in structure
elements */
}
/* Sort the structure elements according to value,
we used stable sort so relative order is maintained. */
stable_sort(element, element+n, mycomp);
/* initialize count of first element as 1 */
element[0].count = 1;
/* Count occurrences of remaining elements */
for (int i = 1; i < n; i++)
{
if (element[i].val == element[i-1].val)
{
element[i].count += element[i-1].count+1;
/* Set count of previous element as -1 , we are
doing this because we'll again sort on the
basis of counts (if counts are equal than on
the basis of index)*/
element[i-1].count = -1;
/* Retain the first index (Remember first index
is always present in the first duplicate we
used stable sort. */
element[i].index = element[i-1].index;
}
/* Else If previous element is not equal to current
so set the count to 1 */
else element[i].count = 1;
}
/* Now we have counts and first index for each element so now
sort on the basis of count and in case of tie use index
to sort.*/
stable_sort(element, element+n, mycomp2);
for (int i = n-1, index=0; i >= 0; i--)
if (element[i].count != -1)
for (int j=0; j<element[i].count; j++)
arr[index++] = element[i].val;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.