中国科学技术大学：《数据结构及算法》课程教学资源（PPT课件讲稿）第1章 数据结构导论（主讲：袁平波）

第一章数据结构导论 1.1数据结构的基本概念 1.2数据结构类型 1.3抽象数据类型 1.4数据与数据结构 1.5算法 1.6算法分析 ypb@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 4 中国科学技术大学 1.1数据结构的基本概念 1.2数据结构类型 1.3抽象数据类型 1.4数据与数据结构 1.5算法 1.6算法分析 第一章 数据结构导论

数据结构研究什么？ ©数据结构的历史 ·1968美国唐·欧·克努特设立《数据结构》课程 ·1976瑞士Niklaus Wirth提出程序设计=算法+数据结构 ©数据结构是研究 ·非数值类问题的对象描述、信息组织方法及其相应的操作， 即逻辑结构及其编程表示方法。 ·(1)加工对象逻辑组织(2)存储到计算机(3)数据运算 ypb@ustc.edu.cn 5 中国科学技术大学

ypb@ustc.edu.cn 5 中国科学技术大学 数据结构的历史 • 1968 美国唐·欧·克努特设立《数据结构》课程 • 1976 瑞士 Niklaus Wirth 提出程序设计=算法+数据结构  数据结构是研究 • 非数值类问题的对象描述、信息组织方法及其相应的操作 ， 即逻辑结构及其编程表示方法。 • (1) 加工对象逻辑组织（2）存储到计算机 (3)数据运算 数据结构研究什么？

d [例]、设有一个电话号码薄，有N个人的姓名和电话号码。 要求设计一个程序，按人名查找号码，若不存在则给出查找 失败的信息。 姓 名 namer nam与 name; name. 电话号码 tel tel2 tel 0444 tel (a)顺序存储 Lhead-3 names namey name name namea tels tela 6 2 (®)链式存储 ypb@ustc.edu.cn 6 中国科学技术大学

ypb@ustc.edu.cn 6 中国科学技术大学 [例]、设有一个电话号码薄，有N个人的姓名和电话号码。 要求设计一个程序，按人名查找号码，若不存在则给出查找 失败的信息

[例]井子棋、非线性数据结构-树 料料料越排 (a) (b) 井字棋对弈“树” (a)棋盘格局示例：(b)对弈树的局部. ypb@ustc.edu.cn 中国科学技木大学

ypb@ustc.edu.cn 7 中国科学技术大学 • [例] 井子棋、非线性数据结构-树

[例]交叉口交通灯设置（顶点着色问题） 非线性一图 AB AD ED (a】 (b) 五叉路口交通管理示意图 (a)五叉路口；(b)表示通路的图 ypb@ustc.edu.cn 8 中国科学技术大学

ypb@ustc.edu.cn 8 中国科学技术大学 [例] 交叉口交通灯设置（顶点着色问题） 非线性——图

1.1数据结构的基本概念 集合和关系 一集合是若干具有共同可辨特征的事物的“聚合”， 每个事物称该集合的元素或成员。 -集合元素之间一般都具有某种“关系”。 ·数据和信息 -数据是指描述客观事物且能由计算机处理的数值、 字符符号的总称 信息是包含在数据中符号的含义。数据是信息的符 号表示形式。 ypb@ustc.edu.cn 9 中国科学技术大学

ypb@ustc.edu.cn 9 中国科学技术大学 • 集合和关系 – 集合是若干具有共同可辨特征的事物的“聚合” ， 每个事物称该集合的元素或成员。 – 集合元素之间一般都具有某种“关系” 。 • 数据和信息 –数据是指描述客观事物且能由计算机处理的数值、 字符符号的总称 – 信息是包含在数据中符号的含义。数据是信息的符 号表示形式。 1.1数据结构的基本概念

数据元素 -是数据的基本单位，有时称记录、结点、顶点。其包 括数据项(Data Item),数据项可以是原子项（性别） 或组合项（出生日期） ·数据对象 一是性质相同的数据元素的集合，是数据的一个子集。 。 关键码(key) 数据元素中起识别作用的数据项。有主次之分，能唯 一识别的称主码，否则称次码。 ypb@ustc.edu.cn 10 中国科学技术大学

ypb@ustc.edu.cn 10 中国科学技术大学 • 数据元素 –是数据的基本单位，有时称记录、结点、顶点。其包 括数据项（Data Item），数据项可以是原子项（性别） 或组合项（出生日期） • 数据对象 – 是性质相同的数据元素的集合，是数据的一个子集 。 • 关键码（key） – 数据元素中起识别作用的数据项。有主次之分，能唯 一识别的称主码，否则称次码

。1 数据结构 特性相同的数据元素构成的集合中，如果在数据 元素之间存在一种或多种特定的关系，则称之为数据 结构。 Data-Structure=(D,S) ypb@ustc.edu.cn 11 中国科学技木大学

ypb@ustc.edu.cn 11 中国科学技术大学 • 数据结构 特性相同的数据元素构成的集合中，如果在数据 元素之间存在一种或多种特定的关系，则称之为数据 结构 。 Data-Structure=(D,S)

1.2数据结构类型 集合 D={1,2,3,4,5}R={0 线性结构 3 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 12 中国科学技术大学

ypb@ustc.edu.cn 12 中国科学技术大学 1.2数据结构类型 • 集合 D={1,2,3,4,5｝ R={} • 线性结构 linear=(D,R) D={1,2,3,4,5,6,7,8,9,10} R={,,,,,, ,,} 1 2 3 4 5

树形结构 Tree=(D,R) D={a,b,c,d,e,f,g,h,i,j,k,1) R={Ka,b>,,,,,,, ,,,} ypb@ustc.edu.cn 13 中国科学技木大学

ypb@ustc.edu.cn 13 中国科学技术大学 • 树形结构 Tree=（D,R） D={a, b, c, d, e, f, g, h, i, j, k, l} R={,,,,,,, ,,,}