文档介绍：1数据结构与算法 2课程安排?讲授 3学时/周, 实验 2学时/周(分组) ?总成绩: 平时(听课、作业、期中) + 期末?教学用书: Robert L. Kruse and Alexander J. Ryba “ Data Structures and Program Design in C++ ”,高教出版社, 2001 年?参考书: 1 .数据结构,许卓群,张乃孝,杨冬青,唐世渭,高等教育出版社, 1987 年 2. 数据结构– C++ 与面向对象的途径,张乃孝,裘宗燕, 高等教育出版社, 1998 年 3 .数据结构(C 语言版),严蔚敏、吴伟民,清华大学出版社, 1997 年 4. 数据结构与算法,王若梅等著,中山大学出版社, 2000 年 3 为什么学习数据结构计算机科学是-- “一种关于信息结构转换的科学”( Wegnor ) Input Output -- “算法的学问, 算法是精确定义的一系列规则,指出怎样从给定的输入信息经过有限步骤产生所求的输出信息”(Knuth) 信息结构(数据结构)和算法是计算机科学的核心课题. +算法= puter system 4程序= 算法+ 数据结构数据结构: ?一种程序构件( programming construct) 、工具; ?编程中常用的数据组织形式及其操作的抽象;编程: ?数据结构的选择, ?算法的设计与度量 5教学目的?掌握常用的数据结构及其应用?学会合理地组织数据,有效地表示数据和处理数据?掌握算法设计技术和分析技术?提高程序设计质量 6第一章概论?什么是数据结构?抽象数据类型?算法的概念?算法的度量?数据结构示例?数据结构的概念?数据的逻辑结构?数据的存储结构 7 什么是数据结构-示例 1 例1 图书馆的书目自动检索系统所处理的基本数据( 数据元素): 每本书由(登录号,书名, 作者,出版社, 分类号) 组成; 数据元素间的关系( 逻辑结构): 一个按登录号顺序排列的书目表和按书名、作者和分类号顺序排列的索引表; 所需的操作: 一组作用在这些表上的运算(查询、插入、修改等); 怎样存储这些数据及其关系使得上述操作容易实现—存储结构。 8 什么是数据结构-示例 2 例2 人机对弈问题(三子棋)。数据元素: 格局(某时刻的棋盘布局); 格局之间的关系:一个格局可以派生出几个下一个格局(树状结构, 博弈树); 操作:由某个格局出发,借助于以上的格局树(显式地或非显式地)找出计算机赢的步骤; 存储结构:如何存储格局及其格局间的关系。 9 什么是数据结构-示例 3 例3 多岔路口的交通灯管理系统。 BA CDE 数据元素:通路, 如: A -> B 通路间的关系(图):通路为结点, 两节点相邻,如果两通路不能同时通行。操作:上图的着色问题:用最少的颜色,对每个节点着色,相邻节点着不同的颜色。存储:如何存储通路间的关系。 10 第一章概论?什么是数据结构?抽象数据类型?算法的概念?算法的度量?数据结构示例?数据结构的概念?数据的逻辑结构?数据的存储结构