Reference vs. Pointer

Reference Pointer
1>is an object which IS AN ALIAS for another object.] [is an object that CONTAINS THE ADRRESS IN MEMORY of another object]

2>the preferred way of undirectly access objects.] [you should use it just if you really need it, as it it lets you to work in a lower level than a reference does]

3>keeps your code clear .] the code is less clear but still understandable

4>it must be initialized when created . you don’t have to initialize it when declared

5>it references to the one object and only
that one, therefore you can not modify
the address referenced.]
because it contains an address, it can point to many different objects during lifetime. The address can be manipulated

6>when used, the address is dereferenced without using any particular operator] the address must be dereferenced using the * operator

All abt Binary Tree

#include
using namespace std;
struct tnode{
int data;
tnode *left;
tnode *right;
};

tnode *insert(tnode *p,int val);
void preorder(tnode *p);
void inorder(tnode *p);
void postorder(tnode *p);
void levelorder(tnode *p);
int height(tnode *p);
int countnode(tnode *p);
int internal(tnode *p);
int leaf(tnode *p);
tnode *delmin(tnode *p);
tnode *delmax(tnode *p);
int sum(tnode *p);
void complete(tnode *p);
int strict(tnode *p);
tnode *mirror(tnode *p);
int search( tnode *p, int val);
void display(tnode *p,int val);
bool identical(tnode *p,tnode *q);

//tnode *del(tnode *p,int num);

void printPathsRecur(struct tnode* node, int path[], int pathLen);
void printArray(int ints[], int len);
/*
Given a binary tree, print out all of its root-to-leaf
paths, one per line. Uses a recursive helper to do the work.
*/
void printPaths(struct tnode* node) {
int path[1000];

printPathsRecur(node, path, 0);
}

/*
Recursive helper function -- given a node, and an array containing
the path from the root node up to but not including this node,
print out all the root-leaf paths.
*/
void printPathsRecur(struct tnode* node, int path[], int pathLen) {
if (node==NULL) return;

// append this node to the path array
path[pathLen] = node->data;
pathLen++;

// it's a leaf, so print the path that led to here
if (node->left==NULL && node->right==NULL) {
printArray(path, pathLen);
}
else {
// otherwise try both subtrees
printPathsRecur(node->left, path, pathLen);
printPathsRecur(node->right, path, pathLen);
}
}

// Utility that prints out an array on a line.
void printArray(int ints[], int len) {
int i;
for (i=0; ileft);
doubleTree(node->right);

// duplicate this node to its left
oldLeft = node->left;

tnode *temp= new tnode;

temp->data=node->data; //Node(node->data);
temp->left=NULL;
temp->right=NULL;
node->left=temp;
node->left->left = oldLeft;
return node;
}

int countTrees(int numKeys) {

if (numKeys <=1) {
return(1);
}
else {
// there will be one value at the root, with whatever remains
// on the left and right each forming their own subtrees.
// Iterate through all the values that could be the root...
int sum = 0;
int left, right, root;

for (root=1; root<=numKeys; root++) {
left = countTrees(root - 1);
right = countTrees(numKeys - root);

// number of possible trees with this root == left*right
sum += left*right;
}

return(sum);
}
}

