Intermediate C Programming. 2 Ed

Cover Page....1

Half-Title Page....2

Title Page....4

Copyright Page....5

Contents....9

List of Figures....64

List of Tables....68

Foreword for the First Edition....72

Recommendations for the First Edition....76

Preface....79

Acknowledgments....86

Source Code....87

Author and Artist....88

I Storage: Memory and File....90

1 Program Execution....91

1.1 Compile....91

1.2 Redirect Output....97

1.3 Problems....98

1.3.1 Replace String....99

1.3.2 Keep Third Column....99

1.3.3 Find String in a File....99

1.3.4 Sort by a Column....99

1.3.5 gcc Warnings....99

1.3.6 du command....100

1.3.7 Show End of a File....100

2 Stack Memory....101

2.1 Values and Addresses....101

2.2 Stack....105

2.3 The Call Stack....106

2.3.1 The Return Location....106

2.3.2 Function Arguments....113

2.3.3 Local Variables....117

2.3.4 Value Address....118

2.3.5 Arrays....122

2.3.6 Retrieving Addresses....124

2.4 Visibility....125

2.5 Examine the Call Stack with DDD....131

2.6 Problems....138

2.6.1 Draw Call Stack I....138

2.6.2 Draw Call Stack II....139

2.6.3 Addresses....141

3 Prevent, Detect, and Remove Bugs....142

3.1 Rules in Software Development....143

3.2 Developing Software ≠ Coding....146

3.2.1 Before Coding....147

3.2.2 During Coding....148

3.2.3 After Coding....151

3.3 Post-Execution and Interactive Debugging....152

3.4 Separate Testing Code from Production Code....154

3.5 Use assert Correctly....156

3.6 How to Comment Code....158

4 Pointers....162

4.1 Scope....162

4.2 The Swap Function....166

4.3 Pointers....170

4.4 Self Test: Pointers....178

4.5 The Swap Function Revisited....179

4.6 Type Errors....185

4.7 Arrays and Pointers....188

4.8 Type Rules....196

4.9 Pointer Arithmetic....197

4.10 Sizes of Data Types....201

4.11 Problems....208

4.11.1 Swap Function 1....208

4.11.2 Swap Function 2....209

4.11.3 Swap Function 3....211

4.11.4 Swap Function 4....212

4.11.5 Swap Function 5....213

4.11.6 15,552 Variations....215

4.11.7 Pointer and Array....217

5 Writing and Testing Programs....221

5.1 Distinct Array Elements....221

5.1.1 main Function....222

5.1.2 areDistinct Function....226

5.1.3 Compiling and Linking....228

5.2 Build and Test Program with Multiple Files....231

5.2.1 make and Makefile....232

5.2.2 Test using make....239

5.2.3 Generate Test Cases....241

5.3 Detect Invalid Memory Access....244

5.4 Test Coverage....249

5.5 Limit Core Size....255

5.6 Remove Large Files....257

5.7 Problems....258

5.7.1 Array Index....258

5.7.2 gcov....258

5.7.3 Test Coverage....258

6 Strings....259

6.1 Array of Characters....259

6.2 String Functions in C....264

6.2.1 Copy: strcpy....265

6.2.2 Copy: strdup....266

6.2.3 Compare: strcmp....267

6.2.4 Find Substrings: strstr....269

6.2.5 Find Characters: strchr....270

6.3 Understand argv....270

6.4 Count Substrings....275

6.5 Problems....278

6.5.1 Compare Strings....278

6.5.2 Count Substring-1....279

6.5.3 Count Substring-2....279

7 Heap Memory....280

7.1 Allocate Memory using malloc....280

7.2 Stack and Heap Memory....285

7.3 Functions that Return a Heap Address....291

7.4 Two-Dimensional Arrays in C....295

7.5 Pointers and Function Arguments....304

7.6 Problems....308

7.6.1 free....308

7.6.2 malloc....308

7.6.3 Address of Stack Memory....308

8 Programming Problems Using Heap Memory....310

8.1 Sort an Array....310

8.1.1 Generate Test Input and Expected Output....310

8.1.2 Sort Integers....311

8.1.3 Makefile....319

8.1.4 Use valgrind to Detect Memory Leaks....322

8.1.5 Use gcc -fsanitize to Detect Memory Leaks....324

8.2 Sort Using qsort....325

8.2.1 qsort....326

8.2.2 The Comparison Function....328

8.2.3 Execution Examples....333

8.2.4 Sort Strings....335

8.3 Problems....339

8.3.1 Bubble Sort....339

8.3.2 Selection Sort....342

