数据结构与STL-第1章-绪论

1、第一章 绪论北京邮电大学信息与通信工程学院数据结构与STL1数据结构与STL第一章 绪论学习内容：1.1 数据结构的起源 1.2 数据结构的基本概念 1.3 算法和算法分析 1.4 STL与数据结构1.5 实例分析2数据结构与STL1.1 数据结构的起源程序设计的两个重要问题： 待处理的数据存储到计算机内存设计相应的算法操作这些数据数据表示数据处理 对数据的处理 数据的逻辑表示数据的存储方法数据结构课程内容3数据结构与STL起源数据结构是计算机及其相关专业的重要课程计算机发展初期：处理数值计算问题 不重视数据结构 20世纪6080年代：非数值处理问题 沃思：算法 + 数据结构 = 程序 20世

2、纪80年代至今：面向对象(OO)技术出现 数据结构与面向对象具有天然的对应 4数据结构与STL第一章 绪论学习内容：1.1 数据结构的起源 1.2 数据结构的基本概念 1.3 算法和算法分析 1.4 STL与数据结构1.5 实例分析5数据结构与STL1.2 数据结构的基本概念数据（data）信息的载体分为两类：数值型数据、非数值型数据数据元素（data element）也称为元素、结点、顶点或记录是数据的基本单位，在计算机程序中通常作为一个整体进行处理。数据项（data item）也称为字段或域构成数据元素的不可分割的最小单位。每个数据元素可以包含多个不同的数据项。数据类型（data type

3、）具有相同性质的计算机数据的集合以及在这个数据集合上的一组操作。可分为简单类型和构造类型。struct Studentint No;char name10;float score;int age;char sex;stu10=1,张三,90,19,M,2,张莉,95,18,F;分析上述代码，哪些是：数据、数据元素、数据项、数据类型？6数据结构与STL数据结构的概念数据结构（data structure）是指按照某种逻辑关系组织起来的一组数据，按一定的存储方式存储在计算机的存储器中，并在这些数据上定义了一组运算的集合。通常人们认为数据结构包含三个方面的内容：对数据的操作或运算 数据的逻辑结构 数

4、据的存储结构 7数据结构与STL数据的逻辑结构描述数据相互间的关联形式或邻接形式反映了数据内部的构成方式定义了数据的本质特点常常将数据的逻辑结构直接称为数据结构数据的逻辑结构独立于计算机，与存储方式无关，可认为是从具体问题抽象出来的数学模型。数据元素之间不同的逻辑特点代表不同的逻辑结构四 种 常 见 的 逻 辑 结 构(a)集合 (b)线性结构 (c)树结构 (d)图结构8数据结构与STL数据的存储结构 考虑如何在计算机的存储器中存储各个数据元素，并且同时反映数据元素间的逻辑关系。对于每种逻辑结构，都可以设计多种存储方法基本的两种存储结构顺序存储结构链式存储结构9数据结构与STL每学习一种数据

5、结构各种数据结构的学习主线其逻辑结构是什么？可有哪些运算？有哪些存储结构？C+如何描述各种存储结构基于每种存储结构，各种运算如何实现？各种存储结构的优缺点对比10数据结构与STL第一章 绪论学习内容：1.1 数据结构的起源 1.2 数据结构的基本概念 1.3 算法和算法分析 1.4 STL与数据结构1.5 实例分析11数据结构与STL1.3 算法和算法分析算法解题的方法数据的运算是通过算法（algorithm）描述的讨论算法的效率和性能是数据结构课程的重要内容算法通常满足5个准则：输入：具有0个或多个输入的参数。输出：算法执行要有输出结果。有穷性：算法中每条指令的执行次数必须是有限的。确定性：

6、每条指令必须有确切的含义，无二义性。可行性：每条指令的执行时间都是有限的。 常见的算法描述方法：自然语言流程图伪代码程序设计语言 12数据结构与STL欧几里得算法描述举例辗转相除法求两个自然数m和n的最大公约数，假定mn 自然语言描述： 流程图描述：(1) 输入m和n；(2) 取得m除以n的余数r；(3) 若r=0，则n为最大公约数，算法结束；否则执行第(4)步；(4) 将n放到m中，r放到n中；(5) 重复执行第(2)步。13数据结构与STL欧几里得算法描述举例伪代码描述： 程序设计语言描述： 1. input m,n2. r=m%n;3. while (r!=0) 3.1 m=n; 3.2

7、 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;14数据结构与STL欧几里得算法描述举例采用面向对象的方法描述： class NaturalNumberpublic: unsigned long int EUCLID(NaturalNumber & n); /欧几里德算法求解最大公约数 /其它外部接口private: unsigned long int num; /存储真正的自然数;/返回欧几里德算法求解最大公约数un

8、signed 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; return n;15数据结构与STL算法好坏的评价:算法的时间复杂度算法的空间复杂度算法的可读性.算

9、法的执行时间:与哪些因素相关？问题规模通常是指算法处理的数据量的大小，记作 n。运行算法所需要的时间T可看作问题规模n的函数，记作T(n)。 算法分析 计算工具 对算法执行时间的度量算法本身 以及？问题的规模16数据结构与STL语句的频度（frequency count） 即：语句执行的次数 假定每条语句执行一次所需的时间是单位时间，则每条语句执行的时间正比于该语句执行的次数 算法运行时间算法中所有语句的频度之和。 for (i=0; in; i+) n+1 for (j=0; jn; j+) n(n+1) k+; n2语句的频度算法的总用时：T(n)=2n2+2n+1 17数据结构与STL算

