OS Data Structures

printf,scanf,getch,getchar,getche,kbhit etc

Used mainly to represent elements in a dynamic environment where it is added on an ad-hoc basis.

Especially in the cases where the total number of elements in the list cannot be pre-decided, linked lists are used. This does not lead to space insufficiency or space wastage as in case of arrays.

For eg. The no. of terms in a order-n polynomial varies greatly, using an array to store the co-efficients is an inefficient methods. If the array size is declared 100, a quadratic equation will use just 3 index and the rest 99 will be wasted. While for a sine or cosine series (from x to infinity) an overflow error might occur..!

void bubble(int x[],int n)

{

int hold,j,pass;

int switched=true;

for(pass=0;pass<n-1&&switched=true;pass++){

switched=false;

for(j=0;j<n-pass-1;j++)

if(x[j]>x[j+1]){

switched=true;

hold=x[j];

x[j]=x[j+1];

x[j+1]=hold;

}

}

}

Tree always takes o(log n) time because tree has height is

(log n).

number of possible tree = (2 power n) - n.

for example:

A tree contain three node.

so n=3.

possible tree = 8 - 3 = 5.

we can use the binary search algorithm for this problem because this searching algorithm has O(log n) performance in both worse and average case.

A red black tree is a binary tree where

1. every node has color.

2. root node is always black

3. the child of a black node is either black or red

4. both the child nodes of every red node must be black

5. all the leaves must be black

enum is not an basic data type like int,float and all it is

a user defined data type, and printf function works only

with basic data type, we 've overload printf function to

make it work for user defined data types :)

Compile time polymorphism(Static polymorphism) means

basically those language structure which will cause the

compiler to produce code at the compile-time. That is, the

compiler is well aware that what code is to be generated at

the compile-time itself: Ex: overloading of operators,

functions.

Run time Polymorphism(Dynamic Polymorphism)means that the

compiler is unaware what code is to be generated so it binds

the possible code and let the program decide it at the

run-time itself.Ex: the virtualness of a class member or the

entire class itself.

Rael world example fo polymorphism can be start machnism of

bike, inwhich u wil hav same method start() but it may be

either by kick start or button start.

N example for encapsulation can be a stack or queue doesn't

matter how it is implented internally with linked list or array

An AVL tree is a self-balancing binary search tree, and it

was the first such data structure to be invented.In an AVL

tree, the heights of the two child subtrees of any node

differ by at most one. Lookup, insertion, and deletion all

take O(log n) time in both the average and worst cases,

where n is the number of nodes in the tree prior to the

operation. Insertions and deletions may require the tree to

be rebalanced by one or more tree rotations.

In linear search each element in the array should be checked

until the required element got searched whereas in binary

search array is divided into two and required element is

searched