C++ Program

From the computer’s point of view, a C program is nothing more than a collection of functions and declarations. Functions can be thought of as sealed capsules of program code which float on a background of white space,and are connected together by means of function calls. White space is the name given to the white of an imaginary piece of paper upon which a program is written, in other words the spaces and new line characters which are invisible to the eye. The global white space is only the gaps between functions, not the gaps inside functions. Thinking of functions as sealed capsules is a useful way of understanding the difference between local and global objects and the whole idea of scope in a program.

There are a handful more preprocessor commands which can largely be  ignored by the beginner. They are commonly used in "include" files to make  sure that things are not defined twice. NOTE : ‘true’ has any non zero value in C. ‘false’ is zero.  #undef         This undefines a macro, leaving the name free. #if                 This is followed by some expression on the same line. It allows                       conditional compilation. It is an advanced feature which can be                       used to say: only compile the code between ‘#if’ and ‘#endif’                        if the value following ‘#if’ is true, else leave out that code altogether. This is      D ifferent from not executing code—the code will  n...

A more advanced use of macros is also permitted by the preprocessor. This involves macros which accept parameters and hand back values. This works by defining a macro with some dummy parameter, say x. For example: a macro which is usually defined in one of the standard libraries is abs() which means the absolute or unsigned value of a number. It is defined below: #define ABS(x) ((x) < 0) ? -(x) : (x) The result of this is to give the positive (or unsigned) part of any number or variable. This would be no problem for a function which could accept parameters, and it is, in fact, no problem for macros. Macros can also be made to take parameters. Consider the ABS() example. If a programmer were to write ABS(4) then the preprocessor would substitute 4 for x. If a program read ABS(i) then the preprocessor would substitute i for x and so on. (There is no reason why macros can’t take more than one parameter too. The programmer just includes two dummy parameters with differe...

The conversion characters for scanf are not identical to those for printf and it is much more important to be precise and totally correct with these than it is with printf. d                        denary integer (int or long int) ld                       long decimal integer x                        hexadecimal integer o                       octal integer h                       short integer f                        float type lf                       long float or double e                       float type le     ...

C is unusual in that it has a pre-processor. This comes from its Unix  origins. As its name might suggest, the preprocessor is a phase which occurs  prior to compilation of a program. The preprocessor has two main uses: it  allows external files, such as header files, to be included and it allows macros  to be defined. This useful feature traditionally allowed constant values to be  defined in Kernighan and Ritchie C, which had no constants in the language. Pre-processor commands are distinguished by the hash (number) symbol  ‘#’. One example of this has already been encountered for the standard  header file ‘stdio.h’. #include <stdio.h>  is a command which tells the preprocessor to treat the file ‘stdio.h’ as if it were the actually part of the program text, in other words to include it as  part of the program to be compiled. Macros are words which can be defined to stand in place of something  complicated: they are a way ...

A variable is a seqeuence of program code with a name (also called its  identifier ). A name or identifier in C can be anything from a single letter to  a word. The name of a variable must begin with an alphabetic letter or the  underscore ‘_’ character but the other characters in the name can be chosen  from the following groups: a .. z (any letter from a to z) A .. Z (any letter from A to Z) 0 .. 9 (any digit from 0 to 9) _ (the underscore character) Some examples of valid variable names are: a total Out_of_Memory VAR integer etc...  In C variables do not only have names: they also have types. The type  of a variable conveys to the the compiler what sort of data will be stored in it. In BASIC and in some older, largely obsolete languages, like PL/1, a  special naming convention is used to determine the sort of data which can  be held in particular variables. e.g. the dollar symbol ‘$’ is commonly used  in BASIC to mean that a va...

Some programmers complain about the use of global variables in a program.  One complaint is that it is difficult to see what information is being passed  to a function unless all that information is passed as parameters. Sometimes  global variables are very useful however, and this problem need not be crip pling. A way to make this clear is to write global variables in capital letters  only, while writing the rest of the variables in mainly small letters.. int GLOBALINTEGER; .... { int local integer; } This allows global variables to be spotted easily. Another reason for restrict ing the use of global variables is that it is easier to debug a program if only  local variables are used. The reason is that once a function capsule is tested  and sealed it can be guaranteed to work in all cases, provided it is not af fected by any other functions from outside. Global variables punch holes in the sealed function capsules because they allow bugs from oth...

