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
Comparison Trees...
The comparison trees also called decision tree or search tree of an algorithm, is obtained by tracing through the actions of the algorithm, representing each comparison of keys by a vertex of the tree (which we draw as a circle). Inside the circle we put the index of the key against which we are comparing the target key. Branches (lines) drawn down from the circle represent the possible outcomes of the comparison and are labeled accordingly. When the algorithm terminates, we put either F (for failure) or the location where the target is found at the end of the appropriate branch, which we call a leaf, and draw as a square. Leaves are also sometimes called end vertices or external vertices of the tree. The remaining vertices are called the internal vertices of the tree. The comparison tree for sequential search is especially simple.
-------------------------------------------------------------------------------------------------
Suppose we have a floating-point number with higher precision say 12.126487687 and we wish it to be printed with only precision up to two decimal places. How can I do this?
Ans.
This can achieved through the use of suppression char '*' in the format string of printf( )
which is shown in the following program.
main( )
{
int p = 2 ;
float n = 12.126487687 ;
printf ( "%.*f",p, n ) ;
}
-------------------------------------------------------------------------------------------------
Spawning
All programs that we execute from DOS prompt can be thought of as children of COMMAND.COM. Thus, the program that we execute is a child process, whereas COMMAND.COM running in memory is its parent. The process of a parent process giving
birth to a child process is known as 'spawning'. If the spawned program so desires, it may in turn spawn children of its own, which then execute and return control to their parent. Who is the parent of COMMAND.COM? COMMAND.COM itself.
We can trace the ancestors of our program using the field Parent Process ID (PID) present at offset 0x16 in the Program Segment Prefix (PSP). To trace this ancestry our program should first locate its PSP, extract the parent process ID from it and then use this to find PSP of the parent.
This process can be repeated till we reach COMMAND.COM (process ID of COMMAND.COM is its own PSP), the father of all processes. Here is a program which achieves this...
/* SPAWN.C */
#include "dos.h"
unsigned oldpsp, newpsp, far *eb_seg, i ;
char far *eb_ptr ;
main( )
{
oldpsp = _psp ;
while ( 1 )
{
printf ( "\n" ) ;
printname ( oldpsp ) ;
printf ( " spawned by " ) ;
newpsp = * ( ( unsigned far * ) MK_FP ( oldpsp, 0x16 ) ) ;
if ( * ( ( unsigned * ) MK_FP ( newpsp, 0x16 ) ) == newpsp )
break ;
else
oldpsp = newpsp ;
printname ( newpsp ) ;
}
printf ( "%-20s (%04X)", "COMMAND.COM", newpsp ) ;
}
printname ( unsigned lpsp )
{
char drive[5], dir[68], name[13], ext[5] ;
eb_seg = ( unsigned far * ) MK_FP ( lpsp, 0x2C ) ;
eb_ptr = MK_FP ( *eb_seg, 0 ) ;
i = 0 ;
while ( 1 )
{
if ( eb_ptr[i] == 0 )
{
if ( eb_ptr[i + 1] == 0 && eb_ptr[i + 2] == 1 )
{
i+= 4 ;
break;
}
}
i++;
}
fnsplit ( eb_ptr + i, drive, dir, name, ext ) ;
strcat ( name, ext ) ;
printf ( "%-20s (%04X)", name, oldpsp ) ;
}
On running the program from within TC the output obtained is shown below. SPWAN.EXE
(58A9) spawned by TC.EXE (0672) TC.EXE (0672) spawned by COMMAND.COM (05B8).
The program simply copies its own process ID in the variable oldpsp and then uses it to
extract its own filename from its environment block. This is done by the function printname( ).
The value in oldpsp is then used to retrieve the parent's PID in newpsp. From there the
program loops reporting the values of oldpsp, newpsp and the corresponding file names until the program reaches COMMAND.COM.
The printname( ) function first locates the environment block of the program and then extracts the file name from the environment block. The fnsplit( ) function has been used to eliminate the path present prior to the file name. Do not run the program from command line since it would give you only one level of ancestry.
-------------------------------------------------------------------------------------------------
Data Structures
Choosing the data structures to be used for information retrieval.
For problems of information retrieval, consider the size, number, and location of the records along with the type and structure of the keys while choosing the data structures to be used. For small records, high speed internal memory will be used, and binary search trees will likely prove adequate. For information retrieval from disk files, methods employing multi-way branching, such as trees, Btrees, and hash tables, will usually be superior. Tries are particularly suited to applications where the keys are structured as a sequence of symbols and where the set of keys is relatively dense in the set of all possible keys. For other applications, methods that treat the key as a single unit will often prove superior. B-trees, together with various generalization and extensions, can be usefully applied to many problems concerned with external information retrieval.
-------------------------------------------------------------------------------------------------
Variably Dimensioned Arrays
While dealing with Scientific or Engineering problems one is often required to make use of multi-dimensioned array. However, when it comes to passing multidimensional arrays to a function C is found wanting. This is because the C compiler wants to know the size of all but the first dimension of any array passed to a function. For instance, we can define a function compute (int n, float x[] ), but not compute (int n, x[][]).
Thus, C can deal with variably dimensioned 1-D arrays, but when an array has more than one dimension, the C compiler has to know the size of the last dimensions expressed as a constant. This problem has long been recognized, and some of the solutions that are often used are:
Declare the arrays in the functions to be big enough to tackle all possible situations. This can lead to a wastage of lot of precious memory in most cases. Another solution is to construct multiple-dimension array as an array of pointers. For example, a matrix (2-D array) of floats can be declared as a 1-D array of float pointers, with each element pointing to an array of floats. The problem with this method is that the calling function has to define all arrays in this fashion. This means that any other computations done on the arrays must take this special structure into account.
Another easy solution, though seldom used, exists. This is based on the following method:
Pass the array to the function as though it is a pointer to an array of floats (or the appropriate data type), no matter how many dimensions the array actually has, along with the dimensions of the array.
Reference individual array elements as offsets from this pointer.
Write your algorithm so that array elements are accessed in storage order. The following program for multiplying two matrices illustrates this procedure.
# define M 3
# define N 2
# define P 4
float a[M][N], b[N][P], c[M][P] ;
void mulmat ( int, int, int, float*, float*, float* ) ;
main( )
{
int i, j;
for ( i = 0 ; i < M ; i++ )
for ( j = 0 ; j < N ; j++ )
a[i][j] = i + j ;
for ( i = 0 ; i < N ; i++ )
for ( j = 0 ; j < P ; j++ )
b[i][j] = i + j ;
mulmat ( M, N, P, a, b, c ) ;
for ( i = 0 ; i < M ; i++ )
{
printf ( "\n" ) ;
for ( j = 0 ; j < P ; j++ )
printf ( "%f\t", c[i][j] ) ;
}
}
void mulmat ( int m, int n, int p, float *a, float *b, float *c )
{
float *ptrtob, *ptrtoc ;
int i, j, k, nc ;
/* set all elements of matrix c to 0 */
for ( i = 0 ; i < m * p ; i++ )
*( c + i ) = 0 ;
for ( i = 0 ; i < m ; i++ )
{
ptrtob = b ;
for ( k = 0 ; k < n ; k++ )
{
ptrtoc = c ;
for ( j = 0 ; j < p ; j++ )
*ptrtoc++ += *a * *ptrtob++ ;
a++ ;
}
c+= p ;
}
}
We know that C stores array elements in a row-major order. Hence to ensure that the elements are accessed in the storage order the above program uses a variation of the normal matrix-multiplication procedure. The pseudo code for this is given below:
for i = 1 to m
for j = 1 to p
c[i][j] = 0
end
for k = 1 to n
for j = 1 to p
c[i][j] = c[i][j] + a[i][k] * b[k][j]
end
end
end
-------------------------------------------------------------------------------------------------
…till next post, bye-bye & take care.
No comments:
Post a Comment