Transcript CPS120 Introduction to Computer Science

CPS120 Introduction to
Computer Science
Exam Review
Lecture 9
Compilers
• An engine that works on your behalf to
process instructions and allow you to deal
with various basic rules of the language
– The compiler’s job is to make sure you follow
the rules, to require that you provide enough
information that the compiler can translate you
instructions into languages the components can
understand
Introduction to Programming
The Program Development Cycle
Understand the problem
Plan the program's logic
Code the program
Get the program into machine-readable form
Translate the program
Test and debug the program
Document the program
Fundamental Programming Concepts
• One-after-another (Sequence)
• Decision-making (Selection)
– Making choices between 2 or more alternatives
• Repetition (Iteration)
– Concerned with repetitive tasks (and the termination
conditions of loops)
• Invocation
– Delegation of sub-tasks to functions / procedures
Common Flowchart Symbols
Common Flowchart Symbols
Terminator. Shows the starting and ending points of the program. A terminator has
flow lines in only one direction, either in (a stop node) or out (a start node).
Data Input or Output. Allows the user to input data and results to be displayed.
Processing. Indicates an operation performed by the computer, such as a variable
assignment or mathematical operation. With a heading – an internal subroutine
Decision. The diamond indicates a decision structure. A diamond always has two
flow lines out. One flow lineout is labeled the “yes” branch and the other is labeled the
“no” branch.
Predefined Process. One statement denotes a group of previously defined statements.
Such as a function or a subroutine created externally
Connector. Connectors avoid crossing flow lines, making the flowchart easier to read.
Connectors indicate where flow lines are connected. Connectors come in pairs, one with
a flow line in and the other with a flow line out.
Off-page connector. Even fairly small programs can have flowcharts that extend several
pages. The off-page connector indicates the continuation of the flowchart on another
page. Just like connectors, off-page connectors come in pairs.
Flow line. Flow lines connect the flowchart symbols and show the sequence of operations
during the program execution.
Rules for Pseudocode
1. Make the pseudocode language-independent
2. Indent lines for readability
3. Make key words stick out by showing them
capitalized, in a different color or a different font
4. Punctuation is optional
5. End every IF with ENDIF
6. Begin loop with LOOP and end with ENDLOOP
7. Show MAINLINE first; all others follow
8. TERMINAE all routines with an END
instruction
Syntax & Logic Errors
• A syntax error is simply the violation of the rules
of a language; misuse of structure and form in
programming or a violation of the compiler’s
rules. These errors are detected by the compiler
– Also know as 'fatal compilation errors'
• A logic error is a mistake that complies with the
rules of the compiler that causes the program to
generate incorrect output
Compiling and Debugging
• Executable code will not be created until
you correct all of the syntax errors in your
source code
• Then the fun (with logic errors) begins
Warnings
• Even though an executable has been
generated, you may not be done with syntax
errors
• Compilers generate syntax warning
messages which are not fatal errors but
represent special error checking functions
for certain common programming errors
Linker Errors
• Not all syntax errors are detectable by the
compiler
– These errors do not become apparent until files
are put together to create an executable
– These errors are not linked to a specific line of
code
• Look for the name of the variable and see what lines
of code it occurs on using EDIT and FIND
– LNIK2001: unresolved external
– LNK1120: unresolved externals
Computer Mathematics
Representing Data
• The computer knows the type of data stored
in a particular location from the context in
which the data are being used;
– i.e. individual bytes, a word, a longword, etc
– 01100011 01100101 01000100 01000000
• Bytes: 99(10, 101 (10, 68 (10, 64(10
• Two byte words: 24,445 (10 and 17,472 (10
• Longword: 1,667,580,992 (10
Alphanumeric Codes
• American Standard Code for Information
Interchange (ASCII)
– 7-bit code
– Since the unit of storage is a bit, all ASCII codes are
represented by 8 bits, with a zero in the most significant
digit
– H e l l o W o r l d
– 48 65 6C 6C 6F 20 57 6F 72 6C 64
• Extended Binary Coded Decimal Interchange
Code (EBCDIC)
Decimal Equivalents
•
Assuming the bits are unsigned, the decimal
value represented by the bits of a byte can be
calculated as follows:
1. Number the bits beginning on the right using
superscripts beginning with 0 and increasing as you
move left
•
Note: 20, by definition is 1
2. Use each superscript as an exponent of a power of 2
3. Multiply the value of each bit by its corresponding
power of 2
4. Add the products obtained
Binary to Hex
• Step 1: Form four-bit groups beginning from the
rightmost bit of the binary number
– If the last group (at the leftmost position) has less than
four bits, add extra zeros to the left of the group to
make it a four-bit group
• 0110011110101010100111 becomes
• 0001 1001 1110 1010 1010 0111
• Step 2: Replace each four-bit group by its
hexadecimal equivalent
– 19EAA7(16
Converting Decimal to Other Bases
• Step 1: Divide the number by the base you are
converting to (r)
• Step 2: Successively divide the quotients by (r)
until a zero quotient is obtained
• Step 3: The decimal equivalent is obtained by
writing the remainders of the successive division
in the opposite order in which they were obtained
– Know as modulus arithmetic
• Step 4: Verify the result by multiplying it out
Representing Negatives
• It is necessary to choose one of the bits of the
“basic unit” as a sign bit
– Usually the leftmost bit
– By convention, 0 is positive and 1 is negative
• Positive values have the same representation in all
conventions
• However, in order to interpret the content of any
memory location correctly, it necessary to know
the convention being used used for negative
numbers
Sign-Magnitude
• For a basic unit of N bits, the leftmost bit is
used exclusively to represent the sign
• The remaining (N-1) bits are used for the
magnitude
• The range of number represented in this
convention is –2 N+1 to +2 N-1 -1
Sign-magnitude Operations
• Addition of two numbers in sign-magnitude is
carried out using the usual conventions of binary
arithmetic
– If both numbers are the same sign, we add their
magnitude and copy the same sign
– If different signs, determine which number has the
larger magnitude and subtract the other from it. The
sign of the result is the sign of the operand with the
larger magnitude
– If the result is outside the bounds of –2 n+1 to +2 n-1 –1,
an overflow results
One’s Complement
• Positive numbers are represented in the usual
way
• For negatives
– STEP 1: Start with the binary representation of the
absolute value
– STEP 2: Complement all of its bits
One's Complement Operations
– Treat the sign bit as any other bit
– For addition, carry out of the leftmost bit is
added to the rightmost bit – end-around carry
Two’s Complement Convention
•
•
A positive number is represented using a
procedure similar to sign-magnitude
To express a negative number
1.
2.
3.
–
–
Express the absolute value of the number in binary
Change all the zeros to ones and all the ones to zeros (called
“complementing the bits”)
Add one to the number obtained in Step 2
The range of negative numbers is one larger than
the range of positive numbers
Given a negative number, to find its positive
counterpart, use steps 2 & 3 above
Two’s Complement Operations
• Addition:
– Treat the numbers as unsigned integers
• The sign bit is treated as any other number
– Ignore any carry on the leftmost position
• Subtraction
– Treat the numbers as unsigned integers
– If a "borrow" is necessary in the leftmost place,
borrow as if there were another “invisible” onebit to the left of the minuend
Introduction to C++
C++ Usages & Conventions
• C++ is absolutely case sensitive
–For Instance: A is 97 in ASCII and a is 65
–Remember: in ASCII {, [, and ( are not
equivalent
• No keywords in ANSI standard are even
partially uppercase
–‘While’ is not a keyword, ‘while’ is
–Be careful if you define new keywords
A Simple C++ Program
Comments
program
Compiler Directive
Main Function
Braces
Statements
program ";
//Simple C++ Program
//
// Purpose: To demonstrate the
// parts of a simple C++
#include <iostream.h>
main ( )
{
cout << "This is a simple
return 0;
}
Comments
• Document what is happening, why it is happening
and other issues
• Commentary is ignored by the compiler
• C++ has inline, block and documentary comments
–Inline comments are within line of code
• Use the // symbols
–Block comments are long comments delimited with /*
and */
Compiler Directives
• Instructions to the compiler rather than part
of the C++ language
– Most common directive is #include
• #include <iostream.h>
– A .h file is a header file. It serves as a link between
program code and standard C++ code needed to make
programs run
Functions
• A function is a block of code that carries out
a specific task
• Every C++ program has a main function
that executes when a program initiates
– Includes open parenthesis to designate a
function
– Ends with a return 0; statement
Scope Delimiters
• A symbol or pair of symbols used to define
a region or area which is considered a locale
• In programming, many structures need to
have their scope defined because they
should not affect the entire program
– In C++, the symbols ‘{‘ and ‘}’ are used
Semicolons
• There must be a semicolon after every
statement
– To tell the compiler that the statement is
complete
– Function definitions and compiler directives are
exempt
Variables
• Variables or identifiers are used to hold
information
– Usually mixed case with the first letters small
and the rest starting with a capital
– e.g. theWeight
Literals
• Literals are system commands and other
pieces of information that the compiler
doesn’t understand, and therefore, takes
your word for them
• In C++, literals are enclosed in straight
double quotes " " which is the shift of the
apostrophe
C++ Control Structures
1. "Sequence statements" are imperatives
2. "Selection" is the "if then else" statement
–
AND, OR, NOT and parentheses ( ) can be used for compound
conditions
3. "Iteration" is satisfied by a number of statements
–
–
–
"while"
" do "
"for"
4. The case-type statement is satisfied by the
"switch" statement.
–
CASE statements are used for most non-trivial
selection decisions
Variables
• Used to store values in virtually every
computer program
– Used for “remembering” things during
program execution
– Variables have names, types and values
• Values can change during execution
Data Types - Whole Numbers
• To store whole numbers in a variable, we
use a variable of the int data type.
– An int variable uses 4 bytes of memory.
– An int variable can store a number as low as
-2,147,483,648.
– An int variable can store a number as high as
2,147,483,647.
Data Types - Decimal Numbers
• To store decimal numbers in a variable, we
use a variable of the double data type
– A double variable uses 8 bytes of memory
– A double variable can store a number as low as
-1.7 x 10308
– A double variable can store a number as high
as 1.7 x 10308
– A double variable can store a number with up
to 15 digits of precision (significant digits)
Data Types - Characters
• To store a letter or a single character (such
as #, $, *, etc.), we use a variable of the
char data type.
– A char variable only uses 1 byte of memory.
– A char variable can only hold one letter, digit,
or character.
Data Types – Words / Phrases
• To store a word or phrase (string value), we
use a variable that is a string
– Technically string is not a data type
– You can think of it as a data type for now
Using Variables in C++
• Variables must be declared before they are used in
C++. Get into the habit of doing this at the top of
your functions
char grade;
// a students semester grade
int numStudents; // number of students in our class
double price;
// price of item
string userName; // user's name
Variable Names
• Choose your own variable names but you
must be careful to use valid ones:
– do not use keywords that are defined in the
programming language (Reserved Words)
– do not include spaces or other disallowed
characters
– do not use more than 255 characters
– do begin the identifier with a letter
Initializing Variables
• C++ does not automatically initialize all
variables to the value 0
• If you do not initialize a variable, the
variable will have an indeterminate value .
Initialize your variables at the same time
that you declare them.
Constants
• Sometimes you need to use the same value
many times throughout a program. In this
case, it is proper to use a constant rather
than a variable
• Constants allow you to give a name to a
value used several times in a program
• The value never changes
The Assignment Operator
• The assignment operator is the equal symbol (=)
• The assignment operator changes the value of the
variable to its left after evaluating the expression
on its right
• For example:
– sum = 3 + 1000;
• The variable sum ends up with the value 1003
–
–
–
–
salary = 40000;
poundsPressure = 15 + 12;
sum = original + 300;
salary = salary + raise;
Common Arithmetic Operators
+
*
/
%
for addition
for subtraction
for multiplication
for division
for modulus (like finding the remainder
of a division problem)
Compound Operators
• Example 1:
j += 1;
// is the same as j = j + 1
• Example 2:
total /= 2;
// is the same as total = total / 2;
Increments and Decrement
• The incrementing (++) and decrementing (--)
operators are useful at times if used carefully
• counter++;
• is equivalent to counter = counter + 1;
1;
and
counter +=
and
counter -= 1;
• counter--;
• is equivalent to counter = counter - 1;
• Use the incrementing and decrementing operators
with variables in statements such as these, that is
with no other operators or code except the variable
name that is being incremented or decremented.
Decision Making In Computers
• A circuit quite simply allows one out of two
choices to be made depending on its inputs
• When decisions are made in a computer program,
they are simply the result of a computation in
which the final result is either TRUE or FALSE
• The value zero (0) is considered to be FALSE by
C++. Any positive or negative value is considered
to be TRUE
Using Relational Operators
• Relational operators provide the tools with
which programs make decisions
==
equal to
NOTE: this is two equals symbols next to each
other, not to be confused with the assignment operator, =
>
greater than
<
less than
>=
greater than or equal to
<=
less than or equal to
!=
not equal to
Order of Logical Operations
•
Logical operators may be mixed within
evaluation statements but the following
order of preference must be respected:
1. NOT operator (!)
2. AND operator (&&)
3. OR operator (||)
Complete order of operations
• The complete order of operations including all of
the arithmetic, relational, and logical operators
including all of the basic arithmetic, relational, &
logical operators is:
*, /, %
+, <, >, <=, >=, ==, !=
!
&&
||
String Literals
• A string literal is a sequence of characters that is
used in a C++ program between double quotes
such as in the statement
cout << "Hello world!";
where "Hello world!" is the string literal
• Note: that the string literal, in this case, includes a
space and an exclamation point
• Similar to a constant
• Ends with an invisible null terminator (ASCII 0)
– Represented as \0
Character Arrays
• Used to store strings that change as the
program runs
– Unlike string literal
• An array is a group of variables of the same
data type that appear together in memory
– In this case each variable holds a character and
the last variable in the string holds the null
terminator (/0)
Using Strings In Programs
• In order to use string variables within any
C++program, you must use the compiler directive:
#include <string.h>
• At the top of your program. You must also refer to
iostream.h header file as iostream
#include <iostream.h>
• you must add the statement below your last
#include directive :
using namespace std;
String Functions
• You can determine the current length of a string
with the use of a string's length function. For
example:
string name = “Paul";
int lengthOfName = 0;
lengthOfName = name.length( );
cout << "His name is " << lengthOfName << "
letters long.";
More cstring Functions
• strcpy
– char [] strcpy (char[] dest, const char[] src);
• Copies the content of src to dest and returns dest
• strlen
– Size_t strlen (const char[] string);
• Returns the length of string
Library functions manipulate
strings
• length function
stringLength = userString.length( );
• To compare two strings
if (string1 = = string2)
• Test two strings alphabetically
if (string1 < string2)
{
cout << "string1 comes before string2
alphabetically ";
}
Input Operations
• The operator >> is known as the input
operator. It is also known as the extraction
operator
• You use the input operator in statements
like,
cin >> numItems;
which would allow the user to input a
value to be stored in the variable
numItems.
Complexities of Word Input
• Some things are done automatically with >>
– get does not skip over line breaks and spaces
• If the user enters a string longer than the length
specified in the call to the get function, the
remaining characters are left in the input stream
• Get always ignores the new line character (‘\n’)
and leaves it in the stream
• Use the ignore function to flush the contents of the
input stream
cin.ignore(80, ‘\n’);
Using setf and unsetf
• Each stream has format options that can be
changed
OPTION
DESCRIPTION
left
right
showpoint
uppercase
showpos
scientific
fixed
Left-justifies the output
Right-justifies the output
Displays decimal point and trailing zeros for
floats
Displays e in scientific as E
Displays a leading plus sign
Displays floating point number scientifically
Displays floating-point in normal notation
Using Manipulators
• You must include the <iomanip.h> header file at
the top of your program in order to use the
setprecision, setw, and other manipulators. You
must use place the following compiler directive at
the top of your program.
#include <iomanip.h>
• I/O manipulators are placed directly in the output
statement
cout << setprecision(2) << price << ‘\n’;
Decision Making in C++
1.
2.
3.
4.
if statement
switch statement
? conditional operator statement
goto statement
IF-THEN
Entry
Test
condition p
Exit
false
true
True
statement a
IF…ELSE
Entry
Test
condition p
false
“false”
statement a
true
Exit
“true”
statement a
General Form
if (test expression)
{
True-block statements;
}
else
{
False-block statements;
}
next statement;
General Form
if (test expression)
{
True-block statements;
}
else
{
False-block statements;
}
next statement;
Switch Structure
• The switch structure is a multiple-selection
structure that allows even more complicated
decision statements than a two-way if/else
structure allows.
• It chooses one of the "cases" depending on the
result of the control expression.
• Only variables with the INT or CHAR data types
may be used in the control expressions (i.e.
parentheses) of switch statements.
– Single quotes must be used around CHAR variables
– Single quotes are NOT used around the integer values
Iterate
• A program loop is a
form of iteration. A
computer can be
instructed to repeat
instructions under
certain conditions.
No
Syntax of a for Loop
for (initializing expression; control expression;
step expression)
{
// one or more statements
}
• The initializing expression sets the counter
variable for the loop to its initial value.
• The control expression ends the loop at the
specified moment.
• The step expression changes the counter variable
• Semi-colons, not commas, divide the expressions
WHILE Loop
Entry
Exit
No
Test
condition p
Yes
Loop
statement a
While Loop Syntax
while (control expression)
{
// one or more statements
}
• The control expression must evaluate to
TRUE in order for the while loop to iterate
even once
DO WHILE Loop
Entry
Loop
statement a
Test
condition p
Exit
No
Yes
Do While Syntax
do
{
// body statements would be placed here
}while (control expression);
• Don't forget to include the required semicolon
after the control expression
In Summary
• Loops
– goto loops
– for
– while
• while (true)
– do … while
-- simple if…then structure
-- fixed number of loops
-- may never be run
-- always true, needs break
-- always run once
• continue causes while, do… while, and for loops
to start over
• break causes while, do … while, for and switch
statements to end
An Example of A Function
#include <iostream.h>
void printMyMessage(int numOfTimes); // PROTOTYPE and NAME
int main( )
{
int userInput = 0;
cout << "Enter a number between 1 and 10 (0 to Exit): " ;
cin >> userInput;
if (userInput != 0)
{
printMyMessage (userInput); // CALL STATEMENT WITH ACTUAL PARAMETER
}
else
cout << "Thanks, Bye!";
return 0;
} // end of main
void printMyMessage(int numOfTimes) // FUNCTION HEADER WITH RETURN TYPE AND ACTUAL PARAMETER
{
int i=0; // LOCAL VARIABLE WITHIN THE FUNCTION
for (i=0; i<= numOfTimes; i++)
// BODY
{cout << "Let's Go State!!" << endl;}
// OF THE
} //end of printMyMessage
// FUNCTION
Scope of Variables
• The scope of a variable is the area in which it can
be legally referenced
– Variables are either global or local in nature
– Global variables are ones that are declared outside and
above the main function
– They can be used in any function throughout the
program.
• It is not wise to use global variables any more than you have
to.
– Local variables are ones that are declared inside of a
function, including main. They cannot be used or
referred to in other functions
Passing Data
• Data is passed to functions as arguments
• When a function is "called" by the main function one
or more arguments are passed to the function
• On the receiving end, the function accepts these
arguments
• The variable names of the arguments from the
"calling" function do not have to be the same as the
names in the "called" function.
– The data types of the arguments and the parameters should
match exactly
Required Compiler Directives
• Any program that uses file pointers must
include the fstream.h header file with the
compiler directive,
#include <fstream.h>
at the top of the program
Preparing to Use Files
• Opening a sequential-access file
ofstream outfile;
– ofstream is a C++ keyword indicating the type of
pointer that you created
– outfile is simply the programmer's chosen name
for the file pointer (and can be any valid name)
• Open the file "mydata.txt" that is stored on
your PC's hard drive
outfile.open("mydata.txt", ios::out);
or the shorter version
outfile.open("mydata.txt");
– output (out) is the default type of access for ofstream
objects
Reading From a File
• Declare a file pointer as an ifstream object
with:
ifstream infile;
– ifstream is a keyword and infile is the name for
the file pointer.
• Open the actual file for reading with:
infile.open("mydata.txt", ios::in);
or the shorter version
infile.open("mydata.txt");
Preparing to Write Output
• It is wise to check to make sure that there
wasn't an error actually opening the data file
• One can use an if statement like the following
to protect the program from crashing.
if (outfile) // same as
if (outfile != 0)
{
outfile << "John Doe" << endl;
}
else
{
cout << "An error occurred while opening the
file.\n";
}
Writing Output
• To write data to a sequential-access data file
you would use a statement like:
outfile << "John Doe" << endl;
to print that name to the next line in the data
file pointed to by the file pointer, outfile.
Appending Data
• Adding data to the end of a sequential-access data
file is called appending
• Open the file using the ios::app stream operation
mode as in:
outfile.open("myfile.txt", ios::app);
• where the app is short for append.
• If you accidentally open the file with the ios::out
mode, you will end up overwriting data in the file
because C++ will write the first piece of outputted
data at the beginning of the sequential-access data
file
Detecting the End of a File.
• Use the eof function to determine whether the end
of a sequential-access file has been reached.
• This function returns a 1 (true) if an attempt has
been made to read past the end of the file.
do
{
infile >> x;
if ( !infile.eof( ) )
{
cout << x << endl;
}
} while ( !infile.eof( ) );
Pointer Use in C++.
• A pointer is a variable or constant that holds
a memory address
– a) Hexadecimal numbers are used for
representing memory locations
216793
216794
216801
…
216801
216802
3
i
iptr
Intializing Pointers
• Declare pointers before use, as with other
variables.
• Each variable being declared as a pointer
must be preceded by an asterisk (*).
• Initialize pointers before use to a 0, NULL
or an address to prevent unexpected results
Pointer Operators
• & is the address operator which returns the
address of its operand
• * is the indirection operator or
dereferencing operator and returns the value
to which the operand (pointer) points.
• sizeof - used to determine the size of an
array during program compiliation
Structures
• Structures group variables together in order to
make one's programming task more efficient.
– Any combination of variables can be combined into one
structure.
– This is a useful and efficient way to store data.
struct Student
{
string socSecNum;
string lastName;
string firstName;
int pointsEarned;
double gpa;
};
CPS120: Introduction
to Computer Science
Lecture 15
Arrays
Arrays: A Definition
• A list of variables accessed using a single
identifier
– May be of any data type
• Can be single or multi-dimensioned
• Vector classifications are object-oriented
representations of arrays
Declaring an Array
• To declare an array before it is used in the body of
your program, you must use a statement like:
int scores[10];
• This would declare an array of integers, named
"scores".
• In this case, scores can store up to 10 different
integer values.
– The positions of the array are identified by their index
positions which run from 0 to 9 (not 1 to 10.)
• Each one of the 10 variables in scores is called an
element
Initializing an Array
• If you wish to initialize each element of an array
to a specific value, you can use the statement,
int scores[] = {65, 76, 45, 83, 99};
• You don't even have to specify a size of the array
in this case since the initialization statement
would cause the compiler to declare an array of
size 5 since there are five values in the set of curly
braces
Loops and Arrays
• Use loops in conjunction with arrays to
allow the user to input data into an array
• Use loops with arrays to display data
stored in an array
Declaring a Multi-dimensional
Array
• To declare an array of integers called
studentGrades to be a 2-dimensional array with 3
rows and 4 columns, you would use the statement:
int studentGrades[3] [4];
where the first integer value is used to specify the
number of rows in the array and the second value
specifies the number of columns
• Think of remote control
Initializing a Multi-dimensional
Array
• You can initialize the 2-dimensional array when you
declare it by using commas and braces appropriately
int studentGrades[3] [4] = {
{ 1, 2, 3, 4},
{ 5, 6, 7, 8},
{ 9, 10, 11, 12}
};
• Be careful though when assigning values to a specific
position within a 2-dimensional array.
– Just like one-dimensional arrays, the subscript positions with
regard to the rows and the columns begin at 0, not
– In the example above the value of the variable
studentGrades[0] [2] is 3