int main()
{
struct tnode *p=NULL;
p=insert(p,10);
p=insert(p,101);
p=insert(p,13);
p=insert(p,15);
p=insert(p,67);
p=insert(p,9);
p=insert(p,4);
p=insert(p,34);

cout<<"\n inorder traversal is :\n";
inorder(p);
cout<<"\n\n level order traversal is :\n";
levelorder(p);
cout<<"\n\n height of bst is :"<<height(p)-1;
cout<<"\n\n total node in bst is :"<<countnode(p);
cout<<"\n\n total no. of internal node in bst is :"<<internal(p);
cout<<"\n\n total no. of leaf in bst is :"<<leaf(p);

tnode *q;
q=insert(p,5);
cout<<endl<<endl;
inorder(q);
cout<<"\n\n sum of node is :"<<sum(q);
complete(p);
strict(p);
if(identical(p,p)==1)
cout<<"\n tree is identical ";
else
cout<<"\n tree is not identical ";
display(p,34);
display(p,99);

cout<<"\n\n after deletion of minimum :";
p=delmin(p);
inorder(p);
cout<<"\n\n after deletion of maxmum :";
p=delmax(p);
inorder(p);

cout<<"\n\n mirror is ";
mirror(p);
inorder(p);
cout<<"\n print paths is from root to leaf ... \n";
printPaths(p);

cout<<"\n the no. of tree which can be made from 5 no. is :"<<countTrees(5)<<endl;

doubleTree(p);

cout<<endl<data=val;
p->left=NULL;
p->right=NULL;
}
else
{
tnode *temp,*q;
q=p;
while(q!=NULL)
{
temp=q;
if(temp->dataright;
else
q=temp->left;
}
tnode *n=new tnode;
n->data=val;
n->left=NULL;
n->right=NULL;

if(val>=temp->data)
temp->right=n;
else
temp->left=n;

}
return p;
}
*/
//insert by recurssion
tnode *insert(tnode *p,int val)
{
if(p==NULL)
{
p=new tnode;
p->data=val;
p->left=NULL;
p->right=NULL;
}
else
{
if(val

data)
p->left=insert(p->left,val);
else
p->right=insert(p->right,val);

}
return p;
}

void preorder(tnode *p)
{
if(p!=NULL)
{
cout<

data<left);
preorder(p->right);
}
}

void inorder(tnode *p)
{
if(p!=NULL)
{
inorder(p->left);
cout<

data<right);
}
}

void postorder(tnode *p)
{
if(p!=NULL)
{
postorder(p->left);
postorder(p->right);
cout<

data<<" ";
}
}

void levelorder(tnode *p)
{
tnode *queue[100]= {(tnode *)0} ;
int size=0;
int q=0;
while(p!=NULL)
{
cout<

data<left)
queue[size++]=p->left;
if(p->right)
queue[size++]=p->right;

p=queue[q++];
}
}

int height(tnode *p)
{
int h1=0,h2=0;
if(p==NULL)
return 0;
if(p->left)
h1=height(p->left);
if(p->right)
h2=height(p->right);
int max;
if(h1>h2)
max=h1;
else
max=h2;
return 1+max;
}

int countnode(tnode *p)
{
int c1=0,c2=0;
if(p==NULL)
return 0;
if(p->left)
c1=countnode(p->left);
if(p->right)
c2=countnode(p->right);
return 1+c1+c2;
}

int internal(tnode *p)
{
int i1=0,i2=0;
if(p->left==NULL && p->right==NULL)
return 0;
if(p->left) //!=NULL)
i1=internal(p->left);
if(p->right) //!=NULL)
i2=internal(p->right);
return 1+i1+i2;
}

int leaf(tnode *p)
{
int l1=0,l2=0,count=0;
if(p==NULL)
return 1;
if(p!=NULL)
{
if(p->left==NULL && p->right==NULL)
count++;
if(p->left)
l1=leaf(p->left);
if(p->right)
l2=leaf(p->right);
}
return count+l1+l2;
}

tnode *delmin(tnode *p)
{
tnode *temp=p,*r;
while(temp->left->left!=NULL)
{ temp=temp->left; }
r=temp->left;
temp->left=temp->left->right;
delete r;;
return p;
}

tnode *delmax(tnode *p)
{
tnode *temp=p,*r;
while(temp->right->right!=NULL)
{ temp=temp->right; }
r=temp->right;
temp->right=temp->right->left;
delete r;
return p;
}

int sum(tnode *p)
{
int s1=0,s2=0;
if(p==NULL)
return 0;
if(p!=NULL)
{
s1=sum(p->left);
s2=sum(p->right);
return s1+s2+p->data;
}
}

