[工学]数据结构C++Ch1课件.ppt

Chapter 1  Data structure and Programming Principles Contents Points 1 What is Data Structure? 2 General steps of processing problems by computer. 3 Program Design in C++. 4 Example demonstration. 1 What is Data Structure? Fundamental Terms Data Layers: Data （数据）：a set of all the symbols that computer can manage.(所有能输入到计算机中并被计算机所识别和处理的符号的总称。) Data Elements （数据元素）:数据中的一个个体。a character ‘+’ or a student when it is stored in a computer. Data Item（数据项）:when the data element is a record,it can be divided into data items. Example:a student record may be combined by number, name, score and so on . Data Structure: Collection of relational Data Elements Logical Structure（逻辑结构）the intrinsic relations between data elements According to the difference of the relation ,we can classify them into four kinds. Lists Trees Graphics Set Storage Structure: （存储结构）Physical Structure in computer Contiguous structure Linked structure 2 Processing problems by computer Processing problems by computer Fundamental Tasks: Definition of Data Structure (including logical structure and base operations); Realization of Data Structure (including storage structure and base operations); Estimation and selection of Data Structure (analysis of algorithms) Asymptotic Time Complexity（时间复杂度） Asymptotic Space Complexity（空间复杂度） Problems of Large Programs 1. Problem specification （需求分析） 2. Program organization 3. Choice of data structures 4. Algorithm analysis 3 Program Design in C++ C++ features: Data Abstraction （数据抽象） Object-oriented design （面向对象的设计） Top-down approach Code reuse （代码重用） Refinement, improvement, extension of C Introduction of OO (Object Oriented) Encapsulation （封装性） Inheritance （继承性） Polymorphism （多态性） 4 Example demonstration——game of life Definition It takes place on an unbounded rectangular grid in which each cell can either be occupied by an organism or not. Occupied cells are called alive; unoccupied cells are called dead. Which cells are alive or not c