Fundamentals of structural programming in C ++

The book "Fundamentals of structural programming in C ++" is intended for the initial learning of programming in a high-level algorithmic language on examples written in C ++. The individual chapters of the book systematically discuss elements of language and programs as well as basic algorithms and algorithmic methods. Their application has been shown for the construction of sequential, branched, repeating calculations, program tasks separated between functions, as well as modules. The book discusses standard types and programmers defined by simple variables and indicators as well as static data structures, such as: arrays, records, record tables, binary files and text files. It also presents dynamic data structures, i.e. dynamic tables, dynamic array of indicators, one-way, two-way and cyclic lists, data structures using lists, e.g. stacks, queues, list of indicators, list lists, as well as binary trees and AVL trees. Much attention is devoted to algorithms for handling data structures, illustrating them with numerous examples of programs. In addition to the theoretical part, each chapter contains an exercise, presenting ready-made programs on which some experiments are carried out, aimed at better understanding and consolidation of elements of the language and algorithms discussed in a given chapter. Examples of programs are also a role model when the reader develops his own programs for tasks to be solved independently. All programs discussed in the book are provided on a medium in various environmental versions for Borland Builder6.0, Visual C ++ 6.0, Visual Studio.Net. The programs use stream input and output as well as those elements of the C ++ language that facilitate programming, i.e. fixed constants, references, new and delete operators, indicator type, function prototypes. Studying the book along with the development of a set of proprietary programs will provide the reader with a good basis for further learning object oriented programming in C ++

Table of Contents

Admission
Notes on the distinctions in the text

Chapter 1. Sequential program
Basic concepts
Features of algorithms
Features of objects
Actions
Characteristics of the C ++ language
Compilation rules
Elements of the C ++ language
Standard types
Program structure
Declarations and definitions of constants
Definitions and declarations of variables
Instructions
subroutines
Validating variables
expressions
Validation by the program, assignment instruction
Validation by the user
Output of information and data from the program to the user
Output of messages
Outputting results
Deriving warnings and error messages
Structure of the sequential program
Notes on rules and programming style
Control questions
Exercise 1. Editing, compiling and running a sequential program
Entering and displaying integers - file wewyint.cpp
Entering and displaying real numbers - file wewyreal.cpp
Entering and displaying subtitles and characters - wewystr.cpp
Works
Rules for converting measures

Chapter 2. Data types. Program with branches
Standard types and expression
Operators and expressions
Arithmetic operators
Assignment operators
Relations operators
Total types
Real types
Character type
Character input
Displaying characters
Subtitles
Entering subtitles
Displaying subtitles
Block diagrams
Organization of branches in programs
Complex instructions
Conditional instructions
An example of a branched program
Construction else else if
Selection instructions
The goto jump statement
Types defined
Enumeration type
Notes on rules and programming style
Control questions
Exercise 2. Programs with branches
Using conditional statements with simple conditions - language file. Cpp
Program with nested conditional statements with relational expressions - language file1.cpp
Program with nested conditional statements examining the value of the variable - language2.cpp file
Program with complex conditions - language file3.cpp
A program with simple and complex conditions - plik warunki.cpp file
Program with branching on a larger number of roads - file selection. Cpp
Works

Chapter 3. Program with repetitions
Basic operations performed in a loop
Types of loops
Loops with a known number of repetitions - for instructions
The syntax of the for statement
Determining the number of repetitions
Using an explicit constant
Using a defined constant
Loop with condition test at the beginning - while statement
Loop with condition test at the end - instruction to while
Loops with a certain number of repetitions and condition for early termination
Infinite loops
An example of a program using the algorithm for calculating the sum
Loops in the loop
Notes on rules and programming style
Control questions
Exercise 3. Organization of loops - iterative instructions
Loops with a certain number of repetitions
Loops with an unspecified number of repetitions - testing of the repeat condition at the beginning of the loop - petlawhi.cpp file
Loops with an unspecified number of repetitions - testing of the repeat condition at the end of the loop - file petlarep.cpp
Works

