数据结构与STL_第1章_绪论

北邮BUPT 数据结构课件

《数据结构与STL》 数据结构与 》

第一章 绪论北京邮电大学 信息与通信工程学院

北邮BUPT 数据结构课件

第一章 绪论学习内容： 学习内容： 1.1 数据结构的起源 1.2 数据结构的基本概念 1.3 算法和算法分析 1.4 STL与数据结构 与数据结构 1.5 实例分析

北邮BUPT 数据结构课件

1.1 数据结构的起源程序设计的两个重要问题： 程序设计的两个重要问题：待处理的数据存储到计算机内存 设计相应的算法操作这些数据 数据表示 数据处理

数据的逻辑表示 数据的存储方法 对数据的处理

数据结构 课程内容

北邮BUPT 数据结构课件

起源数据结构是计算机及其相关专业的重要课程计算机发展初期：处理数值计算问题 计算机发展初期： ——不重视数据结构 不重视数据结构 20世纪 ~80年代：非数值处理问题 世纪60~ 年代 年代： 世纪 ——沃思：算法 + 数据结构 = 程序 沃思： 沃思 20世纪 年代至今：面向对象 世纪80年代至今 世纪 年代至今：面向对象(OO)技术出现 技术出现 ——数据结构与面向对象具有天然的对应 数据结构与面向对象具有天然的对应

北邮BUPT 数据结构课件

第一章 绪论学习内容： 学习内容： 1.1 数据结构的起源 1.2 数据结构的基本概念 1.3 算法和算法分析 1.4 STL与数据结构 与数据结构 1.5 实例分析

北邮BUPT 数据结构课件

1.2 数据结构的基本概念数据( 数据(data) )信息的载体 分为两类：数值型数据、 分为两类：数值型数据、非数值型数据

数据元素( 数据元素(data element) )也称为元素、结点、 也称为元素、结点、顶点或记录 是数据的基本单位， 是数据的基本单位，在计算机程序中通常 作为一个整体进行处理。 作为一个整体进行处理。

数据项( 数据项(data item) )也称为字段或域 构成数据元素的不可分割的最小单位。 构成数据元素的不可分割的最小单位。 每个数据元素可以包含多个不同的数据项。 每个数据元素可以包含多个不同的数据项。

struct Student { int No; char name[10]; float score; int age; char sex; } stu[10]={ {1,"张三 张三",90,19,'M'}, 张三 {2,"张莉 张莉",95,18,'F'}}; 张莉

数据类型( 数据类型(data type) )

分析上述代码，哪些是： 分析上述代码，哪些是： 具有相同性质的计算机数据的集合以及在 数据、数据元素、 数据、数据元素、 这个数据集合上的一组操作。 这个数据集合上的一组操作。 数据项、数据类型？ 数据项、数据类型？可分为简单类型和构造类型。 可分为简单类型和构造类型。

北邮BUPT 数据结构课件

数据结构的概念数据结构( 数据结构(data structure) )是指按照某种逻辑关系组织起来的一组数据， 是指按照某种逻辑关系组织起来的一组数据，按 逻辑关系组织起来的一组数据 一定的存储方式存储在计算机的存储器中， 存储方式存储

在计算机的存储器中 一定的存储方式存储在计算机的存储器中，并在 这些数据上定义了一组运算的集合。 运算的集合 这些数据上定义了一组运算的集合。 通常人们认为数据结构包含三个方面的内容： 通常人们认为数据结构包含三个方面的内容： 数据的逻辑结构 数据的存储结构 对数据的操作或运算

北邮BUPT 数据结构课件

数据的逻辑结构描述数据相互间的关联形式或邻接形式 反映了数据内部的构成方式 定义了数据的本质特点 常常将数据的逻辑结构直接称为数据结构 数据的逻辑结构独立于计算机，与存储方式无关， 数据的逻辑结构独立于计算机，与存储方式无关，可 认为是从具体问题抽象出来的数学模型。 认为是从具体问题抽象出来的数学模型。 数据元素之间不同的逻辑特点代表不同的逻辑结构 四种常见的逻辑结构(a)集合 集合 (b)线性结构 线性结构 (c)树结构 树结构 (d)图结构 图结构

