第1章数据结构的基本概念

1、单击此处编辑母版标题样式单击此处编辑母版标题样式单击此处编辑母版文本样式单击此处编辑母版文本样式第二级第二级第三级第三级第四级第四级第五级第五级1Computer Software Technology计算机软件技术基础计算机软件技术基础冯花平冯花平北京工业大学耿丹学院信息工程系北京工业大学耿丹学院信息工程系单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级2Computer Software Technology第第1 1章章 数据结构基本概念数据结构基本概念1.1 1.1 什么是数据结构

2、什么是数据结构 1.2 1.2 基本概念和术语基本概念和术语1.3 1.3 算法及其分析算法及其分析单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级3Computer Software Technology3下面文字的含义： 漆黑的头发没有麻子脚不大周正 l演绎 漆黑的头发，没有麻子，脚不大，周正。l结论：描述一个古代美人！ l演绎 漆黑的头发没有，麻子，脚不大周正。l结论：描述了一个古代丑女人，还是个瘸子。l结论 两个不同的演绎表现为不同的结果，一个是古代美人，一个确实古代丑女人，原因只

3、是文字的不同组合造成！l也就是说：相同的文字（数据）经过不同的组合（结构）会得到也就是说：相同的文字（数据）经过不同的组合（结构）会得到不同的结果，这就是我们要介绍的数据结构：不同的结果，这就是我们要介绍的数据结构：数据及其之间的关数据及其之间的关系（结构）。系（结构）。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级4Computer Software Technology1.1 什么是什么是数据结构数据结构计算机解决问题的步骤？计算机解决问题的步骤？&数值计算数值计算解决问题的

4、一般步骤：解决问题的一般步骤： 数学模型数学模型选择计算机语言选择计算机语言编出程序编出程序测试测试最终解最终解答。答。 数值计算的关键是：如何得出数值计算的关键是：如何得出数学模型数学模型（方程）？（方程）？ 程序设计人员比较关注程序设计的技巧。程序设计人员比较关注程序设计的技巧。&非数值计算非数值计算问题：问题： 数据元素之间的相互关系一般数据元素之间的相互关系一般无法用数学方程无法用数学方程加以描述加以描述诸如表、树、图之类的数据结构单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级

5、第五级5Computer Software Technology例例1：问题：图书管理，完成书目的检索（线性关系）问题：图书管理，完成书目的检索（线性关系）数据：数据：各类书籍，更确切地说是每本书的信息，即书名、各类书籍，更确切地说是每本书的信息，即书名、作者、出版社、出版日期、书号、价格、内容提要等。作者、出版社、出版日期、书号、价格、内容提要等。操作：操作：书目入库、查询、借书、还书书目入库、查询、借书、还书非数值计算问题非数值计算问题3个引例个引例书目自动检索系统的数学模型书目自动检索系统的数学模型001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代

6、数栾汝书S02书目文件按书名按作者名按分类号高等数学001，003理论力学002，.线性代数004，.L002,S001,003,索引表线性表例例2：人机对奕问题的数学模型（树结构）：人机对奕问题的数学模型（树结构）树树.问题：问题：人机对弈，即人与计算机下棋人机对弈，即人与计算机下棋数据：数据：各种棋局状态，确切地说是描述棋盘格局各种棋局状态，确切地说是描述棋盘格局的信息。的信息。操作：操作：走棋，即选择一种策略使棋局状态发生变走棋，即选择一种策略使棋局状态发生变化（由一个格局派生出另一个格局）化（由一个格局派生出另一个格局）单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版

7、文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级7Computer Software TechnologyCEDABABACADBABCBDDADBDCEAEBECED图例例3：多叉路口的交通灯管理问题的数学模型：多叉路口的交通灯管理问题的数学模型问题：问题：多叉路口的交通灯管理，即在多叉路程口多叉路口的交通灯管理，即在多叉路程口设置几种颜色的交通灯，以保证交通畅通。设置几种颜色的交通灯，以保证交通畅通。数据：数据：路口各条路的信息。路口各条路的信息。操作：操作：设置信号灯（求出各个可同时通行的路的设置信号灯（求出各个可同时通行的路的集合。集合。单击此处

