Labels

Sunday, November 6, 2011

Next Greater Element

Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.

Solution:

1) Push the first element to stack.
2) Pick rest of the elements one by one and follow following steps in loop.
....a) Mark the current element as next.
....b) If stack is not empty, then pop an element from stack and compare it with next.
....c) If next is greater than the popped element, then next is the next greater element fot the popped element.
....d) Keep poppoing from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements
....g) If next is smaller than the popped element, then push the popped element back.
3) After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them.


void printNGE(int arr[], int n)
{
int i = 0;
struct stack s;
s.top = -1;
int element, next;
/* push the first element to stack */
push(&s, arr[0]);
// iterate for rest of the elements
for (i=1; i
{
next = arr[i];
if (isEmpty(&s) == false)
{
// if stack is not empty, then pop an element from stack
element = pop(&s);
/* If the popped element is smaller than next, then
a) print the pair
b) keep popping while elements are smaller and
stack is not empty */
while (element < next)
{
printf("\n %d --> %d", element, next);
if(isEmpty(&s) == true)
break;
element = pop(&s);
}
/* If element is greater than next, then push
the element back */
if (element > next)
push(&s, element);
}
/* push next to stack so that we can find
next greater for it */
push(&s, next);
}
/* After iterating over the loop, the remaining
elements in stack do not have the next greater
element, so print -1 for them */
while(isEmpty(&s) == false)
{
element = pop(&s);
next = -1;
printf("\n %d --> %d", element, next);
}
}

A Boolean Matrix Question

Given a boolean matrix mat[M][N] of size M X N, modify it such that if a matrix cell mat[i][j] is 1 (or true) then make all the cells of ith row and jth column as 1.
if a[i][j]=1
then fill a[i][k]=1 where k 0 to N
and fill a[k][j]=1 where k 0 to M

Method 1 (Use two temporary arrays)
1) Create two temporary arrays row[M] and col[N]. Initialize all values of row[] and col[] as 0.
2) Traverse the input matrix mat[M][N]. If you see an entry mat[i][j] as true, then mark row[i] and col[j] as true.
3) Traverse the input matrix mat[M][N] again. For each entry mat[i][j], check the values of row[i] and col[j]. If any of the two values (row[i] or col[j]) is true, then mark mat[i][j] as true.


void modifyMatrix(bool mat[R][C])
{
bool row[R]={0};
bool col[C]={0};
int i, j;
/* Store the rows and columns to be marked as 1 in row[] and col[]
arrays respectively */
for (i = 0; i < R; i++)
{
for (j = 0; j < C; j++)
{
if (mat[i][j] == 1)
{
row[i] = 1;
col[j] = 1;
}
}
}
/* Modify the input matrix mat[] using the above constructed row[] and
col[] arrays */
for (i = 0; i < R; i++)
{
for (j = 0; j < C; j++)
{
if ( row[i] == 1 || col[j] == 1 )
{
mat[i][j] = 1;
}
}
}
}


Method 2 (A Space Optimized Version of Method 1)
This method is a space optimized version of above method 1. This method uses the first row and first column of the input matrix in place of the auxiliary arrays row[] and col[] of method 1. So what we do is: first take care of first row and column and store the info about these two in two flag variables rowFlag and colFlag. Once we have this info, we can use first row and first column as auxiliary arrays and apply method 1 for submatrix (matrix excluding first row and first column) of size (M-1)*(N-1).

1) Scan the first row and set a variable rowFlag to indicate whether we need to set all 1s in first row or not.
2) Scan the first column and set a variable colFlag to indicate whether we need to set all 1s in first column or not.
3) Use first row and first column as the auxiliary arrays row[] and col[] respectively, consider the matrix as submatrix starting from second row and second column and apply method 1.
4) Finally, using rowFlag and colFlag, update first row and first column if needed.

Time Complexity: O(M*N)
Auxiliary Space: O(1)



