Page 9 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 2. Div (a, b)

Function: Divide a by b.
Precondition: b != 0
Postcondition: output = a/b.
There are two ways of implementing a data structure viz. static and dynamic. In static
implementation, the memory is allocated at the compile time. If there are more elements than
the specified memory then the program crashes. In dynamic implementation, the memory is

allocated as and when required during run time.
Any type of data structure will have certain basic operations to be performed on its data like
insert, delete, modify, sort, search etc depending on the requirement. These are the entities that
decide the representation of data and distinguish data structures from each other.

Let us see why user defined data structures are essential. Consider a problem where we need to
create a list of elements. Any new element added to the list must be added at the end of the list
and whenever an element is retrieved, it should be the last element of the list. One can compare
this to a pile of plates kept on a table. Whenever one needs a plate, the last one on the pile is taken
and if a plate is to be added on the pile, it will be kept on the top. The description wants us to
implement a stack. Let us try to solve this problem using arrays.
We will have to keep track of the index of the last element entered in the list. Initially, it will be
set to –1. Whenever we insert an element into the list we will increment the index and insert the
value into the new index position. To remove an element, the value of current index will be the
output and the index will be decremented by one. In the above representation, we have satisfi ed
the insertion and deletion conditions.
Using arrays we could handle our data properly, but arrays do allow access to other values in
addition to the top most one. We can insert an element at the end of the list but there is no way to
ensure that insertion will be done only at the end. This is because array as a data structure allows
access to any of its values. At this point we can think of another representation, a list of elements
where one can add at the end, remove from the end and elements other than the top one are not
accessible. As already discussed this data structure is called as STACK. The insertion operation is
known as push and removal as pop. You can try to write an ADT for stacks.
Another situation where we would like to create a data structure is while working with complex
numbers. The operations add, subtract division and multiplication will have to be created as per
the rules of complex numbers. The ADT for complex numbers is given below. Only addition and
multiplication operations are considered here, you can try to write the remaining operations.
The ADT for complex numbers is as follows:

Value Defi nition

1. Defi nition Clause: This data type has values a +ib where a and b are integers and i is equal
to under root of –1.
2. Condition Clause: i term should be present.

Operations
1. add:

Function: add, add two complex numbers a1 + ib1 and a2 + ib2.
Precondition: no Precondition.
Post condition: (a1 + a2) + i(b1 + b2).

4 LOVELY PROFESSIONAL UNIVERSITY