数据结构-绪论

1、LOGO 数据结构数据结构 v课程安排课程安排 总学时：总学时：36 36 讲课学时：讲课学时：28 28 实验学时：实验学时：8 8 v课程评分课程评分 期末笔试：期末笔试：80 80 实验：实验：2020 BME 参考书目参考书目 BME 第一章第一章 绪论绪论 1.1什么是数据结构 BME v建立数学模型建立数学模型 v设计解数学模型的算法设计解数学模型的算法 v编制程序编制程序 v调试、调整、调试、调试、调整、调试、 v得到结果得到结果 1、分析问题，提、分析问题，提 取操作对象取操作对象 2、找出操作对象、找出操作对象 之间的关系之间的关系 3、用数学语言加、用数学语言加 以描述以描

2、述 BME 用数学语言用数学语言 描述描述 用数学方程用数学方程 加以描述加以描述 非数值计非数值计 算问题算问题 1.1什么是数据结构 v图书馆书目自动检索问题图书馆书目自动检索问题 BME 编号编号： 书名：书名： 作者名：作者名： 分类号：分类号： 出版单位：出版单位： 出版时间：出版时间： 价格：价格： 书目卡片 书目文件 按书名 按作者名 按分类号 高等数学 001，003 理论力学 002，. 线性代数 004， . 樊映川001, 华罗庚002,. 栾汝书004,. . L002, S001,003, 线性表线性表 1.1什么是数据结构 v计算机文件系统计算机文件系统 BME 1

3、.1什么是数据结构 v计算机和人对弈问题计算机和人对弈问题 9 . . 树树 1.1什么是数据结构 v多叉路口交通灯管理问题多叉路口交通灯管理问题 BME C E D A B ABACAD BABCBD DADBDC EAEBECED 图 1.1什么是数据结构 v综上，描述这类综上，描述这类非数值计算问题非数值计算问题的数的数 学模型不是数学方程学模型不是数学方程,而是表而是表、树和图树和图 之类的数据结构。之类的数据结构。 v因此从广义上讲，数据结构是一门研因此从广义上讲，数据结构是一门研 究究非数值计算非数值计算的程序设计问题中计算的程序设计问题中计算 机的机的操作对象操作对象以及它们之间

4、的以及它们之间的关系和关系和 操作操作的学科的学科. BME 1.1什么是数据结构 1.2 基本概念和术语基本概念和术语 BME 是具有某种特定性质的事物的总体。是具有某种特定性质的事物的总体。 设有集合设有集合A、B，若有，若有xA，必有，必有 xB，那么称，那么称A是是B的子集。的子集。 形如（形如（A，L）的二元组，其中）的二元组，其中A,L代表代表 任意的抽象元素。任意的抽象元素。 由两个元素由两个元素x和和y按一定顺序排列按一定顺序排列 成的二元组。记作成的二元组。记作。 如果一个集合满足以下条件如果一个集合满足以下条件 之一，称该集合为一个二元关系。之一，称该集合为一个二元关系。

5、（1）集合非空，且它的元素都是有序对）集合非空，且它的元素都是有序对 （2）集合是空集）集合是空集 BME 数据数据(Data): 对客观事物的一种符号表示。在计算机科学中是指对客观事物的一种符号表示。在计算机科学中是指 所有能输入到计算机中所有能输入到计算机中 并被计算机程序处理的符号的总称。并被计算机程序处理的符号的总称。 数值型数据数值型数据 非数值型数据非数值型数据 1.2 基本概念和术语基本概念和术语 BME 数据元素数据元素(DataElement): 数据的数据的基本单位基本单位，在计算机程序中通常作为一，在计算机程序中通常作为一 个整体进行考虑和处理。个整体进行考虑和处理。 一

6、个数据元素可由若干个一个数据元素可由若干个数据项数据项(data item)(data item)组成。组成。 数据项是数据的不可分割的数据项是数据的不可分割的最小标识单位最小标识单位。 001高等数学樊映川S01高等教育出版社 数据元素数据元素 数据项数据项 1.2 基本概念和术语基本概念和术语 BME 数据对象数据对象(DataObject)： 性质相同的数据元素的集合。是数据的一个子集。性质相同的数据元素的集合。是数据的一个子集。 u整数数据对象整数数据对象 N=0, 1, 2, u大写英语字母字符数据对象大写英语字母字符数据对象 C=A,B,C,Z 1.2 基本概念和术语基本概念和术语

