Programming in C 2e (Dey, Pradip Ghosh, Manas) (Z-Library)

📄 File Format: PDF

💾 File Size: 12.5 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

Programming in   C  Second Edition          Pradip Dey   Manas Ghosh                        OXFORD  UNIVERSITY PRESS 

📄 Page 2

© Oxford University Press 2011  ISBN: 978-0-198065-28-9

📄 Page 3

Since the evolution of computers, a variety of program- ming languages have come into existence. C stands out among general-purpose programming languages for its unrivaled mix of portability, fl exibility, and ef- fi ciency. It is a versatile language and is commonly used for developing application and system programs. C has block structures, stand-alone functions, a compact set of keywords, and very few restrictions. For all these rea- sons, learning and using C is a necessity for most pro- grammers. ABOUT THE BOOK This book is intended for an introductory course on pro- gramming in C. It assumes no prior programming expe- rience in C or any other language. Readers will fi nd the explanations lucid and effective. Every feature of C has been demonstrated with appropriate programs tested and run on a computer. The output obtained after executing these programs have also been included. The explana- tions have been depicted with suitable diagrams to convey the concepts more effectively. Readers will be profi cient at programming after solving the review questions and programming exercises given at the end of each chapter. Though every attempt has been made to avoid and check errors, we will be grateful to readers if they can bring to our notice any errors that may have crept in inadver- tently. CONTENT AND STRUCTURE Chapter 1 begins by explaining the concept of program- ming. It discusses the techniques of forming an organized approach to problem solving. It also identifi es the differ- ent types of programs and the various categories of pro- gramming languages available. The prescribed tools that are used in this process are described and explained with suffi cient examples and diagrams. For a beginner, Chapter 2 is undoubtedly the most im- portant chapter that describes the basic elements of C. This chapter introduces the keywords, the basic data types and their modifi ers, operators and their precedence, and ex- pressions and data type conversion rules. The basic struc- ture of a C program along with the common commands used in MS-DOS and UNIX/Linux for compiling and running it has been described at length in this chapter. Accepting data from and conveying the results to a user is one of the most important actions desired from a pro- gram. To satisfy these requirements through the console, there are some commonly used input and output func- tions in C. These have been explained with illustrations in Chapter 3. Program fl ow control and looping constructs in C are ex- plained in Chapter 4. The general statement format with fl ow- charts and examples illustrate their signifi cance in programs. Arrays and strings are two important data structures for handling a cluster of homogeneous data. How such clus- C Preface to the First Edition

📄 Page 4

ters are declared and handled is explained with ample ex- amples in Chapter 5. The concept of functions, its form, and its requirement in a program is discussed in Chapter 6 with well-explained examples. Recursive functions are also described with several examples. Analysis of time and space complexity for an algorithm has also been presented in this chapter. One of the most important features of C is pointers. Starting with an introduction to pointers, Chapter 7 also elaborates on how pointers are used with arrays, strings, and functions. The use of pointers is also described in depth with innumerable examples. User-defi ned data types such as structures and unions are described in Chapter 8. What these data types com- prise and how these are handled and used are illustrated with examples. Creating, amending, appending, and many other opera- tions on fi les in C is a necessity for storing and retrieving data and programs. This has been covered in Chapter 9 with suffi cient examples. Linked list, which is a popular data structure, has been covered in Chapter 10. Various types of linked lists and the different operations that can be carried out on such linked lists have been discussed. In this chapter, readers will also get to know how pointers are used in constructing this data structure. Chapter 11 highlights some of the advanced features of C such as command-line arguments, bit-wise operators, different memory models, and type qualifi ers with several illustrations. Frequently asked questions are always a source of learning. Some frequently asked questions have been in- cluded at end of the book, which will help readers to clear any doubts pertaining to programming in C. The appendices contain case studies where the problem is fi rst defi ned and then the algorithm is developed, based on which the C program is coded. Some sample runs ob- tained during the execution of these programs have also been included. It also contains tables for ASCII codes, num- ber system conversions, escape sequences, operators, data types and data conversion rules, commonly used conver- sion characters, and format tags. Among many other useful topics covered in the appendices, an exhaustive listing of C library functions, with programs illustrating how these functions can be put to use, have also been presented. ACKNOWLEDGEMENTS We thank our students Rakesh Dutta and Niloy Debnath for verifying the programs in this book and Sonia Khed- wal, Priyanka Nawalkar, Sayantani Saha, and Debolina Sharangi for their assistance in the preparation of the model questions. We are grateful to the staff of Oxford University Press for their continuous cooperation, interest, and assistance extended to us during the preparation of the book. We are also thankful to our colleague Mr Manash Sinharoy for helping us in preparing the manuscript in time and Mr Tapas Kumar Tunga and Mr P.N. Pathak for their assistance in the preparation of the manuscript. Special thanks are due to Mr Steve Summit for his ar- ticles on C, which have guided us in preparing some of the topics in this book. We also wish to thank Mr Vijay Kumar R Zanvar and Mr Jayasima Ananth for the article on point- ers and arrays as also Mr Thomas Jenkins for the article on recursion, both of which have served as a guide during the development of this manuscript. We express our gratitude to Mr Peter Burden, Mr Mike Banahan, Mr Declan Brady, and Mr Mark Doran for their articles on C. PRADIP DEY MANAS GHOSH vi Preface to the First Edition

📄 Page 5

