数据结构第一章绪论_图文.pptVIP

学而不思则罔，思而不学则殆。 行有余力，则以学文？ 浙江工业大学之江学院教师首堂课授课申明 教师是课堂管理的第一责任人，为营造良好的课堂氛围，提高课堂教学质量，教师在开学第一堂课要告知学生课堂学习的注意事项，主要包含以下内容： 1、课程名称（数据结构）、学时数（64）、考核方式（考试）、作业次数（9）等。 2、成绩评定：平时成绩占 40 %，期末成绩占 60 % 。 3、根据《学籍管理实施细则》第十四条：一学期缺课（包括病假、事假、旷课等）累计超过本课程总学时的三分之一、一学期缺交作业达三分之一、抄袭他人作业和实验报告经批评教育仍不改正、旷考或无故不参加平时测验者，不得参加本课程学期考核，并不得补考，需参加重新学习。 4、根据《学籍管理实施细则》第七条，一学期累计旷课达10学时，给予警告处分；累计旷课达20学时给予严重警告处分；累计旷课达30学时给予记过处分；累计旷课达40学时给予留校察看处分；因旷课屡次受处分并经教育不改的，可以给予开除学籍处分。 5、课堂纪律：爱护教学设施；不得穿背心、拖鞋进教室；不在课堂教学过程中吃东西；教室内禁止吸烟，不随意吐痰，不乱丢纸屑果皮杂物；不在教室内大声喧哗，不准玩手机。 授课内容：第1章～第9章 及时、认真完成课后习题 预习并完成指定实验 上课不能迟到、早退、旷课 准备一个笔记本 成绩总评比例： 习题20% 实验20% 闭卷考试60% 1.1 数据结构的概念 1.2 抽象的数据类型 1.3 算法和算法分析 学习目标 掌握基本概念，尤其是数据逻辑结构和存储结构之间的关系。 理解抽象数据类型的定义、表示和实现方法。 明确算法的作用，并掌握算法时间复杂度的估算方法。 Donald Knuth自传的开头这样写道： “Donald Knuth真的只是一个人么？”作为世界顶级计算机科学家之一，Knuth教授已经完成了编译程序、属性文法和运算法则的前沿研究，并编著完成了已在程序设计领域中具有权威标准和参考价值的书目的前三卷(《计算机程序设计艺术第1卷 基本算法》）。 程序是计算机处理问题编制一组指令集。 算法是处理问题的策略。 数据结构是解决问题的数学模型。 例1： 求一组（n个）整数中的最大值 算法：基本操作是“比较两个数的大小” 模型：线性表，数据的取值取决于整数值的范围 ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 GB/T 11457-2006中定义算法为： 用有限步数求解某问题的一套明确定义的规则的集合。例如，求sin(x)到给定精度的一系列算术运算的顺序的完整规格说明； 为执行特定任务的任何运算序列。 算法具有五大特性： 输入 。有0个或多个输入； 输出 。有一个或多个输出； 确定性。 每步定义都是确切、无歧义的； 有穷性 。算法应在执行有穷步后结束； 可行性 。每一条运算应足够基本。 算法的性能标准包括： 正确性 能正确实现预定的功能和性能； 可使用性 能方便使用； 可读性 可理解、可测试和可修改； 效率 执行算法时计算机资源的消耗，包括时间代价和空间代价； 健壮性 对不同的输入能做出相应的响应。 一个特定算法的“运行工作量”的大小，依赖于：问题的规模（问题规模函数）；数据元素初始状态。 算法复杂度的度量属于事前估计，可分为： 时间复杂度度量：当问题的规模以某种单位从1增加到n时，解决这个问题的算法在执行时所耗费的时间也以某种单位由1增加到T(n)。 空间复杂度度量：当问题的规模以某种单位从1增加到n时，解决这个问题的算法在执行时所占用的存储空间也以某种单位由1增加到S(n)。 存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占的空间。 存储空间的可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间、通过new和delete命令动态使用的空间。 假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作： T (n) = O(f(n)) T (n) 为算法的(渐近)时间复杂度 从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。 设T(n)和f(n)是将非负整数映射为实数的函数。如果存在常数c0和整常数n0≥1对于每个n ≥n0，满足T(n) ≤c·f(n)，则称T(