Make your own free website on Tripod.com

Site Built By Uday CSE

pink_flower_divider_md_wht.gif

C&DS MATERIAL
Home | Things To Remember | AHCET | Sports | Hardware | EDC Material | EDC Part-2 | C&DS MATERIAL | Contact Information

DATA STRUCTURES

                                                                                                           

     Data structure is the concept in which we can discuss about data & its storage activities.

  Data storage deals with the following concept.

 

  1.How the data is stored or retrieved ?

  2.How the data of different locations are linked?

  3.How the data is accessed by using those links.

     It deals with data & links the address of another data .

     Data structure concept is used to store set of records ,with different kinds of links .

     A concept in data structure is known as node.

 

 

NODE:- Node is a collection of variable & pointer.

          Variables are used to hold some data.

          Pointers are used to hold some links.

Nodes can be used to store data and links.

This concept will be mainly used in files , system programming & compiler designing.

 

Advantages of data structures.

 

0.    Data storage analysis.

1.      Supports DMA & allocates memory during the run time of program.

2.    It can be extended based on end users requirement.

3.    Elements can be inserted & deleted.

4.    Unwanted memory can be discarded .

5.    Used  in compiler designing  concepts .

6.    Used in evaluation of mathematical  expressions.

 

There are two types of data structures.

1.Linear.

2.Nonlinear.

 

Linear DS:

        It allocates memory dynamically & elements can be accessed sequentially.

        It may use LIFO or FIFO or both methods for linking items.

 

     Stack –LIFO – Last In First Out.

     Queue –FIFO – First In First Out , linked list are coming  under linear DS.

a.     Single linked list .

b.     Double linked list .

c.     Single circular linked list .

d.     Double circular linked list.

 

 

 

 

 

Non linear DS:

It allocates memory dynamically  & elements can be accessed hirearchically

a.     Trees .

Linear  DS

        There are two ways to develop DS.

1.      Stack concept( LIFO ) .

2.    Queue concept( FIFO ).

Stack

  The data item , entered at last will co me out as first item.

  It displays just reverse order of input data , just like tea tray.

  A variable is used to maintain the top position of stack.

  Using this variable , we can add & remove data back.

  When stack is empty the top element is –1 ( i.e TOP == - 1).

 

PUSH-is a function to push/add the data stack .

        When stack is empty and we try to insert  new element into stack we have to check over flow .

        When stack is empty and we try to perform operation we have to check under flow.

POP-is a function to delete data from stack.

 

APPLICATION OF STACK:

 

A stack can be used for the following  purposes:

1.It can be used for function calls . For example , suppose x function calls function y and passes two variables to a & b. Then the function x can store these two variables on the stack ,from where the function y can retrieve and use them.

2.Recursion .

3.A stack can be used to implement a calculator , by storing the operands & operators on the stack & use them as when required .

 

2.Recursion :

     When a called function in turn calls another function a process of ‘chaining occurs’.

     Recursion is a special case of this process , where a function calls itself.

Example:

       

        Factorial(n)

        int n;

        {

                int fact;

                if(n==1)

                        return(1);

                else

                        fact=n*factorial(n-1);

                return(fact);

        }

 

 

       

 

 

 

 

Stacks can be implemented  in two ways using .

1.Arrays.

2.Linked list.

                                                                                                         

 

QUEUE;

 

     The data item entered first will come out as first item.

     Two variables are used to maintain the front position , and rear position of the queue .

     Insert is a function to insert a data into queue .

     Remove is a function to delete / retrieve data from, queue.

 

Example . Like a QUEUE near a cinema theatre.

 

                                                       

 

 

 

CIRCULAR QUEUE:

     A list can also be circular  which is called as circular queue or a circular list.

     Instead of using a linear list ,a circular list is prefered .

     That is items in a circular list are arranged in circular form .

     A circular list does not have any starting or ending point ,so we have an advantage of starting from any point of the list.

     A circular QUEQE is as follows..

       

 

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        A circular queue.

Advantages of circular queue :

1. In the case of a circular queue , the last element points back to the first element of the queue.

So no null pointer is required .

2.Every node as a predecessor , thus there is no special requirement of a ‘first’ node.

 

 

CONCEPTS OF LINKED LIST:

v    List refers to a set of items organized  sequentially .

v    An array is an example of list .

v    In an array , the sequential organization is provided implicitly by its index .

v    We use the index for accessing & manipulating array elements .

v    One major problem with the array is that the size of an array must be specified precisely at the beginning of the program .

v    As pointed out practical applications .

v    A completely different way to represent list to make each item in the list part of a structure that also contains “a link” to the structure containing the next item as shown in the following figure ,this type of list is called a linked a linked list because it is a link whose order is given by links from one item to other/next.

v    Concepts of linked list ..

v    Node: each structure of list is called as node and it consists of two parts.

        A different to represent a list is to make each item in part of a structure that also contains a “link” to the structure containing the next item.

        As shown….

 

                                                                                                                                                                                                                                                                                                                                                                           Each structure of the list is called the node and consists of two fields ,one containing  the item, and the other containing the address of the next item in the list .

        A linked list is a collection of structures ordered not by their physical placement in memory but by their logical links.

        These logical links are stored as part of the data in the structure itself.

        Example of a structure representation….

Structure node

{

int item;

struct node *next;

};

 

        A structure which contain a member field that that points to the same structure type are called self referential structures.
                    Structure tg-name

{

float age;

struct link_list *next;

};

        The structure may contain more than one item with different data types.

        However , one of the items must be a pointer of the type tag-name.

       

Linked list with header node.:

 

Header node is the node which holds the related  information of linked list .

Ex:-

                Number of nodes e. t. c.

Header nodes link part will hold address of first node in the list.

       

10                               

        Header node    

P                             

 

 

 

                                               

        40

        30

P                             

 

 

 

 

    

 

 

       TREES

It is a collection of nodes .

A tree is represented as follows ..

7

6

5

4

3

20

10

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Here 4 & 5 are siblings of                                                                                          2 , similarly 6 & 7 are siblings                                                                                     of 3.                                                                                                                                                                                                                                                                                

 

                        Here 2,4,5 are left sub tree.             

                        3,6,7 are right sub tree .   

                and 4,5,6,7 are descendents of 1.

Binary tree:-

v    A node can have only less than two nodes.

v    Strictly binary :-

v    It should have not empty left and right sub tree.

As shown…

 

 

 

 

0

0

0

0

0

0

                                                                                                                                                                                                                                                                                                                                                                                               

 

This is  strictly binary tree                                  not strictly binary tree     

 

 

 

 

Tree traversal :

Passing through each & every node is called as tree traversal . There     are three types of tree traversal

        1.preorder traversal .

        2.post order traversal &

        3.inorder traversal.

 

 

 

 

 

 

 

 

 

 

 

 

Preorder traversal :

1.visit root node .

2.visit left sub tree .

3.visit right sub tree .

B0

A                0

+0

+AB is pre order traversal    for this tree.

 

 

 

+0

Post order traversal: 

1.visit left sub tree .                                                                   AB+ is post

B0

A0

2.visit right sub tree .                                                                 order traversal

3.visit root node .                                                                              

 

 

 

 

+0

In order traversal:

.visit root node .                                                                 A+B  is in order

2.visit left sub tree .                                                                  traversal.

B0

A0

3.visit right sub tree

 

 

 

 

 

                                                                                       

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Material Prepared By (Srikanth E.I.E  3rd Year)

AL HABEEB COLLEGE OF ENGINEERING AND TECHNOLOGY