Tree Traversal in C++

We've already seen many implementations of tree and its uses in java. Lets look at a simple implementation of traversing on a tree in C++. Code has been given below which I think is quite self descriptive.

Regards,
Jack

Print % using printf in C

Problem:

How can you print % using the printf function? (Remember % is used as a format specifier!!!)
Very Simple, following cases are examples


Cheers!!
Jack

Find Output for this C Program

Problem:

What would be the output of the following C program? (Is it a valid C program?)


Explanation:

This will produce output “4321”. The return type of printf is “int” which is the number of characters written to stdout.


Cheers!!
Jack

C - %n format specifier in printf

Well, what does the format specifier %n of printf function do?

Explanation:
Print nothing, but write number of characters successfully written so far into an integer pointer parameter.

Example:

Output:
blah blah
val = 38

Cheers!
Jack

C program to determine endian'ess

We shall see a small C program to determine whether a machine's type is little-endian or big-endian.

Definition:

BigEndian means that the higher order byte of the number is stored in memory at the lowest address, and the lower order byte at the highest address. The big end comes first.

eg: OAOBOCOD will be stored as OA(a) OB(a+1) OC(a+2) OD(a+3)

LittleEndian means that the lower order byte of the number is stored in memory at the lowest address, and the higher order byte is stored at the highest address i.e., the little
end comes first.

eg: OAOBOCOD will be stored as OD(a) OC(a+1) OB(a+2) OA(a+3)

Program:


Cheers!!
Jack

Addition without using the + operator in C

Write a C function which does the addition of two integers without using the '+' operator. You can use only the bitwise operators.(Remember the good old method of implementing the full-adder circuit using the OR and XOR gates....)

Now, for the code implemented in C.

Cheers!
Jack

"Offsetof" Macros in C : What it is and why it is

Problem:

The following is the offset macros which is used many a times. Lets figure out what is it trying to do and what is the advantage of using it.


Explanation:

offsetof tells you where in the memory allocation of the structure you will find a particular member.

Consider the example,


The structure defined takes up 12 bytes:

* byte 0: singlechar
* byte 1: arraymember[0]
* byte 2: arraymember[1]
* byte 3: arraymember[2]
* ...
* byte 10: arraymember[9]
* byte 11: anotherchar

The output will be:

offsetof(mystruct,singlechar) is 0
offsetof(mystruct,arraymember) is 1
offsetof(mystruct,anotherchar) is 11

If you allocate an object of type, and get a byte* to the start of the structure, you can use offsetof to find out where each member is. If you use that pointer offset, and convert it back to the correct type, it will give you a pointer to the member.


The output will be:

anotherchar is 17

The reason you can't assume that each member will be a specific offset from the beginning of the struct is complicated, and compiler dependent. If you must do something like this (which is really low-level stuff which you should avoid unless you have to), then use a macro like offsetof, rather than trying to manually specify the offset yourself.

Hope you learnt something.

Cheers!!
Jack

What is the difference between memcpy and memmove?

Answer:

With memcpy, the destination cannot overlap the source at all. With memmove copying takes place as if an intermediate buffer was used, allowing the destination and source to overlap. This means that memmove might be very slightly slower than memcpy, as it cannot make the same assumptions.

Cheers!!
Jack

C program to find fibonacci series using only one variable !!!

Problem:
Generating Fibonacci series using only one variable.

There are many ways to achieve this. I have given three ways to do this in the following methods.

Method #1:
We can have a simple function to do this.

Method #2:
The following recursive function would do the job.

Method #3:
The following one works great as well!

Cheers!!
Jack

Find all possible palindromes in a String in Java C++

This is not the regular palindrome finder. Given a string, we should be able to print all the possible palindromes. Let me quickly give a brief example.
For the following text : abccbab
All the possible palindromes are,
bab
abccba
bccb
cc
If you could see there are two possible outcomes in palindrome, one is odd and other is even. My initial solution was very worse. What I actually did was did a permutation/combination of all the possible texts and send it to a palindrome() method. It will run in the worst possible time.
However, there is even a simpler solution available. First do a parse for odd occurring palindromes followed by even palindromes.
For odd palindromes run through each character from the text. For each character, see if there the pre and post occuring characters are equal, if they are equal print them and do the same for the next levels. In the following example shown below, assume you are at 'y' and see the previous and next characters are equal. If they are see further more until the palindrome functionality ceases. Print all of them whilst this time.

 

Thats it. Do the same for all the characters. Since there is no meaning in doing this for first and last characters, we can very well omit them.
Similar logic holds for even sized palindromes. Here we wont be holding the center character. Rest of the logic remains the same. The java code follows,

package dsa.stringmanipulation;

/**
 * Program to print all palindromes in a string
 * @author Bragaadeesh
 */
public class FindAllPalindromes {
 public static void main(String[] args){
  FindAllPalindromes finder = new FindAllPalindromes();
  finder.printAllPalindromes("abcddcbaABCDEDCBA");
 }
 
 public void printAllPalindromes(String inputText){
  if(inputText==null){
   System.out.println("Input cannot be null!");
   return;
  }
  if(inputText.length()<=2){
   System.out.println("Minimum three characters should be present");
  }
  //ODD Occuring Palindromes
  int len = inputText.length();
  for(int i=1;i<len-1;i++){
   for(int j=i-1,k=i+1;j>=0&&k<len;j--,k++){
    if(inputText.charAt(j) == inputText.charAt(k)){
     System.out.println(inputText.subSequence(j,k+1));
    }else{
     break;
    }
   }
  }
  //EVEN Occuring Palindromes
  for(int i=1;i<len-1;i++){
   for(int j=i,k=i+1;j>=0&&k<len;j--,k++){
    if(inputText.charAt(j) == inputText.charAt(k)){
     System.out.println(inputText.subSequence(j,k+1));
    }else{
     break;
    }
   }
  }

 }
}
/*
Sample Output:
DED
CDEDC
BCDEDCB
ABCDEDCBA
dd
cddc
bcddcb
abcddcba
*/

