Ec 2202 Data Structures and Object Oriented Programming in C

Ec 2202 Data Structures and Object Oriented Programming in C

EC 2202 DATA STRUCTURES AND OBJECT ORIENTED PROGRAMMING IN C++

UNIT III DATA STRUCTURES & ALGORITHMS

3.1. Algorithm

An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaininga required output for any legitimate input in a finite amount of time.

3.1.1. Fundamentals of algorithmic problem solving

Understanding the Problem:

• Clearly read the problem

• Ask any doubts you having

• Analysis what is the input required

Decision making on

• Capabilities of computational devices: The algorithm should adapt to your system. For example if your system executes the instruction in parallel then you have to write parallel Algorithm or else if you having RAM machine (The system executes the instruction sequentially) then you have to write serial algorithm. Decide exact or approximate output need : Write an algorithm depends on output need. For example to find the square root the approximate output is enough but finding shortest way between the cities, we need an exact result.

• Decide Data Structure: In which format going to give the input. Example data structures are Stack, Queue, List and etc.

• Algorithm Techniques: Decide which technique used to write an algorithm. For example you can divide the big problem into number of smaller units and solve each unit. This technique called as Divide and Conquer method. So depending on the problem you can select any onetechniques. Some techniques are Decrees and Conquer, Brute Force, Divide and Conquer andetc.

Specification of an Algorithm:

The way for specifying an algorithm. There are three ways to represent an algorithm

• Natural Language : You can represent the instruction in the form of sentence.

• Pseudo Code : Use identifier, keywords and symbols to represent the instructions. For examplec=a+b.

• Flowchart : The another way for representing the instructions. In this use diagrams and link thesequence using lines. The separate diagrams are available based on the instructions.

Algorithm Verification:

To verify the algorithm apply all the possible input and check the algorithm produce the required

output or not..

Analysis of Algorithm:

Compute the efficiency of the algorithm.. The efficiency iis depend on the following factors

• Time: The amount of time to take execute the algorithm. If the algorithm take lessamount of time to execute then this one will be the best one.

• Space: The amount of memory required to store the algorithm and the amount of memoryrequired to store the input for that algorithm.

• Simplicity: The algorithm should not having any complex instructions. That type ofinstructions are simplified to number of smaller instructions.

• Generality: The algorithm should be in general. It should be implemented in anylanguage. The algorithm is not fit in to a specific output.

Implementation :

After satisfying above all factors code the algorithm in any of language you known and executethe program.

3.1.3. Properties of the algorithm

) Finiteness: - an algorithm terminates after a finite numbers of steps.

2) Definiteness: - each step in algorithm is unambiguous. This means that the action specified by

the step cannot be interpreted (explain the meaning of) in multiple ways & can be performed

without any confusion.

3) Input:- an algorithm accepts zero or more inputs

4) Output:- it produces at least one output.

5) Effectiveness:- it consists of basic instructions that are realizable. This means that the

instructions

6) Non Ambiguity: The algorithm should not having any conflict meaning..

7) Range of Input: Before design a algorithm,, decide what type of iinput going to

given,, whatsis the required output..

8) Multiplicity: You can write different algorithms to solve the same problem..

9) Speed : Apply some idea to speed up the execution time..

3.1.4. Analysis of algorithm

Analysis Framework :

Analysis : To compute the efficiency of an algorithm. When compute the efficiency of an

algorithm, consider the following two factors.

_ Space Complexity

_ Time Complexity

(i) Space Complexity :The amount of memory required to store the algorithm and the amount

of memory required to store the inputs for this algorithm.

S(p) = C + Sp where,

C – Constant (The amount of memory required to store the algorithm)

Sp – The amount of memory required to store the inputs. Each input stored in one unit.

Example :Write an algorithm to find the summation of n numbers and analysis the space

complexity for that algorithm..

Algorithm Summation (X ,,n)

//// Input : n Number of elements

//// Output : The result for summation of n numbers..

sum = 0

for I = 1 to n

sum = sum+ X[ii]

return sum

The Space Complexity of above algorithm:

S(p) = C + Sp

1.. One unit for each element in the array.. The array having n number of elements so the array

required in unit..

2.. One unit for the variable n,, one unit for the variable I and one unit for the variable sum..

3.. Add the above all units and find the space complexity..

S(p) = C + (n + 1 + 1 + 1)

S(p) = C + (n + 3)

(ii) Time Complexity

The amount of time required to run the algorithm.. The execution time depends on the following

factors..

• System load

• Number of other programs running

• Speed of hardware

How to measure the running time?

• Find the basic operation of the algorithm. (The inner most loop or operation is called basic

operation)

• Compute the time required to execute the basic operation.

• Compute how many times the basic operation is executed. The Time complexity calculated by

the following formula

T(n) = Cop * C(n) Where,

Cop – Constant (The amount of time required to execute the basic operation)

C(n) – How many times the basic operation is executed.

Example :The Time complexity of the above algorithm

(Summation of n Numbers)

1. The Basic operation is: addition

