数据结构案例教程（CC++版）第2版 课件 第1章 绪论

2024/9/261数据结构案例教程2024/9/262导学问题1问题中的数据在计算机中如何组织？（1-1）计算某位同学高等数学、英语及计算机导论三门课程的总分。（1-2）已知一个班级20名学生的高等数学成绩，求全班该门课的平均分。（1-3）已知一个班级20名学生的高等数学、英语及计算机导论课程的成绩，计算每位同学的总分以及全班三门课程各自的均分。2024/9/263导学问题1问题中的数据在计算机中如何组织？（1-4）在问题1-3的基础上，列出全班成绩的排名（列出学号、姓名及分数），如表1-1所示。2024/9/264导学问题1问题中的数据在计算机中如何组织？（1-5）假设一个U盘中有3个文件夹，每个文件夹中又有若干文件，如图1-1所示。请设计一种文件信息存储方法，当输入某个文件名称后，显示该文件在U盘中的存储路径，若U盘中无该文件，则显示“文件未找到”。2024/9/265导学问题1问题中的数据在计算机中如何组织？（1-6）某城市中5个地标建筑间有多条道路相通，每条道路长度不同，如图1-2所示。设计一个道路查询系统，能让游客查询从任一个地标建筑到另一个地标建筑之间的最短路径。2024/9/266导学问题1的分析计算机处理的对象由数值发展到非数值数据，而且处理的数据量也越来越大。在程序设计时面对这样的数据，需要解决如何表示这些数据间的结构关系？如何在计算机中存储这些数据？计算机处理的不再只是加减乘除等数值计算，而是排序、信息可视化、求最短路径等较为复杂的非数值计算。在程序设计时，需要解决如何在问题数据上进行非数值计算等操作？以上这些问题正是数据结构这门课程研究的内容。2024/9/267导学问题2编程实现对输入的整数n计算sum=1!+2!+3!+4!+…+n!doublesum(intn){doubles=0;inti,j;doublep;for(i=1;i<=n;i++){p=1;for(j=1;j<=i;j++) p*=j;s+=p;}returns;}2024/9/268导学问题2的分析可考虑将双重循环，进一步简化为单重循环：doublesum2(intn){doubles=0;inti;doublep=1;for(i=1;i<=n;i++){ p*=i; s+=p;}returns;}为什么用单重循环实现比用双重循环实现有效？2024/9/2691.1知识学习1.1.1数据结构课程的研究内容数据结构就是研究非数值计算问题中的数据以及它们之间的关系和操作算法的学科，具体主要包含3个方面的内容：数据的逻辑结构、数据的存储结构（物理结构）和数据的操作算法。2024/9/26101.1知识学习1.1.2数据的结构相关术语

数据

数据元素

数据对象数据结构的三个要素

数据结构涉及三个要素，分别是数据的逻辑结构、存储结构和操作算法2024/9/26111.1知识学习1.1.3算法与算法分析1.什么是算法2.算法的评价3.算法的描述方法2024/9/2612算法性能分析与度量算法的性能标准算法的事前估计算法的后期测试2024/9/2613算法性能分析与度量算法的性能标准正确性健壮性可读性高效率低存储空间算法的事前估计算法的后期测试2024/9/2614

算法性能分析与度量算法的性能标准算法的事前估计时间复杂度空间复杂度算法的后期测试2024/9/2615算法性能分析与度量算法的性能标准算法的事前估计时间复杂度空间复杂度存储空间的固定部分

程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占的空间可变部分

尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间、通过new和delete命令动态使用的空间2024/9/26161.2知识应用导学问题1-4的数据结构2024/9/26171.2知识应用导学问题1-5的数据结构2024/9/26181.2知识应用导学问题1-6的数据结构2024/9/26191.2知识应用导学问题2的时间复杂度问题2的原始程序是一个双重循环，其中外循环体中的语句p=1;执行次数为n；外循环体中的语句s+=p;执行次数为n；内循环体中语句p*=j;的执行次数为：1+2+3+…+n=n(n+1)/2；因此该程序的基本语句执行次数是n2数量级，时间复杂度T(n)=O(n2)。改进后的程序是一个单重循环，循环体中的语句p*=j;和s+=p;分别执行了n次，因此该程序的基本语句执行次数是n数量级，时间复杂度T(n)=O(n)。2024/9/26