7、 v什么是数据结构什么是数据结构 BME 类类C语言描述功能的简要说明：语言描述功能的简要说明： BME v2、数据结构的表示用类型定义（数据结构的表示用类型定义（typedef）描）描 述。数据元素类型约定为述。数据元素类型约定为ElemType，由用户在，由用户在 使用该数据类型时自行定义。使用该数据类型时自行定义。 v3、基本操作的函数表述：、基本操作的函数表述： 1.3 抽象数据类型抽象数据类型 数据类型数据类型函数名函数名（形式参数形式参数） 内部数据说明；内部数据说明； 执行语句组；执行语句组； /*函数名函数名*/ BME 1.3 抽象数据类型抽象数据类型 4、赋值语句、赋值语句

8、 5、选择语句、选择语句 6、循环语句、循环语句 7、结束语句、结束语句 8、输入和输出语句、输入和输出语句 9、注释、注释 10、基本函数、基本函数 11、逻辑运算约定、逻辑运算约定 例例:1.6,1.7 BME 1.4 算法和算法分析算法和算法分析 s=0;+x;s=0; 将将x x自增看成是基本操作，则语句频度为，即时自增看成是基本操作，则语句频度为，即时 间复杂度为间复杂度为(1)(1) 如果将如果将s=0s=0也看成是基本操作，则语句频度为，也看成是基本操作，则语句频度为， 其时间复杂度仍为其时间复杂度仍为(1)(1)，即常量阶。，即常量阶。 v例例2 2、for(i=1;i=n;+

9、i) +x;s+=x;for(i=1;i=n;+i) +x;s+=x; 语句频度为：语句频度为：2n2n，其时间复杂度为：，其时间复杂度为：O(n) O(n) ，即，即 时间复杂度为线性阶。时间复杂度为线性阶。 BME 1.4 算法和算法分析算法和算法分析 v例例3 3、计算两个、计算两个N N N N矩阵相乘矩阵相乘 for(i=1;i=N;+i) for(j=1;j=N;+j) cij=0; for(k=1;k=N;+k) cij+=aik*bkj; 乘法运算是上述矩阵相乘问题的基本操作，由于是乘法运算是上述矩阵相乘问题的基本操作，由于是 一个三重循环，每个循环从一个三重循环，每个循环从1

10、 1到到n n，则总次数为，则总次数为: : n nn nn=nn=n3 3 ， ， T(n)=O(nT(n)=O(n3 3) ) BME 1.4 算法和算法分析算法和算法分析 BME 例例4分析以下程序段的时间复杂度分析以下程序段的时间复杂度 for(i=1;in;i+) y=y+1; for(j=0;j=(2*n);j+) x+; 分析分析：语句的：语句的频度频度指的是指的是 该语句重复执行的次数。该语句重复执行的次数。 一个算法中所有语句的频一个算法中所有语句的频 度之和构成了该算法的运度之和构成了该算法的运 行时间。行时间。 语句语句1的频度是：的频度是：n-1 语句语句2的频度是：的

11、频度是： 12) 12)(1( 2 nnnn 则该程序段的则该程序段的时间时间 复杂度复杂度： T(n)=)(22 22 nOn 1.4 算法和算法分析算法和算法分析 /* 1 * / /* 2 * / 例例5分析以下程序段的时间复杂度分析以下程序段的时间复杂度 i=1; while(i=n) i=i*2/2的的n次方次方 BME 1.4 算法和算法分析算法和算法分析 /* 1 * / /* 2 * / BME 1.4 算法和算法分析算法和算法分析 v &常见函数的时间复杂度按数量递增排列及增长率常见函数的时间复杂度按数量递增排列及增长率。 常数阶常数阶O(1) 对数阶对数阶O(log2n) 线性阶线性阶O(n) 线性对数阶线性对数阶O(nlog2n) 平方阶平方阶O(n2) 立方阶立方阶O(n3) k次方阶次方阶O(nk) 指数阶指数阶O(2n) BME 1.4 算法和算法分析算法和算法分析 BME 1.4 算法和算法分析算法和算法分析 v算法的空间复杂度算法的空间复杂度 一个算法在计算机存储器上所占用的存储空间，包一个算法在计算机存储器上所占用的存储空间，包 括存储算法本身所占用的存储空间，算法的输入括存储算法本身所占用的存储空间，算法的输入 输出数据所占用的存储空间和算法在运行过程中输出数据所占用的存储空间和算法在运