comsci final

memory

collection of data take one byte ( 8 bits)

address of pointer

the specific location in memory where a variable is stored, allowing access to its value through the pointer.

&i

pointer

is variable that contains a memory address of another

int i;

int *p; //define pointe

p=&i; // set p to be address

value of pointer

to get value of pointer,

int i= 27;

int *ptr =&i;

cout<<ptr; // print address

cout << *ptr; // print value

deref Ex

int *ptr=&i; // define pointer that point to i

cout<<*ptr; //print value of i

cout<<i; //print value same as above

*ptr=4; // change value to 4

cout<<i; //print 4

“=” assignment

pointer can be assign to other pointer with same type (null pointer)

int i,j;

int *ptri, *ptrj; //define two pointers i and j

ptri=&i; //ptri points to i

*ptri=11; //set value to 11

*ptrj=22;

ptrj = ptri; //make jptr points to the same value of i ptr

dynamic storage

allocate memory and create variables in dynamic memory during the running time with NEW operator.

variable are not lost even after function returns

int *p; //create new pointer

p = new int; //allocate space for int in dynamic and store its address to p

general syntax

[a pointer variable] = new type ;

array

store a seq of data with same data type

intA[10] //define array with length of 10

name of array are used as the address of first element in that array

int *arrayptr= A; // same as arrayptr= &A[0]

pointer arithmetic operations

pointer to array elements can do “+,-” both p+i , p-i gives us pointer

int a [20];

int *p=a; // array name is pointer

p++; // p+1 now p points to a[1]

p+=2; // p+2 now p points to a[3]

[_]operator

simple rule : for anu pointer p of an element in array then p[i] refer to the element at pointer p+i

in other words any pointer a, a[i] is same as *(a+i)

int a[10];

int *p = &a[2];

cout << p[3] ; // print value of a[5]

cout << *(p+3) // same as above

p[4] = 6; // set value of a[6]

array in dynamic

type *ptr = new type [capacity]

int *arrayptr;

int n =0;

cin>>n;

arrayptr= new int [n]; // pointer points to array in dynamic

arrayptr [3] =100; //set value of arrayptr[3]

delete operator

be sure to always to delete your dynamic variables after your done using them

for array use

delete [] ptr;

c string

is array of characters with special character “\0'“ to mark end

ex.“hi”

[h][i][ ][\o]

creating cstring

char he[] = “hello”

cout << he; // print hello

[h][e][l][l][o][\o]

pointer and cstring

char he[] = “hello”;

char *cp= he +2;

cout<< cp; //print llo

pointer example

int *p; // declare pointers p, q and s

int *q;

int s;

p = &s; // p points to s

*p = 6; // change value of p so s is 6 now

q = p; //q also points to s

*q = 8; // s is now 8

cout << s << endl; // What will it prints?

What is the difference of

ptr1 = ptr2;

and

*ptr1 = *ptr2;

int a = 10;

int b = 20;

int* ptr1 = &a;

int* ptr2 = &b;

ptr1 = ptr2; // ptr1 now point to b

int a = 10;

int b = 20;

int* ptr1 = &a;

int* ptr2 = &b;

*ptr1 =* ptr2;// Now a == 20, but ptr1 still points to a, and ptr2 still points to b

NULL pointer

int *p = NULL;

