Intermediate C Programming

Cover
Half Title
Title Page
Copyright Page
Contents
List of Figures
List of Tables
Foreword for the First Edition
Recommendations for the First Edition
Preface
Acknowledgments
Source Code
Author and Artist
I. Storage: Memory and File
	1. Program Execution
		1.1. Compile
		1.2. Redirect Output
		1.3. Problems
			1.3.1. Replace String
			1.3.2. Keep Third Column
			1.3.3. Find String in a File
			1.3.4. Sort by a Column
			1.3.5. gcc Warnings
			1.3.6. du command
			1.3.7. Show End of a File
	2. Stack Memory
		2.1. Values and Addresses
		2.2. Stack
		2.3. The Call Stack
			2.3.1. The Return Location
			2.3.2. Function Arguments
			2.3.3. Local Variables
			2.3.4. Value Address
			2.3.5. Arrays
			2.3.6. Retrieving Addresses
		2.4. Visibility
		2.5. Examine the Call Stack with DDD
		2.6. Problems
			2.6.1. Draw Call Stack I
			2.6.2. Draw Call Stack II
			2.6.3. Addresses
	3. Prevent, Detect, and Remove Bugs
		3.1. Rules in Software Development
		3.2. Developing Software ≠ Coding
			3.2.1. Before Coding
			3.2.2. During Coding
			3.2.3. After Coding
		3.3. Post-Execution and Interactive Debugging
		3.4. Separate Testing Code from Production Code
		3.5. Use assert Correctly
		3.6. How to Comment Code
	4. Pointers
		4.1. Scope
		4.2. The Swap Function
		4.3. Pointers
		4.4. Self Test: Pointers
		4.5. The Swap Function Revisited
		4.6. Type Errors
		4.7. Arrays and Pointers
		4.8. Type Rules
		4.9. Pointer Arithmetic
		4.10. Sizes of Data Types
		4.11. Problems
			4.11.1. Swap Function 1
			4.11.2. Swap Function 2
			4.11.3. Swap Function 3
			4.11.4. Swap Function 4
			4.11.5. Swap Function 5
			4.11.6. 15,552 Variations
			4.11.7. Pointer and Array
	5. Writing and Testing Programs
		5.1. Distinct Array Elements
			5.1.1. main Function
			5.1.2. areDistinct Function
			5.1.3. Compiling and Linking
		5.2. Build and Test Program with Multiple Files
			5.2.1. make and Makefile
			5.2.2. Test using make
			5.2.3. Generate Test Cases
		5.3. Detect Invalid Memory Access
		5.4. Test Coverage
		5.5. Limit Core Size
		5.6. Remove Large Files
		5.7. Problems
			5.7.1. Array Index
			5.7.2. gcov
			5.7.3. Test Coverage
	6. Strings
		6.1. Array of Characters
		6.2. String Functions in C
			6.2.1. Copy: strcpy
			6.2.2. Copy: strdup
			6.2.3. Compare: strcmp
			6.2.4. Find Substrings: strstr
			6.2.5. Find Characters: strchr
		6.3. Understand argv
		6.4. Count Substrings
		6.5. Problems
			6.5.1. Compare Strings
			6.5.2. Count Substring-1
			6.5.3. Count Substring-2
	7. Heap Memory
		7.1. Allocate Memory using malloc
		7.2. Stack and Heap Memory
		7.3. Functions that Return a Heap Address
		7.4. Two-Dimensional Arrays in C
		7.5. Pointers and Function Arguments
		7.6. Problems
			7.6.1. free
			7.6.2. malloc
			7.6.3. Address of Stack Memory
	8. Programming Problems Using Heap Memory
		8.1. Sort an Array
			8.1.1. Generate Test Input and Expected Output
			8.1.2. Sort Integers
			8.1.3. Makefile
			8.1.4. Use valgrind to Detect Memory Leaks
			8.1.5. Use gcc -fsanitize to Detect Memory Leaks
		8.2. Sort Using qsort
			8.2.1. qsort
			8.2.2. The Comparison Function
			8.2.3. Execution Examples
			8.2.4. Sort Strings
		8.3. Problems
			8.3.1. Bubble Sort
			8.3.2. Selection Sort
			8.3.3. Comparison in qsort
	9. Reading and Writing Files
		9.1. Read from Files
		9.2. Write to Files
		9.3. Read and Write Strings
	10. Programming Problems Using File
		10.1. Sort a File of Integers
		10.2. Count the Occurrences of Characters
		10.3. Count the Occurrences of a Word
		10.4. Problems
			10.4.1. Determine Palindrome
			10.4.2. Compare Two Files
			10.4.3. fscanf and ftell
	11. Array Index, Security, and Trends
		11.1. Array Index
		11.2. Modify Program Behavior
		11.3. Trends in Programming Languages
	12. Version Control
		12.1. Version Control Overview
		12.2. git and github.com
		12.3. Create a Repository on github
		12.4. Sample Repository
		12.5. Use git and github.com
		12.6. Problems
			12.6.1. git commit and git push
			12.6.2. Revert to an earlier version
			12.6.3. When to commit?
			12.6.4. When to clone?
			12.6.5. Recover deleted file
