数据结构数据结构第第1 1章章 绪论绪论北京邮电大学电信工程学院北京邮电大学电信工程学院 计算机技术中心计算机技术中心2024/7/221数据结构数据结构任课教师任课教师 徐雅静 Email :phoenix-jing263.net 办公室：教2-415 电话：21002024/7/222数据结构数据结构一、学习方法一、学习方法 勤于思考、亲手实践二、课程组成二、课程组成 实验：30分 平时作业: 10分 期末考试：60分2024/7/223数据结构数据结构数据结构是什么？数据结构是什么？n数据结构是人们在长期写程序的过数据结构是人们在长期写程序的过程中总结出来的对程中总结出来的对数据组织数据组织, ,数据操数据操作作方面的精华方面的精华2024/7/224数据结构数据结构为什么要学习数据结构？为什么要学习数据结构？n数据结构就是教你怎样用最精简的语数据结构就是教你怎样用最精简的语言，利用最少的资源（包括时间和空言，利用最少的资源（包括时间和空间）编写出间）编写出最优秀最合理的程序最优秀最合理的程序。n换句话说数据结构存在的意义就是使换句话说数据结构存在的意义就是使程序最优化程序最优化。2024/7/225 数据结构不是教你怎样才能编数据结构不是教你怎样才能编程，而是教你怎样才能编好程，程，而是教你怎样才能编好程，一种思维方式的学习。一种思维方式的学习。2024/7/226数据结构在软件开发中的地位数据结构在软件开发中的地位系统分析系统分析系统实现系统实现系统维护系统维护系统设计系统设计2024/7/227思考题思考题题目：题目：n已知有已知有n n个整数的序列，查找指定个整数的序列，查找指定数值数值keykey是否在该序列中，如果存是否在该序列中，如果存在，找出该数值在序列中的位置。在，找出该数值在序列中的位置。1 1、数据组织、数据组织2 2、数据操作、数据操作2024/7/228算法实现算法实现int search(int a, int n, int key)int i； for (i=0; in; i+) if(ai=key)return i+1; return 0;如何优化？如何优化？1、分析程序耗时的地方2024/7/229分析程序耗时的关键点分析程序耗时的关键点int search(int a, int n, int key) for (int i=0; i0)？ for(int i=0; in; i+) n+1 for(int j=i; j无穷大无穷大n表示表示: 随着问题规模随着问题规模 n 的增大，算法执行时间的增长的增大，算法执行时间的增长率和率和 f(n) 的增长率相同。的增长率相同。 例如：例如： limT(n)/n2 = lim(n2+3n+1)/n2=1 说明说明T(n)和和n2是同价的，记作是同价的，记作O(n2).2024/7/2251时间复杂度x=x+1; O(1)for(int i=0;in;i+) x+; O(n)for(int i=0;in;i+) for(int j=0;jm;j+) x+; O(n*m) or O(n2)for(int i=1;in; i=2*i) +x; O(log2n)2024/7/2252算法分析空间复杂度空间复杂度 算法在执行过程中，需要的算法在执行过程中，需要的辅助空间辅助空间的数的数量。辅助空间是指除了算法本身和输入和输出量。辅助空间是指除了算法本身和输入和输出以外临时开辟的空间。也是问题规模以外临时开辟的空间。也是问题规模n n的函数，的函数，计算方法与时间复杂度类似。计算方法与时间复杂度类似。2024/7/2253本章总结本章总结绪绪绪绪 论论论论数据结构数据结构数据结构数据结构算算算算 法法法法基基本本概概念念逻逻辑辑结结构构存存储储结结构构数据数据数据元素数据元素数据对象数据对象ADT逻辑结构逻辑结构数据结构数据结构的分类的分类存储结构存储结构常用存储常用存储方法方法基基本本概概念念算算法法分分析析算法算法算法特性算法特性评价算法评价算法描述算法描述算法问题规模问题规模基本语句基本语句时间复杂度时间复杂度大大O记号记号关关 系系思考题如何生成不重复的随机数？如何生成不重复的随机数？ 题目：题目： 生成值是生成值是1-71-7的的7 7个不同的随机数，考虑时间个不同的随机数，考虑时间效率效率2024/7/2255思考1 公元公元5世纪末，我国古代数学家张丘建在世纪末，我国古代数学家张丘建在它所撰定的算经中，提出这样一个问题：它所撰定的算经中，提出这样一个问题：“鸡翁一，值钱五；鸡母一，值钱三，鸡雏三，鸡翁一，值钱五；鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问鸡翁、母、雏各几何值钱一，百钱买百鸡，问鸡翁、母、雏各几何？” 试设计算法求解该问题，并分析你的算法试设计算法求解该问题，并分析你的算法的时间复杂度的时间复杂度。2024/7/2256关键函数void main()for(int i=0; i20; i+) for(int j=0;j33-i; j+) int k=100-i-j; if (5*i+3*j+k/3.0=100) cout鸡翁：鸡翁：i 鸡母：鸡母：j 鸡雏：鸡雏：k0) coutchangei“美分:”rest/changeiendl; rest= rest % changei+; 2024/7/2260