Evolution of ideas is a never-ending process. New tech- nology and changing needs have a tremendous infl uence on computing requirements, which in turn lead to continu- ous enhancements of the power and scope of a program- ming language. C99 is the modern standard of the C programming lan- guage. It extends the previous version (C90) with new lan- guage and library features, and helps programmers make bet- ter use of available computer hardware and compiler technol- ogy. The new features include inline functions, several new data types, and new header fi les. Hence, with the new fea- tures suggested by the C99 committee, the C programming language has expanded its scope and range of applications. Accordingly, this edition offers several new topics, features based on the recommendations proposed by C99 committee in relevant chapters, and many other useful fea- tures. A special effort has been made to simplify the exist- ing text with better treatment and explain the concepts with the help of examples containing appropriate comments. Further, the inclusion of key terms with brief defi nitions, FAQs with answers, and case studies demonstrating the stepwise approach of solving practical problems will aid the reader to grasp the essence of the concepts and under- stand their practical implementation. NEW TO THE SECOND EDITION ∑ C99 features highlighted wherever relevant in the text ∑ New chapter on Stacks, Queues, and Trees ∑ Chapter-end case studies ∑ Points to Note, Key Terms with defi nitions, Frequently Asked Questions, and Project Questions with each chapter ∑ Improved explanations of algorithms and codes, and new in-text examples ∑ Incremental problem running through Ch 3 to 9, illustrating program code building from basics ∑ New sections such as variable length arrays, searching and sorting algorithms, pointer and const qualifi er, and applications of linked lists ∑ Includes a CD that contains all the example programs, incremental problems, and case studies in a user- friendly format. EXTENDED CHAPTER MATERIAL Chapter 1: Introduction to Programming: Algorithms and Flowcharts Includes new sections on ∑ Correctness and termination of algorithms ∑ Subroutines ∑ Strategy for designing algorithms ∑ Tracing an algorithm to depict logic ∑ Specifi cation for converting algorithms into programs C Preface to the Second Edition

📄 Page 6

Chapter 2: Basics of C Includes new sections on ∑ Compilation model of a C program ∑ Philosophy of main() function ∑ The concept of Type qualifi ers ∑ How integers are stored in memory? Chapter 4: Control Statements Contains new sections on different forms of loop and mov- ing out from a nested loop. Chapter 6: Functions Includes new sections on ∑ Scope, storage class, and linkages ∑ inline function ∑ Different sorting and searching methods along with the analysis of time and space complexity Chapter 7: Pointers Includes new sections on ∑ Pointer and const qualifi er ∑ Constant parameter ∑ Returning pointer from a function Chapter 10: Linked Lists New discussions on the stringizing operator, token pasting operator, and the optional third command line argument of main() function have been included in this chapter. Chapter 12: Stacks, Queues, and Trees It is a new chapter in this edition. This chapter explains the implementation of stacks and queues using arrays and linked lists as well as the applications of these two data structures. It also explains binary trees, their traversal, types, and applications. ACKNOWLEDGEMENTS We are grateful to a host of readers, who have encouraged us in improving this book by their useful suggestions from time to time. There are no words to express our gratitude to Oxford University Press for their continuous support, suggestions, and assistance while preparing this edition. Despite our best endeavour to make this edition error free, some may have crept in inadvertently. Comments and sugges- tions for the improvement of the book are welcome. Please send them to the publisher by logging on to their website www. oup.com or to the authors at pdey.mghosh@gmail.com. PRADIP DEY MANAS GHOSH iv Preface to the Second Edition

📄 Page 7

Preface to the Second Edition .................................................................................................................... iii Preface to the First Edition ..........................................................................................................................v 1. Introduction to Programming, Algorithms and Flowcharts ..............................................................1 2. Basics of C ......................................................................................................................................39 3. Input and Output ..............................................................................................................................94 4. Control Statements .........................................................................................................................117 5. Arrays and Strings ..........................................................................................................................169 6. Functions ........................................................................................................................................214 7. Pointers in C ...................................................................................................................................268 8. User-defi ned Data Types and Variables .........................................................................................350 9. Files in C ........................................................................................................................................388 10. Linked Lists ...................................................................................................................................423 11. Advanced C ....................................................................................................................................460 12. Stacks, Queues, and Trees ..............................................................................................................492 Appendices ...............................................................................................................................................524 Bibliography and References ...................................................................................................................544 Index ........................................................................................................................................................545 C Brief Contents

📄 Page 8

1 INTRODUCTION TO PROGRAMMING, ALGORITHMS AND FLOWCHARTS 1 1.1 Programs and Programming 1 System Software 2 Application Software 2 1.2 Programming Languages 2 System Programming Languages 3 Application Programming Languages 3 Low-level Languages 3 High-level Languages 5 1.3 Compiler, Interpreter, Loader, and Linker 6 Compiling and Executing High-level Language Programs 6 Linker 7 Loader 7 Linking Loader and Linkage Editor 8 1.4 Program Execution 8 1.5 Fourth Generation Languages 9 1.6 Fifth Generation Languages 10 1.7 Classifi cation of Programming 10 Procedural Languages 10 Problem-oriented Languages 11 Non-procedural Languages 11 1.8 Structured Programming Concept 11 Top–down Analysis 12 Preface to the Second Edition iii Preface to the First Edition v Modular Programming 12 Structured Code 13 The Process of Programming 13 1.9 Algorithms 14 What is an Algorithm? 14 Different Ways of Stating Algorithms 14 Key Features of an Algorithm and the Step- form 14 What are Variables? 16 Subroutines 17 Strategy for Designing Algorithms 30 Tracing an Algorithm to Depict Logic 31 Specifi cation for Converting Algorithms into Programs 32 2 BASICS OF C 39 2.1 Introduction 39 Why Learn C? 40 The Future of C 40 2.2 Standardizations of C Language 40 2.3 Developing Programs In C 41 2.4 A Simple C Program 45 2.5 Parts of C Program Revisited 47 2.6 Structure of a C Program 48 2.7 Concept of a Variable 49 C Contents

