We cover solution of exercises on types, operators and expressions in book "The C programming language".
Exercise 2-1. Write a program to determine the ranges of char, short, int, and long variables, both signed and unsigned, by printing appropriate values from standard headers and by direct computation. Harder if you compute them: determine the ranges of the various floating-point types.
Solution
Exercise 2-2. Write a loop equivalent to the for loop above without using && or ||.
Solution
Convert s to integer
Convert c to lower case
Pseudo-random generator
Exercise 2-3. Write a function htoi(s), which converts a string of hexadecimal digits (including an optional 0x or 0X) into its equivalent integer value. The allowable digits are 0 through 9, a through f, and A through F.
Solution
Squeeze
Strcat
Exercise 2-4. Write an alternative version of squeeze(s1,s2) that deletes each character in s1 that matches any character in the string s2.
Solution
Exercise 2-5. Write the function any(s1,s2), which returns the first location in a string s1 where any character from the string s2 occurs, or -1 if s1 contains no characters from s2. (The standard library function strpbrk does the same job but returns a pointer to the location.)
Solution
Exercise 2-6. Write a function setbits(x,p,n,y) that returns x with the n bits that begin at position p set to the rightmost n bits of y, leaving the other bits unchanged.
Solution
Exercise 2-7. Write a function invert(x,p,n) that returns x with the n bits that begin at position p inverted (i.e., 1 changed into 0 and vice versa), leaving the others unchanged.
Solution
Exercise 2-8. Write a function rightrot(x,n) that returns the value of the integer x rotated to the right by n positions.
Solution
Bit count
Exercise 2-9. In a two's complement number system, x &= (x-1) deletes the rightmost 1-bit in x. Explain why. Use this observation to write a faster version of bitcount.
Solution
Exercise 2-10. Rewrite the function lower, which converts upper case letters to lower case, with a conditional expression instead of if-else.
Solution
Friday, September 23, 2016
[C Programming] Exercises on Control flow
We cover solution of exercises on Control flow in book "The C programming language".
Binary search
Exercise 3-1. Our binary search makes two tests inside the loop, when one would suffice (at the price of more tests outside.) Write a version with only one test inside the loop and measure the difference in run-time.
Solution
Count digit
Exercise 3-2. Write a function escape(s,t) that converts characters like newline and tab into visible escape sequences like \n and \t as it copies the string t to s. Use a switch. Write a function for the other direction as well, converting escape sequences into the real characters.
Solution
Convert string to integer
Shellsort
Reverse string
Exercise 3-3. Write a function expand(s1,s2) that expands shorthand notations like a-z in the string s1 into the equivalent complete list abc...xyz in s2. Allow for letters of either case and digits, and be prepared to handle cases like a-b-c and a-z0-9 and -a-z. Arrange that a leading or trailing - is taken literally.
Solution
Convert n to characters
Exercise 3-4. In a two's complement number representation, our version of itoa does not handle the largest negative number, that is, the value of n equal to -(2wordsize-1). Explain why not. Modify it to print that value correctly, regardless of the machine on which it runs.
Solution
Exercise 3-5. Write the function itob(n,s,b) that converts the integer n into a base b character representation in the string s. In particular, itob(n,s,16) formats s as a hexadecimal integer in s.
Solution
Exercise 3-6. Write a version of itoa that accepts three arguments instead of two. The third argument is a minimum field width; the converted number must be padded with blanks on the left if necessary to make it wide enough.
Solution
Strim
Goto
Binary search
Exercise 3-1. Our binary search makes two tests inside the loop, when one would suffice (at the price of more tests outside.) Write a version with only one test inside the loop and measure the difference in run-time.
Solution
Count digit
Exercise 3-2. Write a function escape(s,t) that converts characters like newline and tab into visible escape sequences like \n and \t as it copies the string t to s. Use a switch. Write a function for the other direction as well, converting escape sequences into the real characters.
Solution
Convert string to integer
Shellsort
Reverse string
Exercise 3-3. Write a function expand(s1,s2) that expands shorthand notations like a-z in the string s1 into the equivalent complete list abc...xyz in s2. Allow for letters of either case and digits, and be prepared to handle cases like a-b-c and a-z0-9 and -a-z. Arrange that a leading or trailing - is taken literally.
Solution
Convert n to characters
Exercise 3-4. In a two's complement number representation, our version of itoa does not handle the largest negative number, that is, the value of n equal to -(2wordsize-1). Explain why not. Modify it to print that value correctly, regardless of the machine on which it runs.
Solution
Exercise 3-5. Write the function itob(n,s,b) that converts the integer n into a base b character representation in the string s. In particular, itob(n,s,16) formats s as a hexadecimal integer in s.
Solution
Exercise 3-6. Write a version of itoa that accepts three arguments instead of two. The third argument is a minimum field width; the converted number must be padded with blanks on the left if necessary to make it wide enough.
Solution
Strim
Goto
[C Programming] Functions and Program structure
We cover solution of exercises on Functions and Program structure in book "The C program language".
Power
Longest line
Exercise 1.15. Rewrite the temperature conversion program of Section 1.2 to use a function for conversion.
Solution
Get line
Exercise 1-20. Write a program detab that replaces tabs in the input with the proper number of blanks to space to the next tab stop. Assume a fixed set of tab stops, say every n columns. Should n be a variable or a symbolic parameter?
Solution
Exercise 1-21. Write a program entab that replaces strings of blanks by the minimum number of tabs and blanks to achieve the same spacing. Use the same tab stops as for detab. When either a tab or a single blank would suffice to reach a tab stop, which should be given preference?
Solution
Exercise 1-22. Write a program to ``fold'' long input lines into two or more shorter lines after the last non-blank character that occurs before the n-th column of input. Make sure your program does something intelligent with very long lines, and if there are no blanks or tabs before the specified column.
Solution
Exercise 1-23. Write a program to remove all comments from a C program. Don't forget to handle quoted strings and character constants properly. C comments don't nest.
Solution
Exercise 1-24. Write a program to check a C program for rudimentary syntax errors like unmatched parentheses, brackets and braces. Don't forget about quotes, both single and double, escape sequences, and comments. (This program is hard if you do it in full generality.)
Solution
Exercise 4-1. Write the function strindex(s,t) which returns the position of the rightmost occurrence of t in s, or -1 if there is none.
Solution
Convert string to double
Exercise 4-2. Extend atof to handle scientific notation of the form
123.45e-6
where a floating-point number may be followed by e or E and an optionally signed exponent.
Solution
Reverse Polish calculator
Exercise 4-3. Given the basic framework, it's straightforward to extend the calculator. Add the modulus (%) operator and provisions for negative numbers.
Exercise 4-4. Add the commands to print the top elements of the stack without popping, to duplicate it, and to swap the top two elements. Add a command to clear the stack.
Exercise 4-5. Add access to library functions like sin, exp, and pow. See <math.h> in Appendix B, Section 4.
Exercise 4-6. Add commands for handling variables. (It's easy to provide twenty-six variables with single-letter names.) Add a variable for the most recently printed value.
Exercise 4-7. Write a routine ungets(s) that will push back an entire string onto the input. Should ungets know about buf and bufp, or should it just use ungetch?
Exercise 4-8. Suppose that there will never be more than one character of pushback. Modify getch and ungetch accordingly.
Exercise 4-9. Our getch and ungetch do not handle a pushed-back EOF correctly. Decide what their properties ought to be if an EOF is pushed back, then implement your design.
Exercise 4-10. An alternate organization uses getline to read an entire input line; this makes getch and ungetch unnecessary. Revise the calculator to use this approach.
Exercise 4-11. Modify getop so that it doesn't need to use ungetch. Hint: use an internal static variable.
Quick sort
Exercise 4-12. Adapt the ideas of printd to write a recursive version of itoa; that is, convert an integer into a string by calling a recursive routine.
Exercise 4-13. Write a recursive version of the function reverse(s), which reverses the string s in place.
Exercise 4-14. Define a macro swap(t,x,y) that interchanges two arguments of type t. (Block structure will help.)
Power
Longest line
Exercise 1.15. Rewrite the temperature conversion program of Section 1.2 to use a function for conversion.
Solution
Get line
Exercise 1-20. Write a program detab that replaces tabs in the input with the proper number of blanks to space to the next tab stop. Assume a fixed set of tab stops, say every n columns. Should n be a variable or a symbolic parameter?
Solution
Exercise 1-21. Write a program entab that replaces strings of blanks by the minimum number of tabs and blanks to achieve the same spacing. Use the same tab stops as for detab. When either a tab or a single blank would suffice to reach a tab stop, which should be given preference?
Solution
Exercise 1-22. Write a program to ``fold'' long input lines into two or more shorter lines after the last non-blank character that occurs before the n-th column of input. Make sure your program does something intelligent with very long lines, and if there are no blanks or tabs before the specified column.
Solution
Exercise 1-23. Write a program to remove all comments from a C program. Don't forget to handle quoted strings and character constants properly. C comments don't nest.
Solution
Exercise 1-24. Write a program to check a C program for rudimentary syntax errors like unmatched parentheses, brackets and braces. Don't forget about quotes, both single and double, escape sequences, and comments. (This program is hard if you do it in full generality.)
Solution
Exercise 4-1. Write the function strindex(s,t) which returns the position of the rightmost occurrence of t in s, or -1 if there is none.
Solution
Convert string to double
Exercise 4-2. Extend atof to handle scientific notation of the form
123.45e-6
where a floating-point number may be followed by e or E and an optionally signed exponent.
Solution
Reverse Polish calculator
Exercise 4-3. Given the basic framework, it's straightforward to extend the calculator. Add the modulus (%) operator and provisions for negative numbers.
Exercise 4-4. Add the commands to print the top elements of the stack without popping, to duplicate it, and to swap the top two elements. Add a command to clear the stack.
Exercise 4-5. Add access to library functions like sin, exp, and pow. See <math.h> in Appendix B, Section 4.
Exercise 4-6. Add commands for handling variables. (It's easy to provide twenty-six variables with single-letter names.) Add a variable for the most recently printed value.
Exercise 4-7. Write a routine ungets(s) that will push back an entire string onto the input. Should ungets know about buf and bufp, or should it just use ungetch?
Exercise 4-8. Suppose that there will never be more than one character of pushback. Modify getch and ungetch accordingly.
Exercise 4-9. Our getch and ungetch do not handle a pushed-back EOF correctly. Decide what their properties ought to be if an EOF is pushed back, then implement your design.
Exercise 4-10. An alternate organization uses getline to read an entire input line; this makes getch and ungetch unnecessary. Revise the calculator to use this approach.
Exercise 4-11. Modify getop so that it doesn't need to use ungetch. Hint: use an internal static variable.
Quick sort
Exercise 4-12. Adapt the ideas of printd to write a recursive version of itoa; that is, convert an integer into a string by calling a recursive routine.
Exercise 4-13. Write a recursive version of the function reverse(s), which reverses the string s in place.
Exercise 4-14. Define a macro swap(t,x,y) that interchanges two arguments of type t. (Block structure will help.)
Thursday, September 22, 2016
[C Programming] Exercises on Structures
We cover exercises on Structures in book "The C Programming language".
Count word version 1
Count word version 2
Count word
Exercise 6-2. Write a program that reads a C program and prints in alphabetical order each group of variable names that are identical in the first 6 characters, but different somewhere thereafter. Don't count words within strings and comments. Make 6 a parameter that can be set from the command line.
Solution
Exercise 6-3. Write a cross-referencer that prints a list of all words in a document, and for each word, a list of the line numbers on which it occurs. Remove noise words like ``the,'' ``and,'' and so on.
Solution
Exercise 6-4. Write a program that prints the distinct words in its input sorted into decreasing order of frequency of occurrence. Precede each word by its count.
Solution
Exercise 6-5. Write a function undef that will remove a name and definition from the table maintained by lookup and install.
Solution
Exercise 6-6. Implement a simple version of the #define processor (i.e., no arguments) suitable for use with C programs, based on the routines of this section. You may also find getch and ungetch helpful.
Solution
Count word version 1
Count word version 2
Count word
Exercise 6-2. Write a program that reads a C program and prints in alphabetical order each group of variable names that are identical in the first 6 characters, but different somewhere thereafter. Don't count words within strings and comments. Make 6 a parameter that can be set from the command line.
Solution
Exercise 6-3. Write a cross-referencer that prints a list of all words in a document, and for each word, a list of the line numbers on which it occurs. Remove noise words like ``the,'' ``and,'' and so on.
Solution
Exercise 6-4. Write a program that prints the distinct words in its input sorted into decreasing order of frequency of occurrence. Precede each word by its count.
Solution
Exercise 6-5. Write a function undef that will remove a name and definition from the table maintained by lookup and install.
Solution
Exercise 6-6. Implement a simple version of the #define processor (i.e., no arguments) suitable for use with C programs, based on the routines of this section. You may also find getch and ungetch helpful.
Solution
Wednesday, September 21, 2016
[C Programming] Exercises on Pointer and Array
We cover exercises on Pointer and Array in book "The C programming language".
Longest line
Exercise 1-16. Revise the main routine of the longest-line program so it will correctly print the length of arbitrary long input lines, and as much as possible of the text.
Solution
Exercise 1-17. Write a program to print all input lines that are longer than 80 characters.
Solution
Exercise 1-18. Write a program to remove trailing blanks and tabs from each line of input, and to delete entirely blank lines.
Solution
Exercise 1-19. Write a function reverse(s) that reverses the character string s. Use it to write a program that reverses its input a line at a time.
Solution
Count digits
Exercise 1-13. Write a program to print a histogram of the lengths of words in its input. It is easy to draw the histogram with the bars horizontal; a vertical orientation is more challenging.
Solution
Exercise 1-14. Write a program to print a histogram of the frequencies of different characters in its input.
Solution
Get Int
Exercise 5-1. As written, getint treats a + or - not followed by a digit as a valid representation of zero. Fix it to push such a character back on the input.
Solution
Exercise 5-2. Write getfloat, the floating-point analog of getint. What type does getfloat return as its function value?
Solution
Strlen
Strcpy
Strcmp
Exercise 5-3. Write a pointer version of the function strcat that we showed in Chapter 2: strcat(s,t) copies the string t to the end of s.
Solution
Exercise 5-4. Write the function strend(s,t), which returns 1 if the string t occurs at the end of the string s, and zero otherwise.
Solution
Exercise 5-5. Write versions of the library functions strncpy, strncat, and strncmp, which operate on at most the first n characters of their argument strings. For example, strncpy(s,t,n) copies at most n characters of t to s. Full descriptions are in Appendix B.
Solution
Exercise 5-6. Rewrite appropriate programs from earlier chapters and exercises with pointers instead of array indexing. Good possibilities include getline (Chapters 1 and 4), atoi, itoa, and their variants (Chapters 2, 3, and 4), reverse (Chapter 3), and strindex and getop (Chapter 4).
Solution
Quicksoft
Exercise 5-7. Rewrite readlines to store lines in an array supplied by main, rather than calling alloc to maintain storage. How much faster is the program?
Solution
Day of year
Exercise 5-8. There is no error checking in day_of_year or month_day. Remedy this defect.
Solution
Month name
Exercise 5-9. Rewrite the routines day_of_year and month_day with pointers instead of indexing.
Solution
Pattern-finding
Exercise 5-10. Write the program expr, which evaluates a reverse Polish expression from the command line, where each operator or operand is a separate argument. For example,
expr 2 3 4 + *
evaluates 2 * (3+4).
Solution
Exercise 5-11. Modify the program entab and detab (written as exercises in Chapter 1) to accept a list of tab stops as arguments. Use the default tab settings if there are no arguments.
Solution
Exercise 5-12. Extend entab and detab to accept the shorthand
entab -m +n
to mean tab stops every n columns, starting at column m. Choose convenient (for the user) default behavior.
Solution
Exercise 5-13. Write the program tail, which prints the last n lines of its input. By default, n is set to 10, let us say, but it can be changed by an optional argument so that
tail -n
prints the last n lines. The program should behave rationally no matter how unreasonable the input or the value of n. Write the program so it makes the best use of available storage; lines should be stored as in the sorting program of Section 5.6, not in a two-dimensional array of fixed size.
Solution
Qsort
Exercise 5-14. Modify the sort program to handle a -r flag, which indicates sorting in reverse (decreasing) order. Be sure that -r works with -n.
Solution
Exercise 5-15. Add the option -f to fold upper and lower case together, so that case distinctions are not made during sorting; for example, a and A compare equal.
Solution
Exercise 5-16. Add the -d (``directory order'') option, which makes comparisons only on letters, numbers and blanks. Make sure it works in conjunction with -f.
Solution
Exercise 5-17. Add a field-searching capability, so sorting may bee done on fields within lines, each field sorted according to an independent set of options. (The index for this book was sorted with -df for the index category and -n for the page numbers.)
Solution
Parse Declarator
Exercise 5-18. Make dcl recover from input errors.
Solution
Exercise 5-19. Modify undcl so that it does not add redundant parentheses to declarations.
Solution
Exercise 5-20. Expand dcl to handle declarations with function argument types, qualifiers like const, and so on.
Solution
Longest line
Exercise 1-16. Revise the main routine of the longest-line program so it will correctly print the length of arbitrary long input lines, and as much as possible of the text.
Solution
Exercise 1-17. Write a program to print all input lines that are longer than 80 characters.
Solution
Exercise 1-18. Write a program to remove trailing blanks and tabs from each line of input, and to delete entirely blank lines.
Solution
Exercise 1-19. Write a function reverse(s) that reverses the character string s. Use it to write a program that reverses its input a line at a time.
Solution
Count digits
Exercise 1-13. Write a program to print a histogram of the lengths of words in its input. It is easy to draw the histogram with the bars horizontal; a vertical orientation is more challenging.
Solution
Exercise 1-14. Write a program to print a histogram of the frequencies of different characters in its input.
Solution
Get Int
Exercise 5-1. As written, getint treats a + or - not followed by a digit as a valid representation of zero. Fix it to push such a character back on the input.
Solution
Exercise 5-2. Write getfloat, the floating-point analog of getint. What type does getfloat return as its function value?
Solution
Strlen
Strcpy
Strcmp
Exercise 5-3. Write a pointer version of the function strcat that we showed in Chapter 2: strcat(s,t) copies the string t to the end of s.
Solution
Exercise 5-4. Write the function strend(s,t), which returns 1 if the string t occurs at the end of the string s, and zero otherwise.
Solution
Exercise 5-5. Write versions of the library functions strncpy, strncat, and strncmp, which operate on at most the first n characters of their argument strings. For example, strncpy(s,t,n) copies at most n characters of t to s. Full descriptions are in Appendix B.
Solution
Exercise 5-6. Rewrite appropriate programs from earlier chapters and exercises with pointers instead of array indexing. Good possibilities include getline (Chapters 1 and 4), atoi, itoa, and their variants (Chapters 2, 3, and 4), reverse (Chapter 3), and strindex and getop (Chapter 4).
Solution
Quicksoft
Exercise 5-7. Rewrite readlines to store lines in an array supplied by main, rather than calling alloc to maintain storage. How much faster is the program?
Solution
Day of year
Exercise 5-8. There is no error checking in day_of_year or month_day. Remedy this defect.
Solution
Month name
Exercise 5-9. Rewrite the routines day_of_year and month_day with pointers instead of indexing.
Solution
Pattern-finding
Exercise 5-10. Write the program expr, which evaluates a reverse Polish expression from the command line, where each operator or operand is a separate argument. For example,
expr 2 3 4 + *
evaluates 2 * (3+4).
Solution
Exercise 5-11. Modify the program entab and detab (written as exercises in Chapter 1) to accept a list of tab stops as arguments. Use the default tab settings if there are no arguments.
Solution
Exercise 5-12. Extend entab and detab to accept the shorthand
entab -m +n
to mean tab stops every n columns, starting at column m. Choose convenient (for the user) default behavior.
Solution
Exercise 5-13. Write the program tail, which prints the last n lines of its input. By default, n is set to 10, let us say, but it can be changed by an optional argument so that
tail -n
prints the last n lines. The program should behave rationally no matter how unreasonable the input or the value of n. Write the program so it makes the best use of available storage; lines should be stored as in the sorting program of Section 5.6, not in a two-dimensional array of fixed size.
Solution
Qsort
Exercise 5-14. Modify the sort program to handle a -r flag, which indicates sorting in reverse (decreasing) order. Be sure that -r works with -n.
Solution
Exercise 5-15. Add the option -f to fold upper and lower case together, so that case distinctions are not made during sorting; for example, a and A compare equal.
Solution
Exercise 5-16. Add the -d (``directory order'') option, which makes comparisons only on letters, numbers and blanks. Make sure it works in conjunction with -f.
Solution
Exercise 5-17. Add a field-searching capability, so sorting may bee done on fields within lines, each field sorted according to an independent set of options. (The index for this book was sorted with -df for the index category and -n for the page numbers.)
Solution
Parse Declarator
Exercise 5-18. Make dcl recover from input errors.
Solution
Exercise 5-19. Modify undcl so that it does not add redundant parentheses to declarations.
Solution
Exercise 5-20. Expand dcl to handle declarations with function argument types, qualifiers like const, and so on.
Solution
Tuesday, September 20, 2016
[C programming] Exercises on Input, output
We cover exercises on Input, Output from book "The C programming language".
File copy
Count characters in input
Count line
Exercise 1-8. Write a program to count blanks, tabs, and newlines.
Solution
Exercise 1-9. Write a program to copy its input to its output, replacing each string of one or more blanks by a single blank.
Solution
Exercise 1-10. Write a program to copy its input to its output, replacing each tab by \t, each backspace by \b, and each backslash by \\. This makes tabs and backspaces visible in an unambiguous way.
Solution
Count word
Convert to lower case
Exercise 7-1. Write a program that converts upper case to lower or lower case to upper, depending on the name it is invoked with, as found in argv[0].
Solution
Exercise 7-2. Write a program that will print arbitrary input in a sensible way. As a minimum, it should print non-graphic characters in octal or hexadecimal according to local custom, and break long text lines.
Solution
Exercise 7-3. Revise minprintf to handle more of the other facilities of printf.
Solution
Exercise 7-4. Write a private version of scanf analogous to minprintf from the previous section.
Solution
Exercise 7-5. Rewrite the postfix calculator of Chapter 4 to use scanf and/or sscanf to do the input and number conversion.
Solution
Copy File
Fgets Fputs Getline
Exercise 7-6. Write a program to compare two files, printing the first line where they differ.
Solution
Exercise 7-7. Modify the pattern finding program of Chapter 5 to take its input from a set of named files or, if no files are named as arguments, from the standard input. Should the file name be printed when a matching line is found?
Solution
Exercise 7-8. Write a program to print a set of files, starting each new one on a new page, with a title and a running page count for each file.
Solution
Exercise 7-9. Functions like isupper can be implemented to save space or to save time. Explore both possibilities.
Solution
File copy
Count characters in input
Count line
Exercise 1-8. Write a program to count blanks, tabs, and newlines.
Solution
Exercise 1-9. Write a program to copy its input to its output, replacing each string of one or more blanks by a single blank.
Solution
Exercise 1-10. Write a program to copy its input to its output, replacing each tab by \t, each backspace by \b, and each backslash by \\. This makes tabs and backspaces visible in an unambiguous way.
Solution
Count word
Convert to lower case
Exercise 7-1. Write a program that converts upper case to lower or lower case to upper, depending on the name it is invoked with, as found in argv[0].
Solution
Exercise 7-2. Write a program that will print arbitrary input in a sensible way. As a minimum, it should print non-graphic characters in octal or hexadecimal according to local custom, and break long text lines.
Solution
Exercise 7-3. Revise minprintf to handle more of the other facilities of printf.
Solution
Exercise 7-4. Write a private version of scanf analogous to minprintf from the previous section.
Solution
Exercise 7-5. Rewrite the postfix calculator of Chapter 4 to use scanf and/or sscanf to do the input and number conversion.
Solution
Copy File
Fgets Fputs Getline
Exercise 7-6. Write a program to compare two files, printing the first line where they differ.
Solution
Exercise 7-7. Modify the pattern finding program of Chapter 5 to take its input from a set of named files or, if no files are named as arguments, from the standard input. Should the file name be printed when a matching line is found?
Solution
Exercise 7-8. Write a program to print a set of files, starting each new one on a new page, with a title and a running page count for each file.
Solution
Exercise 7-9. Functions like isupper can be implemented to save space or to save time. Explore both possibilities.
Solution
Greedy Algorithms
Definition
An algorithm is said to be greedy if it makes the locally optimal choice at each step with the hope of eventually reaching the globally optimal solution.
In some cases, greedy works, the solution is short and runs efficiently. For many others, however, it does not.
A problem must exhibit these two properties in order for a greedy algorithm to work:
- It has optimal sub-structures. Optimal solution to the problem contains optimal solutions to the sub-problems.
- It has the greedy property. If we make a choice that seems like the best at the moment and proceed to solve the remaining subproblem, we reach the optimal solution. We will never have to reconsider our previous choices.
Elements of the greedy strategy
To develop a greedy algorithm, we go through the following steps:
- Cast the optimization problem as one in which we make a choice and are left with one subproblem to solve.
- Prove that there is always an optimal solution to the original problem that makes the greedy choice, so that the greedy choice is always safe.
- Demonstrate optimal substructure by showing that, having made the greedy choice, what remains is a subproblem with the property that if we combine an optimal solution to the subproblem with the greedy choice we have made, we arrive an optimal solution to the original problem.
Greedy versus dynamic programming
Both greedy and dynamic programming strategies exploit optimal substructure. In greedy algorithm, we can assemble a globally optimal solution by making locally optimal choices. In more detail, we make the choice that looks best in the current problem, without considering results from subproblems. In dynamic programming, we make a choice at each step, but the choice usually depends on the solutions to the problem.
Coin change problem
Problem discription: Given a target amount V cents and a list of denominations of n coins, i.e. we have coin_value[i] (in cents) for coin types i = 1..n-1, what is the minimum number of coins that we must use to represent amount V? Assume that we have an unlimited supply of coins of any type.
Example: if n = 4, coin_value = {25, 10, 5, 1} cents, and we want to represent V = 42 cents, we can use this Greedy algorithm: Select the largest coint denomination wich is not greater than the remaining amount, i.e. 42 - 35 = 17 , 17 - 10 = 7 , 7 - 5 = 2 , 2 - 1 = 1, 1 - 1 = 0., a total of 5 coins. This is optimal.
The problem above has the two ingredients required for a successful greedy algorithm.
Example: if n = 4, coin_value = {25, 10, 5, 1} cents, and we want to represent V = 42 cents, we can use this Greedy algorithm: Select the largest coint denomination wich is not greater than the remaining amount, i.e. 42 - 35 = 17 , 17 - 10 = 7 , 7 - 5 = 2 , 2 - 1 = 1, 1 - 1 = 0., a total of 5 coins. This is optimal.
The problem above has the two ingredients required for a successful greedy algorithm.
- It has optimal substructures: We have seen that in our quest to represent 42 cents, we used 25 + 10 + 5 + 1 + 1. This is an optimal 5-coin solution to the original problem. i.e. to present 17 cents we can use 10 + 5 + 1 + 1 (part of the solution for 42 cents), to represent 7 cents, we can use 5 + 1 + 1 (also part of te solution for 42 cents).
- It has the greedy property: Given every amount V, we can greedily subtract from it the largest coin denomination which is not greater than this amount V. It can be proven that using any other strategies will not lead to an optimal solution, at least for this set of coin denominations.
#include <stdio.h>
#define COIN_TYPE 4
int main() {
int coin_value[COIN_TYPE] = {25, 10, 5, 1};
int total_value,i;
printf("%s\n", "Enter total value: ");
scanf("%d", &total_value);
printf("%s", "Selected coins are: ");
while ( total_value > 0) {
for (i = 0; i < COIN_TYPE; i++) {
if( total_value >= coin_value[i]){
total_value -= coin_value[i];
printf("%d\n", coin_value[i]);
break;
}
}
}
return 0;
}
However, this greedy algorithm does not work for all sets of coin denominations. Take for example {4, 3, 1} cents. To make 6 cents with that set, a greedy algorithm would choose 3 coins {4, 1, 1} instead of the optimal solution that uses 2 coins {3, 3}.
Station balance problem
Given 1 <= C <= 5 chambers which can store 0, 1, or 2 specimens, 1 <= S <= 2c specimens and a list M of the masses of the S specimens, determine which chamber should store each specimen in order to minimize imbalance.
Denote A the average of the total mass in each of the C chambers. The imbalance is the sum of differences between the actual total mass in each chamber and the average total mass.
If S > C, then S - C specimans must be paired with a chamber already containing other specimens. So we create dummy specimens with mass 0. And use greedy algorithm to out specimens into each chambers.
C code for this example:
#include <stdio.h>
#include <math.h>
#define NUM_SPE 5 //number of specimens
#define NUM_CHB 3 //number of chambers
int specimens[NUM_SPE] = {5, 1, 2, 7, 6};
int optimal[2 * NUM_CHB];
void sort(int array[]) {
int i, j;
for (i = 0; i < NUM_SPE; i++) {
for (j = i + 1; j < NUM_SPE; j++) {
if (array[i] < array[j]) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
}
int main() {
int i;
sort(specimens);
for ( i = 0; i < NUM_CHB; i++) {
printf("Chamber %d has %d ", i, specimens[i]);
if (2 * NUM_CHB - i <= NUM_SPE) {
printf("and %d\n", specimens[2 * NUM_CHB - i - 1]);
} else {
printf("\n");
}
}
return 0;
}
Huffman code
Huffman invented a greedy algorithm that constructs an optimal prefix code called a Huffman code. Huffman codes compress data very effectively: savings of 20% to 90% are typical. Suppose that we have a 100,000 character data that we wish to store compactly, we observe that the character in the file occur with the frequencies given by the following figure.
If we ned 3 bits to represent 6 characters: a = 000, b = 001, ..., f = 101. This method requires 300,000 bits to code the entire file.
The idea of Huffman code is giving frequent characters short codewords and infrequent characters long codewords. As in the above figure, the total bits are only 224,000. To enable to decompress Huffman code, each codeword must not be the prefix of the others. To generate code word we can use a binary tree as follow with assumption that the left (right) child node is corresponding to bit 0 (bit 1).
References
Steven Halim, Felix Halim, "Competitive programming", handbook for ACM ICPC and IOI contestants 2013
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, "Introduction to Algorithm", Third edition.
[C programming] UNIX system interface
We cover below parts.
- File descriptors
- Low level I/O
- Open, create, close, unlink
- Random acess - lseek
- File descriptors
- Low level I/O
- Open, create, close, unlink
- Random acess - lseek
Monday, September 19, 2016
[C programming] Functions and program structure
We cover below parts.
- External variable
- Static variables
- Register variable
- The C preprocessor
Other parts(basics of fuctions, header rules, block structure, initialization and recursion) are skipped.
1. External variable
A variable is external if it is defined outside of any function. When we need to inform other source files about functions/global variables in a file. For functions, put function prototypes in header file. For variables, re-declare the global variable using the extern keyword in header file. extern informs compiler that variable defined somewhere else. extern helps to access/modify of global variable from other source files.
2. Variable scope (static variables and register variables)
scope - defines the region in which a variable is valid.
static keyword has two meanings, depending on where the static variable is declared. Outside a function, static variables/functions only visible within that file, not globally (cannot be extern’ed). Inside a function, static variables have following characteristics. First, they are still local to that function. Second, they are initialized only during program initialization. Third, they do not get reinitialized with each function call.
During execution, data processed in registers. Explicitly storing commonly used data in registers helps to minimize load/store overhead. We can explicitly declare certain variables as registers using register keyword. Registers do not reside in addressed memory; pointer of a register variable illegal.
Check more detailed about rule scope in below links.
https://www.tutorialspoint.com/cprogramming/c_scope_rules.htm
http://www.geeksforgeeks.org/scope-rules-in-c/
Static variable
http://quiz.geeksforgeeks.org/static-variables-in-c/
Register variable
http://www.geeksforgeeks.org/understanding-register-keyword/
3. The C Preprocessor
Check below link for a clearly overview on CPP.
https://gcc.gnu.org/onlinedocs/cpp/
- External variable
- Static variables
- Register variable
- The C preprocessor
Other parts(basics of fuctions, header rules, block structure, initialization and recursion) are skipped.
1. External variable
A variable is external if it is defined outside of any function. When we need to inform other source files about functions/global variables in a file. For functions, put function prototypes in header file. For variables, re-declare the global variable using the extern keyword in header file. extern informs compiler that variable defined somewhere else. extern helps to access/modify of global variable from other source files.
2. Variable scope (static variables and register variables)
scope - defines the region in which a variable is valid.
static keyword has two meanings, depending on where the static variable is declared. Outside a function, static variables/functions only visible within that file, not globally (cannot be extern’ed). Inside a function, static variables have following characteristics. First, they are still local to that function. Second, they are initialized only during program initialization. Third, they do not get reinitialized with each function call.
During execution, data processed in registers. Explicitly storing commonly used data in registers helps to minimize load/store overhead. We can explicitly declare certain variables as registers using register keyword. Registers do not reside in addressed memory; pointer of a register variable illegal.
Check more detailed about rule scope in below links.
https://www.tutorialspoint.com/cprogramming/c_scope_rules.htm
http://www.geeksforgeeks.org/scope-rules-in-c/
Static variable
http://quiz.geeksforgeeks.org/static-variables-in-c/
Register variable
http://www.geeksforgeeks.org/understanding-register-keyword/
3. The C Preprocessor
Check below link for a clearly overview on CPP.
https://gcc.gnu.org/onlinedocs/cpp/
[C programming] control flow
We cover below parts.
- Statements and blocks
- If-else
- Else-if
- Switch
- Loops -While and For
- Loops - Do While
- Break and Continue
- Goto and labels
1. Statements and blocks
An expression such as x = 0 or i++ or printf(...) becomes a statement when it is followed by a semicolon, as in
x = 0;
Braces { and } are used to group declarations and statements together into a compound statement, or block, so that they are syntactically equivalent to a single statement.
2. If-else
if (expression)
statement1
else
statement2
3. Else-If
if (expression)
statement
else if (expression)
statement
else if (expression)
statement
else if (expression)
statement
else
statement
4. Switch
switch (expression) {
case const-expr: statements
case const-expr: statements
default: statements
}
Below example to count digits, white space, others.
5. Loops - While and For
We have already encountered the while and for loops. In
while (expression)
statement
the expression is evaluated. If it is non-zero, statement is executed and expression is re-evaluated. This cycle continues until expression becomes zero, at which point execution resumes after statement.
The for statement
for (expr1; expr2; expr3)
statement
is equivalent to
expr1;
while (expr2) {
statement
expr3;
}
for (;;) {
...
}
is an ``infinite'' loop,
6. Loops - Do-While
do
statement
while (expression);
7. Break and Continue
The break statement provides an early exit from for, while, and do, just as from switch.
The continue statement is related to break, but less often used; it causes the next iteration of the enclosing for, while, or do loop to begin. In the while and do, this means that the test part is executed immediately; in the for, control passes to the increment step. The continue statement applies only to loops, not to switch.
8. Goto and labels
C provides the infinitely-abusable goto statement, and labels to branch to.
for ( ... )
for ( ... ) {
...
if (disaster)
goto error;
}
...
error:
/* clean up the mess */
- Statements and blocks
- If-else
- Else-if
- Switch
- Loops -While and For
- Loops - Do While
- Break and Continue
- Goto and labels
1. Statements and blocks
An expression such as x = 0 or i++ or printf(...) becomes a statement when it is followed by a semicolon, as in
x = 0;
Braces { and } are used to group declarations and statements together into a compound statement, or block, so that they are syntactically equivalent to a single statement.
2. If-else
if (expression)
statement1
else
statement2
3. Else-If
if (expression)
statement
else if (expression)
statement
else if (expression)
statement
else if (expression)
statement
else
statement
4. Switch
switch (expression) {
case const-expr: statements
case const-expr: statements
default: statements
}
Below example to count digits, white space, others.
main() /* count digits, white space, others */
{
int c, i, nwhite, nother, ndigit[10];
nwhite = nother = 0;
for (i = 0; i < 10; i++)
ndigit[i] = 0;
while ((c = getchar()) != EOF) {
switch (c) {
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
ndigit[c-'0']++;
break;
case ' ':
case '\n':
case '\t':
nwhite++;
break;
default:
nother++;
break;
}
}
printf("digits =");
for (i = 0; i < 10; i++)
printf(" %d", ndigit[i]);
printf(", white space = %d, other = %d\n", nwhite, nother);
return 0;
}
The break statement causes an immediate exit from the switch.
5. Loops - While and For
We have already encountered the while and for loops. In
while (expression)
statement
the expression is evaluated. If it is non-zero, statement is executed and expression is re-evaluated. This cycle continues until expression becomes zero, at which point execution resumes after statement.
The for statement
for (expr1; expr2; expr3)
statement
is equivalent to
expr1;
while (expr2) {
statement
expr3;
}
for (;;) {
...
}
is an ``infinite'' loop,
6. Loops - Do-While
do
statement
while (expression);
7. Break and Continue
The break statement provides an early exit from for, while, and do, just as from switch.
The continue statement is related to break, but less often used; it causes the next iteration of the enclosing for, while, or do loop to begin. In the while and do, this means that the test part is executed immediately; in the for, control passes to the increment step. The continue statement applies only to loops, not to switch.
8. Goto and labels
C provides the infinitely-abusable goto statement, and labels to branch to.
for ( ... )
for ( ... ) {
...
if (disaster)
goto error;
}
...
error:
/* clean up the mess */
[C programming] Types, operators and expressions
We cover below parts.
- Variable names
- Data types and sizes
- Constants
- Declarations
- Arithmetic operators
- Relational and logical operators
- Type conversions
- Increment and decrement operators
- Bitwise operators
- Assignment operators and expressions
- Conditional expressions
1. Variable names
There are some restrictions on the names of variables and symbolic constants. Names are made up of letters and digits; the first character must be a letter. The underscore ``_'' counts as a letter;
Don't begin variable names with underscore, however, since library routines often use such names. Upper and lower case letters are distinct, so x and X are two different names. Traditional C practice is to use lower case for variable names, and all upper case for symbolic constants.
Keywords like if, else, int, float, etc., are reserved: you can't use them as variable names.
2. Data types and sizes
There are only a few basic data types in C:
char - a single byte, capable of holding one character in the local character set
int - an integer, typically reflecting the natural size of integers on the host machine
float - single-precision floating point
double - double-precision floating point
In addition, there are a number of qualifiers that can be applied to these basic types. short and long apply to integers:
short int sh;
long int counter;
The intent is that short and long should provide different lengths of integers where practical; int will normally be the natural size for a particular machine. short is often 16 bits long, and int either 16 or 32 bits. Each compiler is free to choose appropriate sizes for its own hardware.
The qualifier signed or unsigned may be applied to char or any integer. unsigned numbers are always positive or zero, and obey the laws of arithmetic modulo 2n, where n is the number of bits in the type. So, for instance, if chars are 8 bits, unsigned char variables have values between 0 and 255, while signed chars have values between -128 and 127 (in a two's complement machine.) Whether plain chars are signed or unsigned is machine-dependent, but printable characters are always positive.
The standard headers <limits.h> and <float.h> contain symbolic constants for all of these sizes.
3. Constants
An integer constant like 1234 is an int. A long constant is written with a terminal l (ell) or L, as in 123456789L; Unsigned constants are written with a terminal u or U, and the suffix ul or UL indicates unsigned long.
Floating-point constants contain a decimal point (123.4) or an exponent (1e-2) or both; their type is double, unless suffixed. The suffixes f or F indicate a float constant;
The value of an integer can be specified in octal or hexadecimal instead of decimal. A leading 0 (zero) on an integer constant means octal; a leading 0x or 0X means hexadecimal.
A character constant is an integer, written as one character within single quotes, such as 'x'.
The character constant '\0' represents the character with value zero, the null character.
A constant expression is an expression that involves only constants. Such expressions may be evaluated at during compilation rather than run-time
i.e
#define MAXLINE 1000
char line[MAXLINE+1];
A string constant, or string literal, is a sequence of zero or more characters surrounded by double quotes, as in
"I am a string". String constants can be concatenated at compile time:
"hello, " "world"
is equivalent to
"hello, world"
A string constant is an array of characters. The internal representation of a string has a null character '\0' at the end.
The standard library function strlen(s) returns the length of its character string argument s, excluding the terminal '\0'.
Be careful to distinguish between a character constant and a string that contains a single character: 'x' is not the same as "x". The former is an integer, used to produce the numeric value of the letter x in the machine's character set. The latter is an array of characters that contains one character (the letter x) and a '\0'.
There is one other kind of constant, the enumeration constant. An enumeration is a list of constant integer values, as in
enum boolean { NO, YES };
Enumerations provide a convenient way to associate constant values with names, an alternative to #define.
4. Bitwise operators
C provides six operators for bit manipulation; these may only be applied to integral operands, that is, char, short, int, and long, whether signed or unsigned.
& - bitwise AND
| - bitwise inclusive OR
^ - bitwise exclusive OR
<< - left shift
>> - right shift
~ - one's complement (unary)
AND operator & is often used to mask off some set of bits.
OR operator | is used to turn bits on.
exclusive OR operator ^ sets a one in each bit position where its operands have different bits, and zero where they are the same.
We must distinguish the bitwise operators & and | from the logical operators && and ||. For example, if x is 1 and y is 2, then x & y is zero while x && y is one.
The shift operators << and >> perform left and right shifts of their left operand by the number of bit positions given by the right operand, which must be non-negative.
i.e x << 2 (equivalent to x^2).
The unary operator ~ yields the one's complement of an integer; that is, it converts each 1-bit into a 0-bit and vice versa.
5. Assignment Operators and Expressions
An expression such as
i = i + 2
can be compressed as
i += 2
The operator += is called an assignment operator.
Most binary operators have a corresponding assignment operator op=, where op is one of
+ - * / % << >> & ^ |
If expr1 and expr2 are expressions, then
expr1 op= expr2
is equivalent to
expr1 = (expr1) op (expr2)
i.e. x *= y + 1
means
x = x * (y + 1)
rather than
x = x * y + 1
6. Conditional Expressions
The conditional expression
expr1 ? expr2 : expr3
the expression expr1 is evaluated first. If it is non-zero (true), then the expression expr2 is evaluated, and that is the value of the conditional expression. Otherwise expr3 is evaluated, and that is the value.
7. Precedence and Order of Evaluation
Below table summarizes the rules for precedence and associativity of all operators, including those that we have not yet discussed. Operators on the same line have the same precedence; rows are in order of decreasing precedence, so, for example, *, /, and % all have the same precedence, which is higher than that of binary + and -.
- Variable names
- Data types and sizes
- Constants
- Declarations
- Arithmetic operators
- Relational and logical operators
- Type conversions
- Increment and decrement operators
- Bitwise operators
- Assignment operators and expressions
- Conditional expressions
1. Variable names
There are some restrictions on the names of variables and symbolic constants. Names are made up of letters and digits; the first character must be a letter. The underscore ``_'' counts as a letter;
Don't begin variable names with underscore, however, since library routines often use such names. Upper and lower case letters are distinct, so x and X are two different names. Traditional C practice is to use lower case for variable names, and all upper case for symbolic constants.
Keywords like if, else, int, float, etc., are reserved: you can't use them as variable names.
2. Data types and sizes
There are only a few basic data types in C:
char - a single byte, capable of holding one character in the local character set
int - an integer, typically reflecting the natural size of integers on the host machine
float - single-precision floating point
double - double-precision floating point
In addition, there are a number of qualifiers that can be applied to these basic types. short and long apply to integers:
short int sh;
long int counter;
The intent is that short and long should provide different lengths of integers where practical; int will normally be the natural size for a particular machine. short is often 16 bits long, and int either 16 or 32 bits. Each compiler is free to choose appropriate sizes for its own hardware.
The qualifier signed or unsigned may be applied to char or any integer. unsigned numbers are always positive or zero, and obey the laws of arithmetic modulo 2n, where n is the number of bits in the type. So, for instance, if chars are 8 bits, unsigned char variables have values between 0 and 255, while signed chars have values between -128 and 127 (in a two's complement machine.) Whether plain chars are signed or unsigned is machine-dependent, but printable characters are always positive.
The standard headers <limits.h> and <float.h> contain symbolic constants for all of these sizes.
3. Constants
An integer constant like 1234 is an int. A long constant is written with a terminal l (ell) or L, as in 123456789L; Unsigned constants are written with a terminal u or U, and the suffix ul or UL indicates unsigned long.
Floating-point constants contain a decimal point (123.4) or an exponent (1e-2) or both; their type is double, unless suffixed. The suffixes f or F indicate a float constant;
The value of an integer can be specified in octal or hexadecimal instead of decimal. A leading 0 (zero) on an integer constant means octal; a leading 0x or 0X means hexadecimal.
A character constant is an integer, written as one character within single quotes, such as 'x'.
The character constant '\0' represents the character with value zero, the null character.
A constant expression is an expression that involves only constants. Such expressions may be evaluated at during compilation rather than run-time
i.e
#define MAXLINE 1000
char line[MAXLINE+1];
A string constant, or string literal, is a sequence of zero or more characters surrounded by double quotes, as in
"I am a string". String constants can be concatenated at compile time:
"hello, " "world"
is equivalent to
"hello, world"
A string constant is an array of characters. The internal representation of a string has a null character '\0' at the end.
The standard library function strlen(s) returns the length of its character string argument s, excluding the terminal '\0'.
Be careful to distinguish between a character constant and a string that contains a single character: 'x' is not the same as "x". The former is an integer, used to produce the numeric value of the letter x in the machine's character set. The latter is an array of characters that contains one character (the letter x) and a '\0'.
There is one other kind of constant, the enumeration constant. An enumeration is a list of constant integer values, as in
enum boolean { NO, YES };
Enumerations provide a convenient way to associate constant values with names, an alternative to #define.
4. Bitwise operators
C provides six operators for bit manipulation; these may only be applied to integral operands, that is, char, short, int, and long, whether signed or unsigned.
& - bitwise AND
| - bitwise inclusive OR
^ - bitwise exclusive OR
<< - left shift
>> - right shift
~ - one's complement (unary)
AND operator & is often used to mask off some set of bits.
OR operator | is used to turn bits on.
exclusive OR operator ^ sets a one in each bit position where its operands have different bits, and zero where they are the same.
We must distinguish the bitwise operators & and | from the logical operators && and ||. For example, if x is 1 and y is 2, then x & y is zero while x && y is one.
The shift operators << and >> perform left and right shifts of their left operand by the number of bit positions given by the right operand, which must be non-negative.
i.e x << 2 (equivalent to x^2).
The unary operator ~ yields the one's complement of an integer; that is, it converts each 1-bit into a 0-bit and vice versa.
5. Assignment Operators and Expressions
An expression such as
i = i + 2
can be compressed as
i += 2
The operator += is called an assignment operator.
Most binary operators have a corresponding assignment operator op=, where op is one of
+ - * / % << >> & ^ |
If expr1 and expr2 are expressions, then
expr1 op= expr2
is equivalent to
expr1 = (expr1) op (expr2)
i.e. x *= y + 1
means
x = x * (y + 1)
rather than
x = x * y + 1
6. Conditional Expressions
The conditional expression
expr1 ? expr2 : expr3
the expression expr1 is evaluated first. If it is non-zero (true), then the expression expr2 is evaluated, and that is the value of the conditional expression. Otherwise expr3 is evaluated, and that is the value.
7. Precedence and Order of Evaluation
Below table summarizes the rules for precedence and associativity of all operators, including those that we have not yet discussed. Operators on the same line have the same precedence; rows are in order of decreasing precedence, so, for example, *, /, and % all have the same precedence, which is higher than that of binary + and -.
[C programming] Input and Output
We cover below points.
- Standard Input and output
- Formatted output - printf
- Variable-length argument Lists
- Formatted input - scanf
- File access
- Error handling - stderr and exit
- Line input and output
- Miscellaneous Functions
1. Standard Input and output
The simplest input mechanism is to read one character at a time from the standard input, normally the keyboard, with getchar.
int getchar(void)
getchar returns the next input character each time it is called, or EOF when it encounters end of file.
The function
int putchar(int)
is used for output: putchar(c) puts the character c on the standard output.
check other standard I/O functions in stdio.h
2. Formatted output - printf
printf converts, formats, and prints its arguments on the standard output under control of the format. It returns the number of characters printed.
int printf(char *format, arg1, arg2, ...);
3. Variable-length argument Lists
This section shows how to write a function that processes a variable-length argument list in a portable way.
Our program, minprintf, will process the format string and arguments but will call the real printf to do the format conversions.
4. Formatted input - scanf
scanf reads characters from the standard input, interprets them according to the specification in format, and stores the results through the remaining arguments.
int scanf(char *format, ...)
sscanf scans the string according to the format in format and stores the resulting values through arg1, arg2, etc. These arguments must be pointers.
int sscanf(char *string, char *format, arg1, arg2, ...)
5. File access
File pointer, FILE *fp, points to a structure that contains information about the file, such as the location of a buffer, the current character position in the buffer, whether the file is being read or written, and whether errors or end of file have occurred.
FILE *fp;
FILE *fopen(char *name, char *mode);
This says that fp is a pointer to a FILE, and fopen returns a pointer to a FILE. Notice that FILE is a type name, like int, not a structure tag; it is defined with a typedef.
Check how to use file I/O functions in stdio.h.
6. Error handling - stderr and exit
Output stream, called stderr, is assigned to a program in the same way that stdin and stdout are. Output written on stderr normally appears on the screen even if the standard output is redirected.
Check more detail in errno.h and error handling here.
In stdlib.h defines how to use exit() function.
Note that within main, return expr is equivalent to exit(expr).
7. Line input and output
The standard library stdio.h provides an input and output routine fgets().
char *fgets(char *line, int maxline, FILE *fp)
fgets reads the next input line (including the newline) from file fp into the character array line; at most maxline-1 characters will be read. The resulting line is terminated with '\0'.
Normally fgets returns line; on end of file or error it returns NULL.
For output, the function fputs writes a string (which need not contain a newline) to a file:
int fputs(char *line, FILE *fp)
It returns EOF if an error occurs, and non-negative otherwise.
The library functions gets and puts are similar to fgets and fputs, but operate on stdin and stdout. Confusingly, gets deletes the terminating '\n', and puts adds it.
8. Miscellaneous Functions
- Standard Input and output
- Formatted output - printf
- Variable-length argument Lists
- Formatted input - scanf
- File access
- Error handling - stderr and exit
- Line input and output
- Miscellaneous Functions
1. Standard Input and output
The simplest input mechanism is to read one character at a time from the standard input, normally the keyboard, with getchar.
int getchar(void)
getchar returns the next input character each time it is called, or EOF when it encounters end of file.
The function
int putchar(int)
is used for output: putchar(c) puts the character c on the standard output.
check other standard I/O functions in stdio.h
2. Formatted output - printf
printf converts, formats, and prints its arguments on the standard output under control of the format. It returns the number of characters printed.
int printf(char *format, arg1, arg2, ...);
3. Variable-length argument Lists
This section shows how to write a function that processes a variable-length argument list in a portable way.
Our program, minprintf, will process the format string and arguments but will call the real printf to do the format conversions.
void minprintf(char *fmt, ...)
{
va_list ap; /* points to each unnamed arg in turn */
char *p, *sval;
int ival;
double dval;
va_start(ap, fmt); /* make ap point to 1st unnamed arg */
for (p = fmt; *p; p++) {
if (*p != '%') {
putchar(*p);
continue;
}
switch (*++p) {
case 'd':
ival = va_arg(ap, int);
printf("%d", ival);
break;
case 'f':
dval = va_arg(ap, double);
printf("%f", dval);
break;
case 's':
for (sval = va_arg(ap, char *); *sval; sval++)
putchar(*sval);
break;
default:
putchar(*p);
break;
}
}
va_end(ap); /* clean up when done */
}
4. Formatted input - scanf
scanf reads characters from the standard input, interprets them according to the specification in format, and stores the results through the remaining arguments.
int scanf(char *format, ...)
sscanf scans the string according to the format in format and stores the resulting values through arg1, arg2, etc. These arguments must be pointers.
int sscanf(char *string, char *format, arg1, arg2, ...)
5. File access
File pointer, FILE *fp, points to a structure that contains information about the file, such as the location of a buffer, the current character position in the buffer, whether the file is being read or written, and whether errors or end of file have occurred.
FILE *fp;
FILE *fopen(char *name, char *mode);
This says that fp is a pointer to a FILE, and fopen returns a pointer to a FILE. Notice that FILE is a type name, like int, not a structure tag; it is defined with a typedef.
Check how to use file I/O functions in stdio.h.
6. Error handling - stderr and exit
Output stream, called stderr, is assigned to a program in the same way that stdin and stdout are. Output written on stderr normally appears on the screen even if the standard output is redirected.
Check more detail in errno.h and error handling here.
In stdlib.h defines how to use exit() function.
Note that within main, return expr is equivalent to exit(expr).
7. Line input and output
The standard library stdio.h provides an input and output routine fgets().
char *fgets(char *line, int maxline, FILE *fp)
fgets reads the next input line (including the newline) from file fp into the character array line; at most maxline-1 characters will be read. The resulting line is terminated with '\0'.
Normally fgets returns line; on end of file or error it returns NULL.
For output, the function fputs writes a string (which need not contain a newline) to a file:
int fputs(char *line, FILE *fp)
It returns EOF if an error occurs, and non-negative otherwise.
The library functions gets and puts are similar to fgets and fputs, but operate on stdin and stdout. Confusingly, gets deletes the terminating '\n', and puts adds it.
8. Miscellaneous Functions
Subscribe to:
Posts (Atom)