The stack, queue and deque data abstractions are all characterized by maintainin
ID: 650020 • Letter: T
Question
The stack, queue and deque data abstractions are all characterized by maintaining values in the order they were inserted. In many situations, however, it is the values themselves, and not their time of insertion, that is of primary importance. The simplest data structure that is simply concerned with the values, and not their time of insertion, is the Bag. A conceptual definition of the Bag operations is shown at right. In subsequent lessons we will encounter several different implementation techniques for this abstraction. In this lesson we will explore how to create a bag using a dynamic array as the underlying storage area.
Recall that the dynamic array structure maintained three data fields. The first was a reference to an array of objects. The number of positions in this array, held in an integer data field, was termed the capacity of the container. The third value was an integer that represented the number of elements held in the container. This was termed the size of the collection. The size must always be smaller than or equal to the capacity.
As new elements are inserted, the size is increased. If the size reaches the capacity, then a new internal array is created with twice the capacity, and the values are copied from the old array into the new. In Worksheet14 you wrote a routine _setCapacityDynArr, to perform this operation.
To add an element to the dynamic array you can simply insert it at the end. This is exactly the same behavior as the function addDynArray you wrote in Worksheet 14.
The contains function is also relatively simple. It simply uses a loop to cycle over the index values, examining each element in turn. If it finds a value that matches the argument, it returns true. If it reaches the end of the collection without finding any value, it returns false. Because we want the container to be generalized, we define equality using a macro definition. This is similar to the symbolic constant trick we used to define the type TYPE. The macro is defined as follows:
# ifndef EQ
# define EQ(a, b) (a == b)
# endif
The ifndef preprocessor instruction allows the user to provide an alternative definition for the EQ function. If none is provided, the primitive equality operator will be used.
The remove function is the most complicated of the Bag abstraction. To simplify this task we will divide it into two distinct steps. The remove function, like the function contains, will loop over each position, examining the elements in the collection. If it finds one that matches the desired value, it will invoke a separate function, removeAt (from Worksheet 14), that removes the value held at a specific location.
void removeDynArr (struct DynArr * dy, TYPE test) {
int i;
for (i = 0; i < dy->size; i++) {
if (EQ(test, dy->data[i])) { /* found it */
_dynArrayRemoveAt(dy, i);
return;
}
}
}
Notice two things about the remove function. First, if no matching element is found, the loop will terminate and the function return without making any change to the data. Second, once an element has been found, the function returns. This means that if there were two or more occurrences of the value that matched the test element, only the first would be removed.
The removeAt function takes as argument an index position in the array, and removes the element stored at that location. This is complicated by the fact that when the element is removed, all values stored at locations with higher index values must be moved down.
Once the values are moved down, the count must be decremented to indicate the size of the collection is decreased.
Based on these ideas, complete the following skeleton implementation of the bag functions for the dynamic array. You can use any of the functions you have previously written in earlier lessons.
struct DynArr {
TYPE * data;
int size;
int capacity;
};
/* the following were written in earlier lessons */
void initDynArr (struct DynArr * da, int initCap);
void addDynArr(struct DynArr * da, TYPE e);
/* remove was shown earlier, to use removeAt */
void removeDynArr (struct DynArr * da, TYPE test) {
int i;
for (i = 0; i < dy->size; i++) {
if (EQ(test, dy->data[i])) { /* found it */
_dynArrayRemoveAt(dy, i);
return;
}
}
}
/* you must write the following */
int containsDynArr (struct DynArr * da, TYPE e) {
}
What should the removeAt method do if the index given as argument is not in range?
What is the algorithmic complexity of the method removeAt? Given your answer to the previous question, what is the worst-case complexity of the method remove?
What are the algorithmic complexities of the operations add and contains?
Explanation / Answer
If the index given as argument is not in range the method removeAt should display an appropiate error message to the user and should not remove any item. It should skip out of the method after displaying the message.
Algorithmic complexity of the method removeAt
removeAt() method on any list simply indexes the given item, and so its algorithmic complexity is O(1).
Removing any item from the end of any list is always of order 1 i.e O(1). Generally removing any item takes order n i.e O(n) time since the reshuffling is needed to be done. So, generally the total time complexity for the removal mechanism is O(n)+O(1).
Therefore simply O(n) is the case.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.