数据结构案例教程 第1章 数据结构与算法.pptVIP

分析算法可知，i的取值范围为1~n；对于求前i个元素的最大值时，需要元素比较(i-1)-1+1=i-1次。在等概率的情况下： 本算法的平均时间复杂度为O(n)。 Page ? * 1.2.3 数据结构+算法=程序 N.Wirth的“数据结构+算法=程序”公式对计算机科学的影响程度足以媲美物理学中爱因斯坦的E=MC2——一个公式展示出了程序的本质。 程序设计是必须认真规划的系统工程，从数据结构的设计到算法的设计，都应在可行性的基础上充分考虑其效率、扩展、异常和可维护性等。 Page ? * 1.3 案例问题解决 1.3.1 1787年高斯算法——比较算法优劣 【源程序】 void main() { int sum=0; //高斯的算法 sum=(1+100)*100/2; printf(sum=%d\n,sum); sum=0; //其小伙伴的算法 for(int i=1;i=100;i++) sum+=i; printf(sum=%d\n,sum); } 比较两个算法可知，高斯算法的时间复杂度为O(1)，而其小伙伴们的算法的时间复杂度为O(n)。 Page ? * 1.3.2 2014年高斯算法——比较结构优劣 【源程序】 void main() { const int N=100 int a[N]={12,23,34,45,56,76,34,23,67……},sum=0; for(int i=0;iN;i++) sum+=a[i]; printf(Sum=%d\n,sum); } 虽然此处高斯算法的时间复杂度为O（n），而其同学直接累加的时间复杂度为O(1)，但采用数组的循环编写程序比用直接累加100个变量或用计算器累加100个常数要方便得多。更重要的是，由于数据与算法耦合较小，前者比后者更容易理解和维护。 Page ? * 1.4 知识与技能扩展 1. ACM程序设计大赛 ACM程序设计大赛是大学级别最高的脑力竞赛，素来被冠以“程序设计的奥林匹克”之称。大赛自1970年开始，至今已有40几年历史，是世界范围内历史最悠久、规模最大的程序设计竞赛。 2.《计算机程序设计艺术》 高德纳（Don E.Knuth）所著的《计算机程序设计艺术》被称为程序设计的圣经。像KMP这样令人不可思议的算法，在此书中比比皆是。难怪连 Bill Gates都说：“如果能做对书里所有的习题，就直接来微软上班吧！” Page ? * 1.4.3 上机实战 1.编写一个程序，计算任意输入的正整数的各位数字之和，并分析算法的时间复杂度。 2.编写一个程序，打印九九乘法表，并分析算法的时间复杂度。 Page ? * 第1章 数据结构与算法 数据结构案例教程 案例提出——高斯的巧妙解题 1787年高斯巧妙解题：1787年，在德国一所乡村小学的三年级课堂里，数学老师为了惩罚吵闹的学生，出了一道计算题：1＋2＋3＋4＋5＋…＋98＋99＋100。。。 请根据时间复杂度分析法比较高斯和他的小伙伴们的算法优劣。 Page ? * 案例提出——高斯的巧妙解题 时间穿越到了2014年，在德国一所乡村小学的三年级信息技术课堂里，计算机老师为了惩罚吵闹的学生，出了一道编程题：先用文本文件记录100个没有规律的数字，然后将文件分发给学生，要求学生利用计算机编程求出它们的和。 请根据时间复杂度分析法比较高斯和他的小伙伴们的算法优劣。 Page ? * 1.2 知识点学习——1.2.1 数据结构 1.2.1.1 数据结构相关概念 数据是用符号对现实世界的事物及活动做出的抽象描述，其中符号可以是文字符号、数字符号以及其他规定的符号。 数据元素是数据的基本单位。例如，201302班点名册中的每个学生记录都是一个数据元素。数据元素也可称为元素、结点、顶点、记录等，在计算机中通常被作为一个整体来进行考虑和处理。 Page ? * 1.2 知识点学习——1.2.1 数据结构 数据结构是指数据和数据之间的关系，可以看成是相互之间存在着某种特定关系的数据元素的集合。数据结构包括数据的逻辑结构、数据的物理结构和数据的运算3个方面。 逻辑结构 物理结构（存储结构） Page ? * Page ? * 《数据结构案例教程》 Page ? * 哥，我们这么好的组合，咋总打败仗呢？ 【例1.1】 表1.1所示的学生表中的数据元素是学生记录，每个数据元素由4个数据项(即学号、姓名、性别和年龄)组成。试讨论其存储结构。 Page ? * 学 号 姓 名 性 别 年 龄 3 张飞 男 18 2 刘备 男 23 14 关羽 男 19 5 小乔 女 18 26 吕布 男 21 12 貂婵 女 17 表1.1 学生表 数