void complete(tnode *p)
{
int h=height(p);
int t=(int)pow(2,float(h)-1);
if(t==1)
cout<<"\n\n its complete tree :";
else
cout<left && !p->right) || (!p->left && p->right) )
{ flag=1; return flag; }
else
{ if(!flag)
{flag=strict(p->left);
flag=strict(p->right);}
}
}
if(flag==0)
cout<<"\n its strict bst ";
else
cout<left);
mirror(p->right);
tnode *temp;
temp=p->left;
p->left=p->right;
p->right=temp;
}
return p;
}

bool identical(tnode *p,tnode *q)
{
if(p==NULL && q==NULL)
return(true);
else if(p!=NULL && q!=NULL)
return (p->data==q->data && identical(p->left,q->left) && identical(p->right,q->right));
else
return false;
}

int search( tnode *p, int val)
{
if(p==NULL)
return -1;
int level=0;
struct tnode *q=p,*temp;
while(q!=NULL)
{
temp=q;
if(val data)
{q=temp->left;
level++; }
else if(val >temp->data)
{q=temp->right;
level++; }
else if(val == temp->data)
return level;
}
return -2;
}

void display(tnode *p,int val)
{
if(search(p,val)==-2)
cout<<"\n\n "<<val< is not present in bst :";
else if(search(p,val)==-1)
cout<<"\n\n bst is NULL";
else
cout<<"\n\n ("<<val<is at ("<<search(p,val)<data)
{ flag=level; break; }
else if(valdata)
{ q=q->left;
level++; }
else if(val>q->data)
{ q=q->right;
level++; }
}
//flag=-2;
if(flag==-1)
cout<<"\ntree is empty ";
else if(flag==-2)
cout<<"\n data is not in bst ";
else
cout<<level<<endl;
}
*/

remove the duplicated no. from a sorted array..

//1st method This function just prints the array without duplicates.
//  It does not modify the original array!

#include <stdio.h>
#include<iostream>
using namespace std;

void remove(int a[], int n);
int main()
{

int a[100],n;
cout<<“\n enter the size of array :”;
cin>>n;
for(int i=0; i<n; i++)
cin>>a[i];
remove(a,n);
system(“pause”);
return(0);
}

void remove(int a[], int n)
{
int i,last_seen_unique;
if(n<= 1){return;}
last_seen_unique = a[0];

cout<<a[0]<<” “;
for(i=1;i<n;i++)
{
if(a[i]!=last_seen_unique)
{
cout<<a[i];
last_seen_unique = a[i];
}
}
}
 //2nd method Changes the original array and resets the size of the array if //duplicates have been removed.

#include <stdio.h>
#include<iostream>
using namespace std;

void remove(int a[], int n) ;
int main()
{
int a[100],n;
cout<<“\n enter the size of array :”;
cin>>n;
for(int i=0; i<n; i++)
cin>>a[i];
remove(a,n);
cout<<endl<<endl;
system(“pause”);
return(0);
}

void remove(int a[], int n)
{
int i, j, k, l;
int current_pos;
int dup_start;
int dup_end;
if(n<= 1){return;}
for (i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]!=a[j])
break;
else
{
current_pos = i;
dup_start = j;
j++;
while((a[i]==a[j])&& j<n)
j++;
dup_end = j-1;
// Now remove elements of the array from “dup_start” to “dup_end”
// and shrink the size of the array.
for(k = (dup_end + 1), l = dup_start ; k <n;)
a[l++]=a[k++];
// Reduce the array size by the number of elements removed.
n=n-(dup_end – dup_start + 1);
}
}
}
cout<<“\n\n final array with size <“<<n<<” >”<<” is :”;
for(i=0;i<n;i++)
cout<<a[i]<<” “;
}

//3rd method  modify the array
void remove1(int a[], int n)
{     int i,j=0;
for(i=1;i<n;i++)
{
for(j=i+1; j<n; j++)
if(a[i]!=a[j])
{ j++;  a[j]=a[i]; }
n=j-1;
}
for(int i=0;i<n;i++)
cout<<a[i]<<” “;
}