Variables can be assigned to numbers: var = 10; and assigned to each other: var1 = var2; In either case the objects on either side of the = symbol must be of the same type. It is possible (though not usually sensible) to assign a floating point number to a character for instance. So i nt a, b = 1; a = b; is a valid statement, and: float x = 1.4; char ch; ch = x; is a valid statement, since the truncated value 1 can be assigned to ch. This is a questionable practice though. It is unclear why anyone would choose to do this. Numerical values and characters will interconvert because characters are stored by their ASCII codes (which are integers!) Thus the following will work: int i; char ch = ’A’; i = ch; printf ("The ASCII code of %c is %d",ch,i); The result of this would be: The ASCII code of A is 65

Suppose that a program is in the middle of some awkward process in a function which is not main(), perhaps two or three loops working together, for example, and suddenly the function finds its answer. This is where the beauty of the return statement becomes clear. The program can simply call return(value) anywhere in the function and control will jump out of any number of loops or whatever and pass the value back to the calling statement without having to finish the function up to the closing brace }. myfunction (a,b) /* breaking out of functions early */ int a,b; { while (a < b) { if (a > b) { return (b); } a = a + 1; } }

C is actually a free format language. This means that there are no rules about how it must be typed, when to start new lines, where to place brackets or whatever. This has both advantages and dangers. The advantage is that the user is free to choose a style which best suits him or her and there is freedom in the way in which a program can be structured. The disadvantage is that, unless a strict style is adopted, very sloppy programs can be the result. The reasons for choosing a well structured style are that: • Long programs are manageable only if programs are properly organized. • Programs are only understandable if care is taken in choosing the names of variables and functions. • It is much easier to find parts of a program if a strict ordering convention is maintained. Such a scheme becomes increasingly difficult to achieve with the size and complexity of the problem.

The compiler uses a special convention for the file names, so that we do  not confuse their contents. The name of a source program (the code  which you write) is ‘filename.c’. The compiler generates a file of ob ject code from this called ‘filename.o’, as yet unlinked. The final pro gram, when linked to libraries is called ‘filename’ on Unix-like operating  systems, and ‘filename.EXE’ on Windows derived systems. The libraries  themselves are also files of object code, typically called ‘liblibraryname.a’  or ‘liblibraryname.so’. Header files are always called ‘libname.h’.  The endings ‘dot something’ (called file extensions) identify the contents  of files for the compiler. The dotted endings mean that the compiler can  generate an executable file with the same name as the original source – just  a different ending. The quad file and the object file are only working files  and should be deleted by the compiler at the end of compilation....

fopen() FILE *fopen(const char *path, const char *mode); The fopen() function is used to open a file and associates an I/O stream with it. This function takes two arguments. The first argument is a pointer to a string containing name of the file to be opened while the second argument is the mode in which the file is to be opened. The mode can be : ‘r’    :  Open text file for reading. The stream is positioned at the beginning of the file. ‘r+’ :  Open for reading and writing. The stream is positioned at the beginning of the file. ‘w’   :  Truncate file to zero length or create text file for writing. The stream is positioned at the beginning of the file. ‘w+’ : Open for reading and writing. The file is created if it does not exist, otherwise it is truncated. The stream is positioned at the beginning of the file. ‘a’    : Open for appending (writing at end of file). The file is created if it does not exist. The stream is positioned at th...

Input and output to and from files is identical to that at the command line, except the fprintf and fscanf functions are used and they require another argument. This additional argument is called a file pointer. In order to write two floating point numbers to a file, you first need to declar the file pointer with the FILE type, and you need to open it, as in float x=1, y=2; FILE *file; file = fopen(‘‘file.txt’’,’’w’’); fprintf(file,’’%f %f\n’’,x,y); fclose(file); The function fprintf is identical to the printf function, except now we see it has another argument file, which is a pointer to the file. Before you use the file variable, you need to open the file with file = fopen(‘‘file.txt’’,’’w’’); This opens up the file ‘‘file.txt’’ and the ‘‘w’’ which is the mode and indicates how the file will be used. The following three modes are allowed: Mode String Open for reading “r” Open for writing “w” Open and append “a” When you are done with the file, you close it ...