📄 Page 9

x Contents 2.8 Data Types in C 50 2.9 Program Statement 55 2.10 Declaration 56 2.11 How Does The Computer Store Data in Memory? 57 How Integers are Stored? 57 How Floats and Doubles are Stored? 58 2.12 Token 60 Identifi er 60 Keywords 61 Constant 61 Assignment 63 Initialization 64 2.13 Operators and Expressions 65 Arithmetic Operators in C 66 Relational Operators in C 71 Logical Operators in C 71 Bitwise Operators in C 72 Conditional Operator in C 73 Comma Operator 73 Sizeof Operator 74 Expression Evaluation—Precedence and Associativity 74 2.14 Expressions Revisited 77 2.15 Lvalues and Rvalues 77 2.16 Type Conversion in C 78 Type Conversion in Expressions 78 Conversion by Assignment 79 Casting Arithmetic Expressions 81 2.17 Working with Complex Numbers 86 3 INPUT AND OUTPUT 94 3.1 Introduction 94 3.2 Basic Screen and Keyboard I/O in C 95 3.3 Non-Formatted Input and Output 96 Single Character Input and Output 96 Single Character Input 96 Single Character Output 96 Additional Single Character Input and Output Functions 97 3.4 Formatted Input and Output Functions 100 Output Function printf ( ) 100 Input Function scanf ( ) 106 4 CONTROL STATEMENTS 117 4.1 Introduction 117 4.2 Specifying Test Condition Forselection and Iteration 119 4.3 Writing Test Expression 119 Understanding How True and False is Represented in C 120 4.4 Conditional Execution and Selection 124 Selection Statements 124 The Conditional Operator 131 The Switch Statement 133 4.5 Iteration and Repetitive Execution 137 While Construct 138 For Construct 143 do-while Construct 151 4.6 Which Loop Should be Used? 153 Using Sentinel Values 153 Using Prime Read 154 Using Counter 155 4.7 Goto Statement 155 4.8 Special Control Statements 156 4.9 Nested Loops 159 5 ARRAYS AND STRINGS 169 5.1 Introduction 169 5.2 One-Dimensional Array 170 Declaration of a One-dimensional Array 171 Initializing Integer Arrays 173 Accessing Array Elements 173 Other Allowed Operations 174 Internal Representation of Arrays in C 176 Variable Length Arrays and the C99 changes 177 Working with One-dimensional Array 177 5.3 Strings: One-dimensional Character Arrays 182 Declaration of a String 182 String Initialization 182 Printing Strings 183 String Input 184 Character Manipulation in the String 190 String Manipulation 191 5.4 Multidimensional Arrays 199 Declaration of a Two-dimensional Array 199 Declaration of a Three-dimensional Array 199 Initialization of a Multidimensional Array 199 Unsized Array Initializations 201 Accessing Multidimensional Arrays 201 Working with Two-dimensional Arrays 202 5.5 Arrays of Strings: Two-dimensional Character Array 206 Initialization 206 Manipulating String Arrays 206

📄 Page 10

Contents xi 6 FUNCTIONS 214 6.1 Introduction 214 6.2 Concept of Function 215 Why are Functions Needed? 215 6.3 Using Functions 216 Function Prototype Declaration 216 Function Defi nition 217 Function Calling 219 6.4 Call by Value Mechanism 221 6.5 Working with Functions 221 6.6 Passing Arrays to Functions 224 6.7 Scope and Extent 227 Concept of Global and Local Variables 227 Scope Rules 229 6.8 Storage Classes 231 Storage Class Specifi ers for Variables 231 Storage Class Specifi ers for Functions 234 Linkage 234 6.9 The Inline Function 234 6.10 Recursion 235 What is Needed for Implementing Recursion? 235 How is Recursion Implemented? 239 Comparing Recursion and Iteration 241 6.11 Searching and Sorting 241 Searching Algorithms 241 Sorting Algorithms 243 6.12 Analysis of Algorithms 248 Asymptotic Notation 250 Effi ciency of Linear Search 252 Binary Search Analysis 253 Analysis of Bubble Sort 254 Analysis of Quick Sort 255 Disadvantages of Complexity Analysis 255 7 POINTERS IN C 268 7.1 Introduction 268 7.2 Understanding Memory Addresses 269 7.3 Address Operator (&) 271 7.4 Pointer 272 Declaring a Pointer 272 Initializing Pointers 274 Indirection Operator and Dereferencing 276 7.5 Void Pointer 278 7.6 Null Pointer 278 7.7 Use of Pointers 279 7.8 Arrays and Pointers 282 One-dimensional Arrays and Pointers 282 Passing an Array to a Function 285 Differences Between Array Name and Pointer 286 7.9 Pointers and Strings 288 7.10 Pointer Arithmetic 289 Assignment 290 Addition or Subtraction with Integers 291 Subtraction of Pointers 298 Comparing Pointers 299 7.11 Pointers to Pointers 300 7.12 Array of Pointers 302 7.13 Pointers To an Array 306 7.14 Two-dimensional Arrays and Pointers 307 Passing Two-dimensional Array to a Function 309 7.15 Three-dimensional Arrays 316 7.16 Pointers to Functions 317 Declaration of a Pointer to a Function 317 Initialization of Function Pointers 317 Calling a Function using a Function Pointer 317 Passing a Function to another Function 318 How to Return a Function Pointer 319 Arrays of Function Pointers 320 7.17 Dynamic Memory Allocation 320 Dynamic Allocation of Arrays 323 Freeing Memory 325 Reallocating Memory Blocks 327 Implementing Multidimensional Arraysusing Pointers 328 7.18 Offsetting a Pointer 331 7.19 Memory Leak and Memory Corruption 333 7.20 Pointer and Const Qualifi er 334 Pointer to Constant 334 Constant Pointers 335 Constant Parameters 335 8 USER-DEFINED DATA TYPES AND VARIABLES 350 8.1 Introduction 350 8.2 Structures 351 Declaring Structures and Structure Variables 351 Accessing the Members of a Structure 354 Initialization of Structures 355 Copying and Comparing Structures 359 Typedef and its Use in Structure Declarations 361 Nesting of Structures 362 Arrays of Structures 363 Initializing Arrays of Structures 364 Arrays within the Structure 365 Structures and Pointers 365 Structures and Functions 367 8.3 Union 370 Declaring a Union and its Members 370

