--------------------------------------------------------------------------- Some of the code here will need mods to enable it to work on amiga's. All the code works fine apart from one bug, i will let you find that one he he...L8z pCm......................................................... ->iNDUSTRIAl sTRENGTh<- ---------------------------------------------------------------------------- 'C' Programming Course - Workbook 1. ------------------------------------- Introduction. ------------- C is a small language and an elegant language. It has imperfections which are easier to live with than the restrictions of other languages such as standard PASCAL. Most of these other languages have non-standard extensions to make them useable. Extensions to C are achieved through macros in the pre-processor or additional libraries of functions. Many aspects of the language challenge current practice in other "standard" programming languages and it is arguable which is the better approach. Features that other languages regard as transparent, for example passing parameters by reference, C places under the responsibility of the programmer. Many of these features are implemented using the pointer which is a far more powerful and flexible construction in C than in other languages. As a language C contains no input/output statements. These are defined within standard libraries of functions. This ensures the compiler is small and easily portable. However, differences in the implementation of these "standard" functions does occur. C has a powerful set of operators as standard but some, the increment /decrement operators in particular, are directly analogous to machine instructions or addressing modes on the PDP-11. This was the machine on which the first full C compiler was implemeted. This gives rise to some inconsistencies across various implementations. C is a modular language but does not exhibit the modularity of modern languages. Limited privacy of data and functions within files is achieved using the keyword static. There is no inter-module checking of imported/exported functions and data. Amongst the criticisms aimed at C the most serious are the implementation dependent nature of the increment/decrement operator and the fact that the compiler can reorder evaluation within expressions and parameter lists. C uses multiple symbols for relational and equality operators and makes multiple use of some of these symbols for logical and arithmetic operators. Relational operators such as != and >= cannot be specified out of order as they then have a different meaning. ============================================================================== THE HELLO WORLD PROGRAM. (Kernigan and Ritchie Chapter 1 Pg 8) ------------------------ #include /* header for standard i/o library */ /* (pre-processor directive) */ main() /* start point for program execution */ { /* start of main() statements */ printf("hello, world\n"); /* print output to stdout device */ } /* end of main() statements */ The #include Statement. ----------------------- #include is a request to the pre-processor to include the header file (.h) for the standard i/o library. This makes available to your program certain i/o functions and constants, in this case the printf statement. This line will normally be found in every program. The right angle brackets <> tell the pre-processor to find the header file in the standard library directory. This is usually pre-defined. Using TurboC (and many other compilers), the program will compile correctly if this statement is omitted, but the compiler will not be able to perform error checking for valid use. The Keyword main(). ------------------- The keyword main() signifies the start of the main statement block. Statements "belonging to" main() are enclosed in braces {}. Program execution always begins at main(). The printf() Statement. ----------------------- The printf statement writes output to the screen. As indicated above, printf() is actually a function found in the standard i/o library. The output sent to the screen is enclosed between double quotes "" and is known as the control string. The \n is a special character meaning print a new line. NOTE: the output in printf MUST be entirely on one line. If the output is too long then two or more printf statements may be specified. printf("hello,"); printf("world\n"); Statements in General. ---------------------- NOTE 1: all executable statements end in a semi-colon. Pre-processor directives such as #include do not end in semi colon. NOTE 2: that #include, main() and printf() are all in lower case. ** THIS IS IMPORTANT ** All C language key words are in lower case and in C lower case and upper case are different (the language is case sensitive). Thus main, Main and MAIN are ALL different and only main is a valid C keyword. ============================================================================== VARIABLES. ---------- A variable definition specifies a type and the variable name. More than one variable may be defined on one line, each variable name separated by a comma. E.g. int counter; int x,y,z; char ch; float realnum; The variable may also be initialized. E.g. int counter = 100; char ch = '*'; int x=0, y=1, z=2; Variable Names or Identifiers. ------------------------------ Variables and functions must both be given a name (identifier). ³ Valid characters are letters, digits and underscores. The first character MUST be a letter. Upper and lower case letters are different. Identifiers can be any length but ANSI standards recommend that the first 31 characters are unique. (This may depend on the particular implementation). Beware of using predefined identifiers (keywords) which are always lower case. E.g. if, then, else, int, long, etc. Data Types. ----------- All variables MUST be defined with their assigned types 4 basic data types are defined in C. char - a character int - an integer float - single precision floating point double - double precision floating point Additional qualifiers can be used with integers. (int is optional). E.g short int, long int, unsigned int The range of values represented by the various data types is implementation dependent. Also valid are: long float, long unsigned, signed char. Typical ranges for the PC (a 16 bit machine). type size range ------------------------------------ char 8 bits 0 to 255 short 16 bits -32768 to +32767 int 16 bits -32768 to +32767 unsigned 16 bits 0 to 65,535 long 32 bits -2147483648 to +2147483647 float 32 bits 1E-36 to 1E+36 7 bits precision double 64 bits 1E-303 to 1E+303 13 bits precision ============================================================================== NUMERIC CONSTANTS. ------------------ Numeric constants may be assigned to integer or floating point variables to initialize them to a known state. Integer constants are decimal by default. Octal constants are preceded by a O. Hexadecimal constants are preceded by Ox. Long integers are followed by L. E.g. x = 10; (decimal) x = O12; (octal) x = OxA; (hexadecimal) long_x = 10L; Floating constants can be specified with a decimal point and fraction or in scientific notation. E.g. 6.7, 1.345E7, 0.1345E8. ============================================================================== THE OUTPUT STATEMENT Printf(). ------------------------------ Consider the following program: ------------------------------- #include main() { int x; char c; float f; c = 'a'; printf("The value of the character variable is - %c",c); x = 100; printf("The value of the integer variable is - %d",x); f = 3.1412; printf("The value of the floating pt. variable is - %f",f); printf("The contents of the three variables are - %c %d %f",c,x,f); } This program defines three variables of different types: a character, an integer and a floating point number (or real). Each variable is assigned an appropriate value (a constant). The printf() function is then used to print out the contents of each variable. The fourth printf() shows the use of multiple arguments. Printf(). --------- The full form of the printf statement consists of a control string enclosed in double qoutes "" and a list of variables or expressions to be output. Format: printf("control string",arg1,arg2,..argn); Each variable or expression must be accompanied by an appropriate format specifier in the control string. Format specifiers are % signs followed by single letter to denote the format required. Again the "control string" is the actual output. It includes exactly one format specifier for each argument in the statement. Too few or too many format specifiers is an error. The full list of format specifiers is: %d - decimal integer %o - unsigned octal %x - unsigned hexadecimal %u - unsigned decimal integer %c - single character %s - string (null terminated) %f - floating point number %e - floating pt. in scientific notation %g - %f or %e whichever is shorter The character 'l' may precede specifiers d,o,x or u to specify long integers. The following may also precede specifiers: positive number - this is the minimum number of characters to be printed (field width). negative number - as for positive numbers but with chars. left justified. '.' and number - the number of decimal places to print for a floating point number. E.g. printf("%4.2f",real); printf("%-5d",number); printf("%ld",long_number); ============================================================================== THE INPUT FUNCTION Scanf(). --------------------------- Consider the following program: ------------------------------- #include main() { int num; printf("Enter a number - "); scanf("%d",&num); printf("\nThe number you entered was: %d\n",num); } Format: scanf("control string",arg1,arg2,...argn); The control string has almost the same format as for the printf function. However, this does not imply that scanf actually outputs anything !. Scanf is used solely for input. E.g. scanf("%5d",&num); Specifiers of the form %5.2f and %-5d are invalid in scanf !. The & character indicates that the address of the variable rather than the value of the variable itself is passed to the scanf function. Scanf() is not used often as it requires accurate input to function correctly. Characters in the input string must comply exactly with those specified in the control string. Characters in the control string which are not format specifiers must match with identical characters typed in the input string. ============================================================================== FAHRENHEIT TO CELSIUS CONVERSION (1). ------------------------------------- Summary ------- The following program combines the material from the previous exercises with the while statement to control the flow of the program. This in turn introduces relational operators and the concept of simple and compound statements. The results of complex expressions and the effects of type casting are examined and the effect this has on subsequent assignments. Consider the following program: ------------------------------- /* print Fahrenheit to Celsius table */ #include main() { int fahr,celsius; - define integer variables int lower,upper,step; lower = 0; - initialize variables upper = 300; - by assignment. step = 20; fahr = lower; while (fahr <= upper) - loop while true { - begin statements celsius = 5 * (fahr - 32) / 9; - arithmetic expression printf("%d\t%d\n",fahr,celsius); - print variables fahr = fahr + step; } - end while statements } - end of main block Five integer variables have been defined by this program. The variables lower, upper ansd step are all given initial values in the first three lines of the main() code (i.e. initialized). The initialization of variables may be combined with the definition of the variables. E.g. int lower = 0, upper = 300, step = 20; The effect of this is IDENTICAL to the previous code but is shorthand notation. Run the program. Are the results as you expect ?. The value for celsius is only approximate as it has been defined as an integer and as we have seen, an integer has limited numeric range and no fractional part. Convert the variable celsius to a float and change the printf statement accordingly. float celsius; int fahr; . . printf("%d\t%f\n",fahr,celsius); Recompile and check the results of each of the following arithmetic expressions: celsius = 5 * (fahr - 32) / 9; celsius = 5 / 9 * (fahr - 32); celsius = 5.0 / 9.0 * (fahr - 32); celsius = 5.0 / 9 * (fahr - 32); Explain the results. The expression on the right hand side evaluates to a temporary result which is subsequently assigned to the left hand side. The size or type of the temporary result is governed by the largest type in the right hand side expression. This is not strictly what happens but the effect is identical and it is easier to understand this way. This is demonstrated by the floating point constants in the last two examples. Only one floating point constant is required for correct operation. The second example will always generate an incorrect result because the value resulting from the division of the two integer constants 5/9 is zero. All of this could have been avoided in the original code by making the variable fahr of type float. Type casts may also be used to control the type of the temporary result on the right hand side. float b; int a = 30000, c = 20000; b = (float) a + c; Enclosing the type name in parenthesis before the expression will control the type of the temporary result. Type are automatically converted (promoted) across assignments in C. For example an integer expression can be assigned to a result of type float. Consider the previous example without the type cast. float b; int a = 30000, c = 20000; b = a + c; What is the result ?. The result is undefined as the numeric range of an integer is only 32768 (16 bit machine) and as both variables in the right hand side are of type integer, the temporary result must be of type integer. The true result 50000 cannot be represented by an integer and so the result is an overflow condition. While Loops. ------------ Format: while (expression) statement; The statement is repeated while 'expression' is TRUE. An expression is TRUE if it has a non-zero value and FALSE if it is zero. NOTE: TRUE and FALSE are not part of the C language. They are not keywords nor are they defined automatically. while (fahr <= upper) { celsius = 5 * (fahr - 32) / 9; printf("%d\t%d\n",fahr,celsius); fahr = fahr + step; } In the example the loop continues to execute until fahr is greater than upper. The expression fahr <= upper is evaluated for each iteration of the loop and returns either TRUE or FALSE. When fahr is greater than upper the result is FALSE and the loop terminates. The operator <= is a relational operator used to conduct tests in loops. Relational Operators. --------------------- The following relational operators are available: a == b a is equal to b a != b a is not equal to b a < b a is less than b a > b a is greater than b a <= b a is less than or equal to b a >= b a is greater than or equal to b They all evaluate to 1 when TRUE and zero when FALSE. Compound Statements. -------------------- Normally only the next statement (terminated by a semicolon) will be executed as part of the while loop. This is often refered to as a simple statement. Where more than one statement is to be executed as part of a (while) loop, the statements are collected into a compound statement. A compound statement is a collection of statements enclosed in braces '{' and '}'. E.g. while (expression) { statement1; statement2; . statementN; } After the loop terminates, the next statement folowing either the simple statement or the compound statement is executed. In the example this is the end of main() and the end of the program execution. Further exercises. ------------------ Modify the program to print a heading above the table. Experiment with the format specifiers in the printf statement to control the field width of both results. Use scanf() to obtain values for lower, upper and step. E.g. scanf("%d",&lower); ============================================================================== FAHRENHEIT TO CELSIUS CONVERSION (2). ------------------------------------- Summary ------- This example introduces the 'C' for loop and illustrates that it is a specialized form of the more general while loop. The use of another pre-processor directive #define is illustrated for defining constant values. Consider the modified version of the previous program: ------------------------------------------------------ #include #define LOWER 0 #define UPPER 300 #define STEP 20 /* print Fahrenheit to Celsius table */ main() { int fahr; for (fahr = LOWER; fahr <= UPPER; fahr = fahr + STEP) printf("%8d\t%8.2f\n",fahr,5*(fahr-32)/9); } The Pre-Processor Directive #define. ------------------------------------ #define is used to set up constant identifiers. Constant identifiers can improve the style, legibility and portability of a program. More importantly, they make the program easier to maintain. Constant identifiers are usually specified in upper case letters. E.g. #define BIGINT 10000 Note: there is no semi-colon at the end of the line. These directives are normally placed at the start of the program prior to the keyword 'main'. The effect of the directive is to replace all occurrences of the identifier (e.g. BIGINT) with the specified value (e.g. 10000) before the program is compiled. Hence the term pre-processor directive. The For Loop. ------------- Format: for (exp1; exp2; exp3) statement; The expressions exp1, exp2 and exp3 need not all be specified depending on use but the two semicolons MUST always be present. exp1 - is executed ONCE before the for loop begins. exp2 - is an expression which is evaluated before each iteration and the statement is then only executed if the result is TRUE. exp3 - is executed at the end of each iteration (after statement or a compound statement has been executed). The statement may be compound, simple or null. The for loop is directly equivalent to: exp1; while (exp2) { statement; exp3; } ============================================================================== PRIME NUMBERS. -------------- Summary ------- This example uses both a for loop and a while loop and introduces the if statement. Two new operators are also introduced, the binary modulus (or remainder) operator and the auto increment operator. A Program To Find Prime Numbers. -------------------------------- A prime number is an integer greater than or equal to 2 which can only be divided by 1 and itself. E.g. 2,3,5,7,11,13,17,19,23,29,..... Write a program to find prime numbers between 2 and some given upper limit. For each number (k) between 2 and LIMIT, check wether k is divisible by any number between 2 and k-1. How do you determine when a number is divisible by another ? #define LIMIT 1000 main() { int cnt = 0, j, k; for (k=2; k < LIMIT; ++k) { j = 2; while (k % j != 0) ++j; if (j == k) { ++cnt; if (cnt % 6 == 1) printf("\n"); printf("%12d",k); } } printf("\n\nThere are %d prime numbers less than %d\n\n",cnt,LIMIT); } Try the above program. There are two instances of the modulus operator in this program, explain their use in both cases. Exercises. ---------- Is the number of primes less than 10000 itself a prime number ?. If p and q are both prime numbers, then if q = p + 2 the pair p,q are called twin primes. E.g. 3 and 5 are twin primes. Find all twin primes less than LIMIT. Binary Operators. ----------------- The following are the five most commonly used binary operators. + - addition - - subtraction * - multiplication / - division % - modulus They are termed binary operators as they take two operators. Operators have a precedence... * and / have precedence over + and -. The order of precedence can be changed by the use of parenthesis. 6 + 2 * 3 = 12 (6 + 2) * 3 = 24 Increment And Decrement Operators. ---------------------------------- Increment and decrement operators add or subtract one from the operand. Increment operator is ++ Decrement operator is -- If the operator is prefixed: ++operand; --operand; The increment/decrement takes place before the variable is dealt with in an expression. If the operator is postfixed: operand++; operand--; The increment/decrement is postponed until after the variable is dealt with. Note: num1 = num2 + 1; and num1 = num2++; are not identical as num2 is only altered in the second case. If Statement. ------------- Format: if (expression) statement; or: if (expression) statement1; else statement2; If the expression is TRUE then statement or statement1 is executed. If the expression is FALSE then in the first case nothing is executed, but in the second statement2 is executed. Compound statements may be substituted for any of the statements above. ============================================================================== FAHRENHEIT TO CELSIUS CONVERSION (3). ------------------------------------- Summary ------- The purpose of this example is to introduce functions in an elementary way and to show the effects of automatic (local) variables and external variables. It also introduces the concepts of definition and declaration illustrating this with the keyword extern. ----------- Using the Fahrenheit to Celsius conversion program, move the while loop from main() into a seperate function called table. (Use the initial while loop version corrected to print out floating point values). #include main() { float fahr,celsius; int lower=0,upper=300,step=20; fahr = lower; table(); } table() /* the function table */ { while (fahr <= upper) { celsius = 5 * (fahr - 32) / 9; printf("%f\t%f\n",fahr,celsius); fahr = fahr + step; } } The function table is called from main() just as you would call the standard i/o function printf(). However, unlike printf(), table() has no arguments. Attempting to compile this program results in a number of compiler errors. This is because the code in table() cannot "see" the variables defined in main(). Variables defined inside main or inside a function are known as AUTOMATIC variables. They can only be referenced by the function in which they are defined. Variables may also be declared outside main or other functions and are known as EXTERNAL variables. External variables can be "seen" by main and other functions. There are two ways to rid this program of compilation errors. - make the variables external i.e visible to both main and table. - pass the variables as arguments to the function table as you would if calling printf. (this is the preferable solution as the function then becomes re-usable in other programs with no modifications required). Dealing with external variables first: Move all the variables above main() leaving them unchanged. #include float fahr,celsius; int lower=0,upper=300,step=20; main() { fahr = lower; table(); } table() /* the function table */ { while (fahr <= upper) { celsius = 5 * (fahr - 32) / 9; printf("%f\t%f\n",fahr,celsius); fahr = fahr + step; } } This now compiles and runs correctly. Check... What happens if the variables are placed between main() and table(). Try this with fahr only. #include float celsius; int lower=0,upper=300,step=20; main() { fahr = lower; table(); } float fahr; table() /* the function table */ { while (fahr <= upper) { celsius = 5 * (fahr - 32) / 9; printf("%f\t%f\n",fahr,celsius); fahr = fahr + step; } } Again this results in a compiler error as the reference to fahr in main() is before the definition of the variable. Now modify the code in main() to read as follows: main() { extern float fahr; fahr = lower; table(); } float fahr; etc.. This now compiles and runs succesfully. External Variables. ------------------- Defining variables outside main() and functions gives external variables. Syntactically they are the same as automatic/local variables. Before main() or a function can use an external variable, it must be made known through the process of declaration. The keyword extern is added before the type to indicate an external declaration. int ext_var; some_function() { extern int ext_var; . . } This would be repeated in all functions that use the external variable ext_var. However, extern declarations can be omitted. The usual practice is to place all external DEFINITIONS at the start of the program. The rule is if the DEFINITION occurs before the use of an external variable, then the DECLARATION may be omitted. (There are other implications for the use of the keyword extern) Definition And Declaration. --------------------------- An external variable must be defined ONCE outside any function. - Definition implies storage is allocated. The variable must also be declared in each function that wants to access it. - No storage is allocated. Simple Comparison Of Auto And External Variables. ------------------------------------------------- Auto Variables -------------- - Created automatically on the stack each time a function is entered. - Their contents are lost when a function exits. - They are not implicitly initialzed (hence the common compiler warning variable xxx used in function xxx before assignment). External Variables. ------------------- - "Seen" by main and all functions. - Can be initialized (more applicable to structured/complex types such as arrays. - Are allocated in "static" memory and retain their contents from one function call to the next (assuming they are not overwritten). - Implicitly initialized to zero. Does an external or automatic variable have to be declared/defined at the top of a function ?. The rule is the declaration/definition must follow an opening curly brace. This has other implications but for the moment we will follow rule that variables must be declared/defined at the top of a function. ============================================================================== 'C' FUNCTIONS. -------------- A function in C is equivalent to subroutines or functions in Fortran and procedures or functions in Pascal. C does not distinguish between procedures which do not return a value and functions which do. In C they are both classed as functions. The function is used to decompose a computing task into a number of smaller sub-tasks. These sub-tasks are arranged to perform specific operations which may then be called several times within the same program. Economic programming demands that functions should be written to be of general use wherever possible. This allows functions to be re-used in other programs. (E.g. the libraries of functions supplied with most C compilers). Good use of functions hide specific details from the main body or flow of a program. C supports modular programming by allowing programs (functions) to be written in several source files and subsequently linked together. NOTE: All functions are automatically exported to other modules (i.e. made global/public). The format of a function is: type function_name(arguments) argument_declarations; { declarations; executable statements; } We have already used some functions: printf(), scanf(). These were supplied in the standard i/o library. ============================================================================== RAISING A NUMBER TO A POSITIVE POWER. ------------------------------------- Summary. -------- This example introduces passing of arguments to functions and returning a value from a function - the function result. Consider the following example: ------------------------------- This program is used to raise a number to a given positive power. #include main() { int i; for (i=0; i<10; i++) printf("%d %d %d\n",i,power(2,i),power(-3,i)); return 0; } int power(int base, int n) { int i,p; p=1; for (i=1; i<=n; ++i) p = p * base; return p; } Study how the function power is called and how it returns the function result. The keyword return must be specified to return a SPECIFIC value. If return is not specified, the flow of the program will still return to the calling point at the end of the function. Run the program and experiment with it. Passing Arguments To Functions. ------------------------------- In C all arguments are passed 'by value'. That is the variables defined in the argument list actually create storage and become variables in their own right. The values defined in the argument list of the caller are assigned to the variables defined in the argument list of the function for use by that function. Passing arguments 'by reference' can be achieved using pointers and passing the address of the variable. More later... The argument list may be empty, e.g. int somefunction() if there are no arguments. Returning Values From Functions. -------------------------------- Return is used to return a specific value from a function The flow of code will automatically return even if no value is passed back. Return can also return control to the calling point before the end of a function. NOTE: When defining a function, the type of the return value will default to int. Thus if the return type is an integer, int need not be specified. E.g. max(int x, int y) { if (x > y) return(x); else return(y); } Other types may be returned by functions but these must be defined explicitly and they will require a function prototype. Modern versus Classic Style --------------------------- This is the 'classic style'. E.g. int somefunction(x,y) int x; int y; { int i; i = x + y; return(i); } There is a 'modern style' which is now more commonly used. You should be aware of both definitions as you will encounter both. E.g. int somefunction(int x, int y) { int i; i = x + y; return(i); } NOTE: in the classic style, only the argument variables are defined outside the braces (curly brackets). ============================================================================== PSUEDO RANDOM NUMBER GENERATOR. ------------------------------- Summary. -------- Both automatic and external variables have now been covered and the use of the keyword extern. This example introduces another keyword, static, which effects the action of automatic variables. Example. -------- Psuedo-random sequences of numbers can be generated using linear congruential methods. The following is an example: #define MULTIPLIER 25173 #define MODULUS 65536 #define INCREMENT 13849 #define INITIAL_SEED 17 random() { static int seed = INITIAL_SEED; seed = (MULTIPLIER * seed + INCREMENT) % MODULUS); return (seed); } By assigning the result of random divided by 65536.0 to a variable of type double, a random number in the range 0.0 to 1.0 is generated. Write a main() routine to call the function random and generate a random number in this way. Generate a 1000 such numbers and calculate the mean value. How close this is to 0.5 is an elementary check of the randomness of the generator. The Keyword Static. ------------------- Static variables are declared in a function and are private to that function. They are declared with the keyword 'static' and are allocated storage for the life of the program. Static variables are implicitly initialized to zero. The value within the variable is not lost when leaving the function. In essence, static variables behave in the same way as external variables except that they can only be "seen" by the function in which they are declared. E.g. int somefunction() { static int variable_name = 1; ... }  The 'C' Programming Course - WorkBook 2. ---------------------------------------- CHARACTER INPUT AND OUTPUT: getchar() and putchar(). ---------------------------------------------------- Input and output facilities are not part of the C language itself, but are provided through standard library routines. The standard library provides a set of functions (not all) for input and output. In C, input and output takes place through streams. A stream is a source or destination of data that may be associated with a disk or other peripheral. Both text and binary streams are supported through the functions in . A text stream is a sequence of characters, divided into lines. Each line consists of zero or more characters followed by the newline ('\n') character. The function getchar() reads a single character from the text stream known as the standard input device (stdin). This is normally associated with the keyboard. The function putchar() writes one character to the standard output text stream (stdout). This is normally associated with the screen. The standard input and output devices may be redirected to other input and output devices under certain operating systems, particularly DOS and UNIX. E.g. DOS> dir >outfile.txt In this example the output of the directory command is redirected to the file outfile.txt. Both getchar and putchar work with buffered i/o to avoid the excessive overhead of dealing with single characters. Buffered i/o means that lines of input or output are stored by the operating system and only passed to or from the application when the end of the line is reached. Getchar(). ---------- Format: ch = getchar(); This assigns the input character to the variable ch. To correctly handle the value EOF, ch is normally defined as a variable of type int. The value EOF is defined in the header file Thus: int ch; ch = getchar(); Putchar(). ---------- Format: putchar(ch); This sends ch to the standard output device. There is no restriction on the type of the variable ch when using putchar. ============================================================================== COPYING INPUT TO OUTPUT USING Getchar() AND Putchar(). ------------------------------------------------------ Consider the following example: ------------------------------- #include main() { int c; c = getchar(); while (c != EOF) { putchar(c); c = getchar(); } } The variable ch is of type int NOT char. This is because in C a character is treated as an unsigned 8 bit integer having a numeric range of 1 to 255. When getchar() reaches the end of the input, the value EOF will be returned. On most systems the value of EOF is defined as -1. This cannot be represented by a variable of type char thus ch must be a variable of type integer. Chars and integers may be freely intermixed in C programs. The relational operator != means "is not equal to". The above example can be simplified to: --------------------------------------- #include main() { int c; while ((c = getchar()) != EOF) putchar(c); } An assignment such as c = getchar() is an expression and has a value (the value of the l.h.s. after the assignment). This allows an assignment to appear as part of a larger expression. The precedence of the relational test (!=) is higher than the assignment operator (=) hence c=getchar() is enclosed in parenthesis to alter the order of evaluation. (c=getchar() != EOF) would assign either 0 or 1 (FALSE or TRUE) to c. That is the result of the relational test would be assigned to c NOT the character returned by getchar(). Run the program using the keyboard and screen for input and output. The EOF is returned from the keyboard by pressing CTRL- Z. Beware of the effects of buffered i/o. Run the program from the command line redirecting the input and output devices. Add a line to the program to verify the value of EOF. [ printf("%d\n",EOF); or printf("%d\n",c) ] ============================================================================== COUNTING CHARACTERS AND LINES IN INPUT. --------------------------------------- Write a program to count the number of characters and lines in an input text stream. This is a possible solution: #include main() { long nc; int c,nl; nc = 0; nl = 0; while ((c = getchar()) != EOF) { if (c == '\n') nl++; nc++; } printf("%ld\t%d\n",nc,nl); } The variable nc has been made a long integer as the number of characters in a given text file could easily exceed 32767. NOTE: the use of the format specifier %ld in the printf statement to cause the long to be printed correctly. The if statement uses the relational operator (==) is equal to. Do not confuse this with the assignment operator (=), one the most common mistakes in C as an assignment is perfectly valid in most cases. ============================================================================== ARRAYS OF CHARACTERS (STRINGS). ------------------------------- An array is a collection of variables of the same type organised consecutively and grouped for convenient handling. E.g. type variable[constant_expression]; char mikes_string[20]; The constant expression gives the length of the array. Storage is allocated for 20 characters in the example. NOTE in C, elements are always numbered from 0 to length-1. E.g. mikes_string[0]......mikes_string[19] The number enclosed in the square brackets is known as the subscript. The standard string terminator is the NULL character ('\0'). This convention is assumed when using many of the standard functions supplied with an implementation of the language. You are responsible for ensuring the NULL character is in place otherwise many of the standard string functions will continue accessing memory beyond the end of string until a suitable NULL byte is found. Individual elements of the array can be assigned and manipulated. E.g. mikes_string[4] = 'c'; The subscript can also be a variable. E.g. mikes_string[i] = 'c'; There is no runtime checking for invalid subscripts in C (as in other languages). Therefore mikes_string[20] will access something but it will not be a valid component of the example string. NOTE: if using an array of characters with scanf(), the name of an array is the address of the array. Therefore the address operator (&) is not required. scanf("%20s", mikes_string); A string may be initialized at compilation time: E.g. static char flower_string[] = "tulip"; "Classic" or older 'C' compilers required that the string variable be declared static or made external. Modern C compilers do not have this restriction and automatic string variables can be initialized. When a string is initialized, the size is automatically calculated together with the null terminator if the size of the array is left blank. ============================================================================== THE FUNCTIONS getline() AND putline(). -------------------------------------- Summary. -------- We will write a function getline() employing getchar() to read whole lines of text from the standard input device. A line of text is zero or more ASCII characters ending with the newline character '\n'. To read a line of characters: ----------------------------- int getline(char buf[]) { int c, i=0; while ((c = getchar()) != EOF && c != '\n') buf[i++] = c; } NOTE that the function argument char buf[] appears to be a character array except that there is no size specified. In this instance, the array is being passed "by reference" rather than by value. Structured types such as arrays are rarely passed by value in any language that uses the stack for parameter passing. This is because the amount of stack space is restricted and stack overflows are fatal errors and difficult to predict. It should also be noted that arrays can be passed by value. When a variable is passed by reference, the argument is the address of the variable rather than the variable itself. In C, the name of an array (no subscript) is the address of the start of the array. The relational test != means does not equal. A number of relational tests may be connected, in this case by a logical and (&&). Remember automatic variables are not implicitly initialized hence int i = 0;. The variable i is initialized each time the function is entered. i++ is the increment operator. It is losely equivalent to saying i = i + 1. ------------------- The getline() function developed above is incomplete for a number of reasons. First, if buf is an argument passed by reference it must refer to a character array outside the function getline. How does getline() know what size this array is to avoid overflowing the array. It doesn't !. The size must be passed as another argument. This size can then be tested in the while loop against the array index i. The second problem with getline() has to do with the way C handles character arrays. All C functions that deal with character arrays expect the array to be terminated with a NULL character. A special character constant has been set aside for this '\0'. This is literally a byte of zero value. NOTE that the length of a string in a fixed size array can be any length upto the size of the array and hence the NULL character can appear anywhere in the array after the string rather than at the end of the array. A NULL character must be appended to the array after the while loop in getline(). int getline(char buf[], int lim) { int c,i=0; while ((c=getchar()) != EOF && c != '\n' && i < (lim - 1)) buf[i++] = c; buf[i] = '\0'; } This version of getline() incorporates these changes. Note that there are two arguments: buf is passed by reference and lim by value. The test against the size of the array is i < (lim -1) why ? Remember if an array is declared as char string[30] then the first element is string[0] and the last string[29]. A test i < lim would account for this. The test is against lim -1 as space must be allowed for the NULL character. This version of getline() contains one important fault. The character is read into c before the test against lim - 1. That is we have read the character before checking if there is room to store it. This can be corrected by moving the test i < (lim-1) before (c=getchar()) != EOF. The reason this works is because each relational test is connected by the logical and operator. For the whole expression to evaluate to TRUE, each relational test must be true. If one relational test is FALSE there is no point in checking the remaining tests as the result of the whole expression must be FALSE. C "short circuits" the remaining tests and hence the assignment c=getchar() is not made. The final point about getline() is that whatever is calling the function must know when getline() has found EOF to stop any subsequent calls. If the getline reads zero characters it has reached the EOF therefore zero can be returned as a function result. The easiest way to do this is to return the value in the variable i. This has the added benefit that it returns the nuber of characters read or zero if EOF. However, at present a blank line ('\n') would have the same result as EOF. A subsequent test is required to check if the terminating character was a newline and if it was to append it to buf. int getline(char buf[], int lim) { int c,i=0; while (i < (lim - 1) && (c=getchar()) != EOF && c != '\n') buf[i++] = c; if (c == '\n') buf[i++] = c; buf[i] = '\0'; return(i); } Rewrite the program to count characters and lines in the input stream so that it makes use of the function getline(). A companion function putline() can also be written. This again takes an argument which is a character array passed by reference. Each character in the array is output using putchar() until the end of string is reached. int putline(char buf[]) { int i; for(i=0; buf[i] != '\0'; i++) putchar(buf[i]); } Increment/Decrement Operators. ------------------------------ An increment (or decrement) operator can either be prefixed (++i) or postfixed (i++), the increment operation taking place before or after the variable is used in an expression. So expressions like x = n++; and x = ++n; or buf[i++]; and buf[++i]; are not the same. Increment and decrement operators can only be applied to variables, so the expression (i+j)++ is illegal. ============================================================================== THE FUNCTION getword(). ----------------------- Summary. -------- Develop a function getword() which will read each successive "word" from a text string. A word in this instance is any group of characters seperated by whitespace (blank, tab or newline) characters. The function should provide notification when the end of the input string is reached. Getword(). ---------- The arguments required by getword() are the input text string and a string buffer to return each word found. The first action of the function is to find the start of a word by stepping over any preceeding whitespace. int getword(char s[], char word[]) { while (s[i] == ' ' || s[i] == '\t' || s[i] == '\n') i++; } The index into the input buffer cannot be a local variable as the function must be called repeatedly to obtain each successive word. It is therefore passed as an argument as well. Having found the start of a word, the function must then copy each character in the word to the output buffer. while (s[i] != ' ' && s[i] != '\t' && s[i] != '\n') word[j++] = s[i++]; A seperate subscript for the word buffer is required as each successive word must be returned as a seperate string starting at word[0] irrespective of it's position in the input buffer. It is the programmers responsibility to terminate each word correctly with an end of string character '\0'. Assembling all this: -------------------- int getword(char s[], int i, char word[]) { int j; while (s[i] == ' ' || s[i] == '\t' || s[i] == '\n') i++; j = 0; while (s[i] != ' ' && s[i] != '\t' && s[i] != '\n') word[j++] = s[i++]; word[j] = '\0'; } It is required that the function notify the calling routine when the end of the input string is reached. It is also necessary for the function to return the current position in the input string (i) on exit. This is achieved by checking for end of string (\0) as a valid terminator to a word in the second while loop. j = 0; while (s[i] != '\0' && s[i] != ' ' && s[i] != '\t' && s[i] != '\n') word[j++] = s[i++]; word[j] = '\0'; Using a similar scheme to getline(), return the current value of i or 0 if the end of string is reached. When has the end of string been reached ?. NOT necessarily when s[i] is equal to \0 as this may the terminator to a word which would then be lost. The answer is when j == 0 as this determines whether or not a word has been read. int getword(char s[], int i, char word[]) { int j; while (s[i] == ' ' || s[i] == '\t' || s[i] == '\n') i++; j = 0; while (s[i] != '\0' && s[i] != ' ' && s[i] != '\t' && s[i] != '\n') word[j++] = s[i++]; word[j] = '\0'; if (j == 0) return (0); else return (i); } NOTE that a semicolon is required at the end of the statement preceeding the else keyword unlike Pascal where it would be a syntax error. Trace the execution of the function and explain why a test for s[i] != '\0' is not required in the first while loop. Counting characters, lines and words. -------------------------------------- #include #include #define MAXLINE 120 char inbuf[MAXLINE]; main() { char wordbuf[MAXLINE]; int i, c = 0; long charcount = 0, wordcount = 0, linecount = 0; while ((c = get_line(inbuf,MAXLINE)) > 0) { charcount += c; linecount++; i = 0; while ((i = getword(inbuf,i,wordbuf)) > 0) { puts(wordbuf); wordcount++; } } printf("\n\nTotal chars - %d\n",charcount); printf("Total words - %d\n",wordcount); printf("Total lines - %d\n",linecount); } int get_line(char buf[], int lim) { int c,i; i = 0; while (i < (lim - 1) && (c=getchar()) != EOF && c != '\n') buf[i++] = c; if (c == '\n') buf[i++] = c; buf[i] = '\0'; return(i); } int getword(char s[], int i, char out[]) { int j; while (s[i] == ' ' || s[i] == '\t' || s[i] == '\n') i++; j = 0; while (s[i] != '\0' && s[i] != ' ' && s[i] != '\t' && s[i] != '\n') out[j++] = s[i++]; out[j] = '\0'; if (j == 0) return(0); else return(i); } ============================================================================== THE CHARACTER CLASSIFICATION MACROS. ------------------------------------ Summary. -------- To introduce character classification macros and the logical not operator. Discussion. ----------- The tests to determine wether or not a character is whitespace are very long winded. If punctuation characters were also included the tests would be unmanageable and also very inefficient. The standard libraries provide a number of routines to classify individual characters. These all look like functions but are actually macros. The code for a macro is included wherever it is referenced and although the resulting code is larger it is also faster as the overhead of calling a function is not incurred. The classification macros use a technique of table lookup which further increases their efficiency. int isspace(int c); - is char whitespace int isupper(int c); - is char uppercase int islower(int c); - is char lowercase int ispunct(int c); - is char punctuation int iscntrl(int c); - is char a control character Converting getword() to use isspace(). -------------------------------------- int getword(char s[], int i, char word[]) { int j; while (isspace(s[i])) i++; j = 0; while (s[i] != '\0' && !isspace(s[i])) word[j++] = s[i++]; word[j] = '\0'; if (j == 0) return(0); else return(i); } The Logical Not Operator. ------------------------- ! - Logical Not. Note that the isspace macro is preceded by the logical not operator. The result of this is taken to mean any character that is not a whitespace character. Remember FALSE = 0 and TRUE = any other value but usually 1. Not is used with logical operators: if (!(num1 > num2)) if (!isdigit(ch)) /* isdigit is a library function returning TRUE or FALSE. */ ============================================================================== READING AND WRITING TO A NAMED TEXT FILE ---------------------------------------- So far we have considered two named files: stdin - the standard input device stdout - the standard output device In fact, the file names stdin and stdout are what are known as file pointers. To open a named file from within a C program it is necessary to declare our own file pointer and associate it with a specific named file (a process referred to as opening a file). ---------- To declare a file pointer we use the "type" name FILE. (This is actually a structure defined in stdio.h and MUST be specified in upper case). E.g. FILE *fp; The * indicates that fp is a pointer to a variable of type FILE (see section on pointers later). ---------- To open a file use the function fopen() E.g. fp = fopen(fname, mode); fname is a character array or string constant and must be legal file specification for the operating system you are using (a valid drive, pathname and file for DOS). E.g. "myfile.txt" is a file on the current drive in the current directory on a DOS system. mode is the operation we are going to perform on the file. "r" - read trying to read a file which does not exist is an error "w" - write the file is created if it does not exist. The contents of an existing file are discarded. "a" - append the file is created if it does not exist. NOTE: that mode is string constant. Strictly, these mean open a file of the default type (either text or binary) depending on the current value of the fmode variable. The initial default is text. To ensure a file is opened in text mode use "rt", "wt" or "at". ---------- Finally, when we have finished with a file we must close it. E.g. fclose(fp); As all access to file is through the file pointer, it is important not to lose or overwrite the value. If this is done, the file can no longer be accessed, nor can it be closed. As the number of files which can be simultaneously open on a given system is limited, the file should be closed when finished with. ---------- The function c = getc(fp); reads one character from the file fp. Again c is defined as an integer to correctly check for EOF. NOTE: getchar(); is actually a macro defined as getc(stdin); The function putc(c,fp); writes one character to the file fp. NOTE: putchar(c); is defined as putc(c, stdout); ---------- #include main() { int c; FILE *fp; fp = fopen("myfile.txt","r"); while ((c = getc(fp)) != EOF) putchar(c); fclose(fp); } Add a second file pointer and open a file for output. Modify putchar(c) to write output to this new file and close the file at the end. The function fopen() returns the value NULL (defined in stdio.h) if the specified file cannot be opened. Modify the above program to test for a value of NULL when the file is opened. Add a string variable for the filename instead of the string constant used. Devise a way of reading the filename from the keyboard before opening the file. #include main() { int c; FILE *fp, *fp1; char fname[30]; printf("\nEnter input filename - "); scanf("%s",fname); if ((fp = fopen(fname,"r")) != NULL) { fp1 = fopen("output.txt","w"); while ((c = getc(fp)) != EOF) putc(c,fp1); fclose(fp1); fclose(fp); } } Again the file pointer fp must be assigned before the relational test != NULL. Why does the line scanf("%s",fname); not read scanf("%s",&fname); as we wish to take the address of fname for scanf to return the name read from the keyboard. The answer is that the name of an array in C is the address of the array. C does not allow arrays to be manipulated as a whole. Library functions are provided for operations such as finding the length, copying, searching for a substring, etc. Only individual elements may be assigned. ---------- Rewrite the functions getline() and putline() to use getc() and putc() instead of getchar() and putchar(). For getline() to work, fopen() and fclose() must be placed in main(). Why ?. fopen() and fclose() could be specified in putline(). How ?. Is this the best solution ?. ============================================================================== PROGRAM TO ANALYZE LETTER FREQUENCY IN A TEXT FILE. --------------------------------------------------- Requirement. ------------ In a given text file we wish to know the number of times each letter of the alphabet occurs. The case is unimportant and so is ignored. Solution. --------- The solution to this problem is simple. Read each character in turn from a file until the end of file is reached. If the character is lower case letter convert to uppercase then if character is a letter increment the equivalent letter count. The count is convieniently held in an array. #include #include main() { int c,i,letter[26]; FILE *fp; fp = fopen("myfile.txt","r"); for (i=0; i<26; i++) letter[i] = 0; while ((c = getc(fp)) != EOF) { c = toupper(c); if (c >= 'A' && c <= 'Z') ++letter[c - 'A']; } for (i=0; i<26; i++) { if (i % 6 == 0) printf("\n"); printf("%5c:%5d",'A'+i,letter[i]); } printf("\n\n"); } Inplementation. --------------- As has been stated previously, C treats characters as unsigned 8 bit integers. The character is represented using the code chosen by the machine manufacturer. This is usually ASCII. When a character constant is specified in an expression such as c - 'A' the ASCII value for 'A' (65) is subtracted from the variable c. ---------- int toupper(int c) is another function similar to the classification routines discussed earlier. It is included through the ctype.h header file. ---------- int letter[26]; is an array of integers as opposed to the arrays of characters met so far. Array Initialization. --------------------- In this program, the array is initialized in a for loop. This is portable with earlier C compilers which did not permit the initialization of automatic (non-static) structures, unions and arrays. ANSI compilers now permit this type of initialization but only by constant constructions. An array may be initialized by enclosing the initializers in curly braces. E.g. int letter[] = { 0,1,2,3,4,5,6,7,8,9,10,11,12, 13,14,15,16,17,18,19,20,21,22,23,24,25 }; Omitting the size of the array causes the compiler to compute the length by counting the initializers. If there are fewer initializers for an array than the number specified, then the missing elements will be zero for external, static and automatic variables. Too many initializers is an error. ============================================================================== Basic Page Formatting Utility ----------------------------- Consider the requirement to write a program which will take a text file and create paged output for subsequent printing on a line printer. Requirements: ------------- - To preset the page length (66 is the default size). - To preset a top and bottom margin for readability and to skip over the perforations. - To allow a preset left margin indentation again for readability if clipping into a ring binder. Decide how you would write a program to solve these requirements before reading the subsequent sections. Solution. --------- We have getline() and putline() to read and write each line of text in turn. Clearly we need variables to hold the page length, the size of top and bottom margins and the left margin. Action: while not EOF do get a line of input if top of a page then write header write left margin write line if bottom of page write footer end while It seems sensible to check for top of page before we write the line out and to check for bottom of page after we have written the line. (Think what happens on 1st page, subsequent pages and the final page). How do we know when we are at the top and bottom of the page ?. Maintain a variable containing the current line number. Each time a line is written out increment the line number. If the line number is initialised to zero, then when the line number is zero write out the header. When the line number is greater than pagelength - bottom margin then write footer and reset line number to zero. Action: while not EOF do get a line of input if line number = 0 then write header line number = top margin + 1 end if write left margin write line increment line number if line number > pagelength - bottom margin then write footer line number = 0 end if end while What happens on the last page if the number of lines does not fill the page ? Developments. ------------- Would the code be improved by moving the lines to write out the header and footer into a seperate function. ? Modify program to write a fixed header message out on each page. ? If the header message contains the character # then substitute the current page number. ? (This requires some additional knowledge which is covered in the next workbook). #include #define MAXLINE 120 char inbuf[MAXLINE]; int pagelength = 66; int header = 3, footer = 3; int leftmargin = 4; int linenumber = 0; main() { FILE *fpin, *fpout; char fname[30]; int i; printf("\nEnter filename - "); scanf("%s",fname); if ((fpin = fopen(fname,"r")) != NULL) { fpout = fopen("output.txt","w"); while (getline(inbuf,MAXLINE,fpin) > 0) { if (linenumber == 0) { for (i=0; i < header; i++) putc('\n',fpout); linenumber = header + 1; } for (i=0; i < leftmargin; i++) putc(' ',fpout); putline(inbuf,fpout); linenumber++; if (linenumber > (pagelength - footer)) { for (i=0; i < footer; i++) putc('\n',fpout); linenumber = 0; } } if (linenumber>0 && linenumber<=(pagelength-footer)) { for (i=linenumber; i <= (pagelength-footer); i++) putc('\n',fpout); for (i=0; i < footer; i++) putc('\n',fpout); } fclose(fpout); fclose(fpin); } } int getline(char buf[], int limit, FILE *fp) { int c, i = 0; while (i < (limit -1) && (c = getc(fp)) != EOF && c != '\n') buf[i++] = c; if (c == '\n') buf[i++] = '\n'; buf[i] = '\0'; return(i); } int putline(char buf[], FILE *fp) { int i; for(i=0; buf[i] != '\0'; i++)'C' Programming Course - Workbook 3 ------------------------------------ The Switch..Case Statement. --------------------------- In the previous workbook we wrote a program to determine the numbers of each alpha character that existed in a given file. A tally was kept by using the ascii value of the character to index into an array. This is fast and efficient for the alpha characters as they are arranged sequentially in the ascii character set. For characters that are not arranged sequentially we may choose to use a different method. This involves using the switch..case statement (a "computed goto"). We could also use a sequence of if.. else if.. else if..else. The case statement becomes the more efficient method as the number of "cases" increases. Consider the following program (K&R pg59): #include main() { 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 program uses a switch statement to categorise characters into numeric, whitespace and others. Each numeric character is recorded seperately in an array in the same way that the alpha characters were previously. Note in both cases that several cases are grouped together and processed with the same code. A block of code in a case clause normally ends with the break statement. If the break statement is omitted, execution continues in the next case clause. (See the description of break below). Switch. ------- The switch statement tests whether an expression matches one of a number of constant integer values (the cases) and branches accordingly. Each case is labelled with an integer constant or constant expression. The default case is executed if none of the other cases match the expression. The default case is optional. The cases may appear in any order. switch (EXPRESSION) { case CONST_EXPRESSION1 : STATEMENTS1; case CONST_EXPRESSION2 : STATEMENTS2; . . case CONST_EXPRESSIONn : STATEMENTSn; default : STATEMENTS; } Note the use of a break statement after each logical group of cases. The most common use of break is to exit from a specific case of a switch statement to the next statement following the switch statement. If this is not done, all subsequent code in the switch statement is executed even if it belongs to another case (unless a subsequent break is present). E.g. switch(ch) { case '+' : a += b; /* if + then both */ case '-' : a -= c; /* statements are */ break; /* executed */ case '*' : a *= b; /* only this statement*/ break; /* is executed */ default : puts("error"); /* ch != +,-,* */ } Or switch (getchar()) { case 'h' : case 'H' : puts("An H !!"); break; case 'g; : case 'G' : puts(" A G !!"); etc.. } Break can also be used to break out of any other loop. However, it is bad style and should be avoided where ever possible. E.g. #define TRUE 1 main() { int ch; while (TRUE) /* An infinite loop */ { puts("Enter a character...Q to quit!"); ch = getche(); if (ch == 'Q') break; } } ============================================================================== Recursive functions ------------------- C functions may be called recursively (i.e. a function may call itself). This is because each call to a function creates a new set of entries on the stack for return address, function arguments, function result and automatic variables. Two or more functions may be mutally recursive. The first function calls the second which in turn calls the first which then calls the second and so on. Recursive functions are not usually permitted for high integrity control and embedded software because of the difficulty in predicting stack depth and the catastrophic results of a stack overflow caused by unpredicted conditions. The following function is usually used to illustrate recursion. It computes the value of a factorial. int factorial(int n) { if (n <= 1) return (1); else return(n * factorial(n-1)); } The function keeps calling itself until the value of n is less than or equal to 1. When n is 1 the function returns the value of one from this level to the calling point - the next level up in the recursion. This returns the current value of n (2) times the value from the previous level (1). The function then returns to the next level which itself returns the current value of n (3) times the previous value (2*1). This process repeats for the next level which returns (4)*(3*2*1). This continues until the initial value of n is reached when the function returns to an external calling point. Write a program to test this function and use the debugging facilities (step, watches and breakpoints) to monitor the values in the variable n. ============================================================================== Integer to ascii conversion. ---------------------------- Develop a function to convert the character representation of an integer into an actual integer value. The following functions implement a non-recusive solution: int itoa(int n, char s[]) { int i,sign; if ((sign = n) < 0) n = -n; i = 0; do { s[i++] = n % 10 + '0'; } while ((n /= 10) > 0); if (sign < 0) s[i++] = '-'; s[i] = '\0'; reverse(s); } int reverse(char s[]) { int i,j,c; for (i=0, j=strlen(s)-1; i < j; i++,j--) { c = s[i]; s[i] = s[j]; s[j] = c; } } Do...While Loops. ----------------- The itoa function contains a do while loop. This is commonly known as the repeat until construction in other languages. do STATEMENT(S); while (EXPRESSION); The do..while loop ensures that the enclosed statements will be executed at least once. The Comma Operator. ------------------- The comma operator combines two or more expressions into one. E.g. while (a < b) { puts("hello"); puts("world"); } can be combined while (a < b) puts("Hello"),puts("world"); The comma operator can be used in the control expression of a loop. E.g. while (a = 1, a < b) Both expressions are evaluated but the result (TRUE or FALSE) is the result of EXPRESSION 2. A more usual use of the comma operator is with the for loop as in the example above. E.g. for (i=0, j=strlen(s)-1; i < j; i++,j--) Special Assignment Operators. ----------------------------- Note the use of a special assignment operator (n /= 10) in the do..while part of the itoa function. In general, an expression such as - num = num + 4; may be shortened to - num += 4; Also... num -= 4; num /= 4; num *= 4; This is one of a series of string operations where the characters/digits are generated in the reverse order to that required. This can be overcome using recursive techniques as the results can either be generated as the function recurses downwards or upwards. ============================================================================== Testing the itoa() function with getint(). ------------------------------------------ Instead of using scanf() to read in an integer to test the above function we will use a very simple function getint(). #include main() { int num1, num2; puts("Enter first number"); num1 = getint(); puts("Enter second number"); num2 = getint(); if (num1 > num2) puts("The first number is the biggest \n"); else puts("The second number is the biggest \n"); } int getint() { int n,c; for (n = 0; (c = getchar()) >= '0' && c <= '9'; n = n * 10 + c - '0') ; return n; } The function getint() uses a for loop to read in numeric characters, adding them as successively lower powers of ten to the running total. The function ends when a non numeric is typed. The function is in fact a very simple atoi() function. Use it to test the itoa() function above. ============================================================================== A Recursive Implementation of itoa(). ------------------------------------- The itoa() function can be re-written as a recusive function. The main saving in doing this is the function reverse() is no longer required as the recursive solution can be made to deliver the characters in the correct order. int itoar(int n, char s[], int i) { if (n < 0) { s[i] = '-'; return(itoar(-n,s,i+1)); } else { if (n>=10) i = itoar(n/10,s,i); s[i] = (n % 10 + '0'); s[i+1] = '\0'; return i+1; } } Use the getint() function to test this version and use the debugging facilities of Turbo C to trace the execution of itoa() as it recurses. ============================================================================== Extending getint() to return negative integers. ----------------------------------------------- The getint() function only returns positive integers at present. Devise a way of reading negative numbers. This is a possible solution. (There are better..see if you can devise one). int getint() { int n = 0, c, sign = 1; c = getchar(); if (c == '-') sign = -1; else if (c >= '0' && c <= '9') n = n * 10 + c - '0'; else return 0; while ((c = getchar()) >= '0' && c <= '9') n = n * 10 + c - '0'; return n * sign; } This brute force approach illustrates the problem of what to do with the first character if it isn't a negative sign. This problem can be greatly (and elegantly) simplified by using the following trick. int getint() { int n, c, sign = 1; if ((c = getchar()) == '-') sign = -1; else ungetc(c, stdin); for (n=0; (c=getchar()) >= '0' && c <= '9'; n = n * 10 + c - '0') ; return n * sign; } The ungetc() function "pushes" a character back on the specified stream, in this case stdin. The function is found in stdio.h. ============================================================================== The Continue Statement. ----------------------- Continue is similar to break and can be used with any loop. However, break terminates a loop immediately whereas continue does not terminate the loop but skips all remaining statements to the end of the loop and then begins the next iteration (if applicable). Again continue is bad style and should be avoided where possible. E.g. do { if ((ch = getchar()) == 'q' || ch == '\n') continue; printf("\n The character is "); putchar(ch); } while (ch != 'q'); Skip the printf/putchar statements if the character is a 'q' or '\n'. The while loop then exits if the character is a 'q'. ============================================================================== POINTERS. --------- A pointer declaration takes the form: type *variable; E.g. int *iptr; char *cptr; There are two operators for use with pointers: * - the indirection operator & - the address operator The address operator takes the address in memory of a variable for assignment to a pointer of the same data type. The indirection operator uses a pointer assigned to a variable to access that variable through the pointer. E.g. int *iptr; /* a pointer to an integer */ int num; /* an integer variable num */ iptr = # /* iptr assigned the address of variable num */ /* NOTE: at this point num and *iptr are interchangeable in an expression */ *iptr = 3; /* same effect as num = 3 */ *iptr = *iptr * 5 /* used on right and left hand sides of expressions */ ============================================================================== POINTERS AND ARRAYS. -------------------- Pointers may be assigned to specific array elements. E.g. int number[10]; /* array of 10 integers */ int *p; /* a pointer to an integer */ p = number; /* p points to first location of number i.e. number[0]. This is identical to saying: p = &number[0]; */ p = number + 3; /* This is identical to the expression: p = &number[3]; */ ============================================================================== INCREMENTING POINTERS. ---------------------- A pointer may be incremented and decremented using the increment and decrement operators (++ and --). E.g. p++; ++p; p--; --p; This is of use with arrays where the pointer will either be incremented to the next array element or decremented to point to the previous element. ============================================================================== POINTER ARITHMETIC. ------------------- If ptr1 and ptr2 point to different locations of the same array, then ptr2 - ptr1 is the number of elements between them (irrespective of the physical memory size between them). E.g. int strlen(s) char *s; { char *p = s; while (*p != '\0') p++; return(p-s); } E.g. void strcpy(d,s) char *d,*s; { while ((*d++ = *s++) != '\0') ; } ============================================================================== The itoa() function using pointers. ----------------------------------- #include char *itoar1(int n, char *s); main() { int num; char buf[20]; puts("Enter number"); num = getint(); itoa(num,buf); printf("Non-recursive conversion : %s\n",buf); itoar(num,buf,0); printf("Recursive conversion [1] : %s\n",buf); itoar1(num,buf); printf("Recursive conversion [2] : %s\n",buf); } int getint() { int n, c, sign = 1; if ((c = getchar()) == '-') sign = -1; else ungetc(c, stdin); for (n=0; (c=getchar()) >= '0' && c <= '9'; n = n * 10 + c - '0') ; return n * sign; } int itoa(int n, char s[]) { int i, sign; if ((sign = n) < 0) n = -n; i = 0; do { s[i++] = n % 10 + '0'; } while ((n /= 10) > 0); if (sign < 0) s[i++] = '-'; s[i] = '\0'; reverse(s); } int reverse(char s[]) { int i,j,c; for (i = 0, j = strlen(s) - 1; i < j; i++, j--) { c = s[i]; s[i] = s[j]; s[j] = c; } } int itoar(int n, char s[], int i) { if (n < 0) { s[i] = '-'; return(itoar(-n,s,i+1)); } else { if (n>=10) i = itoar(n/10,s,i); s[i] = (n % 10 + '0'); s[i+1] = '\0'; return i+1; } } char *itoar1(int n, char *s) { if (n < 0) { *s++ = '-'; return(itoar1(-n,s)); } else { if (n>=10) s = itoar1(n/10,s); *s++ = (n % 10 + '0'); *s = '\0'; return s; } } =============================================================================== POINTERS AND PASSING ARGUMENTS BY REFERENCE. -------------------------------------------- E.g. int swap(int *px, int *py) { int temp; temp = *px; *px = *py; *py = temp; } A function can only return one value by definition. The swap function above needs to return two i.e. the two integers it is trying to exchange. If the arguments are passed using pointers then the function affects the variables outside the function. If the integers were passed directly, then the local automatic variables would be exchanged but lost when the function returned to the calling point. This is the same as passing arguments by reference in PASCAL. (arguments declared var). ============================================================================== RANDOM NUMBERS (Continued). --------------------------- Turbo C has two library functions for obtaining random numbers, both are found in stdlib.h int rand(void); and int random(int num); rand() is found on UNIX and defined in ANSI.C so is preferred for portable code. A random number generator must be seeded before use. The portable method is to use srand also found in stdlib.h. void srand(unsigned seed); #include #include #include #define MAXARRAY 40 main() { int i, intarray[MAXARRAY]; srand(time(NULL) % 37); for (i=0; i a[j]) swap(&a[j-1], &a[j]); } Test this function and then modify so that it terminates after the first pass in which no two elements are interchanged. Use the modified random number generator and you will need to write a swap function (Refer to passing variables by reference). ============================================================================== MERGESORT. ---------- Merge sort works by considering what happens when two sorted arrays are merged together. merge(int a[], int b[], int c[], int m, int n) { int i = 0, j = 0, k = 0; while (i < m && j < n) if (a[i] < b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; while (i < m) c[k++] = a[i++]; while (j < n) c[k++] = b[j++]; } In the first pass of mergesort, we require each successive pair of integers to be in order. After the second pass each quartet of integers will be in order. After the third pass each octet etc... As each ordered "subarray" is merged, the resulting "subarray" is sorted. #define MAXSIZE 1024 mergesort(int key[], int n) { int j, k, m, w[MAXSIZE]; for (m = 1; m < n; m *= 2) ; if (n == m && n <= MAXSIZE) for (k = 1; k < n; k *= 2) { for (j = 0; j < n - k; j += 2 * k) merge(key + j; key + j + k, w + j, k, k); for (j = 0; j < n; ++j) key[j] = w[j]; } else { if (n != m) printf("error: size of array not a power of 2\n\n"); if (n >= MAXSIZE) printf("error: size of array is greater than MAXSIZE\n\n"); } } Write a program to test mergesort. The number of comparisons to sort n elements is proportional to nlogn. This makes the algorithm far more efficient than bubble sort. What is the main limitation of mergesort ?. Modify mergesort so that it can be used with an array of any size, not just with a size that is a power of two. Recall that any positive integer can be expressed as a sum of powers of two. For example: 27 = 16 + 8 + 2 + 1 Consider the array as a collection of subarrays of sizes that are powers of two. Sort the subarrays and then use merge() to produce the final sorted array. Write a program to test the relative efficiency of bubble() versus mergesort(). Generate test data using a random number generator to fill the arrays. Run the program on arrays of various sizes, say 10, 100, 500 and 1000 elements. Plot the running time for each sort versus the size of the array. For large array sizes, you should see the growth indicated by the formulas describing the relative efficiency of each method. For small array sizes, there is too much overhead to deteect this growth pattern. ============================================================================== Quicksort. ---------- Quicksort is a sorting algorithm devised by C.A.R.Hoare in 1962. This algorithm is particularly suited to a recursive solution although non-recursive implementations are possible. A standard library version of quicksort is usually supplied with C compilers. Given an array, one element is chosen as the pivot element and the remainder are partitioned into two subsets. One subset consists of values less than the chosen element, the other with values greater. (N.B. the partitioning operation sorts the elements into two subsets but each subset is not yet in order). The quicksort function is then called recursively for each of the two subsets. This continues until the subsets have fewer than two elements and hence the array is sorted. A great deal of care must be exercised in selecting the pivot element and in performing the subsequent partitioning if the algorithm is to function to it's full potential. The version given in Kernighan and Ritchie (page 87) does not do this, it simply selects the middle element of each subset as the pivot. If the contents of the array are randomly distributed then this is acceptable. This version degenerates rapidly for partially sorted arrays. void qsort(int v[], int left, int right) { int i,last; void swap(int v[], int i, int j); if (left >= right) /* check for fewer than 2 elements */ return; swap(v,left,(left + right)/2); /* select pivot and place in v[0] */ last = left; for (i = left + 1; i <= right; i++) if (v[i] < v[left]) swap(v,++last,i); swap(v,left,last); /* restore pivot */ qsort(v,left,last-1); qsort(v,last+1,right); } void swap(int v[], int i, int j) { int temp; temp = v[i]; v[i] = v[j]; v[j] = temp; } Given the following array of 12 integers, trace the execution of qsort. {4,7,9,5,2,5,9,2,1,9,-5,-3} QSORT - pointer version Can you rewrite QSORT to use pointers ?. First consider swap using pointers. int swap(int *px, int *py) { int temp; temp = *px; *px = *py; *py = temp; } In the previous version the array was passed by referencebut the array indexes were passed by value. In this version, both integers (the contents of the selected array positions) are passed by reference. A pointer is used to pass a value by reference. How would this be called from QSORT ?. Remember from pointers and arrays, given: int number[10]; /* an integer array */ int *p; /* a pointer to an integer */ p = number; is identical to p = &number[0]; p = number + 3; is identical to p = &number[3]; N.B. p and number+3 are both pointers (addresses); therefore we could write swap(v+left,v+last); which is identical to swap(&v[left],&v[last]); However we wish to eliminate array references from QSORT altogether. Let us decide that qsort will take two pointers as it's arguments. void qsort(int *left, int *right) { int *last, *temp; if (left >= right) return; swap(left,left + (right - left)/2); last = left; for (temp = left + 1; temp <= right; temp++) if (*temp < *left) swap(++last,temp); swap(left,last); qsort(left,last-1); qsort(last+1,right); } Trace the execution of this new version with the same array as before. ============================================================================== POINTERS TO FUNCTIONS. ---------------------- Format: int (* fptr)(); Use the right/left rule: Identify the variable name fptr Look right ) Look left * fptr is a pointer Look right () fptr is a pointer to a function Look left int fptr is a pointer to a function returning an integer. E.g. int fun(); /* must be declared if taking a funtions address */ main() { int (*fptr)(); /* declare a pointer to a function */ fptr = fun; (*fptr)(); /* call function */ } int fun() { .. } N.B. the only time a function name is used without parenthesis is when it's address is being taken [the line: fptr = fun;]. What use is this ? Some library functions are made more universal by passing the address of a function to them. E.g. bsearch and qsort. QSORT qsort(numbers,x,sizeof(int),comp); numbers is the address of the array to sort. x is the number of array elements to sort. sizeof(int) is the number of bytes each element takes up comp is a pointer to a function which will compare 2 elements of the appropriate type and return a value indicating whether the first element is less than, equal to or greater than the second element. Refer to the library documentation for specific information. The library version of qsort. ============================================================================== Quicksort. ---------- This is a more sophisticated implementation from Kelley and Pohl. quicksort(int a[], int n) { int k, pivot; if (find_pivot(a, n, &pivot) != 0) { k = partition(a, n, pivot); quicksort(a, k); quicksort(a + k, n - k); } } find_pivot(int a[], int n, int *pivot_ptr) { int i; for (i = 1; i < n; ++i) if (a[0] != a[i]) { *pivot_ptr = (a[0] > a[i]) ? a[0] : a[i]; return (1); } return (0); } partition(int a[], int n, int pivot) { int i = 0; j = n - 1; while (i <= j) { while (a[i] < pivot) ++i; while (a[j] >= pivot) --j; if (i < j) swap(&a[i++], &a[j--]); } return (i); } For arrays of randomly distributed elements, quicksort is proportional to nlogn. For arrays that are in order quicksort is very inefficient and approaches n^2. The reason is the method used to choose the pivot value. Find_pivot can be rewritten to find pivot values that will break the subarrays into nearly equal sizes. find_pivot(int a[], int n, int *pivot_ptr) { int b[3], i; if (n > 3) { b[0] = a[0]; b[1] = a[n/2]; b[2] = a[n-1]; quicksort(b, 3); if (b[0] != b[2]) { *pivot_ptr = (b[0] < b[1]) ? b[1] : b[2]; return (1); } } for (i = 1; i < n; ++i) if (a[0] != a[i]) { *pivot_ptr = (a[0] > a[i]) ? a[0] : a[i]; return (1); } return (0); } In this version of find_pivot change the line if (n > 3) to if (n >= 3) Now when quicksort is invoked, it does not run properly. Why ? Using a random number generator to fill an array of size 100, invoke find_pivot() and partition() to find the partition break size for the array. Do this repeatedly, keeping a running average of the break size. Does the average correspond to the middle of the array ?  Supplements to workbook 3.... Quicksort Quicksort is a sorting algorithm devised by C.A.R.Hoare in 1962. This algorithm is particularly suited to a recursive solution although non-recursive implementations are possible. A standard library version of quicksort is usually supplied with C compilers. Given an array, one element is chosen as the pivot element and the remainder are partitioned into two subsets. One subset consists of values less than the chosen element, the other with values greater. (N.B. the partitioning operation sorts the elements into two subsets but each subset is not yet in order). The quicksort function is then called recursively for each of the two subsets. This continues until the subsets have fewer than two elements and hence the array is sorted. A great deal of care must be exercised in selecting the pivot element and in performing the subsequent partitioning if the algorithm is to function to it's full potential. The version given in Kernighan and Ritchie (page 87) does not do this, it simply selects the middle element of each subset as the pivot. If the contents of the array are randomly distributed then this is acceptable. This version degenerates rapidly for partially sorted arrays. void qsort(int v[], int left, int right) { int i,last; void swap(int v[], int i, int j); if (left >= right) /* check for fewer than 2 elements */ return; swap(v,left,(left + right)/2); /* select pivot and place in v[0] */ last = left; for (i = left + 1; i <= right; i++) if (v[i] < v[left]) swap(v,++last,i); swap(v,left,last); /* restore pivot */ qsort(v,left,last-1); qsort(v,last+1,right); } void swap(int v[], int i, int j) { int temp; temp = v[i]; v[i] = v[j]; v[j] = temp; } Given the following array of 12 integers, trace the execution of qsort. {4,7,9,5,2,5,9,2,1,9,-5,-3} ============================================================================== Quicksort - pointer version. ---------------------------- Can you rewrite QSORT to use pointers ?. First consider swap using pointers. int swap(int *px, int *py) { int temp; temp = *px; *px = *py; *py = temp; } In the previous version the array was passed by reference but the array indexes were passed by value. In this version, both integers (the contents of the selected array positions) are passed by reference. A pointer is used to pass a value by reference. How would this be called from QSORT ?. Remember from pointers and arrays, given: int number[10]; /* an integer array */ int *p; /* a pointer to an integer */ p = number; /* is identical to p = &number[0]; */ p = number + 3; /* is identical to p = &number[3]; */ N.B. p and number+3 are both pointers (addresses); therefore we could write swap(v+left,v+last); which is identical to swap(&v[left],&v[last]); However we wish to eliminate array references from QSORT altogether. Let us decide that qsort will take two pointers as it's arguments. void qsort(int *left, int *right) { int *last, *temp; if (left >= right) return; swap(left,left + (right - left)/2); last = left; for (temp = left + 1; temp <= right; temp++) if (*temp < *left) swap(++last,temp); swap(left,last); qsort(left,last-1); qsort(last+1,right); } Trace the execution of this new version with the same array as before. ============================================================================== Pointers to Functions. Follow the existing notes....... ============================================================================== The library version of the function qsort(). -------------------------------------------- The prototype is in stdlib.h therefore include the line: #include The function prototype is given as: void qsort(void *base, size_t nelem, size_t width, int(*fcmp)(const void*, const void*)); The arguments: void *base - a pointer to the first element in the array where the sort will begin (usually the first [0] element). NOTE: void * is the modern or ANSI way of specifying a GENERIC pointer i.e. a pointer that has no specific base type. Generic pointers can be assigned to/from any typed pointer using a typecast. A generic pointer is used so that arrays of any type may be sorted using QSORT. size_t nelem - the number of elements to be sorted. NOTE: size_t is a defined type giving the largest value that may be specified for nelem in a given implementation. On the PC, size_t is an unsigned int i.e. 64K as this is the segment size and hence the size of the largest array. size_t width - the size of each element in bytes. NOTE: as the pointer is generic, pointer arithmetic will not work correctly. Therefore, the size of each element is required. Again the largest size of a single element is 64K. int(*fcmp)(const void*, const void*) - This is a pointer to a comparison function. The function compares two elements of the array. The array elements are referenced through two generic pointers. As QSORT may deal with arrays of any type, you are responsible for specifying/ writing the function which compares two elements. This function must return an integer result based on the following: *element1 < *element2 return an int less than 0 (-1). *element1 = *element2 return zero. *element1 > *element2 return an int greater than 0 (1). The qualifier const is dealt with below. ============================================================================== The library qsort() used with character arrays. ----------------------------------------------- Try the following example (Turbo C reference manual page 285): #include #include #include char list[5][4] = {"cat","car","cab","cap","can"}; main() { int x; qsort(&list,5,sizeof(list[0]),strcmp); for (x=0; x < 5; x++) printf("%s\n",list[x]); } Can you explain how this program works ?. Is it correct ?. The sizeof() function in the qsort() function call is actually part of the C language. It looks and behaves as a function but isn't. It returns the number of bytes a given object (either variable or type) occupies. We shall meet this again later. strcmp() is a library function in string.h to compare the values of two strings. It returns the values expected of a qsort() comparison function. NOTE: the name of the function - strcmp without parenthesis is the address of the function. Why haven't we specified the prototype for strcmp() ?. Is the &list part of the statement correct given that the name of an array is it's address ?. (Do &list and list both work). ------------------------------------------------------------------------- Given an array of integers called numarray of size MAXENTRIES e.g. int numarray[MAXENTRIES]; Write the qsort() call to sort the entire array and define the comparison function for two integers. ------------------------------------------------------------------------- main() { . qsort(numarray,MAXENTRIES,sizeof(int),icomp); . } int icomp(int *p1,int *p2) { return(*p1 - *p2); } Should we declare icomp as a prototype ?. ============================================================================== The qualifier const. -------------------- The qsort() comparison function takes two arguments which are generic pointers. These also have the qualifier const attached. The const qualifier can be used with array arguments to indicate that the function does not change that array. It is a common sight in the library prototypes. The const qualifier can also be applied to the declaration of any variable to specify that it's value will not be changed. For an actual array, the elements of that array will not be changed. Altering a const variable or argument is implementation dependent. In certain compilers, this effects the memory allocation of the variables. That is const variables are constants that must be allocated storage rather than #defined constants which are simply symbolic replacements and have no storage as such. Const variables can then be placed in code rather than data memory. This is of significance for compilers used to generate romable code. It can also mean that memory management hardware is used to check for write access to const variables. ============================================================================== Follow the notes for Kelley and Pohl version of quicksort. Is the Kelley and Pohl inplementation of qsort() with modified find_pivot function more or less efficient than the library version ?. Stage a test using an array of random numbers and an array of sorted or near sorted numbers. ============================================================================= Shellsort, Goto and Labels. --------------------------- The goto statement is rarely if ever used because C provides the break and continue statements making goto almost totally unnecessary. A goto statement requires a corresponding label to branch to. A label consists of an identifier followed by a semicolon. E.g. for (i=0; i v) { a[j] = a[j-h]; j = j - h; if (j <= h) break; } a[j] = v; } } while (h != 1); } NOTE: because this was adapted directly from Pascal the array is assumed to start at 1 NOT 0. ============================================================================== ARRAYS OF POINTERS. ------------------- It is possible to have arrays of pointers. They are declared: E.g. int *parray[10]; parray is an array of 10 addresses. Each pointer in the array may then point to variables of type int. E.g. main() { int j, num1=1, num2=2, num3=3, *ptr, *parray[4]; parray[1] = &num1; parray[2] = &num2; ptr = &num3; parray[3] = ptr; for (j=1; j<4; j++) printf("%d\n", *parray[j]); } Arrays of pointers to characters can be initialized to strings of different length. Only the memory required for each string is allocated. E.g. static char *cp[] = { "dog", "cat", "mouse", "rabbit" }; A further example to demonstrate arrays of pointers: E.g. char *month(); main() { int num; puts("Enter month number"); scanf("%d",&num); printf("The month name is %s",month(num)); } char *month(int n) { static char *name[] = { "illegal month", "January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December" }; return((n<1 || n>12) ? name[0] : name[n]); } ============================================================================== INITIALIZATION. --------------- By default: External and static variables are initialized to zero. Automatic and register variables are undefined. Scalar variables. ----------------- These are initialized where they are defined. External and static variables must be initialized with a constant expression. Automatic and register variables are not restricted to constant expressions and can be expressions involving previously defined values. E.g. int binsearch(int x, int v[], int n) { int low = 0; int high = n - 1; . . } Array variables. ---------------- An array initializer is a list of values enclosed in braces {} and seperated by commas. E.g. int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; Omitting the size of the array will cause the compiler to compute the size. If the size of the array is given and fewer initial values than this number are specified then the remainder will be set to zero for automatic, static and external variables. More values than the specified array size is an error. Character arrays are a special case. The following are identical but the former is the preferred style. char patt[] = "abcdefgh"; char patt[] = {'a','b','c','d','e','f','g','h'}; ============================================================================== Character Pointers (Supplementary). ----------------------------------- C always refers to character strings (string constants) through a pointer. Therefore, the following is permissible: char *pmessage; pmessage = "the quick brown fow jumps over the lazy dog"; note that it is the character pointer that is assigned. Given the following two initializations: char amessage[] = "now is the time"; char *pmessage = "now is the time"; Are they the same ?. NO.. Amessage is an array. Enough storage has been allocated to hold the specified characters and the terminating null character. Individual characters in the array may subsequently be altered. Amessage will always refer to the same storage and the same amount of storage. Pmessage is a pointer initialized to point to a string constant (held in code space). The pointer itself may be altered but not the string constant. ============================================================================== Arrays of Pointers (Supplemental). Consider the difference between arrays of pointers and multi-dimensional arrays. int a[10][20]; int *b[10]; References such as a[3][4] and b[3][4] are both legal !. However, a multi-dimensional array is actually an array (10) of arrays (each 20 elements). In the above example, the array a has 200 integers allocated. The array b has only 10 pointers to integers. For the above references to be equivalent, each pointer is assumed to point to a 20 integer array. It should be noted that when using arrays of pointers, each row may be of a different length. This fact is more commonly used when initializing character arrays. E.g. char *name[] = {"illegal name", "Jan", "Feb", "Mar", ..etc.. }; char aname[][15] = {"illegal name","Jan","Feb","Mar", ..etc.. }; In the second case a number of 15 character strings have been allocated, but only some of the characters are used. In the first case only the storage required is actually allocated. ============================================================================== COMMAND LINE ARGUMENTS. ----------------------- It is possible to pass arguments to a 'C' program from the operating system command line E.g. C:> mikespgm file1 file2 Command line arguments are passed to the function main(). By convention, these arguments are called argc and argv. argc is an integer count of the number of seperate argument strings on the command line including the program name. argv is an array of pointers to these strings. E.g. main(argc,argv) int argc; char *argv[]; { int i; for (i=1; i < argc; i++) printf("argument %d is %s\n",i,argv[i]); } The following is an alternative way of expressing this: E.g. main(argc,argv) int argc; char **argv; { while(--argc) printf("%s",*++argv); } N.B. As *argv[] is an array of pointers then **argv is a pointer to a pointer. This follows because the name of an array is really a pointer to the start of the array. ============================================================================== AN EXAMPLE OF COMMAND LINE ARGUMENTS AND POINTERS IN GENERAL. ------------------------------------------------------------- Consider the following program: #define FALSE 0 #define TRUE 1 main(argc,argv) int argc; char **argv; { int pal; char *ptr1,*ptr2; while (--argc > 0) { /* position ptr1 at start and ptr2 at end of line */ for (ptr2 = ptr1 = *++argv; *ptr2; ++ptr2) ; --ptr2; pal = TRUE; while (ptr1 < ptr2) if (*ptr1++ != *ptr2--) { pal = FALSE; break; } if (pal) printf("%s is a XXXX\n\n", *argv); else printf("%s is not a XXXX\n\n",*argv); } } The program clearly tests one or more command line arguments. What are the arguments being tested for ?. How (exactly) does the program work ?. ============================================================================== WorkBook 4 - Structures and their application. ---------------------------------------------- STRUCTURES. ----------- A structure is a collection of one or more variables, possibly of different types, grouped under a single name for convenience. E.g. struct employee_record { char name[21]; char address[21]; char town[21]; char postcode[9]; int day; int month; int year; } This defines a type employee_record. Any variable can now be declared as being of this type: E.g. struct employee_record employee; struct employee_record employees[200]; To reference an element of a structure: E.g. employee.name; employees[100].month; The dot operator '.' indicates the element being referenced. In classic 'C' only two operations could be done with a structure: - Take the address using the & operator. - Access one of the elements using the . operator. Modern compilers (to ANSI draft standards) have extensions to these operations: - A structure can be passed to a function as an argument or returned from a function. - Structures may be assigned as a whole. A full structure declaration is: struct [structure_tag] { type element1; type element2; .. type elementn; } [variable_name]; N.B. [structure_tag] and [variable_name] are optional and one or both may be omitted. ============================================================================== NESTED STRUCTURES. ------------------ E.g. struct date { int day; int month; int year; } struct employee_record { char name[21]; char address[21]; char town[21]; char postcode[9]; struct date start_date; } employee; To access the address field: employee.address To access the postcode field: employee.postcode To access the day field: employee.start_date.day The structure date is nested within employee_record. One benefit of this is that the variable start_date has been declared which has a more meaningful name than day month year. ============================================================================== POINTERS TO STRUCTURES. ----------------------- Declared as other pointers: E.g. struct employee_record employee; struct employee_record *employee_pointer; employee_pointer = &employee; A pointer to a structure of type employee_record has been defined and the address of the variable employee has been assigned to it. To access the postcode member. (*employee_pointer).postcode; N.B. the dot operator '.' has a higher precedence than the indirection operator '*' so the parenthesis is necessary ! A shorthand syntax for accessing a member of a structure using a pointer was introduced to the language. E.g. employee_pointer->postcode; N.B. struct date *startptr; /* pointer to struct date */ startptr = &employee_pointer->start_date; Start_date is of type struct date therefore it's address can be taken and assigned to a pointer to a structure date. ============================================================================== POINTERS TO ARRAYS OF STRUCTURES. --------------------------------- If we have a pointer to an element of an array of structures. E.g. struct employee_record emp[200]; struct employee_record *employee_pointer; Then we can point to a specific element employee_pointer = &emp[8]; If employee pointer is incremented: employee_pointer++; then employee pointer points to emp[9]; ============================================================================== Enumeration Constant. --------------------- Enumeration is a list of constant integer values. The enumeration constant assigns a sequence of constant integer values to symbolic names. E.g. enum boolean { FALSE, TRUE }; The first name in the enumeration has a value 0 (FALSE) and the second a value 1 (TRUE). Further values take successive integer values. Explicit values may also be specified. If not all values are specified, unspecified values continue the progression from the last specified value. E.g. enum escapes { BELL = '\a', BACKSPACE = '\b', TAB = '\t', NEWLINE = '\n', VTAB = '\v', RETURN = '\r' }; enum months { JAN = 1, FEB, MAR, APR, MAY, JUN, JUL, AUG, SEP, OCT, NOV, DEC }; Enumeration is an alternative to #define. E.g. #define FALSE 0 #define TRUE 1 Also values are generated automatically. NOTE: names generated in different enumerations must be distinct. values need not be distinct in the same enumeration. ============================================================================== Typedef. -------- Typedef creates new data type names. It does not create a new data type, but adds a new name for an existing data type. Typedef can be used to guard against non-portability through machine dependent data types. Typedef provides for better documentation and clarity. ----------------------------------------------------------------------- E.g. typedef int Length; Length is a synonym for int. Length can now be used as any other data type. Length len,maxlen; Variables of type Length Length *lenptr; Pointer to type Length ----------------------------------------------------------------------- Also: typedef char boolean; boolean is a synonym for char. boolean fill; a variable fill of type boolean typedef enum {TRUE,FALSE} boolean; boolean is a synonym for a enumeration boolean fill = FALSE; a variable fill of type boolean initialized to FALSE. ----------------------------------------------------------------------- typedef is commonly used with structures as structure declarations can get cumbersome. E.g. typedef struct date { int day; int month; int year; } Date; typedef struct employee_record { char name[21]; char address[21]; char town[21]; char postcode[9]; Date start_date; } Employee; Employee employee, *employee_pointer; Note that the new data type names have been capitalized allowing the original names to be retained (C is case sensitive !). Kernighan and Ritchie recommends this for all defined data type names. ============================================================================== SIZEOF Operator. ---------------- The sizeof operator looks like a function but is part of the 'C' language and not in a library. It is used to take the size of any object - type or variable. E.g. sizeof(int); sizeof(variable2); The size returned will be the number of bytes needed to allocate storage for that type. E.g. printf("%d",sizeof(float)); This prints the number of bytes required to store a float on the machine you are using. ============================================================================== FILES AND FILE HANDLING. ------------------------ In C, files are considered to be either text or binary. So far we have considered text files i.e. files containing a sequence of characters and broken into lines terminated by a newline character (\n). Binary files are considered to be a sequential stream of byte values with no structure other than an end of file mark. Text files may be manipulated as binary files. All files in C are considered to have a sequential organisation. This is common with most languages. To implement a random access file in a sequential organisation relies on the file having fixed length records. It is then possible to move directly to a record if we know it's position in the file (i.e. it's record number). Random access files are one of the main applications of structures. A record is defined as a structure and the file is considered to consist of a sequence of structures each of which is a fixed length. ----------------------------------------------------------------------- There are two categories of file functions in 'C'. - high level routines (buffered) - low level routines (unbuffered) High level routines use a file pointer while low level functions use a file descriptor or handle to access an open file. High level functions. fopen fclose getc putc fgetc fputc fread fwrite fgets fputs fscanf fprintf fseek etc.. Low level functions. open creat read write lseek close Most application programs use high level functions which in turn call low level functions. Low level functions correspond mostly to operating system calls. ============================================================================== THE FILE. --------- In 'C' all i/o is considered to be with a file. Therefore, files are not just disk files but devices such as screen and keyboard as well. By default, three files are always open. Name (file pointer) Device Handle ------------------------------------- stdin keyboard 0 standard input stdout display 1 standard output stderr display 2 standard error With MSDOS compilers, 2 other files may be open by default. stdaux comms 3 auxilliary device stdprn printer 4 standard printer As we have seen with the page formatter, stdin and stdout may be redirected from the command line when a program is run. E.g. c:> progname output_file The operating system must support redirection (MSDOS + UNIX) ============================================================================== Opening And Closing A File. --------------------------- Binary files are opened and closed in the same way as text files. To recap: To open a file with fopen() a file pointer must be declared. E.g. FILE *fp; The FILE structure is normally defined in stdio.h ( N.B. FILE must be in uppercase) To open a file: fp = fopen(fname, mode); Where mode is "r" - read trying to read a file which does not exist is an error "w" - write the file is created if it does not exist. The contents o an existing file are discarded. "a" - append the file is created if it does not exist. fopen() returns NULL if an error occurs. To open a file for updating i.e. read and write, then the following are used: "r+" "w+" "a+" Operating system differences may affect file format. E.g. UNIX uses a newline character (ASCII 10) to mark the end of line (EOL), DOS uses newline and cariage return (ASCII 10 and 13). Two types of file are supported: TEXT - ASCII characters written in lines with EOL markers BINARY - Structure is specified by the user and may contain data of any type. The default type is text file, therefore, to open a binary file use the following modes: "rb" "wb" "ab" "r+b" "w+b" "a+b" To close a file use fclose() with the pointer returned when the file was initially opened. E.g. fclose(fp); ============================================================================== RANDOM ACCESS FILES. -------------------- A random access file is a sequence of records of the same structure type. Three new file functions must be considered to manipulate random access files. fseek(), fread() and fwrite(). fseek() is used to set the current position in the file. E.g. ret = fseek(fp, offset, origin); ret is the return value (0 if successful or -1 if an error). offset is the number of bytes from the origin (variable of type long). origin is the offset mode (0 = beginning, 1 = current position and 2 = end of file). To create records of fixed length structures may be used. The records are read from and written to the file using the functions: no = fread(ptr, size, numb, fp); no = fwrite(ptr, size, numb, fp); where: ptr = is a pointer to the first block of data size = is the size of each block numb = is the number of blocks (records) to be read or written. fp = is the file pointer. no = is the number of blocks actually read or written This is best illustrated with an example. E.g. To create or add records to a random access datafile: #include #include #define FILENAME "data.dat" #define AMODE "ab" /* just "a" if UNIX */ typedef enum {FALSE,TRUE} boolean; struct record { char name[32]; char address[32]; char phone[17]; } main() { int c = 0, ch = 0; struct record client; struct record *clptr = &client; FILE *fp; boolean ok; if ((fp = fopen(FILENAME,AMODE)) == NULL) puts("Can't open file"); else while ((toupper(c)) != 'N') { ok = FALSE; while (!ok) { system("cls"); /* DOS cls command */ memset(clptr,0,sizeof(struct record)); puts("Enter name [max 20 characters]\n"); fgets(clptr->name,22,stdin); puts("Enter address [max 30 characters]\n"); fgets(clptr->address,32,stdin); puts("Enter phone no [max 15 characters]\n"); fgets(clptr->phone,17,stdin); system("cls"); puts("\t\t\trecord is - -\n\n\n"); printf("%s\n%s\n%s\n\n\n",clptr->name, clptr->address, clptr->phone); puts("o.k. to write record ? "); if ((ch = getch()) == 'y' || ch == 'Y') ok = TRUE; } fwrite((char *)clptr, sizeof(struct record), 1, fp); puts("record written\n\n\t\tanother entry ? "); c = getch(); } fclose(fp); } E.g. To read records from the datafile created above: #include #include #define FILENAME "data.dat" #define RMODE "rb" struct record { char name[32]; char address[32]; char phone[17]; } long getlong(); main() { int c = 0, ret; long no; struct record client, *clptr = &client; FILE *fp; if ((fp = fopen(FILENAME,RMODE)) != NULL) while ((toupper(c)) != 'N') { system("cls"); /* DOS cls command */ memset(clptr,0,sizeof(struct record)); puts("record no ?\n"); no = getlong(); fseek(fp,((no - 1)*(sizeof(struct record))),0); ret = fread(clptr,sizeof(struct record),1,fp); if (ret) { puts("name - "); puts(clptr->name); puts("address - "); puts(clptr->address); puts("phone no - "); puts(clptr->phone); } else puts("\nERROR\n"); puts("search for another record ? \n\n\t\t"); c = getch(); } else puts("can't find file"); fclose(fp); } long getlong() { long n; int ch; for (n=0; (ch=getchar()) >= '0' && ch <= '9'; n = n * 10 + ch - '0') ; return(n); } Run these two programs seperately. First the program to create records, then the program to read them. Combine both programs to arrive at a single program which will both read and write to a random access datafile. ============================================================================== BIT FIELDS. ----------- Data may be compressed using bit fields E.g. struct date { unsigned day : 5; unsigned month : 4; unsigned year : 7; }; This only allocates 2 bytes instead of the 6 bytes previously allocated. The maximum number that needs to held in day is 31 which has the bit pattern 11111 (5 bits); The maximum number that needs to be held in month is 12 which has a bit pattern 1100 (4 bits); The maximum number that needs to be held in year is 99 which has a bit pattern 1100011 (7 bits); Therefore, 5 + 4 + 7 = 16 bits or two bytes. Declaring a variable of the above type: E.g. struct date today; Then today.year; and today.day access the respective fields. NOTE: BIT ADDRESSES ARE UNSIGNED AND THEY DO NOT HAVE ADDRESSES !!. I.E. YOU CANNOT ASSIGN THE ADDRESS OF A BIT FIELD TO A POINTER. ============================================================================== UNIONS. ------- A union is similar to a structure but each element uses the same data (or storage) space. This means that the same area of memory can be accessed as different types. E.g. union uval { int ival; float fval; char *pval; } u_var; The amount of storage allocated will be the size of the largest element (fval on 16 bit machines). A union is a structured way of converting data of one type to another. E.g. struct bittype { unsigned bit1 : 1; unsigned bit2 : 1; unsigned bit3 : 1; unsigned bit4 : 1; unsigned bit5 : 1; unsigned bit6 : 1; unsigned bit7 : 1; unsigned bit8 : 1; unsigned bit9 : 1; unsigned bit10 : 1; unsigned bit11 : 1; unsigned bit12 : 1; unsigned bit13 : 1; unsigned bit14 : 1; unsigned bit15 : 1; unsigned bit16 : 1; }; union utype { unsigned num; struct bittype bits; }; main() { union utype uvar; int bitno = 0; puts("Enter a number"); scanf("%u",&uvar.num); /* to access bit number 9 for instance */ printf("%d",uvar.bits.bit9); } This is used to read a word from an i/o device etc. and then access individual bits as opposed to using a mask word and bitwise operators. ============================================================================== DIVISION OF MEMORY. ------------------- Memory is divided into code and data sections. The exact size of these sections depends on the memory model in use (MSDOS compilers). The data area is sub-divided into 3 areas: 1. static area - holds static variables external variables constants 2. stack area - holds automatic variables function arguments return addresses 3. heap area - holds dynamic variables/data The size of the heap may be fixed or may vary using library functions such as morecore() (Consult example on hash tables in Kernighan and Ritchie). In general, stacks grow downwards in memory and heaps grow upwards towards the stack. ============================================================================== THE HEAP. --------- The heap space can only be allocated using library functions such as malloc() and calloc(). This space is accessed through pointers. Malloc() requires an argument which is the number of bytes required and it returns a pointer to the first byte. The return type is a character pointer. E.g. char *ptr, fred[30]; /* define a character pointer and a character array */ ptr = malloc(10); /* allocate 10 bytes on the heap and return the address to ptr*/ ptr = malloc(sizeof(fred)); /* OR use sizeof to determine the number of characters required for a given variable or type */ Free() deallocates the memory allocated by malloc(). The pointer returned by malloc() is passed as an argument to free(). E.g. free(ptr); N.B. do not lose the pointer returned by malloc as the space cannot then be accessed or deallocated using free(). ============================================================================== SELF-REFERENTIAL STRUCTURES (LINKED LISTS) ------------------------------------------ A second common application of C structures is the creation of complex data structures on the heap using C structures that are self referencing i.e. structures that contain a member which is a pointer to a structure of the same type. The most common (and easiest!!) example is the linked list. The linked list can be used to model a number of data structures such as the stack, the queue and the deque (double ended queue). These data structures have applications in searching, sorting, list processing and indexed file structures to name a few. More recently, linked lists are commonly used to connect all the individual elements that make up the windows in a graphical user environment. A self-referential structure is a structure variable (usually on the heap) which contains a pointer to another structure variable (usually identical). E.g. struct node { int number; struct node *link; }; main() { struct node *head = NULL, *ptr; int i; for (i=0; i<10; i++) { ptr = head; head = (struct *node)malloc(sizeof(struct node)); head->link = ptr; } ptr = head; while (ptr != NULL) { printf("%d",ptr->number); ptr = ptr->link; } } ============================================================================== sOz brainstrain............hmmmm :-) pCm ------------------------------------------------------------------------------