t is interpreted as “invalid, points to nothing”. (The memory does not have a address 0

array/ pointer as function parameters

It is possible to write a function that takes an array as parameter. For example:

int Func(int A[], int i){

return A[i];

}

Now we can call this function to do something with a given array.

int main() {

int arr[4] = {1,2,3,4};

cout << Func(arr, 2) << endl;

}

Note that pointer operation is involved above! Now we have learnt pointers. We try

to interpret it from the pointer perspective.

common cstring operations

Common used functions in <cstring>

strlen(char * s): strlen returns the length of its string argument. Does not count the null ʼ\0ʼ at the end

strcpy(char* dest, char* source) : Copies characters from source to dest. Copies up to, and including the first ʼ\0ʼ. Note: This function does not work in Visual Studio

strcmp(char* s1, char* s2) : Compares s1 to s2 and returns an int describing the

comparison (

strcat(char* dest, char* source):Appends characters from source to dest.

Note: This function does not work in Visual Studio

operators >> and <<: can be used for input and output

cstring function operation example

char he[]=”hello”;

cout « “str length of he : “ <<stren(he) << end;// output 5

char * cp = he + 2;

cout << "Str Length of cp: " << strlen(cp) << endl; // output 3

Abstract date type ADT

): Defining a data type by specifying what data it captures
and what operations it supports.
Data and operations are bonded together in ADT. This is call Encapsulation.

Defining a data type by specifying what data it captures and what operations it supports. Data and operations are bonded together in ADT. This is call Encapsulation.

c++ classes

is central concept of Object Based Programming. It reflects the concept of ADT. The class allows us to create new data type. Given a class, objects can be created based on the class.

Class : Blueprint

Objects : Products based on the blueprint

class construction

has two part

Declaration: Specifies class name, operations,datas.

Implementation. We write code for the member functions of the class.

Declaration

Specifies class name, operations, dates.

example:

In file Time.h:

#include <iostream>

using namespace std;

class Time {

public: // Normally functions/methods are under public

// Specifies operations for time class objects

void Set(unsigned hours, unsigned minutes, char am_pm);//Set the time

void Display(); //Display the time

private: // Normally data members are under private

// The below specifies the data stored for each object

unsigned myHours, myMinutes;

char myAMorPM;

};

implementation

We write code for the member functions of the class.

#include "Time.h"

void Time::Set(unsigned hours, unsigned minutes, char am_pm){

if (hours >= 1 && hours <= 12 && minutes >= 0 && minutes <= 59 && (am_pm = = 'A'|| am_pm == 'P'))

{

myHours = hours; //Set caller object’s “myHours”

myMinutes = minutes;

myAMorPM = am_pm;

}else

cerr << "*** Can't set these values ***\n";

}

// Display the time represented by the object

void Time::Display ()

{ cout << myHours << ':' << myMinutes <<' '<< myAMorPM << ".M.” << endl; }

using the class

In file main.cpp: (make sure the time.cpp, time.h is in the same folder.)

#include <iostream>

#include "Time.h"

using namespace std;

int main()

{

Time mealTime; // Define a Time object called mealTime

mealTime.Set(5, 30, 'P'); // Set the time of mealTime to

5:30 PM

cout << "We'll be eating at ";

mealTime.Display(); // Display the time stored by mealTime

cout << endl;

return 0;

}

// Execution:

// We'll be eating at 5:30 P.M.

constructors

are member functions in the class and are used to initialize the data members in the classes when the object is created

Example: You want to have a default value for your class objects.

Constructors do not have return type. They might or might not take parameters. Their names are the same as the class name. Multiple constructors in one class is possible.

class ClassName

{ public:

...

ClassName(); // Constructor #1. No Parameters. Default constructor

ClassName(int a); // Constructor #2. Take an integer parameter.

// You could have #3, #4, ... As long as parameters are different

...

};

implementation of constructors

// Definition of default constructor

Time :: Time(): myHours(12), myMinutes(0),

myAMorPM('A') { }

// Special syntax: myHours(12) set the object’s

// myHours initial value to 12

// Definition of explicit-value constructor

Time :: Time(unsigned initHours, unsigned

initMinutes, char initAMPM)

{ myHours = initHours;

myMinutes = initMinutes;

myAMorPM = initAMPM;

}

pointers to class objects

Time * timePtr1; // Declare a Time pointer

Time t;

timePtr1 = &t; // Now timePtr1 points to t

Syntax:

Classname * ptr;

this pointer

member functions of a class have access to a special keyword: this. this is a pointer. You can view it as a special (hidden) const pointer variable of every member function of a class. It can be used by the member function to get the address of the caller object (the object on which the member function is executed)

this pointer example

declaration:

class Time

{

public:

Time();

Time(unsigned hours, unsigned minutes, char ampm);

void Display();

Set(unsigned hours, unsigned minutes, char ampm);

private:

unsigned hours, minutes;

char ampm;

};

implementation:

Time::Time(unsigned hours, unsigned minutes, char

ampm)

{ if (hours >= 1 && hours <= 12 && minutes >= 0 &&

minutes <= 59 && (ampm = = 'A' || ampm == 'P'))

{ this->hours = hours;

this-> minutes = minutes;

this-> ampm = ampm;

}

else

cerr << "*** Can't set these values ***\n";

}

overloading functions

allows us to overloading operator and use them on classes objects

External (Non-member function) Method

step 1: In Time.h file: declare a function, named operator> (as standalone function, NOT a member function in class)

bool operator>(Time & t1, Time & t2);

Step 2: In Time.cpp file: define it,

bool operator>(Time & t1, Time & t2)

{...//Code for comparing...

//return true if t1 is later, otherwise false...}

Done! Now Time class support comparison using ʻ>ʼ!

using overload > external non member function

After the overloading, the compiler can use ‘>’ on Time objects. For Time object a and b, a > b will be translated to operator>(a,b)

#include “Time.h”

...

Time mealTime, bedTime;

......

if (mealTime > bedTime){

cout << “mealTime is later than bedTime.” << endl;

}

rule for overloading external

General rule: For operator symbol ∆ (for example +,-,<,>), suppose we have declare and define a function for named operator∆, like:

ReturnType operator∆(type1 x, type2 y)

{ ......

} //All the types are arbitrary. Take 2 parameters

After the declaration/definition:

Later when c++ sees aΔb,

Where a is type1 and b is type2

C++ will translate it to function call :

operator∆( a, b)

Internal (Member function) Method

Step 1: In Time.h file: add declaration of a member function named operator> to

Time class:

class Time {...

bool operator>(const Time & t);

// Note that it takes only 1 parameter

...

}

Step 2: In Time.cpp file: add implementation:

bool Time::operator>(const Time & t)

{ } //Code for comparing *this and t

//return true if the caller object’s time is later t’s time

using overload > internal Member Function

#include “Time.h”

...

Time mealTime, bedTime;

......

if (mealTime > bedTime)

{ cout << “mealTime is later than bedTime.” << endl;

}

rule for overloading internal

General rule: For operator symbol ∆ (for example +,-,<,>), suppose we have declare and define a member function for named operator∆ in class className, like:

class className {...

ReturnType operator∆(type y);

...

}

After this, when c++ sees a∆b, where a is className object and b is type object, a∆b translated to a function call

a.operator∆(b)

symbols to overload

basically everything but these three

. :: #

overloading <<

Question: How can we use << on Time object, like:

Time t(10,30,’A’);

cout << t << endl; // Expect “10:30 A.M.”

like so

Prototype:

ostream & operator<< (ostream & out, Time timeObj);

Definition:

ostream & operator<< (ostream & out, Time timeObj){

<Code for outputting timeObj to out>

return out; // For cascading!

}

What a list? as Adt?

Data- a list object should maintain an ordered seq of data items of same type

operation- insertion , deletion, get element at any given location, get size ( num of data item in list), check emptiness

list operations

create list object:

list 1;

insertion:

1.insert(2,0); //insert element 2 to position 0

1.insert(10,0);

1.insert(5,1);

1.insert(6,2);

erase:

1.erase(1);

access element:

cout << “item 2 is “ << 1.get(2) << endl;

get number of elements:

cout << “there are “" << 1.size()<< “elements

output:

item 2 is 2

there are 3 elements

list declaration

(assume that the list obj is used to store Element type items . element type is a token that could be replaced by int, double etc)

const int CAPACITY =1024;

typedef int ElementType;

class list {

public:

list(); // default constructor

bool empty(); // check emptiness

int size(); //getsize

void insert ( ElementType item, int x); //insertion

void erase (int pos); //deletion

ElementType get(int pos) // get item at location

private:

int mysize; // num of item inserted into list

ElementType myArray[CAPACITY]; // use array

};

memory view of list objects

important : when using array as data member the capacity must be a fixed constant number

list implementation of List, empty ,display, get

constructor does not take any parameter and set initial size as 0

list:: list(){

mysize=0;

}

getter function that provides the current size

int list:: size(){

return mysize;

}

boolean function that check whether list has no elements. It returns true if mysize is 0 (meaning the list is empty), and false otherwise.

CopyEdit

bool list:: empty(){

return (mysize ==0);

}

this function get an element from list at specified position only if the position is within the valid range ( between 0 and mysize -1) the function returns the elements at that position from the array. if position is outside of the range (less then 0 or greater than or equal to the size) the program call exit(1) to terminate the program.

ElementType list:: get (int post){

if (pos>= 0 && pos< mysize ) return myArray[pos]

else exit(1);

}

list implementation insert

void list :: insert(ElementType item, int pos){

if (mysize == CAPACITY) {

exit(1); // exit if list is full

}

if (pos <0 || pos> mysize) {

return; //return if position is invalid

}

// shift array elements right to make room for item

for(int i = mysize; i> pos; i - -){

myArray[i] = myArray [i-1]; // move element on position to right

}

//insert item at pos and increase list size

myArray [pos] = item;

mysize ++

}

list implementation erase

void List :: erase (int pos){

// check if the pos is valid

if (pos< 0 || pos>= mysize){

return; // return position is invalid

}

// shift array element left

for (int i = pos ; i< mysize-1; i++){

myArray [i] = myArray [i+1];

}

mysize - -;

}

problems of list class with static array

• stuck with one size fits all

• could be wasting space

• could run out of spaces

list declaration with dynamic array

typedef int ElementType;

class list {

public:

list (int maxsize = 1024 ); // constructors

// the following are the big three required for class to use dynamic array

~list(); // 1. destructor

list (list &origlist); //2.copy constructor

list & operator=(list & origlist) //3. overload ‘=’ operator

bool empty(); // check emptiness

int size(); //getsize

void insert ( ElementType item, int x); //insertion

void erase (int pos); //deletion

ElementType get(int pos) // get item at location

private:

int mysize; // num of item inserted into list

int myCapacity; // cap of array

ElementType * myArrayPtr; // pointer to dynamic array

};

implementation of constructor

initalize the object to empty list

list ::list (int maxsize){ // user define cap

mysize= 0;

mycapacity = maxsize;

myArrayPtr =new ElementType[maxsize]

big three - 1. destructor: ~list();

Problem: when list object is destroyed the dynamic memory still there unless we let the system reclaim it causing memory leakage

solution: destructor is special member function that is called automatically when the object is destroyed

destructor

declaration:

~list();

implementation:

List ::list (){

delete [] myArrayPtr;

}

big three 2. copy constructor: list(list & origlist)

c++ adds a default copy constructor for classes we define. takes another object as parameter. allow the user to make copy ex

time mealtime;

mealtime.set(5,30,’a’);

tiem teatime(mealtime); // this create time object teatime which is a copy. this is called shallow copy

deep copy

• Shallow copy means that the new object just points to the same array as the original object, meaning changes to the array in one list would affect the other.

• Deep copy means that the new object allocates its own array and copies the elements from the original list. Changes to the array in one list will not affect the other.

copy constructor

declaration:

list (list &origlist);

implementation:

list :: list (list &origlist){

mysize = origlist.mysize; // copies size of orig to new list

myCapacity = origlist.myCapacity; //copies cap of orig to new list

myArrayPtr = new ElementType [myCapacity];

for(int i= 0 ; i < mysize; i++){ //loop copies the element from orig list and assign to new list

myArrayPtr[i] = origlist.myArrayPtr[i];

}

then the following will work

list copy(origin); //create a new list named copy which is a deepy copy of list origin

big three 3. overloading = operator

let listCopy and alist be 2 list object now we want to assign list to listCopy which means alistCopy becomes identical to list

listCopy= list

by default this does a shallow copy

= operator

declaration:

list & list :: operator=(list & origlist);

implementation:

list & list :: operator=(list & origlist){

if (this != & origlist){ // safety check for list = list

delete[] myArrayPtr; //deallocate current array

mysize = origlist.mysize; //copy size

myCapacity = origlist.myCapacity; //copy cap

myArrayPtr = new ElementType [myCapacity]; //allocate new array

// copy origlist array into this new array

for (int i = 0; i< mysize; i++){

myArrayPtr[i]= origlist. myArrayPtr[i]

}

return *this

}

problem with list class with dynamic array

with dynamic array, our list class allow us to set cap of list when created but sometimes its hard to predict how many items you need

linked list

is data structure to store seq of data. each item is stored in a node. nodes are chained together

linked list constructed by

a list of nodes chained together by pointers.

each nodes contain:

• data part - stores an element of list

• next part - stores link/pointer to next element when no next element, null value

a pointer to the first node (head pointer) is maintained. we use it to acces the linked list

setting up linked list

// declaration of node class

// we use it for storage only so no member function

class node {

public:

type date; //stores a data items of type

node *next; // pint to next node in list

};

working with nodes

declaring pointers

node * ptr;

allocate

ptr = new node;

set member value

prt→data = 5;

ptr→next= NULL;

now we have a linked with only 1 node its first element is pointed to by ptr

adding more nodes

ptr→next=new node;

(ptr→next)→ next = NULL;

(prtr→next) →data = 14;

inserting 19 between 5 and 14

node * p1 = ptr ; // create node p1 and points to ptr

node*p2= ptr→next; // create node and points to 14

p1→ next =new Node;

(p1→next)→data = 19

(p1 → next)→next =p2

printed linked list

void display (node * first ){

node* curr= first; // create pointer that points to first

while (curr != NULL){ //stops when node =null

cout <<(curr→data)<<“ “; // get data

}// curr iterates all nodes in the linked list // make curr points to next node

cout << endl;

}

template for code for doing something to every node of linked list

Void DoSomething (node *first){

node *curr = first

while( curr != NULL){

…. do something with the node

curr= curr→ next; // update curr let it points the next node

}// curr iterates all nodes in linked list

}

ex of function that return sum of all nodes:

int Sum(node *first){

node *curr = first

int sum =0

while( curr != NULL){

sum += curr→data;

curr= curr→ next;

}

return sum;

}

insertion linked list

void insert( node * & first, int position, type date){

if (position ==0){

node * temp = first; // save the current head of the list in temp

first = new node; // create new node and assign it to first

first→ data = data; //set the date of the new node

first→ next = temp; // make the new node point to the old head

}

else{

node * prev = first; // set prev to the head

int prevIndex=0

while (prevIndex < position -1){ //traverse to the node just before the insertion point

prev = prev→next; // move prev to the next node;

prevIndex ++;

}

node * temp = prev →next; // save the node after the insertion point in temp

prev→next= new node; // create a new node and assign it to prev→ next;

(prev→next)→data= data; //set the data of the new node

(prev→next)→next=temp; /// make the new node point to next node after the insertion

}
}

deletion

void remove (node * & first, int position) {

if (position ==0){

node * temp= first;

first= first→ next;

delete temp;}

else {

node * prev = first;

int prevIndex= 0;

while(prevIndex < position -1){

prev = prev→ next;

prevIndex++;

}

node* temp = prev→next;

prev→next= prev→next → next;

delete temp;

}

}

linked list pros and cons

advantages:

• insert new item without shifting

• delete existing item

• can expand. contract as necessary

disadvantages:

• need pointer to next node

• access of nth now less efficient must go through first element then second then third etc.

class list using linked list

stacks

is kind of a very useful container. last in first out style

stack operation

top() return the top element

push() insert new element to the top of the stack

pop() remove the top element

infix and postfix esperssion

evaluating expressions

evaluation with stack

24×95+-

infix version:

(2×4)-(9+5)

using built in stack

c++ has built in stack to use it include the header

#include <stack>

stack<int> intStack; // create a stack named intStack which stores int

intStack.push(5);

intStack.push(10);

intStack.pop();

stack implementation using stack array

data member:

int myArray[CAPACITY]; //stores the data

int my top; //index of the top element

adding another item

empty stack

stack implementation using dynamic array

data members:

int *myArray; //stores the data points to dynamic array

int mytop: // index of top element

int myCapacity // cap of stack

stack implementation using linked list

data members:

node *myTop; // points to the top/first node

stack push implementation using linked list

implementing push():

node *temp = new node();

temp → next = myTop ;

temp → data = <data value>;

myTop = temp;

queue

is very commonly used container its a first in first out style

we can only access/remove the front element. new elements are inserted of the back of the queue

queue operation

enqueue(); add an elements to the container

Front(); return the value of the first element

dequeue(); remove the first element

queue visualization

built in queue

to use include the header:

#include < queue>:

queue<int> intQ; //create queue name intq and stores int

intQ.push(5); // push = enqueue

intQ.push(10);

intQ.pop(); // pop = dequeue

queue class

operations:

constructors

empty // check if empty

enqueue // add element to front

front //return value at front

dequeue // remove element form front

Data;

store seq of data using array or linked list

queue with array

int myArray [queue_capacity];

int myfront , myback;

queue class using array operations

enqueue:

myArray[myBack]= x;

myBack=(myBack +1) % queue_capacity;

dequeue:

myfront = (myfront +1) % queue_capacity;

front:

return myArray[myfront];

empty:

return (myfront ==myback);

queue with linked list

data:

node * myfront;

node * myback;

front();

return myfront→data

dequeue():

delete first node (watch for empty queue)

enqueue():

insert node at end list

templates

allow us to create function /class for different type of daat perform similar tasks

function reusability

ex of code to swap values stored in the two int variables

void swap( int& first, int& second){

int temp = first

first= second;

second =temp

instead of rewriting those 3 lines every time we need to swap just swap(x,y)

function genericity - overloading

write another function of the same name

}

second =temp

}

swap function templates

all types of swap functions has similar format

void swap( _____& first, _____& second){

_____temp = first

first= second;

second = temp;

}

can we write something like this so that we can fill types conveniently as needed without writing everything again

solution= templates

syntax of function template

declare a type of parameter T also called a type placeholder. use it in the function instead of specific type

template <typename T>

void swap(T &first, T &second){

T hold = first;

first=second;

second= hold;

}

the keyword typename can be replaced by keyword class int he type parameter list T can be any symbol

using template

suppose the swap template is defined

int a,b;

swap<int>(a,b);

double c,d;

swap <double>(c,d);

general form of template

template <typename t>

function definition

template max ex

template <typename T>

T max(t a, T b){

if (a>b) {

return a;

}else {

return b:

}