This section contains specifications for exercises dealing with
the topics in section 4.1. Solving these
tasks should give you the possibility to apply your lections learned
and compare your solutions with the ones given in the solutions
part of this tutorial.
Exercise 4.1.1: Write a STL program that declares
a vector of integer values, stores five arbitrary values in the
vector and then prints the single vector elements to cout.
Be sure to have read section 3.3 on how
to compile STL programs.
Solution
Exercise 4.1.2: Write a STL program that takes an
arbitrary sequence of binary digits (integer values 0 and 1) from
cin and stores them into a container. When receiving
a value different from 0 or 1 from cin
stop reading. Now, you should have a container storing a sequence
of 0's and 1's. After finishing the read-process,
apply a "bit-stuffing" algorithm to the container. Bit-stuffing
is used to transmit data from a sender to a receiver. To avoid
bit sequences in the data, which would erroneously be interpreted
as the stop flag (here: 01111110), it is necessary to ensure that
six consecutive 1's in the data are splitted by inserting
a 0 after each consecutive five 1's. Hint:
Complexity considerations (inserting in the middle of a vector
takes linear time!) and the fact, that inserting into a vector
can make all iterators to elements invalid should make you choose
the STL container list. A list of integers is defined
like a vector by list<int> l; All operations
explained in the vector section are provided for the list, too.
Get an iterator to the first list element. As long as
this iterator is different from the end() iterator increment
the iterator and dereference it to get the appropriate binary
value. Note that an element is always inserted before a specified
iterator-position and that this insertion doesn't affect all the
other iterators defined when using a list.
Solution
Exercise 4.1.3: Refine Exercise 4.1.2 and
print the original bit sequence and the "bit-stuffed"
bit sequence to cout. Use the hint from Exercise 4.1.2
to form a loop for the output procedure.
Solution
Exercise 4.1.4: Refine Exercise 4.1.3 and
print out the absolute and relative expansion of the bit sequence.
The absolute expansion is the expasion measured in bits (e.g.
the bit-stuffed sequence has increased by 5 bits), the relative
expansion is the percentage of the expansion (e.g. the relative
expansion between the "new" and "old" sequence
is 5.12%).
Solution
Exercise 4.1.5: Refine Exercise 4.1.4 and
write the inverse algorithm to the one in Exercise 4.1.2
that the receiver has to perform to get the initial binary data
representation. After the bit-stuffing and bit-unstuffing compare
your list with the original one using the equality operator==.
If the lists are equal, you did a fine job. Note: It is
advisable to include a plausibility test in your unstuff algorithm.
After a sequence of five consecutive ones there must be a zero,
otherwise something went wrong in the stuffing algorithm.
Solution
Continue with section 4.2
Back to index
Johannes Weidl
(J.Weidl@infosys.tuwien.ac.at)
- Apr 16, 1996