📄 Page 11

xii Contents Accessing and Initializing the Members of a Union 371 Structure Versus Union 372 8.4 Enumeration Types 373 8.5 Bitfi elds 374 9 FILES IN C 388 9.1 Introduction 388 9.2 Using Files in C 390 Declaration of File Pointer 390 Opening a File 391 Closing and Flushing Files 392 9.3 Working with Text Files 393 Character Input and Output 393 End of File (EOF) 394 Detecting the End of a File Using the feof() Function 400 9.4 Working with Binary Files 401 9.5 Direct File Input and Output 402 Sequential Versus Random File Access 403 9.6 Files of Records 403 Working with Files of Records 403 9.7 Random Access to Files of Records 410 9.8 Other File Management Functions 413 Deleting a File 413 Renaming a File 413 9.9 Low-Level I/O 414 10 LINKED LISTS 423 10.1 Introduction 423 10.2 Singly Linked List 425 Insertion of a Node in a Singly Linked List 430 Deletion of a Node from a Singly Linked List 434 Sorting a Singly Linked List 435 Destroying a Singly Linked List 436 More Complex Operations on Singly Linked Lists 437 10.3 Circular Linked Lists 440 Appending a Node 441 Displaying a Circular Linked List 442 Inserting a Node After a Specifi ed Node 442 Inserting a Node Before a Particular Node 443 Deleting a Node 444 Sorting a Circular Linked List 446 10.4 Doubly Linked List 446 Operations on Doubly Linked List 447 Advantages/Disadvantages of DoublyLinked Lists 450 10.5 Introduction to Circular Doubly Linked List 450 10.6 Applications of Linked Lists 451 Dynamic Storage Management 451 Garbage Collection and Compaction 452 10.7 Disadvantages of Linked Lists 454 10.8 Array Versus Linked List Revisited 454 11 ADVANCED C 460 11.1 Introduction 460 11.2 Bitwise Operator 461 Bitwise and 462 Bitwise or 463 Bitwise Exclusive-OR 464 Bitwise Not 464 Bitwise Shift Operator 465 11.3 Command-Line Arguments 467 11.4 The C Preprocessor 470 The C Preprocessor Directives 470 Predefi ned Identifi ers 474 11.5 Type Qualifi er 475 Const Qualifi er 476 Volatile Qualifi er 478 Restrict Qualifi er 479 11.6 Variable Length Argument List 480 11.7 Memory Models and Pointers 481 12 STACKS, QUEUES, AND TREES 492 12.1 Introduction 492 12.2 Stack 493 Implementation of Stack 493 Application of Stack 498 12.3 Queue 499 Implementation of Queue 499 Other Variations of Queue 505 Applications of Queue 505 12.4 Tree 506 Some Basic Tree Terminology 507 Binary Tree 507 Traversals of a Binary Tree 509 Kinds of Binary Trees 511 Binary Search Tree 511 Application of Tree 518 Appendices 524 Bibliography and References 544 Index 545

📄 Page 12

1.1 PROGRAMS AND PROGRAMMING A computer can neither think nor make a decision on its own. In fact, it is not possible for any computer to independently analyze a given data and fi nd a solution on its own. It needs a program which will convey what is to be done. A program is a set of logically related instructions that is arranged in a sequence that directs the computer in solving a problem. The process of writing a program is called programming. It is a necessary and critical step in data processing. An incorrect program delivers results that cannot be used. There are two ways by which one can acquire a program—either purchase an existing program, referred to as packaged software or prepare a new program from scratch, in which case it is called customized software. Computer software can be broadly classifi ed into two categories: system software and application software. After reading this chapter, the readers will be able to defi ne program and programming identify system programs and application programs get a basic concept of high-, middle-, and low-level languages briefl y understand compiler, interpreter, linker, and loader functions understand algorithms and the key features of an algorithm—sequence, decision, and repetition learn the different ways of stating algorithms—step-form, fl owchart, etc. defi ne variables, types of variables, and naming conventions for variables decide a strategy for designing algorithms Learning Objectives C Chapter Introduction to Programming, Algorithms and Flowcharts 1

