第1章数据结构 1.pptVIP

任课教师介绍 姓名: 宋会英、孙歧峰 电话:13864717907 邮箱:songhuiying@upc.edu.cn, sunqf@upc.edu.cn QQ: 137532671 课程介绍 为什么要学习数据结构？ 该课程的主要内容是什么？如何学习？ 考核方式？ 总成绩=平时（ 40% ）+期末（70%） 平时=上机实习+平时作业+上课回答问题 +4次课内考试（每次5分） 4. 教材：殷人昆，《数据结构（面向对象方法与C++语言描述）》（第2版）清华大学出版社 为什么要学习数据结构？ 该课程的主要内容是什么？ 数据结构=数据+结构（关系） 数据结构 如何学习？ 预习：粗读教材，发现问题 听课：重点、难点，初步解决问题 复习：细读教材，解决问题（理解抽象数据类型、看懂C++类的定义和实现） 做题：巩固知识（C++类的定义和实现） 实习：验证（调试程序） 上机实习作业： 顺序表及其应用 链表及其应用.doc 栈及其应用 队列及其应用 稀疏矩阵及其基本操作 二叉树及其基本操作 堆及其基本操作 Huffman树及其基本操作 图及其基本操作 内容回顾: 1.数据结构=数据+结构=(D,R) 2.结构包括: 逻辑结构:集合、线性、树型、图 物理结构(存储结构):连续、非连续 3.数据类型：（D,R,P） 4.抽象数据类型： （D,R,P） 作业： 1.总结本章主要内容 2.自己找出或设计三个算法，并分析其时间复杂度。（要求三个算法的渐进时间复杂度不能相同） 第一章 绪论 2. 算法与数据结构的关系 算法+数据结构=程序 在计算机解决问题的过程中算法与数据结构是缺一不可的两个方面： 问题的数据组织——数据结构 数据的处理——算法 算法与数据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。 §1.4 算法定义 库额互佛轴鼓骂报懂呕烘冉区粮张卡胚咱伊匿抗乾搜回敛猛懊枯绸沽声宰第1章数据结构 1第1章数据结构 1 怎样才能设计一个好的算法呢？ 要设计一个好的算法通常要考虑以下的要求: ⑴正确： 算法的执行结果应当满足预先规定的功能和性能要求。 ⑵可读： 一个算法应当思路清晰、层次分明、简单明了、易读易懂。 ⑶健壮：当输入不合法数据时，应能作适当处理，不至引起严重后果。 ⑷高效：有效使用存储空间和有较高的时间效率。 集殃郧鬼深育迪颧娠戌遇嘲缓毗嘲呈健杏市摔粥驯缕秘贡岁蛋似侧幂叶烫第1章数据结构 1第1章数据结构 1 第一章 绪论 1. 5.1 算法的描述 1. 自然语言描述：容易，但有时罗嗦、有二义性 2. 图示（流程图、N-S图、PAD图等）：直观清晰，但不易实现 4. 算法语言（伪代码）：严谨、简洁，易程序实现 3. 程序设计语言：可以直接运行，但太严格。 §1.5 算法的性能分析与度量 为了解决理解与执行这两者之间的矛盾，人们常常使用一种称为伪码语言的描述方法来进行算法描述。伪码语言介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，而比自然语言更接近程序设计语言。它虽然不能直接执行但很容易被转换成高级语言。 退僧帅喇蛾洗初唆矽西陆疾记漫挨朵置立温园握嚷课急鬃吟码浊邓押惹惮第1章数据结构 1第1章数据结构 1 第一章 绪论 我们可以从一个算法的时间复杂度与空间复杂度来评价算法的优劣。 一个算法转换成程序并在计算机上执行时，其运行所需要的时间取决于下列因素： ⑴硬件的速度。例如使用486机还是使用586机。 ⑵书写程序的语言。实现语言的级别越高，其执行效率就越低。 ⑶编译程序所生成目标代码的质量。对于代码优化较好的编译程序其所生成的程序质量较高。 ⑷问题的规模。例如，求100以内的素数与求1000以内的素数其执行时间必然是不同的。 §1.5 算法的性能分析与度量 如何评价算法的优劣呢？ 颧广锣等必钓他蓄臣捌陡贡俊咏妮泼料徒观叹滤芋扫尾盛房厘致效剿巷优第1章数据结构 1第1章数据结构 1 第一章 绪论 显然，在各种因素都不能确定的情况下，很难比较出算法的执行时间。 也就是说，使用执行算法的绝对时间来衡量算法的效率是不合适的。为此，可以将上述各种与计算机相关的软、硬件因素都确定下来，这样一个特定算法的运行工作量的大小就只依赖于问题的规模（通常用正整数n表