Write a C program to implement a Generic Linked List.
Here is a C program which implements a generic linked list. This is also one of the very popular interview questions thrown around. The
crux of the solution is to use the void C pointer to make it generic. Also notice how we use function pointers to pass the address of
different functions to print the different generic data.
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef struct list {
void *data;
struct list *next;
} List;
struct check {
int i;
char c;
double d;
} chk[] = { { 1, 'a', 1.1 },
{ 2, 'b', 2.2 },
{ 3, 'c', 3.3 } };
void insert(List **, void *, unsigned int);
void print(List *, void (*)(void *));
void printstr(void *);
void printint(void *);
void printchar(void *);
void printcomp(void *);
List *list1, *list2, *list3, *list4;
int main(void)
{
char c[]
= { 'a', 'b', 'c', 'd' };
int i[]
= { 1, 2, 3, 4 };
char *str[] = { "hello1", "hello2", "hello3", "hello4" };
list1 = list2 = list3 = list4 = NULL;
insert(&list1, &c[0], sizeof(char));
insert(&list1, &c[1], sizeof(char));
insert(&list1, &c[2], sizeof(char));
insert(&list1, &c[3], sizeof(char));
insert(&list2, &i[0], sizeof(int));
insert(&list2, &i[1], sizeof(int));
insert(&list2, &i[2], sizeof(int));
insert(&list2, &i[3], sizeof(int));
insert(&list3,str[0],strlen(str[0])+1);
insert(&list3,str[1],strlen(str[0])+1);
insert(&list3,str[2],strlen(str[0])+1);
insert(&list3,str[3],strlen(str[0])+1);
insert(&list4, &chk[0], sizeof chk[0]);
insert(&list4, &chk[1], sizeof chk[1]);
insert(&list4, &chk[2], sizeof chk[2]);
printf("Printing characters:");
print(list1, printchar);
printf(" : done\n\n");
printf("Printing integers:");
print(list2, printint);
printf(" : done\n\n");
printf("Printing strings:");
print(list3, printstr);
printf(" : done\n\n");
printf("Printing composite:");
print(list4, printcomp);
printf(" : done\n");
return 0;
}
void insert(List **p, void *data, unsigned int n)
{
List *temp;
int i;
/* Error check is ignored */
temp = malloc(sizeof(List));
temp->data = malloc(n);
for (i = 0; i <>
*(char *)(temp->data + i) = *(char *)(data + i);
temp->next = *p;
*p = temp;
}
void print(List *p, void (*f)(void *))
{
while (p)
{
(*f)(p->data);
p = p->next;
}
}
void printstr(void *str)
{
printf(" \"%s\"", (char *)str);
}
void printint(void *n)
{
printf(" %d", *(int *)n);
}
void printchar(void *c)
{
printf(" %c", *(char *)c);
}
void printcomp(void *comp)
{
struct check temp = *(struct check *)comp;
printf(" '%d:%c:%f", temp.i, temp.c, temp.d);
}
Friday, January 21, 2011
REVERSE A Doubly LinkList
#include"stdio.h'
#include'ctype.h"
typedef struct node
{
int value;
struct node *next;
struct node *prev;
}mynode ;
mynode *head, *tail;
void add_node(int value);
void print_list();
void reverse();
int main()
{
head=NULL;
tail=NULL;
add_node(1);
add_node(2);
add_node(3);
add_node(4);
add_node(5);
print_list();
reverse();
print_list();
return(1);
}
void add_node(int value)
{
mynode *temp, *cur;
temp = (mynode *)malloc(sizeof(mynode));
temp->next=NULL;
temp->prev=NULL;
if(head == NULL)
{
printf("\nAdding a head pointer\n");
head=temp;
tail=temp;
temp->value=value;
}
else
{
for(cur=head;cur->next!=NULL;cur=cur->next);
cur->next=temp;
temp->prev=cur;
temp->value=value;
tail=temp;
}
}
void print_list()
{
mynode *temp;
printf("\n--------------------------------\n");
for(temp=head;temp!=NULL;temp=temp->next)
{
printf("\n[%d]\n",temp->value);
}
}
void reverse()
{
mynode *cur, *temp, *save_next;
if(head==tail)return;
if(head==NULL || tail==NULL)return;
for(cur=head;cur!=NULL;)
{
printf("\ncur->value : [%d]\n",cur->value);
temp=cur->next;
save_next=cur->next;
cur->next=cur->prev;
cur->prev=temp;
cur=save_next;
}
temp=head;
head=tail;
tail=temp;
}
#include'ctype.h"
typedef struct node
{
int value;
struct node *next;
struct node *prev;
}mynode ;
mynode *head, *tail;
void add_node(int value);
void print_list();
void reverse();
int main()
{
head=NULL;
tail=NULL;
add_node(1);
add_node(2);
add_node(3);
add_node(4);
add_node(5);
print_list();
reverse();
print_list();
return(1);
}
void add_node(int value)
{
mynode *temp, *cur;
temp = (mynode *)malloc(sizeof(mynode));
temp->next=NULL;
temp->prev=NULL;
if(head == NULL)
{
printf("\nAdding a head pointer\n");
head=temp;
tail=temp;
temp->value=value;
}
else
{
for(cur=head;cur->next!=NULL;cur=cur->next);
cur->next=temp;
temp->prev=cur;
temp->value=value;
tail=temp;
}
}
void print_list()
{
mynode *temp;
printf("\n--------------------------------\n");
for(temp=head;temp!=NULL;temp=temp->next)
{
printf("\n[%d]\n",temp->value);
}
}
void reverse()
{
mynode *cur, *temp, *save_next;
if(head==tail)return;
if(head==NULL || tail==NULL)return;
for(cur=head;cur!=NULL;)
{
printf("\ncur->value : [%d]\n",cur->value);
temp=cur->next;
save_next=cur->next;
cur->next=cur->prev;
cur->prev=temp;
cur=save_next;
}
temp=head;
head=tail;
tail=temp;
}
Wednesday, January 19, 2011
Testing Theory
Testing Theory
Testing is the process of running a program with the intention of finding errors.
Testing should be carried out systematically. It should never be done by intuition.
Most testing is top down, module by module testing.
There are two main approaches to testing:
1. Black Box Testing
2. White Box Testing
Black Box Testing
This treats the system as one that cannot be seen in detail. The structure of the program is not taken into account. The tests are performed based on what the program does. This is sometimes called Functional Testing.
The functional requirements have been agreed with the customer. Thus they can see that the program performs as it was requested at the specification stage. It is difficult to know just how much of the program coding has been tested in this case, but it is the kind of testing which is very popular with the customer. The approach to testing should generally be as shown in the following algorithm:
1. Repeat
2. Code and unit test a component.
3. Add the component to the existing combination.
4. Test and debug the new combination.
5. Until all the components have been added.
6. Deliver the system for acceptance tests.
Unit testing or module testing uses white box techniques, which we'll discuss shortly. It takes detailed structural information into account. Testing and debugging the new combination involves black box testing as you are testing to see that the components perform the desired task.
The acceptance testing stage takes place nearer the end of the software development and it follows an agreed test plan. It applies a black box approach to see how software conforms to the customer's functional requirements. The technique of testing each module as it is developed does have problems. It is not possible to test the modules in isolation. This problem can be overcome by writing small sections of code are written to pass data between modules.
A Main Program segment which passes data to the module is called a Driver. The driver can also print results which the module passes to it. A Dummy Subprogram which is called by the module under test is called a Stub. The stub may accept or pass data to the test module and confirm that the transaction has occurred by simply writing a message to the screen.
Therefore, black box testing involves the programmer looking at the outputs and inputs to a module. The details of the system are treated as if they are in a black box and can therefore not be seen. The programmer (tester) does not look at the code that is going to be tested.
Click on this link for further information on black box testing: http://en.wikipedia.org/wiki/Black_box_testing
White Box Testing
This treats the system as one in which the workings can be seen. The structure of the program is taken into account when tests are designed for the program. This is sometimes called Structural Testing. It should do the following:
1. Guarantee that all statements in the program have been tested at least once, ie: identify all pathways through code (eg: sequence, selection and iteration).
2. Test all the decision statements on their true and false side and check to see which of these paths have not been tested in the Black Box approach.
3. Test all loops at their boundaries and their operational limits.
4. Exercise internal data structures to check their validity.
5. Create new test data for paths not already tested.
Therefore, White Box Testing involves the programmer looking at every path through the coding. The details of the system are treated like a white box or a glass box through which the code can be seen clearly.
Click on this link for further information on white box testing: http://en.wikipedia.org/wiki/White_box_testing
Click on this link to read about white/glass box testing: http://www.cse.fau.edu/~maria/COURSES/CEN4010-SE/C13/glass.htm
Testing Terminology
The purpose of testing is to attempt to detect to logic errors in the code. The code should be tested using as many different types of data input as possible. It is estimated that the testing phase can take 50% of the time allocated for project development. Therefore, testing should be planned and thorough.
Integration Testing
Integration testing is testing the whole program when all of the modules are put together.
Test Case
A test case is a set of data which is prepared in order to test that the program produces the predicted result.
Test Plan
A test plan is a list of test cases which cover all circumstances which can arise. Each test case should detail the expected results.
The actual results of a test run are compared with the expected results for that test case to determine whether the test has been successful.
Testing is the process of running a program with the intention of finding errors.
Testing should be carried out systematically. It should never be done by intuition.
Most testing is top down, module by module testing.
There are two main approaches to testing:
1. Black Box Testing
2. White Box Testing
Black Box Testing
This treats the system as one that cannot be seen in detail. The structure of the program is not taken into account. The tests are performed based on what the program does. This is sometimes called Functional Testing.
The functional requirements have been agreed with the customer. Thus they can see that the program performs as it was requested at the specification stage. It is difficult to know just how much of the program coding has been tested in this case, but it is the kind of testing which is very popular with the customer. The approach to testing should generally be as shown in the following algorithm:
1. Repeat
2. Code and unit test a component.
3. Add the component to the existing combination.
4. Test and debug the new combination.
5. Until all the components have been added.
6. Deliver the system for acceptance tests.
Unit testing or module testing uses white box techniques, which we'll discuss shortly. It takes detailed structural information into account. Testing and debugging the new combination involves black box testing as you are testing to see that the components perform the desired task.
The acceptance testing stage takes place nearer the end of the software development and it follows an agreed test plan. It applies a black box approach to see how software conforms to the customer's functional requirements. The technique of testing each module as it is developed does have problems. It is not possible to test the modules in isolation. This problem can be overcome by writing small sections of code are written to pass data between modules.
A Main Program segment which passes data to the module is called a Driver. The driver can also print results which the module passes to it. A Dummy Subprogram which is called by the module under test is called a Stub. The stub may accept or pass data to the test module and confirm that the transaction has occurred by simply writing a message to the screen.
Therefore, black box testing involves the programmer looking at the outputs and inputs to a module. The details of the system are treated as if they are in a black box and can therefore not be seen. The programmer (tester) does not look at the code that is going to be tested.
Click on this link for further information on black box testing: http://en.wikipedia.org/wiki/Black_box_testing
White Box Testing
This treats the system as one in which the workings can be seen. The structure of the program is taken into account when tests are designed for the program. This is sometimes called Structural Testing. It should do the following:
1. Guarantee that all statements in the program have been tested at least once, ie: identify all pathways through code (eg: sequence, selection and iteration).
2. Test all the decision statements on their true and false side and check to see which of these paths have not been tested in the Black Box approach.
3. Test all loops at their boundaries and their operational limits.
4. Exercise internal data structures to check their validity.
5. Create new test data for paths not already tested.
Therefore, White Box Testing involves the programmer looking at every path through the coding. The details of the system are treated like a white box or a glass box through which the code can be seen clearly.
Click on this link for further information on white box testing: http://en.wikipedia.org/wiki/White_box_testing
Click on this link to read about white/glass box testing: http://www.cse.fau.edu/~maria/COURSES/CEN4010-SE/C13/glass.htm
Testing Terminology
The purpose of testing is to attempt to detect to logic errors in the code. The code should be tested using as many different types of data input as possible. It is estimated that the testing phase can take 50% of the time allocated for project development. Therefore, testing should be planned and thorough.
Integration Testing
Integration testing is testing the whole program when all of the modules are put together.
Test Case
A test case is a set of data which is prepared in order to test that the program produces the predicted result.
Test Plan
A test plan is a list of test cases which cover all circumstances which can arise. Each test case should detail the expected results.
The actual results of a test run are compared with the expected results for that test case to determine whether the test has been successful.
Comman c Errors
1. Introduction
This document lists the common C programming errors that the author sees time and time again. Solutions to the errors are also presented.
Another great resource is the C FAQ. Gimpel Software also has a list of hard to detect C/C++ bugs that might be useful.
2. Beginner Errors
These are errors that beginning C students often make. However, the professionals still sometimes make them too!
2.1 Forgetting to put a break in a switch statement
Remember that C does not break out of a switch statement if a case is encountered. For example:
int x = 2;
switch(x) {
case 2:
printf("Two\n");
case 3:
printf("Three\n");
}
prints out:
Two
Three
Put a break to break out of the switch:
int x = 2;
switch(x) {
case 2:
printf("Two\n");
break;
case 3:
printf("Three\n");
break; /* not necessary, but good if additional cases are added later */
}
2.2 Using = instead of ==
C's = operator is used exclusively for assignment and returns the value assigned. The == operator is used exclusively for comparison and returns an integer value (0 for false, not 0 for true). Because of these return values, the C compiler often does not flag an error when = is used when one really wanted an ==. For example:
int x = 5;
if ( x = 6 )
printf("x equals 6\n");
This code prints out x equals 6! Why? The assignment inside the if sets x to 6 and returns the value 6 to the if. Since 6 is not 0, this is interpreted as true.
One way to have the compiler find this type of error is to put any constants (or any r-value expressions) on the left side. Then if an = is used, it will be an error:
if ( 6 = x)
2.3 scanf() errors
There are two types of common scanf() errors:
2.3.1 Forgetting to put an ampersand (&) on arguments
scanf() must have the address of the variable to store input into. This means that often the ampersand address operator is required to compute the addresses. Here's an example:
int x;
char * st = malloc(31);
scanf("%d", &x); /* & required to pass address to scanf() */
scanf("%30s", st); /* NO & here, st itself points to variable! */
As the last line above shows, sometimes no ampersand is correct!
2.3.2 Using the wrong format for operand
C compilers do not check that the correct format is used for arguments of a scanf() call. The most common errors are using the %f format for doubles (which must use the %lf format) and mixing up %c and %s for characters and strings.
2.4 Size of arrays
Arrays in C always start at index 0. This means that an array of 10 integers defined as:
int a[10];
has valid indices from 0 to 9 not 10! It is very common for students go one too far in an array. This can lead to unpredictable behavior of the program.
2.5 Integer division
Unlike Pascal, C uses the / operator for both real and integer division. It is important to understand how C determines which it will do. If both operands are of an integal type, integer division is used, else real division is used. For example:
double half = 1/2;
This code sets half to 0 not 0.5! Why? Because 1 and 2 are integer constants. To fix this, change at least one of them to a real constant.
double half = 1.0/2;
If both operands are integer variables and real division is desired, cast one of the variables to double (or float).
int x = 5, y = 2;
double d = ((double) x)/y;
2.6 Loop errors
In C, a loop repeats the very next statement after the loop statement. The code:
int x = 5;
while( x > 0 );
x--;
is an infinite loop. Why? The semicolon after the while defines the statement to repeat as the null statement (which does nothing). Remove the semicolon and the loop works as expected.
Another common loop error is to iterate one too many times or one too few. Check loop conditions carefully!
2.7 Not using prototypes
Prototypes tell the compiler important features of a function: the return type and the parameters of the function. If no prototype is given, the compiler assumes that the function returns an int and can take any number of parameters of any type.
One important reason to use prototypes is to let the compiler check for errors in the argument lists of function calls. However, a prototype must be used if the function does not return an int. For example, the sqrt() function returns a double, not an int. The following code:
double x = sqrt(2);
will not work correctly if a prototype:
double sqrt(double);
does not appear above it. Why? Without a prototype, the C compiler assumes that sqrt() returns an int. Since the returned value is stored in a double variable, the compiler inserts code to convert the value to a double. This conversion is not needed and will result in the wrong value.
The solution to this problem is to include the correct C header file that contains the sqrt() prototype, math.h. For functions you write, you must either place the prototype at the top of the source file or create a header file and include it.
2.8 Not initializing pointers
Anytime you use a pointer, you should be able to answer the question: What variable does this point to? If you can not answer this question, it is likely it doesn't point to any variable. This type of error will often result in a Segmentation fault/coredump error on UNIX/Linux or a general protection fault under Windows. (Under good old DOS (ugh!), anything could happen!)
Here's an example of this type of error.
#include
int main()
{
char * st; /* defines a pointer to a char or char array */
strcpy(st, "abc"); /* what char array does st point to?? */
return 0;
}
How to do this correctly? Either use an array or dynamically allocate an array.
#include
int main()
{
char st[20]; /* defines an char array */
strcpy(st, "abc"); /* st points to char array */
return 0;
}
or
#include
#include
int main()
{
char *st = malloc(20); /* st points to allocated array*/
strcpy(st, "abc"); /* st points to char array */
free(st); /* don't forget to deallocate when done! */
return 0;
}
Actually, the first solution is much preferred for what this code does. Why? Dynamical allocation should only be used when it is required. It is slower and more error prone than just defining a normal array.
3. String Errors
3.1 Confusing character and string constants
C considers character and string constants as very different things. Character constants are enclosed in single quotes and string constants are enclosed in double quotes. String constants act as a pointer to the actually string. Consider the following code:
char ch = 'A'; /* correct */
char ch = "A"; /* error */
The second line assigns the character variable ch to the address of a string constant. This should generate a compiler error. The same should happen if a string pointer is assigned to a character constant:
const char * st = "A"; /* correct */
const char * st = 'A'; /* error */
3.2 Comparing strings with ==
Never use the == operator to compare the value of strings! Strings are char arrays. The name of a char array acts like a pointer to the string (just like other types of arrays in C). So what? Consider the following code:
char st1[] = "abc";
char st2[] = "abc";
if ( st1 == st2 )
printf("Yes");
else
printf("No");
This code prints out No. Why? Because the == operator is comparing the pointer values of st1 and st2, not the data pointed to by them. The correct way to compare string values is to use the strcmp() library function. (Be sure to include string.h) If the if statement above is replaced with the following:
if ( strcmp(st1,st2) == 0 )
printf("Yes");
else
printf("No");
the code will print out Yes. For similar reasons, don't use the other relational operators (<,>, etc.) with strings either. Use strcmp() here too.
3.3 Not null terminating strings
C assumes that a string is a character array with a terminating null character. This null character has ASCII value 0 and can be represented as just 0 or '\0'. This value is used to mark the end of meaningful data in the string. If this value is missing, many C string functions will keep processing data past the end of the meaningful data and often past the end of the character array itself until it happens to find a zero byte in memory!
Most C library string functions that create strings will always properly null terminate them. Some do not (e.g., strncpy() ). Be sure to read their descriptions carefully.
3.4 Not leaving room for the null terminator
A C string must have a null terminator at the end of the meaningful data in the string. A common mistake is to not allocate room for this extra character. For example, the string defined below
char str[30];
only has room for only 29 (not 30) actually data characters, since a null must appear after the last data character.
This can also be a problem with dynamic allocation. Below is the correct way to allocate a string to the exact size needed to hold a copy of another.
char * copy_str = malloc( strlen(orig_str) + 1);
strcpy(copy_str, orig_str);
The common mistake is to forget to add one to the return value of strlen(). The strlen() function returns a count of the data characters which does not include the null terminator.
This type of error can be very hard to detect. It might not cause any problems or only problems in extreme cases. In the case of dynamic allocation, it might corrupt the heap (the area of the program's memory used for dynamic allocation) and cause the next heap operation (malloc(), free(), etc.) to fail.
4. Input/Output Errors
4.1 Using fgetc(), etc. incorrectly
The fgetc(), getc() and getchar() functions all return back an integer value. For example, the prototype of fgetc() is:
int fgetc( FILE * );
Sometimes this integer value is really a simple character, but there is one very important case where the return value is not a character!
What is this value? EOF A common misconception of students is that files have a special EOF character at the end. There is no special character stored at the end of a file. EOF is an integer error code returned by a function. Here is the wrong way to use fgetc():
int count_line_size( FILE * fp )
{
char ch;
int cnt = 0;
while( (ch = fgetc(fp)) != EOF && ch != '\n')
cnt++;
return cnt;
}
What is wrong with this? The problem occurs in the condition of the while loop. To illustrate, here is the loop rewritten to show what C will do behind the scenes.
while( (int) ( ch = (char) fgetc(fp) ) != EOF && ch != '\n')
cnt++;
The return value of fgetc(fp) is cast to char to store the result into ch. Then the value of ch must be cast back to an int to compare it with EOF. So what? Casting an int value to a char and then back to an int may not give back the original int value. This means in the example above that if fgetc() returns back the EOF value, the casting may change the value so that the comparison later with EOF would be false.
What is the solution? Make the ch variable an int as below:
int count_line_size( FILE * fp )
{
int ch;
int cnt = 0;
while( (ch = fgetc(fp)) != EOF && ch != '\n')
cnt++;
return cnt;
}
Now the only hidden cast is in the second comparison.
while( (ch = fgetc(fp)) != EOF && ch != ((int) '\n') )
cnt++;
This cast has no harmful effects at all! So, the moral of all this is: always use an int variable to store the result of the fgetc(), getc() and getchar().
4.2 Using feof() incorrectly
There is a wide spread misunderstanding of how C's feof() function works. Many programmers use it like Pascal's eof() function. However, C's function works differently!
What's the difference? Pascal's function returns true if the next read will fail because of end of file. C's function returns true if the last function failed. Here's an example of a misuse of feof():
#include
int main()
{
FILE * fp = fopen("test.txt", "r");
char line[100];
while( ! feof(fp) ) {
fgets(line, sizeof(line), fp);
fputs(line, stdout);
}
fclose(fp);
return 0;
}
This program will print out the last line of the input file twice. Why? After the last line is read in and printed out, feof() will still return 0 (false) and the loop will continue. The next fgets() fails and so the line variable holding the contents of the last line is not changed and is printed out again. After this, feof() will return true (since fgets() failed) and the loop ends.
How should this fixed? One way is the following:
#include
int main()
{
FILE * fp = fopen("test.txt", "r");
char line[100];
while( 1 ) {
fgets(line, sizeof(line), fp);
if ( feof(fp) ) /* check for EOF right after fgets() */
break;
fputs(line, stdout);
}
fclose(fp);
return 0;
}
However, this is not the best way. There is really no reason to use feof() at all. C input functions return values that can be used to check for EOF. For example, fgets returns the NULL pointer on EOF. Here's a better version of the program:
#include
int main()
{
FILE * fp = fopen("test.txt", "r");
char line[100];
while( fgets(line, sizeof(line), fp) != NULL )
fputs(line, stdout);
fclose(fp);
return 0;
}
The author has yet to see any student use the feof() function correctly!
Incidently, this discussion also applies to C++ and Java. The eof() method of an istream works just like C's feof().
4.3 Leaving characters in the input buffer
C input (and output) functions buffer data. Buffering stores data in memory and only reads (or writes) the data from (or to) I/O devices when needed. Reading and writing data in big chunks is much more efficient than a byte (or character) at a time. Often the buffering has no effect on programming.
One place where buffering is visible is input using scanf(). The keyboard is usually line buffered. This means that each line input is stored in a buffer. Problems can arise when a program does not process all the data in a line, before it wants to process the next line of input. For example, consider the following code:
int x;
char st[31];
printf("Enter an integer: ");
scanf("%d", &x);
printf("Enter a line of text: ");
fgets(st, 31, stdin);
The fgets() will not read the line of text that is typed in. Instead, it will probably just read an empty line. In fact, the program will not even wait for an input for the fgets() call. Why? The scanf() call reads the characters needed that represent the integer number read in, but it leaves the '\n' in the input buffer. The fgets() then starts reading data from the input buffer. It finds a '\n' and stops without needing any additional keyboard input.
What's the solution? One simple method is to read and dump all the characters from the input buffer until a '\n' after the scanf() call. Since this is something that might be used in lots of places, it makes sense to make this a function. Here is a function that does just this:
/* function dump_line
* This function reads and dumps any remaining characters on the current input
* line of a file.
* Parameter:
* fp - pointer to a FILE to read characters from
* Precondition:
* fp points to a open file
* Postcondition:
* the file referenced by fp is positioned at the end of the next line
* or the end of the file.
*/
void dump_line( FILE * fp )
{
int ch;
while( (ch = fgetc(fp)) != EOF && ch != '\n' )
/* null body */;
}
Here is the code above fixed by using the above function:
int x;
char st[31];
printf("Enter an integer: ");
scanf("%d", &x);
dump_line(stdin);
printf("Enter a line of text: ");
fgets(st, 31, stdin);
One incorrect solution is to use the following:
fflush(stdin);
This will compile but its behavior is undefined by the ANSI C standard. The fflush() function is only meant to be used on streams open for output, not input. This method does seem to work with some C compilers, but is completely unportable! Thus, it should not be used.
4.4 Using the gets() function
Do not use this function! It does not know how many characters can be safely stored in the string passed to it. Thus, if too many are read, memory will be corrupted. Many security bugs that have been exploited on the Internet use this fact! Use the fgets() function instead (and read from stdin). But remember that unlike gets(), fgets() does not discard a terminating \n from the input.
The scanf() functions can also be used dangerously. The %s format can overwrite the destination string. However, it can be used safely by specifying a width. For example, the format %20s will not read more than 20 characters
This document lists the common C programming errors that the author sees time and time again. Solutions to the errors are also presented.
Another great resource is the C FAQ. Gimpel Software also has a list of hard to detect C/C++ bugs that might be useful.
2. Beginner Errors
These are errors that beginning C students often make. However, the professionals still sometimes make them too!
2.1 Forgetting to put a break in a switch statement
Remember that C does not break out of a switch statement if a case is encountered. For example:
int x = 2;
switch(x) {
case 2:
printf("Two\n");
case 3:
printf("Three\n");
}
prints out:
Two
Three
Put a break to break out of the switch:
int x = 2;
switch(x) {
case 2:
printf("Two\n");
break;
case 3:
printf("Three\n");
break; /* not necessary, but good if additional cases are added later */
}
2.2 Using = instead of ==
C's = operator is used exclusively for assignment and returns the value assigned. The == operator is used exclusively for comparison and returns an integer value (0 for false, not 0 for true). Because of these return values, the C compiler often does not flag an error when = is used when one really wanted an ==. For example:
int x = 5;
if ( x = 6 )
printf("x equals 6\n");
This code prints out x equals 6! Why? The assignment inside the if sets x to 6 and returns the value 6 to the if. Since 6 is not 0, this is interpreted as true.
One way to have the compiler find this type of error is to put any constants (or any r-value expressions) on the left side. Then if an = is used, it will be an error:
if ( 6 = x)
2.3 scanf() errors
There are two types of common scanf() errors:
2.3.1 Forgetting to put an ampersand (&) on arguments
scanf() must have the address of the variable to store input into. This means that often the ampersand address operator is required to compute the addresses. Here's an example:
int x;
char * st = malloc(31);
scanf("%d", &x); /* & required to pass address to scanf() */
scanf("%30s", st); /* NO & here, st itself points to variable! */
As the last line above shows, sometimes no ampersand is correct!
2.3.2 Using the wrong format for operand
C compilers do not check that the correct format is used for arguments of a scanf() call. The most common errors are using the %f format for doubles (which must use the %lf format) and mixing up %c and %s for characters and strings.
2.4 Size of arrays
Arrays in C always start at index 0. This means that an array of 10 integers defined as:
int a[10];
has valid indices from 0 to 9 not 10! It is very common for students go one too far in an array. This can lead to unpredictable behavior of the program.
2.5 Integer division
Unlike Pascal, C uses the / operator for both real and integer division. It is important to understand how C determines which it will do. If both operands are of an integal type, integer division is used, else real division is used. For example:
double half = 1/2;
This code sets half to 0 not 0.5! Why? Because 1 and 2 are integer constants. To fix this, change at least one of them to a real constant.
double half = 1.0/2;
If both operands are integer variables and real division is desired, cast one of the variables to double (or float).
int x = 5, y = 2;
double d = ((double) x)/y;
2.6 Loop errors
In C, a loop repeats the very next statement after the loop statement. The code:
int x = 5;
while( x > 0 );
x--;
is an infinite loop. Why? The semicolon after the while defines the statement to repeat as the null statement (which does nothing). Remove the semicolon and the loop works as expected.
Another common loop error is to iterate one too many times or one too few. Check loop conditions carefully!
2.7 Not using prototypes
Prototypes tell the compiler important features of a function: the return type and the parameters of the function. If no prototype is given, the compiler assumes that the function returns an int and can take any number of parameters of any type.
One important reason to use prototypes is to let the compiler check for errors in the argument lists of function calls. However, a prototype must be used if the function does not return an int. For example, the sqrt() function returns a double, not an int. The following code:
double x = sqrt(2);
will not work correctly if a prototype:
double sqrt(double);
does not appear above it. Why? Without a prototype, the C compiler assumes that sqrt() returns an int. Since the returned value is stored in a double variable, the compiler inserts code to convert the value to a double. This conversion is not needed and will result in the wrong value.
The solution to this problem is to include the correct C header file that contains the sqrt() prototype, math.h. For functions you write, you must either place the prototype at the top of the source file or create a header file and include it.
2.8 Not initializing pointers
Anytime you use a pointer, you should be able to answer the question: What variable does this point to? If you can not answer this question, it is likely it doesn't point to any variable. This type of error will often result in a Segmentation fault/coredump error on UNIX/Linux or a general protection fault under Windows. (Under good old DOS (ugh!), anything could happen!)
Here's an example of this type of error.
#include
int main()
{
char * st; /* defines a pointer to a char or char array */
strcpy(st, "abc"); /* what char array does st point to?? */
return 0;
}
How to do this correctly? Either use an array or dynamically allocate an array.
#include
int main()
{
char st[20]; /* defines an char array */
strcpy(st, "abc"); /* st points to char array */
return 0;
}
or
#include
#include
int main()
{
char *st = malloc(20); /* st points to allocated array*/
strcpy(st, "abc"); /* st points to char array */
free(st); /* don't forget to deallocate when done! */
return 0;
}
Actually, the first solution is much preferred for what this code does. Why? Dynamical allocation should only be used when it is required. It is slower and more error prone than just defining a normal array.
3. String Errors
3.1 Confusing character and string constants
C considers character and string constants as very different things. Character constants are enclosed in single quotes and string constants are enclosed in double quotes. String constants act as a pointer to the actually string. Consider the following code:
char ch = 'A'; /* correct */
char ch = "A"; /* error */
The second line assigns the character variable ch to the address of a string constant. This should generate a compiler error. The same should happen if a string pointer is assigned to a character constant:
const char * st = "A"; /* correct */
const char * st = 'A'; /* error */
3.2 Comparing strings with ==
Never use the == operator to compare the value of strings! Strings are char arrays. The name of a char array acts like a pointer to the string (just like other types of arrays in C). So what? Consider the following code:
char st1[] = "abc";
char st2[] = "abc";
if ( st1 == st2 )
printf("Yes");
else
printf("No");
This code prints out No. Why? Because the == operator is comparing the pointer values of st1 and st2, not the data pointed to by them. The correct way to compare string values is to use the strcmp() library function. (Be sure to include string.h) If the if statement above is replaced with the following:
if ( strcmp(st1,st2) == 0 )
printf("Yes");
else
printf("No");
the code will print out Yes. For similar reasons, don't use the other relational operators (<,>, etc.) with strings either. Use strcmp() here too.
3.3 Not null terminating strings
C assumes that a string is a character array with a terminating null character. This null character has ASCII value 0 and can be represented as just 0 or '\0'. This value is used to mark the end of meaningful data in the string. If this value is missing, many C string functions will keep processing data past the end of the meaningful data and often past the end of the character array itself until it happens to find a zero byte in memory!
Most C library string functions that create strings will always properly null terminate them. Some do not (e.g., strncpy() ). Be sure to read their descriptions carefully.
3.4 Not leaving room for the null terminator
A C string must have a null terminator at the end of the meaningful data in the string. A common mistake is to not allocate room for this extra character. For example, the string defined below
char str[30];
only has room for only 29 (not 30) actually data characters, since a null must appear after the last data character.
This can also be a problem with dynamic allocation. Below is the correct way to allocate a string to the exact size needed to hold a copy of another.
char * copy_str = malloc( strlen(orig_str) + 1);
strcpy(copy_str, orig_str);
The common mistake is to forget to add one to the return value of strlen(). The strlen() function returns a count of the data characters which does not include the null terminator.
This type of error can be very hard to detect. It might not cause any problems or only problems in extreme cases. In the case of dynamic allocation, it might corrupt the heap (the area of the program's memory used for dynamic allocation) and cause the next heap operation (malloc(), free(), etc.) to fail.
4. Input/Output Errors
4.1 Using fgetc(), etc. incorrectly
The fgetc(), getc() and getchar() functions all return back an integer value. For example, the prototype of fgetc() is:
int fgetc( FILE * );
Sometimes this integer value is really a simple character, but there is one very important case where the return value is not a character!
What is this value? EOF A common misconception of students is that files have a special EOF character at the end. There is no special character stored at the end of a file. EOF is an integer error code returned by a function. Here is the wrong way to use fgetc():
int count_line_size( FILE * fp )
{
char ch;
int cnt = 0;
while( (ch = fgetc(fp)) != EOF && ch != '\n')
cnt++;
return cnt;
}
What is wrong with this? The problem occurs in the condition of the while loop. To illustrate, here is the loop rewritten to show what C will do behind the scenes.
while( (int) ( ch = (char) fgetc(fp) ) != EOF && ch != '\n')
cnt++;
The return value of fgetc(fp) is cast to char to store the result into ch. Then the value of ch must be cast back to an int to compare it with EOF. So what? Casting an int value to a char and then back to an int may not give back the original int value. This means in the example above that if fgetc() returns back the EOF value, the casting may change the value so that the comparison later with EOF would be false.
What is the solution? Make the ch variable an int as below:
int count_line_size( FILE * fp )
{
int ch;
int cnt = 0;
while( (ch = fgetc(fp)) != EOF && ch != '\n')
cnt++;
return cnt;
}
Now the only hidden cast is in the second comparison.
while( (ch = fgetc(fp)) != EOF && ch != ((int) '\n') )
cnt++;
This cast has no harmful effects at all! So, the moral of all this is: always use an int variable to store the result of the fgetc(), getc() and getchar().
4.2 Using feof() incorrectly
There is a wide spread misunderstanding of how C's feof() function works. Many programmers use it like Pascal's eof() function. However, C's function works differently!
What's the difference? Pascal's function returns true if the next read will fail because of end of file. C's function returns true if the last function failed. Here's an example of a misuse of feof():
#include
int main()
{
FILE * fp = fopen("test.txt", "r");
char line[100];
while( ! feof(fp) ) {
fgets(line, sizeof(line), fp);
fputs(line, stdout);
}
fclose(fp);
return 0;
}
This program will print out the last line of the input file twice. Why? After the last line is read in and printed out, feof() will still return 0 (false) and the loop will continue. The next fgets() fails and so the line variable holding the contents of the last line is not changed and is printed out again. After this, feof() will return true (since fgets() failed) and the loop ends.
How should this fixed? One way is the following:
#include
int main()
{
FILE * fp = fopen("test.txt", "r");
char line[100];
while( 1 ) {
fgets(line, sizeof(line), fp);
if ( feof(fp) ) /* check for EOF right after fgets() */
break;
fputs(line, stdout);
}
fclose(fp);
return 0;
}
However, this is not the best way. There is really no reason to use feof() at all. C input functions return values that can be used to check for EOF. For example, fgets returns the NULL pointer on EOF. Here's a better version of the program:
#include
int main()
{
FILE * fp = fopen("test.txt", "r");
char line[100];
while( fgets(line, sizeof(line), fp) != NULL )
fputs(line, stdout);
fclose(fp);
return 0;
}
The author has yet to see any student use the feof() function correctly!
Incidently, this discussion also applies to C++ and Java. The eof() method of an istream works just like C's feof().
4.3 Leaving characters in the input buffer
C input (and output) functions buffer data. Buffering stores data in memory and only reads (or writes) the data from (or to) I/O devices when needed. Reading and writing data in big chunks is much more efficient than a byte (or character) at a time. Often the buffering has no effect on programming.
One place where buffering is visible is input using scanf(). The keyboard is usually line buffered. This means that each line input is stored in a buffer. Problems can arise when a program does not process all the data in a line, before it wants to process the next line of input. For example, consider the following code:
int x;
char st[31];
printf("Enter an integer: ");
scanf("%d", &x);
printf("Enter a line of text: ");
fgets(st, 31, stdin);
The fgets() will not read the line of text that is typed in. Instead, it will probably just read an empty line. In fact, the program will not even wait for an input for the fgets() call. Why? The scanf() call reads the characters needed that represent the integer number read in, but it leaves the '\n' in the input buffer. The fgets() then starts reading data from the input buffer. It finds a '\n' and stops without needing any additional keyboard input.
What's the solution? One simple method is to read and dump all the characters from the input buffer until a '\n' after the scanf() call. Since this is something that might be used in lots of places, it makes sense to make this a function. Here is a function that does just this:
/* function dump_line
* This function reads and dumps any remaining characters on the current input
* line of a file.
* Parameter:
* fp - pointer to a FILE to read characters from
* Precondition:
* fp points to a open file
* Postcondition:
* the file referenced by fp is positioned at the end of the next line
* or the end of the file.
*/
void dump_line( FILE * fp )
{
int ch;
while( (ch = fgetc(fp)) != EOF && ch != '\n' )
/* null body */;
}
Here is the code above fixed by using the above function:
int x;
char st[31];
printf("Enter an integer: ");
scanf("%d", &x);
dump_line(stdin);
printf("Enter a line of text: ");
fgets(st, 31, stdin);
One incorrect solution is to use the following:
fflush(stdin);
This will compile but its behavior is undefined by the ANSI C standard. The fflush() function is only meant to be used on streams open for output, not input. This method does seem to work with some C compilers, but is completely unportable! Thus, it should not be used.
4.4 Using the gets() function
Do not use this function! It does not know how many characters can be safely stored in the string passed to it. Thus, if too many are read, memory will be corrupted. Many security bugs that have been exploited on the Internet use this fact! Use the fgets() function instead (and read from stdin). But remember that unlike gets(), fgets() does not discard a terminating \n from the input.
The scanf() functions can also be used dangerously. The %s format can overwrite the destination string. However, it can be used safely by specifying a width. For example, the format %20s will not read more than 20 characters
Sunday, September 12, 2010
2 Egg Problem
Q.
* You are given 2 eggs.
* You have access to a 100-storey building.
* Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.
* You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
* Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process
ANS:
The maximum drops is 14.
take it as n(n+1)/2 is just greater than or equal to 100.so n=14.
Algo:
i=14,j=13
1.drop the egg from ith floor
if egg breaks then
drop egg from (i-j)th floor and then go one floor up and keep droping(until req floor is found)
else
i=i+j
j--
if(j>=1)
goto step 1.
Lets take the case with 16 as the answer
1 + 15 16 if breaks at 16 checks from 1 to 15 in 15 drops
1 + 14 31 if breaks at 31 checks from 17 to 30 in 14 drops
1 + 13 45 .....
1 + 12 58
1 + 11 70
1 + 10 81
1 + 9 91
1 + 8 100 We can easily do in the end as we have enough drops to accomplish the task
Now finding out the optimal one we can see that we could have done it in either 15 or 14 drops only but how can we find the optimal one. From the above table we can see that the optimal one will be needing 0 linear trials in the last step.
So we could write it as
(1+p) + (1+(p-1))+ (1+(p-2)) + .........+ (1+0) >= 100.
Let 1+p=q which is the answer we are looking for
q (q+1)/2 >=100
Solving for 100 you get q=14.
So the answer is: 14
Drop first orb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100... (i.e. move up 14 then 13, then 12 floors, etc) until it breaks (or doesn't at 100).
* You are given 2 eggs.
* You have access to a 100-storey building.
* Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.
* You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
* Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process
ANS:
The maximum drops is 14.
take it as n(n+1)/2 is just greater than or equal to 100.so n=14.
Algo:
i=14,j=13
1.drop the egg from ith floor
if egg breaks then
drop egg from (i-j)th floor and then go one floor up and keep droping(until req floor is found)
else
i=i+j
j--
if(j>=1)
goto step 1.
EXPLANATION:
Lets take the case with 16 as the answer
1 + 15 16 if breaks at 16 checks from 1 to 15 in 15 drops
1 + 14 31 if breaks at 31 checks from 17 to 30 in 14 drops
1 + 13 45 .....
1 + 12 58
1 + 11 70
1 + 10 81
1 + 9 91
1 + 8 100 We can easily do in the end as we have enough drops to accomplish the task
Now finding out the optimal one we can see that we could have done it in either 15 or 14 drops only but how can we find the optimal one. From the above table we can see that the optimal one will be needing 0 linear trials in the last step.
So we could write it as
(1+p) + (1+(p-1))+ (1+(p-2)) + .........+ (1+0) >= 100.
Let 1+p=q which is the answer we are looking for
q (q+1)/2 >=100
Solving for 100 you get q=14.
So the answer is: 14
Drop first orb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100... (i.e. move up 14 then 13, then 12 floors, etc) until it breaks (or doesn't at 100).
Saturday, August 21, 2010
Reverse string by words in c
That is, given a sentence like this
Sachin is a good boy
The in place reverse would be
boy good a is Sachin
First reverse the whole string and then individually reverse the words
Sachin is a good boy
<------------->
yob doog a si nihcaS
<-> <--> <-> <-> <->
boy good a is Sachin
Here is some C code to do the same ....
/*
Algorithm..
1. Reverse whole sentence first.
2. Reverse each word individually.
All the reversing happens in-place.
*/
#include
void rev(char *l, char *r);
int main(int argc, char *argv[])
{
char buf[] = "the world will go on forever";
char *end, *x, *y;
// Reverse the whole sentence first..
for(end=buf; *end; end++);
rev(buf,end-1);
// Now swap each word within sentence...
x = buf-1;
y = buf;
while(x++ <>
{
if(*x == '\0' || *x == ' ')
{
rev(y,x-1);
y = x+1;
}
}
// Now print the final string....
printf("%s\n",buf);
return(0);
}
// Function to reverse a string in place...
void rev(char *l,char *r)
{
char t;
while(l <>
{
t = *l;
*l++ = *r;
*r-- = t;
}
}
Input : I am a good boy
< --
< -------
< ---------
< ------------
< --------------
Output : boy
: boy good
: boy good a
: boy good a am
: boy good a am I
The only problem to this solution is the extra space required for the output and one has to write this code really well as we are traversing the string in the reverse direction and there is no null at the start of the string to know we have reached the start of the string!. One can use the strtok() function to breakup the string into multiple words and rearrange them in the reverse order later.
Create a linked list like
| I | -> | <> | -> | am | -> | <> | -> | a | -> | <> | -> | good | -> | <> | -> | boy | -> | NULL |
Now its a simple question of reversing the linked list!. There are plenty of algorithms to reverse a linked list easily. This also keeps track of the number of spaces between the words. Note that the linked list algorithm, though inefficient, handles multiple spaces between the words really well.
#include "stdio"
#include "stdlib"
#include "string"
/* reverse a string in place, return str */
static char* reverse(char* str)
{
char* left = str;
char* right = left + strlen(str) - 1;
char tmp;
while (left < style="color: rgb(0, 51, 0);"> tmp = *left;
*left++ = *right;
*right-- = tmp;
}
return str;
}
static int reverseWords(
const char* instr, /* in: string of words */
char* outstr) /* out: reversed words */
/* (caller must ensure big enough) */
{int k;
char* p;
char* buf;
*outstr = '\0';
if ((buf = (char*)malloc(strlen(instr)+1)) == NULL) {
fprintf(stderr, "oops, out of memory\n");
return -1;
}
strcpy(buf, instr);
reverse(buf);
if ((p = strtok(buf, " \t")) == NULL) {
free(buf);
return 0;
}
strcpy(outstr, reverse(p));
outstr += strlen(p);
while ((p = strtok(NULL, " \t")) != NULL) {
*outstr++ = ' ';
strcpy(outstr, reverse(p));
outstr += strlen(p);
}
free(buf);
return 0;
}
int main()
{
char instr[256];
char outstr[256];
printf("\n enter a string:");
gets(instr);
reverseWords(instr, outstr);
printf("in='%s' out='%s'\n", instr, outstr);
return 0;
}
:::::::::::::::::::::::::::::::::::::::
/* function prototype for utility function to
reverse a string from begin to end */
void reverse(char *begin, char *end);
/*Function to reverse words*/
void reverseWords(char *s)
{
char *word_begin = s;
char *temp = s; /* temp is for word boundry */
/*STEP 1 of the above algorithm */
while( *temp )
{
temp++;
if (*temp == '\0')
{
reverse(word_begin, temp-1);
}
else if(*temp == ' ')
{
reverse(word_begin, temp-1);
word_begin = temp+1;
}
} /* End of while */
/*STEP 2 of the above algorithm */
reverse(s, temp-1);
}
/* UTILITY FUNCTIONS */
/*Function to reverse any sequence starting with pointer
begin and ending with pointer end */
void reverse(char *begin, char *end)
{
char temp;
while (begin < end )
{
temp = *begin;
*begin++ = *end;
*end-- = temp;
}
}
/* Driver function to test above functions */
int main()
{
char s[] = "i like this program very much";
char *temp = s;
reverseWords(s);
printf("%s", s);
getchar();
return 0;
}
Sachin is a good boy
The in place reverse would be
boy good a is Sachin
Method1
First reverse the whole string and then individually reverse the words
Sachin is a good boy
<------------->
yob doog a si nihcaS
<-> <--> <-> <-> <->
boy good a is Sachin
Here is some C code to do the same ....
/*
Algorithm..
1. Reverse whole sentence first.
2. Reverse each word individually.
All the reversing happens in-place.
*/
#include
void rev(char *l, char *r);
int main(int argc, char *argv[])
{
char buf[] = "the world will go on forever";
char *end, *x, *y;
// Reverse the whole sentence first..
for(end=buf; *end; end++);
rev(buf,end-1);
// Now swap each word within sentence...
x = buf-1;
y = buf;
while(x++ <>
{
if(*x == '\0' || *x == ' ')
{
rev(y,x-1);
y = x+1;
}
}
// Now print the final string....
printf("%s\n",buf);
return(0);
}
// Function to reverse a string in place...
void rev(char *l,char *r)
{
char t;
while(l <>
{
t = *l;
*l++ = *r;
*r-- = t;
}
}
Method2
Another way to do it is, allocate as much memory as the input for the final output. Start from the right of the string and copy the words one by one to the output.
Input : I am a good boy
< --
< -------
< ---------
< ------------
< --------------
Output : boy
: boy good
: boy good a
: boy good a am
: boy good a am I
The only problem to this solution is the extra space required for the output and one has to write this code really well as we are traversing the string in the reverse direction and there is no null at the start of the string to know we have reached the start of the string!. One can use the strtok() function to breakup the string into multiple words and rearrange them in the reverse order later.
Method3
Create a linked list like
| I | -> | <> | -> | am | -> | <> | -> | a | -> | <> | -> | good | -> | <> | -> | boy | -> | NULL |
Now its a simple question of reversing the linked list!. There are plenty of algorithms to reverse a linked list easily. This also keeps track of the number of spaces between the words. Note that the linked list algorithm, though inefficient, handles multiple spaces between the words really well.
#include "stdio"
#include "stdlib"
#include "string"
/* reverse a string in place, return str */
static char* reverse(char* str)
{
char* left = str;
char* right = left + strlen(str) - 1;
char tmp;
while (left < style="color: rgb(0, 51, 0);"> tmp = *left;
*left++ = *right;
*right-- = tmp;
}
return str;
}
static int reverseWords(
const char* instr, /* in: string of words */
char* outstr) /* out: reversed words */
/* (caller must ensure big enough) */
{int k;
char* p;
char* buf;
*outstr = '\0';
if ((buf = (char*)malloc(strlen(instr)+1)) == NULL) {
fprintf(stderr, "oops, out of memory\n");
return -1;
}
strcpy(buf, instr);
reverse(buf);
if ((p = strtok(buf, " \t")) == NULL) {
free(buf);
return 0;
}
strcpy(outstr, reverse(p));
outstr += strlen(p);
while ((p = strtok(NULL, " \t")) != NULL) {
*outstr++ = ' ';
strcpy(outstr, reverse(p));
outstr += strlen(p);
}
free(buf);
return 0;
}
int main()
{
char instr[256];
char outstr[256];
printf("\n enter a string:");
gets(instr);
reverseWords(instr, outstr);
printf("in='%s' out='%s'\n", instr, outstr);
return 0;
}
:::::::::::::::::::::::::::::::::::::::
/* function prototype for utility function to
reverse a string from begin to end */
void reverse(char *begin, char *end);
/*Function to reverse words*/
void reverseWords(char *s)
{
char *word_begin = s;
char *temp = s; /* temp is for word boundry */
/*STEP 1 of the above algorithm */
while( *temp )
{
temp++;
if (*temp == '\0')
{
reverse(word_begin, temp-1);
}
else if(*temp == ' ')
{
reverse(word_begin, temp-1);
word_begin = temp+1;
}
} /* End of while */
/*STEP 2 of the above algorithm */
reverse(s, temp-1);
}
/* UTILITY FUNCTIONS */
/*Function to reverse any sequence starting with pointer
begin and ending with pointer end */
void reverse(char *begin, char *end)
{
char temp;
while (begin < end )
{
temp = *begin;
*begin++ = *end;
*end-- = temp;
}
}
/* Driver function to test above functions */
int main()
{
char s[] = "i like this program very much";
char *temp = s;
reverseWords(s);
printf("%s", s);
getchar();
return 0;
}
Saturday, August 7, 2010
binary tree in c
A normal search across a BST (Binary Search Tree) would look like this
bool BinaryTree::Search (int data )
{
Node *current = this->root;
while ( current != NULL )
{
if (current->data < data)
{
current = current->left;
}
else if (current->data > data)
{
current = current->right;
}
else if ( current->data == data )
{
return true;
}
}
return false;
}
You keep going down the tree, until you find a node whose value is equal to one you are looking for, or you bail out when you hit a leaf (NULL) node. If you look at the number of statements, there is one conditional check on the while, and an average of 1.5 conditional checks inside the loop. That makes it a total of 2.5 checks every iteration. On a tree with a 1000 nodes, that’s 2500 checks.
Let’s see how we can improve this. I am using the sentinel node technique for this purpose. In this case static Node * Leaf;
This is how the search will look like
static Node* Leaf;
bool BinaryTree::Search (int data )
{
Node *current = this->root;
Leaf->data = data;
while ( current->data != lead->data )
{
if (current->data < data)
{
current = current->left;
}
else
{
current = current->right;
}
}
return (current != Leaf);
}
The sentinel is a static node, and while building the tree, you point all the leaf nodes to this sentinel node instead of NULL. Before you start the search, you set the value of the sentinel node to the data you are searching for. This way you are guaranteed to get a hit. You just need to do one extra check at the end to see if the Hit node was a Node in the tree or the sentinel node. If you look at the number of conditional statements in the loop, there is one in the while statement and one inside the loop, that makes it 2 searches every iteration. You just saved half a conditional statement. Don’t underestimate this improvement. E.g. In a 1000 iteration loop you saved 500 checks.
This is extremely useful with large trees or when you are searching the tree several times or any other scenario where this call happens in a hot section.
Subscribe to:
Posts (Atom)