2. To compute how many times the Basic operation is executed: n

3. So, T(n) Cop * n

4. Remove the constant or assume Cop = 1

5. The Time Complexity is T(n) = n.

3.2. List ADT

Abstract Data Type (ADT)

A set of data values and associated operations that are precisely specified independent of any particular implementation. It is also known as ADT.

List ADT

A list is a sequential data structure, ie. a collection of items accessible one after another beginning at the head and ending at the tail.

  • It is a widely used data structure for applications which do not need random access
  • Addition and removals can be made at any position in the list
  • lists are normally in the form of a1,a2,a3.....an. The size of this list is n.The first element of the list is a1,and the last element is an.The position of element ai in a list is i.
  • List of size 0 is called as null list.

Basic Operations on a List

  • Creating a list
  • Traversing the list
  • Inserting an item in the list
  • Deleting an item from the list
  • Concatenating two lists into one

Implementationof List:
A list can be implemented in two ways

  1. Array list
  2. Linked list

3.2.1. Array Implementation of List

  • This implementation stores the list in an array.
  • The position of each element is given by an index from 0 to n-1, where n is the number of elements.
  • The element with the index can be accessed in constant time (ie) the time to access does not depend on the size of the list.
  • The time taken to add an element at the end of the list does not depend on the size of the list. But the time taken to add an element at any other point in the list depends on the size of the list because the subsequent elements must be shifted to next index value.So the additions near the start of the list take longer time than the additions near the middle or end.
  • Similarly when an element is removed,subsequent elements must be shifted to the previous index value. So removals near the start of the list take longer time than removals near the middle or end of the list.

Problems with Array implementation of lists

  • Insertion and deletion are expensive. For example, inserting at position 0 (a new first element) requires first pushing the entire array down one spot to make room, whereas deleting the first element requires shifting all the elements in the list up one, so the worst case of these operations is O(n).
  • Even if the array is dynamically allocated, an estimate of the maximum size of the list is required. Usually this requires a high over-estimate, which wastes considerable space. This could be a serious limitation, if there are many lists of unknown size.
  • Simple arrays are generally not used to implement lists. Because the running time for insertion and deletion is so slow and the list size must be known in advance

3.2.2. Linked list implementation

A Linked list is a chain of structs or records called Nodes. Each node has at least two members, one of which points to the next Node in the list and the other holds the data. These are defined as Single Linked Lists because they can only point to the next Node in the list but not to the previous.

The list can be made just as long as required. It does not waste memory space because successive elements are connected by pointers. The position of each element is given by an index from 0 to n-1, where n is the number of elements. The time taken to access an element with an index depends on the index because each element of the list must be traversed until the required index is found. The time taken to add an element at any point in the list does not depend on the size of the list, as no shifts are required Additions and deletion near the end of the list take longer than additions near the middle or start of the list. because the list must be traversed until the required index is found.

Types of Linked List

Singly Linked List

Doubly Linked List

Circular Linked List

Operation on Linked List(List ADT)

1.is_last()

intis_last( position p, LIST L )

{

return( p->next == NULL );

}

This procedure is used to check whether the position p is an end of the linked list L

2. Isempty()

intis_empty( LIST L )

{

return( L->next == NULL );

}

This is used to check whether the linked list is empty or not. If the header of linked list is NULL then return TRUE otherwise return FALSE.

3.Insert()

void insert( element_type x, LIST L, position p )

{

positiontmp_cell;

tmp_cell = (position) malloc(sizeof (struct node) );

tmp_cell->element = x;

tmp_cell->next = p->next;

p->next = tmp_cell;

}

This procedure is used to insert an element x at the position p in the linked list L. This is done by

Create a new node as tmpcell

Assign the value x in the data filed of tmpcell

Identify the position p and assign the address of next cell of p to the pointer filed of tmpcell

Assign the address of tmpcell to the address filed of p

4. Delete()

void delete( element_type x, LIST L )

{

position p, tmp_cell;

p = find_previous( x, L );

if( p->next != NULL )

{

tmp_cell = p->next;

p->next = tmp_cell->next;

free(tmp_cell );

}}

This is used to delete an element x from the linked list L. This is done by

Identify the element x in the linked list L using findpreviuos() function

Name the node x as tmpcell

Assign the address of next cell of x to the previous cell.

Remove the node x

5.Find()

position find ( element_type x, LIST L )

{

position p;

p = L->next;

while( (p != NULL) & (p->element != x) )

p = p->next;

return p;

}

This is used to check whether the element x is present in the linked list L or not. This is done by searching an element x from the beginning of the linked list. If it is matched then return TRUE, else move the next node and continue this process until the end of the linked list. If an element is matched with any of the node then return FALSE.

3.2.3. Cursor based Linked List Implementation

Many languages, such as BASIC and FORTRAN, do not support pointers. If linked lists are required and pointers are not available, then an alternate implementation must be used. The alternate method we will describe is known as a cursor implementation.

The two important items present in a pointer implementation of linked lists are

