Overview

The different models used to organize data in the main memory are collectively referred to as data structure, where as the different models used to organize data in the secondary memory are collectively referred to as file structures.

BASIC TERMINOLOGY OF DATA STRUCTURE

1. Data:
The term data simply refers to a value or set of values.
2. Data item:
A data item refers to a single unit of values.
3. Entity:
An entity is something that has certain attributes or properties which may be assigned values.
4. Entity set:
An entity set is a collection of similar entities.
5. Record:
A record is a collection of related records.
6. File:
A file is a collection of related records.
7. Key:
A key is a data item in a record that takes unique values and can be used to distinguish a record from other records.
8. Information:
information is a processed data.

DATA STRUCTURED DEFINED

A data structure is a logical model of a particular organization of data. The choice of a particular data structure depends on the following consideration:

1. It must be able to represent the inherent relationship of the data in the real world.
2. It must be simple enough so that it can process efficiently as and when necessary.

The various data structures are divided into the following categories:

1. Linear data structure:
a data structure whose elements from a sequence, and every element in the structure has a unique predecessor and unique successor. Like arrays, linked list, stack and queues.
2. Non-Linear data structure:
a data structure whose elements do not form a sequence, there is no unique predecessor and unique successor. Like tree & graph.

COMMON OPERATION ON DATA STRUCTURE

The various operations that can be performed on different data structure are described below:

1. Traversal:
Accessing each element exactly once in order to process it. This operation is called visiting the element.
2. Searching:
Finding the location of a given element
3. Insertion:
Adding a new element to the structure.
4. Deletion:
Removing a existing element from the structure.
5. Sorting:
Arranging the elements in some logical order. This logical order may be ascending or descending in case of numeric key and dictionary order in alphanumeric key.
6. Merging:
Combining the elements of two similar ted structures into a single structure.

BASIC CONCEPT OF C PROGRAMMING

In C Programming language some toppic is very important in Data Structure & Algorithm:

1. Enumerated Data Type:
2. Typedef:
3. Array:
4. User Defined Function:
5. Structure:
6. Pointer:
7. Recursion:
8. Dynamic Memeory Alloation:

Program design tools

The various program design tools:

1. Structure charts
2. Algorithms
3. Flowcharts
4. Decision tables
5. Pseudo codes
6. Coding the program

Introduction to algorithms

An algorithm is a finite set of steps defining the solution of a particular problem. An algorithm can be expressed in English like language, called pseudo code, in a programming language or in the form of flow chart.

Algorithm complexity

As an algorithm is a sequence of steps to solve a problem. Algorithm depends on following considerations:

1. Performance requirement i.e., time complexity
2. Memory requirement i.e., space complexity
3. Programming requirements

Performance requirements are usually more critical than memory requirements; in general it is not necessary to worry about memory faster than performance requirements. Algorithms are analyzed only on the basis of performance requirements i.e. running-time efficiency.

BIG Oh Notation

There is an important theorem in literature, which states that if
F(n)=a_mn^m+ a_m-1n^m-1+…..+ a₂n²+ a₁n+a₀ and a_m>0
Then f(n)=O(n^m)

Categories of Algorithm

1. Constant time(O(1)) algorithm
2. Logarithmic time(O(logn)) algorithm
3. Linear time(O(n)) algorithm
4. Polynomial time(O(n^k), for k>1) algorithm
5. Exponential time (O(Kⁿ), for k>1) algorithm

Limitation of Big Oh Notation

1. It contains no consideration of programming effort
2. It masks potential important constants

Linked List

A linked list is a linear collection of data elements, called nodes. The linear order is given by pointer. Each node is divided into two or more parts. A linked list can be of the following types:

1. Linear linked list or one-way list
2. Doubly linked list or two way lists
3. Circular linked list
4. Header linked list

LINEAR LINKED LIST

In a linear linked list, also called singly linked list or one-way list, each node is divided in two parts:

1. First part contains the information of the elements, and
2. Second part, called the link field or nextpointer field, contains the address of the next node in the list.

Representation of linear linked list

typedef struct nodeType
{
	int info;
	struct nodeType *next;
}node ;
node *head;

Operation on Linear Linked List

Create an Empty List

The variable head is declared as pointer to a node data type. This variable is used to point to the first element of the list. Since the list will be empty in the beginning, the variable head is assigned a NULL (sentinel value) to indicate that list is empty

