《【精品数据结构】The Need for Data Structures.ppt》由会员分享，可在线阅读，更多相关《【精品数据结构】The Need for Data Structures.ppt（16页珍藏版）》请在三一文库上搜索。
1、The Need for Data Structures,Data structures organize data more efficient programs.More powerful computers more complex applications.More complex applications demand more calculations.Complex computing tasks are unlike our everyday experience.,Organizing Data,Any organization for a collection of rec
2、ords can be searched, processed in any order, or modified.The choice of data structure and algorithm can make the difference between a program running in a few seconds or many days.,Efficiency,A solution is said to be efficient if it solves the problem within its resource constraints.SpaceTimeThe co
3、st of a solution is the amount of resources that the solution consumes.,有效率的,资源限制,Selecting a Data Structure,Select a data structure as follows:Analyze the problem to determine the resource constraints a solution must meet.Determine the basic operations that must be supported. Quantify the resource
4、constraints for each operation.Select the data structure that best meets these requirements.,Some Questions to Ask,Are all data inserted into the data structure at the beginning, or are insertions interspersed with other operations?Can data be deleted?Are all data processed in some well-defined orde
5、r, or is random access allowed?,Data Structure Philosophy,Each data structure has costs and benefits.Rarely is one data structure better than another in all situations.A data structure requires:space for each data item it stores,time to perform each basic operation,programming effort.,原则、方法,Goals of
6、 this Course,Reinforce the concept that costs and benefits exist for every data structure.Learn the commonly used data structures.These form a programmers basic data structure toolkit.Understand how to measure the cost of a data structure or program.These techniques also allow you to judge the merit
7、s of new data structures that you or others might invent.,Abstract Data Types,Abstract Data Type (ADT): a definition for a data type in terms of a set of values and a set of operations on that data type.Each ADT operation is defined by its inputs and outputs.Encapsulation: Hide implementation detail
8、s.,Data Structure,A data structure is the physical implementation of an ADT.Each operation associated with the ADT is implemented by one or more subroutines in the implementation.Data structure usually refers to an organization for data in main memory.File structure is an organization for data on pe
9、ripheral storage, such as a disk drive.,Logical vs. Physical Form,Data items have both a logical and a physical form.Logical form: definition of the data item within an ADT.Ex: Integers in mathematical sense: +, -Physical form: implementation of the data item within a data structure.Ex: 16/32 bit in
10、tegers, overflow.,Data Type,ADT:TypeOperations,Data Items: Logical Form,Data Items: Physical Form,Data Structure:Storage SpaceSubroutines,Problems,Problem: a task to be performed.Best thought of as inputs and matching outputs.Problem definition should include constraints on the resources that may be
11、 consumed by any acceptable solution.,Problems mathematical functionsA function is a matching between inputs (the domain) and outputs (the range).An input to a function may be single number, or a collection of information.The values making up an input are called the parameters of the function.A part
12、icular input must always result in the same output every time the function is computed.,Algorithms and Programs,Algorithm: a method or a process followed to solve a problem.A recipe.An algorithm takes the input to a problem (function) and transforms it to the output.A mapping of input to output.A pr
13、oblem can have many algorithms.,Algorithm Properties,An algorithm possesses the following properties:It must be correct.It must be composed of a series of concrete steps.There can be no ambiguity as to which step will be performed next.It must be composed of a finite number of steps.It must terminat
14、e.A computer program is an instance, or concrete representation, for an algorithm in some programming language.,-finiteness: Algorithm must complete after a finite number of instructions have been executed.-absence of ambiguity: Each step must be clearly defined, having only one interpretation.-defi
15、nition of sequence: Each step must have a unique defined preceding & succeeding step. The first step (start step) & last step (halt step) must be clearly noted. -input/output: Number and types of required inputs and results must be specified.-feasibility: It must be possible to perform each instruction.,