📄 Page 13

2 Programming in C Computer Software System Software Application Software Figure 1.1 Computer software classifi cation 1.1.1 System Software System software is a collection of programs that interfaces with the hardware. Some common categories of system software are described as follows. Language translator It is a system software that transforms a computer program written by a user into a form that can be understood by the machine. Operating system (OS) This is the most important system software that is required to operate a computer system. An operating system manages the computer’s resources effectively, takes care of scheduling multiple jobs for execution, and manages the fl ow of data and instructions between the input/output units and the main memory. An operating system has become a part of computer software with the advent of the third generation computers. Since then a number of operating systems have been developed and some have undergone several revisions and modifi cations to achieve better utilization of computer resources. Advances in computer hardware have helped in the development of more effi cient operating systems. System Software Language Translator Operating System Utilities Special Purpose Program Figure 1.2 Categories of system software 1.1.2 Application Software Application software is written to enable the computer to solve a specifi c data processing task. There are two categories of application software: pre-written software packages and user application programs. A number of powerful application software packages that do not require signifi cant programming knowledge have been developed. These are easy to learn and use compared to programming languages. Although these packages can perform many general and special functions, there are applications where these packages are found to be inadequate. In such cases, user application programs are written to meet the exact requirements. A user application program may be written using one of these packages or a programming language. The most important categories of software packages available are ∑ Database management software ∑ Spreadsheet software ∑ Word processing, Desktop Publishing (DTP), and presentation software ∑ Multimedia software ∑ Data communication software ∑ Statistical and operational research software Application Software Pre-written Software Packages User-written Application Programs Figure 1.3 Categories of application software Points to Note 1. A program is a sequence of logically related instructions and the process of making it is programming. 2. A program is a software that is broadly categorized as system software and application software. 1.2 PROGRAMMING LANGUAGES To write a computer program, a standard programming language is used. A programming language is composed of a set of instructions in a language understandable to the programmer and recognizable by a computer. Programming languages can be classifi ed as high-level, middle-level, and low-level. High-level languages such as BASIC, COBOL (Common Business Oriented Programming Language), and FORTRAN (Formula Translation Language) are used

📄 Page 14

Introduction to Programming, Algorithms and Flowcharts 3 to write application programs. A middle-level language such as C is used for writing application and system programs. A low-level language such as the assembly language is mostly used to write system programs. Low-level programming languages were the fi rst category of programming languages to evolve. Gradually, high-level and middle-level programming languages were developed and put to use. Figure 1.4 depicts the growth in computer languages since the 1940s. The fi gure is meant to give some idea of the times that the different generations appeared, time scales, and relativity of computer languages to each other and the world of problem solving. Human Oriented Machine Oriented Problem definition Fourth Generation Language Third Generation Language Assembly Language Machine Code 1940 1950 1960 1970 1980 1990 Years Figure 1.4 Growth of computer languages 1.2.1 System Programming Languages System programs or softwares are designed to make the computer easier to use. An example of system software is an operating system consisting of many other programs that control input/output devices, memory, processor, schedule the execution of multiple tasks, etc. To write an operating system program, the programmer needs instructions to control the computer’s circuitry as well as manage the resources of the computer. For example, instructions that move data from one location of storage to a register of the processor are required. Assembly language, which has a one-to-one correspondence with machine code, was the normal choice for writing system programs like operating systems. But, today C is widely used to develop system software. 1.2.2 Application Programming Languages There are two main categories of application programs: business programs and scientifi c application programs. Application programs are designed for specifi c computer applications, such as payroll processing and inventory control. To write programs for payroll processing or other such applications, the programmer does not need to control the basic circuitry of a computer. Instead, the programmer needs instructions that make it easy to input data, produce output, perform calculations, and store and retrieve data. Programming languages suitable for such application programs have the appropriate instructions. Most programming languages are designed to be good for one category of applications but not necessarily for the other, although there are some general-purpose languages that support both types. Business applications are characterized by processing of large inputs and high-volume data storage and retrieval but call for simple calculations. Languages which are suitable for business program development must support high-volume input, output, and storage but do not need to support complex calculations. On the other hand, programming languages designed for writing scientifi c programs contain very powerful instructions for calculations but have poor instructions for input, output, etc. Among the traditionally used programming languages, COBOL is more suitable for business applications whereas FORTRAN is more suitable for scientifi c applications. 1.2.3 Low-level Languages A low-level computer programming language is one that is closer to the native language of the computer, which is 1’s and 0’s. Machine language This is a sequence of instructions written in the form of binary numbers consisting of 1’s and 0’s to which the computer responds directly. The machine language is also referred to as the machine code, although the term is used more broadly to refer to any program text. A machine language instruction generally has three parts as shown in Fig. 1.5. The fi rst part is the command or operation code that conveys to the computer what function

📄 Page 15

