第一章绪论 1.1《数据结构》讨论范畴 1.2基本概念和术语 1.3抽象数据类型的表示与实现 1.4算法和算法分析 ypb@ustc.edu.cn 中国科学技木大学
ypb@ustc.edu.cn 7 中国科学技术大学 1.1《数据结构》讨论范畴 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 第一章 绪论
1.1《数据结构》 研究什么 ©算法+数据结构=程序设计 ·1968美国唐·欧·克努特设立《数据结构》课程 ·1976瑞士Niklaus Wirth提出算法+数据结构=程序设计 ©数据结构是讨论非数值类问题的对象描述、信息组 织方法及其相应的操作 [例]、设有一个电话号码薄，有N个人的姓名和电话 号码。要求设计一个程序，按人名查找号码，若 不存在则给出不存在的信息。 ypb@ustc.edu.cn 8 中国科学技术大学
ypb@ustc.edu.cn 8 中国科学技术大学 1.1《数据结构》研究什么 算法+数据结构=程序设计 • 1968 美国唐·欧·克努特设立《数据结构》课程 • 1976 瑞士 Niklaus Wirth提出算法+数据结构=程序设计 数据结构是讨论非数值类问题的对象描述、信息组 织方法及其相应的操作 [例]、设有一个电话号码薄，有N个人的姓名和电话 号 码。要求设计一个程序，按人名查找号码，若 不存在则给出不存在的信息
姓 名 namey name name, 年44 namee 电话号码 tel tel2 tel tel (a)顺序存储 Lhead=3 names name, name namey name. tels tel telr tel tela 6 5 4 2 2 ()链式存储 ypb@ustc.edu.cn 9 中国科学技木大学
ypb@ustc.edu.cn 9 中国科学技术大学
[例]下棋井子棋非线性数据结构-树 特料排 (a) (b) 图1.2片字棋对弈“树” (a)棋盘格局示例：(b)对弈树的局部。 ypb@ustc.edu.cn 10 中国科学技术大学
ypb@ustc.edu.cn 10 中国科学技术大学 • [例] 下棋 井子棋 非线性数据结构-树
[例]交叉口交通灯设置（顶点着色问题） 非线性一图 AB AD BL DO ED (a) 图1.3五叉路口交通管理示意图 (a)五叉路口；(b)表示通路的图 ypb@ustc.edu.cn 11 中国科学技木大学
ypb@ustc.edu.cn 11 中国科学技术大学 [例] 交叉口交通灯设置（顶点着色问题） 非线性——图
1.2基本概念和术语 >数据：数据是客观事物的符号表示。 >数据元素：数据的基本单位，通常看作一个整体。 >数据对象：性质相同的数据元素的集合。 >关系：集合中元素之间的相关性。 > 数据结构：特性相同的数据元素构成的集合中，如 果在数据元素之间存在一种或多种特定的关系，则 称之为数据结构。 Data-Structure=(D,S) D是元素有限集，S是关系有限集。 四类基本结构：1)集合2)线性3)树形4)网状（图） ypb@ustc.edu.cn 12 中国科学技术大学
ypb@ustc.edu.cn 12 中国科学技术大学 1.2 基本概念和术语 ➢ 数据：数据是客观事物的符号表示。 ➢ 数据元素：数据的基本单位，通常看作一个整体。 ➢ 数据对象：性质相同的数据元素的集合。 ➢ 关系：集合中元素之间的相关性。 ➢ 数据结构：特性相同的数据元素构成的集合中，如 果在数据元素之间存在一种或多种特定的关系，则 称之为数据结构 。 Data-Structure=(D,S) D是元素有限集，S是关系有限集。 四类基本结构：1)集合 2)线性 3)树形 4)网状(图)
[例] linear=(D,R) D={1,2,3,4,5,6,7,8,9,10} R={,,,,, ,,,} 0-0-0-0-0-0-00-0-0 ypb@ustc.edu.cn 13 中国科学技术大学
ypb@ustc.edu.cn 13 中国科学技术大学 [例] linear=(D,R) D={1,2,3,4,5,6,7,8,9,10} R={,,,,, ,,,}
[例]tree=（D,R) D=(a,b,c,d,e,f,g,h,i,j,k,1} R={,,,,,,,, ,,} d ypb@ustc.edu.cn 14 中国科学技术大学
ypb@ustc.edu.cn 14 中国科学技术大学 [例]tree=（D,R） D={a, b, c, d, e, f, g, h, i, j, k, l} R={,,,,,,,, , ,}
[例] graph=(D,R) D={1,2,3,4,5,6,7,8,9) R={,,,,,,,,,,,,,} ypb@ustc.edu.cn 15 中国科学技木大学
ypb@ustc.edu.cn 15 中国科学技术大学 [例] graph=(D,R) D={1, 2, 3, 4, 5, 6, 7, 8, 9} R={,,,,,,,, ,,,,,}
其他概念与术语 >逻辑结构/物理结构（存储结构） >位(bit)/字节(Byte) >元素(Element)/结点(Node)/数据域(DataField) >顺序存储/链式存储 > 数据类型：值的集合和定义在这个值集上的一组 操作的总称。分原子和结构两种类型。 >抽象数据类型(Abstract Data Type): 一个数学模型以及定义在该模型上的一组操作。 ypb@ustc.edu.cn 16 中国科学技术大学
ypb@ustc.edu.cn 16 中国科学技术大学 其他概念与术语 ➢ 逻辑结构/物理结构(存储结构) ➢ 位(bit)/字节(Byte) ➢ 元素(Element)/结点(Node)/数据域(DataField) ➢ 顺序存储/链式存储 ➢ 数据类型：值的集合和定义在这个值集上的一组 操作的总称。分原子和结构两种类型。 ➢ 抽象数据类型(Abstract Data Type)： 一个数学模型以及定义在该模型上的一组操作