Structures with functions
The main philosophy of c language is the use of functions . And therefore it is natural that c support the passing structure values as a functions . there are three methods are there for passing structutres as function arguments
->first method is passing each member of structure as artual argument . if structure have more members means itssome what complex
->second copy rhe original structure send it to called function if u do any modification its wont reflect on original structure .
->third one is emploalled pointers a concept called pointers in which we send address of a structure . this is the most useful way compare secon one
Advantages of Structures:
Structures is a more meaning ful way to organize the complex data in a more meaningful way . it is the powerful concept that we may often use in our program design
TypeDef :
Unoins:
Unions a re defined and declared in the same fashion as structures . How ever the major distinction is interms of storage in structures each term has its own storage locationa .where as the all the members of union use th same memory location
Union can be declared using union keyword
Union poduct
{
Int m;
Float x;
Char c;
}code;
Its contain three value eventhough we use one data item at a time .
Ex : code.m =100;
Code.x =102.10;
Printf(“%d” ,shows error);
Unions may declare at the time of declaration like structures . it can be with only one value of same type as first union member
Ex: union product code={100}//good
union product code={100.130}//error type mismatch
therefor compiler allocates piece of storage that is enough to largest variable of type in union
in product example float is the largest one that’s why its assign 4 bytes
Data Structures :
a data structure is a particular way of storing and organizing data in a computer so that it can be usedefficiently.[1][2]
Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasksDatastructures
1)linear
Linear ,linkedlist ,stacks ,queues
In linear datastucture values are arranged in a linear fashion . an array ,queue etc . in lineardata structure values are stored in sequential manner .
Nonlinear:
Opposite to liniar
Trees ,graphs ,tables ,sets
Single linkedlist:
in this types of linked list two success nodes of the linkedlist are linked each other in sequential linear manner .
Singlelinked list is a dynamic datastructure with the ability to expand and shrink and as the per the program requirement . the single linked list is easy and straight forward data structure as compare to other structure by changing the link position other types of linked lists such as circular diuble linked lists
The principal benefit of a linked list over a conventional array is that the list elements can easily be inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk. Linked lists allow insertion and removal of nodes at any point in the list, and can do so with a constant number of operations if the link previous to the link being added or removed is maintained during list traversal.
Singly linked lists contain nodes which have a data field as well as a next field, which points to the next node in the linked list.
The above structure is used to implement the linked list , in it number is variable entered and stored in a memory .the second number is pointed to the same structure .
struct node
{
int number;
int number;
Struct node *p;
};
The above structure is used to implement the linked list , in it number is variable entered and stored in a memory .the second number is pointed to the same structure .
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct slist
{
int data;
struct slist *next;
}*head,*root,*temp1,*temp,*del;
void intial();
void create();
void insert();
void display();
void delet();
void main()
{
int ch;
clrscr();
intial();
while(1)
{
printf("enter 1-create\n 2-insert\n 3-display\n,4-delet \n,5-exit\n");
scanf("%d",&ch);
switch(ch)
{
case 1:
create();
break;
case 2:
insert();
break;
case 3:
display();
break;
case 4:
delet();
break;
case 5:
exit(0);
}
}
}
void intial()
{
head=(struct slist *)malloc(sizeof(struct slist));
head->next=NULL;
}
void create()
{
if(head->next==NULL)
{
temp=(struct slist *)malloc(sizeof(struct slist));
scanf("%d",&temp->data);
head->next= temp;
temp->next=NULL;
}
else
{
temp1=(struct slist *)malloc(sizeof(struct slist));
scanf("%d",&temp1->data);
temp->next=temp1;
temp1->next=NULL;
temp=temp1;
}
}
void delet()
{
int d,i;
temp=head;
printf("enter pos of a ele u want to delete\n");
scanf("%d",&d);
for(i=1;i<d;i++)
temp=temp->next;
temp->next=temp->next->next;
}
void display()
{
temp=head;
if(temp->next==NULL)
{
printf("list is empty\n");
}
else
{
while(temp->next!=NULL)
{
printf("%d",temp->next->data);
temp=temp->next;
}
}
}
void insert()
{
inti,ch,d;
printf("printf enter which location u want to insert\n");
temp1=(struct slist *)malloc(sizeof(struct slist));
printf("1-first\n2-last\n3-anywhere");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("enter ele to be inserted \n");
scanf("%d",&temp1->data);
temp1->next=head->next;
head->next=temp1;
break;
case 2:
temp=head;
printf("enter ele to be inserted \n");
temp1=(struct slist *)malloc(sizeof(struct slist));
scanf("%d",&temp1->data);
temp1->next=NULL;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=temp1;
temp=temp1;
break;
case 3
temp=head;
printf("enter ele to be inserted \n");
temp1=(struct slist *)malloc(sizeof(struct slist));
scanf("%d",&temp1->data);
temp1->next=NULL;
printf("enter pos of a ele u want to delete\n");
scanf("%d",&d);
for(i=1;i<d;i++)
temp=temp->next;
temp1->next=temp->next;
temp->next=temp1;
temp=temp1;
break;
}
}
Doublelinked List
Doublelinked List
Doubly-linked list is a more sophisticated form of linked list data structure. Each node of the
list contain two references (or links) – one to the previous node and other to the next node. The
previous link of the first node and the next link of the last node points to NULL. In comparison
to singly-linked list, doubly-linked list requires handling of more pointers but less information
is required as one can use the previous links to observe the preceding element. It has a dynamic
size, which can be determined only at run time.
- struct node
- {
- int data;
- struct node *prev,*next;
- };
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next,*prev;
}*head,*cur,*t,*q;
void create();
void add();
void insert();
void del();
void delpos();
void create()
{
head=(struct node*)malloc(sizeof(struct node));
head->next=NULL;
head->prev=NULL;
}
void add()
{
cur=head;
while(cur->next!=NULL)
cur=cur->next;
t=(struct node*)malloc(sizeof(struct node));
printf("enter data");
scanf("%d",&t->data);
cur->next=t;
t->next=NULL;
t->prev=cur;
cur = t;
}
}
void insert()
{
int p,i;
printf("enter the position");
scanf("%d",&p);
cur=head;
for(i=1;i<p;i++)
cur=cur->next;
t=(struct node*)malloc(sizeof(struct node));
printf("enter data");
scanf("%d",&t->data);
//q=cur->next;
t->next=q;
q->prev=t;
cur->next=t;
t->prev=cur;
}
void del()
{
int d;
printf("enter data to delete");
scanf("%d",&d);
cur=head;
while(cur->next!=NULL)
{
if(cur->next->data==d)
{
t=cur->next;
cur->next=cur->next->next;
cur->next->prev=cur;
printf("deleted");
free(t);
}
else
cur=cur->next;
}
printf("no such data\n");
}
void delpos()
{
int p,i;
printf("enter the position");
scanf("%d",&p);
cur=head;
for(i=1;i<p;i++)
cur=cur->next->next;
t=cur->next;
cur->next=cur->next->next;
cur->next->prev=cur;
free(t);
printf("deleted\n");
}
void disp()
{
cur=head;
if(head->next==NULL)
{
printf("list is empty\n");
}
while(cur->next!=NULL)
{
printf("%d",cur->next->data);
cur = cur->next;
}
}
main()
{
int ch1;
create();
do
{
printf("1.add \n2.insert\n3.delete\n4.display\n5.exit\n");
printf("enter your choise");
scanf("%d",&ch1);
switch(ch1)
{
case 1:
add();
break;
case 2:
insert();
break;
case 3:
del();
break;
case 4:
disp();
break;
case 5:
exit(0);
}
}while(ch1<=5);
}
First and last elements of a circular list are adjacent .A linear single linked list can be circled by storing first node address in the last node address field .
void insert()
Circular list:
First and last elements of a circular list are adjacent .A linear single linked list can be circled by storing first node address in the last node address field .
In sll, dll we are at the last node and want to access first node . we are unable to access first node from last node in sll , dll .but its possible with cll
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
struct node
{
int data;
struct node *next;
}*head,*cur,*t;
void create();
void add();
void insert();
void del();
void delpos();
void disp();
void create()
{
head=(struct node*)malloc(sizeof(struct node));
head->next=head;
}
void add()
{
cur=head;
while(cur->next!=head)
{
cur=cur->next;
}
t=(struct node*)malloc(sizeof(struct node));
printf("enter data");
scanf("%d",&t->data);
cur->next=t;
t->next=head;
cur=t;
}
void insert()
{
int p,i;
printf("enter position to insert");
scanf("%d",&p);
cur=head;
for(i=1;i<p;i++)
cur=cur->next;
t=(struct node*)malloc(sizeof(struct node));
printf("enter data");
scanf("%d",&t->data);
t->next=cur->next;
cur->next=t;
}
void del()
{
int d;
printf("enter element to delete");
scanf("%d",&d);
cur=head;
while(cur->next!=head)
{
if(cur->next->data==d)
{
t=cur->next;
cur->next=cur->next->next;
printf("deleted");
free(t);
return;
}
else
cur=cur->next;
}
printf("no such data");
}
void delpos()
{
int p,i;
printf("enter position of data to delete");
scanf("%d",&p);
cur=head;
for(i=1;i<p;i++)
cur= cur->next;
t=cur->next;
cur->next=cur->next->next;
free(t);
printf("deleted");
}
void disp()
{
cur=head;
if(head->next==head)
{
printf("list is empty");
return;
}
while(cur->next!=head)
{
printf("%d\n",cur->next->data);
cur=cur->next;
}
}
void main()
{
int ch;
create();
while(1)
{
printf("\n 1.add\n 2.insert\n 3.delete\n 4.delete by position\n 5.display\n 6.exit\n");
printf("enter your choise");
scanf("%d",&ch);
switch(ch)
{
case 1:
add();
break;
case 2:
insert();
break;
case 3:
del();
break;
case 4:
delpos();
break;
case 5:
disp();
break;
case 6:
exit(0);
}
}
}
stacks
It is one of the linear data structure that is extensively used in programming languages . in stack we can insert , delete an elements from list ,which takes from one end that is called top . top which is variable of type int which points top most element of the stack .we can perform insertion ,deletion from top .
The insertion operation of an element onto the stack is called push .
The deletion operation of an element onto the stack is called pop .
The stack is also known as pushdown list .
Stack follows last-in-first-out ( LIFO ) principle that means element which is appended lastly is deleted first
Stack overfolw: if(top=maxsize-1) then stack overflow
Stack underflow : top==-1 then stack is underflow
Operations on stack is done by two ways , They are follows
1)stack implementation with an array.
2)Dynamic implementation with pointers . .
#include<stdio.h>
#define MAX 10
#include<stdlib.h>
int stack[MAX];
int top=-1;
int i;
main()
{
int ch;
while(1)
{
printf("\n 1-push \n 2-pop \n 3-display \n4-topmost\n 5-exit \n");
scanf("%d",&ch);
switch(ch)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
topmost();
break;
case 5:
exit(0);
}
}
}
void push()
{
int ele;
printf("enter ele u want to insert\n");
scanf("%d",&ele);
top++;
stack[top]=ele;
}
void display()
{
i=top;
if(top==-1)
printf("stack is empty\n");
while(i>-1)
{
printf("%d\n",stack[i]);
i--;
}
}
void pop()
{
int ele;
if(top==MAX-1)
{
printf("stack is overflow \n");
}
{
ele=stack[top];
top--;
printf("deleted ele is %d",ele);
}
}
void topmost()
{
if(top==-1)
{
printf("stack is underflow\n");
}
else
{
printf("top ele is %d",stack[top]);
}
}
Stack using linked list :
#include<stdio.h>
struct lstack
{
int data;
struct lstack *next;
}*top=0;
typedef struct lstack it;
void main()
{
int ch;
void push();
void pop();
void display();
while(1)
{
printf("\n enter option\n");
printf("\n1-push\n2-pop\n3-display\n4-topmost\n5-exit\n");
scanf("%d",&ch);
switch(ch)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 5:
exit(0);
}
}
}
void push()
{
it *node,*root;
node=(it *)malloc(sizeof(it));
printf("enter data\n");
scanf("%d",&node->data);
node->next=top;
top=node;
}
void pop()
{
it *temp;
if(top==0)
printf("stack is underflow\n");
else
{
temp=top;
top=top->next;
free(temp);
}
}
void display()
{
it *temp;
temp=top;
while(temp->next!=0)
{
printf("%d\n",temp->data);
temp=temp->next;
}
}
Application of stack:
Queue :
A queue is linear data structure and sub class of list data structure . in which elements are appended one end called rear end and elements deleted at other end called front .
Here front points currentstart of the queue . Rear points currentend of the queue
Queue follows the principle called (FIFO)first-in-first-out
One stimulate the real life situations with data structure . the theory of queue is common to all .we come across its application in every occupation . Queue of people in bank queue for tickets at railway station .
Queue operations can be implemented in two ways
1)static implementation (array)(size of array is decided before compilation)
2)dynamic implementation (pointers)
dynamic implementation (pointers)
#include<stdio.h>
#include<stdlib.h>
structlque
{
int data;
structlque *next;
}*front=NULL,*rear=NULL,*temp;
void main()
{
intch;
while(1)
{
printf("\n1-insert2-delet3-display4-exit\n");
scanf("%d",&ch);
switch(ch)
{
case 1:
insert();
break;
case 2:
delet();
break;
case 3:
display();
break;
case 4:
exit(0);
}
}
}
void insert()
{
temp=(structlque *)malloc(sizeof(structlque));
printf("enter data\n");
scanf("%d",&temp->data);
if(front==NULL)
{
front=rear=temp;
temp->next=NULL;
}
rear->next=temp;
temp->next=NULL;
rear=temp;
}
void delet()
{
int ele;
if(front==NULL)
printf("queue is underflow\n");
else
{
ele=front->data;
front=front->next;
printf("deleted eleis%d\n",ele);
}
}
void display()
{
temp=front;
while(temp!=rear)
{
printf("%d\n",temp->data);
temp=temp->next;
}
printf("%d\n",temp->data);
}
Application of stack:
- It is used in various expression conversion and evaluation - infix to post-fix or prefix evaluation.
- Stack is implicitly used by system while calling to sub routines function from main program.
- Recursion
- Stacks are used in tree traversal techniques.
· . Compilers use stacks in syntax analysis phase to check whether a particular in a program is syntactically correct or not.
Application of queue:
- Used by operating system in scheduling jobs and spooling (queue of print jobs)
- Disk I/O calls
- Queue is also part of the architecture of processors ex- 80386,8086
- In a computer network, different systems may request for same resource. In such a case resources requests are queue and serived one by one.
The operation of linear or straight-line queue is simple , but it has no of limitations . deletion of an element from the queue means creating vacant memory location ,which can not be reutilized .Even if memory locations are available due to deletion operations at the beginning of the queue , elements cannot be inserted
The circular queue overcome the limitations simple queue . a linear queue can be converted to circular from the lost node is connected to the first .
Like simple queue the circular queue also have front and rear ends. The rear and front ends is used know the status of the queue after inserting and deleting from the queue .
The circular queue overcome the limitations simple queue . a linear queue can be converted to circular from the lost node is connected to the first .
In C array c[3] lost position is attaching first position c[0] .
In the circular queue , the turn of the first element immediately after the last element
#include<stdio.h>
#define MAX 5
int cqueue[MAX];
int front=-1,rear=-1;
void insert();
void delete();
void display();
main()
{
int ch,val;
do
{
puts("1.insert\n2.delete\n3.display\n4.exit\nselect your choice");
scanf("%d",&ch)switch(ch)
{
case 1:insert();
break;
case 2:delete();
break;
case 3:display();
break;
case 4:exit(0);
}
}while(ch!=4);
}
void insert()
{
int num;
puts("enter data to be inserted");
scanf("%d",&num);
if(((front==0)&&(rear==MAX-1))||(front==rear+1))
{
puts("overflow");
return;
}
else if((front==-1)&&(rear==-1))
{
front=rear=0;
cqueue[rear]=num;
return;
}
else if((rear==MAX-1)&&(front!=0))
{
rear=0;
cqueue[rear]=num;
return;
}
else
{
rear++;
cqueue[rear]=num;
}
}
void delete()
{
int val;
if((front ==-1)&&(rear ==-1))
{
puts("underflow");
return;
}
val=cqueue[front];
printf("the deleted data is %d\n",val);
if(front==rear)
front=rear=-1;
else if(front==MAX-1)
front=0;
else
front++;
}
void display()
{
int i,p=rear,k=0;
if((front==-1)&&(rear==-1))
{
puts("underflow");
return;
}
for(i=front;i<MAX;i++)
{
printf("%d\t",cqueue[i]);
}
while((k<=p)&&(front!={
printf("%d\t",cqueue[k]);
k++;
}
}
Degree of tree :
Nonterminal Nodes :
Level number of a node :
Maximum and highest level number in the tree is Known as depth or height of a tree .
Parent Vs Child :
Edge:
A link between parent and child is known is known as edge
In-Degree :
Out-Degree :
Ancestors :
Descendant :
3)Post order traversal technic :
DEBFGCA
A graph consist of a set of nodes (or vertices ) and set of arcs (or edges ) . Each arc is specified by a pair of nodes .
Circular queue using linked list:
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
struct node
{
int data;
struct node *next;
}*head,cur,*t;
void create();
void add();
void insert(();
void del();
void delpos();
void disp();
void create()
{
head=(struct node*)malloc(sizeof(struct node));
head->next=head;
}
void add()
{
cur=head;
while(cur->next!=head)
cur=cur->next;
t=(struct node*)malloc(sizeof(struct node));
printf("enter data");
scanf("%d",&t->data);
cur->next=t;
t->next=head;
}
void insert()
{
intp,i;
printf("enter position to insert");
scanf("%d",&p);
cur=head;
for(i=1;i<p;i++)
cur=cur->next;
t=(struct node*)malloc(sizeof(struct node));
printf("enter data");
scanf("%d",&t->data);
t->next=cur->next;
cur->next=t;
}
void del()
{
int d;
printf("enter element to delete");
scanf("%d",&d);
cur=head;
while(cur->next!=head)
{
if(cur->next->data=d)
{
t=cur->next;
cur->next=cur->next->next;
printf("deleted");
free(t);
return;
}
else
cur=cur->next;
}
printf("no such data");
}
void delpos()
{
printf("enter position of data to delete");
scanf("%d",&p);
cur=head;
for(i=1;i<p;i++)
cur=cur->next;
t=cur->next;
cur->next=cur->next->next;
free(t);
printf("deleted");
}
void disp()
{
cur=head;
if(head->next==head)
{
printf("list is empty");
return;
}
while(cur->next!=head)
{
printf("%d",cur->next->data);
cur=cur->next;
}
}
printf("\n 1.add 2.insert 3.delete 4.delete by position 5.display 6.exit");
printf("enter your choise");
scanf("%d",&ch);
switch(ch)
{
case 1:
add();
break;
case 2:
insert();
break;
case 3:
del();
break;
case 4:
delpos();
break;
case 5:
disp();
break;
case 6:
exit(0);
}
while(ch<=5);
TREE:
A tree is finite set of nonempty set . the tree ‘T’ contains various elements among those one element is known as ROOT element . and other elements are treated as sub trees . A tree is a structure where each node contains none, one, or more pointers to child nodes
Define the following terms :
· Degree of the node :
· Degree of tree :
· Siblings :
· Terminal Nodes :
· Nonterminal Nodes :
· Level number of a node :
· Depth Or Height :
· Parent Vs Child :
· In-Degree :
· Out-Degree :
· Ancestors :
· Descendant :
Degree of the node :
The no of sub trees of a given node is degree of node
In the above figure degree of A=3 . The degree of C=2 . the degree oc I=0 .
Degree of tree :
The max degree of node in the tree is known as degree of a tree
Degree of a tree = max{degree(node1) ,degree(node2)…………….degree(node n)};
= max{3,1,2,1 ………0} .
= 3 .
Siblings :
children of the same parent is known is known is a siblings .
in the above figure B,C,D are siblings
F,G siblings of C
E, F are not siblings but they are cousins .
Terminal Nodes :
A node is said to be terminal node if and only if whose degree is zero
In the above figure I,J,K,L are terminal nodes whose degree is ‘0’ .
Nonterminal Nodes :
A Nonterminal node is node whose degree is > 0 .
In the above figure A,B,C,D,E,F,G,H are Nonterminal nodes since whose degree is > 0 .
Terminal and Nonterminal nodes also known as leaf and non leaf nodes respectively
Level number is a numerical number it is used for processing the elements of the tree . level number of any node is level number of its parent node +1 . for example root node level is 0 .then level of its child nodes is 1.
In the above figure A level is 0 , B level is 1 , L level is 3 .
Depth Or Height :
Maximum and highest level number in the tree is Known as depth or height of a tree .
Above tree height is 3 .
Parent Vs Child :
If there exist aedge between U to V . Then U is called parent V is called child .
In the above fig A is called root and B,C,D are called child’s .
Edge:
A link between parent and child is known is known as edge
In-Degree :
In-degree is defined as number of edges arriving at the node
In-degree of root node is 0
Out-Degree :
The no of edges leaving from the node is Known as out-degree . Terminal node out-degree is 0 .
Ancestors :
If there is edge between U to V . U is ancestor . root node doesn’t have any ancestors .
Descendant :
If there is edge between U to V . V is descendant . leaf node doesn’t have any descendants .
Applications :
Disk directory
General trees are used to model applications such as file systems.
Organizational hierarchy
Family tree
Disadvantages of trees:
· What ever the data we are inserting in a tree that data is not having proper directions
· The data in a tree cannot be represented in the main memory of the tree
· To search an element in the tree it takes more processing and its very complex process
· On tree we cannot perform any operations like inserting an element into the tree .deleting an element from the tree and modifying the tree .
Binary Trees
A linked list is an efficient data structure . the main drawback of a linked list is that it is linear . Every node has information of only previous or next node only . Hence searching is done only in a sequential manner . the binary tree is advantages as it is hierarchical data structure .
A binary tree is a fixed set of nodes . It maybe empty or divided into three disjoint subsets .The first subset is called root of the tree . it contains single element . the other two subsets are called right and left sub trees of the main tree .
Fig(1):
Fig formed with 9 nodes named with alphabets
B,C are left and right subtrees
Strictly binary tree :
s.b.t is a tree every non-terminal node in a binary tree has filled left and right sub trees , the tree is called s.b.t
N=no of nodes .
Propertise of binary tree :
fig(2):
complete binary tree :
cbt is a binary tree where all non terminal nodes have two sons excluding the last node
(or)
A cbt has all it leaves at same level
A binary tree is said to be cbt the total number of nodes N=Pow(2,n)-1
n=depth of a tree .
fig 3:
Propertise of binary tree :
1) In a binary tree there exist n number of nodes then it contain (n-1) edges
2) The total no of nodes in a given binary tree N=Pow(2,n)-1
3) The total noof nodes in a given binary tree whose level =Pow(2,l)
4) The sum of the node at all levels of the given binary tree is nothing but total number of nodes in a given binary tree whose hight is h
TRAVERSAL TECHNICS BINARY TREES :
Another common operation Traversing a binary tree . that is pass the tree ,enumerating each of its nodes once . may simply wish to print the content of each node as we enumerate it .
The order of traverse Linear lists are first to last . but in binary trees four types of orderings are there .
Traversing technics are used for converting the ordinary given expressions into either infix (or)prefix (or)postfix
The real-time applications traversal technics are used evaluating the expressions which we are frequently used in various programming languages
In data structures we have four traversal technics
1)Pre order traversal technic
2)In order traversal technic
3)Post order traversal technic
4)Level order traversal technic
1)Pre order traversal technic :
Pre order traversal technic is used for constructing Pre-fix expressions from the given binary Tree
steps
1)print the root node
2)traverse the left most sub treein pre order traversal technic recursively
3)traverse the right most sub tree in pre order traversal technic recursively
ABDECFG
2)In order traversal technic :
In order traversal technic is used for constructing infix expressions from the given binary Tree
steps
1)traverse the left most subtree in Inorder traversal technic recursively
2)print the root node
3)traverse the right most subtree in Inorder traversal technic recursively
DBEAFCG
Post order traversal technic is used for constructing Postfix expressions from the given binary Tree
Steps:
1)traverse the left most subtree in postorder traversal technic recursively
2)traverse the right most subtree in postorder traversal technic recursively
3)print the root node
DEBFGCA
4)Level order traversal technic :
In Level order traversal technic all nodes are traversed level by level
ABCDEFG
GRAPHS:
A graph consist of a set of nodes (or vertices ) and set of arcs (or edges ) . Each arc is specified by a pair of nodes .
A graph G=(V,E) is an ordered finite set of elements of V,E where V represents set of vertices and E represents set of edges
the set of nodes is = {o,p,q,r,s}
set of edges is= {(o,p),(o,r),(o,q),(q,s),(r,s)}
Define The following terms :
· Degree of vertex
· Degree of graph
· In degree
· Out degree
· Directed graph
· Undirected graph
· Cycle
· Self loop
· Weighted Graph
· Spanning tree
· Minimum cost spanning tree
· Path of a graph
· Cost of a path
Degree of vertex :
· No of edges which are incident or leaving from a vertex is called Degree of vertex
· This can be applied only for undirected graphs
In the fig degree each vertex deg(1)=2
Degree of graph :
The max degree of vertex is known as degree of a graph
In this fig Deg(1)=3
Deg(4)=3
Max{deg(1),deg(2),deg(3),deg(4)}
=Max{3,2,2,4}
=3
In degree :
No of edges incident on a particular vertex is known as In degree
In above fig in degree of vertex 1,2,3,4 is 2.
The no of edges which are leaving from a particular vertex is known as outdegree
Int the above fig out deg(3)= 2;
Out Deg(1)=0;
Out degree :
The no of edges which are leaving from a particular vertex is known as outdegree
In above fig out degree of vertex 1,2,3,4 is 2.
Int the above fig out deg(3)= 0;
Out Deg(1)=2;
Both in degree and out degree of vertex of undirected graph is same
Both in degree and out degree of vertex of directed graph is may or may not same
UnDirected graph :
Directed graph :
If graph is said to be directed graph iff all edges in the graph are directed
Edges {<1,2>,<1,3><2,4>,<4,5>,<5,3>}
If graph is said to be directed graph iff all edges in the graph are undirected
set of edges is= {(o,p),(o,r),(o,q),(q,s),(r,s)}
Cycle:
If the first vertex and last vertex of a path is same then it is cycle
Graph does not contain cycle (2->3,3->4,4->5)
Cycle will be exist for only directed graph
Selfloop:
Above graph does n’t contain any self loop
Weight of< 2,3> is13
<4,3>is 11
Selfloop:
An edge which is pointing to it self it is known as self loop
Above graph contain self loop
Above graph does n’t contain any self loop
Weighted Graph :
If an edge is qualified with a positive real no then that graph is known as weighted graph
Weight of< 2,3> is13
<3,4> is 12
<4,3>is 11
<5,2> is 10
Above fig represents Main Graph G1(V,E)
Graph G(V,E)
G2(V,E)
Spanning tree :
A spanning tree ‘T ‘ of graph ‘ G’ if T should be Tree (or) A graph is said to be a spanning tree iff it should be satisfy the following properties
1)all the vertices of sub graph must be available in main graph
1)all the edges of sub graph must be available in main graph
3) edgeset of sub graph is subset of main graph edge set
. A single graph can have many different spanning trees
Above fig represents Main Graph G1(V,E)
Above fig represents Sub Graph G2(V,E)
Above fig represents Sub Graph G3(V,E)
Both G2,G3 are known as spanning trees if the cost required to visit .
A minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with
weight less than or equal to the weight of every other spanning tree
Graph G(V,E)
G2(V,E)
The cost of G2 spanning Tree =3+6+4 =13
Path of g=2->3->4->5
Path of the Graph :
if the first vertex and last vertex is different then the sequence of edges is known as path
Path of g=2->3->4->5
=3+4+5
=12
Connected Graph :
If a vertex of a graph connected with all vertices of same graph then that graph is known as connected graph
.
Above graph G2(V,E) is not a connected graph
Graph Representations:
A graph can be represented using data structures in two ways ,they are
Bubblesort :
#include< stdio.h>
Insertion sort :
Sorting is typically done in-place, by iterating up the array, growing the sorted list behind it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position.
The basic aim of linear search is that to search element in the list of numbers sequentially in the worst case 0 to n-1 element position .
Binary search:
In linear search we need to search for the search key for n number of times which leads to lots of consuming process
low=0;
I)Adjacency matrix representation
II)Adjacency linked list representation
I)Adjacency matrix representation :
In mathematics and computer science, an adjacency matrix is a means of representing which vertices (or nodes) of a graph are adjacent to which other vertices.
The adjacency matrix of n-vertex graph G=(V,E) is n
n matrix A . Each element of A is either 0 or 1.
n matrix A . Each element of A is either 0 or 1.
1)Adjacency matrix is represented in the main memory of the computer by using two dimensional array
2) Adjacency matrix representation follow the following formula
for undirected graph :
I) (i , j)
E or (j , i)E => A(i ,j)=1
E or (j , i)E => A(i ,j)=1
II) (i , j)
E => A(i ,j)=0 .
E => A(i ,j)=0 .
for directed graph :
I) (i , j)E => A(i ,j)=1
E => A(i ,j)=1
II) (i , j)E => A(i ,j)=0 .
E => A(i ,j)=0 .
Here A represents A adjacency matrix . Consider the following graphs and represent then by using adjacency matrix
for undirected graph in adjacency matrix symmetric property is satisfied
(A(i , j)=A(j , i))
1) Either row sum or column sum of a vertex of undirected graph will give either in-degree or out-degree since it satisfy symmetric property in other words in-degree and out-degree of a particular vertex of undirected graph is equal
2) Adjacency matrix of directed graph may or may not satisfy the symmetric property
3) In adjacency matrix of directed graph , row sum gives out-degree where as column sum gives in-degree of a particular vertex hence the in-degree and out-degree of a particular vertex of directed graph may or may not be same since it doesn’t satisfy symmetric property
II)Adjacency linked list representation :
In this representation the data will be represented in the form of nodes .node contain two parts they are 1)data part 2) address part
The typical structure of node is given below
1)Data part gives information about vertex . address part represent address of adjacent nodes of a particular vertex (or) address of next node in the sub child nodes
2)If address part must be NULL if no child information available
3) the architectural diagram of adjacency linked representation is shown below
Represent the following graphs using adjacency linked list representation for directed graph (G1)
Represent the following graphs using adjacency linked list representation for undirected graph (G2)
From this representations in-degree of any vertex is equal to = no of occurrences of a particular node sub child parts
In-degree(1) in G1 is 0 ,in G2 is 1
Out-degree of a particular node = no of sub Childs of a particular node
As per directed graph concern in-degree and out-degree of a particular node may or may not be same . since symmetric property may or may not be satisfied
As per undirected graph is concern both in-degree and out-degree of a particular node is equal or samesince it satisfy symmetric propertyn
SORTINGS AND SEARCHINGS
SelectionSort :
Sorting is the process of arranging the given random data into either in ascending order or descending order
• (or)Sorting takes an unordered collection and makes it an ordered one.
Steps:
1)find first least among ‘n’ no of numbers and keep it into first position
2)find second least among (n-1) numbers and keep it second position
--------
--------
-------
5)Find (n-1) least element among two elements and keep it into (n-1)th position
6)for the lost element we need not apply the process since only one element that is trivially sorted by itself . and placed in ‘n’th position
Ele are 80,40,35,90,23,-40,60,70
#include< stdio.h>
#include< string.h>
main()
{
int a[10];
inti,n;
printf("enter no of elements u want to sort\n");
scanf("%d",&n);
printf("enterelements u want to sort\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
selectionsort(a,n);
printf("the ele are\n");
for(i=0;i<n;i++)
{
printf("%d\n",a[i]);
}
}
void selectionsort(int a[],int n)
{
inti,pass,j,k;
for(i=0;i<n;i++)
{
pass=i;
for(j=i+1;j<n;j++)
{
if(a[pass]>a[j])
{
pass=j;
}
}
if(i!=pass)
{
k=a[i];
a[i]=a[pass];
a[pass]=k;
}
}
}
INPUT
enter no of elements u want to sort
8
enterelements u want to sort
80
40
35
90
23
-40
60
70
the ele are
-40
23
35
40
60
70
80
90
Bubblesort :
The simplest sorting algorithm is bubble sort. The bubble sort works by iterating down an array to be sorted from the first element to the last, comparing each pair of elements and switching their positions if necessary. This process is repeated as many times as necessary, until the array is sorted .Since the worst case scenario is that the array is in reverse order, and that the first element in sorted array is the last element in the starting array .
#include< stdio.h>
#include< string.h>
main()
{
int a[10];
inti,n;
printf("enter elements u want to sort\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
bubblesort(a,n);
printf("the ele are\n");
for(i=0;i<n;i++)
{
printf("%d\n",a[i]);
}
}
void bubblesort(int a[],int n)
{
inti,pass,j,k;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
k=a[i];
a[i]=a[j];
a[j]=k;
}
}
}
}
enter no of elements u want to sort
8
enterelements u want to sort
80
40
35
90
23
-40
60
70
the ele are
-40
23
35
40
60
70
80
90
Quicksort :
#include< stdio.h>
#include< string.h>
main()
{
int a[10];
inti,n;
printf("enter elements u want to sort\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
quicksort(a,0,n-1);
printf("the ele are\n");
for(i=0;i<n;i++)
{
printf("%d\n",a[i]);
}
}
void quicksort(int a[],intfirst,int lost)
{
inti,j,pivot,temp;
if(first>=lost)
return;
else
{
i=first;
j=lost;
pivot=a[first];
while(i<=j)
{
while(a[i]<=pivot)
{
++i;
}while(a[j]>pivot)
{
--j;
}
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[j];
a[j]=a[first];
a[first]=temp;
quicksort(a,0,j-1);
quicksort(a,j+1,lost);
}
}
Enter no of ele
10
Enter ele to be sort
10
42
23
74
11
65
58
94
36
99
87
the ele are
11
23
36
42
58
65
74
87
94
99
Insertion sort :
Sorting is typically done in-place, by iterating up the array, growing the sorted list behind it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position.
An example of an insertion sort occurs in everyday life while playing cards. To sort the cards in your hand you extract a card, shift the remaining cards, and then insert the extracted card in the correct place. This process is repeated until all the cards are in the correct sequence. Both average and worst-case time is O(n2). For further reading
The best case input is an array that is already sorted .
3 7 4 9 5 2 6 1
3 7 4 9 5 2 6 1
3 7 4 9 5 2 6 1
3 4 7 9 5 2 6 1
3 4 7 9 5 2 6 1
3 4 5 7 9 2 6 1
2 3 4 5 7 9 6 1
2 3 4 5 6 7 9 1
1 2 3 4 5 6 7 9
#include< stdio.h>
#include< string.h>
main()
{
int a[10];
inti,n;
printf("enter elements u want to sort\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
insertionsort(a,n);
printf("the ele are\n");
for(i=0;i<n;i++)
{
printf("%d\n",a[i]);
}
}
void insertionsort(int array[],int n)
{
inti,d,t;
for (i = 1 ; i <= n - 1; i++)
{
d = i;
while ( d > 0 && array[d] < array[d-1])
{
t = array[d];
array[d] = array[d-1];
array[d-1] = t;
d--;
}
}
}
Enter no of ele
10
Enter ele to be sort
10
42
23
74
11
65
58
94
36
99
87
the ele are
11
23
36
42
58
65
74
87
94
99
Searching :
Searching is a process of taking one element and searching into the list of elements .if the element is found in list of elements . then we print the position of the element and we can say search is successful . If an element is not found we can say search is unsuccessful .
While we are searching an element in list of elements the list of numbers must be available in sorted order .
In data structures we have two types of searching technics they are
1)linear/sequential search
1)linear/sequential search
2)binary search
Linear search :
The basic aim of linear search is that to search element in the list of numbers sequentially in the worst case 0 to n-1 element position .
Steps for linear search :
1)list of numbers represent them in an array(a[0…..n-1]) .
· The elements a0,a1,a2….an must be in a sorted order .
· Take an element to search in list elements that element is known as search key .
· If search key found in the list of given numbers we can stop the process
· We print the relative position of serch key
· We can say that search is successful
· If search key is not found in the list of numbers we can say search is unsuccessful
#include< stdio.h>
#include< string.h>
main()
{
inti,n,a[10],res,key;
printf("enter no of elements\n");
scanf("%d",&n);
printf("enter elements\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("enter search key\n");
scanf("%d",&key);
res=lsearch(a,n,key);
if(res==0)
{
printf("search is un success ful\n");
}
else
{
printf("search is sucessful\n");
printf("%d\n",res);
}}
intlsearch(int a[],intn,int key)
{
int i;
for(i=0;i<n;i++)
{
if(a[i]==key)
return i+1;
}
}
Binary search:
In linear search we need to search for the search key for n number of times which leads to lots of consuming process
In binary search we search for the particular element in the entire list half of the time of linear search . in general if an array contain n number of elements we search n/2 elements
Steps for binary search :
· We will be given ‘n’ no of elements and they can represented in array
· Obtain search key element
· Initialize low=0 and high=size-1
· Calculate mid=floor((low+high)/2);
And check for ((low<=high)&&(a[mid]!=key)) if it is true perform the following steps otherwise return mid+1
if(a[mid]<key) then
low=mid+1;
if(a[mid]>key) then
high=mid-1;
mid=(low+high)/2;
if(a[mid]==key) then return mid+1 other wise return 0;
#include< stdio.h>
#include< string.h>
main()
{
inti,n,a[10],res,key;
printf("enter no of elements\n");
scanf("%d",&n);
printf("enter elements\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("enter search key\n");
scanf("%d",&key);
res=bsearch(a,n,key);
if(res==0)
{
printf("search is un success ful\n");
}
else
{
printf("search is sucessful\n");
printf("%d\n",res);
}}
intbsearch(int a[],intn,int key)
{
low=0;
high=n-1;
mid=(low+high)/2;
while((low<=high)&&(a[mid]!=key))
{
if(a[mid]<key)
{
low=mid+1;
}
if(a[mid]>key)
{
high=mid-1;
}
mid=(low+high)/2;
}
if(a[mid]==key)
{
return mid+1;
}
else
{
return 0;
}
} Thanks for visiting this blog. How is the content?. Your comment is great gift to my work. Cheers.
No comments:
Post a Comment