Chapter 4. The process of program production
The life cycle of the program
Program design
Types of software constructions used in the construction of algorithms and their implementation *
Structural algorithm *
Testing and running the program
Testing rules
Facilities of the BC, BB and VC system startup program
Documenting programs
Types of documentation
Contents of student program documentation
Meaning and types of comments in the program
Notes on rules and programming style
Control questions
Exercise 4. Conditional instructions and iterative instructions
Nested loops - a for loop in a for loop
Nested loops - a while loop in the for loop - plika.cpp file
Nested loops - a while loop in the for loop - a file of date.cpp
Works

Chapter 5. Subprograms - functions
Purpose and effects of use
Definition of a subroutine
Function definition
The types of communication of functions with the program
Non-parametric functions, non-return values
Functions with input parameters, non-return values
Functions with input parameters that return a value
Functions with input and output parameters, non-return values
Functions without input parameters that return several results
Functions with input and output parameters that return a value
Passing parameters to the subroutine
Passing a parameter by value
Passing a parameter by a constant
Passing a parameter by reference
Contents of the subprogram
Calling a function
Program structure with functions
The range of visibility of program variables
Inline functions *
Function overloading and default parameters *
Overloading operators *
Logical division of the program into subprograms - methods of program design
Diagrams for presenting data structures and program structure *
Purpose and general characteristics *
Forms of program structure diagrams *
Examples of structure diagrams and control flow *
Recursive functions *
Intermediate recursion *
Specific recursion *
Examples of recursive functions *
Applications of recursion **
Notes on rules and programming style
Control questions
Exercise 5. Functions
Function without parameters returning value - file key.cpp
Function with a parameter passed by a value, returning the calculated value - calculation of iterative patterns - firstfile.cpp file
Function with a parameter passed by a value, returning the calculated result - calculation of series sums - file functions.cpp
Function with parameters passed by references - data.cpp file
Works

Chapter 6. Arrays - index access
General characteristics
Definitions and declarations of tables
A reference to an array element
Initiating the table
Giving values to array elements
Assigning an initial value to elements of an array by assigning
Giving values to elements of the table by loading data entered from the keyboard
Output of array elements
Derivation of one-dimensional array elements
Output of two-dimensional array elements
Searching in an array of an element that meets a given condition
Line search with a loop to while
Search with a guard with a loop to while
Line search with a while loop - classical algorithm
Search with a guard with a while loop
Line search with for loop
Searching in multidimensional arrays
Selection of array elements that meet a given condition
Determination of the maximum value in the table
Operations on rows and columns of a two-dimensional array
Sums in rows
Counting in the columns of a two-dimensional array
Other algorithms that perform operations on arrays or tables
Sorting a one-dimensional array by selecting
Bubble sorting
Quick Sort Quick Sort *
Merging tables
Eratosthenes sieve *
A pseudo-random number generator with a non-uniform distribution from the 1-m interval
Notes on rules and programming style
Control questions
Exercise 6. One- and two-dimensional boards
Operations on a one-dimensional array - tablind.cpp file
The algorithm for quick search of minimum and maximum values in the array - file minmaks.cpp Recursive algorithm for quick search of minimum and maximum values in the array * - file minmaksr.cpp
Operations on a two-dimensional table - tab2ind.cpp file
Works

Chapter 7. Indicators
General characteristics
Indicator to the indicator
Passing the function parameter by pointer
Transmission of indicators
Operations on indicators and variables indicated
Assignment of the address of another variable to the pointer
Assignment of indicators
Assignment of indicated variables
Moving the pointer
Comparison of indicators
Indicators for fixed and fixed indicators *
Indicator of an indeterminate type
Indicator access to array elements. Indicator arithmetic
One-dimensional boards
Two-dimensional boards
Notes on rules and programming style
Control questions
Exercise 7. Indicators
Operations on indicators - the file wskliczb.cpp
Indicative access to elements of one-dimensional tables - file tablwsk.cpp
Indexable access to two-dimensional array elements - tab2wsk.cpp file
Works

