1、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. Intr

2、oduce 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 ha

3、s 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: Manage

4、ment of the traffic lights in intersections,C, E are one-way road, there are 13 path to go. Can go at the same time : AB EC Cannot go at the same time: EB AD,This is a graph,The purpose and contents of the course,2 . Prerequisite of other courses: Principles of compiling : use stack to compute expre

5、ssion 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 algori

6、thm: 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 proces

7、sed 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 mem

8、bers 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 ope

9、rate 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 typearray, struct,ADT and OO,2. ADTs: Abstract Data Types Abstract: i

10、s 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 hi

11、de the information.,ADT NaturalNunber is objects: 一個(gè)整數(shù)的有序子集合,它開(kāi)始于0,結(jié)束于機(jī)器能表示的最大整數(shù)(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-orientedobjectclassi

12、nherit 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 classintegrate the same part (including attributes and operations) in all the derived cla

13、sses derived classadd the specific attributes and operations to the base class Example: base classpolygon derivedclassquadrilateral,triangular,ADT and OO,Communication: each class object communicate with others using messages. Message: instructions that one class object used in order to require anot

14、her 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. Alg

15、orithm has multiple descriptive methods, such as language, graph, table. 2.program cant 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)

16、+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,

17、Templates in C+,Program1.3 template 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 T Abc (T a, T b, T c ) return a+b+b

18、*c+(a+b-c)/(a+b)+4; z=Abc(2,x,y);,Parameter passing,2) Reference Parameters templateT Abc (T ,Recursive Function,1) direct recursive 2) indirect recursive Example 1 factorial function f(n)=n! 1 n1 (recursive component) f(5)=5f(4)=5*4f( 3)=5*4*3f(2)=5*4*3*2f(1)=120,f(n)=,Recursive Function,int factor

19、ial (int n) if (n=1) return 1; else return n*Factorial(n-1); ,Recursive Function,Example 2: computes the sum of the elements a0 through an-1 (Program 1.9) a0, a1, , an-2, an-1,Recursive Function,Template T Rsum(T a, int n) if (n0) return Rsum(a,n-1)+an-1; return 0; ,Recursive Function,Example 3: Per

20、mutation (Program 1-10) a,b,c : abc, acb, bac, bca, cab, cba permutation of n elements has n!,Recursive Function,Template void perm(T list , int k, int m) int i; if (k=m) for (i=0; i=m; i+) cout listi; cout endl; else for (i=k; i=m; i+) swap(listk, listi); perm(list, k+1, m); swap(listk, listi); ,Dy

21、namic Memory Allocation,1. New int *y = new int ; *y = 10; int *y = new int(10); Delete delete y ; delete x;,Dynamic Memory Allocation,2.Exception Handling float *x = new float n; an exception occurs float * x; try x=new floatn; catch (xalloc) cerr“out of Memory”endl; exit(1);,Dynamic Memory Allocat

22、ion,3. One-dimensional Arrays float * x = new float n;,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

23、 4,X0,X1,X2,Dynamic Memory Allocation,Program 1.13 template void Make2DArray (T * ,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; in-1; i+) int k=i; for ( int j=i+1; jn; j+) if ( ajak) k=j; int te

24、mp=ai; ai=ak;ak=temp; ,Example,# ifndef DATALIST_H # define DATALIST_H # include template 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 TypeSize) datalist( )delete Element; void Sort( ); friend ostream # endif,Example,# ifndef SELECTTM-H # define SELECTTM