8、编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级8Computer Software Technology&求求解非数值计算的问题：解非数值计算的问题： 主要考虑的是设计出合适的数据结构及相主要考虑的是设计出合适的数据结构及相应的算法。应的算法。 即：首先要考虑即：首先要考虑对相关的各种信息如何表对相关的各种信息如何表示、组织和存储？示、组织和存储？ 数据结构数据结构是一门研究非数值计算的程序设是一门研究非数值计算的程序设计问题中计算机的操作计问题中计算机的操作对象对象以及它们之间以及它们

9、之间的的关系关系和和操作操作的学科。的学科。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级9Computer Software Technology 程序设计：程序设计：为计算机处理问题编制一组为计算机处理问题编制一组指令集。指令集。 算法：算法：处理问题的策略。处理问题的策略。 数据结构：数据结构：问题的数学模型。问题的数学模型。Niklaus Wirth1.1 什么是什么是数据结构数据结构Algorithm+DataStructures=Programs算法算法+ +数据结构数据结构

10、= =程序程序单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级10Computer Software Technology基本概念和术语基本概念和术语1.2.1基本概念基本概念数据（数据（data）：）： 数据是信息的载体，是描述客观事物的数、字符、以数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并及所有能输入到计算机中并被计算机程序识别和处理被计算机程序识别和处理的符号的集合的符号的集合, , 是计算机程序加工的是计算机程序加工的”原料原料”。 分类：分类： 数值性

11、数据数值性数据 非数值性数据非数值性数据单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级11Computer Software Technology2、数据元素（、数据元素（data element）数据的数据的基本单位。基本单位。在计算机程序在计算机程序中常作为一个整体进行考虑和处中常作为一个整体进行考虑和处理。有时理。有时一个数据元素可以由若一个数据元素可以由若干数据项干数据项(Data Item)(Data Item)组成。组成。数据项数据项是数据不可分割的最小标是数据不可分割的最小

12、标识单位。识单位。数据元素数据元素又称为又称为元素元素、结点结点、顶顶点点、记录。记录。学号学号姓名姓名成绩成绩001LiLy89002Yang98003Zhao78单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级12Computer Software Technology数据、数据元素、数据项的区别：数据、数据元素、数据项的区别：数据数据数据元素数据元素数据项数据项实数集实数集单个实数单个实数单个实数（不可再分）单个实数（不可再分）复数集复数集单个复数单个复数实部，虚部实部，虚部职工信息

13、职工信息 单个职工记录单个职工记录 多个数据项（姓名、年多个数据项（姓名、年龄、龄、）单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级13Computer Software Technology3、数据对象（、数据对象（data object）l数据对象是具有相同性质的数据元素的集合。数据对象是具有相同性质的数据元素的集合。u整数数据对象整数数据对象 N = 0, 1, 2, u字母字符数据对象字母字符数据对象 C=A，B，Zu学生成绩数据对象学生成绩数据对象Cj=（101，jane，80

14、），）， （ 102，jack，90 ），）， （ 103，jerry，75 ）单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级14Computer Software Technology4、数据结构、数据结构(data structure) 数据结构数据结构是相互之间存在一种或多种特定关系是相互之间存在一种或多种特定关系的数据元素的集合。的数据元素的集合。 在任何问题中，数据元素都不是孤立存在的，在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元而是在它们之

15、间存在着某种关系，这种数据元素相互之间的素相互之间的关系关系称为称为结构结构(Structure)。 数据结构数据结构是一堆数据元素和这些数据元素之间是一堆数据元素和这些数据元素之间的关系的总和。的关系的总和。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级15Computer Software Technology 按数据元素之间关系的不同特性，通常有按数据元素之间关系的不同特性，通常有4类类基本结构基本结构（1）集合）集合 结构中的数据元素除了结构中的数据元素除了“同属于一个集同属于一