4 Programming in C has to be performed by the instruction. All computers have operation codes for functions such as adding, subtracting and moving. The second part of the instruction either specifi es that the operand contains data on which the operation has to be performed or it specifi es that the operand contains a location, the contents of which have to be subjected to the operation. n-bits q-bits Operation Code Mode Operand p-bits r-bits Figure 1.5 General format of machine language instruction Just as hardware is classifi ed into generations based on technology, computer languages also have a generation classifi cation based on the level of interaction with the machine. Machine language is considered to be the fi rst generation language (1GL). Advantage of machine language The CPU directly understands machine instructions, and hence no translation is required. Therefore, the computer directly starts executing the machine language instructions, and it takes less execution time. Disadvantages of machine language ∑ Diffi cult to use It is diffi cult to understand and de- velop a program using machine language. For any- body checking such a program, it would be diffi cult to forecast the output when it is executed. Neverthe- less, computer hardware recognizes only this type of instruction code. ∑ Machine dependent The programmer has to re- member machine characteristics while preparing a program. As the internal design of the computer is different across types, which in turn is determined by the actual design or construction of the ALU, CU, and size of the word length of the memory unit, the ma- chine language also varies from one type of computer to another. Hence, it is important to note that after be- coming profi cient in the machine code of a particular computer, the programmer may be required to learn a new machine code and would have to write all the existing programs again in case the computer system is changed. ∑ Error prone It is hard to understand and remember the various combinations of 1’s and 0’s representing data and instructions. This makes it diffi cult for a programmer to concentrate fully on the logic of the problem, thus frequently causing errors. ∑ Diffi cult to debug and modify Checking machine instructions to locate errors are about as tedious as writing the instructions. Further, modifying such a program is highly problematic. Following is an example of a machine language program for adding two numbers. Example 1. Machine Code Comments 0011 1100 Load A register with value 7 0000 0111 0000 0110 Load B register with 10 0000 1010 1000 0000 A = A + B 0011 1010 Store the result into the memory location whose address is 100 (decimal) 0110 0110 0111 0110 Halt processing Assembly language When symbols such as letters, digits, or special characters are employed for the operation, operand, and other parts of the instruction code, the representation is called an assembly language instruction. Such representations are known as mnemonic codes; they are used instead of binary codes. A program written with mnemonic codes forms an assembly language program. This is considered to be a second generation language (2GL). Machine and assembly languages are referred to as low-level languages since the coding for a problem is at the individual instruction level. Each computer has its own assembly language that is dependent upon the internal architecture of the processor.

📄 Page 16

Introduction to Programming, Algorithms and Flowcharts 5 An assembler is a translator that takes input in the form of the assembly language program and produces machine language code as its output. An instruction word consists of parts shown in Fig. 1.5 where, ∑ the Opcode (Operation Code) part indicates the operation to be performed by the instruction and ∑ the mode and operand parts convey the address of the data to be found or stored. The following is an example of an assembly language program for adding two numbers X and Y and storing the result in some memory location. Example 2. Mnemonics Comments Register/ Location LD A, 7 Load register A with 7 A 7 LD B, 10 Load register B with 10 B 10 ADD A, B A + B: Add contents of A 17 A with contents of B and store result in register A LD (100), A Save the result in the main memory location 100 100 17 HALT Halt process From this example program, it is clear that using mnemonics such as LD, ADD, and HALT, the readability of the program has improved signifi cantly. An assembly language program cannot be executed by a machine directly as it is not in a binary machine language form. An assembler is needed to translate an assembly language program into the object code, which can then be executed by the machine. The object code is the machine language code. This is illustrated in Fig. 1.6. Assembly Language Program Source Code Object Code Assembler Object Code in Machine Language Figure 1.6 Assembler Advantage of assembly language Writing a program in assembly language is more convenient than writing one in machine language. Instead of binary sequence, as in machine language, a program in assembly language is written in the form of symbolic instructions. This gives the assembly language program improved readability. Disadvantages of assembly language ∑ Assembly language is specifi c to a particular machine architecture, i.e., machine dependent. Assembly languages are designed for a specifi c make and model of a microprocessor. This means that assembly language programs written for one processor will not work on a different processor if it is architecturally different. That is why an assembly language program is not portable. ∑ Programming is diffi cult and time consuming. ∑ The programmer should know all about the logical structure of the computer. 1.2.4 High-level Languages High-level programming languages such as COBOL, FORTRAN, and BASIC were mentioned earlier in the chapter. Such languages have instructions that are similar to human languages and have a set grammar that makes it easy for a programmer to write programs and identify and correct errors in them. To illustrate this point, a program written in BASIC, to obtain the sum of two numbers, is shown below. Example 3. Stmt. No. Program stmnt Comments 10 LET X = 7 Put 7 into X 20 LET Y = 10 Put 10 into Y 30 LET SUM = X + Y Add values in X and Y and put in SUM. 40 PRINT SUM Output the content in SUM. 50 END Stop The time and cost of creating machine and assembly language programs were quite high. This motivated the development of high-level languages. Advantages of high-level programming languages Readability Programs written in these languages are more readable than those written in assembly and machine languages.

📄 Page 17