北邮BUPT 数据结构课件

数据的存储结构考虑如何在计算机的存储器中存储各个数据元 并且同时反映数据元素间的逻辑关系。 素，并且同时反映数据元素间的逻辑关系。 对于每种逻辑结构， 对于每种逻辑结构，都可以设计多种存储方法基本的两种存储结构顺序存储结构 链式存储结构

北邮BUPT 数据结构课件

各种数据结构的学习主线每学习一种数据结构 其逻辑结构是什么？可有哪些运算？ 其逻辑结构是什么？可有哪些运算？ 有哪些存储结构？C++如何描述各种存储结构 有哪些存储结构？C++如何描述各种存储结构 基于每种存储结构，各种运算如何实现？ 基于每种存储结构，各种运算如何实现？ 各种存储结构的优缺点对比

北邮BUPT 数据结构课件

第一章 绪论学习内容： 学习内容： 1.1 数据结构的起源 1.2 数据结构的基本概念 1.3 算法和算法分析 1.4 STL与数据结构 与数据结构 1.5 实例分析

北邮BUPT 数据结构课件

1.3 算法和算法分析算法——解题的方法 解题的方法 算法数据的运算是通过算法( 数据的运算是通过算法(algorithm)描述的 ) 讨论算法的效率和性能是数据结构课程的重要内容

算法通常满足5个准则： 算法通常满足 个准则： 个准则输入：具有 个或多个输入的参数 个或多个输入的参数。 输入：具有0个或多个输入的参数。 输出：算法执行要有输出结果。 输出：算法执行要有输出结果。 有穷性：算法中每条指令的执行次数必须是有限的。 有穷性：算法中每条指令的执行次数必须是有限的。 确定性：每条指令必须有确切的含义，无二义性。 确定性：每条指令必须有确切的含义，无二义性。 可行性：每条指令的执行时间都是有限的。 可行性：每条指令的执行时间都是有限的。

常见的算法描述方法： 常见的算法描述方法：自然语言 流程图 伪

代码 程序设计语言

北邮BUPT 数据结构课件

欧几里得算法描述举例辗转相除法求两个自然数m和 的最大公约数 的最大公约数， 辗转相除法求两个自然数 和n的最大公约数，假定 m≥n

自然语言描述： 自然语言描述：

流程图描述： 流程图描述：

(1) 输入m和n; (2) 取得m除以n的余数r; (3) 若r=0,则n为最大公 约数，算法结束；否则执行 第(4)步； (4) 将n放到m中，r放到n 中； (5) 重复执行第(2)步。

北邮BUPT 数据结构课件

欧几里得算法描述举例伪代码描述： 伪代码描述：1. input m,n 2. r=m%n; 3. while (r!=0) 3.1 m=n; 3.2 n=r; 3.3 r=m%n; 4. output n;

程序设计语言描述： 程序设计语言描述：int EUCLID (int m, int n) { int r = m % n; while (r != 0){ m = n; n = r; r = m % n; } return n; }

北邮BUPT 数据结构课件

欧几里得算法描述举例采用面向对象的方法描述： 采用面向对象的方法描述：class NaturalNumber{ public: unsigned long int EUCLID(NaturalNumber & n); //欧几里德算法求解最大公约数 //……其它外部接口 private: unsigned long int num; //存储真正的自然数 }; //返回欧几里德算法求解最大公约数 unsigned long int NaturalNumber :: EUCLID(NaturalNumber & n) { unsigned long int m = (num > n.num) ? num : n.num; //较大的自然数赋值给m unsigned long int n = (num < n.num) ? num : n.num; //较小的自然数赋值给n unsigned long int r = m % n; while (r != 0) {m = n; n = r; r = m % n;} r …… 此处隐藏：2155字，全部文档内容请下载后查看。喜欢就下载吧 ……