abt storage class n type qualifier

This is a part of a variable declaration that tells the compiler how to interpret the variable’s symbol. It does not in itself allocate storage, but it usually tells the compiler how the variable should be stored. Storage class specifiers help you to specify the type of storage used for data objects. Only one storage class specifier is permitted in a declaration this makes sense, as there is only one way of storing things and if you omit the storage class specifier in a declaration, a default is chosen. The default depends on whether the declaration is made outside a function (external declarations) or inside a function (internal declarations). For external declarations the default storage class specifier will be extern and for internal declarations it will be auto. The only exception to this rule is the declaration of functions, whose default storage class specifier is always extern.

Here are C’s storage classes and what they signify:

* auto – local variables.
* static – variables are defined in a nonvolatile region of memory such that they retain their contents though out the program’s execution.
* register – asks the compiler to devote a processor register to this variable in order to speed the program’s execution. The compiler may not comply and the variable looses it contents and identity when the function it which it is defined terminates.
* extern – tells the compiler that the variable is defined in another module.

In C, const and volatile are type qualifiers. The const and volatile type qualifiers are completely independent. A common misconception is to imagine that somehow const is the opposite of volatile and vice versa. This is wrong. The keywords const and volatile can be applied to any declaration, including those of structures, unions, enumerated types or typedef names. Applying them to a declaration is called qualifying the declaration?that’s why const and volatile are called type qualifiers, rather than type specifiers.

* const means that something is not modifiable, so a data object that is declared with const as a part of its type specification must not be assigned to in any way during the run of a program. The main intention of introducing const objects was to allow them to be put into read-only store, and to permit compilers to do extra consistency checking in a program. Unless you defeat the intent by doing naughty things with pointers, a compiler is able to check that const objects are not modified explicitly by the user. It is very likely that the definition of the object will contain an initializer (otherwise, since you can’t assign to it, how would it ever get a value?), but this is not always the case. For example, if you were accessing a hardware port at a fixed memory address and promised only to read from it, then it would be declared to be const but not initialized.
* volatile tells the compiler that other programs will be modifying this variable in addition to the program being compiled.

For example, an I/O device might need write directly into a program or data space. Meanwhile, the program itself may never directly access the memory area in question.

In such a case, we would not want the compiler to optimize-out this data area that never seems to be used by the program, yet must exist for the program to function correctly in a larger context.

It tells the compiler that the object is subject to sudden change for reasons which cannot be predicted from a study of the program itself, and forces every reference to such an object to be a genuine reference.
* const volatile – Both constant and volatile.
The “volatile” modifier

The volatile modifier is a directive to the compiler?s optimizer that operations involving this variable should not be optimized in certain ways.

There are two special cases in which use of the volatile modifier is desirable.

The first case involves memory-mapped hardware (a device such as a graphics adaptor that appears to the computer?s hardware as if it were part of the computer?s memory),

and the second involves shared memory (memory used by two or more programs running simultaneously).

Most computers have a set of registers that can be accessed faster than the computer?s main memory.

A good compiler will perform a kind of optimization called ?redundant load and store removal.?

The compiler looks for places in the code where it can either remove an instruction to load data from memory because the value is already in a register, or remove an instruction to store data to memory because the value can stay in a register until it is changed again anyway.
If a variable is a pointer to something other than normal memory, such as memory-mapped ports on a peripheral, redundant load and store optimizations might be detrimental. For instance, here?s a piece of code that might be used to time some operation:

time_t time_addition(volatile const struct timer *t, int a)
{
int n;
int x;
time_t then;
x = 0;
then = t->value;
for (n = 0; n < 1000; n++)
{
x = x + a;
}
return t->value – then;
}