16、个集合合”外，别无其它关系。外，别无其它关系。（2）线性结构）线性结构 结构中的数据元素之间存在一对一结构中的数据元素之间存在一对一的关系。的关系。（3）树型结构）树型结构 结构中的数据元素之间存在一对多结构中的数据元素之间存在一对多的关系。的关系。（4）图状结构或网状结构）图状结构或网状结构 结构中的数据元素之间结构中的数据元素之间存在多对多的关系。存在多对多的关系。14131211234567891031587101199874566231311152436单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级

17、第四级 第五级第五级16Computer Software Technology数据结构的形式定义数据结构的形式定义用一个二元组表示，记为：用一个二元组表示，记为： Data_Structure = （D, S） 其中，其中，D 是数据元素的有限集（即一个数据是数据元素的有限集（即一个数据 对象），对象），S 是该对象中所有数据成员之间的关是该对象中所有数据成员之间的关系的有限集合。系的有限集合。在计算机科学中，对复数的定义：复数是一种数据结构在计算机科学中，对复数的定义：复数是一种数据结构Complex=(C,R)其中：其中：C是包含两个实数的集合是包含两个实数的集合 C1, C2 ,R=P

18、,P是定义在是定义在C上的一种关系上的一种关系 。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级17Computer Software Technology5、数据的逻辑结构、数据的逻辑结构 数据的逻辑结构数据的逻辑结构从从逻辑关系逻辑关系上描述数据，可以上描述数据，可以看作是从具体问题抽象出来的看作是从具体问题抽象出来的数据模型数据模型，与数，与数据的存储无关，也与数据元素本身的形式、内据的存储无关，也与数据元素本身的形式、内容、相对位置无关；容、相对位置无关； 数据的逻辑结构分类数据

