There are many commonly asked questions regarding C programming language. Below are some collected such question-answer examples. The questions are usually related with Turbo C IDE in windows or GCC under Linux environment [not always].
For more such examples, click C_Q&A label.
-------------------------------------------------------------------------------------------------
Data Structures
Radix Sort
This sorting technique is based on the values of the actual digits in the positional representations of the numbers being sorted. Using the decimal base, for example, where the radix is 10, the numbers can be partitioned into ten groups on the sorter. For example, to sort a collection of numbers where each number is a four-digit number, then, All the numbers are first sorted according to the the digit at unit's place.
In the second pass, the numbers are sorted according to the digit at tenth place. In the third pass, the numbers are sorted according to the digit at hundredth place. In the forth and last pass, the numbers are sorted according to the digit at thousandth place.
During each pass, each number is taken in the order in which it appears in partitions from unit's place onwards. When these actions have been performed for each digit, starting with the least significant and ending with most significant, the numbers are sorted. This sorting method is called the radix sort.
Let us take another example. Suppose we have a list of names. To sort these names using radix sort method we will have to classify them into 26 groups The list is first sorted on the first letter of each name, i.e. the names are arranged in 26 classes, where the first class consists of those names that begin with alphabet 'A', the second class consists of those names that begin with alphabet 'B' and so on.
During the second pass each class is alphabetized according to the second letter of the name, and so on.
-------------------------------------------------------------------------------------------------
Exception Handling in C
Consider the following program:
#include <math.h>
void main( )
{
float i ;
i = pow ( -2, 3 ) ;
printf ( "%f", i ) ;
}
int matherr ( struct exception *a )
{
if (a-> type == DOMAIN )
{
if (!strcmp (a-> name, "pow" ))
{
a-> retval = pow ( - ( a -> arg1 ), a -> arg2 ) ;
return 1 ;
}
}
return 0 ;
}
If we pass a negative value in pow( ) function a run time error occurs. If we wish to get the proper output even after passing a negative value in the pow( ) function we must handle the run time error. For this, we can define a function matherr( ) which is declared in the 'math.h' file. In this function we can detect the run-time error and write our code to correct the error. The elements of the exception structure receives the function name and arguments of the function causing the exception.
-------------------------------------------------------------------------------------------------
Data Structures
AVL Trees
For ideal searching in a binary search tree, the heights of the left and right sub-trees of any node should be equal. But, due to random insertions and deletions performed on a binary search tree, it often turns out to be far from ideal. A close approximation to an ideal binary search tree is achievable if it can be ensured that the difference between the heights of the left and the right sub trees of any node in the tree is at most one. A binary search tree in which the difference of heights of the right and left sub-trees of any node is less than or equal to one is known as an AVL tree. AVL tree is also called as Balanced Tree.
The name "AVL Tree" is derived from the names of its inventors who are Adelson-Veilskii and Landi. A node in an AVL tree have a new field to store the "balance factor" of a node which denotes the difference of height between the left and the right sub-trees of the tree rooted at that node. And it can assume one of the three possible values {-1,0,1}.
-------------------------------------------------------------------------------------------------
Unique combinations for a given number
How do I write a program which can generate all possible combinations of numbers from 1 to one less than the given number?
main( )
{
long steps, fval, bstp, cnt1 ;
int num, unit, box[2][13], cnt2, cnt3, cnt4 ;
printf ( "Enter Number " ) ;
scanf ( "%d", &num ) ;
num = num < 1 ? 1 : num > 12 ? 12 : num ;
for ( steps = 1, cnt1 = 2 ; cnt1 <= num ; steps *= cnt1++ ) ;
for ( cnt1 = 1 ; cnt1 <= steps ; cnt1++ )
{
for ( cnt2 = 1 ; cnt2 <= num ; cnt2++ )
box[0][cnt2] = cnt2 ;
for ( fval = steps, bstp = cnt1, cnt2 = 1 ; cnt2 <= num ; cnt2++ )
{
if (bstp == 0)
{
cnt4=num ;
while ( box[0][cnt4] == 0 )
cnt4-- ;
}
else
{
fval /= num - cnt2 + 1 ;
unit = ( bstp + fval - 1 ) / fval ;
bstp %= fval ;
for ( cnt4 = 0, cnt3 = 1 ; cnt3 <= unit ; cnt3++ )
while ( box[0][++cnt4] == 0 ) ;
}
box[1][cnt2] = box[0][cnt4] ;
box[0][cnt4] = 0 ;
}
printf ( "\nSeq.No.%ld:", cnt1 ) ;
for ( cnt2 = 1 ; cnt2 <= num ; cnt2++ )
printf ( " %d", box[1][cnt2] ) ;
}
}
This program computes the total number of steps. But instead of entering into the loop of the first and last combination to be generated it uses a loop of 1 to number of combinations. For example, in case of input being 5 the number of possible combinations would be factorial 5, i.e. 120. The program suffers from the limitation that it cannot generate combinations for input beyond 12 since a long int cannot handle the resulting combinations.
-------------------------------------------------------------------------------------------------
Data Structures
Hashing...
Hashing or hash addressing is a searching technique. Usually, search of an element is carried out via a sequence of comparisons. Hashing differs from this as it is independent of the number of elements n in the collection of data. Here, the address or location of an element is obtained by computing some arithmetic function. Hashing is usually used in file management. The general idea is of using the key to determine the address of a record. For this, a function fun( ) is applied to each key, called the hash function. Some of the popular hash functions are: 'Division' method, 'Midsquare' method, and 'Folding' method. Two records cannot occupy the same position. Such a situation is called a hash collision or a hash clash. There are two basic methods of dealing with a hash clash. The first technique, called rehashing, involves using secondary hash function on the hash key of the item. The rehash function is applied successively until an empty position is found where the item can be inserted. If the hash position of the item is found to be occupied during a search, the rehash function is again used to locate the item. The second technique, called chaining, builds a linked list of all items whose keys hash to the same values. During search, this short linked list is traversed sequentially for the desired key. This technique involves adding an extra link field to each table position.
-------------------------------------------------------------------------------------------------
The following program demonstrates how to get input from the user in graphics mode, echoed in the current colors and font size and font style.
#define ON 1
#define OFF 0
#include <graphics.h>
main( )
{
char nameString[80], ageString[80] ;
int age, gd = DETECT, gm ;
initgraph ( &gd, &gm, "c:\\tc\\bgi" ) ;
setbkcolor ( BLUE ) ;
setcolor ( YELLOW ) ;
settextstyle ( GOTHIC_FONT, HORIZ_DIR, 0 ) ;
moveto ( 0, 0 ) ;
outtext ( "Enter your name: " ) ;
getGrString ( nameString ) ;
moveto ( 0, gety( ) + textheight ( "A" ) ) ;
outtext ( "Name: " ) ;
outtext ( nameString ) ;
moveto ( 0, gety( ) + textheight ( "A" ) ) ;
outtext ( "Press key to exit! " ) ;
getch( ) ;
closegraph( ) ;
restorecrtmode( ) ;
}
getGrString ( char *inputString )
{
int stringIndex = 0, oldColor ;
char ch, outString[2] ;
/* xVal will store the screen position for each char */
int xVal[255] ;
outString[1] = 0 ;
xVal[0] = getx( ) ;
do{
cursor (ON );
ch = getch( ) ;
cursor ( OFF ) ;
if ( ch == 0 ) /* avoid dealing with all special keys */
getch( ) ;
else
{
if (ch == 8)
/* backspace */
{
oldColor = getcolor( ) ;
--stringIndex ;
if ( stringIndex < 0 )
stringIndex = 0 ;
/* move to ( old horz position, current vert position ) */
moveto ( xVal[stringIndex], gety( ) ) ;
setcolor ( getbkcolor( ) ) ;
outString[0] = inputString[stringIndex] ;
outtext ( outString ) ;
moveto ( xVal [stringIndex], gety( ) ) ;
setcolor ( oldColor ) ;
}
else
{
inputString[stringIndex] =ch ;
outString[0] = ch ;
outtext ( outString ) ;
++stringIndex ;
xVal[stringIndex] = getx( ) ;
}
}
}
while ( ch != 13 && ch != 10 ) ;
inputString[stringIndex] = 0 ;
}
cursor (int on )
{
int curX, oldColor ;
/* we'll use an underscore as a cursor */
char uBarStr[2] = { '_', 0 } ;
if ( !on )
{
oldColor = getcolor( ) ;
setcolor ( getbkcolor( ) ) ;
}
/* save horizontal position before drawing cursor */
curX = getx( ) ;
outtext ( uBarStr ) ;
moveto ( curX, gety( ) ) ;
/* if we changed the color to erase cursor, change it back */
if ( !on )
setcolor ( oldColor ) ;
}
The function getGrString( ) echoes graphically the user input and stores it in a buffer, and the function cursor( ) handles the cursor position.
-------------------------------------------------------------------------------------------------
…till next post, bye-bye & take care.
No comments:
Post a Comment