The code in C++

#include <iostream>
using namespace std;

void printAllPalindromes(char*);

char* subSequence(char*,int,int);

int main() {
 char *s = "abcddcbaABCDEDCBA";
 printAllPalindromes(s);
 return 0;
}

char* subSequence(char* mainSequence, int from, int to){
 char * tgt = new char[to-from+1];
 for(int i=0;i<(to-from);i++){
  tgt[i] = mainSequence[i+from];
 }
 tgt[to-from] = '\0';
 return tgt;
}

void printAllPalindromes(char* inputText) {
 if(!inputText) {
  printf("Input cannot be null!");
  return;
 }
 if(strlen(inputText)<=2) {
  printf("Minimum three characters should be present\n");
 }
 //ODD Occuring Palindromes
 int len = strlen(inputText);
 for(int i=1;i<len-1;i++) {
  for(int j=i-1,k=i+1;j>=0&&k<len;j--,k++) {
   if(inputText[j] == inputText[k]) {
    char* subSeq = subSequence(inputText,j,k+1);
    cout<<subSeq<<endl;
    delete subSeq;
   } else {
    break;
   }
  }
 }
 //EVEN Occuring Palindromes
 for(int i=1;i<len-1;i++) {
  for(int j=i,k=i+1;j>=0&&k<len;j--,k++) {
   if(inputText[j] == inputText[k]) {
    char* subSeq = subSequence(inputText,j,k+1);
    cout<<subSeq<<endl;
    delete subSeq;
   } else {
    break;
   }
  }
 }

}
/*
 Sample Output:
 DED
 CDEDC
 BCDEDCB
 ABCDEDCBA
 dd
 cddc
 bcddcb
 abcddcba
 */

Cheers,
Bragaadeesh.

Difference between two days implemented in C

Although Java is my forte, I started my early days by coding with C. The below program is to get the difference in days between two dates. The program is simple and has well defined comments to explain for itself. Thought I would post it here.

#include<stdio.h>
#include<conio.h>
#include<dos.h>
int datecmp(struct date,struct date);
int leap(int);
void main()
{
 struct date a,b;
 int leep;
 clrscr();
 b.da_year=2000;
 b.da_mon=7;
 b.da_day=1;
 getdate(&a);
 printf("%u\t%u\t%u\t",b.da_day,b.da_mon,b.da_year);
 printf("\n%u\t%u\t%u\t",a.da_day,a.da_mon,a.da_year);
 datecmp(a,b);
 /*if((leep=leap(b.da_year))==1)
  printf("\nThe year is leep year");
 else
  printf("\nThe year is an ordinary year");*/
 getch();
}


int datecmp(struct date a,struct date b)
{
 struct date c;
 char days[12]={31,28,31,30,31,30,31,31,30,31,30,31};
 int y=365;
 int i,j;
 int td=0;
 c.da_year=a.da_year-b.da_year;
 c.da_mon=a.da_mon-b.da_mon;
 if(c.da_year==0)//SAME YEAR BUT DIFFERENT MONTH OR SAME MONTH
 {
  if(c.da_mon==0)
   td=a.da_day-b.da_day;
  else
  {
   for(i=0,j=b.da_mon;i<(c.da_mon-1);i++,j++)
    td+=days[j];
   td+=days[b.da_mon-1]-b.da_day;
   td+=a.da_day-1;
  }
 }
 else if(c.da_year>1 && c.da_mon>1)//YEAR DIFF B/W TWO INPUTS IS >THAN 1 YEAR
 {
  if(b.da_mon<3 && leap(b.da_year)==1)
   td=1;
  else
   td=0;
  for(i=0,j=b.da_year+1;i<(c.da_year);i++,j++)
    td=td+365+leap(j);
  if(c.da_mon==0)
   td+=a.da_day-b.da_day;
  else
  {
   for(i=0,j=b.da_mon;i<(c.da_mon-1);i++,j++)
    td+=days[j];
   td+=days[b.da_mon-1]-b.da_day;
   td+=a.da_day-1+leap(a.da_year);
  }
 }
 else if(c.da_year==1)//YEAR DIFF B/W TWO INPUTS IS==1 YEAR
 {
  if(c.da_mon>0)
  {
   if(b.da_mon>1 && leap(b.da_year)==1)
    td=1;
   else
    td=0;
   for(i=0,j=b.da_year+1;i<(c.da_year);i++,j++)
     td=td+365+leap(j);
   if(c.da_mon==0)
    td+=a.da_day-b.da_day;
   else
   {
    for(i=0,j=b.da_mon;i<(c.da_mon-1);i++,j++)
     td+=days[j];
    td+=days[b.da_mon-1]-b.da_day;
    td+=a.da_day-1+leap(a.da_year);
   }
  }
  else if(c.da_mon==0 && c.da_day>0)
  {
    if(b.da_mon>1)
    td=0;
   else
    td=1;
   for(i=0,j=b.da_year+1;i<(c.da_year);i++,j++)
     td=td+365+leap(j);
    td+=a.da_day-b.da_day;
  }
 }
 else if(c.da_year==1)
 {

 }

 printf("\n The days are %d",td);
 getch();
}
int leap(int year)//LEAP YEAR FUNCTION
{
 if(year%4==0)
 {
  if(year%100==0)
  {
   if(year%400==0)
    return(1);
   else
    return(0);
  }
 else
  return(1);
 }
 else
  return(0);
}

Cheers,
Bragaadeesh.