II. Recursion
	13. Concept
		13.1. Select Balls with Restrictions
			13.1.1. Balls of Two Colors
			13.1.2. Balls of Three Colors
		13.2. One-Way Streets
		13.3. The Tower of Hanoi
		13.4. Calculate Integer Partitions
			13.4.1. Count the Number of “1”s
			13.4.2. Odd Numbers Only
			13.4.3. Increasing Values
			13.4.4. Alternating Odd and Even Numbers
		13.5. Problems
			13.5.1. Parentheses
			13.5.2. Ball Selection
			13.5.3. Partition using Odd and Even Numbers
	14. Recursive C Functions
		14.1. Select Balls with Restrictions
		14.2. One-Way Streets
		14.3. The Tower of Hanoi
		14.4. Integer Partition
		14.5. Factorial
		14.6. Fibonacci Numbers
		14.7. Performance Profiling with gprof
		14.8. Problems
			14.8.1. Count Number of Calls: Original Definition
			14.8.2. Count Number of Calls: Efficient Recursion
			14.8.3. Parentheses
			14.8.4. Fibonacci Numbers
	15. Integer Partition
		15.1. Print Partitions
		15.2. Stack and Heap Memory
		15.3. Trace Recursive Function Calls
		15.4. Generate Partitions with Restrictions
			15.4.1. Using Odd Numbers Only
			15.4.2. Using Sequences of Increasing Numbers
			15.4.3. Using Alternating Odd and Even Numbers
		15.5. Problems
			15.5.1. Even Numbers Only
			15.5.2. Decreasing Values
			15.5.3. Error in partition
			15.5.4. Error in partition
			15.5.5. Error in partition
	16. Programming Problems Using Recursion
		16.1. Binary Search
		16.2. Quick Sort
		16.3. Permutations and Combinations
		16.4. Stack Sort
		16.5. An Incorrect Recursive Function
		16.6. Problems
			16.6.1. Shuffle Cards - 1
			16.6.2. Shuffle Cards - 2
			16.6.3. Shuffle Cards - 3
