第二章面向对象程序设计 和算法性能分析 2.1<数据结构>的主要内容及教学要求 计算机学院信息教研室 2.2基本术语 23算法描述及分析 lixuejun@swust.edu.cn
计 算 机 学 院 信 息 教 研 室 lixuejun@swust.edu.cn D S 第二章 面向对象程序设计 和算法性能分析 2.1 <数据结构>的主要内容及教学要求 2.2 基本术语 2.3 算法描述及分析
2.1<数据结构>的主要内容 例1: 200080-32419237621002510102780618748 计 热200080-3班号 院2419237计算机学院办公室电话号码 621002西南科技大学邮编 研室 510102780618748身份证号码 结论工.杂乱的数据不能表达和交流信息 lixuejun@swust.edu.cn
计 算 机 学 院 信 息 教 研 室 lixuejun@swust.edu.cn D S 2.1 <数据结构>的主要内容 200080-3 班号 2419237 计算机学院办公室电话号码 621002 西南科技大学邮编 510102780618748 身份证号码 例1： 200080-32419237621002510102780618748 结论1. 杂乱的数据不能表达和交流信息
21<数据结构>的主要内容 例2:电话号码簿(a1,b)(a2,b2)…(an,bn) 其中:a为某人姓名,b为该人的电话号码。 要求:设计一个算法,给定一个姓名时, 能査出此人的电话号码。 计 如果姓名和电话号码的排列次序无规律 院 则只能逐一比较姓名进行查找 ·如果姓名按字典顺序组织,则查找就快捷多了 研结论2,数据之间是有联系的 这些联系常常影响算法的选择和效率。 DS》就是要研究数据之间的联系。 lixuejun@swust.edu.cn
计 算 机 学 院 信 息 教 研 室 lixuejun@swust.edu.cn D S 2.1 <数据结构>的主要内容 例2: 电话号码簿 (a1，b1 ) (a2，b2 )…(an，bn ) 其中： ai为某人姓名，bi为该人的电话号码。 要求：设计一个算法，给定一个姓名时， 能查出此人的电话号码。 • 如果姓名和电话号码的排列次序无规律， 则只能逐一比较姓名进行查找 • 如果姓名按字典顺序组织，则查找就快捷多了 结论2. 数据之间是有联系的 这些联系常常影响算法的选择和效率。 《DS》就是要研究数据之间的联系
21<数据结构>的主要内容 例3:大学学生管理机构 学校 系 八系 计 一年级二年级三年级四年级 院 班 8班 张 李四 研结论3.数据之周是有结构的 例3中数据之间呈分层结构(树状结构) 《DS》就是要研究数据之间的各类结构。 lixuejun@swust.edu.cn
计 算 机 学 院 信 息 教 研 室 lixuejun@swust.edu.cn D S 2.1 <数据结构>的主要内容 例3：大学学生管理机构 学校 一系 ．．．八系 ．．． 一年级 二年级 三年级 四年级 １班 ．．．８班 张三．．．李四 结论３． 数据之间是有结构的 例３中数据之间呈分层结构（树状结构） 《DS》就是要研究数据之间的各类结构
21<数据结构>的主要内容 例4:图书目录管理 设每个书目含:书名,作者,登录号,分类,出版年月 对图书目录常有如下操作: 计 ·查找:某书在书库中是否存在? ·插入:购进新书时的登录; 院 删除:报废或丢失的书,需从目录中去掉; 研 室结论4.在某种数据结构上可定义一组运算 《Ds》就是要研究各类数据结构上的各种运算。 lixuejun@swust.edu.cn
计 算 机 学 院 信 息 教 研 室 lixuejun@swust.edu.cn D S 2.1 <数据结构>的主要内容 例４：图书目录管理 设每个书目含：书名，作者，登录号，分类，出版年月 对图书目录常有如下操作： • 查找：某书在书库中是否存在？ • 插入：购进新书时的登录； • 删除：报废或丢失的书，需从目录中去掉； 结论４． 在某种数据结构上可定义一组运算 《DS》就是要研究各类数据结构上的各种运算