文档介绍：数据结构基础
教材: 《数据结构(C++描述)》(金远平编著,清华大学出版社,2005) 讲课教师: 金远平,软件学院 ******@seu.
1
JYP
考试:
期末考试采用开卷方式,占总评成绩的70%。
平时作业和实验占总评成绩30%。
考试注重:
概念、方法、技巧、思想、创新、关键步骤、程序设计风格
2
JYP
参考文献:
1 E. Horowitz, S. Sahni, D. Mehta, Fundamentals of Data Structure In C++, Computer Science Press,1995
2 W. Ford and W. Topp, Data Structures with C++,清华大学出版社(影印版), 1997
3 T. A. Standish, Data Structures, Algorithms & Software Principles in C, Addison-Wesley pany, 1994
3
JYP
第1章基本概念和方法
本章论述学****和研究数据结构所必须的并且将反复出现的基本概念和方法。
4
JYP
数据结构与软件系统
设计解决实际问题的计算机软件系统,首先需要建立被处理对象的数据模型。
数据和世上万物一样,都是具有结构的。人们很自然地用数据结构表示应用领域的被处理对象。例如,树和图。
数据结构由一个数据对象以及该对象中的所有数据元素之间的关系组成。
数据元素本身可以是数据结构,因此,可以构造非常复杂的数据结构。
5
JYP
为了模拟实际问题的求解过程和现实对象的行为,还必须提供对数据结构的相应操作。
数据结构的实现是以下一层数据结构表示上一层数据结构,直至以程序设计语言提供的基本数据类型表示的过程。
评价数据结构表示能力的标准主要是它能否方便且有效地实现需要的操作,而实现操作的算法设计及其效率高低也依赖于数据结构表示。
数据结构的定义、表示及其操作的实现相互关联,都是数据结构研究的重要内容。
6
JYP
计算机软件系统可看成是通过不同层次的数据结构及其操作实现的。例如:
7
JYP
中间层数据结构起着核心作用,称之为建模层。
对数据结构的研究产生了一批通用性强、具有很高实用价值的中间层数据结构,如数组、字符串、集合、线性表、栈、队列、链表、树、图、符号表等。
系统地学****进而掌握数据结构的知识和方法,对于提高设计与开发软件系统尤其是复杂软件系统的能力,无疑是十分重要的。
8
JYP
数据抽象与封装
抽象和封装的概念在日常生活中是普遍存在的,例如,人们常用的手机。
通过数据封装,将一个数据对象的内部结构和实现细节对外屏蔽。
通过数据抽象,将一个数据对象的规格说明与其实现分离,对外提供简洁、清晰的接口。
数据结构多层表示的过程反过来也就是从基础数据结构到应用领域数据结构的不断抽象与封装的过程。
9
JYP
用抽象数据类型(ADT)描述数据抽象与封装是一种自然、有效的方法。
数据类型由一个数据对象的集合和一组作用于这些数据对象的操作组成。例如,C++的基本数据类型char、int、float和double等。
抽象数据类型是一个数据类型,该数据类型的组织遵循将数据对象及对这些数据对象的操作的规格说明与这些数据对象的表示、操作的实现相分离的原则。
10
JYP