1、严蔚敏严蔚敏 吴伟民吴伟民 清华大学出版社清华大学出版社精品课件 1.1 的主要内容的主要内容 1.2 基本术语基本术语 1.3 算法描述及分析算法描述及分析精品课件1.1 的主要内容的主要内容99080-3 班号班号 3202670 计算机学院办公室电话号码计算机学院办公室电话号码610054 电子科技大学邮编电子科技大学邮编510102780618748 身份证号码身份证号码 结论结论1.杂乱的数据不能表达和交流信息杂乱的数据不能表达和交流信息精品课件1.1 的主要内容的主要内容2:电话号码簿电话号码簿(a1,b1)(a2,b2)(an,bn)其中:其中:ai为某人姓名,为某人姓名,bi为
2、该人的电话号码。为该人的电话号码。要求:设计一个算法,给定一个姓名时,要求:设计一个算法,给定一个姓名时,能查出此人的电话号码。能查出此人的电话号码。如果姓名和电话号码的排列次序无规律,如果姓名和电话号码的排列次序无规律,则只能逐一比较姓名进行查找则只能逐一比较姓名进行查找 如果姓名按字典顺序组织,则查找就快捷多了如果姓名按字典顺序组织,则查找就快捷多了结论结论2.数据之间是有联系的数据之间是有联系的这些联系常常影响算法的选择和效率。这些联系常常影响算法的选择和效率。DS就是要研究数据之间的联系。就是要研究数据之间的联系。精品课件1.1 的主要内容的主要内容结论结论 数据之间是有结构的数据之间
3、是有结构的例中数据之间呈分层结构(树状结构)例中数据之间呈分层结构(树状结构)DS就是要研究就是要研究数据之间的各类结构数据之间的各类结构。精品课件1.1 的主要内容的主要内容结论结论 在某种数据结构上可定义一组运算在某种数据结构上可定义一组运算DS就是要研究各类数据结构上的各种运算。就是要研究各类数据结构上的各种运算。精品课件1.1 的主要内容的主要内容 常见的数据结构有:数组、栈、队列、表、常见的数据结构有:数组、栈、队列、表、串、树、图和文件等。串、树、图和文件等。精品课件数据结构与问题求解精品课件1.2 基本术语基本术语精品课件1.2 基本术语基本术语精品课件1.2 基本术语基本术语精
4、品课件1.2 基本术语基本术语精品课件1.3 算法算法描述和算法分析描述和算法分析算法基本特性:有穷性:算法经有限步后结束;确定性:下一步必须是明确的;可行性:每一步是可执行的;精品课件1.3 算法算法描述和算法分析描述和算法分析主要区别在:主要区别在:有穷性有穷性 和和描述方法描述方法 程序可以是无穷的,例如程序可以是无穷的,例如OS,算法是有穷的;算法是有穷的;程序是用程序设计语言描述,在机器上可以执行;程序是用程序设计语言描述,在机器上可以执行;算法还可以用框图、自然语言等方式描述。算法还可以用框图、自然语言等方式描述。精品课件1.3 算法描述算法描述和算法分析和算法分析精品课件1.3 算法描述算法描述和算法分析和算法分析精品课件1.3 算法描述算法描述和算法分析和算法分析精品课件1.3 算法描述算法描述和算法分析和算法分析精品课件1.3 算法描述算法描述和算法分析和算法分析精品课件1.3 算法描述和算法描述和算法分析算法分析精品课件1.3 算法描述和算法描述和算法分析算法分析精品课件精品课件