(1.3.1)--ch1-03数据结构的基本概念-3.pdf

Data Structures and AlgorithmsBasic Concepts in Data Structures-12Chapter 1 Introduction1.1 Basic concepts of data structureRelated nouns:DataData Data ElementData Element Data ObjectData Object Data StructureData Structure Data Type Data Type Data abstraction and abstractData abstraction and abstract data types data typesData Structures and AlgorithmsData Structures and Algorithms3Related nouns:Data：Data are numeric values,characters,and a collection of various symbols that can be entered into the machine and processed.Data includes integer、real、Boolean、image、character、sound,etc.,which can be input to the computer.For example:for C source programC compilerC compilerSource Source codecode（.c.c）Target Target programprogram（.obj.obj）Executable Executable programprogram（.exe.exe）C linkerC linkerData Structures and AlgorithmsData Structures and AlgorithmsChapter 1 Introduction1.1 Basic concepts of data structure4Related nouns:Data Element：It is the basic unit that composes the data，and the individual of the data collection,which is usually considered and processed as a whole in the computer.e.g.nullnullcomputercomputercomputer science0704computer science0704womanwoman Li ShaLi Sha1313PositionPosition DepartmentDepartment P ProfessionrofessionSexSex NameName S Student IDtudent ID Data Data element element数据项数据项A data element can be made up of one or more data items，which is the smallest unit with independent meaning.recordingData Structures and AlgorithmsData Structures and AlgorithmsChapter 1 Introduction1.1 Basic concepts of data structure5 据据 结结 构构Related nouns:Data Object：A data object is a collection of data elements of the same nature,and is a subset of data.e.g.Integer set:N=0,1,2,.infinite setCharacter set:C=A,B,Z limited setData Structures and AlgorithmsData Structures and AlgorithmsChapter 1 Introduction1.1 Basic concepts of data structure6Data Structure：e.g.Table Structure It refers to a collection of data elements that have one or more specific relationships with each other.It is a collection of data elements with structure.It refers to the relationship between data elements,that is,the organization of data.1313Data Structures and AlgorithmsData Structures and AlgorithmsChapter 1 Introduction1.1 Basic concepts of data structureS Student IDtudent ID NameName SexSex P ProfessionrofessionDepartmentDepartment PositionPosition nullnullcomputercomputercomputer science0704computer science0704Li ShaLi Shawomanwoman 7Data Structure：e.g.It refers to a collection of data elements that have one or more specific relationships with each other.It is a collection of data elements with structure.It refers to the relationship between data elements,that is,the organization of data.Tree structureteaching and research officelaboratorysystemofficeResearch institutionsschoolschoolGraph structure12543Data Structures and AlgorithmsData Structures and AlgorithmsChapter 1 Introduction1.1 Basic concepts of data structure8Data Type：e.g.In high-level languages,the value range of integer types is:-32768+32767,and the set of operators are addition,subtraction,multiplication,division,and modulo,namely+,-,*,/,%.Data type is the general term for a set of values with the same properties and a set of operations defined on this value set.Atomic type:Its value cannot be decomposed.Such as the standard types in C language(integer,real,character).Structure type:Its value is composed of several components in a certain structure,so it can be decomposed,and itscomponents can be non-structural or structural.What kind of pointer type is it?Data Structures and AlgorithmsData Structures and AlgorithmsChapter 1 Introduction1.1 Basic concepts of data structure9Related nouns:data abstraction and abstract data typesAbstract Data Type:Refers to a data type based on a logical relationship and a set of operations defined on this type.The abstract data type determines a model,but hides the implementation details of the model;it defines a set of operations,but hides the implementation process of the operations.Data Structures and AlgorithmsData Structures and AlgorithmsChapter 1 Introduction1.1 Basic concepts of data structure10Abstract Data TypeFor example:the description of the abstract data type of the linear table:ADT Linear_listData element All ai belong to the same data object,i=1,2,.,n n0;Logical structure All data elements ai(i=1,2,.,n-1)have an order relationship,a1 has no predecessor,an has no successor;Operation Let L be Linear_list Initial(L)：Initialize the empty linear table;Length(L)：Find the length of the linear table;Get(L,i)：Get the i-th element of the linear table;Insert(L,i,b)：Insert element b at the i-th position of the linear table;Delete(L,i)：Delete the i-th element of the linear table;ADT Linear_list Data Structures and AlgorithmsData Structures and AlgorithmsChapter 1 Introduction1.1 Basic concepts of data structure11Abstract Data TypeThree ways to achieve:Traditional process-oriented programming Design method of package and model Object Oriented Programming （abbreviation OOP）Data Structures and AlgorithmsData Structures and AlgorithmsChapter 1 Introduction1.1 Basic concepts of data structure12 据据 结结 构构Related nouns:data abstraction and abstract data typesAbstract Data TypeADT has two important characteristics:Data abstraction:Data encapsulation：Separate the external characteristics of the entity from its internal implementation details,and hide its internal implementation details from external users.When using ADT to describe the entity handled by the program,it emphasizes its essential characteristics,the functionsthat it can complete,and its interface with external users(that is,theway the outside world uses it).Data Structures and AlgorithmsData Structures and AlgorithmsChapter 1 Introduction1.1 Basic concepts of data structureThanks！D Da at ta a S St tr ru uc ct tu ur re es s a an nd d A Al lg go or ri it th hm ms s