Void createEmptyList(node **head)
{
	*head=NULL;
}
                                            

Inserting an element

To insert an element in the list, the first task is to get a new node, assign the element to be inserted to the info field of the node, and then new node is placed at the appropriate position by adjusting the appropriate pointer. The insertion in the list can take place at the following position:

1. at beginning of the list
2. at end of the list
3. after a given element

Inserting at the Beginning of the List

Insert an element at the beginning of the list, first we test whether the linked list is initially empty. If yes, then the element is inserted as the first and only element of the list by performing the following steps:

1. Assign NULL value to the next pointer field of the new node
2. Assign address of the new node to head

However, if the list is initially not empty, then the element is inserted as the first element of the list by performing the following steps:

1. Assign value of the head variable (the address of the first element of the existing list) to the next pointer field of the new node.
2. Assign address of the new node to head

void insertAtBegenning(node **head, int item)
{
	node *ptr;
    ptr=(node*)malloc(sizeof(node));
    ptr->info=item;
    if(*head==NULL)
	    Ptr->next=NULL;
    else
    ptr->next=*head;
    *head=ptr;
}
                                            

Inserting at the End of the List

To insert the element at the end of the list, first we test whether the linked list is initially empty. If yes, then the element is inserted as the first and only element of the list by performing the following steps:

1. Assign NULL value to the next pointer field of the new node
2. Assign address of the new node to head

However, if the list is initially not empty, then the list is traversed to reach the last element, and then the element is inserted as the last element of the list by performing the following steps.

1. Assign NULL, value to the next pointer field of the new node.
2. Assign address of the new node to next pointer field of the last node.

void insert AtEnd (node **head, int item)
{
    node *ptr,*loc;
    ptr= (node*) malloc( sizeof( node ));
    ptr->info = item;
    ptr->next=  NULL;
    if(*head == NULL) /* list initially empty */
        *head= ptr;
    else 
    {
        loc =*head;
        while (loc->next != NULL)
            loc = loc->next;
        loc->next = ptr;
    }
}
                                            

Inserting after the Given Element of the List

To insert the new element after the given element first we find the location. say loc, of the given clement in the list, and then the element is inserted in the list by performing the following steps:

1. Assign the next pointer field of the node pointed by loc to the next pointer field of the new node.
2. Assign address of the new node to the next pointer field of the node pointed by loc.

Void insertAftertElement(node *head, int item, int after)
{
	node *ptr, *loc;
    loc=search(head,after);
    If(loc==(node *)NULL)
	    return;
    Ptr=(node*)malloc(sizeof(node));
    Ptr->info=item;
    Ptr->next= loc->next;
    loc->next =ptr;
}
                                                

Traversing a list

Linear linked list can be traversed in two ways. These are

1. In-order traversal
2. Reverse-order traversal

In-order Traversal

To traverse the linear linked list, we move along the pointer, and process each element till we reach the last element.The following listing shows the various steps required.

Void traverseInorder1(node *head)
{
	While(head != NULL)
    {
	    printf(“%d\n”, head->info);
	    Head=head->next;
    }
}                                           

reverse-order Traversal

To traverse the linear linked list, we move last element to first element.The following listing shows the various steps required.

                                                
void traverseInReverseOrder2(node *head){
	if(head->next!=NULL)	
		traverseInReverseOrder2(head->next);
	printf(“%d\n”,head->info);
}

Doubly Linked List

In a Doubly Linked List, also called two-way list, each node is divided into three parts:

1. The first Part, called previouspointer field, contains the address of the preceding element in the list.
2. The second part, contains the information of the element,
3. The third Part, called nextpointer field, contains the address of the succeeding element in the list.

Representation of Doubly linked list

typedef struct nodetype{
    struct nodetype *prev;
    int info;
    struct nodetype *next;
}node;
node *head,*tail;

Operation on Doubly Linked List

Create an Empty List

The list will be empty in the beginning, the variable head and tail are assigned NULL value.

Void createEmptyList(node**head, node **tail)
{
	*head=*tail=NULL;
}

                                            

Traversing a list

Doubly linked list can be traversed in two ways. These are

1. In-order traversal
2. Reverse-order traversal

In-order Traversal

To traverse the linear linked list, we move along the pointer, and process each element till we reach the last element.The following listing shows the various steps required.

