散列( hashing)的方法 数据的运算 110 逻辑结构和存储结构都相同,但 运算不同,则数据结构不同 例如,栈与队列 ■对于一种数据结构,常见的运算 建立、清除数据结构 插入、删除、修改某个数据元素 H(k)=k%11 排序、检索 举位▲张倍墙写 北大单张铭写 叔新有,命邮 排序问题 抽象数据类型ADT ■ Google等搜索引擎返回结果排级 图书馆员书目编号、上架 抽象数据类型是定义了一组运算 各种排名 的数学模型 (霜与B)x套学排名 剥离存储与实现细节 保研成绩排名 在适当的抽象层次上考虑程序的 Windows资源管理器,文件查看 结构和算法 封装和信息隐蔽 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 栈的不同存储实现 ■逻辑、存储、运算三者不同,都 插入、删除、检索都只能被限制在 可以看作不同数据结构 同一端的线性表先进后出LFo ■忽略存储,强调逻辑、运算则为 顺序实现 ADT [3 max size-1 ■不特别指明,允许使用sTL ■链表实现 機顶 北真大学张铭编写 聊张帖写 权新有,究10 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 55 散列（hashing）的方法 H(k) = k % 11 0 1 2 3 4 5 6 7 8 9 10 77 14 7 75 110 6295 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 56 数据的运算 „ 逻辑结构和存储结构都相同, 但 运算不同, 则数据结构不同 „ 例如, 栈与队列 „ 对于一种数据结构, 常见的运算 „ 建立、清除数据结构 „ 插入、删除、修改某个数据元素 „ 排序、检索 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 57 排序问题 „ Google等搜索引擎返回结果排级 „ 图书馆员书目编号、上架 „ 各种排名 „ 《泰晤士报》 大学排名 „ 《福布斯》 富豪榜 „ 保研成绩排名 „ …… „ Windows资源管理器，文件查看 „ …… 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 58 抽象数据类型ADT „ 抽象数据类型是定义了一组运算 的数学模型 „ 剥离存储与实现细节 „ 在适当的抽象层次上考虑程序的 结构和算法 „ 封装和信息隐蔽 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 59 „ 逻辑、存储、运算三者不同，都 可以看作不同数据结构 „ 忽略存储，强调逻辑、运算则为 ADT „ 不特别指明，允许使用STL 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 60 栈的不同存储实现 „ 插入、删除、检索都只能被限制在 同一端的线性表先进后出LIFO „ 顺序实现 „ 链表实现 栈顶 5 4 8 7 1 element [0] [1] [2] [3] [4] max_size - 1 N 1 2 3 4 栈顶