资源描述
计算机学院计算机学院 谢芳谢芳Data Structures Using C2017-2-21Data Structures 1/9计算机学院 谢芳Data Structures Using 2017-2-21Data Structures 2/9Prerequisites(Backgrounds)Good knowledge of C ProgrammingA course in discrete mathematics2017-2-21Data Structures 2/9Pr2017-2-21Data Structures 3/9Grading Schemes1.Homework+Attendance(20%)2.Programming(20%)3.Terminal Examination(60%)2017-2-21Data Structures 3/9Gr2017-2-21Data Structures 4/9RecommendedReferenceTextbook:1.A Practical Introduction to Data Strcutres and Algorithm Analysis,Clifford A.Shaffer.2.，严严蔚敏，吴蔚敏，吴伟伟民民编编著，清著，清华华大学出版社。大学出版社。Course MaterialRequired Textbook:Structures,Algorithm Analysis,the electronic book.2017-2-21Data Structures 4/9Re2017-2-21Data Structures 5/9Contents1.Data Structures-An Overview2.Sequential Lists3.Stacks4.Queues5.Linked Lists6.Trees7.Graphs8.Sorting9.Searching2017-2-21Data Structures 5/9Co2017-2-21Data Structures 6/9Why C?Modular procedural language with arrays,structures,and referencesExperimental toolVC 6.0VS 2008C vs.C+or Javasmall,clean,simplecan support learning data structures without learning too much language extras2017-2-21Data Structures 6/9Wh2017-2-21Data Structures 7/9Learning Data StructuresWHY?WHAT?HOW?Practise!Practise!Practise!2017-2-21Data Structures 7/9Le2017-2-21Data Structures 8/9Why we use Data Structures?It should go without saying that people write programs to solve problems.However，it is crucial to keep this truism in mind when selecting a data structure to solve a particular problem.Only by first analyzing the problem to determine the performance goals that must be achieved can there be any hope of selecting the right data structure that they are familiar with but which is inappropriate to the problem.2017-2-21Data Structures 8/9Wh2017-2-21Data Structures 9/9Purpose/GoalsData Structures-if your program needs to store a few things-number,payroll records,or job descriptions for example-the simplest and most effective approach might be to put them in a list(in c array).Only when you have to organize and search through a large number of things do more sophisticated data structures usually become necessary.2017-2-21Data Structures 9/9Pu2017-2-21Data Structures 10/9How to use Data Structures?When selecting a data structure to solve a problem,you should follow these steps:1.Analyze your problem to determine the basic operations that must be supported.Examples of basic operations include inserting a data item into the data structure,deleting a data item from the data structure,and finding a specified data item.2.Quantify the resource constraints for each operation.3.Select the data structure that best meets these requirements.2017-2-21Data Structures 10/9H2017-2-21Data Structures 11/9Abstract Data Types and Data Structures The previous pages used the terms“data item”and“data structure”without properly defining them.This section presents terminology and motivates the design process embodied in the three-step approach to selecting a data structure.This motivation stems from the need to manage the tremendous complexity of computer programs.2017-2-21Data Structures 11/9A2017-2-21Data Structures 12/9Data Types(DT)A type is a collection of values.For example,-The Boolean type consists of the values true and false.The integers also form a type.An integer is a simple type because its values contain no subparts.-A bank account record will typically contain serval pieces of information such as name,address,account number,and account balance.Such a record is an example of an aggregate type or composite type.2017-2-21Data Structures 12/9D2017-2-21Data Structures 13/9Data Types(DT)-A data item is a piece of information or a record whose value is drawn from a type.A data item is said to be a member of a type.-A data type is a type together with a collection of operations to manipulate the type.For example,an integer variable is a member of the integer data type.Addition is an example of an operation on the integer data type.2017-2-21Data Structures 13/9D2017-2-21Data Structures 14/9Abstract Data Types(ADT)An abstract data type is the realization of a data type as a software component.The interface of the ADT is defined in terms of a types and a set of operations on that type.The behavior of each operation is determined by its inputs and outputs.An ADT does not specify how the data type is implemented.These implementation details are hidden from the user of the ADT and protected from outside access,a concept referred to as encapsulation.(An ADT must be defined before we use it)2017-2-21Data Structures 14/9A2017-2-21Data Structures 15/9Distinction of Logical Concept of a data type and its physical implementation in a computer programIn a computer program,there are two traditional implementations for the list data type：the linked list and array-based list.The list data type can therefore be implemented using a linked list or an array.“Array”is commonly used in computer programming to mean a contiguous block of memory location,where each memory location stores one fixed-length data item.By this meaning,an array is a physical data structure.2017-2-21Data Structures 15/9D2017-2-21Data Structures 16/9Distinction of Logical Concept of a data type and its physical implementation in a computer programHowever,array can also mean a logical data type composed a collection of data items,with each data item identified by an index number(in c programming language,it uses pointer to represent the index).It is possible to implement arrays in many different ways.2017-2-21Data Structures 16/9DADT Example:Array:Fixed length string method#Example:char*str;str=“CHINA”;012345Advantage:simple.Disadvantage:possible wastage of memory space;complex operations.str0str19NULL6.19C H IN A0.ADT Example:#Example:char*stLinked list methodAdvantage:no wastage of memory space;memory allocation is dynamic;simpler operations.Disadvantage:accessing a substring requiredstrating from the beginning;required more memory space.Linked list methodAdvantage:nSingly Linked liststruct node chardata;struct node*next;struct node*header,*string;Logical Representation of stringPhysical Representation of string(header)data nextS20C30U10header40TPhysical Space TNULL001070Address:20C3030U1040S207040Singly Linked liststruct node2017-2-21Data Structures 20/9 Discuss1.What is Data Structures?2.What is ADT?3.What is the distinction of logical conception and physical implementation?2017-2-21Data Structures 20/9
展开阅读全文