6 Programming in C Portability High-level programming languages can be run on different machines with little or no change. It is, therefore, possible to exchange software, leading to creation of program libraries. Easy debugging Errors can be easily detected and removed. Ease in the development of software Since the commands of these programming languages are closer to the English language, software can be developed with ease. High-level languages are also called third generation languages (3GLs). Points to Note 1. There are two kinds of programming languages --- the low-level and high level. 2. The high level programming language is easy to read, portable, allows swift development of programs and is easy to debug. 3. The low level programming language is not portable, takes more time to develop programs and debugging is diffi cult. 1.3 COMPILER, INTERPRETER, LOADER, AND LINKER For executing a program written in a high-level language, it must be fi rst translated into a form the machine can understand. This is done by a software called the compiler. The compiler takes the high-level language program as input and produces the machine language code as output for the machine to execute the program . This is illustrated in Fig. 1.7. Source Program in High Level Compiler Object Code in Machine Language Figure 1.7 Compiler action During the process of translation, the compiler reads the source program statement- wise and checks for syntax errors. In case of any error, the computer generates a printout of the same. This action is known as diagnostics. There is another type of software that also does translation. This is called an interpreter. The compiler and interpreter have different approaches to translation. Table 1.1 lists the differences between a compiler and an interpreter. Table 1.1 Differences between a compiler and an Interpreter Compiler Interpreter Scans the entire program before translating it into machine code. Translates and executes the program line by line. Converts the entire program to machine code and executes program only when all the syntax errors are removed. The interpreter executes one line at a time, after checking and correcting its syntax errors and then converting it to machine code. Slow in debugging or removal of mistakes from a program. Good for fast debugging. Program execution time is less. Program execution time is more. 1.3.1 Compiling and Executing High-level Language Programs The compiling process consists of two steps: the analysis of the source program and the synthesis of the object program in the machine language of the specifi ed machine. The analysis phase uses the precise description of the source programming language. A source language is described using lexical rules, syntax rules, and semantic rules. Lexical rules specify the valid syntactic elements or words of the language. Syntax rules specify the way in which valid syntactic elements are combined to form the statements of the language. Syntax rules are often described using a notation known as BNF (Backus Naur Form) grammar. Semantic rules assign meanings to valid statements of the language. The steps in the process of translating a source program in a high-level language to executable code are depicted in Fig. 1.8. The fi rst block is the lexical analyzer. It takes successive lines of a program and breaks them into individual lexical items namely, identifi er, operator delimiter, etc. and attaches a type tag to each of these. Beside this, it constructs a symbol table for each identifi er and fi nds the internal representation of each constant. The symbol table is used later to allocate memory to each variable.

📄 Page 18

Introduction to Programming, Algorithms and Flowcharts 7 Lexical Rules Syntax Rules Semantic Rules Object Code Object Code from Other Compilations Intermediate Code Source Program Lexical Analysis Syntactic Analysis Semantic Analysis Code Generator Symbol Table Other Tables Linker and Loader Executable Code Figure 1.8 The process of compilation The second stage of translation is called syntax analysis or parsing. In this phase, expressions, declarations, and other statements are identifi ed by using the results of lexical analysis. Syntax analysis is done by using techniques based on formal grammar of the programming language. In the semantic analysis phase, the syntactic units recognized by the syntax analyzer are processed. An intermediate representation of the fi nal machine language code is produced. The last phase of translation is code generation, when optimization to reduce the length of machine language program is carried out. The output of the code generator is a machine level language program for the specifi ed computer. If a subprogram library is used or if some subroutines are separately translated and compiled, a fi nal linking and loading step is needed to produce the complete machine language program in an executable form. If subroutines were compiled separately, then the address allocation of the resulting machine language instructions would not be fi nal. When all routines are connected and placed together in the main memory, suitable memory addresses are allocated. The linker’s job is to fi nd the correct main memory locations of the fi nal executable program. The loader then places the executable program in memory at its correct address. Therefore, the execution of a program written in high- level language involves the following steps: 1. Translation of the program resulting in the object program. 2. Linking of the translated program with other object programs needed for execution, thereby resulting in a binary program. 3. Relocation of the program to execute from the specifi c memory area allocated to it. 4. Loading of the program in the memory for the purpose of execution. 1.3.2 Linker Linking resolves symbolic references between object programs. It makes object programs known to each other. The features of a programming language infl uence the linking requirements of a program. In FORTRAN/COBOL, all program units are translated separately. Hence, all subprogram calls and common variable references require linking. PASCAL procedures are typically nested inside the main program. Hence, procedure references do not require linking; they can be handled through relocation. References to built-in functions however require linking. In C, fi les are translated separately. Thus, only function calls that cross fi le boundaries and references to global data require linking. Linking makes the addresses of programs known to each other so that transfer of control from one subprogram to another or a main program takes place during execution. Relocation Relocation means adjustment of all address-dependent locations, such as address constant, to correspond to the allocated space, which means simple modifi cation of the object program so that it can be loaded at an address different from the location originally specifi ed. Relocation is more than simply moving a program from one area to another in the main memory. It refers to the adjustment of address fi elds. The task of relocation is to add some constant value to each relative address in the memory segment. 1.3.3 Loader Loading means physically placing the machine instructions and data into main memory, also known as primary storage area.

📄 Page 19