void traverseinorder(node *head)
{
	while(head!=null){
		printf(“%d”, head->info);
		head=head->next;
    }
}
                                      

reverse-order Traversal

To traverse the linear linked list, we move last element to first element.The following listing shows the various steps required.

                                                
void traverseinreverseorder(node *tail)
{
	while(tail!=null)
	{
		printf(“%d”, tail->info);
		tail=tail->prev;
    }
}

Searching an element

In searching we traverse in list in any order and search position specified information of list

node * search(node *head, int item){
    while(head!=null){
		if(head->info==item)
			return head;
		head=head->next;
    }
    return NULL;
}

                                            

Inserting an element

To insert an element in the list, the first task is to get a new node, assign the element to be inserted to the info field of the node, and then new node is placed at the appropriate position by adjusting the appropriate pointer. The insertion in the list can take place at the following position:

1. at beginning of the list
2. at end of the list
3. after a given element

Inserting at the Beginning of the List

Insert an element at the beginning of the list, first we test whether the linked list is initially empty. If yes, then the element is inserted as the first and only element of the list by performing the following steps:

1. Assign NULL value to the next pointer field of the new node
2. Assign address of the new node to head

However, if the list is initially not empty, then the element is inserted as the first element of the list by performing the following steps:

1. Assign value of the head variable (the address of the first element of the existing list) to the next pointer field of the new node.
2. Assign address of the new node to head

void insertAtBegenning(node **head, int item)
{
	node *ptr;
    ptr=(node*)malloc(sizeof(node));
    ptr->info=item;
    if(*head==NULL)
	    Ptr->next=NULL;
    else
    ptr->next=*head;
    *head=ptr;
}
                                            

Inserting at the End of the List

To insert the element at the end of the list, first we test whether the linked list is initially empty. If yes, then the element is inserted as the first and only element of the list by performing the following steps:

1. Assign NULL value to the next pointer field of the new node
2. Assign address of the new node to head

However, if the list is initially not empty, then the list is traversed to reach the last element, and then the element is inserted as the last element of the list by performing the following steps.

1. Assign NULL, value to the next pointer field of the new node.
2. Assign address of the new node to next pointer field of the last node.

void insert AtEnd (node **head, int item)
{
    node *ptr,*loc;
    ptr= (node*) malloc( sizeof( node ));
    ptr->info = item;
    ptr->next=  NULL;
    if(*head == NULL) /* list initially empty */
        *head= ptr;
    else 
    {
        loc =*head;
        while (loc->next != NULL)
            loc = loc->next;
        loc->next = ptr;
    }
}
                                            

Inserting after the Given Element of the List

To insert the new element after the given element first we find the location. say loc, of the given clement in the list, and then the element is inserted in the list by performing the following steps:

1. Assign the next pointer field of the node pointed by loc to the next pointer field of the new node.
2. Assign address of the new node to the next pointer field of the node pointed by loc.

Void insertAftertElement(node *head, int item, int after)
{
	node *ptr, *loc;
    loc=search(head,after);
    If(loc==(node *)NULL)
	    return;
    Ptr=(node*)malloc(sizeof(node));
    Ptr->info=item;
    Ptr->next= loc->next;
    loc->next =ptr;
}
                                                

Stack

A stack, also called Last-In-First-Out(LIFO) System, is a linear list in which insertions(PUSH) and deletions(POP) can take place only at one end called the TOP. Example- Stack of tray

Operation on stacks

1. CreateStack(s) – to create s as an empty stack.
2. Push(s,i) – to push element I onto stack s.
3. Pop(s) – to access and remove the top element of the stack s.
4. Peek(s) – to access the top element of the stack s.
5. IsFull(s) – to check whether the stack s is empty.
6. IsEmpty(s) – to check whether the stack s is empty.

All of these operation runs O(1) time.

Representing a stack using an array

#define MAX 10
Typedef struct{	
	int top;
	int elements[MAX];
}stack;
stack s;

Operation on Stack using Array

Creating an Empty Stack using an array

The list will be empty in the beginning, the variable head and tail are assigned NULL value.

void createStack(stack *ps)
{
	Ps->top=-1;	

}
                                            

Testing Stack for Underflow

boolean isEmpty(stack *ps)
{
	if(ps->top==-1)
		return true;
	else
		return false;
}