In this code, the variable t->value is actually a hardware counter that is being incremented as time passes. The function adds the value of a to x 1000 times, and it returns the amount the timer was incremented by while the 1000 additions were being performed. Without the volatile modifier, a clever optimizer might assume that the value of t does not change during the execution of the function, because there is no statement that explicitly changes it. In that case, there?s no need to read it from memory a second time and subtract it, because the answer will always be 0. The compiler might therefore ?optimize? the function by making it always return 0. If a variable points to data in shared memory, you also don?t want the compiler to perform redundant load and store optimizations. Shared memory is normally used to enable two programs to communicate with each other by having one program store data in the shared portion of memory and the other program read the same portion of memory. If the compiler optimizes away a load or store of shared memory, communication between the two programs will be affected.

What is the difference between constants defined through #define and the constant keyword?

A constant is similar to a variable in the sense that it represents a memory location (or simply, a value). It is different from a normal variable, in that it cannot change it’s value in the proram – it must stay for ever stay constant.

So whats the difference between these two?

#define ABC 5

and

const int abc = 5;

There are two main advantages of the second one over the first technique. First, the type of the constant is defined. “pi” is float. This allows for some type checking by the compiler.

Second, these constants are variables with a definite scope. The scope of a variable relates to parts of your program in which it is defined.

There is also one good use of the important use of the const keyword. Suppose you want to make use of some structure data in some function. You will pass a pointer to that structure as argument to that function. But to make sure that your structure is readonly inside the function you can declare the structure argument as const in function prototype. This will prevent any accidental modification of the structure values inside the function.

How are floating point numbers stored? Whats the IEEE format?

IEEE Standard 754 floating point is the most common representation today for real numbers on computers, including Intel-based PC’s, mackintoshes, and most Unix platforms.

IEEE floating point numbers have three basic components: the sign, the exponent, and the mantissa. The mantissa is composed of the fraction and an implicit leading digit (explained below). The exponent base(2) is implicit and need not be stored.

The following figure shows the layout for single (32-bit) and double (64-bit) precision floating-point values. The number of bits for each field are shown (bit ranges are in square brackets):

Sign   Exponent   Fraction   Bias
————————————————–
Single Precision 1 [31] 8 [30-23]  23 [22-00] 127
Double Precision 1 [63] 11 [62-52] 52 [51-00] 1023

The sign bit is as simple as it gets. 0 denotes a positive number; 1 denotes a negative number. Flipping the value of this bit flips the sign of the number.

The exponent field needs to represent both positive and negative exponents. To do this, a bias is added to the actual exponent in order to get the stored exponent. For IEEE single-precision floats, this value is 127. Thus, an exponent of zero means that 127 is stored in the exponent field. A stored value of 200 indicates an exponent of (200-127), or 73.

For reasons discussed later, exponents of -127 (all 0s) and +128 (all 1s) are reserved for special numbers. For double precision, the exponent field is 11 bits, and has a bias of 1023.

The mantissa, also known as the significand, represents the precision bits of the number. It is composed of an implicit leading bit and the fraction bits. To find out the value of the implicit leading bit, consider that any number can be expressed in scientific notation in many different ways. For example, the number five can be represented as any of these:

5.00 � 1.00
0.05 � 10 ^ 2
5000 � 10 ^ -3

In order to maximize the quantity of representable numbers, floating-point numbers are typically stored in normalized form. This basically puts the radix point after the first non-zero digit. In normalized form, five is represented as 5.0 � 1.00. A nice little optimization is available to us in base two, since the only possible non-zero digit is 1. Thus, we can just assume a leading digit of 1, and don’t need to represent it explicitly. As a result, the mantissa has effectively 24 bits of resolution, by way of 23 fraction bits.

So, to sum up:

1. The sign bit is 0 for positive, 1 for negative.
2. The exponent’s base is two.
3. The exponent field contains 127 plus the true exponent for single-precision,
or 1023 plus the true exponent for double precision.
4. The first bit of the mantissa is typically assumed to be 1.f, where f is the
field of fraction bits.

What is the token pasting operator and stringizing operator in C?

Token pasting operator

