Transcript CS212-01-Basic+ADTsx

CS212
Programming-II
for Engineers
Spring 2013
1
Chapter
Topic
1
Basic Data Elements & Numeric arrays
2
More ADTs & functions, Intro to Complexity
3
Linear list structures & recursion
1. Queues (using arrays)
2. Linked lists
a. Stacks & Queues with pointers
b. Prefix, postfix & infix notations
4
General Lists & Strings
5&6
Searching, binary trees & Big O again
class
slides
only
addenda
1. C++ classes, objects, methods &
"friends"
2. I/O, iostream, etc.
7
Sorting
8
Hashing
9
Trees (general)
Encoding & Compression (Huffman)
11
Graphs (time permitting)
2
Course Material
• Syllabus and other course information available
at:
– dforeman.cs.binghamton.edu/~foreman
• Makefiles:
• http://www.gnu.org/software/make/manu
al/make.html
• http://www.cprogramming.com/tutorial/m
akefiles.html
3
Some rules for CS212
• This is primarily a course in Data Structures!
– principles are language independent
• We will be using C and C++
• Platforms
– Lab: Linux
– Cygwin is NOT acceptable
– Programs submitted must compile using the GNU
compiler: G++
• Review makefiles. See links on previous
page.
Some Course Goals
• Use common organizations of data in RAM
• Learn to evaluate efficiency
– memory space (RAM) needed for storage
– algorithms to manipulate the data
• Learn to define, implement and use
– Structured data types
– Basic Abstract Data Types (ADTs)
• Learn to use libraries of data structures
– STL, Java Collection classes
5
ANSI C++ Compilers
• GNU compiler
–
–
–
–
–
open source software from the Free Software Foundation
www.gnu.org
available on Bingsuns & labs in LNG103
built-in on most Linux systems
Cygwin is a Linux-like environment (including the GNU compiler) for
Windows (sources.redhat.com/cygwin/) – UNACCEPTABLE!!
• Microsoft Visual Studio
– integrated editor, compiler, linker, project manager (IDE)
– installed on all Computer Center PCs and in Watson Microlab
– free to students in Watson courses through the Microsoft Academic
Alliance (see Prof. Foreman's website for link)
6
Development Process

Java is an interpreted
language

C & C++ are compiled
languages
Source code
Myprog.java
Source code
Myprog.cpp
Interpreter
Compiler
byte-code file
Myprog.class
Object Code file
Myprog.o
CPU
Executable file
Myprog.exe
MUST have interpreter to run Java pgm
CPU
Data + Algorithms = Programs
• Every program processes data
• Data is stored in memory (RAM) at run-time
• Java, C, C++ are strongly typed languages
– all data items have a type associated with them
• Data to be processed must be declared as data objects
(variables) using this syntax (for C, C+++ & Java):
type name;
type name = value;
• Type of a data object determines
– Allowable operations (+ - * / etc.)
– how data is represented in memory (integer, float, etc.)
8
Program structure – pt 1
-preprocessor directives
(control compilation)
(include header files}
-global declarations
(constants and types only!)
myProg.c or
myProg.cpp
-function prototypes
(names & parameters only)
main
f1
....
fn
function definitions
(implementations)
compile / link / execute
Myprog.cpp
#include “myinfo.h”
Yourprog.cpp
#include “myinfo.h”
object's methods
Myprog.o
Yourprog.o
Ourpgm.exe (a.out is a default name)
10
Linux Compiler Commands
g++ -c Myprog.cpp
produces Myprog.o
g++ -c Yourprog.cpp
produces Yourprog.o
g++ -o Ourpgm Myprog.o Yourprog.o
produces Ourpgm
./Ourpgm
executes the program
g++ Myprog.cpp
produces a.out
compile
only
link
execute
compile
& link
11
Types
• Pre-defined (built-in) types
– scalar (atomic) types – store a single value
•
•
•
•
int
char
float, double
bool
– structured types – store a collection of values
• Most languages have libraries of types
– STL for C++
– Java library
• Programmer-defined types
– create new "types" appropriate for your problem
– built from pre-defined types
12
Types - 2
• An int is 8, 16, 32 or 64 bits
– defined at compile time
• Size of float/double depends on machine arch.
• A char is USUALLY 8 bits
– Has a numeric value 0-255
– Represents a printable symbol
– Some embedded systems may have 16 bit char's
– Arithmetic with a char is invalid (e.g.; char+char)
• A bool is a single T/F value –
– stored as a whole byte(?) - Compiler defined
13
typedef
• Allows using the name of an element as a
datatype
• Does NOT reserve space for the element!!!
• Uses no memory
14
Types - 3
• uint8_t is a typedef for unsigned char
• Why use it?
– Indicates intent – you will do math with it.
– Char is printable data in range 32-126 (decimal)
– 0-31 and 127-255 are for other uses
• but all 256 values are legal
– Examples:
unsigned char i, x='a', y=0x01; i=x+y; // unclear
uint8_t x='a', y=0x01; i=x+y
// is clear.
(both output 'b' as the value of i)
15
C++ Types
Composite Types
Structured Types
Scalar Types
Arithmetic
Integral
Floating point
(reals)
Characters
Enumerations Integers
char
unsigned char
signed char
void
bool complex
float
double
long double
int
short int
long int
unsigned
short unsigned
long unsigned
pointer
array
struct
union
class
C++ Standard
Library classes
istream
ostream
iostream
ifstream
ofstream
fstream
string
vector
deque
list
stack
queue
priority_que
ue
map
multimap
set
multiset
bitset
valarray
16
C vs. C++
• C++ is a superset of C
– allows ALL of C syntax
– adds NEW syntax for
• objects
• I/O
• namespaces
• Any C program is a valid C++ program
– even if it does not use any of the ++ syntax
– compiler knows by the file extension
• c vs. cpp
17
namespaces (C & C++)
• "namespaces" allow you to assign portions of
your program to different namespaces
– variable names are local so they may be reused in a
program as long as the uses are in different
namespaces
using namespace std;
– the namespace “std” is a little special
• you don’t have to specify the “.h” for all standard
#includes
• e.g.; #include <iostream>
#include <iomanip>
Structured data types – C arrays
• One name for a collection of items
• Subscripted (as in standard math notation)
– X3 is represented as X[3]
– There are no subscript keys on a keyboard!
• Multiple values
– X[0], X[1], etc.
– All elements are same type
– Max # elements must be a constant (in C, C++, Java)
(for non-dynamic arrays)
int x[20];
float y[2012];
19
Arrays - 2
int X[5];
X[0]
X[1]
X[2]
X[3]
X[4]
x[3]=17;
17
X[0]
20
Arrays - 3
• C does not have an "array" data type
• C uses a simple variable with subscript notation:
int x[5]; // BUT
– max subscript value in definition must be a constant
– int x[y]; // is ILLEGAL, even if y has a fixed value
• all arrays start at element 0
– above is x[0] … x[4]
• C allows multi-dimensioned arrays (like Xijk)
int y[3][4][2]; y[0][2][1]=17;
21
Arrays - 4
• compiler ALWAYS reserves memory for the ENTIRE array,
whether it is used or not
• arrays may be ANY data type, including structs
• no protection on accessing beyond real size
int x[5]; x[5]=3; // ERROR at RUNTIME
compiler might not detect it!!!!!
the array has 5 items, numbered 0-4
int j; scanf("enter j%i",j); x[j]=3;
compiler CANNOT detect it!!!!!
22
Structured data types - more
• "struct" – a simple collection of items
• "union" – multiple types for the same RAM
bytes
– union {char a,b,c,d; int X;}
– "a" is the leftmost byte of "X"
• "class" – data + functions that operate on it
– this is in C++,later in course
• All allow collections of dissimilar types
23
struct's
• A way to combine basic elements
– Create collections of elements
– Treat them separately AND/OR as a collection
– Use them to create more complex elements
• Complex numbers
– Real part
– Imaginary part
24
struct's – an example
struct Complx
{float my_real_part;
float my_imag_part;
};
// note the semicolon!!!!!
Complx c; // "c" now refers to BOTH parts
c.my_real_part=5.2;
c.my_imag_part=3.6;
// this is equivalent to 5.2+3.6j
25
Pointers
• a pointer is a memory address (points to some data)
• lets you refer to data without the data's name
int x[5] ;
// this takes up 20 bytes 5*(4 bytes/int)
int *z;
// z is a pointer to an int and is 4 bytes
int (*y)[5]; // uses only 4 bytes
y is a pointer to an array of 5 ints
y=&x;
z=&x[3];
int *P[8];
// y now points at X (≠ X)
// z now points to x[3] (has x's address)
// z does not EQUAL the value in X[3]
// array of 8 "pointers to int's" (8*4bytes)
NOT the integers themselves!!!!!!
26
Dynamic allocation
• Often need to make space at runtime
– Size/amount of data not pre-defined
– Data may need to be ordered by some rule (e.g.; "<")
Complx *
p; // defines ONLY the POINTER, p
// p "points" to a Complex data type
p=new Complx; //reserves RAM, p points to it
p->my_real_part=3.5; p->my_imag_part=5.6;
// equivalent to 3.5+5.6j
27
Abstract Data Types (ADTs)
• Collection of data items + operations for it
• Independent of programming language
• 2 parts:
– Definition – of data and operations allowed
– Implementation – how data is stored and algorithms to
carry out the operations
• User –
– uses the ADT to solve a problem;
– doesn't need to know the implementation details
– Needs to know the syntax rules for the ADT
28
The Basic Concept
An ADT encapsulates data
and the operations on that
data.
The data can be accessed
only via the operations &
operators.
Operations
(methods)
data
29
ADT vs. Class
• ADT: a model of data AND its related functions
• C++ Class: a syntactical & programmatic
element for describing how the functions and
data are related
• An ADT implementation has several parts:
– interface function-names (methods)
– operators (possibly re-defined symbols)
– data
• Any/all of these may be public or private
30
ADTs - example
struct Complx
{
float my_real_part;
float my_imag_part;
};
// note the semicolon!!!!!
• All elements "visible"
31
C++ console I/O
• #include <iostream>
• basic operators
– << the "insertion" operator
– >> the "extraction" operator
• stream names for standard I/O
– cin
– cout
is the input "file"
is the output "file"
• usage
– cin>>x;
– cout<<x;
// get a value
// output a value
32
Operators
• Ordinary variables have basic operators built-in
+ - * / % | & || &&
• New objects (structs, classes) may need more
• How do you "add" 2 complex numbers?
• Given: complex#'s a and b;
– what does a+b mean???
– compiler knows nothing about complex #'s
• Define a NEW action (function) to perform "+"
– add the real parts, add the imaginary parts
– store each result in the proper answer-part.
33
Example – Declare the functions
struct Complx
{ float my_real_part,
my_imag_part;
};
// below are member functions (i.e.; "methods")
float Complx_get_real(return my_real_part); // not shown
float Complx_init(set my_real_part); // not shown
Complx Complx_add(add 2 complexes); // not shown
// orange: declare the structure, green: use it, red: return-value
34
Example- implementation
// no automatic functions for initialization
Complx x;
Complx_init(Complx *x, float a, float b)
{ x.my_real_part=a;
x.my_imag_part=b;
}
Complx Complx_add (Complx a, Complx b)
{Complx tmp; // need a place for output
tmp.my_real_part = a.my_real_part + b.my_real_part;
tmp.my_imag_part = a.my_imag_part + b.my_imag_part;
return tmp;
}
// orange: declare the structure, green: use it, red: return-value
35
Example-pt 2
void main()
{
Complx A, B, C;
init_Complx (*A,2,2);
init_Complx (*B,1,1);
C=Complx_add(A,B);
printf("C=%d+%dj",C.myreal_part,
C.my_imag_part);
}
36
Program structure – 2
• Usually, put the struct definition in a header
file
• #include it later in BOTH :
– the implementation file
• where the methods are defined
– the user-program file
• where methods get used
37