Testing Stack for Overflow

                                                
boolean isFull(stack *ps)
{
	if(ps->top==(MAX-1))
		return true;
	else
		return false;
}

Push operation

void push (stack *ps , int value)
{
	ps->top++;
	ps->elements[ps->top]=value;
}
                                        

Pop operation

void pop (stack *ps)
{
	int temp;
	temp=ps->elements[ps->top];
	ps->top--;
	return temp;
}
                                            

Accessing Top Elements

int peek(stack *ps)
{
	return(ps->elements[ps->top]);
}
                                                

Representing a stack using Linked list

Typedef struct nodeType
{	
	int info;
	struct nodeType *next;
}stack;
stack *top;

Operation on Stack using Linked list

Creating an Empty Stack using Linked list

void createStack(stack **top)
{
	*top=NULL;	

}
                                       

Testing Stack for Underflow

boolean isEmpty(stack *top)
{
	if(top==NULL)
		return true;
	else
		return false;
}

Push operation

void push (stack **top , int value)
{	Stack *ptr;
         Ptr=(stack *)malloc(sizeof(stack));
         If(ptr=NULL)
          {         Printf(“\nunable to allocate memory”);
                    Printf(“\npress any key to exit…….”);
                    Getch();
                    Return;
           }         
	Ptr->info=value;
         Ptr->next=*top;
         *top=ptr;
}
                                  

Pop operation

void pop (stack **top)
{
	int temp;
         stack *ptr;
	temp=(*top)->info;
         ptr=*top;
         *top=(*top)->next;
	Free(ptr);
	return temp;
}
                                    

Accessing Top Elements

int peek(stack *top)
{
	return(top->info);
}
                                           

Disposing Stack using Linked List

Void disposeStack(stack **top)
{
	stack *ptr;
    while(*top!=NULL)
    {
        ptr=*top;
        *top=(*top)->next;
        free(ptr);
    }
}                                          

Queue

A queue is a line of person waiting for their turn at some service counter/window. Service counter is provided on the First-Come-First-Serve (FCFS) basis.

In context of data structure, a queue is a linear list in which insertion can take place at one end of the list, called the rear of the list and deletion can take place only at other end, called the front of the list. The behavior of a queue is like a First-In-First-Out (FIFO) System.

Operation on Queue

The following operations are performed on queues:
1. CreateQueue (q):
to create q as an empty queue.
2. Enqueue (q,i):
to insert(add) element I in a queue.
3. Dequeue (q):
to access and remove an element of a queue q.
4. Peek (q):
to access the first element of the queue q without removing it.
5. IsFull (q):
to check whether the queue q is full.
6. IsEmpty (q):
to check whether the queue q is empty.

All of these operation runs O(1) time.

Representing a Queue using an array

#define CAPACITY 10
typedef struct{	
	int front, rear;
	int elements[CAPACITY];
}queue;
queue q;

Operation on Queue using Array

Creating an Empty Linear Queue Using Array

As the index of array elements can take any value in the range 0 to CAPACITY-1, the purpose of initializing the queue is served by assigning value -1(sentinel value) to front and rear variables.

Void createQueue(queue *pq)
{
     Pq->front=pq->rear=-1;
}
                                            

Testing a Linear Queue For Underflow

Before we remove an element from queue, it is necessary to test whether a queue still have some elements.

boolean isEmpty(queue *pq)
{
     If(pq->front==-1)
         return true;
     else
         return false;

}

Testing a Linear Queue for overflow

Before we start a new element in a queue, test whether the queue is full or not. If it is not full then the enqueue operation can be performed to insert the element at rear end of the queue.

                                                
Boolean isFull(queue *pq)
{
	If((pq->front==0)&&(pq->rear==CAPACITY-1))
		Return true;
	else
		Return false;
}

Enqueue operation on Linear Queue

There are two conditions, which can occur, even if the queue is not full. These are:

1. If a linear queue is empty, then the value of the front and rear variables will be NIL(sentinel value), then both front and rear are set to 0.
2. If a linear queue is not empty, then there are further two possibilities:
   1. If the value of the rear variable is less than CAPACITY-1, then the rear variable is incremented.
   2. If the value of the rear variable is equal to CAPACITY-1, then the elements of the linear queue are moved forward, and the front and rear variables are adjusted accordingly.