Chapter 8. Inscriptions - strings
Declarations, entering, filling and displaying subtitles
Declaring and initiating constant and subtitle variables and indicators for subtitles
Entering and outputting subtitles
Functions working on subtitles - string module
Reading the length of the string - strlen function
Copy subtitles - functions: strcpy, strncpy, strdup
Connecting (concatenation) subtitles - functions: strcat, strncat
Comparing subtitles - functions: strcmp, stricmp, strncmp
Searching for subtitles - functions: strstr, strchr, strrchr
Completing subtitles
Conversions of subtitles
Examples of the use of standard functions that operate on subtitles
Functions that work on characters
Examples of functions and programs operating on subtitles
Removing starting spaces
Insert, delete and replace functions
Conversion of dates in the form of three numbers into a string in a format suitable for comparing dates
Towers of Hanoi *
Tables of subtitles
Notes on rules and programming style
Control questions
Exercise 8. Subtitles
Operations on indicators - file wsknapis.cpp
Validation of the string - check.cpp file
Operations on an unordered subtitle table - tabnapis.cpp file
Works

Chapter 9. Records and record tables
Destiny
Diagrams for presenting data structures *
Declarations of variables
Operations on constituent structures and structures
Initializing the structure
Field selector - component structure selector
Assigning field values and reading fields
Assigning entire structures
Passing the structure to and from the function: loading, displaying and updating the structure
Passing the structure to a function by reference
The structure is passed to the function by the pointer
Passing the structure into a function by value
Passing the structure into the program by the return value
References to fields of the structure provided by the pointer
Operations for a single record
Importing modules and global declarations
Defined functions
Main program
Bit fields *
Lift *
Collecting records in tables
declarations
References to array elements and their fields
Operations performed on the record table
Organization of data files
Processing of an organized file in the record table
Notes on rules and programming style
Control questions
Exercise 9. Records and tables of records
Operations performed on one record - file record.cpp
Creating files in the record table and displaying its contents - tabreka.cpp file
Records table processing - tabrekb.cpp file
Examples of real objects and their features

Chapter 10. User communication with the program. Division of the program into modules
User communication with the program
Program operation modes
Types of programs
Controlling the work of programs
Constructing and presenting the program offer *
Controlling user input
Controlling the output of data by the program
Division of the program into modules
Purpose of the module
Construction and use of the module
An example of a program that uses functions from its own module
Modularization rules
Library of user's own functions
Notes on rules and programming style
Control questions
Exercise 10. Physical division of the program into modules
Program modules

Chapter 11. Files
General characteristics and purpose
Features of files
Ways of handling files in C ++
Ways of data storage
Ways to access file data
Types of operations
Selection of file features for the purpose of the file
File variables
Operations on logical files
Low level operations *
Operations on streams
Open the file
Closing the file
Write to file
Reading from a file
Error handling*
File pointer operations
Support for stream buffers *
Operations on physical files
Fixing data on tables
Save the record table in a binary file
Recreation of the array of records data structure based on a file
File processing algorithms
Writing elements to a file
The algorithm of data processing from a file
An algorithm for selecting file elements with a non-unique field value
File element search algorithm according to a unique field
The element update algorithm in the file
Algorithm to remove an element from an unordered file
Removal of an element from an ordered file
Group update algorithm - processing the source file into a result file with the same name
Features for directories and disk files
Directory management functions *
Features for disk files *
Advanced index operations
Application of transmission to the indicator function on the indicator
The indicator on the function
Passing the pointer to the function via the parameter
Notes on rules and programming style
Control questions
Exercise 11. Binary files
Save and restore the array
Creating files in the file and displaying data from the file
Processing of the record file
Searching in a record record file with a unique field value
Delete the found record from the file
Works