8.3.3 Comparison in qsort....342

9 Reading and Writing Files....343

9.1 Read from Files....343

9.2 Write to Files....352

9.3 Read and Write Strings....357

10 Programming Problems Using File....365

10.1 Sort a File of Integers....365

10.2 Count the Occurrences of Characters....370

10.3 Count the Occurrences of a Word....376

10.4 Problems....379

10.4.1 Determine Palindrome....379

10.4.2 Compare Two Files....380

10.4.3 fscanf and ftell....380

11 Array Index, Security, and Trends....383

11.1 Array Index....384

11.2 Modify Program Behavior....390

11.3 Trends in Programming Languages....393

12 Version Control....396

12.1 Version Control Overview....396

12.2 git and github.com....397

12.3 Create a Repository on github....400

12.4 Sample Repository....408

12.5 Use git and github.com....418

12.6 Problems....428

12.6.1 git commit and git push....428

12.6.2 Revert to an earlier version....428

12.6.3 When to commit?....428

12.6.4 When to clone?....428

12.6.5 Recover deleted file....428

II Recursion....430

13 Concept....431

13.1 Select Balls with Restrictions....432

13.1.1 Balls of Two Colors....432

13.1.2 Balls of Three Colors....434

13.2 One-Way Streets....436

13.3 The Tower of Hanoi....438

13.4 Calculate Integer Partitions....441

13.4.1 Count the Number of “1”s....443

13.4.2 Odd Numbers Only....447

13.4.3 Increasing Values....448

13.4.4 Alternating Odd and Even Numbers....450

13.5 Problems....454

13.5.1 Parentheses....454

13.5.2 Ball Selection....456

13.5.3 Partition using Odd and Even Numbers....456

14 Recursive C Functions....458

14.1 Select Balls with Restrictions....459

14.2 One-Way Streets....461

14.3 The Tower of Hanoi....464

14.4 Integer Partition....468

14.5 Factorial....470

14.6 Fibonacci Numbers....475

14.7 Performance Profiling with gprof....486

14.8 Problems....489

14.8.1 Count Number of Calls: Original Definition....489

14.8.2 Count Number of Calls: Efficient Recursion....490

14.8.3 Parentheses....492

14.8.4 Fibonacci Numbers....495

15 Integer Partition....496

15.1 Print Partitions....496

15.2 Stack and Heap Memory....500

15.3 Trace Recursive Function Calls....508

15.4 Generate Partitions with Restrictions....513

15.4.1 Using Odd Numbers Only....515

15.4.2 Using Sequences of Increasing Numbers....517

15.4.3 Using Alternating Odd and Even Numbers....518

15.5 Problems....520

15.5.1 Even Numbers Only....520

15.5.2 Decreasing Values....520

15.5.3 Error in partition....520

15.5.4 Error in partition....521

15.5.5 Error in partition....521

16 Programming Problems Using Recursion....523

16.1 Binary Search....523

16.2 Quick Sort....529

16.3 Permutations and Combinations....542

16.4 Stack Sort....551

16.5 An Incorrect Recursive Function....560

16.6 Problems....564

16.6.1 Shuffle Cards - 1....564

16.6.2 Shuffle Cards - 2....567

16.6.3 Shuffle Cards - 3....567

III Structure....568

17 Programmer-Defined Data Types....569

17.1 Struct and Object....569

17.2 Objects as Arguments....579

17.3 Objects and Pointers....583

17.4 Constructors and Destructors....593

17.5 Structures within Structures....611

17.6 Binary Files and Objects....617

17.7 Problems....625

17.7.1 Structure and Pointer....625

17.7.2 Structure and Attributes' Sizes....628

17.7.3 Alternative Ways to Assign Attributes....632

18 Programming Problems Using Structure....635

18.1 Sort a Person Database....635

18.2 Packing Decimal Digits....651

18.3 Binary File and Pointer....674

18.4 Problems....679

18.4.1 Number Systems....679

18.4.2 Structure with Pointer-1....680

18.4.3 Structure with Pointer-2....680

19 Linked Lists....681

19.1 Dynamic Data Structure....681

19.2 Linked Lists....683

19.3 Insert Data....685

19.4 Search a Linked List....690

19.5 Delete a Node from a Linked List....691

19.6 Print a Linked List....695

19.7 Destroy a Linked List....697

20 Programming Problems Using Linked List....703

20.1 Queues....703

20.2 Sort Numbers....705

20.3 Sparse Arrays....708

20.4 Reversing a Linked List....720

20.5 Doubly Linked List....722

21 Binary Search Trees....725