void enqueue(queue *pq, int value){
int i;
If(isEmpty(pq))
		pq->front=pq->rear=0;
else if(pq->rear==CAPACITY-1)
{
		for(i=pq->front;i<=pq->rear;i++)
			pq->elements[i-pq->front]=pq->elements[i];
		pq->rear=pq->rear - pq->front+1;
		pq->front=0;
}
else
{
		pq->rear++;
}
pq->elements[pq->rear]=value;
}

Dequeue operation on Linear Queue

The front element of a linear queue is assigned to a local variable, which later on will be returned via the return statement. After assigning the front element of a linear queue to a local variable, the value of the front variable is modified so that it points to the new front.

There are two possibilities:
1. If only one element in a linear queue, then after dequeue operation queue will become empty. i.e. front and rear variable to -1(sentinel value).
2. Otherwise the value of the front variable is incremented.

Int dequeue(queue *pq){
	Int temp;
	Temp=pq->elements[pq->front];
	If(pq->front==pq->rear)
		pq->front=pq->rear=-1;
else
	pq->front++;
return temp;
}

Accessing Front Element on Linear Queue

Int peek(queue *pq){
	Return(pq->elements[pq->front]);
}

Representing a queue using Linked lis

typedef struct nodeType{
     int info;
     struct nodeType *next;
}node;
typedef struct{
     node *front;
     node *rear;
} queue;
queue q;

Operation on Queue using Linked list

Creating an Empty Linear Queue using Linked list

Void createQueue(queue *pq)
{
     Pq->front=pq->rear=NULL;
}
                                       

Testing a Linear Queue For Underflow using Linked list

boolean isEmpty(queue *pq)
{
     if(pq->front == NULL)
          return true;
     else
         return false;
}

Enqueue operation on Linear Queue using Linked List

void enqueue (queue *pq, int item)
{
node *ptr;
ptr= (node*) malloc( sizeof( node ));
ptr->info = item;
ptr->next=  NULL;
if(pq->rear== NULL) /* list initially empty */
pq->front=pq->rear=ptr;
else {
(pq->rear)->next=ptr;
pq->rear=ptr;
}
}

dequeue operation on Linear Queue using Linked List

int dequeue(queue *pq)
{
	int temp;
node *ptr;
temp=(pq->front)->info;
ptr=pq->front;
if(pq->front==pq->rear)
pq->front=pq->rear = NULL;
else
	pq->front = (pq->front) ->next;
free(ptr);
return temp;	
}

Accessing Front Element on Linear Queue using Linked List

int peek(queue *pq)
{
	return ((pq->front)->info);
}

                                           

Disposing Queue on Linear Queue using Linked List

void disposeQueue (queue *pq){
node  *ptr;
while(pq->front != NULL){
ptr=pq->front;
pq->front =( pq->front)->next;
free (ptr);
}
Pq->rear = (node *)NULL;
}
                                    

A (general) tree T is a finite nonempty set of elements. One of these elements is called the root, and the remaining elements, if any, are partitioned into trees, which are called the sub-tree of T.

TREE TERMINOLOGY

1. Level of elements:
The root of tree is at level 1;its children, if any, are at level 2, their children at level 3 and so on.
2. Degree of Elements
number of children of its element
3. Degree of Tree:
maximum of its children degree
4. Height of a Tree:
maximum level of tree

BINARY TREES

A binary tree T is either empty or has a finite collection of elements. When the binary tree is not empty, one of its elements is called the root and the remaining elements, if any, are portioned into two binary trees, which are called the left & right sub tree of T.

Some Properties of Binary Trees

• Property 1:
A binary tree with n elements, n>0 has exactly n-1 edges.
• Property 2:
A binary tree of height h, h>0, has at least h and at most 2h-1 elements in it.
• Property 3:
A height of the binary tree that contains n elements, n>=0, has at least [log2(n+1)] and at most n elements in it.
• Property 4:
Let I, 1 <= I <= n, be the number assigned to an elements of a complete binary tree. The following statements are true.
1. If i=1, then this element is the root of the binary tree. If i>1, then the parent of this element has been assigned the number[i/2]
2. If 2i>n, then this element has no left child. Otherwise its left child has been assigned the number 2i.
3. If 2i+1>n, then this element has no right child. Otherwise its right child has been assigned the number 2i+1.