void modifyMatrix(bool mat[R][C])
{
bool rowFirst;
bool colFirst;
int i, j;
for (i = 0; i < C; i++)
{
if(mat[0][i]){ rowFirst=1; break;
}
for (i = 0; i < R; i++)
{
if(mat[i][o]) { colFirst=1 ; break;}
}
for (i = 1; i < R; i++)
{
for (j = 1; j < C; j++)
{
if (mat[i][j] == 1)
{
mat[i][0] = 1;
mat[0][j] = 1;
}
}
}
for (i = 1; i < R; i++)
{
for (j = 1; j < C; j++)
{
if ( mat[i][0] == 1 || mat[0][j] == 1 )
{
mat[i][j] = 1;
}
}
}

if(rowFirst)
for (i = 0; i < R; i++)
mat[0][i]=1;
if(colFirst)
for (i = 0; i < C; i++)
mat[i][0]=1;
}

Wednesday, June 29, 2011

* Find duplicates in O(n) time and O(1) extra space

/*Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) and using only constant memory space.*/

#include "stdio.h"

#include"stdlib.h"
void printRepeating(int arr[], int size)
{
int i,index=0;
printf("The repeating elements are: \n");
for(i = 0; i < size; i++)
{
index=abs(arr[i])%size;
if(arr[index] == 0)
arr[index]=-size;
else if(arr[index]>0 && arr[index]<size)
arr[index] = -arr[index];
else if(arr[index]<0)
{
printf(" %d ", abs(arr[i]));
arr[index]=-arr[index];
arr[index]+=size;
}
}
//restore previous array
for(i=0;i <size;i++)
arr[i]=abs(arr[i])%size;
}

int main()
{
int arr[] = {1, 1,1,1,1,1,2,2,3,0,0,0};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;
}

Friday, January 28, 2011

Write a C program to sort a stack in ascending order without using extra space

Write a C program to sort a stack in ascending order. You should not
make any assumptions about how the stack is implemented. The following
are the only
functions that should be used to write this program:
Push | Pop | Top | IsEmpty | IsFull

Method 1: Recursion

void sort(stack)
{
type x;

if (!isEmpty(stack)) {
x = pop(stack);
sort(stack);
insert(x, stack);
}
}

void insert(x, stack)
{
type y;

if (!isEmpty(stack) && top(stack) .<. x) y = pop(stack);
insert(x, stack);
push(y, stack);
} else {
push(x, stack);
}
}


