Tech Mahindra Frequently Asked C Language Interview Questions Answers
Which Is Better To Use A Macro Or A Function?
The
depends on the situation you are writing code for. Macros have the distinct advantage of being more efficient (and faster) than functions, because their corresponding code is inserted directly into your source code at the point where the macro is called. There is no overhead involved in using a macro like there is in placing a call to a function. However, macros are generally small and cannot handle large, complex coding constructs. A function is more suited for this type of situation. Additionally, macros are expanded inline, which means that the code is replicated for each occurrence of a macro. Your code therefore could be somewhat larger when you use macros than if you were to use functions. Thus, the choice between using a macro and using a function is one of deciding between the tradeoff of faster program speed versus smaller program size. Generally, you should use macros to replace small, repeatable code sections, and you should use functions for larger coding tasks that might require several lines of code.
How Are Portions Of A Program Disabled In Demo Versions?
If you are distributing a demo version of your program, the preprocessor can be used to enable or disable portions of your program. The following portion of code shows how this task is accomplished, using the preprocessor directives #if and #endif
int save document(char* doc_name)
{
#if DEMO_VERSION
printf(“Sorry! You can’t save documents using the DEMO
version of this program!n”);
return(0);
#endif
What Is The Easiest Sorting Method To Use?
The
is the standard library function qsort(). It’s the easiest sort by far for several reasons
It is already written.
It is already debugged.
It has been optimized as much as possible (usually).
Void qsort(void *buf, size_t num, size_t size, int (*comp)
(const void *ele1, const void *ele2));
Which Is The Quickest Sorting Method To Use?
The
depends on what you mean by quickest. For most sorting problems, it just doesn’t matter how quick the sort is because it is done infrequently or other operations take significantly more time anyway. Even in cases in which sorting speed is of the essence, there is no one
. It depends on not only the size and nature of the data, but also the likely order. No algorithm is best in all cases.
There are three sorting methods in this author’s “toolbox” that are all very fast and that are useful in different situations. Those methods are quick sort, merge sort, and radix sort.
The Quick Sort :The quick sort algorithm is of the “divide and conquer” type. That means it works by reducing a sorting problem into several easier sorting problems and solving each of them. A “dividing” value is chosen from the input data, and the data is partitioned into three sets: elements that belong before the dividing value, the value itself, and elements that come after the dividing value. The partitioning is performed by exchanging elements that are in the first set but belong in the third with elements that are in the third set but belong in the first Elements that are equal to the dividing element can be put in any of the three sets—the algorithm will still work properly.
The Merge Sort: The merge sort is a “divide and conquer” sort as well. It works by considering the data to be sorted as a sequence of already-sorted lists (in the worst case, each list is one element long). Adjacent sorted lists are merged into larger sorted lists until there is a single sorted list containing all the elements. The merge sort is good at sorting lists and other data structures that are not in arrays, and it can be used to sort things that don’t fit into memory. It also can be implemented as a stable sort.
The Radix Sort : The radix sort takes a list of integers and puts each element on a smaller list, depending on the value of its least significant byte. Then the small lists are concatenated, and the process is repeated for each more significant byte until the list is sorted. The radix sort is simpler to implement on fixed-length data such as ints.
What Is The Benefit Of Using Const For Declaring Constants?
The benefit of using the const keyword is that the compiler might be able to make optimizations based on the knowledge that the value of the variable will not change. In addition, the compiler will try to ensure that the values won’t be changed inadvertently.
Of course, the same benefits apply to #defined constants. The reason to use const rather than #define to define a constant is that a const variable can be of any type (such as a struct, which can’t be represented by a #defined constant). Also, because a const variable is a real variable, it has an address that can be used, if needed, and it resides in only one place in memory.
Is It Acceptable To Declare/define A Variable In A C Header?
A global variable that must be accessed from more than one file can and should be declared in a header file. In addition, such a variable must be defined in one source file.
Variables should not be defined in header files, because the header file can be included in multiple source files, which would cause multiple definitions of the variable. The ANSI C standard will allow multiple external definitions, provided that there is only one initialization. But because there’s really no advantage to using this feature, it’s probably best to avoid it and maintain a higher level of portability.
“Global” variables that do not have to be accessed from more than one file should be declared static and should not appear in a header file.
When Should A Type Cast Be Used?
There are two situations in which to use a type cast. The first use is to change the type of an operand to an arithmetic operation so that the operation will be performed properly.
The second case is to cast pointer types to and from void * in order to interface with functions that expect or return void pointers. For example, the following line type casts the return value of the call to malloc() to be a pointer to a foo structure.
struct foo *p = (struct foo *) malloc(sizeof(struct foo));
Give The Benefit Of Using #define To Declare A Constant?
Using the #define method of declaring a constant enables you to declare a constant in one place and use it throughout your program. This helps make your programs more maintainable, because you need to maintain only the #define statement and not several instances of individual constants throughout your program. For instance, if your program used the value of pi (approximately 3.14159) several times, you might want to declare a constant for pi as follows
#define PI 3.14159
Using the #define method of declaring a constant is probably the most familiar way of declaring constants to traditional C programmers. Besides being the most common method of declaring constants, it also takes up the least memory. Constants defined in this manner are simply placed directly into your source code, with no variable space allocated in memory. Unfortunately, this is one reason why most debuggers cannot inspect constants created using the #define method.
How To Avoid Including A Header More Than Once?
One easy technique to avoid multiple inclusions of the same header is to use the #ifndef and #define preprocessor directives. When you create a header for your program, you can #define a symbolic name that is unique to that header. You can use the conditional preprocessor directive named #ifndef to check whether that symbolic name has already been assigned. If it is assigned, you should not include the header, because it has already been preprocessed. If it is not defined, you should define it to avoid any further inclusions of the header. The following header illustrates this technique
#ifndef _FILENAME_H
#define _FILENAME_H
#define VER_NUM “1.00.00”
#define REL_DATE “08/01/94”
#if _ _WINDOWS_ _
#define OS_VER “WINDOWS”
#else
#define OS_VER “DOS”
#endif
#endif
When the preprocessor encounters this header, it first checks to see whether _FILENAME_H has been defined. If it hasn’t been defined, the header has not been included yet, and the _FILENAME_H symbolic name is defined. Then, the rest of the header is parsed until the last #endif is encountered, signaling the end of the conditional #ifndef _FILENAME_H statement. Substitute the actual name of the header file for “FILENAME” in the preceding example to make it applicable for your programs.
Differentiate Between Arrays And Pointers?
Pointers are used to manipulate data using the address. Pointers use * operator to access the data pointed to by them Arrays use subscripted variables to access and manipulate data. Array variables can be equivalently written using pointer expression.
Mention The Purpose Of Realloc ( )?
The function realloc (ptr,n) uses two arguments. The first argument ptr is a pointer to a block of memory for which the size is to be altered. The second argument n specifies the new size. The size may be increased or decreased. If n is greater than the old size and if sufficient space is not available subsequent to the old region, the function realloc ( ) may create a new region and all the old data are moved to the new region.
Describe Static Memory Allocation And Dynamic Memory Allocation?
Static memory allocation: The compiler allocates the required memory space for a declared variable. By using the address of operator, the reserved address is obtained and this address may be assigned to a pointer variable. Since most of the declared variable has static memory, this way of assigning pointer value to a pointer variable is known as static memory allocation. Memory is assigned during compilation time. Dynamic memory allocation: It uses functions such as malloc ( ) or calloc ( ) to get memory dynamically. If these functions are used to get memory dynamically and the values returned by these functions are assigned to pointer variables, such assignments are known as dynamic memory allocation. Memory is assigned during run time.
How Are Pointer Variables Initialized?
Pointer variable are initialized by one of the following two ways
Static memory allocation
Dynamic memory allocation
What Is A Pointer Variable?
A pointer variable is a variable that may contain the address of another variable or any valid address in the memory.
Differentiate Between Text And Binary Modes?
Streams can be classified into two types: text streams and binary streams. Text streams are interpreted, with a maximum length of 255 characters. With text streams, carriage return/line feed combinations are translated to the newline n character and vice versa. Binary streams are uninterpreted and are treated one byte at a time with no translation of characters. Typically, a text stream would be used for reading and writing standard text files, printing output to the screen or printer, or receiving input from the keyboard.
A binary text stream would typically be used for reading and writing binary files such as graphics or word processing documents, reading mouse input, or reading and writing to the modem.
How To Restore A Redirected Standard Stream?
The preceding example showed how you can redirect a standard stream from within your program. But what if later in your program you wanted to restore the standard stream to its original state? By using the standard C library functions named dup() and fdopen(), you can restore a standard stream such as stdout to its original state.
The dup() function duplicates a file handle. You can use the dup() function to save the file handle corresponding to the stdout standard stream. The fdopen() function opens a stream that has been duplicated with the dup() function.
How To Search For Data In A Linked List?
Unfortunately, the only way to search a linked list is with a linear search, because the only way a linked list’s members can be accessed is sequentially. Sometimes it is quicker to take the data from a linked list and store it in a different data structure so that searches can be more efficient.
How To Sort A Linked List?
Both the merge sort and the radix sort are good sorting algorithms to use for linked lists.
What Do You Mean By Hashing?
To hash means to grind up, and that’s essentially what hashing is all about. The heart of a hashing algorithm is a hash function that takes your nice, neat data and grinds it into some random-looking integer.
The idea behind hashing is that some data either has no inherent ordering (such as images) or is expensive to compare (such as images). If the data has no inherent ordering, you can’t perform comparison searches.
If the data is expensive to compare, the number of comparisons used even by a binary search might be too many. So instead of looking at the data themselves, you’ll condense (hash) the data to an integer (its hash value) and keep all the data with the same hash value in the same place. This task is carried out by using the hash value as an index into an array. To search for an item, you simply hash it and look at all the data whose hash values match that of the data you’re looking for. This technique greatly lessens the number of items you have to look at. If the parameters are set up with care and enough storage is available for the hash table, the number of comparisons needed to find an item can be made arbitrarily close to one.
One aspect that affects the efficiency of a hashing implementation is the hash function itself. It should ideally distribute data randomly throughout the entire hash table, to reduce the likelihood of collisions. Collisions occur when two different keys have the same hash value. There are two ways to resolve this problem. In “open addressing,” the collision is resolved by the choosing of another position in the hash table for the element inserted later. When the hash table is searched, if the entry is not found at its hashed position in the table, the search continues checking until either the element is found or an empty position in the table is found.
The second method of resolving a hash collision is called “chaining.” In this method, a “bucket” or linked list holds all the elements whose keys hash to the same value. When the hash table is searched, the list must be searched linearly.
Which Is The Quickest Searching Method To Use?
A binary search, such as bsearch() performs, is much faster than a linear search. A hashing algorithm can provide even faster searching. One particularly interesting and fast method for searching is to keep the data in a “digital trie.” A digital trie offers the prospect of being able to search for an item in essentially a constant amount of time, independent of how many items are in the data set.
A digital trie combines aspects of binary searching, radix searching, and hashing. The term “digital trie” refers to the data structure used to hold the items to be searched. It is a multilevel data structure that branches N ways at each level.
How To Determine The Maximum Value That A Numeric Variable Can Hold?
For integral types, on a machine that uses two’s complement arithmetic (which is just about any machine you’re likely to use), a signed type can hold numbers from –2(number of bits – 1) to +2(number of bits – 1) – 1. An unsigned type can hold values from 0 to +2(number of bits) – 1. For instance, a 16-bit signed integer can hold numbers from –2^15 (–32768) to +2^15 – 1 (32767).
Can A Variable Be Both Const And Volatile?
Yes. The const modifier means that this code cannot change the value of the variable, but that does not mean that the value cannot be changed by means outside this code. For instance, in the example in FAQ 8, the timer structure was accessed through a volatile const pointer. The function itself did not change the value of the timer, so it was declared const. However, the value was changed by hardware on the computer, so it was declared volatile. If a variable is both const and volatile, the two modifiers can appear in either order.
When Does The Register Modifier Be Used? Does It Really Help?
The register modifier hints to the compiler that the variable will be heavily used and should be kept in the CPU’s registers, if possible, so that it can be accessed faster. There are several restrictions on the use of the register modifier.
First, the variable must be of a type that can be held in the CPU’s register. This usually means a single value of a size less than or equal to the size of an integer. Some machines have registers that can hold floating-point numbers as well. Second, because the variable might not be stored in memory, its address cannot be taken with the unary & operator. An attempt to do so is flagged as an error by the compiler. Some additional rules affect how useful the register modifier is. Because the number of registers is limited, and because some registers can hold only certain types of data (such as pointers or floating-point numbers), the number and types of register modifiers that will actually have any effect are dependent on what machine the program will run on. Any additional register modifiers are silently ignored by the compiler.
Also, in some cases, it might actually be slower to keep a variable in a register because that register then becomes unavailable for other purposes or because the variable isn’t used enough to justify the overhead of loading and storing it.
So when should the register modifier be used? The
is never, with most modern compilers. Early C compilers did not keep any variables in registers unless directed to do so, and the register modifier was a valuable addition to the language. C compiler design has advanced to the point, however, where the compiler will usually make better decisions than the programmer about which variables should be stored in registers. In fact, many compilers actually ignore the register modifier, which is perfectly legal, because it is only a hint and not a directive.
What Is The Benefit Of Using An Enum Rather Than A #define Constant?
The use of an enumeration constant (enum) has many advantages over using the traditional symbolic constant style of #define. These advantages include a lower maintenance requirement, improved program readability, and better debugging capability.
The first advantage is that enumerated constants are generated automatically by the compiler. Conversely, symbolic constants must be manually assigned values by the programmer. For instance, if you had an enumerated constant type for error codes that could occur in your program, your enum definition could look something like this
enum Error_Code
{
OUT_OF_MEMORY,
INSUFFICIENT_DISK_SPACE,
LOGIC_ERROR,
FILE_NOT_FOUND
};
In the preceding example, OUT_OF_MEMORY is automatically assigned the value of 0 (zero) by the compiler because it appears first in the definition. The compiler then continues to automatically assign numbers to the enumerated constants, making INSUFFICIENT_DISK_SPACE equal to 1, LOGIC_ERROR equal to 2, and FILE_NOT_FOUND equal to 3, so on. If you were to approach the same example by using symbolic constants, your code would look something like this
#define OUT_OF_MEMORY 0
#define INSUFFICIENT_DISK_SPACE 1
#define LOGIC_ERROR 2
#define FILE_NOT_FOUND 3
values by the programmer. Each of the two methods arrives at the same result: four constants assigned numeric values to represent error codes. Consider the maintenance required, however, if you were to add two constants to represent the error codes DRIVE_NOT_READY and CORRUPT_FILE. Using the enumeration constant method, you simply would put these two constants anywhere in the enum definition. The compiler would generate two unique values for these constants. Using the symbolic constant method, you would have to manually assign two new numbers to these constants. Additionally, you would want to ensure that the numbers you assign to these constants are unique.
Another advantage of using the enumeration constant method is that your programs are more readable and thus can be understood better by others who might have to update your program later.
A third advantage to using enumeration constants is that some symbolic debuggers can print the value of an enumeration constant. Conversely, most symbolic debuggers cannot print the value of a symbolic constant. This can be an enormous help in debugging your program, because if your program is stopped at a line that uses an enum, you can simply inspect that constant and instantly know its value. On the other hand, because most debuggers cannot print #define values, you would most likely have to search for that value by manually looking it up in a header file.
Can A File Other Than A .h File Be Included With #include?
The preprocessor will include whatever file you specify in your #include statement. Therefore, if you have the line
#include <macros.inc>
in your program, the file macros.inc will be included in your precompiled program. It is, however, unusual programming practice to put any file that does not have a .h or .hpp extension in an
#include statement.
You should always put a .h extension on any of your C files you are going to include. This method makes it easier for you and others to identify which files are being used for preprocessing purposes. For instance, someone modifying or debugging your program might not know to look at the macros.inc file for macro definitions. That person might try in vain by searching all files with .h extensions and come up empty. If your file had been named macros.h, the search would have included the macros.h file, and the searcher would have been able to see what macros you defined in it.
Which Is Better To Use A Macro Or A Function?
The
depends on the situation you are writing code for. Macros have the distinct advantage of being more efficient (and faster) than functions, because their corresponding code is inserted directly into your source code at the point where the macro is called. There is no overhead involved in using a macro like there is in placing a call to a function. However, macros are generally small and cannot handle large, complex coding constructs. A function is more suited for this type of situation. Additionally, macros are expanded inline, which means that the code is replicated for each occurrence of a macro. Your code therefore could be somewhat larger when you use macros than if you were to use functions. Thus, the choice between using a macro and using a function is one of deciding between the tradeoff of faster program speed versus smaller program size. Generally, you should use macros to replace small, repeatable code sections, and you should use functions for larger coding tasks that might require several lines of code.
How Are Portions Of A Program Disabled In Demo Versions?
If you are distributing a demo version of your program, the preprocessor can be used to enable or disable portions of your program. The following portion of code shows how this task is accomplished, using the preprocessor directives #if and #endif
int save document(char* doc_name)
{
#if DEMO_VERSION
printf(“Sorry! You can’t save documents using the DEMO
version of this program!n”);
return(0);
#endif
What Is The Easiest Sorting Method To Use?
The
is the standard library function qsort(). It’s the easiest sort by far for several reasons
It is already written.
It is already debugged.
It has been optimized as much as possible (usually).
Void qsort(void *buf, size_t num, size_t size, int (*comp)
(const void *ele1, const void *ele2));
Which Is The Quickest Sorting Method To Use?
The
depends on what you mean by quickest. For most sorting problems, it just doesn’t matter how quick the sort is because it is done infrequently or other operations take significantly more time anyway. Even in cases in which sorting speed is of the essence, there is no one
. It depends on not only the size and nature of the data, but also the likely order. No algorithm is best in all cases.
There are three sorting methods in this author’s “toolbox” that are all very fast and that are useful in different situations. Those methods are quick sort, merge sort, and radix sort.
The Quick Sort :The quick sort algorithm is of the “divide and conquer” type. That means it works by reducing a sorting problem into several easier sorting problems and solving each of them. A “dividing” value is chosen from the input data, and the data is partitioned into three sets: elements that belong before the dividing value, the value itself, and elements that come after the dividing value. The partitioning is performed by exchanging elements that are in the first set but belong in the third with elements that are in the third set but belong in the first Elements that are equal to the dividing element can be put in any of the three sets—the algorithm will still work properly.
The Merge Sort: The merge sort is a “divide and conquer” sort as well. It works by considering the data to be sorted as a sequence of already-sorted lists (in the worst case, each list is one element long). Adjacent sorted lists are merged into larger sorted lists until there is a single sorted list containing all the elements. The merge sort is good at sorting lists and other data structures that are not in arrays, and it can be used to sort things that don’t fit into memory. It also can be implemented as a stable sort.
The Radix Sort : The radix sort takes a list of integers and puts each element on a smaller list, depending on the value of its least significant byte. Then the small lists are concatenated, and the process is repeated for each more significant byte until the list is sorted. The radix sort is simpler to implement on fixed-length data such as ints.
What Is The Benefit Of Using Const For Declaring Constants?
The benefit of using the const keyword is that the compiler might be able to make optimizations based on the knowledge that the value of the variable will not change. In addition, the compiler will try to ensure that the values won’t be changed inadvertently.
Of course, the same benefits apply to #defined constants. The reason to use const rather than #define to define a constant is that a const variable can be of any type (such as a struct, which can’t be represented by a #defined constant). Also, because a const variable is a real variable, it has an address that can be used, if needed, and it resides in only one place in memory.
 |
| Tech Mahindra Frequently Asked C Language Interview Questions Answers |
Is It Acceptable To Declare/define A Variable In A C Header?
A global variable that must be accessed from more than one file can and should be declared in a header file. In addition, such a variable must be defined in one source file.
Variables should not be defined in header files, because the header file can be included in multiple source files, which would cause multiple definitions of the variable. The ANSI C standard will allow multiple external definitions, provided that there is only one initialization. But because there’s really no advantage to using this feature, it’s probably best to avoid it and maintain a higher level of portability.
“Global” variables that do not have to be accessed from more than one file should be declared static and should not appear in a header file.
When Should A Type Cast Be Used?
There are two situations in which to use a type cast. The first use is to change the type of an operand to an arithmetic operation so that the operation will be performed properly.
The second case is to cast pointer types to and from void * in order to interface with functions that expect or return void pointers. For example, the following line type casts the return value of the call to malloc() to be a pointer to a foo structure.
struct foo *p = (struct foo *) malloc(sizeof(struct foo));
Give The Benefit Of Using #define To Declare A Constant?
Using the #define method of declaring a constant enables you to declare a constant in one place and use it throughout your program. This helps make your programs more maintainable, because you need to maintain only the #define statement and not several instances of individual constants throughout your program. For instance, if your program used the value of pi (approximately 3.14159) several times, you might want to declare a constant for pi as follows
#define PI 3.14159
Using the #define method of declaring a constant is probably the most familiar way of declaring constants to traditional C programmers. Besides being the most common method of declaring constants, it also takes up the least memory. Constants defined in this manner are simply placed directly into your source code, with no variable space allocated in memory. Unfortunately, this is one reason why most debuggers cannot inspect constants created using the #define method.
How To Avoid Including A Header More Than Once?
One easy technique to avoid multiple inclusions of the same header is to use the #ifndef and #define preprocessor directives. When you create a header for your program, you can #define a symbolic name that is unique to that header. You can use the conditional preprocessor directive named #ifndef to check whether that symbolic name has already been assigned. If it is assigned, you should not include the header, because it has already been preprocessed. If it is not defined, you should define it to avoid any further inclusions of the header. The following header illustrates this technique
#ifndef _FILENAME_H
#define _FILENAME_H
#define VER_NUM “1.00.00”
#define REL_DATE “08/01/94”
#if _ _WINDOWS_ _
#define OS_VER “WINDOWS”
#else
#define OS_VER “DOS”
#endif
#endif
When the preprocessor encounters this header, it first checks to see whether _FILENAME_H has been defined. If it hasn’t been defined, the header has not been included yet, and the _FILENAME_H symbolic name is defined. Then, the rest of the header is parsed until the last #endif is encountered, signaling the end of the conditional #ifndef _FILENAME_H statement. Substitute the actual name of the header file for “FILENAME” in the preceding example to make it applicable for your programs.
Differentiate Between Arrays And Pointers?
Pointers are used to manipulate data using the address. Pointers use * operator to access the data pointed to by them Arrays use subscripted variables to access and manipulate data. Array variables can be equivalently written using pointer expression.
Mention The Purpose Of Realloc ( )?
The function realloc (ptr,n) uses two arguments. The first argument ptr is a pointer to a block of memory for which the size is to be altered. The second argument n specifies the new size. The size may be increased or decreased. If n is greater than the old size and if sufficient space is not available subsequent to the old region, the function realloc ( ) may create a new region and all the old data are moved to the new region.
Describe Static Memory Allocation And Dynamic Memory Allocation?
Static memory allocation: The compiler allocates the required memory space for a declared variable. By using the address of operator, the reserved address is obtained and this address may be assigned to a pointer variable. Since most of the declared variable has static memory, this way of assigning pointer value to a pointer variable is known as static memory allocation. Memory is assigned during compilation time. Dynamic memory allocation: It uses functions such as malloc ( ) or calloc ( ) to get memory dynamically. If these functions are used to get memory dynamically and the values returned by these functions are assigned to pointer variables, such assignments are known as dynamic memory allocation. Memory is assigned during run time.
How Are Pointer Variables Initialized?
Pointer variable are initialized by one of the following two ways
Static memory allocation
Dynamic memory allocation
What Is A Pointer Variable?
A pointer variable is a variable that may contain the address of another variable or any valid address in the memory.
Differentiate Between Text And Binary Modes?
Streams can be classified into two types: text streams and binary streams. Text streams are interpreted, with a maximum length of 255 characters. With text streams, carriage return/line feed combinations are translated to the newline n character and vice versa. Binary streams are uninterpreted and are treated one byte at a time with no translation of characters. Typically, a text stream would be used for reading and writing standard text files, printing output to the screen or printer, or receiving input from the keyboard.
A binary text stream would typically be used for reading and writing binary files such as graphics or word processing documents, reading mouse input, or reading and writing to the modem.
How To Restore A Redirected Standard Stream?
The preceding example showed how you can redirect a standard stream from within your program. But what if later in your program you wanted to restore the standard stream to its original state? By using the standard C library functions named dup() and fdopen(), you can restore a standard stream such as stdout to its original state.
The dup() function duplicates a file handle. You can use the dup() function to save the file handle corresponding to the stdout standard stream. The fdopen() function opens a stream that has been duplicated with the dup() function.
How To Search For Data In A Linked List?
Unfortunately, the only way to search a linked list is with a linear search, because the only way a linked list’s members can be accessed is sequentially. Sometimes it is quicker to take the data from a linked list and store it in a different data structure so that searches can be more efficient.
How To Sort A Linked List?
Both the merge sort and the radix sort are good sorting algorithms to use for linked lists.
What Do You Mean By Hashing?
To hash means to grind up, and that’s essentially what hashing is all about. The heart of a hashing algorithm is a hash function that takes your nice, neat data and grinds it into some random-looking integer.
The idea behind hashing is that some data either has no inherent ordering (such as images) or is expensive to compare (such as images). If the data has no inherent ordering, you can’t perform comparison searches.
If the data is expensive to compare, the number of comparisons used even by a binary search might be too many. So instead of looking at the data themselves, you’ll condense (hash) the data to an integer (its hash value) and keep all the data with the same hash value in the same place. This task is carried out by using the hash value as an index into an array. To search for an item, you simply hash it and look at all the data whose hash values match that of the data you’re looking for. This technique greatly lessens the number of items you have to look at. If the parameters are set up with care and enough storage is available for the hash table, the number of comparisons needed to find an item can be made arbitrarily close to one.
One aspect that affects the efficiency of a hashing implementation is the hash function itself. It should ideally distribute data randomly throughout the entire hash table, to reduce the likelihood of collisions. Collisions occur when two different keys have the same hash value. There are two ways to resolve this problem. In “open addressing,” the collision is resolved by the choosing of another position in the hash table for the element inserted later. When the hash table is searched, if the entry is not found at its hashed position in the table, the search continues checking until either the element is found or an empty position in the table is found.
The second method of resolving a hash collision is called “chaining.” In this method, a “bucket” or linked list holds all the elements whose keys hash to the same value. When the hash table is searched, the list must be searched linearly.
Which Is The Quickest Searching Method To Use?
A binary search, such as bsearch() performs, is much faster than a linear search. A hashing algorithm can provide even faster searching. One particularly interesting and fast method for searching is to keep the data in a “digital trie.” A digital trie offers the prospect of being able to search for an item in essentially a constant amount of time, independent of how many items are in the data set.
A digital trie combines aspects of binary searching, radix searching, and hashing. The term “digital trie” refers to the data structure used to hold the items to be searched. It is a multilevel data structure that branches N ways at each level.
How To Determine The Maximum Value That A Numeric Variable Can Hold?
For integral types, on a machine that uses two’s complement arithmetic (which is just about any machine you’re likely to use), a signed type can hold numbers from –2(number of bits – 1) to +2(number of bits – 1) – 1. An unsigned type can hold values from 0 to +2(number of bits) – 1. For instance, a 16-bit signed integer can hold numbers from –2^15 (–32768) to +2^15 – 1 (32767).
Can A Variable Be Both Const And Volatile?
Yes. The const modifier means that this code cannot change the value of the variable, but that does not mean that the value cannot be changed by means outside this code. For instance, in the example in FAQ 8, the timer structure was accessed through a volatile const pointer. The function itself did not change the value of the timer, so it was declared const. However, the value was changed by hardware on the computer, so it was declared volatile. If a variable is both const and volatile, the two modifiers can appear in either order.
When Does The Register Modifier Be Used? Does It Really Help?
The register modifier hints to the compiler that the variable will be heavily used and should be kept in the CPU’s registers, if possible, so that it can be accessed faster. There are several restrictions on the use of the register modifier.
First, the variable must be of a type that can be held in the CPU’s register. This usually means a single value of a size less than or equal to the size of an integer. Some machines have registers that can hold floating-point numbers as well. Second, because the variable might not be stored in memory, its address cannot be taken with the unary & operator. An attempt to do so is flagged as an error by the compiler. Some additional rules affect how useful the register modifier is. Because the number of registers is limited, and because some registers can hold only certain types of data (such as pointers or floating-point numbers), the number and types of register modifiers that will actually have any effect are dependent on what machine the program will run on. Any additional register modifiers are silently ignored by the compiler.
Also, in some cases, it might actually be slower to keep a variable in a register because that register then becomes unavailable for other purposes or because the variable isn’t used enough to justify the overhead of loading and storing it.
So when should the register modifier be used? The
is never, with most modern compilers. Early C compilers did not keep any variables in registers unless directed to do so, and the register modifier was a valuable addition to the language. C compiler design has advanced to the point, however, where the compiler will usually make better decisions than the programmer about which variables should be stored in registers. In fact, many compilers actually ignore the register modifier, which is perfectly legal, because it is only a hint and not a directive.
The use of an enumeration constant (enum) has many advantages over using the traditional symbolic constant style of #define. These advantages include a lower maintenance requirement, improved program readability, and better debugging capability.
The first advantage is that enumerated constants are generated automatically by the compiler. Conversely, symbolic constants must be manually assigned values by the programmer. For instance, if you had an enumerated constant type for error codes that could occur in your program, your enum definition could look something like this
enum Error_Code
{
OUT_OF_MEMORY,
INSUFFICIENT_DISK_SPACE,
LOGIC_ERROR,
FILE_NOT_FOUND
};
In the preceding example, OUT_OF_MEMORY is automatically assigned the value of 0 (zero) by the compiler because it appears first in the definition. The compiler then continues to automatically assign numbers to the enumerated constants, making INSUFFICIENT_DISK_SPACE equal to 1, LOGIC_ERROR equal to 2, and FILE_NOT_FOUND equal to 3, so on. If you were to approach the same example by using symbolic constants, your code would look something like this
#define OUT_OF_MEMORY 0
#define INSUFFICIENT_DISK_SPACE 1
#define LOGIC_ERROR 2
#define FILE_NOT_FOUND 3
values by the programmer. Each of the two methods arrives at the same result: four constants assigned numeric values to represent error codes. Consider the maintenance required, however, if you were to add two constants to represent the error codes DRIVE_NOT_READY and CORRUPT_FILE. Using the enumeration constant method, you simply would put these two constants anywhere in the enum definition. The compiler would generate two unique values for these constants. Using the symbolic constant method, you would have to manually assign two new numbers to these constants. Additionally, you would want to ensure that the numbers you assign to these constants are unique.
Another advantage of using the enumeration constant method is that your programs are more readable and thus can be understood better by others who might have to update your program later.
A third advantage to using enumeration constants is that some symbolic debuggers can print the value of an enumeration constant. Conversely, most symbolic debuggers cannot print the value of a symbolic constant. This can be an enormous help in debugging your program, because if your program is stopped at a line that uses an enum, you can simply inspect that constant and instantly know its value. On the other hand, because most debuggers cannot print #define values, you would most likely have to search for that value by manually looking it up in a header file.
Can A File Other Than A .h File Be Included With #include?
The preprocessor will include whatever file you specify in your #include statement. Therefore, if you have the line
#include <macros.inc>
in your program, the file macros.inc will be included in your precompiled program. It is, however, unusual programming practice to put any file that does not have a .h or .hpp extension in an
#include statement.
You should always put a .h extension on any of your C files you are going to include. This method makes it easier for you and others to identify which files are being used for preprocessing purposes. For instance, someone modifying or debugging your program might not know to look at the macros.inc file for macro definitions. That person might try in vain by searching all files with .h extensions and come up empty. If your file had been named macros.h, the search would have included the macros.h file, and the searcher would have been able to see what macros you defined in it.
Post a Comment