21.1 Binary Tree....725

21.2 Binary Search Tree....729

21.3 Insert Data into a Binary Search Tree....732

21.4 Search a Binary Search Tree....736

21.5 Print a Binary Tree....738

21.6 Delete from a Binary Search Tree....743

21.7 Destroy a Binary Tree....747

21.8 Count the Different Shapes of a Binary Tree....748

21.9 Problems....753

21.9.1 Count Nodes....753

21.9.2 Tree Height....753

21.9.3 Check Binary Search Tree....753

21.9.4 Ancestor-Offspring....753

21.9.5 Build Binary Tree....753

22 Parallel Programming Using Threads....755

22.1 Parallel Programming....755

22.2 POSIX Threads....757

22.3 Subset Sum....762

22.3.1 Sequential Solution....765

22.3.2 Multiple-Threads Solution....773

22.4 Interleave the Execution of Threads....785

22.5 Thread Synchronization....796

22.6 Amdahl's Law....803

22.6.1 Speedup vs. Efficiency....805

22.6.2 Understanding Amdahl's Law....808

22.6.3 The Limit's of Amdahl's Law....810

22.7 Problems....812

22.7.1 Interleaving of Threads....812

22.7.2 Interleaving of Threads....812

23 Unit Test....813

23.1 Google Test Framework....813

23.2 Rational Numbers....820

23.3 Rational Numbers and Operations....828

23.3.1 Create Ratoinal Object....828

23.3.2 Arithmetic Operations....835

23.4 Use and Test Rational Numbers....844

23.4.1 Use Rational Numbers....844

23.4.2 Test Rational Numbers....852

23.5 Testing Strategies....865

IV Applications....868

24 Find the Exit of a Maze....869

24.1 Maze File Format....869

24.2 Strategy to Find Exit....873

24.3 Implement the Strategy....876

24.4 Problems....890

24.4.1 Mark of Bricks....890

24.4.2 Multiple Exits....890

24.4.3 Order of Directions....890

24.4.4 Change if Conditions....890

25 Sudoku....892

25.1 Sudoku Game....892

25.2 Recursive Solution....895

25.3 Implement the Solution....899

25.4 Design Decisions....922

25.5 Network Communication....925

25.5.1 Server....928

25.5.2 Client....936

25.6 Problems....942

25.6.1 Check Sudoku....942

25.6.2 Transfer Large File....943

26 Image Processing....944

26.1 Structure for Image....944

26.2 Image Pixels and Colors....957

26.3 Color Filter....961

26.4 Invert Colors....963

26.5 Detect Edges....964

26.6 Equalize Colors....969

26.7 main Function....974

26.8 Problems....977

26.8.1 Color Histogram....977

26.8.2 Color Space....978

26.8.3 Gradient....978

26.8.4 Vertical Mirror....978

27 Huffman Compression....979

27.1 Variable-Length Coding....979

27.2 Compress....981

27.2.1 Count and Sort Occurrences....981

27.2.2 Build the Code Tree....983

27.2.3 Create Code Book and Compress Data....986

27.2.4 Describe the Coding Tree....987

27.2.5 Use Bits....988

27.3 Decompress....992

27.4 Implementation....993

27.4.1 Test Case Generator....993

27.4.2 main Function....996

27.4.3 Makefile....998

27.4.4 Compression....1000

27.4.5 Decompression....1011

27.4.6 Compression Ratios....1017

27.5 Problems....1018

27.5.1 Compression Tree....1018

27.5.2 Compressed File....1018

27.5.3 Compressed File....1018

27.5.4 One-Letter Input....1018

27.5.5 Compressed File....1018

27.5.6 Number of Leaf Nodes....1018

27.5.7 Compression Ratio....1018

27.5.8 Tree Description....1018

27.5.9 Highest Possible Compression Ratio....1019

27.5.10 Lowest Possible Compression Ratio....1019

Index....1020

Epilogue: The Computer Engineer as Tool-User....1067

Revised for a new second edition, Intermediate C Programming provides a stepping-stone for intermediate-level students to go from writing short programs to writing real programs well. It shows students how to identify and eliminate bugs, write clean code, share code with others, and use standard Linux-based tools, such as ddd and valgrind.

This second edition provides expanded coverage of these topics with new material focused on software engineering, including version control and unit testing. The text enhances their programming skills by explaining programming concepts and comparing common mistakes with correct programs. It also discusses how to use debuggers and the strategies for debugging as well as studies the connection between programming and discrete mathematics.

Including additional student and instructor resources available online, this book is particularly appealing as a classroom resource.