10、法的渐进时间复杂度简称为T(n)与n2是同阶的 T(n)与n2是同数量级的记作T(n)=O(n2) 称T(n)=O(n2)为算法的时间复杂度时间复杂度也可以利用算法中的基本语句计算 基本语句：执行次数与算法的执行次数成正比的语句。 18数据结构与STL分析算法的时间复杂度 j += i;i = j - i;j = j - i;for (i=0;i100;i+) for (j=0;ji;j+)sum += j;for (i=0;in;i+) for (j=0;j=i;j+)sum += j;O(1)O(1)O(n2)19数据结构与STLy=0;while (y+1)*(y+1)=n) y+; T

11、(n)+1)2 nT(n)=O(n1/2) i=0,j=0;while (i+jj) j+;else i+;O(n) 20数据结构与STL特殊情况下的算法时间复杂度最好时间复杂度最坏时间复杂度平均时间复杂度 在数组an中查找值为k的元素，若找到返回其位置i（0in），否则返回-1。int i=n-1;while(i=0 & ai!=k) i-;return i;O(1) O(n) O(n) 21数据结构与STL时间复杂度的思考？多项式时间问题(polynomial time problem)存在以问题规模n为变量的多项式函数p(n)，解决问题的算法的时间复杂度为O(p(n) P问题指数时间算法

12、：时间复杂度函数不能用多项式函数界定 O(？) 1, log2n, n1/2, n, nlog2n, n2 , n3, 2n, 3n, nn , n!, nlogn ?22数据结构与STL常见的时间复杂度常数阶O(1)、对数阶O(logn)、线性阶O(n)、线性对数阶O(nlogn)、平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)、指数阶O(2n)等。当问题规模n较大时，具有指数阶量级的算法是不可计算的NP问题非确定性多项式时间问题:non-deterministic polynomial time problem对于NP问题，人们可能还不清楚是否存在一个能在多项式的时间里解决它的算法

13、，但可以在多项式的时间里验证一个解。显然有：PNP 23数据结构与STL算法的空间复杂度空间复杂度算法在执行过程中所耗费的存储空间 也是问题规模n的函数 对空间复杂度的重视情况：早期：计算机系统内存较小空间复杂度非常重视现代：计算机内存储器成本降低，存储容量的不断增大 空间效率换时间效率问题规模n很大，算法的空间效率也非常重要！ 24数据结构与STL第一章 绪论学习内容：1.1 数据结构的起源 1.2 数据结构的基本概念 1.3 算法和算法分析 1.4 STL与数据结构1.5 实例分析25数据结构与STL1.4 STL与数据结构STL:Standard Template Library，标准模

14、板类是C+语言提供的一个基础模板集合，包含了各种常用的存储数据的模板类及相应的操作函数，为开发者提供了一种快速有效的访问机制L最初由惠普实验室（Hewett-Packard Labs）开发，并于1998年被定为国际标准，正式成为C+语言的标准库。是一些容器、算法和其他一些组件的集合，这些容器有list，vector，set，map等。 26数据结构与STLSTL构成 适配器容器适配器，如stack、queue、priority_queue迭代器适配器泛函适配器 容器顺序容器：vector、list、 deque 关联容器：set、multiset、map、multimap、hash_set等

15、空间管理器迭代器泛函适配器容器算法27数据结构与STLSTL与数据结构的关系 STL与数据结构的关系密不可分STL的基础就是算法和数据结构的基本理论和研究成果目前两者仍然处于不断发展的过程中。使用STL进行编程时，程序员往往不需要花太多精力考虑一般数据的存储和常见算法的优化有了STL，算法和数据结构的基础知识不再重要？复杂数据的处理还需要程序员自己来设计高效的存储方法和算法了解算法和数据结构的知识才能更好的使用STLSTL自身就来源于算法和数据结构错！28数据结构与STLSTL应用举例 const int n = 10;int an;int n = 10;int * p = new int n

16、;int * temp = new int m; memcpy(temp, p, sizeo(int) * n);delete p;p = temp;vector a; for (int i=0;i10;i+) a.push_back(i); a.resize(100); a90=100; a.clear();a.resize(20, -1);29数据结构与STL第一章 绪论学习内容：1.1 数据结构的起源 1.2 数据结构的基本概念 1.3 算法和算法分析 1.4 STL与数据结构1.5 实例分析30数据结构与STL电话号码查询问题电话号码簿，n个人名和对应的电话号码。要求：设计一个算法，当给定任何一个人名时，该算法能打印出此人的电话号码，若没有此人，则报告标志。数据：人名和电话号码。数据表示：（1）无规则的任意排列。 （2）将人名按拼音的字母顺序排列，或按姓氏笔划排列。操作：查找。算法设计：与结构有关，如何设计。31数据结构与STL电话号码查询问题如果要求按电话号码查询人名呢？如何设计数据结构。顺序查找索引查找 32数据结构与STL田径运动会的时间安排问题 七个项目：分别为10