8 Programming in C A loader is a system program that accepts object programs and prepares them for execution and initiates the execution (see Fig. 1.9). The functions performed by the loader are : ∑ Assignment of load-time storage area to the program ∑ Loading of program into assigned area ∑ Relocation of program to execute properly from its load time storage area ∑ Linking of programs with one another Source Program Data Result Translator Linker Loader Binary Program Data Flow Control Flow Object Module Binary Program Figure 1.9 A schematic of program execution Thus, a loader is a program that places a program’s instructions and data into primary storage locations. An absolute loader places these items into the precise locations indicated in the machine language program. A relocating loader may load a program at various places in primary storage depending on the availability of primary storage area at the time of loading. A program may be relocated dynamically with the help of a relocating register. The base address of the program in primary storage is placed in the relocating register. The contents of the relocation register are added to each address developed by a running program. The user is able to execute the program as if it begins at location zero. At execution time, as the program runs, all address references involve the relocation register. This allows the program to reside in memory locations other than those for which it was translated to occupy. 1.3.4 Linking Loader and Linkage Editor User programs often contain only a small portion of the instructions and data needed to solve a given problem. Large subroutine libraries are provided so that a programmer wanting to perform certain common operations may use system-supplied routines to do so. Input/output, in particular, is normally handled by routines outside the user program. Hence, the machine language program produced by the translator must normally be combined with other machine language programs residing within the library to form a useful execution unit. This process of program combination is called linking and the software that performs this operation is variously known as a linking loader or a linkage editor. Linking is done after object code generation, prior to program execution time. At load time, a linking loader combines whatever programs are required and loads them directly into primary storage. A linkage editor also performs the same task, but it creates a load image that it preserves on secondary storage for future reference. Whenever a program is to be executed, the load image produced by the linkage editor may be loaded immediately without the overhead of recombining program segments. Points to Note 1. A compiler converts a high-level language program into executable machine instructions after the removal of syntax errors. 2. An interpreter executes each high-level language pro- gram one line at a time after removing its syntax error and converting it into machine instructions. 3. A linker makes the addresses of programs known to each other so that transfer of control from one subpro- gram to another or a main program takes place prop- erly during execution. 4. A loader is a program that places a program’s execut- able machine instructions and data into primary stor- age locations. 1.4 PROGRAM EXECUTION The primary memory of a computer, also called the Random Access Memory, is divided into units known as words. Depending on the computer, a word of memory may be two, four, or even eight bytes in size. Each word is associated with a unique address, which is a positive integer that helps the CPU to access the word. Addresses increase consecutively from the top of the memory to its bottom. When a program is compiled and linked, each instruction and each item of data is assigned an address. At execution time, the CPU fi nds instructions and data from these addresses.

📄 Page 20

Introduction to Programming, Algorithms and Flowcharts 9 The PC, or program counter, is a CPU register that holds the address of the next instruction to be executed in a program. In the beginning, the PC holds the address of the zeroth instruction of the program. The CPU fetches and then executes the instruction found at this address. The PC is meanwhile incremented to the address of the next instruction in the program. Having executed one instruction, the CPU goes back to look up the PC where it fi nds the address of the next instruction in the program. This instruction may not necessarily be in the next memory location. It could be at quite a different address. For example, the last statement could have been a go to statement, which unconditionally transfers control to a different point in the program; or there may have been a branch to a function subprogram. The CPU fetches the contents of the words addressed by the PC in the same amount of time, whatever their physical locations. The CPU has random access capability to any and all words of the memory, no matter what their addresses. Program execution proceeds in this way until the CPU has processed the last instruction. Points to Note 1. When a program is compiled and linked, each instruction and each item of data is assigned an address. 2. During program execution, the CPU fi nds instructions and data from the assigned addresses. 1.5 FOURTH GENERATION LANGUAGES The Fourth Generation Language is a non-procedural language that allows the user to simply specify what the output should be without describing how data should be processed to produce the result. Fourth generation programming languages are not as clearly defi ned as are the other earlier generation languages. Most people feel that a fourth generation language, commonly referred to as 4GL, is a high-level language that requires signifi cantly fewer instructions to accomplish a particular task than does a third generation language. Thus, a programmer should be able to write a program faster in 4GL than in a third generation language. Most third generation languages are procedural languages. That is, the programmer must specify the steps of the procedure the computer has to follow in a program. By contrast, most fourth generation languages are non- procedural languages. The programmer does not have to give the details of the procedure in the program, but specify, instead, what is wanted. For example, assume that a programmer needs to display some data on the screen, such as the address of a particular employee, say MANAS, from the EMP fi le. In a procedural language, the programmer would have to write a series of instructions using the following steps: Step 1: Get a record from the EMP fi le. Step 2: If this is the record for MANAS, display the address. Step 3: If this is not the record for MANAS, go to step 1, until end-of-fi le. In a non-procedural language (4GL), however, the programmer would write a single instruction that says: Get the address of MANAS from EMP fi le. Major fourth generation languages are used to get information from fi les and databases, as in the previous example, and to display or print the information. These fourth generation languages contain a query language, which is used to answer queries or questions with data from a database. The following example shows a query in a common query language, SQL. SELECT ADDRESS FROM EMP WHERE NAME = ‘MANAS’ End user-oriented 4GLs are designed for applications that process low data volumes. These 4GLs run on mainframe computers and may be employed either by information users or by the programmers. This type of 4GL may have its own internal database management software that in turn interacts with the organization’s DBMS package. People who are not professional programmers use these products to query databases, develop their own custom-made applications, and generate their own reports with minimum amount of training. For example, ORACLE offers a number of tools suitable for the end user. Some fourth generation languages are used to produce complex printed reports. These languages contain certain types of programs called generators. With a report generator, the programmer specifi es the headings, detailed data, and totals needed in a report. Thus, the report generator produces the required report using data from a fi le. Other fourth generation languages are used to design screens for data input and output and for menus. These languages