Data Structures,
Algorithms,
and Applications in C++
Chen Peipei
March 13,2003
Chapter 1
preface
The purpose and contents of the course
? Introduce most used data structures and
algorithms
? Prerequisite of other courses
? Introduce algorithm analysis
? Review C++
The purpose and contents of the course
1,Introduce most used data structures and
algorithms,
Use proper data structures to solve different
problems.
Example,
? Game problem
? Management of library catalogue by computer
? Management of the traffic lights in intersections
The purpose and contents of the course
Example 1:
Game problem:
Next step:
x has five choices.
The purpose and contents of the course
Example 1 uses a tree structure.
The purpose and contents of the course
Example 2,Management of library catalogue by
computer
书名 作者名 登录号 分类 出版年月
It is a linear list.
D.S,Sartaj Sahni 000001 computer 2000.1
The purpose and contents of the course
Example 3:
Management of the traffic lights in intersections
C
B D
A E
C,E are one-way road,there are
13 path to go.
Can go at the same time,
A?B E?C
Cannot go at the same time:
E?B A?DThis is a graph
The purpose and contents of the course
2, Prerequisite of other courses:
? Principles of compiling, use stack to compute
expression and implement recursive procedure
? Operating System,use queue to implement job
scheduling
? Database,use B+ tree to organize,store and
load massive data in the hard memory.
...
The purpose and contents of the course
3,Basic methods of algorithm analysis
? standards of the performance of an algorithm,
time complexity,space complexity,
and accuracy
4,Review C++
What is Data Structure
1,Data
is the carrier of information,
Data is a set of numbers,characters,and
other symbols
? that can be used to describe the objective
things,
? These symbols can be input into computers,
identified and processed by the computer
program.
What is Data Structure
Data can divided into two classes:
numerical data,int,float,complex,……
non-numerical data,character,string,
graph,voice…
What is Data Structure
２, Data structure
A data structure is a data object together
with the relationships among the data
members that compose the object
Data_Structure={D,R}
Ｄ is a data object，
R is a limited set of relationships of all
the data members in D.
What is Data Structure
Linear structure
Data structure
Non-linear stucture
ADT and OO
1,Data type
Definition,is a set of values together with a
operation set that operate on these values.
Example,
int type
value set,{……,-2,-1,0,1,2,……}
operation set,{+,-,*,/,%,…}
ADT and OO
Most of the programming languages provide
a group of predefined data type.
Atom data type — int,float,double……
Structure data type—array,struct,……
ADT and OO
2,ADTs,Abstract Data Types
Abstract,is a method used to hide the
information.
Example,
int x ; float x,y:
:,
x=735; x=x*y+3.0;
:,
abstract of int data type abstract of float data type
assignment operation
ADT and OO
Abstract data type:
is a new programming method that
part the usage and implementation,in order
to encapsulate and hide the information.
ADT NaturalNunber is
? objects,一个整数的有序子集合,它开始
于 0,结束于机器能表示的最大整数
(MAXINT)。
? Function:
? Zero( ):NaturalNumber
? IsZero(x):Boolean
? Add(x,y):NaturalNumber
? Equal(x,y):Boolean
? Successor(x):NaturalNumber
? Subtract(x,y):NaturalNumber
? end NaturalNumber
ADT and OO
3,OO:
object-oriented＝ object＋ class＋ inherit＋
communicate
object=attribute values+ operates
class,objects of same attributes and operates.
an instance is an object of the class.
different object has deferent attribute
value
ADT and OO
Inherit:
base class—integrate the same part (including
attributes and operations) in all the
derived classes
derived class—add the specific attributes and
operations to the base class
? Example,base class—polygon
derivedclass—quadrilateral,triangular
ADT and OO
Communication,each class object
communicate with others using messages.
Message,instructions that one class object
used in order to require another class object
to perform some operation,
Algorithm definition
Algorithm, an operation sequence of soluting
a problem
Characteristic,1.finite
2,deterministic
3,initial action
4,sequence ends
Algorithm definition
Program:
1,Program is written by languages that can be
performed by machine.
Algorithm has multiple descriptive methods,
such as language,graph,table,
2.program can?t satisfy the finiteness,For
example,OS,
Templates in C++
Problem:
program1.1:
int Abc(int a,int b,int c)
{return a+b+b*c+(a+b-c)/(a+b)+4; }
program1.2:
float Abc(float a,float b,float c)
{return a+b+b*c+(a+b-c)/(a+b)+4; }
Templates in C++
program1.1 and 1.2 differ only in the data
type of the formal parameters and of the
value returned.
We can write a generic code in which the
data type is a variable whose value is
determined by the compiler.This generic
code is written using the template statement
in program1.3
Templates in C++
Program1.3
template<class T>
T Abc(T a,T b,T c)
{return a+b+b*c+(a+b-c)/(a+b)+4; }
From this generic code the compiler can
construct 1.1 by substituting int for T and
1.2 by substituting float for T,
Parameter passing
1) Value Parameters (Program 1.1)
template <class T> T Abc (T a,T b,T c )
{ return a+b+b*c+(a+b-c)/(a+b)+4;
}
z=Abc(2,x,y);
Parameter passing
2) Reference Parameters
template<class T>T Abc (T & a,T& b,T &c )
{ return a+b+b*c+(a+b-c)/(a+b)+4;
}
m=Abc(x,y,z);
Recursive Function
1) direct recursive
2) indirect recursive
Example 1 factorial function f(n)=n!
1 n<=1 (base)
n*f(n-1) n>1 (recursive component)
f(5)=5f(4)=5*4f( 3)=5*4*3f(2)=5*4*3*2f(1)=120
f(n)=
Recursive Function
int factorial (int n)
{ if (n<=1) return 1;
else return n*Factorial(n-1);
}
Recursive Function
Example 2:
computes the sum of the elements a[0]
through a[n-1] (Program 1.9)
a[0],a[1],…,a[n -2],a[n-1]
Recursive Function
Template<class T> T Rsum(T a[],int n)
{ if (n>0)
return Rsum(a,n-1)+a[n-1];
return 0;
}
Recursive Function
Example 3:
Permutation (Program 1-10)
{a,b,c}, abc,acb,bac,bca,cab,cba
permutation of n elements has n!
Recursive Function
Template <class T> void perm(T list[ ],int k,int m)
{ int i;
if (k==m) { for (i=0; i<=m; i++) cout << list[i];
cout << endl; }
else{ for (i=k; i<=m; i++)
{ swap(list[k],list[i]);
perm(list,k+1,m);
swap(list[k],list[i]);
}
}
}
Dynamic Memory Allocation
1,New
int *y = new int ;
*y = 10;
int *y = new int(10);
Delete
delete y ; delete[] x;
y
10
Dynamic Memory Allocation
2.Exception Handling
float *x = new float [n];
? an exception occurs
float * x;
try { x=new float[n];}
catch (xalloc)
{ cerr<<“out of Memory”<<endl; exit(1);}
Dynamic Memory Allocation
3,One-dimensional Arrays
float * x = new float [n];
x[0] x[1] x[2] x[3] x[n-1]
Dynamic Memory Allocation
4,Two-Dimensional Arrays
Use dynamically allocated
two-dimensional arrays
x00 x01 x02 x03 x04
x10 x11 x12 x13 x14
x20 x21 x22 x23 x24
T ** x ;
Dynamic Memory Allocation
memory structure for a three by five array
[0] [1] [2] [3] [4]
X[0]
X[1]
X[2]
Dynamic Memory Allocation
Program 1.13
template <class T> void Make2DArray
(T ** & x,int rows,int cols)
{ x=new T *[rows];
for(int i=0; i<rows; i++)
x[i] = new int [cols];
}
Other concept C++
Class
Constructor
Member function
Operator overloading
Friends of a class
Example
void selectsort(int a[ ],const int n)
{
for ( int i=0; i<n-1; i++)
{ int k=i;
for ( int j=i+1; j<n; j++)
if ( a[j]<a[k]) k=j;
int temp=a[i]; a[i]=a[k];a[k]=temp;
}
}
Example
# ifndef DATALIST_H
# define DATALIST_H
# include <iostream.h>
template <class Type>
class datalist {
private:
Type * Element;
int ArraySize;
void Swap(const int mark1,const int mark2);
int MaxKey (const int low,const int high);
Example
public:
datalist(int size=10):ArraySize(size),Element(new
Type[Size]){ }
~datalist( ){delete[ ]Element;}
void Sort( );
friend ostream & operator << (ostream&
outStream,const datalist<Type>& outlist);
friend istream & operator >> (istream& inStream,const
datalist<Type>& inlist);
};
# endif
Example
# ifndef SELECTTM-H
# define SELECTTM-H
# include,datalist.h”
template<class Type> void datalist <Type>::Swap(const
int mark1,const int mark2)
{ Type temp=Element[mark1];
Element[mark1]=Element[mark2];
Element[mark2]=temp;
}
Example
template<class Type>int datalist<Type>::MaxKey(const
int low,const int high)
{
int max=low;
for(int k=low+1;k<=high;k++)
if (Element[max]<Element[k]) max=k;
return max;
}
Example
template <class Type> ostream& operator<<(ostream&
OutStream,const dataList<Type>& OutList)
{ OutStream<<“Array Contents:\n”;
for(int i=0; i<OutList.ArraySize; i++)
OutStream<<OutList.Element[i]<<? ?;
OutStream<<endl;
OutStream<<“Array Current Size:”
<<OutList.ArraySize<<endl;
return OutStream;
}
Example
template<classType>istream&operator>>(istream&
InStream,const dataList<Type>&Inlist)
{ cout<<“Enter array Current Size:”;
InStream>>InList.ArraySize;
cout<<“Enter array element:\n”;
for(int i=0; i<InList.ArraySize; i++)
{ cout<<“Element”<<i<<“:”;
InStream>>InList.Element[i];
}
return InStream;
}
Example
template<class Type>void datalist<Type>::sort( )
{ for( int i=ArraySize-1; i>0; i--)
{ int j=Maxkey(0,i);
if (j!=i) Swap(j,i);
}
}
# endif
Example
# include,selecttm.h”
const int SIZE=10;
int main( )
{ dataList <int> Testlist(SIZE);
cin>>Testlist;
cout<<“Testing selection Sort:\n”<<Testlist<<endl;
Testlist.Sort( );
cout<<“After sorting,\n”<<Testlist<<endl;
return 0;
}
Testing and Debugging
1,Testing
2,Debugging
Chapter 1
Exercises:
(English) P13,2,5 ; P19,7
(Chinese) P9,2,5 ; P13,7
Algorithms,
and Applications in C++
Chen Peipei
March 13,2003
Chapter 1
preface
The purpose and contents of the course
? Introduce most used data structures and
algorithms
? Prerequisite of other courses
? Introduce algorithm analysis
? Review C++
The purpose and contents of the course
1,Introduce most used data structures and
algorithms,
Use proper data structures to solve different
problems.
Example,
? Game problem
? Management of library catalogue by computer
? Management of the traffic lights in intersections
The purpose and contents of the course
Example 1:
Game problem:
Next step:
x has five choices.
The purpose and contents of the course
Example 1 uses a tree structure.
The purpose and contents of the course
Example 2,Management of library catalogue by
computer
书名 作者名 登录号 分类 出版年月
It is a linear list.
D.S,Sartaj Sahni 000001 computer 2000.1
The purpose and contents of the course
Example 3:
Management of the traffic lights in intersections
C
B D
A E
C,E are one-way road,there are
13 path to go.
Can go at the same time,
A?B E?C
Cannot go at the same time:
E?B A?DThis is a graph
The purpose and contents of the course
2, Prerequisite of other courses:
? Principles of compiling, use stack to compute
expression and implement recursive procedure
? Operating System,use queue to implement job
scheduling
? Database,use B+ tree to organize,store and
load massive data in the hard memory.
...
The purpose and contents of the course
3,Basic methods of algorithm analysis
? standards of the performance of an algorithm,
time complexity,space complexity,
and accuracy
4,Review C++
What is Data Structure
1,Data
is the carrier of information,
Data is a set of numbers,characters,and
other symbols
? that can be used to describe the objective
things,
? These symbols can be input into computers,
identified and processed by the computer
program.
What is Data Structure
Data can divided into two classes:
numerical data,int,float,complex,……
non-numerical data,character,string,
graph,voice…
What is Data Structure
２, Data structure
A data structure is a data object together
with the relationships among the data
members that compose the object
Data_Structure={D,R}
Ｄ is a data object，
R is a limited set of relationships of all
the data members in D.
What is Data Structure
Linear structure
Data structure
Non-linear stucture
ADT and OO
1,Data type
Definition,is a set of values together with a
operation set that operate on these values.
Example,
int type
value set,{……,-2,-1,0,1,2,……}
operation set,{+,-,*,/,%,…}
ADT and OO
Most of the programming languages provide
a group of predefined data type.
Atom data type — int,float,double……
Structure data type—array,struct,……
ADT and OO
2,ADTs,Abstract Data Types
Abstract,is a method used to hide the
information.
Example,
int x ; float x,y:
:,
x=735; x=x*y+3.0;
:,
abstract of int data type abstract of float data type
assignment operation
ADT and OO
Abstract data type:
is a new programming method that
part the usage and implementation,in order
to encapsulate and hide the information.
ADT NaturalNunber is
? objects,一个整数的有序子集合,它开始
于 0,结束于机器能表示的最大整数
(MAXINT)。
? Function:
? Zero( ):NaturalNumber
? IsZero(x):Boolean
? Add(x,y):NaturalNumber
? Equal(x,y):Boolean
? Successor(x):NaturalNumber
? Subtract(x,y):NaturalNumber
? end NaturalNumber
ADT and OO
3,OO:
object-oriented＝ object＋ class＋ inherit＋
communicate
object=attribute values+ operates
class,objects of same attributes and operates.
an instance is an object of the class.
different object has deferent attribute
value
ADT and OO
Inherit:
base class—integrate the same part (including
attributes and operations) in all the
derived classes
derived class—add the specific attributes and
operations to the base class
? Example,base class—polygon
derivedclass—quadrilateral,triangular
ADT and OO
Communication,each class object
communicate with others using messages.
Message,instructions that one class object
used in order to require another class object
to perform some operation,
Algorithm definition
Algorithm, an operation sequence of soluting
a problem
Characteristic,1.finite
2,deterministic
3,initial action
4,sequence ends
Algorithm definition
Program:
1,Program is written by languages that can be
performed by machine.
Algorithm has multiple descriptive methods,
such as language,graph,table,
2.program can?t satisfy the finiteness,For
example,OS,
Templates in C++
Problem:
program1.1:
int Abc(int a,int b,int c)
{return a+b+b*c+(a+b-c)/(a+b)+4; }
program1.2:
float Abc(float a,float b,float c)
{return a+b+b*c+(a+b-c)/(a+b)+4; }
Templates in C++
program1.1 and 1.2 differ only in the data
type of the formal parameters and of the
value returned.
We can write a generic code in which the
data type is a variable whose value is
determined by the compiler.This generic
code is written using the template statement
in program1.3
Templates in C++
Program1.3
template<class T>
T Abc(T a,T b,T c)
{return a+b+b*c+(a+b-c)/(a+b)+4; }
From this generic code the compiler can
construct 1.1 by substituting int for T and
1.2 by substituting float for T,
Parameter passing
1) Value Parameters (Program 1.1)
template <class T> T Abc (T a,T b,T c )
{ return a+b+b*c+(a+b-c)/(a+b)+4;
}
z=Abc(2,x,y);
Parameter passing
2) Reference Parameters
template<class T>T Abc (T & a,T& b,T &c )
{ return a+b+b*c+(a+b-c)/(a+b)+4;
}
m=Abc(x,y,z);
Recursive Function
1) direct recursive
2) indirect recursive
Example 1 factorial function f(n)=n!
1 n<=1 (base)
n*f(n-1) n>1 (recursive component)
f(5)=5f(4)=5*4f( 3)=5*4*3f(2)=5*4*3*2f(1)=120
f(n)=
Recursive Function
int factorial (int n)
{ if (n<=1) return 1;
else return n*Factorial(n-1);
}
Recursive Function
Example 2:
computes the sum of the elements a[0]
through a[n-1] (Program 1.9)
a[0],a[1],…,a[n -2],a[n-1]
Recursive Function
Template<class T> T Rsum(T a[],int n)
{ if (n>0)
return Rsum(a,n-1)+a[n-1];
return 0;
}
Recursive Function
Example 3:
Permutation (Program 1-10)
{a,b,c}, abc,acb,bac,bca,cab,cba
permutation of n elements has n!
Recursive Function
Template <class T> void perm(T list[ ],int k,int m)
{ int i;
if (k==m) { for (i=0; i<=m; i++) cout << list[i];
cout << endl; }
else{ for (i=k; i<=m; i++)
{ swap(list[k],list[i]);
perm(list,k+1,m);
swap(list[k],list[i]);
}
}
}
Dynamic Memory Allocation
1,New
int *y = new int ;
*y = 10;
int *y = new int(10);
Delete
delete y ; delete[] x;
y
10
Dynamic Memory Allocation
2.Exception Handling
float *x = new float [n];
? an exception occurs
float * x;
try { x=new float[n];}
catch (xalloc)
{ cerr<<“out of Memory”<<endl; exit(1);}
Dynamic Memory Allocation
3,One-dimensional Arrays
float * x = new float [n];
x[0] x[1] x[2] x[3] x[n-1]
Dynamic Memory Allocation
4,Two-Dimensional Arrays
Use dynamically allocated
two-dimensional arrays
x00 x01 x02 x03 x04
x10 x11 x12 x13 x14
x20 x21 x22 x23 x24
T ** x ;
Dynamic Memory Allocation
memory structure for a three by five array
[0] [1] [2] [3] [4]
X[0]
X[1]
X[2]
Dynamic Memory Allocation
Program 1.13
template <class T> void Make2DArray
(T ** & x,int rows,int cols)
{ x=new T *[rows];
for(int i=0; i<rows; i++)
x[i] = new int [cols];
}
Other concept C++
Class
Constructor
Member function
Operator overloading
Friends of a class
Example
void selectsort(int a[ ],const int n)
{
for ( int i=0; i<n-1; i++)
{ int k=i;
for ( int j=i+1; j<n; j++)
if ( a[j]<a[k]) k=j;
int temp=a[i]; a[i]=a[k];a[k]=temp;
}
}
Example
# ifndef DATALIST_H
# define DATALIST_H
# include <iostream.h>
template <class Type>
class datalist {
private:
Type * Element;
int ArraySize;
void Swap(const int mark1,const int mark2);
int MaxKey (const int low,const int high);
Example
public:
datalist(int size=10):ArraySize(size),Element(new
Type[Size]){ }
~datalist( ){delete[ ]Element;}
void Sort( );
friend ostream & operator << (ostream&
outStream,const datalist<Type>& outlist);
friend istream & operator >> (istream& inStream,const
datalist<Type>& inlist);
};
# endif
Example
# ifndef SELECTTM-H
# define SELECTTM-H
# include,datalist.h”
template<class Type> void datalist <Type>::Swap(const
int mark1,const int mark2)
{ Type temp=Element[mark1];
Element[mark1]=Element[mark2];
Element[mark2]=temp;
}
Example
template<class Type>int datalist<Type>::MaxKey(const
int low,const int high)
{
int max=low;
for(int k=low+1;k<=high;k++)
if (Element[max]<Element[k]) max=k;
return max;
}
Example
template <class Type> ostream& operator<<(ostream&
OutStream,const dataList<Type>& OutList)
{ OutStream<<“Array Contents:\n”;
for(int i=0; i<OutList.ArraySize; i++)
OutStream<<OutList.Element[i]<<? ?;
OutStream<<endl;
OutStream<<“Array Current Size:”
<<OutList.ArraySize<<endl;
return OutStream;
}
Example
template<classType>istream&operator>>(istream&
InStream,const dataList<Type>&Inlist)
{ cout<<“Enter array Current Size:”;
InStream>>InList.ArraySize;
cout<<“Enter array element:\n”;
for(int i=0; i<InList.ArraySize; i++)
{ cout<<“Element”<<i<<“:”;
InStream>>InList.Element[i];
}
return InStream;
}
Example
template<class Type>void datalist<Type>::sort( )
{ for( int i=ArraySize-1; i>0; i--)
{ int j=Maxkey(0,i);
if (j!=i) Swap(j,i);
}
}
# endif
Example
# include,selecttm.h”
const int SIZE=10;
int main( )
{ dataList <int> Testlist(SIZE);
cin>>Testlist;
cout<<“Testing selection Sort:\n”<<Testlist<<endl;
Testlist.Sort( );
cout<<“After sorting,\n”<<Testlist<<endl;
return 0;
}
Testing and Debugging
1,Testing
2,Debugging
Chapter 1
Exercises:
(English) P13,2,5 ; P19,7
(Chinese) P9,2,5 ; P13,7