Method:2 Iterative use one more stack
void sort_stack(Stack * src, Stack * dest)
{
while (!src->IsEmpty())
{
Int tmp = src->Pop();
while(!dest->IsEmpty() && dest->Top() > tmp)
{
src->Push(dest->Pop());
}
dest->Push(tmp);
}


Methode 3:
ascending(stack *s, int top){
IsEmpty(s){
push(top);
return;
}
i = pop(s);
if(i .<. top){
ascending(s, top);
push(i);
}
else{
ascending(s, i);
push(top);
}
}




Tuesday, January 25, 2011

What do lvalue and rvalue mean?

What do lvalue and rvalue mean?
An lvalue is an expression that could appear on the left-hand sign of an assignment (An object that has a location). An rvalue is any
expression that has a value (and that can appear on the right-hand sign of an assignment).
The lvalue refers to the left-hand side of an assignment expression. It must always evaluate to a memory location. The rvalue represents the
right-hand side of an assignment expression; it may have any meaningful combination of variables and constants.
Is an array an expression to which we can assign a value?
An lvalue was defined as an expression to which a value can be assigned. The answer to this question is no, because an array is composed
of several separate array elements that cannot be treated as a whole for assignment purposes.
The following statement is therefore illegal:
int x[5], y[5];
x = y;
Additionally, you might want to copy the whole array all at once. You can do so using a library function such as the memcpy() function, which
is shown here:
memcpy(x, y, sizeof(y));
It should be noted here that unlike arrays, structures can be treated as lvalues. Thus, you can assign one
structure variable to another structure variable of the same type, such as this:
typedef struct t_name
{
char last_name[25];
char first_name[15];
char middle_init[2];
} NAME;
...
NAME my_name, your_name;
...
your_name = my_name;

Whats wrong with the expression a[i]=i++; ? Whats a sequence point?

Whats wrong with the expression a[i]=i++; ? Whats a sequence point?
Although its surprising that an expression like i=i+1; is completely valid, something like a[i]=i++; is not. This is because all accesses to an
element must be to change the value of that variable. In the statement a[i]=i++; , the access to i is not for itself, but for a[i] and so its
invalid. On similar lines, i=i++; or i=++i; are invalid. If you want to increment the value of i, use i=i+1; or i+=1; or i++; or ++i; and not some
combination.
A sequence point is a state in time (just after the evaluation of a full expression, or at the ||, &&, ?:, or comma operators, or just before a
call to a function) at which there are no side effects.
The ANSI/ISO C Standard states that
Between the previous and next sequence point an object shall have its stored
value modified at most once by the evaluation of an expression. Furthermore,
the prior value shall be accessed only to determine the value to be stored.
At each sequence point, the side effects of all previous expressions will be completed. This is why you cannot rely on expressions such as
a[i] = i++;, because there is no sequence point specified for the assignment, increment or index operators, you don't know when the effect
of the increment on i occurs.
The sequence points laid down in the Standard are the following:

1.The point of calling a function, after evaluating its arguments.
2.The end of the first operand of the && operator.
3.The end of the first operand of the || operator.
4.The end of the first operand of the ?: conditional operator.
5.The end of the each operand of the comma operator.
6.Completing the evaluation of a full expression. They are the following:
1-Evaluating the initializer of an auto object.
2-The expression in an ?ordinary? statement?an expression followed by semicolon.
3-The controlling expressions in do, while, if, switch or for statements.
4-The other two expressions in a for statement.
5-The expression in a return statement.

Sunday, January 23, 2011

Segmentation fault, access violation, core dump and Bus error

What do Segmentation fault, access violation, core dump and Bus error mean?
The segmentation fault, core dump, bus error kind of errors usually mean that the program tried to access memory it shouldn't have.
Probable causes are overflow of local arrays; improper use of null pointers; corruption of the malloc() data structures; mismatched function
arguments (specially variable argument functions like sprintf(), fprintf(), scanf(), printf()).
For example, the following code is a sure shot way of inviting a segmentation fault in your program:
sprintf(buffer,"%s %d","Hello");
So whats the difference between a bus error and a segmentation fault?
A bus error is a fatal failure in the execution of a machine language instruction resulting from the processor
detecting an anomalous condition on its bus.
Such conditions include:
-
-
-
-
-
Invalid address alignment (accessing a multi-byte number at an odd address).
Accessing a memory location outside its address space.
Accessing a physical address that does not correspond to any device.
Out-of-bounds array references.
References through uninitialized or mangled pointers.
A bus error triggers a processor-level exception, which Unix translates into a "SIGBUS" signal,which if not caught, will terminate the current
process. It looks like a SIGSEGV, but the difference between the two is that SIGSEGV indicates an invalid access to valid
memory, while SIGBUS indicates an access to an invalid address.
Bus errors mean different thing on different machines. On systems such as Sparcs a bus error occurs when you access memory that is not
positioned correctly.
Maybe an example will help to understand how a bus error occurs
#include " stdlib.h"
#include " stdio.h"
int main(void)
{
char *c;
long int *i;
c = (char *) malloc(sizeof(char));
c++;
i = (long int *)c;
printf("%ld", *i);
return 0;
}
On Sparc machines long ints have to be at addresses that are multiples of four (because they are four bytes long), while chars do not (they
are only one byte long so they can be put anywhere). The example code uses the char to create an invalid address, and assigns the long int
to the invalid address. This causes a bus error when the long int is dereferenced.
A segfault occurs when a process tries to access memory that it is not allowed to, such as the memory at address 0 (where NULL usually
points). It is easy to get a segfault, such as the following example, which dereferences NULL.
#include " stdio.h"
int main(void)
{
char *p;
p = NULL;
putchar(*p);
return 0;
}

Friday, January 21, 2011

Write a C program to implement a Generic Linked List

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);
}

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;
}

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.

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