1. The data is stored in a collection of structures. Each structure contains the data and a pointer to the next structure.

2. A new structure can be obtained from the system's global memory by a call to malloc and released by a call to free.

Figure : Example of a cursor implementation of linked lists

Operation on Linked List

1.is_last()

intis_last( position p, LIST L) /* using a header node */

{

return( CURSOR_SPACE[p].next == 0

}

This procedure is used to check whether the position p is an end of the linked list L

2. Isempty()

intis_empty( LIST L ) /* using a header node */

{

return( CURSOR_SPACE[L].next == 0

}

This is used to check whether the linked list is empty or not. If the header of linked list is NULL then return TRUE otherwise return FALSE.

3.Insert()

void insert( element_type x, LIST L, position p )

{

positiontmp_cell;

tmp_cell = cursor_alloc( );

if(tmp_cell ==0 )

fatal_error("Out of space!!!");

else

{

CURSOR_SPACE[tmp_cell].element = x;

CURSOR_SPACE[tmp_cell].next = CURSOR_SPACE[p].next;

CURSOR_SPACE[p].next = tmp_cell;

}

}

This procedure is used to insert an element x at the position p in the linked list L. This is done by

Create a new node as tmpcell

Assign the value x in the data filed of tmpcell

Identify the position p and assign the address of next cell of p to the pointer filed of tmpcell

Assign the address of tmpcell to the address filed of p

4. Delete()

void delete( element_type x, LIST L )

{

position p, tmp_cell;

p = find_previous( x, L );

if( !is_last( p, L) )

{

tmp_cell = CURSOR_SPACE[p].next;

CURSOR_SPACE[p].next = CURSOR_SPACE[tmp_cell].next;

cursor_free(tmp_cell );

}

}

This is used to delete an element x from the linked list L. This is done by

Identify the element x in the linked list L using findpreviuos() function

Name the node x as tmpcell

Assign the address of next cell of x to the previous cell.

Remove the node x

5.Find()

position find( element_type x, LIST L) /* using a header node */

{

position p;

CURSOR_SPACE[L].next;

while( p & CURSOR_SPACE[p].element != x )

p = CURSOR_SPACE[p].next;

return p;

}

This is used to check whether the element x is present in the linked list L or not. This is done by searching an element x from the beginning of the linked list. If it is matched then return TRUE, else move the next node and continue this process until the end of the linked list. If an element is matched with any of the node then return FALSE.

3.2.4. Double linked list implementation

A doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.

Operations on double linked list

1. Insert()

void insert( element_type B, LIST L, position p )

{

positionnewnode,temp;

newnode = (position) malloc( sizeof (struct node) );

newnode->element = B;

p->next=newnode;

temp=p->next;

temp->prev=newnode;

newnode->prev=p;

newnode->next=temp->prev;

}

This procedure is used to insert an element x after the node p in the doubly linked list. This is done by,

Create a new node and assign the value x into the data field of new node.

Rearrange the pointers by assigning the address of x to the pointer field of p and vice versa

Assigning the address of next cell of p to the address filed of x and vice versa

2.Delete()

void delete( element_type B, LIST L)

{

positionnewnode,temp;

newnode=findprevious(B,L);

temp=newnode->next;

newnode->prev=temp->next;

temp->next->prev=newnode;

}

This is used to remove a node B from the doubly linked list. Removing a node from the middle requires that the preceding node skips over the node being removed, and the following node to skip over in the reverse direction.

3.2.5. Circular Linked List

A linked list have a beginning node and an ending node: the beginning node was a node pointed to by a special pointer called head and the end of the list was denoted by a special node which had a NULL pointer in its next pointer field. If a problem requires that operations need to be performed on nodes in a linked list and it is not important that the list have special nodes indicating the front and rear of the list, then this problem should be solved using a circular linked list. A singly linked circular list is a linked list where the last node in the list points to the first node in the list. A circular list does not contain NULL pointers.

3.3. Stack ADT

A stack is a list with the restriction that inserts and deletes can be performed in only one position, namely the end of the list called the top. The fundamental operations on a stack are push, which is equivalent to an insert, and pop, which deletes the most recently inserted element. It is also called Last In First Out (LIFO)

Implementation of Stacks

Linked List Implementation of Stacks

Array Implementation of Stacks

3.3.1. Linked List Implementation of Stacks

Stack data structure can be implemented using linked list. All thyeinsertion(push) and deletion operation(pop) can be performed in LIFO(Last In First Out) manner. Here, the elements can be inserted up to the size of storage space. The operations can be performed under stack is push(), pop() and top().

(i) push():

This is the function which is for insertion(pushing)of an element into stack. It is similar to the insertion of an element at the beginning of a single linked list. The steps to be followed,

  • Get the element to be inserted
  • Create a new cell to store the new element using malloc()
  • If the linked list is empty, then insert the new element as the first cell of the linked list and assign the address the new cell to NULL
  • Otherwise, insert the new cell in the first of linked list by rearranging the pointers

void push( element_type x, STACK S )

Top View