III. Structure
	17. Programmer-Defined Data Types
		17.1. Struct and Object
		17.2. Objects as Arguments
		17.3. Objects and Pointers
		17.4. Constructors and Destructors
		17.5. Structures within Structures
		17.6. Binary Files and Objects
		17.7. Problems
			17.7.1. Structure and Pointer
			17.7.2. Structure and Attributes’ Sizes
			17.7.3. Alternative Ways to Assign Attributes
	18. Programming Problems Using Structure
		18.1. Sort a Person Database
		18.2. Packing Decimal Digits
		18.3. Binary File and Pointer
		18.4. Problems
			18.4.1. Number Systems
			18.4.2. Structure with Pointer-1
			18.4.3. Structure with Pointer-2
	19. Linked Lists
		19.1. Dynamic Data Structure
		19.2. Linked Lists
		19.3. Insert Data
		19.4. Search a Linked List
		19.5. Delete a Node from a Linked List
		19.6. Print a Linked List
		19.7. Destroy a Linked List
	20. Programming Problems Using Linked List
		20.1. Queues
		20.2. Sort Numbers
		20.3. Sparse Arrays
		20.4. Reversing a Linked List
		20.5. Doubly Linked List
	21. Binary Search Trees
		21.1. Binary Tree
		21.2. Binary Search Tree
		21.3. Insert Data into a Binary Search Tree
		21.4. Search a Binary Search Tree
		21.5. Print a Binary Tree
		21.6. Delete from a Binary Search Tree
		21.7. Destroy a Binary Tree
		21.8. Count the Different Shapes of a Binary Tree
		21.9. Problems
			21.9.1. Count Nodes
			21.9.2. Tree Height
			21.9.3. Check Binary Search Tree
			21.9.4. Ancestor-Offspring
			21.9.5. Build Binary Tree
	22. Parallel Programming Using Threads
		22.1. Parallel Programming
		22.2. POSIX Threads
		22.3. Subset Sum
			22.3.1. Sequential Solution
			22.3.2. Multiple-Threads Solution
		22.4. Interleave the Execution of Threads
		22.5. Thread Synchronization
		22.6. Amdahl’s Law
			22.6.1. Speedup vs. Efficiency
			22.6.2. Understanding Amdahl’s Law
			22.6.3. The Limit’s of Amdahl’s Law
		22.7. Problems
			22.7.1. Interleaving of Threads
			22.7.2. Interleaving of Threads
	23. Unit Test
		23.1. Google Test Framework
		23.2. Rational Numbers
		23.3. Rational Numbers and Operations
			23.3.1. Create Ratoinal Object
			23.3.2. Arithmetic Operations
		23.4. Use and Test Rational Numbers
			23.4.1. Use Rational Numbers
			23.4.2. Test Rational Numbers
		23.5. Testing Strategies
IV. Applications
	24. Find the Exit of a Maze
		24.1. Maze File Format
		24.2. Strategy to Find Exit
		24.3. Implement the Strategy
		24.4. Problems
			24.4.1. Mark of Bricks
			24.4.2. Multiple Exits
			24.4.3. Order of Directions
			24.4.4. Change if Conditions
	25. Sudoku
		25.1. Sudoku Game
		25.2. Recursive Solution
		25.3. Implement the Solution
		25.4. Design Decisions
		25.5. Network Communication
			25.5.1. Server
			25.5.2. Client
		25.6. Problems
			25.6.1. Check Sudoku
			25.6.2. Transfer Large File
	26. Image Processing
		26.1. Structure for Image
		26.2. Image Pixels and Colors
		26.3. Color Filter
		26.4. Invert Colors
		26.5. Detect Edges
		26.6. Equalize Colors
		26.7. main Function
		26.8. Problems
			26.8.1. Color Histogram
			26.8.2. Color Space
			26.8.3. Gradient
			26.8.4. Vertical Mirror
	27. Huffman Compression
		27.1. Variable-Length Coding
		27.2. Compress
			27.2.1. Count and Sort Occurrences
			27.2.2. Build the Code Tree
			27.2.3. Create Code Book and Compress Data
			27.2.4. Describe the Coding Tree
			27.2.5. Use Bits
		27.3. Decompress
		27.4. Implementation
			27.4.1. Test Case Generator
			27.4.2. main Function
			27.4.3. Makefile
			27.4.4. Compression
			27.4.5. Decompression
			27.4.6. Compression Ratios
		27.5. Problems
			27.5.1. Compression Tree
			27.5.2. Compressed File
			27.5.3. Compressed File
			27.5.4. One-Letter Input
			27.5.5. Compressed File
			27.5.6. Number of Leaf Nodes
			27.5.7. Compression Ratio
			27.5.8. Tree Description
			27.5.9. Highest Possible Compression Ratio
			27.5.10. Lowest Possible Compression Ratio
Index
Epilogue: The Computer Engineer as Tool-User