- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
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.
Data Structures 2017-2-21 9/9
How 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.
Data Structures 2017-2-21 14/9
Distinction of Logical Concept of a data type and its physical implementation in a computer program
In 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.
Abstract Data Types and Data Structures
Data Structures
2017-2-21
11/9
Data 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.
Data Structures 2017-2-21 15/9
Distinction of Logical Concept of a data type and its physical implementation in a computer program
However, 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.
Data Structures
2017-2-21
4/9
Contents
1. 2. 3. 4. 5. 6. 7. 8. 9. Data Structures-An Overview Sequential Lists Stacks Queues Linked Lists Trees Graphs Sorting Searching
Course Material
◆ Recommended Reference Textbook: 1.A Practical Introduction to Data Strcutres and Algorithm Analysis, Clifford A.Shaffer. 2.<<数据结构 (C语言版)>>， 严蔚敏，吴伟民编 著，清华大学出版社。
Data Structures 2017-2-21 10/9
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.
Data Structures
2017-2-21
13/9
Abstract 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-21 5/9
Data Structures
◆Modular procedural language with arrays, structures, and references ◆Experimental tool – VC 6.0 – VS 2008 ◆ C vs. C++ or Java – small, clean, simple – can support learning data structures without learning too much language extras
Data Structures
2a 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.
Data Structures 2017-2-21 6/9
Why C ?
Learning Data Structures
WHY ? WHAT ? HOW ?
Practise! Practise! Practise!
Data Structures 2017-2-21 7/9
Why we use Data Structures?
计算机学院 谢芳
Data Structures Using C
Data Structures
2017-2-21
1/9
Prerequisites (Backgrounds)
◆Good knowledge of C Programming ◆A course in discrete mathematics
Data Structures
2017-2-21
2/9
Grading Schemes 1.Homework + Attendance(20%)
2.Programming (20%)
3.Terminal Examination (60%)
Data Structures
2017-2-21
3/9
◆Required Textbook : Structures,Algorithm Analysis, the electronic book.
Data Structures
2017-2-21
8/9
Purpose / Goals
Data 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.