ANSI has introduced a well-defined token-pasting operator, ##, which can be used like this:


#define f(g,g2) g##g2

main()

{

  int var12=100;

  printf("%d",f(var,12));

}

O/P

100


Stringizing operator


#define sum(xy) printf(#xy " = %f\n",xy);

main()

{

    sum(a+b); // As good as printf("a+b = %f\n", a+b);

}

So what does the message “warning: macro replacement within a string literal” mean?


#define TRACE(var, fmt) printf("TRACE: var = fmt\n", var)

TRACE(i, %d);

gets expanded as

printf("TRACE: i = %d\n", i);

In other words, macro parameters were expanded even inside string literals and character constants. Macro expansion is *not* defined in this way by K&R or by Standard C. When you do want to turn macro arguments into
strings, you can use the new # preprocessing operator, along with string literal concatenation:


#define TRACE(var, fmt) printf("TRACE: " #var " = " #fmt "\n", var)

See and try to understand this special application of the strigizing operator!

#define Str(x) #x
#define Xstr(x) Str(x)
#define OP plus

char *opname = Xstr(OP); //This code sets opname to “plus” rather than “OP”.

Here are some more examples

Example1


Define a macro DEBUG such that the following program

int main()
{
int x=4;
float a = 3.14;
char ch = 'A';

DEBUG(x, %d);
DEBUG(a, %f);
DEBUG(ch, %c);
}

outputs

DEBUG: x=4
DEBUG: y=3.140000
DEBUG: ch=A

The macro would be

#define DEBUG(var, fmt) printf("DEBUG:" #var "=" #fmt "\n", var);

Example2


Write a macro PRINT for the following program

int main()
{
int x=4, y=4, z=5;
int a=1, b=2, c=3;
PRINT(x,y,z);
PRINT(a,b,c);
}

such that it outputs

x=4 y=4 z=5
a=1 b=2 c=3

Here is a macro that will do this

#define PRINT(v1,v2,v3) printf("\n" #v1 "=%d" #v2 "=%d" #v3 "=%d", v1, v2, v3)

How can I write a macro which takes a variable number of arguments?

One can define the macro with a single, parenthesized “argument” which in the macro expansion becomes the entire argument list, parentheses and all, for a function such as printf():


#define DEBUG(args) (printf("DEBUG: "), printf args)

if(n != 0) DEBUG(("n is %d\n", n));


The caller must always remember to use the extra parentheses.

Other possible solutions are to use different macros depending on the number of arguments.

C9X will introduce formal support for function-like macros with variable-length argument lists.

The notation … will appear at the end of the macro “prototype” (just as it does for varargs functions).

Is it acceptable to declare/define a variable in a C header?

A global variable that must be accessed from more than one file can and should be declared in a header file. In addition, such a variable must be defined in one source file.

Variables should not be defined in header files, because the header file can be included in multiple source files, which would cause multiple definitions of the variable.

The ANSI C standard will allow multiple external definitions, provided that there is only one initialization.

But because there?s really no advantage to using this feature, it?s probably best to avoid it and maintain a higher level of portability.

“Global” variables that do not have to be accessed from more than one file should be declared static and should not appear in a header file.

external sorting?

A sorting program that sorts items that are on secondary storage (disk or tape) rather than primary storage (memory) is called an external sort. Exactly how to sort large data depends on what is meant by ?too large to fit in memory.? If the items to be sorted are themselves too large to fit in memory (such as images), but there aren?t many items, you can keep in memory only the sort key and a value indicating the data?s location on disk. After the key/value pairs are sorted, the data is rearranged on disk into the correct order. If ?too large to fit in memory? means that there are too many items to fit into memory at one time, the data can be sorted in groups that will fit into memory, and then the resulting files can be merged. A sort such as a radix sort can also be used as an external sort, by making each bucket in the sort a file. Even the quick sort can be an external sort. The data can be partitioned by writing it to two smaller files. When the partitions are small enough to fit, they are sorted in memory and concatenated to form the sorted file.