文档介绍：2 教材: 1、数据结构部分:《数据结构——用C++ 语言描述》, 陈慧南主编,南大学出版社 2、算法分析与设计部分:《计算机算法设计与分析》, 王晓东编著,电子工业出版社课时安排: 第一次面授:《数据结构》第一章到第五章第二次面授:《数据结构》第六章到第十章第三次面授:《算法分析》第二章到第七章(部分) 考试时间及方式: 第三次面授最后半天,复习加考试,开卷。 3 第一章绪论什么是数据结构数据抽象和抽象数据类型面向对象程序设计 C++ 程序设计数据结构的描述算法及其性能分析内容提要: 内容提要: 1 2 3 C++ 语言的基本特征 4 5 4 第一章绪论什么是数据结构数据抽象和抽象数据类型面向对象程序设计 C++ 程序设计数据结构的描述算法及其性能分析什么是数据结构在程序设计时就已经遇到过。一维数组是一个数据结构例如:一维数组 A=(a 1,a 2,a 3,a 4) int a[4]; // 定义并创建一维整型 // 数组(a[0],a[1],a[2],a[3]) x=a[2]; // 读数组元素 a[2] 的值 a[2]=x; // 置a[2] 的值为 x 数据结构由数据元素依某种逻辑关系组织起来,在数据结构上需要定义一组操作(运算)。 1、数据结构学科的定义: 主要是为研究和解决如何使用计算机处理非数值问题而产生的理论、技术和方法。 5 1. 1. 数据: 数据: 是信息的载体是信息的载体, ,. 2. 数值数据和非数值数据数值数据和非数值数据(1) 数值数据: 包括整数、实数或复数。主要用于工程计算、科学计算。(2) 非数值数据: 包括字符、文字、图形、图象、语音等。用于情报检索、企业管理、图形图象、人工智能、远程教育、远程医疗、电子商务、电子图书馆和办公自动化等诸多领域。3. 3. 数据元素: 数据元素: 组成数据的基本单位。第一章绪论什么是数据结构一、数据和数据元素二、什么是数据结构一、数据和数据元素 6 例如:一维数组 A=(a 1,a 2,a 3,a 4) (1) 数据元素间的逻辑关系: B=(D,R) 其中, D是数据元素的有限集合, R是D 上关系的有限集合。本书中一般只考虑 R包含一个关系的情况,即 R={r} 。 D={ a 1,a 2,a 3,a 4} r={ <a 1,a 2>,<a 2,a 3>,<a 3,a 4>} R={r} 第一章绪论什么是数据结构一、数据和数据元素二、什么是数据结构 1. 数据结构举例(1)数据元素之间的逻辑关系二、什么是数据结构 1. 数据结构举例 7 什么是数据结构一、数据和数据元素二、什么是数据结构 1. 数据结构举例(1)数据元素之间的逻辑关系(2)数据在计算机内的表示(2) 数据在计算机内的表示例如:一维数组 A=(a 1,a 2,a 3,a 4) 8 Create(): 建立一个数组。 Retrieve(i): 返回下标为 i的元素值。 Store(i,x): 将下标为 i的数据元素的值置为 x。什么是数据结构一、数据和数据元素二、什么是数据结构 1. 数据结构举例(1)数据元素之间的逻辑关系(2)数据在计算机内的表示(3)运算的定义和算法(3) 运算的定义和算法例如: int a[4]; // 定义一个一维整型数组 //( a[0],a[1],a[2],a[3]) x=a[2]; // 读数组元素 a[2] 的值 a[2]=x; // 置a[2] 的值为 x 9 2. 4 种基本的逻辑结构集合结构: 集合结构: 结构中的数据元素之间除了“同属于一个集合”的关系外,别无其它关系; 线性结构: 线性结构: 结构中的数据元素之间存在一对一的关系; 树形结构: 树形结构: 结构中的数据元素之间存在一对多的关系; 图结构: 图结构: 结构中的数据元素之间存在多对多的关系。什么是数据结构一、数据和数据元素二、什么是数据结构 1. 数据结构举例 2. 4 种基本的结构关系 3. 什么是数据结构 10 什么是数据结构一、数据和数据元素二、什么是数据结构 1. 数据结构举例 2. 4 种基本的结构关系 3. 什么是数据结构 2. 4 种基本的逻辑结构