19、的逻辑结构分类：线性结构线性结构 线性表、栈、队列线性表、栈、队列 、串、串非线性结构非线性结构 树树 、图（或网络）、图（或网络）单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级18Computer Software Technology6、数据的存储结构、数据的存储结构 数据结构在数据结构在计算机中的表示计算机中的表示( (或称映象）或称映象）称为称为数据的存储结构，又称为物理结构。数据的存储结构，又称为物理结构。它包括它包括数数据元素的表示据元素的表示和和关系的表示关系的表示。（1）

20、数据元素的表示：位、字长、元素、结点、数）数据元素的表示：位、字长、元素、结点、数据域据域（2）关系的表示）关系的表示两种基本的存储方法：两种基本的存储方法：顺序映像（顺序存储结构）顺序映像（顺序存储结构）非顺序映像（链式存储结构）非顺序映像（链式存储结构） 算法设计算法设计逻辑结构逻辑结构算法实现算法实现存储结构存储结构单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级19Computer Software Technology19 借助数据元素在存储器中的相对位置来表示借助数据元素在存储

21、器中的相对位置来表示数据元素之间的逻辑关系。数据元素之间的逻辑关系。 所有元素存放在一片所有元素存放在一片连续的存贮单元连续的存贮单元中，中，逻逻辑上相邻的元素存放到计算机内仍然相邻。辑上相邻的元素存放到计算机内仍然相邻。 把必要的数据元素存储在存储单元中后，通过把必要的数据元素存储在存储单元中后，通过对存储单元的对存储单元的地址进行一个固定的计算地址进行一个固定的计算就能直接就能直接表达数据元素之间逻辑上的关系的物理结构。表达数据元素之间逻辑上的关系的物理结构。 顺序存储结构（顺序存储结构（sequential storage structure）单击此处编辑母版标题样式单击此处编辑母版标题

22、样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级20Computer Software Technology20元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Lo(元素i)=Lo+（i-1)*m 例如例如: : 顺序存储顺序存储设一个元素占设一个元素占m个字节，则个字节，则n 个元个元素顺序存储在内素顺序存储在内存中的映象如右存中的映象如右图。图。如果知道了第如果知道了第1个个元素的首地址，元素的首地址，则可直接则可直接计算计算出出第第i个元素的地址个元素的地址。单击此处编辑母版标题

23、样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级21Computer Software Technology21链式存储结构（链式存储结构（linked storage structure） 把数据元素存储在把数据元素存储在附设了指针域的存储单元附设了指针域的存储单元中，通过中，通过指针域的值指针域的值来表达数据元素之间逻辑上来表达数据元素之间逻辑上的关系的物理结构。的关系的物理结构。 所有元素存放在可以所有元素存放在可以不连续的存贮单元不连续的存贮单元中，中，但元素之间的关系可以通过但元素之间的关系可以通过

24、地址（指针）地址（指针）确定，确定，逻辑上相邻的元素存放到计算机内存后不一定是逻辑上相邻的元素存放到计算机内存后不一定是相邻的。相邻的。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级22Computer Software Technology221536元素21400元素11346元素3 元素41345存储地址存储地址 存储内容存储内容 指针指针 1345 1345 元素元素1 1 1400 1400 1346 1346 元素元素4 4 . . . . . 1400 1400 元素元素2

25、 2 1536 1536 . . . . . 1536 1536 元素元素3 3 1346 1346 例如例如: : 链式存储链式存储 h单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级23Computer Software Technology23 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构数据结构单击此处编辑母版标题样式单击此处编辑母

26、版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级24Computer Software Technology 算法与数据结构的关系非常密切，在算法与数据结构的关系非常密切，在算法设计算法设计时先要时先要确定相应的数据结构确定相应的数据结构，而，而在讨论在讨论某一种数据结构某一种数据结构时时也必然会涉及相也必然会涉及相应的算法。应的算法。 算法的特性与设计要求算法的特性与设计要求 算法效率的度量算法效率的度量 1.3 算法和算法分析算法和算法分析单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编

27、辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级25Computer Software Technology1.3 算法和算法分析算法和算法分析 算法的定义：是对算法的定义：是对特定问题求解步骤特定问题求解步骤的一种描的一种描述述, ,是一个是一个有穷的指令集有穷的指令集，这些指令表示一个，这些指令表示一个或多个操作。或多个操作。 算法的特性算法的特性( (要素要素) )：有穷性有穷性 算法应在执行有穷步后结束算法应在执行有穷步后结束, ,且每一步都在有穷时间且每一步都在有穷时间内完成内完成确定性确定性 每步定义都是确切、无歧义的每步定义都是确切、无歧义的可行性可行性 算

28、法中描述的操作应能通过执行有限次已经实现的算法中描述的操作应能通过执行有限次已经实现的基本运算而实现基本运算而实现输入输入 有有0 0个或多个输入个或多个输入输出输出 有一个或多个输出有一个或多个输出( (处理结果处理结果) )。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级26Computer Software Technology算法设计的要求算法设计的要求 正确性：正确性：不含有语法错误；对于各种合法的输不含有语法错误；对于各种合法的输入数据能够得到满足规格说明要求的结果。入数据能

29、够得到满足规格说明要求的结果。 可读性：可读性：要求程序有较好的人机交互性要求程序有较好的人机交互性,有助有助于人们对算法的理解。于人们对算法的理解。 健壮性：健壮性：对输入的非法数据能作出适当的响应对输入的非法数据能作出适当的响应或处理。或处理。 效率与低存储需求：效率与低存储需求：主要指算法的执行时间和主要指算法的执行时间和所需的最大存储空间，这两方面主要和问题的所需的最大存储空间，这两方面主要和问题的规模有关。规模有关。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级27Comput

30、er Software Technology27 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面：单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级28Computer Software Technology本章小结本章小结 与数据结构相关的几个名词概念与数据结构相关的几个名词概念 数据结构研究的内容：数据结构研究的内容： 数据的逻辑结构数据的逻辑结构 数据的物理结构（存储结构）数据的物理结构（存储结构） 在数据结构上的操作在数据结构上的操作 了解算法分析