Chapter 12. Text files
General characteristics and purpose
Operations performed on text files
Text file processing schemes
Saving individual characters
Saving rows
Reading individual characters
Reading rows
Reading data from a file by format
Save data to a file by format
Creating a list in the form of a table
Creating a report in the form of a table
Generating a mail merge document
Communication between the program and the printer *
Sending a source file to the printer with character blocks *
Copying a text file to the printer with blocks *
Other comments *
Direct access to text file characters *
Notes on rules and programming style
Control questions
Exercise 12. Binary and text files
Copying binary files
Create a list with data from a record file in a text file
Writing a report to a text file
Generate a mail merge document in a text file
Works

Chapter 13. Dynamic variables - dynamic tables and lists
Allocation and freeing of memory for dynamic variables
Arrays in C ++
Number tables
Tables of subtitles
Other functions operating on memory blocks *
Grouping of dynamic variables in lists - organization of lists
General characteristics
Rules for the organization of letter structures
Creating dynamic data structures
Operations on a one-way list
Declarations for the list
One-way list module
Attach an element to the top of the list
Attach an element to the end of the list
Joining an element by an element with a known address
Joining an element while maintaining the order of the list
Browse the list
Search in the list
Selecting elements that meet a given condition
Counting the number of list elements
Removing items from the list
Reversing the order of items in the list *
Release list elements
Restore the list based on the file
Operations on a bidirectional list
List element structure
Bidirectional list module
Attach an element to the top of the list
Attach an item to the end of the list *
Joining an element by an element with a known address
Joining an element in front of an element with a known address
Attach an item to the ordered list
Browse the list
Search in the list
Removing items from a bidirectional list
Release list elements
Restore the list by file
Letters with head and circular lists
Rules for the organization of a one-way list with your head
Rules for the organization of a one-way circular list with your head
Rules for the organization of a two-way circular list with your head
Program module, universal module
Standard module with functions to handle the list
Universal module *
Template list module
Recursive functions in a one-way list *
Attach an element to the end of the list
Joining the ordered list *
Displaying the list in reverse order *
List length *
Sorting list **
Notes on rules and programming style
Control questions
Exercise 13. List
A program that uses a one-way list module -1ab13 \ listalk
Program using the bidirectional list module 1ab13 \ listalk
Program using a bidirectional, cyclic list with head 1ab13 / listac
Creating a list of selected records from a file *
Works
Application examples

Chapter 14. Dynamic data structures - lists and tables
Abstract data type
Stack
General characteristics
Stack implementation through a static structure
Stack implementation by the dynamic structure
Queue
General characteristics
The ordinary queue
Priority queue
Implementation of the queue in the form of a list of links
The group is ordered
Declarations for an ordered group
Functions for handling an ordered group
Complex dynamic structures based on lists
Combined lists and independent lists *
List of lists
Collection*
declarations
Functions that support the collection
Rare vector and sparse matrix **
Declarations for a vector and rare matrices
Functions of Rare Matrix matrix data structure
Other data structures organized on the basis of lists
Self-organizing lists **
Topological lists **
List of indexes to a file
Notes on rules and programming style
Control questions
Exercise 14. Data structures using dynamic memory allocation
Dynamic data table - collection.cpp
Dynamic array of indicators
Indicator array for records
A program that uses a one-way link list module
Implementation of a two-way queue
Works

Chapter 15. Trees
Features of trees
Tree implementation in the form of static and dynamic structures
The tree is carefully balanced
Binary search trees - BST trees
Attaching a node to a tree
Search in a binary tree
Browsing the tree
Removing a node from a tree
Balanced trees AVL *
Omni directional tree *
Notes on rules and programming style
Control questions
Exercise 15. Binary trees
A program that uses a binary tree module
Balanced tree AVL *
Works

Appendix A. C input-output instructions

Appendix B. Object-input-output

Appendix C. Example of program documentation
Description of the program's purpose and operations
Technical data of the program
Data structures of the program
Program structure
Description of the program's functions
The rules of cooperation with the user
Description of the possibilities of expanding or optimizing the program

Literature

Index