Introduction to Programming
************************************************************************************************
Hello world + C Program Dissection
Getting Started
The only way to learn a new programming language is by writing programs in it. The first program to write is the same for all languages:
Print the words
hello, world
This is a big hurdle; to leap over it you have to be able to create the program text somewhere, compile it successfully, load it, run it, and find out where your output went. With these mechanical details mastered, everything else is comparatively easy.
In C, the program to print ``hello, world'' is
#include
main()
{
printf("hello, world\n");
}
Just how to run this program depends on the system you are using. As a specific example, on the UNIX operating system you must create the program in a file whose name ends in ``.c'', such as hello.c, then compile it with the command
cc hello.c
If you haven't botched anything, such as omitting a character or misspelling something, the compilation will proceed silently, and make an executable file called a.out. If you run a.out by typing the command
a.out
it will print hello, world
A C program, whatever its size, consists of functions and variables. A function contains statements that specify the computing operations to be done, and variables store values used during the computation. C functions are like the subroutines and functions in Fortran or the procedures and functions of Pascal. Our example is a function named main. Normally you are at liberty to give functions whatever names you like, but ``main'' is special - your program begins executing at the beginning of main. This means that every program must have a main somewhere. main will usually call other functions to help perform its job, some that you wrote, and others from libraries that are provided for you. The first line of the program,
#include
tells the compiler to include information about the standard input/output library; the line appears at the beginning of many C source files. The standard library is described in detail in the coming modules.
One method of communicating data between functions is for the calling function to provide a list of values, called arguments, to the function it calls. The parentheses after the function name surround the argument list. In this example, main is defined to be a function that expects no arguments, which is indicated by the empty list ( ).
#include
main() define a function called main that received no argument values
{ statements of main are enclosed in braces
printf("hello, world\n"); main calls library function printf to print this sequence of characters
} \n represents the newline character
The first C program
The statements of a function are enclosed in braces { }. The function main contains only one statement,
printf("hello, world\n");
A function is called by naming it, followed by a parenthesized list of arguments, so this calls the function printf with the argument "hello, world\n". printf is a library function that prints output, in this case the string of characters between the quotes.
A sequence of characters in double quotes, like "hello, world\n", is called a character string or string constant. For the moment our only use of character strings will be as arguments for printf and other functions.
The sequence \n in the string is C notation for the newline character, which when printed advances the output to the left margin on the next line. If you leave out the \n (a worthwhile experiment), you will find that there is no line advance after the output is printed. You must use \n to include a newline character in the printf argument;
if you try something like
printf("hello, world
");
C compiler will produce an error message.
printf never supplies a newline character automatically, so several calls may be used to build up an output line in stages. Our first program could just as well have been written
#include
main()
{
printf("hello, ");
printf("world");
printf("\n");
}
to produce identical output.
Notice that \n represents only a single character. An escape sequence like \n provides a general and extensible mechanism for representing hard-to-type or invisible characters. Among the others that C provides are \t for tab, \b for backspace, \" for the double quote and \\ for the backslash itself. There is a complete list given in the coming chapters.
************************************************************************************************
************************************************************************************************
Tracing of a C Program
************************************************************************************************
How does it work inside the computer?
A Tour of Computer Systems
A computer system consists of hardware and systems software that work together to run application programs. Specific implementations of systems change over time, but the underlying concepts do not. All computer systems have similar hardware and software components that perform similar functions.
In the Module1, we introduced students to C using the hello program shown below:
#include
int main()
{
printf("hello, world\n");
}
Although hello is a very simple program, every major part of the system must work in concert in order for it to run to completion. In this Module you will understand what happens and why, when you run hello on your system.
We begin our study of systems by tracing the lifetime of the hello program, from the time it is created by a programmer, until it runs on a system, prints its simple message, and terminates. As we follow the lifetime of the program, we will briefly introduce the key concepts, terminology, and components that come into play. Later chapters will expand on these ideas.
The hello program
#include
int main()
{
printf("hello, world\n");
}
Information Is Bits + Context
Our hello program begins life as a source program (or source file) that the programmer creates with an editor and saves in a text file called hello.c. The source program is a sequence of bits, each with a value of 0 or 1, organized in 8-bit chunks called bytes. Each byte represents some text character in the program.
Most modern systems represent text characters using the ASCII standard that represents each character with a unique byte-sized integer value. For example, Figure 1.1 shows the ASCII representation of the hello.c program.
The hello.c program is stored in a file as a sequence of bytes. Each byte has an integer value that corresponds to some character. For example, the first byte has the integer value 35, which corresponds to the character '#'. The second byte has the integer value 105, which corresponds to the character 'i', and so on. Notice that each text line is terminated by the invisible newline character '\n', which is represented by the integer value 10. Files such as hello.c that consist exclusively of ASCII characters are known as text files. All other files are known as binary files.
The representation of hello.c illustrates a fundamental idea: All information in a system - including disk files, programs stored in memory, user data stored in memory, and data transferred across a network - is represented as a bunch of bits. The only thing that distinguishes different data objects is the context.
PROGRAMS ARE TRANSLATED BY OTHER PROGRAMS INTO DIFFERENT FORMS
in which we view them. For example, in different contexts, the same sequence of bytes might represent an integer, floating-point number, character string, or machine instruction.
As programmers, we need to understand machine representations of numbers because they are not the same as integers and real numbers. They are finite approximations that can behave in unexpected ways.
\**********************************************************************************************\
Aside: Origins of the C programming language.
* C was developed from 1969 to 1973 by Dennis Ritchie of Bell Laboratories. The American National Standards Institute (ANSI) ratified the ANSI C standard in 1989, and this standardization later became the responsibility of the International Standards Organization (ISO). The standards define the C language and a set of library functions known as the C standard library. Kernighan and Ritchie describe ANSI C in their classic book, which is known affectionately as "K&R" [58]. In Ritchie's words [88], C is "quirky, flawed, and an enormous success." So why the success?
* C was closely tied with the Unix operating system. C was developed from the beginning as the system programming language for Unix. Most of the Unix kernel, and all of its supporting tools and libraries, were written in C. As Unix became popular in universities in the late 1970s and early 1980s, many people were exposed to C and found that they liked it. Since Unix was written almost entirely in C, it could be easily ported to new machines, which created an even wider audience for both C and Unix.
* C is a small, simple language. The design was controlled by a single person, rather than a committee, and the result was a clean, consistent design with little baggage. The K&R book describes the complete language and standard library, with numerous examples and exercises, in only 261 pages. The simplicity of C made it relatively easy to learn and to port to different computers.
* C was designed for a practical purpose. C was designed to implement the Unix operating system. Later, other people found that they could write the programs they wanted, without the language getting in the way.C is the language of choice for system-level programming, and there is a huge installed base of application-level programs as well. However, it is not perfect for all programmers and all situations. C pointers are a common source of confusion and programming errors. C also lacks explicit support for useful abstractions such as classes, objects, and exceptions. Newer languages such as C++ and Java address these issues for application-level programs.
End Aside.
\****************************************************************************************\
Programs Are Translated by Other Programs into Different Forms
The hello program begins life as a high-level C program because it can be read and understood by human beings in that form. However, in order to run hello.c on the system, the individual C statements must be translated by other programs into a sequence of low-level machine-language instructions. These instructions are then packaged in a form called an executable object program and stored as a binary disk file. Object programs are also referred to as executable object files. On a Unix system, the translation from source file to object file is performed by a compiler driver:
unix> gcc -o hello hello.c
Here, the GCC compiler driver reads the source file hello.c and translates it into an executable object file hello. The translation is performed in the sequence of four phases shown in Figure 1.2. The programs that perform the four phases (preprocessor, compiler, assembler, and linker) are known collectively as the compilation system.
* Preprocessing phase. The preprocessor (cpp)modifies the original C program according to directives that begin with the # character. For example, the #include command in line 1 of hello.c tells the preprocessor to read the contents of the system header file stdio.h and insert it directly into the program text. The result is another C program, typically with the .i suffix.
* Compilation phase: The compiler (cc1) translates the text file hello.i into the text file hello.s, which contains an assembly-language program. Each statement in an assembly-language program exactly describes one low-level machine-language instruction in a standard text form. Assembly language is useful because it provides a common output language for different compilers for different high-level languages. For example, C compilers and Fortran compilers both generate output files in the same assembly language.
* Assembly phase: Next, the assembler (as) translates hello.s into machine-language instructions, packages them in a form known as a relocatable object program, and stores the result in the object file hello.o. The hello.o file is a binary file whose bytes encode machine language instructions rather than characters. If we were to view hello.owith a text editor, it would appear to be gibberish.
* Linking phase: Notice that our hello program calls the printf function, which is part of the standard C library provided by every C compiler. The printf function resides in a separate precompiled object file called printf.o, which must somehow be merged with our hello.o program. The linker (ld) handles this merging. The result is the hello file, which is an executable object file (or simply executable) that is ready to be loaded into memory and executed by the system.
Understand How Compilation Systems Work
For simple programs such as hello.c, we can rely on the compilation system to produce correct and efficient machine code. However, there are some important reasons why programmers need to understand how compilation systems work:
* Optimizing program performance. Modern compilers are sophisticated tools that usually produce good code. As programmers, we do not need to know the inner workings of the compiler in order to write efficient code. However, in order to make good coding decisions in our C programs, we do need a basic understanding of machine-level code and how the compiler translates different C statements into machine code. For example, is a switch statement always more efficient than a sequence of if-else statements? How much overhead is incurred by a function call? Is a while loop more efficient than a for loop? Are pointer references more efficient than array indexes? Why does our loop run so much faster if we sum into a local variable instead of an argument that is passed by reference? How can a function run faster when we simply rearrange the parentheses in an arithmetic expression?
* Understanding link-time errors. In our experience, some of the most perplexing programming errors are related to the operation of the linker, especially when you are trying to build large software systems. For example, what does it mean when the linker reports that it cannot resolve a reference? What is the difference between a static variable and a global variable? What happens if you define two global variables in different C files with the same name? What is the difference between a static library and a dynamic library? Why does it matter what order we list libraries on the command line? And scariest of all, why do some linker-related errors not appear until run time?
* Avoiding security holes. For many years, buffer overflow vulnerabilities have accounted for the majority of security holes in network and Internet servers. These vulnerabilities exist because too few programmers understand the need to carefully restrict the quantity and forms of data they accept from untrusted sources. A first step in learning secure programming is to understand the consequences of the way data and control information are stored on the program stack.
Processors Read and Interpret Instructions Stored in Memory
At this point, our hello.c source program has been translated by the compilation system into an executable object file called hello that is stored on disk. To run the executable file on a Unix system, we type
unix> ./hello
its name to an application program known as a shell: hello, world
unix>
The shell is a command-line interpreter that prints a prompt, waits for you to type a command line, and then performs the command. If the first word of the command line does not correspond to a built-in shell command, then the shell assumes that it is the name of an executable file that it should load and run. So in this case, the shell loads and runs the hello program and then waits for it to terminate. The hello program prints its message to the screen and then terminates. The shell then prints a prompt and waits for the next input command line.
Hardware Organization of a System
To understand what happens to our hello program when we run it, we need to understand the hardware organization of a typical system, which is shown in Figure 1.3
CPU: Central Processing Unit, ALU: Arithmetic/ Logic Unit, PC: Program counter, USB: Universal Serial Bus.
PROCESSORS READ AND INTERPRET INSTRUCTIONS STORED IN MEMORY
Buses
Running throughout the system is a collection of electrical conduits called buses that carry bytes of information back and forth between the components. Buses are typically designed to transfer fixed-sized chunks of bytes known as words. The number of bytes in a word (the word size) is a fundamental system parameter that varies across systems. Most machines today have word sizes of either 4 bytes (32 bits) or 8 bytes (64 bits).
I/O Devices
Input/output (I/O) devices are the system's connection to the external world. Our example system has four I/O devices: a keyboard and mouse for user input, a display for user output, and a disk drive (or simply disk) for long-term storage of data and programs. Initially, the executable hello program resides on the disk. Each I/O device is connected to the I/O bus by either a controller or an adapter. The distinction between the two is mainly one of packaging. Controllers are chip sets in the device itself or on the system's main printed circuit board (often called the motherboard). An adapter is a card that plugs into a slot on the motherboard. Regardless, the purpose of each is to transfer information back and forth between the I/O bus and an I/O device.
Main Memory
The main memory is a temporary storage device that holds both a program and the data it manipulates while the processor is executing the program. Physically, main memory consists of a collection of dynamic random access memory (DRAM) chips. Logically, memory is organized as a linear array of bytes, each with its own unique address (array index) starting at zero. In general, each of the machine instructions that constitute a program can consist of a variable number of bytes. The sizes of data items that correspond to C program variables vary according to type. For example, on an IA32 machine running Linux, data of type short requires two bytes, types int, float, and long four bytes, and type double eight bytes.
Processor
The central processing unit (CPU), or simply processor, is the engine that interprets (or executes) instructions stored in main memory. At its core is a word-sized storage device (or register) called the program counter (PC). At any point in time, the PC points at (contains the address of) some machine-language instruction in main memory.
From the time that power is applied to the system, until the time that the power is shut off, a processor repeatedly executes the instruction pointed at by the program counter and updates the program counter to point to the next instruction. A processor appears to operate according to a very simple instruction execution model, defined by its instruction set architecture. In this model, instructions execute in strict sequence, and executing a single instruction involves performing a series of steps. The processor reads the instruction from memory pointed at by the program counter (PC), interprets the bits in the instruction, performs some simple operation dictated by the instruction, and then updates the PC to point to the next instruction, which may or may not be contiguous in memory to the instruction that was just executed.
There are only a few of these simple operations, and they revolve around main memory, the register file, and the arithmetic/logic unit (ALU). The register file is a small storage device that consists of a collection of word-sized registers, each with its own unique name. The ALU computes new data and address values. Here are some examples of the simple operations that the CPU might carry out at the request of an instruction:
* Load: Copy a byte or a word from main memory into a register, overwriting the previous contents of the register.
* Store: Copy a byte or a word from a register to a location in main memory, overwriting the previous contents of that location.
* Operate: Copy the contents of two registers to the ALU, perform an arithmetic operation on the two words, and store the result in a register, overwriting the previous contents of that register.
* Jump: Extract a word from the instruction itself and copy that word into the program counter (PC), overwriting the previous value of the PC.
We say that a processor appears to be a simple implementation of its instruction set architecture, but in fact modern processors use far more complex mechanisms to speed up program execution. Thus, we can distinguish the processor's instruction set architecture, describing the effect of each machine-code instruction, from its microarchitecture, describing how the processor is actually implemented.
Running the hello Program
Given this simple view of a system's hardware organization and operation, we can begin to understand what happens when we run our example program. Initially, the shell program is executing its instructions, waiting for us to type a command. As we type the characters "./hello" at the keyboard, the shell program reads each one into a register, and then stores it in memory, as shown in Figure 1.4.
When we hit the enter key on the keyboard, the shell knows that we have finished typing the command. The shell then loads the executable hello file by executing a sequence of instructions that copies the code and data in the hello object file from disk to main memory. The data include the string of characters "hello, world\n" that will eventually be printed out.
Using a technique known as direct memory access the data travels directly from disk to main memory, without passing through the processor. This step is shown in Figure 1.5. Once the code and data in the hello object file are loaded into memory, the processor begins executing the machine-language instructions in the hello program's main routine. These instructions copy the bytes in the "hello, world\n" string from memory to the register file, and from there to the display device, where they are displayed on the screen. This step is shown in Figure 1.6.
Caches Matter
An important lesson from this simple example is that a system spends a lot of time moving information from one place to another. The machine instructions in the hello program are originally stored on disk. When the program is loaded, they are copied to main memory. As the processor runs the program, instructions are copied from main memory into the processor. Similarly, the data string "hello,world\n", originally on disk, is copied to main memory, and then copied from main memory to the display device. From a programmer's perspective, much of this copying is overhead that slows down the "real work" of the program.
Thus, a major goal for system designers is to make these copy operations run as fast as possible. Because of physical laws, larger storage devices are slower than smaller storage devices. And faster devices are more expensive to build than their slower counterparts. For example, the disk drive on a typical system might be 1000 times larger than the main memory, but it might take the processor 10,000,000 times longer
Storage Devices Form a Hierarchy
This notion of inserting a smaller, faster storage device (e.g., cache memory) between the processor and a larger slower device (e.g., main memory) turns out to be a general idea. In fact, the storage devices in every computer system are organized as a memory hierarchy similar to Figure 1.7. As we move from the top of the hierarchy to the bottom, the devices become slower, larger, and less costly per byte. The register file occupies the top level in the hierarchy, which is known as level 0 or L0. We show three levels of caching L1 to L3, occupying memory hierarchy levels 1 to 3. Main memory occupies level 4, and so on.
The main idea of a memory hierarchy is that storage at one level serves as a cache for storage at the next lower level. Thus, the register file is a cache for the L1 cache. Caches L1 and L2 are caches for L2 and
L3, respectively. The L3 cache is a cache for the main memory, which is a cache for the disk. On some networked systems with distributed file systems, the local disk serves as a cache for data stored on the disks of other systems.
The Operating System Manages the Hardware
Back to our hello example. When the shell loaded and ran the hello program, and when the hello program printed its message, neither program accessed the keyboard, display, disk, or main memory directly. Rather, they relied on the services provided by the operating system. We can think of the operating system as a layer of software interposed between the application program and the hardware, as shown in Figure 1.8.
THE OPERATING SYSTEM MANAGES THE HARDWARE
The operating system has two primary purposes: (1) to protect the hardware from misuse by runaway application, and (2) to provide applications with simple and uniform mechanisms for manipulating complicated and often wildly different low-level hardware devices. The operating system achieves both goals via the fundamental abstractions shown in Figure 1.9: processes, virtual memory, and files. As this figure suggests, files are abstractions for I/O devices, virtual memory is an abstraction for both the main memory and disk I/O devices, and processes are abstractions for the processor, main memory, and I/O devices.
Processes
When a program such as hello runs on a modern system, the operating system provides the illusion that the program is the only one running on the system. The program appears to have exclusive use of the processor, main memory, and I/O devices. The processor appears to execute the instructions in the program, one after the other, without interruption. And the code and data of the program appear to be the only objects in the system's memory. These illusions are provided by the notion of a process, one of the most important and successful ideas in computer science.
A process is the operating system's abstraction for a running program. Multiple processes can run concurrently on the same system, and each process appears to have exclusive use of the hardware. By concurrently, we mean that the instructions of one process are interleaved with the instructions of another process. In most systems, there are more processes to run than there are CPUs to run them. Traditional systems could only execute one program at a time, while newer multi-core processors can execute several programs simultaneously. In either case, a single CPU can appear to execute multiple processes concurrently by having the processor switch among them. The operating system performs this interleaving with a mechanism known as context switching.
The operating system keeps track of all the state information that the process needs in order to run. This state, which is known as the context, includes information such as the current values of the PC, the register file, and the contents of main memory. At any point in time, a uniprocessor system can only execute the code for a single process.
When the operating system decides to transfer control from the current process to some new process, it performs a context switch by saving the context of the current process, restoring the context of the new process, and then passing control to the new process. The new process picks up exactly where it left off. Figure 1.10 shows the basic idea for our example hello scenario.
There are two concurrent processes in our example scenario: the shell process and the hello process. Initially, the shell process is running alone, waiting for input on the command line. When we ask it to run the hello program, the shell carries out our request by invoking a special function known as a system call that passes control to the operating system. The operating system saves the shell's context, creates a new hello process and its context, and then passes control to the new hello process. After hello terminates, the operating system restores the context of the shell process and passes control back to it, where it waits for the next command line input. Implementing the process abstraction requires close cooperation between both the low-level hardware and the operating system software.
THE OPERATING SYSTEM MANAGES THE HARDWARE
Threads
Although we normally think of a process as having a single control flow, in modern systems a process can actually consist of multiple execution units, called threads, each running in the context of the process and sharing the same code and global data. Threads are an increasingly important programming model because of the requirement for concurrency in network servers, because it is easier to share data between multiple threads than between multiple processes, and because threads are typically more efficient than processes.
Virtual Memory
Virtual memory is an abstraction that provides each process with the illusion that it has exclusive use of the main memory. Each process has the same uniform view of memory, which is known as its virtual address space. The virtual address space for Linux processes is shown in Figure 1.11. (Other Unix systems use a similar layout.) In Linux, the topmost region of the address space is reserved for code and data in the operating system that is common to all processes. The lower region of the address space holds the code and data defined by the user's process. Note that addresses in the figure increase from the bottom to the top.
The virtual address space seen by each process consists of a number of well-defined areas, each with a specific purpose.
* Program code and data. Code begins at the same fixed address for all processes, followed by data locations that correspond to global C variables. The code and data areas are initialized directly from the contents of an executable object file, in our case the hello executable.
* Heap. The code and data areas are followed immediately by the run-time heap. Unlike the code and data areas, which are fixed in size once the process begins running, the heap expands and contracts dynamically at run time as a result of calls to C standard library routines such as malloc and free.
* Shared libraries. Near the middle of the address space is an area that holds the code and data for shared libraries such as the C standard library and the math library. The notion of a shared library is a powerful, but somewhat difficult concept.
* Stack. At the top of the user's virtual address space is the user stack that the compiler uses to implement function calls. Like the heap, the user stack expands and contracts dynamically during the execution of the program. In particular, each time we call a function, the stack grows. Each time we return from a function, it contracts.
* Kernel virtual memory. The kernel is the part of the operating system that is always resident in memory. The top region of the address space is reserved for the kernel. Application programs are not allowed to read or write the contents of this area or to directly call functions defined in the kernel code.
For virtual memory to work, a sophisticated interaction is required between the hardware and the operating system software, including a hardware translation of every address generated by the processor. The basic idea is to store the contents of a process's virtual memory on disk, and then use the main memory as a cache for the disk.
Files
"A file is a sequence of bytes, nothing more and nothing less. Every I/O device, including disks, keyboards, displays, and even networks, is modeled as a file. All input and output in the system is performed by reading and writing files, using a small set of system calls known as Unix I/O".
This simple and elegant notion of a file is nonetheless very powerful because it provides applications with a uniform view of all of the varied I/O devices that might be contained in the system. For example, application programmers who manipulate the contents of a disk file are blissfully unaware of the specific disk technology. Further, the same program will run on different systems that use different disk technologies.
************************************************************************************************
************************************************************************************************
Variables, Expressions and Loops
************************************************************************************************
Variables and Arithmetic Expressions
The next program uses the formula C= (5/9)(F-32) to print the following table of Fahrenheit temperatures and their centigrade or Celsius equivalents:
1 -17
20 -6
40 4
60 15
80 26
100 37
120 48
140 60
160 71
180 82
200 93
220 104
240 115
260 126
280 137
300 148
The program itself still consists of the definition of a single function named main. It is longer than the one that printed ``hello, world'', but not complicated. It introduces several new ideas, including comments, declarations, variables, arithmetic expressions, loops , and formatted output.
#include
/* print Fahrenheit-Celsius table
for fahr = 0, 20, ..., 300 */
main()
{
int fahr, celsius;
int lower, upper, step;
lower = 0; /* lower limit of temperature scale */
upper = 300; /* upper limit */
step = 20; /* step size */
fahr = lower;
while (fahr <= upper) { celsius = 5 * (fahr-32) / 9; printf("%d\t%d\n", fahr, celsius); fahr = fahr + step; } } The two lines /* print Fahrenheit-Celsius table for fahr = 0, 20, ..., 300 */ are a comment, which in this case explains briefly what the program does. Any characters between /* and */ are ignored by the compiler; they may be used freely to make a program easier to understand. Comments may appear anywhere where a blank, tab or newline can. In C, all variables must be declared before they are used, usually at the beginning of the function before any executable statements. A declaration announces the properties of variables; it consists of a name and a list of variables, such as int fahr, celsius; int lower, upper, step; The type int means that the variables listed are integers; by contrast with float, which means floating point, i.e., numbers that may have a fractional part. The range of both int and float depends on the machine you are using; 16-bits ints, which lie between -32768 and +32767, are common, as are 32-bit ints. A float number is typically a 32-bit quantity, with at least six significant digits and magnitude generally between about 10-38 and 1038. C provides several other data types besides int and float, including: char character - a single byte short short integer long long integer double double-precision floating point The size of these objects is also machine-dependent. There are also arrays, structures and unions of these basic types, pointers to them, and functions that return them, all of which we will meet in due course. Computation in the temperature conversion program begins with the assignment statements lower = 0; upper = 300; step = 20; which set the variables to their initial values. Individual statements are terminated by semicolons. Each line of the table is computed the same way, so we use a loop that repeats once per output line; this is the purpose of the while loop while (fahr <= upper) { ... } The while loop operates as follows: The condition in parentheses is tested. If it is true (fahr is less than or equal to upper), the body of the loop (the three statements enclosed in braces) is executed. Then the condition is retested, and if true, the body is executed again. When the test becomes false (fahr exceeds upper) the loop ends, and execution continues at the statement that follows the loop. There are no further statements in this program, so it terminates. The body of a while can be one or more statements enclosed in braces, as in the temperature converter, or a single statement without braces, as in while (i < j) i = 2 * i; In either case, we will always indent the statements controlled by the while by one tab stop (which we have shown as four spaces) so you can see at a glance which statements are inside the loop. The indentation emphasizes the logical structure of the program. Although C compilers do not care about how a program looks, proper indentation and spacing are critical in making programs easy for people to read. We recommend writing only one statement per line, and using blanks around operators to clarify grouping. The position of braces is less important, although people hold passionate beliefs. We have chosen one of several popular styles. Pick a style that suits you, and then use it consistently. Most of the work gets done in the body of the loop. The Celsius temperature is computed and assigned to the variable celsius by the statement celsius = 5 * (fahr-32) / 9; The reason for multiplying by 5 and dividing by 9 instead of just multiplying by 5/9 is that in C, as in many other languages, integer division truncates: any fractional part is discarded. Since 5 and 9 are integers. 5/9 would be truncated to zero and so all the Celsius temperatures would be reported as zero. This example also shows a bit more of how printf works. printf is a general-purpose output formatting function, which we will describe in detail in coming chapters. Its first argument is a string of characters to be printed, with each % indicating where one of the other (second, third, ...) arguments is to be substituted, and in what form it is to be printed. For instance, %d specifies an integer argument, so the statement printf("%d\t%d\n", fahr, celsius); causes the values of the two integers fahr and celsius to be printed, with a tab (\t) between them. Each % construction in the first argument of printf is paired with the corresponding second argument, third argument, etc.; they must match up properly by number and type, or you will get wrong answers. By the way, printf is not part of the C language; there is no input or output defined in C itself. printf is just a useful function from the standard library of functions that are normally accessible to C programs. The behaviour of printf is defined in the ANSI standard, however, so its properties should be the same with any compiler and library that conforms to the standard. If you have to input numbers, read the discussion of the function scanf in later modules scanf is like printf, except that it reads input instead of writing output. There are a couple of problems with the temperature conversion program. The simpler one is that the output isn't very pretty because the numbers are not right-justified. That's easy to fix; if we augment each %d in the printf statement with a width, the numbers printed will be right-justified in their fields. For instance, we might say printf("%3d %6d\n", fahr, celsius); to print the first number of each line in a field three digits wide, and the second in a field six digits wide, like this: 1 -17 20 -6 40 4 60 15 80 26 100 37 ... The more serious problem is that because we have used integer arithmetic, the Celsius temperatures are not very accurate; for instance, 0oF is actually about -17.8oC, not -17. To get more accurate answers, we should use floatingpoint arithmetic instead of integer. This requires some changes in the program. Here is the second version: #include /* print Fahrenheit-Celsius table for fahr = 0, 20, ..., 300; floating-point version */ main() { float fahr, celsius; float lower, upper, step; lower = 0; /* lower limit of temperatuire scale */ upper = 300; /* upper limit */ step = 20; /* step size */ fahr = lower; while (fahr <= upper) { celsius = (5.0/9.0) * (fahr-32.0); printf("%3.0f %6.1f\n", fahr, celsius); fahr = fahr + step; } } This is much the same as before, except that fahr and celsius are declared to be float and the formula for conversion is written in a more natural way. We were unable to use 5/9 in the previous version because integer division would truncate it to zero. A decimal point in a constant indicates that it is floating point, however, so 5.0/9.0 is not truncated because it is the ratio of two floating-point values. If an arithmetic operator has integer operands, an integer operation is performed. If an arithmetic operator has one floating-point operand and one integer operand, however, the integer will be converted to floating point before the operation is done. If we had written (fahr-32), the 32 would be automatically converted to floating point. Nevertheless, writing floating-point constants with explicit decimal points even when they have integral values emphasizes their floating-point nature for human readers. The detailed rules for when integers are converted to floating point are in coming chapters. For now, notice that the assignment fahr = lower; and the test while (fahr <= upper) also work in the natural way - the int is converted to float before the operation is done. The printf conversion specification %3.0f says that a floating-point number (here fahr) is to be printed at least three characters wide, with no decimal point and no fraction digits. %6.1f describes another number (celsius) that is to be printed at least six characters wide, with 1 digit after the decimal point. The output looks like this: 0 -17.8 20 -6.7 40 4.4 ... Width and precision may be omitted from a specification: %6f says that the number is to be at least six characters wide; %.2f specifies two characters after the decimal point, but the width is not constrained; and %f merely says to print the number as floating point. %d print as decimal integer %6d print as decimal integer, at least 6 characters wide %f print as floating point %6f print as floating point, at least 6 characters wide %.2f print as floating point, 2 characters after decimal point %6.2f print as floating point, at least 6 wide and 2 after decimal point Among others, printf also recognizes %o for octal, %x for hexadecimal, %c for character, %s for character string and %% for itself. The for statement There are plenty of different ways to write a program for a particular task. Let's try a variation on the temperature converter. #include
/* print Fahrenheit-Celsius table */
main()
{
int fahr;
for (fahr = 0; fahr <= 300; fahr = fahr + 20) printf("%3d %6.1f\n", fahr, (5.0/9.0)*(fahr-32)); } This produces the same answers, but it certainly looks different. One major change is the elimination of most of the variables; only fahr remains, and we have made it an int. The lower and upper limits and the step size appear only as constants in the for statement, itself a new construction, and the expression that computes the Celsius temperature now appears as the third argument of printf instead of a separate assignment statement. This last change is an instance of a general rule - in any context where it is permissible to use the value of some type, you can use a more complicated expression of that type. Since the third argument of printf must be a floating-point value to match the %6.1f, any floating-point expression can occur here. The for statement is a loop, a generalization of the while. If you compare it to the earlier while, its operation should be clear. Within the parentheses, there are three parts, separated by semicolons. The first part, the initialization fahr = 0 is done once, before the loop proper is entered. The second part is the test or condition that controls the loop: fahr <= 300 This condition is evaluated; if it is true, the body of the loop (here a single printf) is executed. Then the increment step fahr = fahr + 20 is executed, and the condition re-evaluated. The loop terminates if the condition has become false. As with the while, the body of the loop can be a single statement or a group of statements enclosed in braces. The initialization, condition and increment can be any expressions. The choice between while and for is arbitrary, based on which seems clearer. The for is usually appropriate for loops in which the initialization and increment are single statements and logically related, since it is more compact than while and it keeps the loop control statements together in one place. Symbolic Constants A final observation before we leave temperature conversion forever. It's bad practice to bury ``magic numbers'' like 300 and 20 in a program; they convey little information to someone who might have to read the program later, and they are hard to change in a systematic way. One way to deal with magic numbers is to give them meaningful names. A #define line defines a symbolic name or symbolic constant to be a particular string of characters: #define name replacement list Thereafter, any occurrence of name (not in quotes and not part of another name) will be replaced by the corresponding replacement text. The name has the same form as a variable name: a sequence of letters and digits that begins with a letter. The replacement text can be any sequence of characters; it is not limited to numbers. #include
#define LOWER 0 /* lower limit of table */
#define UPPER 300 /* upper limit */
#define STEP 20 /* step size */
/* print Fahrenheit-Celsius table */
main()
{
int fahr;
for (fahr = LOWER; fahr <= UPPER; fahr = fahr + STEP) printf("%3d %6.1f\n", fahr, (5.0/9.0)*(fahr-32)); } The quantities LOWER, UPPER and STEP are symbolic constants, not variables, so they do not appear in declarations. Symbolic constant names are conventionally written in upper case so they can ber readily distinguished from lower case variable names. Notice that there is no semicolon at the end of a #define line. ************************************************************************************************************************************************************************************************ Character Input and Output ************************************************************************************************ We are going to consider a family of related programs for processing character data. You will find that many programs are just expanded versions of the prototypes that we discuss here. The model of input and output supported by the standard library is very simple. Text input or output, regardless of where it originates or where it goes to, is dealt with as streams of characters. A text stream is a sequence of characters divided into lines; each line consists of zero or more characters followed by a newline character. It is the responsibility of the library to make each input or output stream confirm this model; the C programmer using the library need not worry about how lines are represented outside the program. The standard library provides several functions for reading or writing one character at a time, of which getchar and putchar are the simplest. Each time it is called, getchar reads the next input character from a text stream and returns that as its value. That is, after c = getchar(); the variable c contains the next character of input. The characters normally come from the keyboard; input from files is discussed in coming chapters. The function putchar prints a character each time it is called: putchar(c); prints the contents of the integer variable c as a character, usually on the screen. Calls to putchar and printf may be interleaved; the output will appear in the order in which the calls are made. File Copying Given getchar and putchar, you can write a surprising amount of useful code without knowing anything more about input and output. The simplest example is a program that copies its input to its output one character at a time: read a character while (charater is not end-of-file indicator) output the character just read read a character Converting this into C gives: #include
/* copy input to output; 1st version */
main()
{
int c;
c = getchar();
while (c != EOF) {
putchar(c);
c = getchar();
}
}
The relational operator != means ``not equal to''. What appears to be a character on the keyboard or screen is of course, like everything else, stored internally just as a bit pattern. The type char is specifically meant for storing such character data, but any integer type can be used. We used int for a subtle but important reason.
The problem is distinguishing the end of input from valid data. The solution is that getchar returns a distinctive value when there is no more input, a value that cannot be confused with any real character. This value is called EOF, for ``end of file''. We must declare c to be a type big enough to hold any value that getchar returns. We can't use char since c must be big enough to hold EOF in addition to any possible char. Therefore we use int.
EOF is an integer defined in
The program for copying would be written more concisely by experienced C programmers. In C, any assignment, such as
c = getchar();
is an expression and has a value, which is the value of the left hand side after the assignment. This means that a assignment can appear as part of a larger expression. If the assignment of a character to c is put inside the test part of a while loop, the copy program can be written this way:
#include
/* copy input to output; 2nd version */
main()
{
int c;
while ((c = getchar()) != EOF)
putchar(c);
}
The while gets a character, assigns it to c, and then tests whether the character was the end-of-file signal. If it was not, the body of the while is executed, printing the character. The while then repeats. When the end of the input is finally reached, the while terminates and so does main.
This version centralizes the input - there is now only one reference to getchar - and shrinks the program. The resulting program is more compact, and, once the idiom is mastered, easier to read. You'll see this style often. (It's possible to get carried away and create impenetrable code, however, a tendency that we will try to curb.)
The parentheses around the assignment, within the condition are necessary. The precedence of != is higher than that of =, which means that in the absence of parentheses the relational test != would be done before the assignment =. So the statement
c = getchar() != EOF
is equivalent to
c = (getchar() != EOF)
This has the undesired effect of setting c to 0 or 1, depending on whether or not the call of getchar returned end of file.
Character Counting
The next program counts characters; it is similar to the copy program.
#include
/* count characters in input; 1st version */
main()
{
long nc;
nc = 0;
while (getchar() != EOF)
++nc;
printf("%ld\n", nc);
}
The statement
++nc;
presents a new operator, ++, which means increment by one. You could instead write nc = nc + 1 but ++nc is more concise and often more efficient. There is a corresponding operator -- to decrement by 1. The operators ++ and -- can be either prefix operators (++nc) or postfix operators (nc++); these two forms have different values in expressions, as will be shown in coming chapters, but ++nc and nc++ both increment nc. For the moment we will will stick to the prefix form.
The character counting program accumulates its count in a long variable instead of an int. long integers are at least 32 bits. Although on some machines, int and long are the same size, on others an int is 16 bits, with a maximum value of 32767, and it would take relatively little input to overflow an int counter. The conversion specification %ld tells printf that the corresponding argument is a long integer.
It may be possible to cope with even bigger numbers by using a double (double precision float). We will also use a for statement instead of a while, to illustrate another way to write the loop.
#include
/* count characters in input; 2nd version */
main()
{
double nc;
for (nc = 0; gechar() != EOF; ++nc)
;
printf("%.0f\n", nc);
}
printf uses %f for both float and double; %.0f suppresses the printing of the decimal point and the fraction part, which is zero.
The body of this for loop is empty, because all the work is done in the test and increment parts. But the grammatical rules of C require that a for statement have a body. The isolated semicolon, called a null statement, is there to satisfy that requirement. We put it on a separate line to make it visible.
Before we leave the character counting program, observe that if the input contains no characters, the while or for test fails on the very first call to getchar, and the program produces zero, the right answer. This is important. One of the nice things about while and for is that they test at the top of the loop, before proceeding with the body. If there is nothing to do, nothing is done, even if that means never going through the loop body. Programs should act intelligently when given zero-length input. The while and for statements help ensure that programs do reasonable things with boundary conditions.
************************************************************************************************************************************************************************************************
Line and Word counting
************************************************************************************************
Line Counting
The next program counts input lines. As we mentioned above, the standard library ensures that an input text stream appears as a sequence of lines, each terminated by a newline. Hence, counting lines is just counting newlines:
#include
/* count lines in input */
main()
{
int c, nl;
nl = 0;
while ((c = getchar()) != EOF)
if (c == '\n')
++nl;
printf("%d\n", nl);
}
The body of the while now consists of an if, which in turn controls the increment ++nl. The if statement tests the parenthesized condition, and if the condition is true, executes the statement (or group of statements in braces) that follows. We have again indented to show what is controlled by what.
The double equals sign == is the C notation for ``is equal to'' (like Pascal's single = or Fortran's .EQ.). This symbol is used to distinguish the equality test from the single = that C uses for assignment. A word of caution: newcomers to C occasionally write = when they mean ==. As we will see in coming chapters, the result is usually a legal expression, so you will get no warning.
A character written between single quotes represents an integer value equal to the numerical value of the character in the machine's character set. This is called a character constant, although it is just another way to write a small integer. So, for example, 'A' is a character constant; in the ASCII character set its value is 65, the internal representation of the character A. Of course, 'A' is to be preferred over 65: its meaning is obvious, and it is independent of a particular character set.
The escape sequences used in string constants are also legal in character constants, so '\n' stands for the value of the newline character, which is 10 in ASCII. You should note carefully that '\n' is a single character, and in expressions is just an integer; on the other hand, '\n' is a string constant that happens to contain only one character.
Word Counting
The fourth in our series of useful programs counts lines, words, and characters, with the loose definition that a word is any sequence of characters that does not contain a blank, tab or newline. This is a bare-bones version of the UNIX program wc.
#include
#define IN 1 /* inside a word */
#define OUT 0 /* outside a word */
/* count lines, words, and characters in input */
main()
{
int c, nl, nw, nc, state;
state = OUT;
nl = nw = nc = 0;
while ((c = getchar()) != EOF) {
++nc;
if (c == '\n')
++nl;
if (c == ' ' || c == '\n' || c = '\t')
state = OUT;
else if (state == OUT) {
state = IN;
++nw;
}
}
printf("%d %d %d\n", nl, nw, nc);
}
Every time the program encounters the first character of a word, it counts one more word. The variable state records whether the program is currently in a word or not; initially it is ``not in a word'', which is assigned the value OUT. We prefer the symbolic constants IN and OUT to the literal values 1 and 0 because they make the program more readable. In a program as tiny as this, it makes little difference, but in larger programs, the increase in clarity is well worth the modest extra effort to write it this way from the beginning. You'll also find that it's easier to make extensive changes in programs where magic numbers appear only as symbolic constants.
The line
nl = nw = nc = 0;
sets all three variables to zero. This is not a special case, but a consequence of the fact that an assignment is an expression with the value and assignments associated from right to left. It's as if we had written
nl = (nw = (nc = 0));
The operator || means OR, so the line
if (c == ' ' || c == '\n' || c = '\t')
says ``if c is a blank or c is a newline or c is a tab''. (Recall that the escape sequence \t is a visible representation of the tab character.) There is a corresponding operator && for AND; its precedence is just higher than ||. Expressions connected by && or || are evaluated left to right, and it is guaranteed that evaluation will stop as soon as the truth or falsehood is known. If c is a blank, there is no need to test whether it is a newline or tab, so these tests are not made. This isn't particularly important here, but is significant in more complicated situations, as we will soon see.
The example also shows an else, which specifies an alternative action if the condition part of an if statement is false. The general form is
if (expression)
statement1
else
statement2
One and only one of the two statements associated with an if-else is performed. If the expression is true, statement1 is executed; if not, statement2 is executed. Each statement can be a single statement or several in braces.
In the word count program, the one after the else is an if that controls two statements in braces.
************************************************************************************************************************************************************************************************
Arrays
************************************************************************************************
There are twelve categories of input, so it is convenient to use an array to hold the number of occurrences of each digit, rather than ten individual variables. Here is one version of the program:
#include
/* count digits, white space, others */
main()
{
int c, i, nwhite, nother;
int ndigit[10];
nwhite = nother = 0;
for (i = 0; i < 10; ++i) ndigit[i] = 0; while ((c = getchar()) != EOF) if (c >= '0' && c <= '9') ++ndigit[c-'0']; else if (c == ' ' || c == '\n' || c == '\t') ++nwhite; else ++nother; printf("digits ="); for (i = 0; i < 10; ++i) printf(" %d", ndigit[i]); printf(", white space = %d, other = %d\n",nwhite, nother); } The output of this program on itself is digits = 9 3 0 0 0 0 0 0 0 1, white space = 123, other = 345 The declaration int ndigit[10]; declares ndigit to be an array of 10 integers. Array subscripts always start at zero in C, so the elements are ndigit[0], ndigit[1], ..., ndigit[9]. This is reflected in the for loops that initialize and print the array. A subscript can be any integer expression, which includes integer variables like i, and integer constants. This particular program relies on the properties of the character representation of the digits. For example, the test if (c >= '0' && c <= '9') determines whether the character in c is a digit. If it is, the numeric value of that digit is c - '0' This works only if '0', '1', ..., '9' have consecutive increasing values. Fortunately, this is true for all character sets. By definition, chars are just small integers, so char variables and constants are identical to ints in arithmetic expressions. This is natural and convenient; for example c-'0' is an integer expression with a value between 0 and 9 corresponding to the character '0' to '9' stored in c, and thus a valid subscript for the array ndigit. The decision as to whether a character is a digit, white space, or something else is made with the sequence if (c >= '0' && c <= '9') ++ndigit[c-'0']; else if (c == ' ' || c == '\n' || c == '\t') ++nwhite; else ++nother; The pattern if (condition1) statement1 else if (condition2) statement2 ... ... else statementn occurs frequently in programs as a way to express a multi-way decision. The conditions are evaluated in order from the top until some condition is satisfied; at that point the corresponding statement part is executed, and the entire construction is finished. (Any statement can be several statements enclosed in braces.) If none of the conditions is satisfied, the statement after the final else is executed if it is present. If the final else and statement are omitted, as in the word count program, no action takes place. There can be any number of else if(condition) statement groups between the initial if and the final else. As a matter of style, it is advisable to format this construction as we have shown; if each if were indented past the previous else, a long sequence of decisions would march off the right side of the page. The switch statement, to be discussed in coming chapters, provides another way to write a multi-way branch that is particularly suitable when the condition is whether some integer or character expression matches one of a set of constants. ************************************************************************************************************************************************************************************************ Functions ************************************************************************************************ Introduction In C, a function is equivalent to a subroutine or function in Fortran, or a procedure or function in Pascal. A function provides a convenient way to encapsulate some computation, which can then be used without worrying about its implementation. With properly designed functions, it is possible to ignore how a job is done; knowing what is done is sufficient. C makes the sue of functions easy, convenient and efficient; you will often see a short function defined and called only once, just because it clarifies some piece of code. So far we have used only functions like printf, getchar and putchar that have been provided for us; now it's time to write a few of our own. Since C has no exponentiation operator like the ** of Fortran, let us illustrate the mechanics of function definition by writing a function power(m,n) to raise an integer m to a positive integer power n. That is, the value of power(2,5) is 32. This function is not a practical exponentiation routine, since it handles only positive powers of small integers, but it's good enough for illustration.(The standard library contains a function pow(x,y) that computes x y.) Here is the function power and a main program to exercise it, so you can see the whole structure at once. #include
int power(int m, int n);
/* test power function */
main()
{
int i;
for (i = 0; i < 10; ++i) printf("%d %d %d\n", i, power(2,i), power(-3,i)); return 0; } /* power: raise base to n-th power; n >= 0 */
int power(int base, int n)
{
int i, p;
p = 1;
for (i = 1; i <= n; ++i) p = p * base; return p; } A function definition has this form: return-type function-name(parameter declarations, if any) { declarations statements } Function definitions can appear in any order, and in one source file or several, although no function can be split between files. If the source program appears in several files, you may have to say more to compile and load it than if it all appears in one, but that is an operating system matter, not a language attribute. For the moment, we will assume that both functions are in the same file, so whatever you have learned about running C programs will still work. The function power is called twice by main, in the line printf("%d %d %d\n", i, power(2,i), power(-3,i)); Each call passes two arguments to power, which each time returns an integer to be formatted and printed. In an expression, power(2,i) is an integer just as 2 The first line of power itself, int power(int base, int n) declares the parameter types and names, and the type of the result that the function returns. The names used by power for its parameters are local to power, and are not visible to any other function: other routines can use the same names without conflict. This is also true of the variables i and p: the i in power is unrelated to the i in main. We will generally use parameter for a variable named in the parenthesized list in a function. The terms formal argument and actual argument are sometimes used for the same distinction. The value that power computes is returned to main by the return: statement. Any expression may follow return: return expression; A function need not return a value; a return statement with no expression causes control, but no useful value, to be returned to the caller, as does ``falling off the end'' of a function by reaching the terminating right brace. And the calling function can ignore a value returned by a function. You may have noticed that there is a return statement at the end of main. Since main is a function like any other, it may return a value to its caller, which is in effect the environment in which the program was executed. Typically, a return value of zero implies normal termination; non-zero values signal unusual or erroneous termination conditions. In the interests of simplicity, we have omitted return statements from our main functions up to this point, but we will include them hereafter, as a reminder that programs should return status to their environment. The declaration int power(int base, int n); just before main says that power is a function that expects two int arguments and returns an int. This declaration, which is called a function prototype, has to agree with the definition and uses of power. It is an error if the definition of a function or any uses of it do not agree with its prototype. parameter names need not agree. Indeed, parameter names are optional in a function prototype, so for the prototype we could have written int power(int, int); Well-chosen names are good documentation however, so we will often use them. A note of history: the biggest change between ANSI C and earlier versions is how functions are declared and defined. In the original definition of C, the power function would have been written like this: /* power: raise base to n-th power; n >= 0 */
/* (old-style version) */
power(base, n)
int base, n;
{
int i, p;
p = 1;
for (i = 1; i <= n; ++i) p = p * base; return p; } The parameters are named between the parentheses, and their types are declared before opening the left brace; undeclared parameters are taken as int. (The body of the function is the same as before.) The declaration of power at the beginning of the program would have looked like this: int power(); No parameter list was permitted, so the compiler could not readily check that power was being called correctly. Indeed, since by default power would have been assumed to return an int, the entire declaration might well have been omitted. The new syntax of function prototypes makes it much easier for a compiler to detect errors in the number of arguments or their types. The old style of declaration and definition still works in ANSI C, at least for a transition period, but we strongly recommend that you use the new form when you have a compiler that supports it. 1. Rewrite the temperature conversion program of Module 3 to use a function for conversion 2. Write a program to call a function power(x,y) = xy Note: write a function power and call it in the main function. 33.3. The function called menu which prints the text string "Menu choices", and does not pass any data back, and does not accept any data as parameters, looks like function 1 void menu( void ) { printf("Menu choices"); } function 2 int menu( void ) { printf("Menu choices"); } function 3 int menu( char string[] ) { printf("%s", string); } 44. A function called print which prints a text string passed to it as a parameter (ie, a character based array), looks like function 1 int print( char string[] ) { printf("%s", string); } function 2 void print( char string[] ) { printf("Menu choices"); } function 3 void print( char string[] ) { printf("%s", string); } 4455. 5. A function called total, totals the sum of an integer array passed to it (as the first parameter) and returns the total of all the elements as an integer. Let the second parameter to the function be an integer which contains the number of elements of the array. function 1 int total( int numbers[], int elements ) { int total = 0, loop; for( loop = 0; loop < elements; loop++ ) total = total + numbers[loop]; return total; } function 2 int total( int numbers[], int elements ) { int total = 0, loop; for( loop = 0; loop <= elements; loop++ ) total = total + numbers[loop]; return total; } function 3 int total( int numbers[], int elements ) { int total, loop; for( loop = 0; loop > elements; loop++ )
total = total + numbers[loop];
return total;
}
Arguments - Call by Value
One aspect of C functions may be unfamiliar to programmers who are used to some other languages, particulary Fortran. In C, all function arguments are passed ``by value.'' This means that the called function is given the values of its arguments in temporary variables rather than the originals. This leads to some different properties than are seen with ``call by reference'' languages like Fortran or with var parameters in Pascal, in which the called routine has access to the original argument, not a local copy.
Call by value is an asset, however, not a liability. It usually leads to more compact programs with fewer extraneous variables, because parameters can be treated as conveniently initialized local variables in the called routine. For example, here is a version of power that makes use of this property.
/* power: raise base to n-th power; n >= 0; version 2 */
int power(int base, int n)
{
int p;
for (p = 1; n > 0; --n)
p = p * base;
return p;
}
The parameter n is used as a temporary variable, and is counted down (a for loop that runs backwards) until it becomes zero; there is no longer a need for the variable i. Whatever is done to n inside power has no effect on the argument that power was originally called with. When necessary, it is possible to arrange for a function to modify a variable in a calling routine. The caller must provide the address of the variable to be set (technically a pointer to the variable), and the called function must declare the parameter to be a pointer and access the variable indirectly through it.
The story is different for arrays. When the name of an array is used as an argument, the value passed to the function is the location or address of the beginning of the array - there is no copying of array elements. By subscripting this value, the function can access and alter any argument of the array.
************************************************************************************************************************************************************************************************
Character Arrays
************************************************************************************************
Introduction
The most common type of array in C is the array of characters. To illustrate the use of character arrays and functions to manipulate them, let's write a program that reads a set of text lines and prints the longest. The outline is simple enough:
while (there's another line)
if (it's longer than the previous longest)
(save it)
(save its length)
print longest line
This outline makes it clear that the program divides naturally into pieces. One piece gets a new line, another saves it, and the rest controls the process. Since things divide so nicely, it would be well to write them that way too.
Accordingly, let us first write a separate function getline to fetch the next line of input. We will try to make the function useful in other contexts. At the minimum, getline has to return a signal about possible end of file; a more useful design would be to return the length of the line, or zero if end of file is encountered. Zero is an acceptable end-of-file return because it is never a valid line length. Every text line has at least one character; even a line containing only a newline has length 1.
When we find a line that is longer than the previous longest line, it must be saved somewhere. This suggests a second function, copy, to copy the new line to a safe place.
Finally, we need a main program to control getline and copy. Here is the result.
#include
#define MAXLINE 1000 /* maximum input line length */
int getline(char line[], int maxline);
void copy(char to[], char from[]);
/* print the longest input line */
main()
{
int len; /* current line length */
int max; /* maximum length seen so far */
char line[MAXLINE]; /* current input line */
char longest[MAXLINE]; /* longest line saved here */
max = 0;
while ((len = getline(line, MAXLINE)) > 0)
if (len > max) {
max = len;
copy(longest, line);
}
if (max > 0) /* there was a line */
printf("%s", longest);
return 0;
}
/* getline: read a line into s, return length */
int getline(char s[],int lim)
{
int c, i;
for (i=0; i < lim-1 && (c=getchar())!=EOF && c!='\n'; ++i) s[i] = c; if (c == '\n') { s[i] = c; ++i; } s[i] = '\0'; return i; } /* copy: copy 'from' into 'to'; assume to is big enough */ void copy(char to[], char from[]) { int i; i = 0; while ((to[i] = from[i]) != '\0') ++i; } The functions getline and copy are declared at the beginning of the program, which we assume is contained in one file. main and getline communicate through a pair of arguments and a returned value. In getline, the arguments are declared by the line int getline(char s[], int lim); which specifies that the first argument, s, is an array, and the second, lim, is an integer. The purpose of supplying the size of an array in a declaration is to set aside storage. The length of an array s is not necessary in getline since its size is set in main. getline uses return to send a value back to the caller, just as the function power did. This line also declares that getline returns an int; since int is the default return type, it could be omitted. Some functions return a useful value; others, like copy, are used only for their effect and return no value. The return type of copy is void, which states explicitly that no value is returned. getline puts the character '\0' (the null character, whose value is zero) at the end of the array it is creating, to mark the end of the string of characters. This conversion is also used by the C language: when a string constant like "hello\n" appears in a C program, it is stored as an array of characters containing the characters in the string and terminated with a '\0' to mark the end. The %s format specification in printf expects the corresponding argument to be a string represented in this form. copy also relies on the fact that its input argument is terminated with a '\0', and copies this character into the output. It is worth mentioning in passing that even a program as small as this one presents some sticky design problems. For example, what should main do if it encounters a line which is bigger than its limit? getline works safely, in that it stops collecting when the array is full, even if no newline has been seen. By testing the length and the last character returned, main can determine whether the line was too long, and then cope as it wishes. In the interests of brevity, we have ignored this issue. There is no way for a user of getline to know in advance how long an input line might be, so getline checks for overflow. On the other hand, the user of copy already knows (or can find out) how big the strings are, so we have chosen not to add error checking to it. ************************************************************************************************************************************************************************************************ Variables and Constants ************************************************************************************************ Variables and constants are the basic data objects manipulated in a program. Declarations list the variables to be used, and state what type they have and perhaps what their initial values are. Operators specify what is to be done to them. Expressions combine variables and constants to produce new values. The type of an object determines the set of values it can have and what operations can be performed on it. These building blocks are the topics of this chapter. The ANSI standard has made many small changes and additions to basic types and expressions. There are now signed and unsigned forms of all integer types, and notations for unsigned constants and hexadecimal character constants. Floating-point operations may be done in single precision; there is also a long double type for extended precision. String constants may be concatenated at compile time. Enumerations have become part of the language, formalizing a feature of long standing. Objects may be declared const, which prevents them from being changed. The rules for automatic coercions among arithmetic types have been augmented to handle the richer set of types. Variable Names There are some restrictions on the names of variables and symbolic constants. Names are made up of letters and digits; the first character must be a letter. The underscore ``_'' counts as a letter; it is sometimes useful for improving the readability of long variable names. Don't begin variable names with underscore, however, since library routines often use such names. Upper and lower case letters are distinct, so x and X are two different names. Traditional C practice is to use lower case for variable names, and all upper case for symbolic constants. At least the first 31 characters of an internal name are significant. For function names and external variables, the number may be less than 31, because external names may be used by assemblers and loaders over which the language has no control. For external names, the standard guarantees uniqueness only for 6 characters and a single case. Keywords like if, else, int, float, etc., are reserved: you can't use them as variable names. They must be in lower case. It's wise to choose variable names that are related to the purpose of the variable, and that are unlikely to get mixed up typographically. We tend to use short names for local variables, especially loop indices, and longer names for external variables. Data Types and Sizes There are only a few basic data types in C: char a single byte, capable of holding one character in the local character set int an integer, typically reflecting the natural size of integers on the host machine float single-precision floating point double double-precision floating point In addition, there are a number of qualifiers that can be applied to these basic types. short and long apply to integers: short int sh; long int counter; The word int can be omitted in such declarations, and typically it is. The intent is that short and long should provide different lengths of integers where practical; int will normally be the natural size for a particular machine. short is often 16 bits long, and int either 16 or 32 bits. Each compiler is free to choose appropriate sizes for its own hardware, subject only to the the restriction that shorts and ints are at least 16 bits, longs are at least 32 bits, and short is no longer than int, which is no longer than long. The qualifier signed or unsigned may be applied to char or any integer. unsigned numbers are always positive or zero, and obey the laws of arithmetic modulo 2n, where n is the number of bits in the type. So, for instance, if chars are 8 bits, unsigned char variables have values between 0 and 255, while signed chars have values between -128 and 127 (in a two's complement machine.) Whether plain chars are signed or unsigned is machine-dependent, but printable characters are always positive. The type long double specifies extended-precision floating point. As with integers, the sizes of floating-point objects are implementation-defined; float, double and long double could represent one, two or three distinct sizes. The standard headers
Additional Problem
1. Write a program to determine the ranges of char, short, int, and long variables, both signed and unsigned, by printing appropriate values from standard headers and by direct computation. Harder if you compute them: determine the ranges of the various floating-point types.
Hint: For char its printf("Size of Char %d\n", CHAR_BIT);
Constants
An integer constant like 1234 is an int. A long constant is written with a terminal l (ell) or L, as in 123456789L; an integer constant too big to fit into an int will also be taken as a long. Unsigned constants are written with a terminal u or U, and the suffix ul or UL indicates unsigned long.
Floating-point constants contain a decimal point (123.4) or an exponent (1e-2) or both; their type is double, unless suffixed. The suffixes f or F indicate a float constant; l or L indicate a long double.
The value of an integer can be specified in octal or hexadecimal instead of decimal. A leading 0 (zero) on an integer constant means octal; a leading 0x or 0X means hexadecimal. For example, decimal 31 can be written as 037 in octal and 0x1f or 0x1F in hex. Octal and hexadecimal constants may also be followed by L to make them long and U to make them unsigned: 0XFUL is an unsigned long constant with value 15 decimal.
A character constant is an integer, written as one character within single quotes, such as 'x'. The value of a character constant is the numeric value of the character in the machine's character set. For example, in the ASCII character set the character constant '0' has the value 48, which is unrelated to the numeric value 0. If we write '0' instead of a numeric value like 48 that depends on the character set, the program is independent of the particular value and easier to read. Character constants participate in numeric operations just as any other integers, although they are most often used in comparisons with other characters.
Certain characters can be represented in character and string constants by escape sequences like \n (newline); these sequences look like two characters, but represent only one. In addition, an arbitrary bytesized bit pattern can be specified by
'\ooo'
where ooo is one to three octal digits (0...7) or by
'\xhh'
where hh is one or more hexadecimal digits (0...9, a...f, A...F). So we might write
#define VTAB '\013' /* ASCII vertical tab */
#define BELL '\007' /* ASCII bell character */
or, in hexadecimal,
#define VTAB '\xb' /* ASCII vertical tab */
#define BELL '\x7' /* ASCII bell character */
The complete set of escape sequences is
The character constant '\0' represents the character with value zero, the null character. '\0' is often written instead of 0 to emphasize the character nature of some expression, but the numeric value is just 0.
A constant expression is an expression that involves only constants. Such expressions may be evaluated at during compilation rather than run-time, and accordingly may be used in any place that a constant can occur, as in
#define MAXLINE 1000
char line[MAXLINE+1];
or
#define LEAP 1 /* in leap years */
int days[31+28+LEAP+31+30+31+30+31+31+30+31+30+31];
A string constant, or string literal, is a sequence of zero or more characters surrounded by double quotes, as in
"I am a string"
or
"" /* the empty string */
The quotes are not part of the string, but serve only to delimit it. The same escape sequences used in character constants apply in strings; \" represents the double quote character. String constants can be concatenated at compile time:
"hello, " "world"
is equivalent to
"hello, world"
This is useful for splitting up long strings across several source lines. Technically, a string constant is an array of characters. The internal representation of a string has a null character '\0' at the end, so the physical storage required is one more than the number of characters written between the quotes. This representation means that there is no limit to how long a string can be, but programs must scan a string completely to determine its length. The standard library function strlen(s) returns the length of its character string argument s, excluding the terminal '\0'. Here is our version:
/* strlen: return length of s */
int strlen(char s[])
{
int i;
while (s[i] != '\0')
++i;
return i;
}
strlen and other string functions are declared in the standard header
Be careful to distinguish between a character constant and a string that contains a single character: 'x' is not the same as "x". The former is an integer, used to produce the numeric value of the letter x in the machine's character set. The latter is an array of characters that contains one character (the letter x) and a '\0'.
There is one other kind of constant, the enumeration constant. An enumeration is a list of constant integer values, as in
enum boolean { NO, YES };
The first name in an enum has value 0, the next 1, and so on, unless explicit values are specified. If not all values are specified, unspecified values continue the progression from the last specified value, as the second of these examples:
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 };
/* FEB = 2, MAR = 3, etc. */
Names in different enumerations must be distinct. Values need not be distinct in the same enumeration. Enumerations provide a convenient way to associate constant values with names, an alternative to #define with the advantage that the values can be generated for you. Although variables of enum types may be declared, compilers need not check that what you store in such a variable is a valid value for the enumeration. Nevertheless, enumeration variables offer the chance of checking and so are often better than #defines. In addition, a debugger may be able to print values of enumeration variables in their symbolic form.
Declarations
All variables must be declared before use, although certain declarations can be made implicitly by content. A declaration specifies a type, and contains a list of one or more variables of that type, as in
int lower, upper, step;
char c, line[1000];
Variables can be distributed among declarations in any fashion; the lists above could well be written as
int lower;
int upper;
int step;
char c;
char line[1000];
The latter form takes more space, but is convenient for adding a comment to each declaration for subsequent modifications. A variable may also be initialized in its declaration. If the name is followed by an equals sign and an expression, the expression serves as an initializer, as in
char esc = '\\';
int i = 0;
int limit = MAXLINE+1;
float eps = 1.0e-5;
If the variable in question is not automatic, the initialization is done once only, conceptionally before the program starts executing, and the initializer must be a constant expression. An explicitly initialized automatic variable is initialized each time the function or block it is in is entered; the initializer may be any expression. External and static variables are initialized to zero by default. Automatic variables for which is no explicit initializer have undefined (i.e., garbage) values.
The qualifier const can be applied to the declaration of any variable to specify that its value will not be changed. For an array, the const qualifier says that the elements will not be altered.
const double e = 2.71828182845905;
const char msg[] = "warning: ";
The const declaration can also be used with array arguments, to indicate that the function does not change that array:
int strlen(const char[]);
The result is implementation-defined if an attempt is made to change a const.
************************************************************************************************************************************************************************************************
Operators
************************************************************************************************
Arithmetic Operators
The binary arithmetic operators are +, -, *, /, and the modulus operator %. Integer division truncates any fractional part. The expression
x % y
produces the remainder when x is divided by y, and thus is zero when y divides x exactly. For example, a year is a leap year if it is divisible by 4 but not by 100, except that years divisible by 400 are leap years.
Therefore
if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)
printf("%d is a leap year\n", year);
else
printf("%d is not a leap year\n", year);
The % operator cannot be applied to a float or double. The direction of truncation for / and the sign of the result for % are machine-dependent for negative operands, as is the action taken on overflow or underflow.
The binary + and - operators have the same precedence, which is lower than the precedence of *, / and %, which is in turn lower than unary + and -. Arithmetic operators associate left to right. [Top]
Relational and Logical Operators
The relational operators are
> >= < <= They all have the same precedence. Just below them in precedence are the equality operators: == != Relational operators have lower precedence than arithmetic operators, so an expression like i < lim-1 is taken as i < (lim-1), as would be expected. More interesting are the logical operators && and ||. Expressions connected by && or || are evaluated left to right, and evaluation stops as soon as the truth or falsehood of the result is known. Most C programs rely on these properties. For example, here is a loop from the input function getline that we wrote in previous modules: for (i=0; i < lim-1 && (c=getchar()) != '\n' && c != EOF; ++i) s[i] = c; Before reading a new character it is necessary to check that there is room to store it in the array s, so the test i < lim-1 must be made first. Moreover, if this test fails, we must not go on and read another character. Similarly, it would be unfortunate if c were tested against EOF before getchar is called; therefore the call and assignment must occur before the character in c is tested. The precedence of && is higher than that of ||, and both are lower than relational and equality operators, so expressions like i < lim-1 && (c=getchar()) != '\n' && c != EOF need no extra parentheses. But since the precedence of != is higher than assignment, parentheses are needed in (c=getchar()) != '\n' to achieve the desired result of assignment to c and then comparison with '\n'. By definition, the numeric value of a relational or logical expression is 1 if the relation is true, and 0 if the relation is false. The unary negation operator ! converts a non-zero operand into 0, and a zero operand in 1. A common use of ! is in constructions like if (!valid) rather than if (valid == 0) It's hard to generalize about which form is better. Constructions like !valid read nicely (``if not valid''), but more complicated ones can be hard to understand. [Top] Type Conversions When an operator has operands of different types, they are converted to a common type according to a small number of rules. In general, the only automatic conversions are those that convert a ``narrower'' operand into a ``wider'' one without losing information, such as converting an integer into floating point in an expression like f + i. Expressions that don't make sense, like using a float as a subscript, are disallowed. Expressions that might lose information, like assigning a longer integer type to a shorter, or a floating-point type to an integer, may draw a warning, but they are not illegal. A char is just a small integer, so chars may be freely used in arithmetic expressions. This permits considerable flexibility in certain kinds of character transformations. One is exemplified by this naïve implementation of the function atoi, which converts a string of digits into its numeric equivalent. /* atoi: convert s to integer */ int atoi(char s[]) { int i, n; n = 0; for (i = 0; s[i] >= '0' && s[i] <= '9'; ++i) n = 10 * n + (s[i] - '0'); return n; } As we discussed in previous modules, the expression s[i] - '0' gives the numeric value of the character stored in s[i], because the values of '0', '1', etc., form a contiguous increasing sequence. Another example of char to int conversion is the function lower, which maps a single character to lower case for the ASCII character set. If the character is not an upper case letter, lower returns it unchanged. /* lower: convert c to lower case; ASCII only */ int lower(int c) { if (c >= 'A' && c <= 'Z') return c + 'a' - 'A'; else return c; } This works for ASCII because corresponding upper case and lower case letters are a fixed distance apart as numeric values and each alphabet is contiguous -- there is nothing but letters between A and Z. This latter observation is not true of the EBCDIC character set, however, so this code would convert more than just letters in EBCDIC. The standard header
tests and conversions that are independent of character set. For example, the function tolower is a portable replacement for the function lower shown above. Similarly, the test
c >= '0' && c <= '9' can be replaced by isdigit(c) We will use the
There is one subtle point about the conversion of characters to integers. The language does not specify whether variables of type char are signed or unsigned quantities. When a char is converted to an int, can it ever produce a negative integer? The answer varies from machine to machine, reflecting differences in architecture. On some machines a char whose leftmost bit is 1 will be converted to a negative integer (``sign extension''). On others, a char is promoted to an int by adding zeros at the left end, and thus is always positive.
The definition of C guarantees that any character in the machine's standard printing character set will never be negative, so these characters will always be positive quantities in expressions. But arbitrary bit patterns stored in character variables may appear to be negative on some machines, yet positive on others. For portability, specify signed or unsigned if non-character data is to be stored in char variables.
Relational expressions like i > j and logical expressions connected by && and || are defined to have value 1 if true, and 0 if false. Thus the assignment
d = c >= '0' && c <= '9' sets d to 1 if c is a digit, and 0 if not. However, functions like isdigit may return any non-zero value for true. In the test part of if, while, for, etc., ``true'' just means ``non-zero'', so this makes no difference. Implicit arithmetic conversions work much as expected. In general, if an operator like + or * that takes two operands (a binary operator) has operands of different types, the ``lower'' type is promoted to the ``higher'' type before the operation proceeds. If there are no unsigned operands, however, the following informal set of rules will suffice: If either operand is long double, convert the other to long double. l Otherwise, if either operand is double, convert the other to double. l Otherwise, if either operand is float, convert the other to float. l Otherwise, convert char and short to int. l Then, if either operand is long, convert the other to long. Notice that floats in an expression are not automatically converted to double; this is a change from the original definition. In general, mathematical functions like those in
Conversion rules are more complicated when unsigned operands are involved. The problem is that comparisons between signed and unsigned values are machine-dependent, because they depend on the sizes of the various integer types. For example, suppose that int is 16 bits and long is 32 bits. Then - 1L < 1U, because 1U, which is an unsigned int, is promoted to a signed long. But -1L > 1UL because -1L is promoted to unsigned long and thus appears to be a large positive number.
Conversions take place across assignments; the value of the right side is converted to the type of the left, which is the type of the result.
A character is converted to an integer, either by sign extension or not, as described above. Longer integers are converted to shorter ones or to chars by dropping the excess high-order bits. Thus in
int i;
char c;
i = c;
c = i;
the value of c is unchanged. This is true whether or not sign extension is involved.
Reversing the order of assignments might lose information, however. If x is float and i is int, then x = i and i = x both cause conversions; float to int causes truncation of any fractional part. When a double is converted to float, whether the value is rounded or truncated is implementation dependent.
Since an argument of a function call is an expression, type conversion also takes place when arguments are passed to functions. In the absence of a function prototype, char and short become int, and float becomes double. This is why we have declared function arguments to be int and double even when the function is called with char and float.
Finally, explicit type conversions can be forced (``coerced'') in any expression, with a unary operator called a cast. In the construction
(type name) expression
the expression is converted to the named type by the conversion rules above. The precise meaning of a cast is as if the expression were assigned to a variable of the specified type, which is then used in place of the whole construction. For example, the library routine sqrt expects a double argument, and will produce nonsense if inadvertently handled something else. (sqrt is declared in
to convert the value of n to double before passing it to sqrt. Note that the cast produces the value of n in the proper type; n itself is not altered. The cast operator has the same high precedence as other unary operators, as summarized in the table at the end of this chapter.
If arguments are declared by a function prototype, as the normally should be, the declaration causes automatic coercion of any arguments when the function is called. Thus, given a function prototype for
sqrt:
double sqrt(double)
the call
root2 = sqrt(2)
coerces the integer 2 into the double value 2.0 without any need for a cast.
The standard library includes a portable implementation of a pseudo-random number generator and a function for initializing the seed; the former illustrates a cast:
unsigned long int next = 1;
/* rand: return pseudo-random integer on 0..32767 */
int rand(void)
{
next = next * 1103515245 + 12345;
return (unsigned int)(next/65536) % 32768;
}
/* srand: set seed for rand() */
void srand(unsigned int seed)
{
next = seed;
} [Top]
Increment and Decrement Operators
C provides two unusual operators for incrementing and decrementing variables. The increment operator ++ adds 1 to its operand, while the decrement operator -- subtracts 1. We have frequently used ++ to increment variables, as in
if (c == '\n')
++nl;
The unusual aspect is that ++ and -- may be used either as prefix operators (before the variable, as in ++n), or postfix operators (after the variable: n++). In both cases, the effect is to increment n. But the expression ++n increments n before its value is used, while n++ increments n after its value has been
used. This means that in a context where the value is being used, not just the effect,
++n and n++ are different. If n is 5, then
x = n++;
sets x to 5, but
x = ++n;
sets x to 6. In both cases, n becomes 6. The increment and decrement operators can only be applied to variables; an expression like (i+j)++ is illegal.
In a context where no value is wanted, just the incrementing effect, as in
if (c == '\n')
nl++;
prefix and postfix are the same. But there are situations where one or the other is specifically called for.
For instance, consider the function squeeze(s,c), which removes all occurrences of the character c from the string s.
/* squeeze: delete all c from s */
void squeeze(char s[], int c)
{
int i, j;
for (i = j = 0; s[i] != '\0'; i++)
if (s[i] != c)
s[j++] = s[i];
s[j] = '\0';
}
Each time a non-c occurs, it is copied into the current j position, and only then is j incremented to be ready for the next character. This is exactly equivalent to
if (s[i] != c) {
s[j] = s[i];
j++;
}
Another example of a similar construction comes from the getline function where we can replace
if (c == '\n') {
s[i] = c;
++i;
}
by the more compact
if (c == '\n')
s[i++] = c;
As a third example, consider the standard function strcat(s,t), which
concatenates the string t to the end of string s. strcat assumes that there is enough space in s to hold the combination. As we have written it, strcat returns no value; the standard library version returns a pointer to the resulting
string.
/* strcat: concatenate t to end of s; s must be big enough */
void strcat(char s[], char t[])
{
int i, j;
i = j = 0;
while (s[i] != '\0') /* find end of s */
i++;
while ((s[i++] = t[j++]) != '\0') /* copy t */
;
}
As each member is copied from t to s, the postfix ++ is applied to both i and j to make sure that they are in position for the next pass through the loop.
************************************************************************************************************************************************************************************************
Operators and Expressions
************************************************************************************************
Bitwise Operators
C provides six operators for bit manipulation; these may only be applied to integral operands, that is, char, short, int, and long, whether signed or unsigned.
& bitwise AND
| bitwise inclusive OR
^ bitwise exclusive OR
<< left shift >> right shift
~ one's complement (unary)
The bitwise AND operator & is often used to mask off some set of bits, for example
n = n & 0177;
sets to zero all but the low-order 7 bits of n.
The bitwise OR operator | is used to turn bits on:
x = x | SET_ON;
sets to one in x the bits that are set to one in SET_ON.
The bitwise exclusive OR operator ^ sets a one in each bit position where its operands have different bits, and zero where they are the same.
One must distinguish the bitwise operators & and | from the logical operators && and ||, which imply left-to-right evaluation of a truth value. For example, if x is 1 and y is 2, then x & y is zero while x && y is one.
The shift operators << and >> perform left and right shifts of their left operand by the number of bit positions given by the right operand, which must be non-negative. Thus x << 2 shifts the value of x by two positions, filling vacated bits with zero; this is equivalent to multiplication by 4. Right shifting an unsigned quantity always fits the vacated bits with zero. Right shifting a signed quantity will fill with bit signs (``arithmetic shift'') on some machines and with 0-bits (``logical shift'') on others. The unary operator ~ yields the one's complement of an integer; that is, it converts each 1-bit into a 0-bit and vice versa. For example x = x & ~077 sets the last six bits of x to zero. Note that x & ~077 is independent of word length, and is thus preferable to, for example, x & 0177700, which assumes that x is a 16-bit quantity. The portable form involves no extra cost, since ~077 is a constant expression that can be evaluated at compile time. As an illustration of some of the bit operators, consider the function getbits(x,p,n) that returns the (right adjusted) n-bit field of x that begins at position p. We assume that bit position 0 is at the right end and that n and p are sensible positive values. For example, getbits(x,4,3) returns the three bits in positions 4, 3 and 2, right-adjusted. /* getbits: get n bits from position p */ unsigned getbits(unsigned x, int p, int n) { return (x >> (p+1-n)) & ~(~0 << n); } The expression x >> (p+1-n) moves the desired field to the right end of the word. ~0 is all 1-bits; shifting it left n positions with ~0<
#include
main()
{
int n;
printf(" enter any +ve integer \n");
scanf("%d",&n);
if( n & 1 == 1) // if last bit in numbers is 1, 'n' is odd , 0 for even
printf(" odd number\n");
else
printf(" even number \n");
getch();
}
o/p:
If you enter 'n' value as 25 output is odd number, or if you enter 24 output is even number
2. Swapping two values by using bitwise operators
#include
#include
main()
{
int a , b;
printf(" enter any 2 integers \n");
scanf("%d%d", &a , &b);
a = a ^ b;
b = a ^ b;
a = a ^ b;
printf(" a = %d \n", a);
printf( " b = %d \n", b);
getch();
}
o/p:
If you enter a, b values as 5, 6 output is a = 6 , b = 5
3. Write a function setbits(a,b,c,d) that returns a with the n bits that begin at position b set to the rightmost c bits of d, leaving the other bits unchanged.
#include
#include
unsigned setbits(unsigned a, int b, int c, int d);
int main(void)
{
printf("%u\n", setbits(170, 4, 3, 7));
return EXIT_SUCCESS;
}
/* getbits: place c rightmost bits from position b at position d */
unsigned setbits(unsigned x, int p, int n, int y)
{
int i, mask, j;
/* The rightmost c bits of d. */
i = (a >> (d+1-c)) & ~(~0 <
int main(void)
{
unsigned x;
int p, n;
for(x = 0; x < 700; x += 49) for(n = 1; n < 8; n++) for(p = 1; p < 8; p++) printf("%u, %d, %d: %u\n", x, n, p, invert(x, n, p)); return 0; } 3. Write a function rightrot(x,n) that returns the value of the integer x rotated to the right by n positions. Solution: unsigned rightrot(unsigned x, unsigned n) { while (n > 0) {
if ((x & 1) == 1)
x = (x >> 1) | ~(~0U >> 1);
else
x = (x >> 1);
n--;
}
return x;
}
#include
int main(void)
{
unsigned x;
int n;
for(x = 0; x < 700; x += 49) for(n = 1; n < 8; n++) printf("%u, %d: %u\n", x, n, rightrot(x, n)); return 0; } Assignment Operators and Expressions An expression such as i = i + 2 in which the variable on the left side is repeated immediately on the right, can be written in the compressed form i += 2 The operator += is called an assignment operator. Most binary operators (operators like + that have a left and right operand) have a corresponding assignment operator op=, where op is one of + - * / % << >> & ^ |
If expr1 and expr2 are expressions, then
expr1 op= expr2
is equivalent to
expr1 = (expr1) op (expr2)
except that expr1 is computed only once. Notice the parentheses around expr2:
x *= y + 1
means
x = x * (y + 1)
rather than
x = x * y + 1
As an example, the function bitcount counts the number of 1-bits in its integer argument.
/* bitcount: count 1 bits in x */
int bitcount(unsigned x)
{
int b;
for (b = 0; x != 0; x >>= 1)
if (x & 01)
b++;
return b;
}
Declaring the argument x to be an unsigned ensures that when it is right-shifted, vacated bits will be filled with zeros, not sign bits, regardless of the machine the program is run on.
Quite apart from conciseness, assignment operators have the advantage that they correspond better to the way people think. We say ``add 2 to i'' or ``increment i by 2'', not ``take i, add 2, then put the result back in i''. Thus the expression i += 2 is preferable to i = i+2. In addition, for a complicated expression like
yyval[yypv[p3+p4] + yypv[p1]] += 2
the assignment operator makes the code easier to understand, since the reader doesn't have to check painstakingly that two long expressions are indeed the same, or to wonder why they're not. And an assignment operator may even help a compiler to produce efficient code.
We have already seen that the assignment statement has a value and can occur in expressions; the most common example is
while ((c = getchar()) != EOF)
...
The other assignment operators (+=, -=, etc.) can also occur in expressions, although this is less frequent. In all such expressions, the type of an assignment expression is the type of its left operand, and the value is the value after the assignment.
Worked Out Example [Problem Set][Example]
1. This program calculates the volume of a cylinder, given its radius and height
#include
int main()
{
float radius, height, volume;
radius = 2.5;
height = 16.0;
volume = 3.1416 * radius * radius * height;
cout << "The volume of the cylinder is " << volume << endl; return 0; } The output of the above program: The volume of the cylinder is 314.16 Worked Example: 1. In a two's complement number system, m &= (m-1) deletes the rightmost 1-bit in m. Explain why. Use this observation to write a faster version of bitcount. Answer: If m is odd, then (m-1) has the same bit representation as m except that the rightmost 1-bit is now a 0. In this case, (m & (m-1)) == (m-1). If x is even, then the representation of (m-1) has the rightmost zeros of m becoming ones and the rightmost one becoming a zero. Anding the two clears the rightmost 1-bit in m and all the rightmost 1-bits from (m-1). Here's the version of bitcount: /* bitcount: count 1 bits in m */ int bitcount(unsigned m) { int b; for (b = 0; m != 0; m &= (m-1)) b++; return b; } Problem Set 1. In a two's complement number system, x &= (x-1) deletes the rightmost 1-bit in x. Explain why. Use this observation to write a faster version of bitcount. Conditional Expressions The statements if (a > b)
z = a;
else
z = b;
compute in z the maximum of a and b. The conditional expression, written with the ternary operator ``?:'', provides an alternate way to write this and similar constructions. In the expression
expr1 ? expr2 : expr3
the expression expr1 is evaluated first. If it is non-zero (true), then the expression expr2 is evaluated, and that is the value of the conditional expression. Otherwise expr3 is evaluated, and that is the value. Only one of expr2 and expr3 is evaluated.
Thus to set z to the maximum of a and b,
z = (a > b) ? a : b; /* z = max(a, b) */
It should be noted that the conditional expression is indeed an expression, and it can be used wherever any other expression can be. If expr2 and expr3 are of different types, the type of the result is determined by the conversion rules, For example, if f is a float and n an int, then the expression
(n > 0) ? f : n
is of type float regardless of whether n is positive.
Parentheses are not necessary around the first expression of a conditional expression, since the precedence of ?: is very low, just above assignment. They are advisable anyway, however, since they make the condition part of the expression easier to see.
The conditional expression often leads to succinct code. For example, this loop prints n elements of an array, 10 per line, with each column separated by one blank, and with each line (including the last) terminated by a newline.
for (i = 0; i < n; i++) printf("%6d%c", a[i], (i%10==9 || i==n-1) ? '\n' : ' '); A newline is printed after every tenth element, and after the n-th. All other elements are followed by one blank. This might look tricky, but it's more compact than the equivalent if-else. Another good example is printf("You have %d items%s.\n", n, n==1 ? "" : "s"); Worked Out Example 1. write the function upper, which converts lower case letters to upper case, with a conditional expression instead of if-else. int upper(int c); int main(void) { putchar(upper('r')); putchar('\n'); return EXIT_SUCCESS; } /* upper: convert c to upper case; ASCII only */ int upper(int c) { return ('a' <= c && c <= 'z') ? c - 'a' + 'A' : c; } Problem Set 1. Rewrite the function lower, which converts upper case letters to lower case, with a conditional expression instead of if-else. 2. Write a program to count letters, digits in a file Top of Form Hint: For the sample worked out example , pls see the ppt. 3. The statement that tests to see if sum is equal to 10 and total is less than 20, and if so, prints the text string "incorrect.", is Statement 1 if( (sum = 10) && (total < 20) ) printf("incorrect."); Statement 2 if( (sum == 10) && (total < 20) ) printf("incorrect."); Statement 3 if( (sum == 10) || (total < 20) ) printf("incorrect."); 4. If flag is 1 or letter is not an 'X', then assign the value 0 to exit_flag, else set exit_flag to 1. Statement 1 if( (flag = 1) || (letter != 'X') ) exit_flag = 0; else exit_flag = 1; Statement 2 if( (flag == 1) || (letter <> 'X') )
exit_flag = 0;
else
exit_flag = 1;
Statement 3
if( (flag == 1) || (letter != 'X') )
exit_flag = 0;
else
exit_flag = 1;
Precedence and Order of Evaluation
Table 2.1 summarizes the rules for precedence and associativity of all operators, including those that we have not yet discussed. Operators on the same line have the same precedence; rows are in order of decreasing precedence, so, for example, *, /, and % all have the same precedence, which is higher than that of binary + and -. The ``operator'' () refers to function call
Operators Associativity
1
Note that the precedence of the bitwise operators &, ^, and | falls below == and !=. This implies that bittesting expressions like
if ((x & MASK) == 0) ...
must be fully parenthesized to give proper results.
C, like most languages, does not specify the order in which the operands of an operator are evaluated.
(The exceptions are &&, ||, ?:, and `,'.) For example, in a statement like
x = f() + g();
f may be evaluated before g or vice versa; thus if either f or g alters a variable on which the other depends, x can depend on the order of evaluation. Intermediate results can be stored in temporary variables to ensure a particular sequence.
Similarly, the order in which function arguments are evaluated is not specified, so the statement
printf("%d %d\n", ++n, power(2, n)); /* WRONG */
can produce different results with different compilers, depending on whether n is incremented before power is called. The solution, of course, is to write
++n;
printf("%d %d\n", n, power(2, n));
Function calls, nested assignment statements, and increment and decrement operators cause ``side effects'' - some variable is changed as a by-product of the evaluation of an expression. In any expression involving side effects, there can be subtle dependencies on the order in which variables taking part in the
expression are updated. One unhappy situation is typified by the statement
a[i] = i++;
The question is whether the subscript is the old value of i or the new. Compilers can interpret this in different ways, and generate different answers depending on their interpretation. The standard intentionally leaves most such matters unspecified. When side effects (assignment to variables) take place
within an expression is left to the discretion of the compiler, since the best order depends strongly on machine architecture. (The standard does specify that all side effects on arguments take effect before a function is called, but that would not help in the call to printf above.)
The moral is that writing code that depends on order of evaluation is a bad programming practice in any language. Naturally, it is necessary to know what things to avoid, but if you don't know how they are done on various machines, you won't be tempted to take advantage of a particular implementation.
Problem Set
1. main()
{
int i=10;
i=!i>14;
printf("i=%d",i);
}
Answer:
i=0
************************************************************************************************************************************************************************************************
Control Flow Statements
************************************************************************************************
The control-flow of a language specify the order in which computations are performed. We have already met the most common control-flow constructions in earlier examples; here we will complete the set, and be more precise about the ones discussed before.
Statements and Blocks
An expression such as x = 0 or i++ or printf(...) becomes a statement when it is followed by a semicolon, as in
x = 0;
i++;
printf(...);
In C, the semicolon is a statement terminator, rather than a separator as it is in languages like Pascal.
Braces { and } are used to group declarations and statements together into a compound statement, or block, so that they are syntactically equivalent to a single statement. The braces that surround the statements of a function are one obvious example; braces around multiple statements after an if, else, while, or for are another. There is no semicolon after the right brace that ends a block.
If-Else
The if-else statement is used to express decisions. Formally the syntax is
if (expression)
statement1
else
statement2
where the else part is optional. The expression is evaluated; if it is true (that is, if expression has a nonzero value), statement1 is executed. If it is false (expression is zero) and if there is an else part, statement2 is executed instead. Since an if tests the numeric value of an expression, certain coding shortcuts are possible. The most obvious is writing
if (expression)
instead of
if (expression != 0)
Sometimes this is natural and clear; at other times it can be cryptic.
Because the else part of an if-else is optional,there is an ambiguity when an else if omitted from a nested if sequence. This is resolved by associating the else with the closest previous else-less if. For example, in
if (n > 0)
if (a > b)
z = a;
else
z = b;
the else goes to the inner if, as we have shown by indentation. If that isn't what you want, braces must be used to force the proper association:
if (n > 0) {
if (a > b)
z = a;
}
else
z = b;
The ambiguity is especially pernicious in situations like this:
if (n > 0)
for (i = 0; i < n; i++) if (s[i] > 0) {
printf("...");
return i;
}
else /* WRONG */
printf("error -- n is negative\n");
The indentation shows unequivocally what you want, but the compiler doesn't get the message, and associates the else with the inner if. This kind of bug can be hard to find; it's a good idea to use braces when there are nested ifs.
By the way, notice that there is a semicolon after z = a in
if (a > b)
z = a;
else
z = b;
This is because grammatically, a statement follows the if, and an expression statement like ``z = a;'' is always terminated by a semicolon. [Top]
Else-If
The construction
if (expression)
statement
else if (expression)
statement
else if (expression)
statement
else if (expression)
statement
else
statement
occurs so often that it is worth a brief separate discussion. This sequence of if statements is the most general way of writing a multi-way decision. The expressions are evaluated in order; if an expression is true, the statement associated with it is executed, and this terminates the whole chain. As always, the code for each statement is either a single statement, or a group of them in braces.
The last else part handles the ``none of the above'' or default case where none of the other conditions is satisfied. Sometimes there is no explicit action for the default; in that case the trailing
else
statement
can be omitted, or it may be used for error checking to catch an ``impossible'' condition.
To illustrate a three-way decision, here is a binary search function that decides if a particular value x occurs in the sorted array v. The elements of v must be in increasing order. The function returns the position (a number between 0 and n-1) if x occurs in v, and -1 if not.
Binary search first compares the input value x to the middle element of the array v. If x is less than the middle value, searching focuses on the lower half of the table, otherwise on the upper half. In either case, the next step is to compare x to the middle element of the selected half. This process of dividing the range in two continues until the value is found or the range is empty.
/* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] */ int binsearch(int x, int v[], int n) { int low, high, mid; low = 0; high = n - 1; while (low <= high) { mid = (low+high)/2; if (x < v[mid]) high = mid + 1; else if (x > v[mid])
low = mid + 1;
else /* found match */
return mid;
}
return -1; /* no match */
}
The fundamental decision is whether x is less than, greater than, or equal to the middle element v[mid] at each step; this is a natural for else-if.
Additional Problem
1. Our binary search makes two tests inside the loop, when one would suffice (at the price of more tests outside.) Write a version with only one test inside the loop and measure the difference in runtime.
#include
#include
/* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] */ int binsearch(int x, int v[], int n) { int low, high, mid; low = 0; high = n-1; while(low < high) { mid = (low + high) / 2; if(x <= v[mid]) high = mid; else low = mid+1; } return (x == v[low]) ? low : -1; } int main(void) { int v[5] = {3, 6, 9, 12, 4}; int x = 36; printf("%d\n", binsearch(x, v, 5)); return EXIT_SUCCESS; } Switch The switch statement is a multi-way decision that tests whether an expression matches one of a number of constant integer values, and branches accordingly. switch (expression) { case const-expr: statements case const-expr: statements default: statements } Each case is labeled by one or more integer-valued constants or constant expressions. If a case matches the expression value, execution starts at that case. All case expressions must be different. The case labeled default is executed if none of the other cases are satisfied. A default is optional; if it isn't there and if none of the cases match, no action at all takes place. Cases and the default clause can occur in any order. In previous modules, we wrote a program to count the occurrences of each digit, white space, and all other characters, using a sequence of if ... else if ... else. Here is the same program with a switch: #include
main() /* count digits, white space, others */
{
int c, i, nwhite, nother, ndigit[10];
nwhite = nother = 0;
for (i = 0; i < 10; i++) ndigit[i] = 0; while ((c = getchar()) != EOF) { switch (c) { case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': ndigit[c-'0']++; break; case ' ': case '\n': case '\t': nwhite++; break; default: nother++; break; } } printf("digits ="); for (i = 0; i < 10; i++) printf(" %d", ndigit[i]); printf(", white space = %d, other = %d\n", nwhite, nother); return 0; } The break statement causes an immediate exit from the switch. Because cases serve just as labels, after the code for one case is done, execution falls through to the next unless you take explicit action to escape. break and return are the most common ways to leave a switch. A break statement can also be used to force an immediate exit from while, for, and do loops. Falling through cases is a mixed blessing. On the positive side, it allows several cases to be attached to a single action, as with the digits in this example. But it also implies that normally each case must end with a break to prevent falling through to the next. Falling through from one case to another is not robust, being prone to disintegration when the program is modified. With the exception of multiple labels for a single computation, fall-throughs should be used sparingly, and commented. As a matter of good form, put a break after the last case (the default here) even though it's logically unnecessary. Some day when another case gets added at the end, this bit of defensive programming will save you. Additional Problem Write a function escape(s,t) that converts characters like newline and tab into visible escape sequences like \n and \t as it copies the string t to s. Use a switch. Write a function for the other direction as well, converting escape sequences into the real characters. #include
#include
#define TRUE 1
#define FALSE 0
/* escape: converts newlines and tabs into visible escape sequenes as
it copies the string t into s */
void
************************************************************************************************************************************************************************************************
Loops
************************************************************************************************
While and For
We have already encountered the while and for loops. In
while (expression)
statement
the expression is evaluated. If it is non-zero, statement is executed and expression is re-evaluated. This cycle continues until expression becomes zero, at which point execution resumes after statement.
The for statement
for (expr1; expr2; expr3)
statement
is equivalent to
expr1;
while (expr2) {
statement
expr3;
}
except for the behaviour of continue, which is described in later in this module.
Grammatically, the three components of a for loop are expressions. Most commonly, expr1 and expr3 are assignments or function calls and expr2 is a relational expression. Any of the three parts can be omitted, although the semicolons must remain. If expr1 or expr3 is omitted, it is simply dropped from the
expansion. If the test, expr2, is not present, it is taken as permanently true, so
for (;;) {
...
}
is an ``infinite'' loop, presumably to be broken by other means, such as a break or return.
Whether to use while or for is largely a matter of personal preference. For example, in
while ((c = getchar()) == ' ' || c == '\n' || c = '\t')
; /* skip white space characters */
there is no initialization or re-initialization, so the while is most natural.
The for is preferable when there is a simple initialization and increment since it keeps the loop control statements close together and visible at the top of the loop. This is most obvious in
for (i = 0; i < n; i++) ... which is the C idiom for processing the first n elements of an array, the analog of the Fortran DO loop or the Pascal for. The analogy is not perfect, however, since the index variable i retains its value when the loop terminates for any reason. Because the components of the for are arbitrary expressions, for loops are not restricted to arithmetic progressions. Nonetheless, it is bad style to force unrelated computations into the initialization and increment of a for, which are better reserved for loop control operations. As a larger example, here is another version of atoi for converting a string to its numeric equivalent. It copes with optional leading white space and an optional + or - sign. The structure of the program reflects the form of the input: skip white space, if any get sign, if any get integer part and convert it Each step does its part, and leaves things in a clean state for the next. The whole process terminates on the first character that could not be part of a number. #include
/* atoi: convert s to integer; version 2 */
int atoi(char s[])
{
int i, n, sign;
for (i = 0; isspace(s[i]); i++) /* skip white space */
;
sign = (s[i] == '-') ? -1 : 1;
if (s[i] == '+' || s[i] == '-') /* skip sign */
i++;
for (n = 0; isdigit(s[i]); i++)
n = 10 * n + (s[i] - '0');
return sign * n;
}
The standard library provides a more elaborate function strtol for conversion of strings to long integers;
The advantages of keeping loop control centralized are even more obvious when there are several nested loops. The following function is a Shell sort for sorting an array of integers. The basic idea of this sorting algorithm, which was invented in 1959 by D. L. Shell, is that in early stages, far-apart elements are compared, rather than adjacent ones as in simpler interchange sorts. This tends to eliminate large
amounts of disorder quickly, so later stages have less work to do. The interval between compared elements is gradually decreased to one, at which point the sort effectively becomes an adjacent interchange method.
/* shellsort: sort v[0]...v[n-1] into increasing order */
void shellsort(int v[], int n)
{
int gap, i, j, temp;
for (gap = n/2; gap > 0; gap /= 2)
for (i = gap; i < n; i++) for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap) {
temp = v[j];
v[j] = v[j+gap];
v[j+gap] = temp;
}
}
There are three nested loops. The outermost controls the gap between compared elements, shrinking it from n/2 by a factor of two each pass until it becomes zero. The middle loop steps along the elements. The innermost loop compares each pair of elements that is separated by gap and reverses any that are out of order. Since gap is eventually reduced to one, all elements are eventually ordered correctly. Notice how the generality of the for makes the outer loop fit in the same form as the others, even though it is not an arithmetic progression. One final C operator is the comma ``,'', which most often finds use in the for statement. A pair of expressions separated by a comma is evaluated left to right, and the type and value of the result are the type and value of the right operand. Thus in a for statement, it is possible to place multiple expressions in the various parts, for example to process two indices in parallel. This is illustrated in the function reverse(s), which reverses the string s in place.
#include
/* reverse: reverse string s in place */
void reverse(char s[])
{
int c, i, j;
for (i = 0, j = strlen(s)-1; i < j; i++, j--) { c = s[i]; s[i] = s[j]; s[j] = c; } } The commas that separate function arguments, variables in declarations, etc., are not comma operators, and do not guarantee left to right evaluation. Comma operators should be used sparingly. The most suitable uses are for constructs strongly related to each other, as in the for loop in reverse, and in macros where a multistep computation has to be a single expression. A comma expression might also be appropriate for the exchange of elements in reverse, where the exchange can be thought of a single operation: for (i = 0, j = strlen(s)-1; i < j; i++, j--) c = s[i], s[i] = s[j], s[j] = c; [Top] Do-While The third loop in C, the do-while, tests at the bottom after making each pass through the loop body; the body is always executed at least once. The syntax of the do is do statement while (expression); The statement is executed, then expression is evaluated. If it is true, statement is evaluated again, and so on. When the expression becomes false, the loop terminates. Except for the sense of the test, do-while is equivalent to the Pascal repeat-until statement. Experience shows that do-while is much less used than while and for. Nonetheless, from time to time it is valuable, as in the following function itoa, which converts a number to a character string (the inverse of atoi). The job is slightly more complicated than might be thought at first, because the easy methods of generating the digits generate them in the wrong order. We have chosen to generate the string backwards, then reverse it. /* itoa: convert n to characters in s */ void itoa(int n, char s[]) { int i, sign; if ((sign = n) < 0) /* record sign */ n = -n; /* make n positive */ i = 0; do { /* generate digits in reverse order */ s[i++] = n % 10 + '0'; /* get next digit */ } while ((n /= 10) > 0); /* delete it */
if (sign < 0) s[i++] = '-'; s[i] = '\0'; reverse(s); } The do-while is necessary, or at least convenient, since at least one character must be installed in the array s, even if n is zero. We also used braces around the single statement that makes up the body of the do-while, even though they are unnecessary, so the hasty reader will not mistake the while part for the beginning of a while loop. [Top] Break and Continue It is sometimes convenient to be able to exit from a loop other than by testing at the top or bottom. The break statement provides an early exit from for, while, and do, just as from switch. A break causes the innermost enclosing loop or switch to be exited immediately. The following function, trim, removes trailing blanks, tabs and newlines from the end of a string, using a break to exit from a loop when the rightmost non-blank, non-tab, non-newline is found. /* trim: remove trailing blanks, tabs, newlines */ int trim(char s[]) { int n; for (n = strlen(s)-1; n >= 0; n--)
if (s[n] != ' ' && s[n] != '\t' && s[n] != '\n')
break;
s[n+1] = '\0';
return n;
}
strlen returns the length of the string. The for loop starts at the end and scans backwards looking for the first character that is not a blank or tab or newline. The loop is broken when one is found, or when n becomes negative (that is, when the entire string has been scanned). You should verify that this is correct behavior even when the string is empty or contains only white space characters.
The continue statement is related to break, but less often used; it causes the next iteration of the enclosing for, while, or do loop to begin. In the while and do, this means that the test part is executed immediately; in the for, control passes to the increment step. The continue statement applies only to loops, not to switch. A continue inside a switch inside a loop causes the next loop
iteration.
As an example, this fragment processes only the non-negative elements in the array a; negative values are skipped.
for (i = 0; i < n; i++) if (a[i] < 0) /* skip negative elements */ continue; ... /* do positive elements */ The continue statement is often used when the part of the loop that follows is complicated, so that reversing a test and indenting another level would nest the program too deeply. [Top] Goto and labels C provides the infinitely-abusable goto statement, and labels to branch to. Formally, the goto statement is never necessary, and in practice it is almost always easy to write code without it. We have not used goto in this book. Nevertheless, there are a few situations where gotos may find a place. The most common is to abandon processing in some deeply nested structure, such as breaking out of two or more loops at once. The break statement cannot be used directly since it only exits from the innermost loop. Thus: for ( ... ) for ( ... ) { ... if (disaster) goto error; } ... error: /* clean up the mess */ This organization is handy if the error-handling code is non-trivial, and if errors can occur in several places. A label has the same form as a variable name, and is followed by a colon. It can be attached to any statement in the same function as the goto. The scope of a label is the entire function. As another example, consider the problem of determining whether two arrays a and b have an element in common. One possibility is for (i = 0; i < n; i++) for (j = 0; j < m; j++) if (a[i] == b[j]) goto found; /* didn't find any common element */ ... found: /* got one: a[i] == b[j] */ ... Code involving a goto can always be written without one, though perhaps at the price of some repeated tests or an extra variable. For example, the array search becomes found = 0; for (i = 0; i < n && !found; i++) for (j = 0; j < m && !found; j++) if (a[i] == b[j]) found = 1; if (found) /* got one: a[i-1] == b[j-1] */ ... else /* didn't find any common element */ ... With a few exceptions like those cited here, code that relies on goto statements is generally harder to understand and to maintain than code without gotos. Although we are not dogmatic about the matter, it does seem that goto statements should be used rarely, if at all. ************************************************************************************************************************************************************************************************ One Dimensional Arrays ************************************************************************************************ Background Most of the data encountered in everyday life occurs in groups rather than in individual pieces. Data items tend to be collected into conceptual units with names assigned to them. For example, all of the scores made on a test by students in a pds class might be stored in an array, or the names of students in a pds class might be stored in an array. Introduction To understand what an array is, we first review what a variable is. A variable is a symbolic name for a specific location in main memory. For example, the statements: int x; x = 25; First statement instructs the computer to set aside a memory location that will hold an integer, giving the memory location the symbolic name x. The second statement instructs the computer to store the integer 25 in the memory location with the symbolic name x. How can we store twenty integers in memory? We could dream up twenty different symbolic names, such as x1, x2, x3, ..., x20, for twenty places in memory. Obviously, this is not convenient way to represent. C has a data type called an array that addresses this particular problem. An array, then is a group of locations in memory such that a) the locations are usually consecutive, b) all of these locations will contain the same type of data, and c) all of these locations are referenced by the same symbolic name. Arrays are used anytime we wish to store and manipulate more than a few pieces of same data type. Consider the following examples: 1. Suppose that we wish to compute the average pay for 30 people. We do not require an array for this application, since we do not need to remember the data for all 30 people. In this problem we input data for one person and add it to an accumulator. We can use the same variable for the next person, since we no longer need to remember data for the previous person. 2. Suppose we wish to print out 30 scores in reverse order. We need an array for this application because we must remember all 30 numbers in order to print them out in reverse. Array declaration A collection of items can be given one variable name using only one subscript such as variable is called a single subscripted variable or a one-dimensional array . A one-dimensional array is a structured collection of components (often called array elements) that can be accessed individually by specifying the position of a component with a single index value. Here is the syntax template of a one-dimensional array declaration: DataType ArrayName [ConstIntExpression]; In the syntax template, DataType describes what is stored in each component of the array. Array components may be of any type, but for now we limit our discussion to simple data types (e.g. integral and floating types). ConstIntExpression indicates the size of the array declared. That is, it specifies the number of array components in the array. It must have a value greater than 0. If the value is n, the range of the index values is 0 to n-1. For example, the declaration int number[50]; creates the number array, which has 50 components, each capable of holding one int value. In other words, the number array has a total of 50 components, all of type int. Suppose we need an array to store 30 integer scores. We might accomplish this using the following C code: const int MAX_SCORES = 30; int scores[MAX_SCORES]; Note the use of the constant MAX_SCORES for the upper limit on the size of the array. Using a const value to denote the size of the array is not required but is good programming practice. This code causes 30 locations in memory to be set aside under the name scores. scores is the name of the array while int is the data type. This array, scores, can hold up to 30 integer values. It is said to be one-dimensional because it uses only one set of [ ] in its declaration. Accessing an Array Element Ex1: Declare a one-dimensional array that could be used to hold data for the salaries (int type) of 100 employees. In order to store information in an array, one must: 1. Specify the name of the array and 2. Specify exactly which location in the array is to be used to store the information. We specify locations in the array by using an index. For example, reconsider the array scores defined above. The C statement scores[i]=20; means: look at the location designated by i in the array list and store the value 20 in this position. The index can be a constant, variable, or expression as shown below: scores[5] = 100; //index = 5 scores[x] = 80; //index = the value of the variable x scores[3*x] = 75; //index = three times x To determine valid values for the index, reconsider the definition of the array: int scores[MAX_SCORES]; The upper limit of the index is calculated from the value in brackets, namely MAX_SCORES - 1. In C, the lower limit is always 0. Thus the index may vary from 0 to MAX_SCORES - 1. Thus the first memory location assigned to scores is designated by the first index value 0, the second by index value 1, and so on, up to the last one which is designated by the index value MAX_SCORES - 1. If, instead, scores were declared as follows: int scores[MAX_SCORES + 1]; then we could access scores[0], scores[1],..., scores[MAX_SCORES]. Usually a loop of some kind is used when one is working with an array. The following code could be used to read in an array of values from the keyboard. int howMany,i,scores[30]; printf("How many scores?\n"); scanf("%d",&howMany); //now read the scores for (i = 0; i < howMany; i++) { printf("Input scores[%d]: ",i); scanf("%d",&scores[i]); } The following code could be used to print the entire scores array to the screen. //print the scores for (int i = 0; i
#define NUM_STUDENTS 25
#define NUM_TESTS 10
int get_highest(int a[][NUM_TESTS], int row, int col);
int main()
{
int grades[NUM_STUDENTS][NUM_TESTS] = { {55, 60, 65},
{85, 90, 95} };
int num_students = 2;
int num_tests = 3;
int high_test;
high_test = get_highest( grades, num_students, num_tests);
printf("The highest score is %d.\n", high_test);
return 0;
}
int get_highest(int a[][NUM_TESTS], int row, int col)
/* Assumes that there is at least one element */
{
int i, j;
int highest = a[0][0];
for( i = 0; i < row; i++) for( j = 0; j < col; j++) if ( a[i][j] > highest)
highest = a[i][j];
return highest;
}
************************************************************************************************************************************************************************************************
Character Arrays
************************************************************************************************
Introduction:
A string is a sequence of characters. Any sequence or set of characters defined within double quotation symbols is a constant string. In c it is required to do some meaningful operations on strings they are:
· Reading string displaying strings
· Combining or concatenating strings
· Copying one string to another.
· Comparing string & checking whether they are equal
· Extraction of a portion of a string
Strings are stored in memory as ASCII codes of characters that make up the string appended with‘\0’(ASCII value of null). Normally each character is stored in one byte, successive characters are stored in successive bytes.
Character
m
y
A
g
e
i
s
2
\0
ASCII Code
77
121
32
97
103
100
32
105
115
50
0
The last character is the null character having ASCII value zero.
Initializing Strings
Following the discussion on characters arrays, the initialization of a string must the following form which is simpler to one dimension array.
char month1[ ]={‘j’,’a’,’n’,’u’,’a’,’r’,’y’};
Then the string month is initializing to January. This is perfectly valid but C offers a special way to initialize strings. The above string can be initialized char month1[]=”January”; The characters of thestring are enclosed within a part of double quotes. The compiler takes care of string enclosed within a pair of a double quotes. The compiler takes care of storing the ASCII codes of characters of the string in the memory and also stores the null terminator in the end.
/*String.c string variable*/
#include < stdio.h >
main()
{
char month[15];
printf (“Enter the string”);
gets (month);
printf (“The string entered is %s”, month);
}
In this example string is stored in the character variable month the string is displayed in the statement.
printf(“The string entered is %s”, month”);
It is one dimension array. Each character occupies a byte. A null character (\0) that has the ASCII value 0 terminates the string. The figure shows the storage of string January in the memory recall that \0 specifies a single character whose ASCII value is zero.
J
A
N
U
A
R
Y
\0
Character string terminated by a null character ‘\0’.
A string variable is any valid C variable name & is always declared as an array. The general form of declaration of a string variable is
char string_name[size];
The size determines the number of characters in the string name.
Example:
char month[10];
char address[100];
The size of the array should be one byte more than the actual space occupied by the string since the complier appends a null character at the end of the string.
Reading Strings from the terminal:
The function scanf with %s format specification is needed to read the character string from the terminal.
Example:
char address[15];
scanf(“%s”,address);
scanf statement has a draw back it just terminates the statement as soon as it finds a blank space, suppose if we type the string new york then only the string new will be read and since there is a blank space after word “new” it will terminate the string.
Note that we can use the scanf without the ampersand symbol before the variable name.
In many applications it is required to process text by reading an entire line of text from the terminal.
The function getchar can be used repeatedly to read a sequence of successive single characters and store it in the array.
We cannot manipulate strings since C does not provide any operators for string. For instance we cannot assign one string to another directly.
For example:
String=”xyz”;
String1=string2;
Are not valid. To copy the chars in one string to another string we may do so on a character tocharacter basis.
Writing strings to screen:
The printf statement along with format specifier %s to print strings on to the screen. The format %s can be used to display an array of characters that is terminated by the null character for example printf(“%s”,name); can be used to display the entire contents of the array name.
Arithmetic operations on characters:
We can also manipulate the characters as we manipulate numbers in c language. When ever the system encounters the character data it is automatically converted into a integer value by the system. We can represent a character as a interface by using the following method.
X=’a’;
printf(“%d\n”,x);
Will display 97 on the screen. Arithmetic operations can also be performed on characters for example x=’z’-1; is a valid statement. The ASCII value of ‘z’ is 122 the statement the therefore will assign 121 to variable x.
It is also possible to use character constants in relational expressions for example
ch>’a’ && ch < = ’z’ will check whether the character stored in variable ch is a lower case letter. Acharacter digit can also be converted into its equivalent integer value suppose un the expression a=character-‘1’; where a is defined as an integer variable & character contains value 8 then a= ASCII value of 8 ASCII value ‘1’=56-49=7. We can also get the support of the c library function to converts a string of digits into their equivalent integer values the general format of the function in x=atoi(string) here x is an integer variable & string is a character array containing string of digits. String operations (string.h) C language recognizes that string is a different class of array by letting us input and output the array as a unit and are terminated by null character. C library supports a large number of string handling functions that can be used to array out many o f the string manipulations such as: · Length (number of characters in the string). · Concatentation (adding two are more strings) · Comparing two strings. · Substring (Extract substring from a given string) · Copy(copies one string over another) To do all the operations described here it is essential to include string.h library header file in the program. strlen() function: This function counts and returns the number of characters in a string. The length does not include a nullcharacter. syntax n=strlen(string); Where n is integer variable. Which receives the value of length of the string. Example length=strlen(“Hollywood”); The function will assign number of characters 9 in the string to a integer variable length. /c prog. to find the length of the string usingstrlen()function*/ #include
#include
void
main()
{
char name[100];
int length;
printf(“Enter the string”);
gets(name);
length=strlen(name);
printf(“\nNumber of characters in the string is=%d”,length);
}
strcat() function:
when you combine two strings, you add the characters of one string to the end of other string. This process is called concatenation. The strcat() function joins 2 strings together. It takes the following form
strcat(string1,string2)
string1 & string2 are character arrays. When the function strcat is executed string2 is appended to string1. the string at string2 remains unchanged.
Example
strcpy(string1,”sri”);
strcpy(string2,”Bhagavan”);
Printf(“%s”,strcat(string1,string2);
From the above program segment the value of string1 becomes sribhagavan. The string at str2 remains unchanged as bhagawan.
strcmp function:
In c you cannot directly compare the value of 2 strings in a condition like if(string1==string2)
Most libraries however contain the strcmp() function, which returns a zero if 2 strings are equal, or a non zero number if the strings are not the same. The syntax of strcmp() is given below:
Strcmp(string1,string2)
String1 & string2 may be string variables or string constants. String1, & string2 may be string variables or string constants some computers return a negative if the string1 is alphabetically less than the second and a positive number if the string is greater than the second.
Example:
strcmp(“Newyork”,”Newyork”) will return zero because 2 strings are equal.
strcmp(“their”,”there”) will return a 9 which is the numeric difference between ASCII ‘i’ and ASCII ’r’.
strcmp(“The”, “the”) will return 32 which is the numeric difference between ASCII “T” & ASCII “t”.
strcmpi() function
This function is same as strcmp() which compares 2 strings but not case sensitive.
Example
strcmpi(“THE”,”the”); will return 0.
strcpy() function:
C does not allow you to assign the characters to a string directly as in the statement name=”Robert”;
Instead use the strcpy(0 function found in most compilers the syntax of the function is illustrated below.
strcpy(string1,string2);
strcpy function assigns the contents of string2 to string1. string2 may be a character array variable or a string constant.
strcpy(Name,”Robert”);
In the above example Robert is assigned to the string called name.
strlwr () function:
This function converts all characters in a string from uppercase to lowercase.
syntax
strlwr(string);
For example:
strlwr(“EXFORSYS”)converts to exforsys.
strrev() function:
This function reverses the characters in a string.
Syntax
strrev(string);
For ex strrev(“program”) reverses the characters in a string into “margrop”.
strupr() function:
This function converts all characters in a string from lower case to uppercase.
Syntax
strupr(string);
For examplestrupr(“exforsys”) will convert the string to EXFORSYS.
/* C program to use string functions*/
#include < stdio.h >
#include < string.h >
void main()
{
char s1[20],s2[20],s3[20];
int x,l1,l2,l3;
printf(“Enter the strings”);
scanf(“%s%s”,s1,s2);
x=strcmp(s1,s2);
if(x!=0)
{printf(“\nStrings are not equal\n”);
strcat(s1,s2);
}
else
printf(“\nStrings are equal”);
strcpy(s3,s1);
l1=strlen(s1);
l2=strlen(s2);
l3=strlen(s3);
printf(“\ns1=%s\t length=%d characters\n”,s1,l1);
printf(“\ns2=%s\t length=%d characters\n”,s2,l2);
printf(“\ns3=%s\t length=%d characters\n”,s3,l3);
}
/*Another C program to use string functions */
#include
#include
#include
void main()
{
char String1[100],String2[100];
char *String3;
/* Concatenate String2 to the end of String1 */
strcat(String1,String2);
/* Compare String1 and String2 */
strcmp(String1,String2) == 0
/* find first occurence of 'a' in String 1 */
/* Returns char * */
String3 = strchr(String1,'a');
/* Copy String1 to String2 */
strcpy(String2,String1);
/* find the first occurence of a, b or c in String1 and Returns integer position */
strcspn(String1,"abc");
/* Compares String1 and String2 without regard to case */
_stricmp(String1,String2)
/* Find the length of String1 */
strlen(String1);
/* Convert String1 to lower case */
_strlwr(String1);
/* Find the first occurence of a, b, or c in String1 and Returns a char * */
strpbrk(String1,"abc");
/* Finds the last occurence of 'a' in String1 */
strrchr(String1,'a');
/* Reverses String1 */
_strrev(String1)
/* Sets all characters of String1 to 'a' and Length determined by '\0' character */
_strset(String1,'a');
/* Find the first character in String1 that is NOT equal to a, b, or c and Returns an integer */
strspn(String1,"abc");
/* find the first occurence of the string "abc" in String1 and Returns a char * */
strstr(String1,"abc");
/* break String1 apart using spaces for delimiters */
/* see help (or man) for full details. */
strtok(String1," ");
/* Convert String1 to upper case */
_strupr(String1);
/* FIXED LENGTH STRING FUNCTIONS (ignores '\0') and Same as strcat 3-characters copied */
strncat(String2,String1,3);
/* Same as strcmp 4-characters compared */
strncmp(String1,String2,4);
/* Same as strcpy 2-characters copied */
strncpy(String2,String1,2);
/* Same as stricmp, 6-characters compared */
_strnicmp(String1,String2,6);
/* Same as _strset, 8-characters initialized. Stops when '\0' found */
_strnset(String1,'a',8);
}
************************************************************************************************************************************************************************************************
Functions
************************************************************************************************
Introduction
A function is a block of code that has a name and it has a property that it is reusable i.e. it can be executed from as many different points in a C Program as required.
Function groups a number of program statements into a unit and gives it a name. This unit can be invoked from other parts of a program. A computer program cannot handle all the tasks by itself. Instead its requests other program like entities – called functions in C – to get its tasks done. A function is a self contained block of statements that perform a coherent task of same kind
The name of the function is unique in a C Program and is Global. It means that a function can be accessed from any location within a C Program. We pass information to the function called arguments specified when the function is called. And the function either returns some value to the point it was called from or returns nothing.
We can divide a long C program into small blocks which can perform a certain task. A function is a self contained block of statements that perform a coherent task of same kind.
Formal Parameters
Formal parameters are written in the function prototype and function header of the definition. Formal parameters are local variables which are assigned values from the arguments when the function is called.
Actual Parameters or Arguments
When a function is called, the values (expressions) that are passed in the call are called the arguments or actual parameters (both terms mean the same thing). At the time of the call each actual parameter is assigned to the corresponding formal parameter in the function definition.
For value parameters (the default), the value of the actual parameter is assigned to the formal parameter variable. For reference parameters, the memory address of the actual parameter is assigned to the formal parameter
Structure of a Function
There are two main parts of the function. The function header and the function body.
int sum(int x, int y)
{
int ans = 0; //holds the answer that will be returned
ans = x + y; //calculate the sum
return ans //return the answer
}
Function Header
In the first line of the above code
int sum(int x, int y)
It has three main parts
1. The name of the function i.e. sum
2. The parameters of the function enclosed in parenthesis
3. Return value type i.e. int
Function Body
What ever is written with in { } in the above example is the body of the function.
Function Prototypes
The prototype of a function provides the basic information about a function which tells the compiler that the function is used correctly or not. It contains the same information as the function header contains. The prototype of the function in the above example would be like
int sum (int x, int y);
The only difference between the header and the prototype is the semicolon; there must a semicolon at the end of the prototype.
Parameter Passing
The arguments passed to function can be of two types namely
1. Values passed
2. Address passed
The first type refers to call by value and the second type refers to call by reference.
For instance, consider program1
main()
{
int x=50, y=70;
interchange(x,y);
printf(“x=%d y=%d”,x,y);
}
interchange(x1,y1)
int x1,y1;
{
int z1;
z1=x1;
x1=y1;
y1=z1;
printf(“x1=%d y1=%d”,x1,y1);
}
Here the value to function interchange is passed by value.
Consider program2
main()
{
int x=50, y=70;
interchange(&x,&y);
printf(“x=%d y=%d”,x,y);
}
interchange(x1,y1)
int *x1,*y1;
{
int z1;
z1=*x1;
*x1=*y1;
*y1=z1;
printf(“*x=%d *y=%d”,x1,y1);
}
Here the function is called by reference. In other words address is passed by using symbol & and the value is accessed by using symbol *.
The main difference between them can be seen by analyzing the output of program1 and program2.
The output of program1 that is call by value is
x1=70 y1=50
x=50 y=70
But the output of program2 that is call by reference is
*x=70 *y=50
x=70 y=50
This is because in case of call by value the value is passed to function named as interchange and there the value got interchanged and got printed as
x1=70 y1=50
and again since no values are returned back and therefore original values of x and y as in main function namely
x=50 y=70 got printed.
But in case of call by reference address of the variable got passed and therefore what ever changes that happened in function interchange got reflected in the address location and therefore the got reflected in original function call in main also without explicit return value. So value got printed as *x=70 *y=50 and x=70 y=50
Instructions to declare C function:
Create the Function Declaration
1. Create a unique name which says clearly what the function does. Use verbs in the name to emphasize the action. Use a consistent format, such as underscores (e.g., "calculate_subtotal") or inner capitalization (e.g., "CalculateSubtotal"). Avoid names that are too generic. For instance, "calculate_GPA_subtotal" might be better, since different things may be subtotalled.
2. Use functions to return a single value of built-in C datatype (including pointers). Functions that don't return anything will be declared as void.
3. Choose the function's parameters and their types. Pass exactly what the function needs to be do its job, no more and no less. Functions which don't need anything will use void.
4. Realize that most parameters are "passed by value." The function doesn't get the actual variable, only its value, and can change it without affecting the source. If you need to "pass by reference" to allow the function to change the value in the original variable, you must use pointers for the parameters.
5. Declare the function declaration like this:
int calculate_GPA_subtotal(short studenttype, int *scores) { }
The declaration starts with the return type, then its name, then the parameters inside parentheses.
6. Include an abbreviated declaration. At the top of the C program file, or better yet in a header (.h) file, include an abbreviated declaration which omits the body, like this:
int calculate_GPA_subtotal(short studenttype, int *scores);
void reset_printer(void);
Note that you can leave out the parameter names if you like, though it's good form to include them.
Write the Function Body
7. Use {}. Function definitions end with a { which starts the body of the function and continues until the matching }. Use indentation to make the scope clear.
8. Use the return command to return a value. For void functions, use it without a value to jump out of the function from the middle.
************************************************************************************************************************************************************************************************
Recursion
************************************************************************************************
Recursion
Recursion is a powerful principle that allows something to be defined in terms of smaller instances of itself. Perhaps there is no better way to appreciate the significance of recursion than to look at the mysterious ways nature uses it. Think of the fragile leaf of a fern, in which each individual sprig from the leaf's stem is just a smaller copy of the overall leaf; or the repeating patterns in a reflection, in which two shiny objects reflect each other. Examples like these convince us that even though nature is a great force, in many ways it has a paradoxical simplicity that is truly elegant. The same can be said for recursive algorithms; in many ways, recursive algorithms are simple and elegant, yet they can be extremely powerful.
Recursion is a process by which a function calls itself repeatedly, until some specified condition has been satisfied. The process is used for repetitive computations in which each action is stated in terms of a precious result. In order to solve a problem recursively, two conditions must be satisfied. The problem must be written in a recursive form, and the problem statement must include a stopping condition.
In computing, recursion is supported via recursive functions. A recursive function is a function that calls itself. Each successive call works on a more refined set of inputs, bringing us closer and closer to the solution of a problem. Most developers are comfortable with the idea of dividing a larger problem into several smaller ones and writing separate functions to solve them. However, many developers are less comfortable with the idea of solving a larger problem with a single function that calls itself. Admittedly, looking at a problem in this way can take some getting used to. This chapter explores how recursion works and shows how to define some problems in a recursive manner. Some examples of recursive approaches are found in tree traversals breadth-first and depth-first searches with graphs .
Basic recursion
A powerful principle that allows a problem to be defined in terms of smaller and smaller instances of itself. In computing, we solve problems defined recursively by using recursive functions, which are functions that call themselves.
Tail recursion
A form of recursion for which compilers are able to generate optimized code. Most modern compilers recognize tail recursion. Therefore, we should make use of it whenever we can.
Basic Recursion
To begin, let's consider a simple problem that normally we might not think of in a recursive way. Suppose we would like to compute the factorial of a number n. The factorial of n, written n!, is the product of all numbers from n down to 1. For example, 4! = (4)(3)(2)(1). One way to calculate this is to loop through each number and multiply it with the product of all preceding numbers. This is an iterative approach, which can be defined more formally as:
n!=\prod_{k=1}^n k \!
n! = (n)(n - 1)(n - 2) . . . (1)
Another way to look at this problem is to define n! as the product of smaller factorials. To do this, we define n! as n times the factorial of n - 1. Of course, solving (n - 1)! is the same problem as n!, only a little smaller. If we then think of (n - 1)! as n - 1 times (n - 2)!, (n - 2)! as n - 2 times (n - 3)!, and so forth until n = 1, we end up computing n!. This is a recursive approach, which can be defined more formally as:
n! = \begin{cases} 1 & \text{if } n = 0, \\ (n-1)!\times n & \text{if } n > 0. \end{cases}
Figure 18.1 illustrates computing 4! using the recursive approach just described. It also delineates the two basic phases of a recursive process: winding and unwinding. In the winding phase, each recursive call perpetuates the recursion by making an additional recursive call itself. The winding phase terminates when one of the calls reaches a terminating condition. A terminating condition defines the state at which a recursive function should return instead of making another recursive call. For example, in computing the factorial of n, the terminating conditions are n = 1 and n = 0, for which the function simply returns 1. Every recursive function must have at least one terminating condition; otherwise, the winding phase never terminates. Once the winding phase is complete, the process enters the unwinding phase, in which previous instances of the function are revisited in reverse order. This phase continues until the original call returns, at which point the recursive process is complete.
Example 18.1 presents a C function, fact, that accepts a number n and computes its factorial recursively. The function works as follows. If n is less than 0, the function returns 0, indicating an error. If n is or 1, the function returns 1 because 0! and 1! are both defined as 1. These are the terminating conditions. Otherwise, the function returns the result of n times the factorial of n - 1. The factorial of n - 1 is computed recursively by calling fact again, and so forth. Notice the similarities between this implementation and the recursive definition shown earlier.
Example 18.1. Implementation of a Function for Computing Factorials Recursively
/*****************************************************************************
* *
* -------------------------------- fact.c -------------------------------- *
* *
*****************************************************************************/
#include "fact.h"
/*****************************************************************************
* *
* --------------------------------- fact --------------------------------- *
* *
*****************************************************************************/
int fact(int n) {
/*****************************************************************************
* *
* Compute a factorial recursively. *
* *
*****************************************************************************/
if (n < 0) return 0; else if (n == 0) return 1; else if (n == 1) return 1; else return n * fact(n - 1); } To understand how recursion really works, it helps to look at the way functions are executed in C. For this, we need to understand a little about the organization of a C program in memory. Fundamentally, a C program consists of four areas as it executes: a code area, a static data area, a heap, and a stack (see Figure 18.2a). The code area contains the machine instructions that are executed as the program runs. The static data area contains data that persists throughout the life of the program, such as global variables and static local variables. The heap contains dynamically allocated storage, such as memory allocated by malloc. The stack contains information about function calls. By convention, the heap grows upward from one end of a program's memory, while the stack grows downward from the other (but this may vary in practice). When a function is called in a C program, a block of storage is allocated on the stack to keep track of information associated with the call. Each call is referred to as an activation. The block of storage placed on the stack is called an activation record or, alternatively, a stack frame. An activation record consists of five regions: incoming parameters, space for a return value, temporary storage used in evaluating expressions, saved state information for when the activation terminates, and outgoing parameters (see Figure 18.2b). Incoming parameters are the parameters passed into the activation. Outgoing parameters are the parameters passed to functions called within the activation. The outgoing parameters of one activation record become the incoming parameters of the next one placed on the stack. The activation record for a function call remains on the stack until the call terminates. Returning to Example 18.1, consider what happens on the stack as one computes 4!. The initial call to fact results in one activation record being placed on the stack with an incoming parameter of n = 4 (see Figure 18.3, step 1). Since this activation does not meet any of the terminating conditions of the function, fact is recursively called with n set to 3. This places another activation of fact on the stack, but with an incoming parameter of n = 3 (see Figure 18.3, step 2). Here, n = 3 is also an outgoing parameter of the first activation since the first activation invoked the second. The process continues this way until n is 1, at which point a terminating condition is encountered and fact returns 1 (see Figure 18.3, step 4). Once the n = 1 activation terminates, the recursive expression in the n = 2 activation is evaluated as (2)(1) = 2. Thus, the n = 2 activation terminates with a return value of 2 (see Figure 18.3, step 5). Consequently, the recursive expression in the n = 3 activation is evaluated as (3)(2) = 6, and the n = 3 activation returns 6 (see Figure 18.3, step 6). Finally, the recursive expression in the n = 4 activation is evaluated as (4)(6) = 24, and the n = 4 activation terminates with a return value of 24 (see Figure 18.3, step 7). At this point, the function has returned from the original call, and the recursive process is complete. The stack is a great solution to storing information about function calls because its last-in, first-out behaviour is well suited to the order in which functions are called and terminated. However, stack usage does have a few drawbacks. Maintaining information about every function call until it returns takes a considerable amount of space, especially in programs with many recursive calls. In addition, generating and destroying activation records takes time because there is a significant amount of information that must be saved and restored. Thus, if the overhead associated with these concerns becomes too great, we may need to consider an iterative approach. Fortunately, we can use a special type of recursion, called tail recursion, to avoid these concerns in some cases. Tail Recursion A recursive function is said to be tail recursive if all recursive calls within it are tail recursive. A recursive call is tail recursive when it is the last statement that will be executed within the body of a function and its return value is not a part of an expression. Tail-recursive functions are characterized as having nothing to do during the unwinding phase. This characteristic is important because most modern compilers automatically generate code to take advantage of it. When a compiler detects a call that is tail recursive, it overwrites the current activation record instead of pushing a new one onto the stack. The compiler can do this because the recursive call is the last statement to be executed in the current activation; thus, there is nothing left to do in the activation when the call returns. Consequently, there is no reason to keep the current activation around. By replacing the current activation record instead of stacking another one on top of it, stack usage is greatly reduced, which leads to better performance in practice. Thus, we should make recursive functions tail recursive whenever we can. To understand how tail recursion works, let's revisit computing a factorial recursively. First, it is helpful to understand the reason the previous definition was not tail recursive. Recall that the original definition computed n! by multiplying n times (n - 1)! in each activation, repeating this for n = n - 1 until n = 1. This definition was not tail recursive because the return value of each activation depended on multiplying n times the return value of subsequent activations. Therefore, the activation record for each call had to remain on the stack until the return values of subsequent calls were determined. Now consider a tail-recursive definition for computing n!, which can be defined formally as: This definition is similar to the one presented earlier, except that it uses a second parameter, a (initially set to 1), which maintains the value of the factorial computed thus far in the recursive process. This prevents us from having to multiply the return value of each activation by n. Instead, in each recursive call, we let a = na and n = n - 1. We continue this until n = 1, which is the terminating condition, at which point we simply return a. Figure 18.4 illustrates the process of computing 4! using this approach. Notice how there is no work that needs to be performed during the unwinding phase, a signature of all tail-recursive functions. Example 18.2 presents a C function, facttail, that accepts a number n and computes its factorial in a tail-recursive manner. This function also accepts the additional parameter a, which is initially set to 1. The function facttail is similar to fact, except that it uses a to maintain the value of the factorial computed thus far in the recursion. Notice the similarities between this implementation and the tail-recursive definition. Example 18.2. Implementation of a Function for Computing Factorials in a Tail-Recursive Manner /***************************************************************************** * * * ------------------------------ facttail.c ------------------------------ * * * *****************************************************************************/ #include "facttail.h" /***************************************************************************** * * * ------------------------------- facttail ------------------------------- * * * *****************************************************************************/ int facttail(int n, int a) { /***************************************************************************** * * * Compute a factorial in a tail-recursive manner. * * * *****************************************************************************/ if (n < 0) return 0; else if (n == 0) return 1; else if (n == 1) return a; else return facttail(n - 1, n * a); } The function in Example 18.2 is tail recursive because the single recursive call to facttail is the last statement executed before returning from the call. It just happens that this is the last statement of facttail as well, but this does not have to be the case. In other words, there could have been other statements after the recursive call, provided they were executed only when the recursive call was not. Figure 18.5 illustrates the limited activity on the stack while computing 4! using this tail-recursive function. Contrast this with the activity on the stack. ************************************************************************************************************************************************************************************************ Structures ************************************************************************************************ C Structure Introduction We used variable in our C program to store value but one variable can store only single piece information (an integer can hold only one integer value) and to store similar type of values we had to declare many variables. To overcome this problem we used array which can hold numbers of similar data type. But array too have some limitations, like in our real world application we deal with set of dissimilar data types and single array cannot store dissimilar data. For example think about storing book information or product information, a product can have different information to store like product code (an integer), product name (a char array), product price (a float) etc. And to store 20 products information we can declare integer array for product code, 2D character array for storing product name and float array to store product price. This approach definitely achieves your goals, but try to consider these things too. What if you wanted to add more products than 20, what if you want to add more information on products like stock, discount, tax etc? It will become difficult to differentiate these variables with other variables declared for calculation etc. To solve this problem C language has a unique data type called Structure. C structure is nothing but collection of different related data types. If we are using C structure then we are combining different related data types in one group so that we can use and manage those variables easily. Here related data type means, a structure holding information about book will contains variable and array related to book. Syntax for C Structure declaration struct structure_name { data type member1; data type member2; … … }; Example: struct products { char name[20]; int stock; float price; }; So structure declaration begins with struct keyword and with a space we need to provide a structure name. Within open and closed curly braces we can declare required and related variable, you can see it in our example structure declaration. And most important point to remember in case of C structure is that it ends with semicolon (;). Let’s have a complete example of structure in C language. Example of C Structure 1. #include
2. #include
3. struct product
4. {
5. char name[30];
6. int stock;
7. float price, dis;
8. };
9. void main()
10. {
11. struct product p1 ={"Apple iPod Touch 32GB", 35,298.56, 2.32};
12. clrscr(); printf("Name=%s,\nStock=%d,\nPrice=$%.2f,\nDiscount=%.2f%.", p1.name, p1.stock, p1.price,p1.dis);
13. getch();
14. }
http://s1.hubimg.com/u/2762016_f496.jpg
Code Explanation
So line no.4-9 declares a C structure named “product”, this structure contains four variables to store different information about product. In the beginning there is a character array (char name[30]) which stores name of the product, next we have integer variable (int stock) to store stock of product and last two variable are float type (float price, discount) to product price & discount on product respectively.
Here we just declared product structure and now we have to use it in main(). Line no. 14 declares a product type variable p1. Here product type variable means, in our C program product is a structure and to use that structure we need to create its variable. Declaring a product structure variable is simple just use following syntax:
struct structure_name variable_name;
Remember struct is a C keyword, “structure_name” is name of structure you used while declaring a C structure (in above C program its product) and “variable_name” could be any name of your choice (in above C program its p1) but standard naming convention applies.
Along with declaring C structure variable p1 we have also initialized it and to initialize C structure you need to assign values in proper order. Proper order means assign value in the order they are declared in structure. For example, in our product structure we declare variable in following orders:
char name[30];
int stock;
float price, discount;
So for this structure proper order will be:
char name[30];
int stock;
float price;
float discount;
You don’t need to rewrite your structure, you just need to keep it in mind that structure variable initialization should be performed in orderly manner (top – bottom and left – right manner) otherwise it will show error or you may get strange output.
So in above program we have initialized p1 variable in following way:
struct product p1 ={"Apple iPod Touch 32GB", 35, 298.56, 2.32}; means
struct product p1 ={char name[30], int stock, float price, float discount}; //this line of code is only assumption.
Next in line no. 16 we just printed the values stores in product structure. You cannot print values stored in product structure member variable (like name, stock etc.) directly, you have to link member variable with structure variable and you can do this using (.) dot operator. For example: character array name is unknown to main() because it is declared in structure product, so to access member variable we will follow the following syntax:
structure_variable.member_variable;
Example:
p1.name;
We can rewriteprintf("Name=%s,\nStock=%d,\nPrice=$%.2f,\nDiscount=%.2f%.", p1.name, p1.stock, p1.price,p1.discount); in the following manner:
printf(“Name = %s”,p1.name);
printf(“Stock = %d”,p1.stock);
printf(“Price = $%.2f”,p1.price);
printf(“Stock = %.2f”,p1.discount);
Here is full working code sample of C Structure.
1. #include
2. #include
3.
4. struct product
5. {
6. char name[30];
7. int stock;
8. float price, discount;
9. };
10.
11. void main()
12. {
13.
14. struct product p1 ={"Apple iPod Touch 32GB", 35,298.56, 2.32};
15. clrscr();
16. printf("Name = %s\n",p1.name);
17. printf("Stock = %d\n",p1.stock);
18. printf("Price = %.2f\n",p1.price);
19. printf("Discount= %.2f\n",p1.discount);
20. getch();
21. }
Output of the program:
http://s4.hubimg.com/u/2762019_f496.jpg
Arrays of Structures:
Arrays of structures mean collection of structures, in other word array storing different type of structure member variables. Arrays of Structures are one of the interesting topics for C programmer because it has power of two powerful data types; Structure and Array.
Look at following image.
http://s2.hubimg.com/u/2935413_f496.jpg
In above image, cell size does not represent actual byte taken by variables. Same color cells represent structure whereas each cell represents each member variable of structure.
Let's have above example in real code. Below is a product structure containing same member variables as in above example image has.
1. struct product
2. {
3. char name[30];
4. int stock;
5. float price, discount;
6. };
We have now a product structure which consist four member variables name, stock, price and discount. We can now either create structure variables to store 2 or more product information, or we can declare arrays of structures. Look at following program.
1. #include
2. #include
3.
4. struct product
5. {
6. char name[30];
7. int stock;
8. float price, discount;
9. };
10.
11. void main()
12. {
13.
14. struct product p[3];
15. int i;
16. float temp;
17. clrscr();
18.
19. for(i=0;i<3;i++) 20. { 21. printf("Enter product name :"); 22. gets(p[i].name); 23. 24. printf("\nEnter Stock :"); 25. scanf("%d",&p[i].stock); 26. 27. printf("\nEnter Price :"); 28. scanf("%f",&temp); 29. p[i].price = temp; 30. 31. printf("\nEnter Discount :"); 32. scanf("%f",&temp); 33. p[i].discount = temp; 34. 35. printf("\n\n"); 36. fflush(stdin); 37. } 38. 39. clrscr(); 40. for(i=0;i<3;i++) 41. { 42. printf("Name=%s, Stock=%d, Price=$%.2f, Discount=%.2f%.\n", p[i].name, p[i].stock, p[i].price,p[i].discount); 43. } 44. getch(); 45. } Output of above program http://s4.hubimg.com/u/2941175_f496.jpg Code Explanation Once again, above program lets you to store information about 3 different products. Product information contains product name, stock, price and discount on purchase. From line no. 4 – 9 declares product structure. Line no 14 declares an array of structure which can store 3 products you increase or decrease its capacity by replacing 3 by any positive integer. Line no. 13 – 37 accepts data for products from user and stores it to structure. As you can see this block begins with for loop. As I already told you that it’s an array of structure, so to loop through array I have used for loop. This for loop will loop only 3 times as we have declared product structure variable to store 3 products information. If you want to store more product information say 100 products then you must change 3 to 100 on lines 11, 15 & 31. Now carefully understand how to store values in array of structure. http://s4.hubimg.com/u/2941199_f496.jpg As you can see in line no. 14 we declared product structure variable p[3]. This means we have three structures in an array p[0], p[1] and p[2]. Above image represents the same. So to store data in first index of structure variable (i.e. p[0]) we can write following lines: gets(p[0].name); scanf("%d",&p[0].stock); scanf("%f",&p[0].price); scanf("%f",&p[0].discount); Above style for storing data is good for storing information of 1 or2 products but if you have 100s of product then you should use because it is very convenient and if don’t have to write lengthy code to do same job. That’s why to store information of 3 products I used for loop. Now it’s time to display stored data in p structure variable. Here also I have used for loop which loops for 3 times. So to display data in first index of structure variable (i.e. p[0]) we can write following lines: printf("%s”, p[0].name); printf("%d”, p[0].stock); printf("%.2f”, p[0].price); printf("%.2f", p[0].discount); ************************************************************************************************************************************************************************************************ Storage classes ************************************************************************************************ STORAGE CLASSES Every C variable has a storage class and a scope. The storage class determines the part of memory where storage is allocated for an object and how long the storage allocation continues to exist. It also determines the scope which specifies the part of the program over which a variable name is visible, i.e. the variable is accessible by name. There are following storage classes which can be used in a C Program * auto * register * static * extern auto - Storage Class auto is the default storage class for all local variables. { int Count; auto int Month; } The example above defines two variables with the same storage class. auto can only be used within functions, i.e. local variables. register - Storage Class register is used to define local variables that should be stored in a register instead of RAM. This means that the variable has a maximum size equal to the register size (usually one word) and cant have the unary '&' operator applied to it (as it does not have a memory location). { register int Miles; } Register should only be used for variables that require quick access - such as counters. It should also be noted that defining 'register' goes not mean that the variable will be stored in a register. It means that it MIGHT be stored in a register - depending on hardware and implementation restrictions. static - Storage Class static is the default storage class for global variables. The two variables below (count and road) both have a static storage class. static int Count; int Road; { printf("%d\n", Road); } static variables can be 'seen' within all functions in this source file. At link time, the static variables defined here will not be seen by the object modules that are brought in. static can also be defined within a function. If this is done the variable is initialised at run time but is not reinitialized when the function is called. This inside a function static variable retains its value during various calls. void func(void); static count=10; /* Global variable - static is the default */ main() { while (count--) { func(); } } void func( void ) { static i = 5; i++; printf("i is %d and count is %d\n", i, count); } This will produce following result i is 6 and count is 9 i is 7 and count is 8 i is 8 and count is 7 i is 9 and count is 6 i is 10 and count is 5 i is 11 and count is 4 i is 12 and count is 3 i is 13 and count is 2 i is 14 and count is 1 i is 15 and count is 0 NOTE : Here keyword void means function does not return anything and it does not take any parameter. You can memorise void as nothing. static variables are initialized to 0 automatically. Example: main() { value(); value (); value(); getch(); } value() { static int a=5; a=a+2; printf("\n%d",a); } The output of the program is not 7,7,7 but it is, 7,9,11 Definition vs Declaration: Before proceeding, let us understand the difference between definition and declaration of a variable or function. Definition means where a variable or function is defined in reality and actual memory is allocated for variable or function. Declaration means just giving a reference of a variable and function. Through declaration we assure to the complier that this variable or function has been defined somewhere else in the program and will be provided at the time of linking. In the above examples char *func(void) has been put at the top which is a declaration of this function where as this function has been defined below to main() function. There is one more very important use for 'static'. Consider this bit of code. char *func(void); main() { char *Text1; Text1 = func(); } char *func(void) { char Text2[10]="martin"; return(Text2); } Now, 'func' returns a pointer to the memory location where 'text2' starts BUT text2 has a storage class of 'auto' and will disappear when we exit the function and could be overwritten but something else. The answer is to specify static char Text[10]="martin"; The storage assigned to 'text2' will remain reserved for the duration if the program. extern - Storage Class extern is used to give a reference of a global variable that is visible to ALL the program files. When you use 'extern' the variable cannot be initialized as all it does is point the variable name at a storage location that has been previously defined. When you have multiple files and you define a global variable or function which will be used in other files also, then extern will be used in another file to give reference of defined variable or function. Just for understanding extern is used to declare a global variable or function in other files. File 1: main.c int count=5; main() { write_extern(); } File 2: write.c void write_extern(void); extern int count; void write_extern(void) { printf("count is %i\n", count); } Here extern keyword is being used to declare count in another file. Now compile these two files as follows gcc main.c write.c -o write This fill produce write program which can be executed to produce result. Count in 'main.c' will have a value of 5. If main.c changes the value of count - write.c will see the new value In briefly a variable storage class tells us 1. Where the variable would be stored. 2. What will be the initial value of the variable, if the initial value is not specifically assigned (i.e, the default initial value). 3. What is the scope of the variable, i.e., in which functions the value of the variable would be available. 4. What is the life of the variables; i.e., how long would the variable exist. ************************************************************************************************************************************************************************************************ Pointers ************************************************************************************************ Introduction In c, a pointer is a variable that can holds the address of another variable or references a memory location in which data is stored. Each memory cell in the computer has an address that can be used to access that location so a pointer variable points to a memory location we can access and change the contents of this memory location via the pointer. A pointer enables us to access a variable that is designed outside the function. 1. Pointer reduces the length and complexity of a program. 2. Pointers are more efficient in handling the data tables. 3. Pointers increase the execution speed. Advantages of Pointer: 1. Pointers can be used to pass the information back and forth between a function and its reference point, particularly pointer provides a way to return multiple data titem from a function through arguments. 2. Pointers are closely associated with arrays and provide an alternate way to access individual array elements. 3. Pointer provides a convenient way to represent multi dimensional arrays allowing a single multi dimensional array to be replaced by a lower dimensional array of pointers. 4. Pointer permits a collection of strings to be represented within a single array even through the individual strings may differ in length. 5. Pointer reduces the length and complexity of a program. Hence increase the execution speed. Pointer declaration: A pointer is a variable that contains the memory location of another variable. The syntax is as shown below. You start by specifying the type of data stored in the location identified by the pointer. The asterisk tells the compiler that you are creating a pointer variable. Finally you give the name of the variable. Syntax: *
Example:
int *ptr;
float *string;
i.e., declares the variable ‘ptr’ & ‘string’ are as pointer variables, which point to an integer data type & float point data type. The type ‘int’ &’float’ are refers to the data type of a variable.
Address operator:
Once we declare a pointer variable we must point it to something we can do this by assigning to the pointer the address of the variable .The computer’s memory is sequential collection of storage cells and cell is known, as bit has a number called address associated with it. These addresses are starting from ‘0’ and the last address depends on the memory size. Whenever we declare variables the system allocates some location to hold the value of variable in the memory. Suppose ‘num’ is a variable that represents some particular data item and can be accessed if we know the location or address of the data item. The expression ‘&num’ can determine the address of the data item. Where ‘&’ is called as the address operator.
Example:
ptr=#
Address of num à Value ptr
This places the address where num is stores into the variable ‘ptr’. If ‘num’ is stored in memory 21260 address then the variable ‘ptr’ has the value 21260.
/* A program to illustrate pointer declaration*/
main()
{
int *ptr;
int sum;
sum=45;
ptr=∑
printf (“\n Sum is %d\n”, sum);
printf (“\n The sum pointer is %d”, ptr);
}
We will get the same result by assigning the address of num to a regular (non pointer) variable. The benefit is that we can also refer to the pointer variable as ‘*ptr’ the asterisk tells to the computer that we are not interested in the value 21260 but in the value stored in that memory location. While the value of pointer is 21260 the value of ‘sum’ is 45 however we can assign a value to the pointer ‘* ptr’ as in ‘*ptr=45’.
This means place the value 45 in the memory address pointer by the variable ptr. Since the pointer contains the address 21260 the value 45 is placed in that memory location. And since this is the location of the variable num the value also becomes 45. this shows how we can change the value of pointer directly using a pointer and the indirection pointer.
/* Program to display the contents of the variable their address using pointer variable*/
include< stdio.h >
{
int num, *intptr;
float x, *floptr;
char ch, *cptr;
num=123;
x=12.34;
ch=’a’;
intptr=&x;
cptr=&ch;
floptr=&x;
printf(“Num %d stored at address %u\n”,*intptr,intptr);
printf(“Value %f stored at address %u\n”,*floptr,floptr);
printf(“Character %c stored at address %u\n”,*cptr,cptr);
}
Pointer expressions & pointer arithmetic:
Like other variables pointer variables can be used in expressions. For example if p1 and p2 are properly declared and initialized pointers, then the following statements are valid.
y=*p1**p2;
sum=sum+*p1;
z= 5* - *p2/*p1;//equivalent to 5*(-(*p2))/*p1
*p2= *p2 + 10;
C allows us to add integers to or subtract integers from pointers as well as to subtract one pointer from the other.
We can also use short hand operators with the pointers p1++ ; sum+=*p2; etc.,
we can also compare pointers by using relational operators the expressions such as p1 >p2 , p1==p2 and p1!=p2 are allowed.
/*Program to illustrate the pointer expression and pointer arithmetic*/
#include< stdio.h >
main()
{
int ptr1,ptr2;
int a,b,x,y,z;
a=30;b=6;
ptr1=&a;
ptr2=&b;
x=*ptr1+ *ptr2 –6;
y=6*- *ptr1/ *ptr2 +30;
printf(“\nAddress of a +%u”,ptr1);
printf(“\nAddress of b %u”,ptr2);
printf(“\na=%d, b=%d”,a,b);
printf(“\nx=%d,y=%d”,x,y);
ptr1=ptr1 + 70;
ptr2= ptr2;
printf(“\na=%d, b=%d”,a,b);
}
Pointers with function:
The pointers are very much used in a function declaration. Sometimes only with a pointer a complex function can be easily represented and success. The usage of the pointers in a function definition may be classified into two groups.
1. Call by value.
2. Call by reference.
Call by value:
We have seen that a function is invoked there will be a link established between the formal and actual parameters. A temporary storage is created where the value of actual parameters is stored. The formal parameters picks up its value from storage area the mechanism of data transfer between actual and formal parameters allows the actual parameters mechanism of data transfer is referred as call by value. The corresponding formal parameter represents a local variable in the called function. The current value of corresponding actual parameter becomes the initial value of formal parameter. The value of formal parameter may be changed in the body of the actual parameter. The value of formal parameter may be changed in the body of the subprogram by assignment or input statements. This will not change the value of actual parameters.
#include< stdio.h >
void main()
{
int x,y;
x=20;
y=30;
printf(“\n Value of a and b before function call =%d %d”,a,b);
fncn(x,y);
printf(“\n Value of a and b after function call =%d %d”,a,b);
}
fncn(p,q)
int p,q;
{
p=p+p;
q=q+q;
}
Call by Reference:
When we pass address to a function the parameters receiving the address should be pointers. The process of calling a function by using pointers to pass the address of the variable is known as call by reference. The function which is called by reference can change the values of the variable used in the call.
/* example of call by reference*/
#include< stdio.h >
void main()
{
int x,y;
x=20;
y=30;
printf(“\n Value of a and b before function call =%d %d”,a,b);
fncn(&x,&y);
printf(“\n Value of a and b after function call =%d %d”,a,b);
}
fncn(p,q)
int p,q;
{
*p=*p+*p;
*q=*q+*q;
}
Pointers with arrays:
an array is actually very much like pointer. We can declare the arrays first element as a[0] or as int *a because a[0] is an address and *a is also an address the form of declaration is equivalent. The difference is pointer is a variable and can appear on the left of the assignment operator that is l value. The array name is constant and cannot appear as the left side of assignment operator.
/* A program to display the contents of array using pointer*/
main()
{
int a[100];
int i,j,n;
printf(“\nEnter the elements of the array\n”);
scanf(“%d”,&n);
printf(“Enter the array elements”);
for(I=0;I< n;I++) scanf(“%d”,&a[I]); printf(“Array element are”); for(ptr=a,ptr< (a+n);ptr++) printf(“Value of a[%d]=%d stored at address %u”,j+=,*ptr,ptr); } Strings are characters arrays and here last element is \0 arrays and pointers to char arrays can be used to perform a number of string functions. Pointers with structures: We know the name of an array stands for the address of its zeroth element the same concept applies for names of arrays of structures. Suppose item is an array variable of struct type. Consider the following declaration: struct products { char name[30]; int manufac; float net; }; item[2],*ptr; this statement declares item as array of two elements, each type struct products and ptr as a pointer data objects of type struct products, the assignment ptr=item; would assign the address of zeroth element to product[0]. Its members can be accessed by using the following notation. ptr->name;
ptr->manufac;
ptr->net;
The symbol’ - >’ is called arrow pointer and is made up of minus sign and greater than sign. Note that ptr- > is simple another way of writing product[0].
When the pointer is incremented by one it is made to pint to next record ie item[1]. The following statement will print the values of members of all the elements of the product array.
for(ptr=item; ptr
We could also use the notation
(*ptr).number
to access the member number. The parenthesis around ptr are necessary because the member operator ‘.’ Has a higher precedence than the operator *.
Points on pointer:
While pointers provide enormous power and flexibility to the programmers, they may use cause manufactures if it not properly handled. Consider the following precautions using pointers to prevent errors. We should make sure that we know where each pointer is pointing in a program. Here are some general observations and common errors that might be useful to remember.
A pointer contains garbage until it is initialized. Since compilers cannot detect uninitialized or wrongly initialized pointers, the errors may not be known until we execute the program remember that even if we are able to locate a wrong result, it may not provide any evidence for us to suspect problems in the pointers.
The abundance of c operators is another cause of confusion that leads to errors. For example the expressions such as
*ptr++, *p[],(ptr).member
etc should be carefully used. A proper understanding of the precedence and associativity rules should be carefully used.
Pointer Drawbacks
Pointers have tremendous power but the power can swing both sides good and evil. Pointer if used incorrectly leads to very difficult to unearth bugs which will most probably make you go wild. Pointers are itself are not any trouble but the value they are storing can be. If it contains a incorrect value it can lead to disasters of massive magnitude when used.
When you use this incorrect pointer to read a memory location, you may be reading a incorrect garbage value which if unluckily accepted by your program as assumed correct value nothing can help you. Consider a scenario in banking in which any customers real account value is switched with this garbage value, he can become a millionaire or beggar in a second, or think that in a rocket launching software you use this incorrect value as launching angle and crashing the billion dollar masterpiece. These scenarios are just my imagination running wild but you cannot ignore the fact that they are possibility.
Now when you use this incorrect pointer to write a memory location you may be writing a unknown memory location. If you have a large memory in the system maybe you are using a unassigned memory but if that memory by any luck is a memory used by O.S. or Hardware and you are modifying it you maybe corrupting your Operating System software or damaging your hardware and thier drivers. Also it is a possibility that you may be using a memory location already in use by your software storing some essential data and you are unknowingly modifying it. You maybe writing over your own code and data.
Such bugs and errors created by the pointers may not show up immediately but come up later and it is at that time difficult to predict that it was the pointer to blame.
To help you avoid these pointers error, we will be looking at some types of pointers error which are possible and learn how to avoid them by using good programming practices.
Uninitialized Pointers
Carefully look at the c source code below -
#include
int main ()
{
int a, *p;
a = 1;
*p = a;
return 0;
}
Now notice above that pointer p above is pointing to some unknown location. Maybe if you are luckily your compiler or O.S. points it to some safe location but it is just an assumption. It can be pointing to any damn memory location in the system. Now the code above write value 1 into the unknown memory location pointed to by p. There is a large possibility with large program in small environment that p is pointing something vital which is now destroyed. To avoid this error you must use pointer initialization so that pointer is pointing to nothing and compiler issue an error (runtime or compile time) when you use that pointer incorrectly and some damage control can happen.
Code would be
#include
int main ()
{
int a, *p = NULL;
a = 1;
*p = a; //This would generate a run time error always and a compile time error in smart compilers.
return 0;
}
Example Programs:
1. An example program using simple pointers.
#include
main()
{
int balance;
int *address;
int value;
balance = 5000;
address = &balance;
value = *address;
printf("Balance is : %d\n" , value);
}
Another example using pointers.
#include
main()
{
int *p , num;
p = #
*p = 100;
printf("%d\n" , num);
(*p)++;
printf("%d\n" , num);
(*p)--;
printf("%d\n" , num);
}
2. An example program demonstrating pointer Arithmetic.
#include
main()
{
char *c , ch[10];
int *i , j[10];
float *f , g[10];
int x;
c = ch;
i = j;
f = g;
for ( x=0 ; x<10 ; x++ ) printf("%p %p %p\n" , c+x , i+x , f+x); } 3. An example program using pointers and arrays. #include
main()
{
char str[80];
char token[10];
char *p , *q;
printf("Enter a sentence: ");
gets(str);
p = str;
while (*p) {
q = token;
while (*p != ' ' && *p) {
*q = *p;
q++ ; p++;
}
if (*p) p++;
*q = '\0';
printf("%s\n" , token);
}
}
************************************************************************************************************************************************************************************************
Dynamic Allocation
************************************************************************************************
Dynamic memory allocation:
The process of allocating memory at run time is known as dynamic memory allocation. Although c does not inherently have this facility there are four library routines which allow this function.
Many languages permit a programmer to specify an array size at run time. Such languages have the ability to calculate and assign during executions, the memory space required by the variables in the program. But c inherently does not have this facility but supports with memory management functions, which can be used to allocate and free memory during the program execution. The following functions are used in c for purpose of memory management.
Memory allocations process:
According to the conceptual view the program instructions, global variables and static variables are stored in a permanent storage area and local variables are stored in stacks. The memory space that is located between these two regions in available for dynamic allocation during the execution of the program. The free memory region is called the heap. The size of heap keeps changing when program is executed due to creation and death of variables that are local for functions and blocks. Therefore it is possible to encounter memory overflow during dynamic allocation process. In such situations, the memory allocation functions mentioned above will return a null pointer.
Allocating a block of memory:
A block of memory may be allocated using the function malloc. The malloc function reserves a block of memory of specified size and returns a pointer of type void. This means that we can assign it to any type of pointer. It takes the following form:
ptr=(cast-type*)malloc(byte-size);
ptr is a pointer of type cast-type the malloc returns a pointer (of cast type) to an area of memory with size byte-size.
Example:
x=(int*)malloc(100*sizeof(int));
On successful execution of this statement a memory equivalent to 100 times the area of int bytes is reserved and the address of the first byte of memory allocated is assigned to the pointer x of type int.
Allocating multiple blocks of memory:
calloc is another memory allocation function that is normally used to request multiple blocks of storage each of the same size and then sets all bytes to zero. The general form of calloc is:
ptr=(cast-type*) calloc(n,elem-size);
The above statement allocates contiguous space for n blocks each size of elements size bytes. All bytes are initialized to zero and a pointer to the first byte of the allocated region is returned. If there is not enough space a null pointer is returned.
Releasing the used space:
Compile time storage of a variable is allocated and released by the system in accordance with its storage class. With the dynamic runtime allocation, it is our responsibility to release the space when it is not required. The release of storage space becomes important when the storage is limited. When we no longer need the data we stored in a block of memory and we do not intend to use that block for storing any other information, we may release that block of memory for future use, using the free function.
free(ptr);
ptr is a pointer that has been created by using malloc or calloc.
To alter the size of allocated memory:
The memory allocated by using calloc or malloc might be insufficient or excess sometimes in both the situations we can change the memory size already allocated with the help of the function realloc. This process is called reallocation of memory. The general statement of reallocation of memory is :
ptr=realloc(ptr,newsize);
This function allocates new memory space of size newsize to the pointer variable ptr ans returns a pointer to the first byte of the memory block. The allocated new block may be or may not be at the same region.
/*Example program for malloc,reallocation and free*/
#include < stdio.h >
#include < stdlib.h >
#define NULL 0
main()
{
char *buffer;
/*Allocating memory*/
if((buffer=(char *) malloc(10))==NULL)
{
printf(“Malloc failed\n”);
exit(1);
}
printf(“Buffer of size %d created \n,_msize(buffer));
strcpy(buffer,”Bangalore”);
printf(“\nBuffer contains:%s\n”,buffer);
/*Reallocation*/
if((buffer=(char *)realloc(buffer,15))==NULL)
{
printf(“Reallocation failed\n”);
exit(1);
}
printf(“\nBuffer size modified.\n”);
printf(“\nBuffer still contains: %s\n”,buffer);
strcpy(buffer,”Mysore”);
printf(“\nBuffer now contains:%s\n”,buffer);
/*freeing memory*/
free(buffer);
}
Differences between malloc() and calloc() are:
1. malloc() allocates byte of memory, whereas calloc()allocates block of memory.
2. malloc(s); returns a pointer for enough storage for an object of s bytes. calloc(n,s); returns a pointer for enough contiguous storage for n objects, each of s bytes. The storage is all initialized to zeros.
3. Simply, malloc takes a single argument and allocates bytes of memory as per the argument taken during its invocation. Whereas calloc takes two arguments, they are the number of variables to be created and the capacity of each variable (i.e. the bytes per variable).
4. By default, memory allocated by malloc() contains garbage values. Whereas memory allocated by calloc() contains all zeros.
5. Number of arguments differs.
************************************************************************************************************************************************************************************************
Linked Lists
************************************************************************************************
Introduction
When dealing with many problems we need a dynamic list, dynamic in the sense that the size requirement need not be known at compile time. Thus, the list may grow or shrink during runtime. A linked list is a data structure that is used to model such a dynamic list of data items, so the study of the linked lists as one of the data structures is important.
Concept
An array is represented in memory using sequential mapping, which has the property that elements are fixed distance apart. But this has the following disadvantage: It makes insertion or deletion at any arbitrary position in an array a costly operation, because this involves the movement of some of the existing elements.
When we want to represent several lists by using arrays of varying size, either we have to represent each list using a separate array of maximum size or we have to represent each of the lists using one single array. The first one will lead to wastage of storage, and the second will involve a lot of data movement.
So we have to use an alternative representation to overcome these disadvantages. One alternative is a linked representation. In a linked representation, it is not necessary that the elements be at a fixed distance apart. Instead, we can place elements anywhere in memory, but to make it a part of the same list, an element is required to be linked with a previous element of the list. This can be done by storing the address of the next element in the previous element itself. This requires that every element be capable of holding the data as well as the address of the next element. Thus every element must be a structure with a minimum of two fields, one for holding the data value, which we call a data field, and the other for holding the address of the next element, which we call link field.
Therefore, a linked list is a list of elements in which the elements of the list can be placed anywhere in memory, and these elements are linked with each other using an explicit link field, that is, by storing the address of the next element in the link field of the previous element.This type of list is called a linked list since it can be considered as a list whose order is given by links from one item to the next.
Structure
Item
->
Each item has a node consisting two fields one containing the variable and another consisting of address of the next item(i.e., pointer to the next item) in the list. A linked list is therefore a collection of structures ordered by logical links that are stored as the part of data.
Consider the following example to illustrator the concept of linking. Suppose we define a structure as follows
struct linked_list
{
float age;
struct linked_list *next;
}
struct Linked_list node1,node2;
this statement creates space for nodes each containing 2 empty fields
node1
node1.age
node1.next
node2
node2.age
node2.next
The next pointer of node1 can be made to point to the node 2 by the same statement.
node1.next=&node2;
This statement stores the address of node 2 into the field node1.next and this establishes a link between node1 and node2 similarly we can combine the process to create a special pointer value called null that can be stored in the next field of the last node
Program
Here is a program for building and printing the elements of the linked list:
# include
# include
struct node
{
int data;
struct node *link;
};
struct node *insert(struct node *p, int n)
{
struct node *temp;
/* if the existing list is empty then insert a new node as the
starting node */
if(p==NULL)
{
p=(struct node *)malloc(sizeof(struct node)); /* creates new node
data value passes
as parameter */
if(p==NULL)
{
printf("Error\n");
exit(0);
}
p-> data = n;
p-> link = p; /* makes the pointer pointing to itself because it
is a circular list*/
}
else
{
temp = p;
/* traverses the existing list to get the pointer to the last node of
it */
while (temp-> link != p)
temp = temp-> link;
temp-> link = (struct node *)malloc(sizeof(struct node)); /*
creates new node using
data value passes as
parameter and puts its
address in the link field
of last node of the
existing list*/
if(temp -> link == NULL)
{
printf("Error\n");
exit(0);
}
temp = temp-> link;
temp-> data = n;
temp-> link = p;
}
return (p);
}
void printlist ( struct node *p )
{
struct node *temp;
temp = p;
printf("The data values in the list are\n");
if(p!= NULL)
{
do
{
printf("%d\t",temp->data);
temp=temp->link;
} while (temp!= p);
}
else
printf("The list is empty\n");
}
void main()
{
int n;
int x;
struct node *start = NULL ;
printf("Enter the nodes to be created \n");
scanf("%d",&n);
while ( n -- > 0 )
{
printf( "Enter the data values to be placed in a node\n");
scanf("%d",&x);
start = insert ( start, x );
}
printf("The created list is\n");
printlist ( start );
}
Explanation
1. This program uses a strategy of inserting a node in an existing list to get the list created. An insert function is used for this.
2. The insert function takes a pointer to an existing list as the first parameter, and a data value with which the new node is to be created as a second parameter, creates a new node by using the data value, appends it to the end of the list, and returns a pointer to the first node of the list.
3. Initially the list is empty, so the pointer to the starting node is NULL. Therefore, when insert is called first time, the new node created by the insert becomes the start node.
4. Subsequently, the insert traverses the list to get the pointer to the last node of the existing list, and puts the address of the newly created node in the link field of the last node, thereby appending the new node to the existing list.
5. The main function reads the value of the number of nodes in the list. Calls iterate that many times by going in a while loop to create the links with the specified number of nodes.
Points to Remember
1. Linked lists are used when the quantity of data is not known prior to execution.
2. In linked lists, data is stored in the form of nodes and at runtime, memory is allocated for creating nodes.
3. Due to overhead in memory allocation and deallocation, the speed of the program is lower.
4. The data is accessed using the starting pointer of the list.
INSERTING A NODE BY USING RECURSIVE PROGRAMS
A linked list is a recursive data structure. A recursive data structure is a data structure that has the same form regardless of the size of the data. You can easily write recursive programs for such data structures.
Program
# include
# include
struct node
{
int data;
struct node *link;
};
struct node *insert(struct node *p, int n)
{
struct node *temp;
if(p==NULL)
{
p=(struct node *)malloc(sizeof(struct node));
if(p==NULL)
{
printf("Error\n");
exit(0);
}
p-> data = n;
p-> link = NULL;
}
else
p->link = insert(p->link,n);/* the while loop replaced by
recursive call */
return (p);
}
void printlist ( struct node *p )
{
printf("The data values in the list are\n");
while (p!= NULL)
{
printf("%d\t",p-> data);
p = p-> link;
}
}
void main()
{
int n;
int x;
struct node *start = NULL ;
printf("Enter the nodes to be created \n");
scanf("%d",&n);
while ( n- > 0 )
{
printf( "Enter the data values to be placed in a node\n");
scanf("%d",&x);
start = insert ( start, x );
}
printf("The created list is\n");
printlist ( start );
}
Explanation
1. This recursive version also uses a strategy of inserting a node in an existing list to create the list.
2. An insert function is used to create the list. The insert function takes a pointer to an existing list as the first parameter, and a data value with which the new node is to be created as the second parameter. It creates the new node by using the data value, then appends it to the end of the list. It then returns a pointer to the first node of the list.
3. Initially, the list is empty, so the pointer to the starting node is NULL. Therefore, when insert is called the first time, the new node created by the insert function becomes the start node.
4. Subsequently, the insert function traverses the list by recursively calling itself.
5. The recursion terminates when it creates a new node with the supplied data value and appends it to the end of the list.
SORTING AND REVERSING A LINKED LIST
To sort a linked list, first we traverse the list searching for the node with a minimum data value. Then we remove that node and append it to another list which is initially empty. We repeat this process with the remaining list until the list becomes empty, and at the end, we return a pointer to the beginning of the list to which all the nodes are moved, as shown in Figure 20.1.
Click To expand
Figure 20.1: Sorting of a linked list.
To reverse a list, we maintain a pointer each to the previous and the next node, then we make the link field of the current node point to the previous, make the previous equal to the current, and the current equal to the next, as shown in Figure 20.2.
Click To expand
Figure 20.2: A linked list showing the previous, current, and next nodes at some point during reversal process.
Therefore, the code needed to reverse the list is
Prev = NULL;
While (curr != NULL)
{
Next = curr->link;
Curr -> link = prev;
Prev = curr;
Curr = next;
}
Program
# include
# include
struct node
{
int data;
struct node *link;
};
struct node *insert(struct node *p, int n)
{
struct node *temp;
if(p==NULL)
{
p=(struct node *)malloc(sizeof(struct node));
if(p==NULL)
{
printf("Error\n");
exit(0);
}
p-> data = n;
p-> link = NULL;
}
else
{
temp = p;
while (temp-> link!= NULL)
temp = temp-> link;
temp-> link = (struct node *)malloc(sizeof(struct node));
if(temp -> link == NULL)
{
printf("Error\n");
exit(0);
}
temp = temp-> link;
temp-> data = n;
temp-> link = null;
}
return(p);
}
void printlist ( struct node *p )
{
printf("The data values in the list are\n");
while (p!= NULL)
{
printf("%d\t",p-> data);
p = p-> link;
}
}
/* a function to sort reverse list */
struct node *reverse(struct node *p)
{
struct node *prev, *curr;
prev = NULL;
curr = p;
while (curr != NULL)
{
p = p-> link;
curr-> link = prev;
prev = curr;
curr = p;
}
return(prev);
}
/* a function to sort a list */
struct node *sortlist(struct node *p)
{
struct node *temp1,*temp2,*min,*prev,*q;
q = NULL;
while(p != NULL)
{
prev = NULL;
min = temp1 = p;
temp2 = p -> link;
while ( temp2 != NULL )
{
if(min -> data > temp2 -> data)
{
min = temp2;
prev = temp1;
}
temp1 = temp2;
temp2 = temp2-> link;
}
if(prev == NULL)
p = min -> link;
else
prev -> link = min -> link;
min -> link = NULL;
if( q == NULL)
q = min; /* moves the node with lowest data value in the list
pointed to by p to the list
pointed to by q as a first node*/
else
{
temp1 = q;
/* traverses the list pointed to by q to get pointer to its
last node */
while( temp1 -> link != NULL)
temp1 = temp1 -> link;
temp1 -> link = min; /* moves the node with lowest data value
in the list pointed to
by p to the list pointed to by q at the end of list pointed by
q*/
}
}
return (q);
}
void main()
{
int n;
int x;
struct node *start = NULL ;
printf("Enter the nodes to be created \n");
scanf("%d",&n);
while ( n- > 0 )
{
printf( "Enter the data values to be placed in a
node\n");
scanf("%d",&x);
start = insert ( start,x);
}
printf("The created list is\n");
printlist ( start );
start = sortlist(start);
printf("The sorted list is\n");
printlist ( start );
start = reverse(start);
printf("The reversed list is\n");
printlist ( start );
}
************************************************************************************************************************************************************************************************ Doubly Linked List
************************************************************************************************
DOUBLY LINKED LISTS:
Introduction:
The following are problems with singly linked lists:
1. A singly linked list allows traversal of the list in only one direction.
2. Deleting a node from a list requires keeping track of the previous node, that is, the node whose link points to the node to be deleted.
3. If the link in any node gets corrupted, the remaining nodes of the list become unusable.
These problems of singly linked lists can be overcome by adding one more link to each node, which points to the previous node. When such a link is added to every node of a list, the corresponding linked list is called a doubly linked list. Therefore, a doubly linked list is a linked list in which every node contains two links, called left link and right link, respectively. The left link of the node points to the previous node, whereas the right points to the next node. Like a singly linked list, a doubly linked list can also be a chain or it may be circular with or without a header node. If it is a chain, the left link of the first node and the right link of the last node will be NULL, as shown in Figure A.
Figure A: A doubly linked list maintained as chain.
If it is a circular list without a header node, the right link of the last node points to the first node. The left link of the first node points to the last node, as shown in Figure B.
Figure B: A doubly linked list maintained as a circular list.
If it is a circular list with a header node, the left link of the first node and the right link of the last node point to the header node. The right link of the header node points to the first node and the left link of the header node points to the last node of the list, as shown in Figure C.
Figure C: A doubly linked list maintained as a circular list with a header node.
Therefore, the following representation is required to be used for the nodes of a doubly linked list.
struct dnode
{
int data;
struct dnode *left,*right;
};
Program: 1
A program for building and printing the elements of a doubly linked list follows:
# include
# include
struct dnode
{
int data;
struct dnode *left, *right;
};
struct dnode *insert(struct dnode *p, struct dnode **q, int n)
{
struct dnode *temp;
/* if the existing list is empty then insert a new node as the
starting node */
if(p==NULL)
{
p=(struct dnode *)malloc(sizeof(struct dnode)); /* creates new
node data value
passed as parameter */
if(p==NULL)
{
printf("Error\n");
exit(0);
}
p->data = n;
p-> left = p->right =NULL;
*q =p;
}
else
{
temp = (struct dnode *)malloc(sizeof(struct dnode)); /* creates
new node using
data value passed as
parameter and puts its
address in the temp
*/
if(temp == NULL)
{
printf("Error\n");
exit(0);
}
temp->data = n;
temp->left = (*q);
temp->right = NULL;
(*q)->right = temp;
(*q) = temp;
}
return (p);
}
void printfor( struct dnode *p )
{
printf("The data values in the list in the forward order are:\n");
while (p!= NULL)
{
printf("%d\t",p-> data);
p = p->right;
}
}
void printrev( struct dnode *p )
{
printf("The data values in the list in the reverse order are:\n");
while (p!= NULL)
{
printf("%d\t",p->data);
p = p->left;
}
}
void main()
{
int n;
int x;
struct dnode *start = NULL ;
struct dnode *end = NULL;
printf("Enter the nodes to be created \n");
scanf("%d",&n);
while ( n-- > 0 )
{
printf( "Enter the data values to be placed in a node\n");
scanf("%d",&x);
start = insert ( start, &end,x );
}
printf("The created list is\n");
printfor ( start );
printrev(end);
}
Explanation:
1. This program uses a strategy of inserting a node in an existing list to create it. For this, an insert function is used. The insert function takes a pointer to an existing list as the first parameter.
2. The pointer to the last node of a list is the second parameter. A data value with which the new node is to be created is the third parameter. This creates a new node using the data value, appends it to the end of the list, and returns a pointer to the first node of the list. Initially, the list is empty, so the pointer to the start node is NULL. When insert is called the first time, the new node created by the insert becomes the start node.
3. Subsequently, insert creates a new node that stores the pointer to the created node in a temporary pointer. Then the left link of the node pointed to by the temporary pointer becomes the last node of the existing list, and the right link points to NULL. After that, it updates the value of the end pointer to make it point to this newly appended node.
4. The main function reads the value of the number of nodes in the list, and calls insert that many times by going in a while loop, in order to get a doubly linked list with the specified number of nodes created. [Top]
INSERTION OF A NODE IN A DOUBLY LINKED LIST
Introduction:
The following program inserts the data in a doubly linked list.
Program: 2
# include
# include
struct dnode
{
int data;
struct node *left, *right;
};
struct dnode *insert(struct dnode *p, struct dnode **q, int n)
{
struct dnode *temp;
/* if the existing list is empty then insert a new node as the
starting node */
if(p==NULL)
{
p=(struct dnode *)malloc(sizeof(struct dnode)); /* creates new
node data value
passed as parameter */
if(p==NULL)
{
printf("Error\n");
exit(0);
}
p-> data = n;
p-> left = p->right =NULL;
*q =p
}
else
{
temp = (struct dnode *)malloc(sizeof(struct dnode)); /* creates
new node using
data value passed as
parameter and puts its
address in the temp
*/
if(temp == NULL)
{
printf("Error\n");
exit(0);
}
temp-> data = n;
temp->left = (*q);
temp->right = NULL;
(*q) = temp;
}
return (p);
}
void printfor( struct dnode *p )
{
printf("The data values in the list in the forward order are:\n");
while (p!= NULL)
{
printf("%d\t",p-> data);
p = p-> right;
}
}
/* A function to count the number of nodes in a doubly linked list */
int nodecount (struct dnode *p )
{
int count=0;
while (p != NULL)
{
count ++;
p = p->right;
}
return(count);
}
/* a function which inserts a newly created node after the specified
node in a doubly
linked list */
struct node * newinsert ( struct dnode *p, int node_no, int value )
{
struct dnode *temp, * temp1;
int i;
if ( node_no <= 0 || node_no > nodecount (p))
{
printf("Error! the specified node does not exist\n");
exit(0);
}
if ( node_no == 0)
{
temp = ( struct dnode * )malloc ( sizeof ( struct dnode ));
if ( temp == NULL )
{
printf( " Cannot allocate \n");
exit (0);
}
temp -> data = value;
temp -> right = p;
temp->left = NULL
p = temp ;
}
else
{
temp = p ;
i = 1;
while ( i < node_no ) { i = i+1; temp = temp-> right ;
}
temp1 = ( struct dnode * )malloc ( sizeof(struct dnode));
if ( temp == NULL )
{
printf("Cannot allocate \n");
exit(0);
}
temp1 -> data = value ;
temp1 -> right = temp -> right;
temp1 -> left = temp;
temp1->right->left = temp1;
temp1->left->right = temp1
}
return (p);
}
void main()
{
int n;
int x;
struct dnode *start = NULL ;
struct dnode *end = NULL;
printf("Enter the nodes to be created \n");
scanf("%d",&n);
while ( n- > 0 )
{
printf( "Enter the data values to be placed in a node\n");
scanf("%d",&x);
start = insert ( start, &end,x );
}
printf("The created list is\n");
printfor ( start );
printf("enter the node number after which the new node is to be
inserted\n");
scanf("%d",&n);
printf("enter the data value to be placed in the new node\n");
scanf("%d",&x);
start=newinsert(start,n,x);
printfor(start);
}
Explanation:
1. To insert a new node in a doubly linked chain, it is required to obtain a pointer to the node in the existing list after which a new node is to be inserted.
2. To obtain this pointer, the node number after which the new node is to be inserted is given as input. The nodes are assumed to be numbered as 1,2,3,…, etc., starting from the first node.
3. The list is then traversed starting from the start node to obtain the pointer to the specified node. Let this pointer be x. A new node is then created with the required data value, and the right link of this node is made to point to the node to the right of the node pointed to by x. And the left link of the newly created node is made to point to the node pointed to by x. The left link of the node which was to the right of the node pointed to by x is made to point to the newly created node. The right link of the node pointed to by x is made to point to the newly created node.. [Top]
DELETING A NODE FROM A DOUBLY LINKED LIST
Introduction:
The following program deletes a specific node from the linked list.
Program: 3
# include
# include
struct dnode
{
int data;
struct dnode *left, *right;
};
struct dnode *insert(struct dnode *p, struct dnode **q, int n)
{
struct dnode *temp;
/* if the existing list is empty then insert a new node as the
starting node */
if(p==NULL)
{
p=(struct dnode *)malloc(sizeof(struct dnode)); /* creates new node
data value
passed as parameter */
if(p==NULL)
{
printf("Error\n");
exit(0);
}
p-> data = n;
p-> left = p->right =NULL;
*q =p;
}
else
{
temp = (struct dnode *)malloc(sizeof(struct dnode)); /* creates
new node using
data value passed as
parameter and puts its
address in the temp
*/
if(temp == NULL)
{
printf("Error\n");
exit(0);
}
temp-> data = n;
temp->left = (*q);
temp->right = NULL;
(*q)->right = temp;
(*q) = temp;
}
return (p);
}
void printfor( struct dnode *p )
{
printf("The data values in the list in the forward order are:\n");
while (p!= NULL)
{
printf("%d\t",p-> data);
p = p-> right;
}
}
/* A function to count the number of nodes in a doubly linked list */
int nodecount (struct dnode *p )
{
int count=0;
while (p != NULL)
{
count ++;
p = p->right;
}
return(count);
}
/* a function which inserts a newly created node after the specified
node in a doubly
linked list */
struct dnode * delete( struct dnode *p, int node_no, int *val)
{
struct dnode *temp ,*prev=NULL;
int i;
if ( node_no <= 0 || node_no > nodecount (p))
{
printf("Error! the specified node does not exist\n");
exit(0);
}
if ( node_no == 0)
{
temp = p;
p = temp->right;
p->left = NULL;
*val = temp->data;
return(p);
}
else
{
temp = p ;
i = 1;
while ( i < node_no ) { i = i+1; prev = temp; temp = temp-> right ;
}
prev->right = temp->right;
if(temp->right != NULL)
temp->right->left = prev;
*val = temp->data;
free(temp);
}
return (p);
}
void main()
{
int n;
int x;
struct dnode *start = NULL ;
struct dnode *end = NULL;
printf("Enter the nodes to be created \n");
scanf("%d",&n);
while ( n-- > 0 )
{
printf( "Enter the data values to be placed in a node\n");
scanf("%d",&x);
start = insert ( start, &end,x );
}
printf("The created list is\n");
printfor ( start );
printf("enter the number of the node which is to be deleted\n");
scanf("%d",&n);
start=delete(start,n,&x);
printf("The data value of the node deleted from list is :
%d\n",x);
printf("The list after deletion of the specified node is :\n");
printfor(start);
}
Explanation:
1. To delete a node from a doubly linked chain, it is required to obtain a pointer to the node in the existing list that appears to the left of the node which is to be deleted.
2. To obtain this pointer, the node number which is to be deleted is given as input. The nodes are assumed to be numbered 1,2,3,…, etc., starting from the first node.
3. The list is then traversed starting from the start node to obtain the pointer to the specified node. Let this pointer be x. A pointer to the node to the right of the node x is also obtained. Let this be pointer y (this is a pointer to the node to be deleted). The right link of the node pointed to by x is the node pointing to the node to which the right link of the node pointed to by y points. The left link of the node to the right of the node pointed to by y is made to point to x. The node pointed to by y is then freed. [Top]
APPLICATION OF DOUBLY LINKED LISTS TO MEMORY MANAGEMENT
Introduction:
A doubly linked list is used to maintain both the list of allocated blocks and the list of free blocks by the memory manager of the operating system. To keep track of the allocated and free portions of memory, the memory manager is required to maintain a linked list of allocated and free segments. Each node of this list contains a starting address, size, and status of the segment. This list is kept sorted by the starting address field to facilitate the updating, because when a process terminates, the memory segment allocated to it becomes free, and so if any of the segments are freed, then they can be merged with the adjacent segment, if the adjacent segment is already free. This requires traversal of the list both ways to find out whether any of the adjacent segments are free. So this list is required to be maintained as a doubly linked list. For example, at a particular point in time, the list may be as shown in Figure 20.21.
Figure 20.21: Before termination of process p1.
If the process p1 terminates, it is required to be modified as shown in Figure 20.22.
Figure 20.22: After termination of process p1.
General Comments on Linked Lists:
1. A linked list is a dynamic data structure that can grow and shrink based on need.
2. The elements are not necessarily at a fixed distance apart.
3. In a linked list, the elements are placed in non-contiguous blocks of memory, and each block is linked to its previous block.
4. To link the next element to the previous element, the address of the next element is stored in the previous element itself.
5. Insertion or deletion at any arbitrary position in the linked list can be done easily, since it requires adjustment of only a few pointers.
6. Linked lists can be used for manipulation of symbolic polynomials.
7. A linked list is suitable for representation of sparse matrices.
8. A circular list is a list in which the link field of the last node is made to point to the start/first node of the list
9. A doubly linked list (DLL) is a linked list in which every node contains two links, called the left link and right link, respectively.
10. The left link of the node in a DLL is made to point to the previous node, whereas the right link is made to point to the next node.
11. A DLL can be traversed in both directions.
12. Having two pointers in a DLL provides safety, because even if one of the pointers get corrupted, the node still remains linked.
13. Deleting a particular node from a list, therefore, does not require keeping track of the previous node in a DLL.
Exercises(Additional Programs):
1. Write a C program to delete a node with the minimum value from a singly linked list.
2. Write a C program that will remove a specified node from a given doubly linked list and insert it at the end of the list.
3. Write a C program to transform a circular list into a chain.
4. Write a C program to merge two given lists A and B to form C in the following manner:
The first element of C is the first element of A and the second element of C is the first element of B. The second elements of A and B become the third and fourth elements of C, and so on. If either A or B gets exhausted, the remaining elements of the other are to be copied to C.
5. Write a C program to delete all occurrences of x from a given singly linked list.
************************************************************************************************************************************************************************************************