C allows you to define your own types, and this can make your codes much more legible. For example, you can define a type called price that you can use to define variables that you use to represent the price of certain objects. To do so, you would use typedef float price; int main(void) { price x, y; } The typedef is used in the following way: typedef existing_type new_type; The price type example is identical to using float x, y; but it is useful to use typedef when you would like the ability to change the types of certain variables throughout your codes by only changing one line. That is, if you wanted to change all of your prices to type double, then you would only need to change the typedef line to typedef double price;

As we saw in the hello.c example in the last lecture, Every C program must contain a main function , since the main function is the first function called when you run your program at the command line. In its simplest form, a C program is given by int main(void) { printf(‘‘Hello world!\n’’); } The int stands for the “return type”, which says that the main function returns an integer if you tell it to do so. We will get into more detail with functions and return types, but you can return a number to the command line with the return function in C, as in int main(void) { printf(‘‘Helloworld!\n’’); return 2; }

Tree Structures Introduction In many situation, an efficient way to represent data structures is to use trees. A tree can be defined recursively as an object containing some data and references to a certain number of subtrees. This definition leads to a hierarchical structure, in which trees with no sub-trees are called leaves. The other ones are called internal nodes. More mathematically, a tree is a graph with no cycles. Those data structures are very useful to store and organize informations associ- ated to comparable values. Here we give an example of an associative memory int -> string.

The left operand of >> will always be an istream and the right operand will be whatever we want : #include <iostream> class Crazy { public: double a, b; }; istream & operator >> (istream &i, Crazy &c) { return i >> (c.a) >> (c.b); } int main(int argc, char **argv) { Crazy x; cin >> x; } The ostream can not be copied, and will always exist as a lvalue (by definition printing modifies its state), so you have to alway pass it by reference and return a reference : #include <iostream> void dumb1(ostream &s) {} void dumb2(ostream s) {} int main(int argc, char **argv) { dumb1(cout); dumb2(cout); } /usr/lib/gcc-lib/i586-pc-linux-gnu/2.95.1/../../../../include/g++-3/streambuf.h:12 ‘ios::ios(const ios &)’ is private Here the line 8 tries to pass the stream by value, thus to call a copy constructor, which is private.

The usual dumb algorithms for sorting things require a number of operations proportional to the square of the number of elements to sort (O(n2)). In practice, the used algorithms require a number of operations proportional to n×log n. The first one is the fusion sort. The main point is that given two sorted list of numbers, generating the sorted merged list needs a number of operations proportional to the size of this result list. Two index indicate the next elements to take from each list, and one indicates where to store the smallest of the two (see figure 7.3). This process can be iterated, starting with packets of size 1 (which are already sorted ...) and merging them each time two by two (see figure 7.4). After k iterations of that procedure, the packets are of size 2k, so the number of iterations for this process is log2 n where n is the total number of objects to sort. Each step of this main process cost the sum of the sizes of the resulting packets, which is n. Finally t...

Big-O Notation Why ? How ? To estimate the efficiency of an algorithm, the programmer has to be able to  estimate the number of operations if requires to be executed.  Usually the number of operations is estimated as a function of a parameter (like  the number of data to work on, or the expected precision of a computation, etc.) For example : for(i = 0; i < n; i++) { ... } has a cost proportional to n. for(i = 1; i < n; i = i*2) { ... } has a cost proportional to log2 n for(i = 0; i < n; i++) for(j = 0; j<n*n; j++) { ... } has a cost proportional to n3.

GDB The most standard debugging tool on UNIX is the GNU Debugger gdb. Its main functionnality is to display the piece of code which procuced a crash. To do it, compile your code with the -g option, so that debugging information will be added to the executable. This information is mainly a correspondance between the machine langage instructions and locations in the source. Then, execute the program from gdb. For instance int main(int argc, char **argv) { int size = 100; int a[size]; for(int i = 0; i < 100 * size; i++) a[i] = i; } > g++ -o bang -g bang.cc > gdb ./bang