《chapter1数据结构课件.ppt

Why Study Data structure Present commonly used data structure. Introduce the idea of tradeoff(折中); reinforce the concept of costs and benefits associated with every data structure. Measure the effectiveness of a data structure or algorithm. Concepts about Data Structure Linear structure Tree Graph set Problem Solving: Main Steps Problem definition Algorithm design / Algorithm specification Algorithm analysis Implementation Testing [Maintenance] * * * 数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。 数据元素：数据中的一个“个体”，也称 “数据记录” 。是数据结构中讨论的基本单位 。 数据项: 相当于记录的“域”, 是数据的不可分割的最小单位。是数据结构中讨论的最小单位 。 (原子项、组合项) 数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。 数据元素：数据中的一个“个体”，也称 “数据记录” 。是数据结构中讨论的基本单位 。 数据项: 相当于记录的“域”, 是数据的不可分割的最小单位。是数据结构中讨论的最小单位 。 (原子项、组合项) * * 数据类型 :一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称.一个变量的数据类型规定了这个变量的取值范围，也定义了这个变量可用的操作， 抽象，就是抽取反映问题本质的东西，忽略非本质的细节。例如在计算机中使用二进制定点书和浮点数实现数据的存储和运算，而在汇编语言中则给出了个中数据的自然表示，使用时不考虑实现的细节，在高级语言中出现了整形实型等，待到抽象数据类型是，定义出更高级的数据抽象，如表，队列，图窗口等，这种抽象的层次为设计者提供了有力的手段，使得设计者可以抽象的概念出发，从整体上进行考虑，最后得到需要的结果 抽象数据类型：由用户定义，用以表示应用问题的数据模型，由基本的数据类型组成, 并包括一组相关的服务（或称操作） 信息隐蔽和数据封装，使用与实现相分离 * * * * * * * * * * * * * * * * * * * * * * * * * * * * Data Structure Software College Northeastern University Ways to estimate the running time Rule 1 - For loops for (i=0; iN; i++) k++; Rule 2 - Nested for loops for (i=0; iN; i++) for (j=0; jN; j++) k++ Running Time Calculations * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Data Structure Software College Northeastern University Rule 3: Consecutive Statements for (i=0;iN; i++) k++; for (i=0; iN; i++) for (j=0; jN; j++) k++; Running Time Calculations * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Data Structure Software College Northeastern University Rule 4: Condition Statement if (condition) S1 else S2 Running time of test plus larger of times s1 and s2