[教育]DS1.pptVIP

* * * Data Structures QieJianMin PREFACE Purpose/Goals Approach Overview Purpose/Goals Data structures: methods of organizing large amounts of data; Algorithm analysis: the estimation of the running time of algorithm. A realistic example Suppose we have a group of N numbers and would like to determine the kth largest. This is known as the selection problem. Approach Students are encouraged to supply the realistic programming issues; The algorithms in this course are presented in ANSI C or a simultaneous assignment. Overview Algorithm analysis Lists, stacks, queues Trees Graph algorithm Sorting Selection algorithm Chapter 1 Introduction Concepts about data structure ADT(Abstract Data Types) Algorithm and algorithm analysis 1.1 Concepts about data structure 1.1.1 Common sense of solving problems Analyzing Modeling Designing( storage and code) Debug Example1A waiting room(collection) Example2 Spring The shifting seasons(linear list) Summer Fall Winter Example3 Family tree(nonlinear list) Example4A computer network(graph) Example5 Information system of students( a realistic example) 1.1.2 Concept and term Data Data item Data element Data object Fig 1.1 Data, Data Item, Data Object Data item Data element Data object Data structure: The gathering of several data elements, which have some relationships between each other. There exists four basic structures: Disjoint Set Linear Structure Tree Graph Fig 1.2 Four basic structures Data structure also includes logical structure and physical structure; Logical structure (built by mental work) linear/nonlinear Physical structure (mathematical model reflection in computer’s storage) sequential/linked/index/hash 1.1.3 Estimation criterion of algorithm analysis We can understand this abstract subject from three levels: Abstract: Logical structure referring to basic computation Material: Physical structure referring to algorithm Estimate: Comparing and analyzing different algorithms 1.2 Abs