Data structures Algorithms and Applications in C++ Chen Peipei March 13.2003
Data Structures, Algorithms, and Applications in C++ Chen Peipei March 13, 2003
Chapter 1 preface
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 ctt
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 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: 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 1 uses a tree structure
The purpose and contents of the course Example 2: Management of library catalogue by computer 书名作者名登录号分类出版年月 D.S. Sartaj Sahni 000001 computer 2000.1 It is a linear list
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, e are one-way road there are 13 path to go B D Can go at the same time A A→BE→C Cannot go at the same time This is a graph E→BA→D
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: This is a graph E→B A→D
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 schedulin g Database: use B+ tree to organize store and load massive data in the hard memory
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+t
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++