第4章数据结构.ppt

《第4章数据结构.ppt》由会员分享，可在线阅读，更多相关《第4章数据结构.ppt（183页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第4章数据结构 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望1.1基本数据结构与算法基本数据结构与算法-1.1.11.1.1数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念（P27P27）一一.数据结构的定义数据结构的定义1.数据：数据：信息载体，能够被计算机识别、存储和信息载体，能够被计算机识别、存储和加工处理。可以是加工处理。可以是数值数据数值数据(整数、实数整数、实数)，也，也可以是可以是非数值数据非数值数据(声音、图像等声音、图像

2、等)。2.数据项数据项:是数据的具有独立含义的不可分割的是数据的具有独立含义的不可分割的最小最小标识单位标识单位,如成绩表中学号如成绩表中学号,姓名。姓名。3.数据元素（数据元素（又称结点、记录又称结点、记录)一个数据元素由一个数据元素由若干数据项若干数据项组成组成,是数据是数据的的基本单位基本单位，通常作为一个整体进行考虑和处，通常作为一个整体进行考虑和处理。理。学号学号姓名姓名系系别别住址住址电话电话981111李洪李洪机械机械六舍六舍5371111982111王王刚刚电电子子四舍四舍5372111983211王将王将计计算机算机五舍五舍5373211983212张张强强机械机械六舎六舎5

3、3722214个数据元素个数据元素5个数个数据项据项1个数个数据项据项1个数个数据元素据元素1.数据对象数据对象:具有具有相同性质相同性质的的数据元素的数据元素的集合集合。是数据的一个子集。是数据的一个子集。例例:成绩表成绩表学号学号姓名姓名系系别别住址住址电话电话981111李洪李洪机械机械六舍六舍5371111982111王王刚刚电电子子四舍四舍5372111983211王将王将计计算机算机五舍五舍5373211983212张张强强机械机械六舎六舎53722211.1基本数据结构与算法基本数据结构与算法一一.数据结构的定义数据结构的定义1.数据：数据：2.数据项数据项:3.数据元素：数据元

4、素：1.1.11.1.1数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 （P27P27）数据对象数据对象-由由4 4个记录组成个记录组成,表中每行是一个记录表中每行是一个记录,每个每个记录由记录由5 5个数据项组成个数据项组成.学号学号姓名姓名系系别别住址住址电话电话981111李洪李洪机械机械六舍六舍5371111982111王王刚刚电电子子四舍四舍5372111983211王将王将计计算机算机五舍五舍5373211983212张张强强机械机械六舎六舎53722211.1基本数据结构与算法基本数据结构与算法一一.数据结构的定义数据结构的定义1.1.11.1.1数据结

5、构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 （P27P27）关键码：关键码：值唯一能区别不同的值唯一能区别不同的数据元素的数据项数据元素的数据项1.1基本数据结构与算法一一.数据结构的定义数据结构的定义1.数据：数据：2.数据项数据项:3.数据元素：数据元素：1.数据对象数据对象:1.1.11.1.1数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 （P27P27）5.数据结构数据结构:相互之间存在着一种或多种相互之间存在着一种或多种关系关系的的数据元素数据元素的集合。的集合。1)1)研究研究 内容内容数据的逻辑结构数据的逻辑结构：各数据元素之间

6、的逻辑关系各数据元素之间的逻辑关系数据的存储结构数据的存储结构：各数据元素在各数据元素在计算机计算机中的存储关系中的存储关系对各种数据结构进行的运算对各种数据结构进行的运算：添加，删除，排序等。添加，删除，排序等。1.1基本数据结构与算法基本数据结构与算法一一.数据结构的定义数据结构的定义1.数据：数据：2.数据项数据项:3.数据元素：数据元素：1.数据对象数据对象:1.1.11.1.1数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 （P27P27）5.数据结构数据结构:相互之间存在着一种或多种相互之间存在着一种或多种关系关系的的数据元素数据元素的集合。的集合。2)2

7、)研究研究 目的目的一是提高数据处理的一是提高数据处理的速度速度.二是尽量二是尽量节省节省在数据处理过程中所在数据处理过程中所占用的计算机存储占用的计算机存储空间空间.1.1基本数据结构与算法基本数据结构与算法一一.数据结构的定义数据结构的定义1.数据：数据：2.数据项数据项:3.数据元素：数据元素：1.数据对象数据对象:1.1.11.1.1数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 （P27P27）5.数据结构数据结构:相互之间存在着一种或多种相互之间存在着一种或多种关系关系的的数据元素数据元素的集合。的集合。3)3)常见的数常见的数据结构类型据结构类型集合集合

8、元素间为松散的关系元素间为松散的关系(属于关系属于关系)线性结构线性结构元素间为一对一关系元素间为一对一关系树形结构树形结构元素间为一对多关系元素间为一对多关系图状结构图状结构元素间为多对多关系元素间为多对多关系学号姓名语文数学C语言1001张三8554921002李四9284641003王五877473.通迅录、成绩单、花名册通迅录、成绩单、花名册通迅录、成绩单、花名册通迅录、成绩单、花名册线性结构线性结构线性结构线性结构电子字典、家谱、目录电子字典、家谱、目录电子字典、家谱、目录电子字典、家谱、目录树型结构树型结构树型结构树型结构HBCDEFGAHGFECDBA计算机中的目录结构问题计算机

9、中的目录结构问题树图状结构图状结构图状结构图状结构树型结构特点树型结构特点结点间具有分层次的连接关系结点间具有分层次的连接关系通迅录、成绩单、花名册通迅录、成绩单、花名册通迅录、成绩单、花名册通迅录、成绩单、花名册线性结构线性结构电子字典、家谱、目录、电子字典、家谱、目录、电子字典、家谱、目录、电子字典、家谱、目录、计算机中的目录结构问题计算机中的目录结构问题树型结构树型结构交通线路、通信网络交通线路、通信网络交通线路、通信网络交通线路、通信网络图形结构图形结构图形结构图形结构图形结构特点图形结构特点结点间的连结是任意的，结点间的连结是任意的，数据元素之间存在多个对多个关系。数据元素之间存在多

10、个对多个关系。AEBCD1.1基本数据结构与算法一一.数据结构的定义数据结构的定义1.数据：数据：2.数据项数据项:3.数据元素：数据元素：1.数据对象数据对象:1.1.11.1.1数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 （P27P27）5.数据结构数据结构:相互之间存在着一种或多种相互之间存在着一种或多种关系关系的的数据元素数据元素的集合。的集合。4)4)包含包含 信息信息表示数据表示数据元素的信息元素的信息表示各数据元素之间的表示各数据元素之间的前后件关系前后件关系几种基本数据结构的节点图几种基本数据结构的节点图：叶子结点叶子结点根结点根结点根节点根节点:

11、在数据结构中在数据结构中,没有前件的节点没有前件的节点称为根结点称为根结点.叶子节点叶子节点:没有后件的结点没有后件的结点称为终端结点或叶子结点称为终端结点或叶子结点叶子结点叶子结点有关概念有关概念(补充补充):结点结点:组成数据结构的数据元素称为一个结点。组成数据结构的数据元素称为一个结点。前后件关系前后件关系:数据元素之间的固有关系可以用前后件关系数据元素之间的固有关系可以用前后件关系(前驱与后继前驱与后继关系关系)描述。举例：家庭成员辈分关系描述。举例：家庭成员辈分关系(父亲、儿子、女儿父亲、儿子、女儿)，“父亲父亲”是是“儿子儿子”和和“女儿女儿”的前件，的前件，“儿子儿子”和和“女儿

12、女儿”是是“父亲父亲”后件。后件。根结点根结点1.1基本数据结构与算法基本数据结构与算法一一.数据结构的定义数据结构的定义1.数据：数据：2.数据项数据项:3.数据元素：数据元素：1.数据对象数据对象:5.数据数据结构结构1.1.11.1.1数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 （P27P27）二二.数据结构的逻辑结构（数据结构的逻辑结构（P27-P28）数据的逻辑结构：数据的逻辑结构：数据之间的相互关系，被称为数据的逻辑结构数据之间的相互关系，被称为数据的逻辑结构逻辑结构分类：逻辑结构分类：根据数据结构中各数据元素之间的前后件关系根据数据结构中各数据元素之

13、间的前后件关系的复杂程度的复杂程度,一般将数据逻辑结构分为一般将数据逻辑结构分为:线性结构与非线性结构线性结构与非线性结构1.1基本数据结构与算法基本数据结构与算法一一.数据结构的定义数据结构的定义1.数据：数据：2.数据项数据项:3.数据元素：数据元素：1.数据对象数据对象:5.数据数据结构结构1.1.11.1.1数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 （P27P27）二二.数据结构的逻辑结构（数据结构的逻辑结构（P27-P28）线性结构：线性结构：数据元素之间存在数据元素之间存在一个对一个一个对一个的前后次序关系的前后次序关系 特点特点:有且只有一个根结点

14、有且只有一个根结点 每个结点最多有一个前件，也最多有一个后件每个结点最多有一个前件，也最多有一个后件非线性结构：非线性结构：一个数据结构如果不是线性结构，则称之为一个数据结构如果不是线性结构，则称之为 非线性结构。非线性结构。特点特点：数据元素的前后关系复杂，数据元素的前后关系复杂，一个结点既可以有一个结点既可以有多个前件，也可以有多个后件多个前件，也可以有多个后件，如，如集合集合、树型、图形结构树型、图形结构属于非线性结构。属于非线性结构。集合结构集合结构:数据元素间的关系是属于同一个集合数据元素间的关系是属于同一个集合 树型结构：树型结构：数据元素之间存在一个对多个的关系数据元素之间存在一

15、个对多个的关系图形结构：图形结构：数据元素之间存在多个对多个的关系数据元素之间存在多个对多个的关系 1.1基本数据结构与算法一.数据结构的定义1.数据：2.数据项:3.数据元素：1.数据对象:5.数据结构1.1.11.1.1数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 （P27P27）二二.数据结构的逻辑结构（数据结构的逻辑结构（P27-P28）三三.数据结构的存储结构（数据结构的存储结构（P27-P28）1.1.定义：定义：数据的逻辑结构在数据的逻辑结构在计算机存储空间计算机存储空间中的存放形式中的存放形式。数据存储结构中不仅存。数据存储结构中不仅存放各数据元素信

16、息，还存放前后件关系放各数据元素信息，还存放前后件关系的信息。的信息。1.1基本数据结构与算法基本数据结构与算法一一.数据结构的定义数据结构的定义二二.数据结构的逻辑结构（数据结构的逻辑结构（P27-P28）1.1.11.1.1数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 （P27P27）三三.数据结构的存储结构（数据结构的存储结构（P27-P28）1.定义：定义：2.特点：特点：存储结构研究的是存储结构研究的是逻辑结构用计算机语言逻辑结构用计算机语言实现，实现，依赖于依赖于计算机语言。计算机语言。一种一种一种一种数据结构可以根据需要采用数据结构可以根据需要采用数据

17、结构可以根据需要采用数据结构可以根据需要采用多种不同的存储多种不同的存储多种不同的存储多种不同的存储结构结构结构结构，常用的存储结构有顺序、链接与索引等存储，常用的存储结构有顺序、链接与索引等存储，常用的存储结构有顺序、链接与索引等存储，常用的存储结构有顺序、链接与索引等存储方式。方式。方式。方式。数据的数据的数据的数据的存储结构不同存储结构不同存储结构不同存储结构不同，解决问题的，解决问题的，解决问题的，解决问题的方法就有所方法就有所方法就有所方法就有所不同不同不同不同，数据处理的，数据处理的，数据处理的，数据处理的效率也是不同效率也是不同效率也是不同效率也是不同的。的。的。的。1.1基本数

18、据结构与算法1.1.11.1.1数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 （P27P27）根据数据结构中各数据元素之间的前后件根据数据结构中各数据元素之间的前后件关系的复杂程度关系的复杂程度,一般将数据结构分为一般将数据结构分为:线性结构与非线性结构线性结构与非线性结构线性结构：线性结构：数据元素之间存在数据元素之间存在一个对一个一个对一个的前后次序关系的前后次序关系 特点特点:有且只有一个根结点有且只有一个根结点 每个结点最多有一个前件，也最多有一个后件每个结点最多有一个前件，也最多有一个后件非线性结构：非线性结构：一个数据结构如果不是线性结构，则称之为一个数

19、据结构如果不是线性结构，则称之为非线性结构。非线性结构。特点特点：数据元素的前后关系复杂，数据元素的前后关系复杂，一个结点既可以有一个结点既可以有多个前件，也可以有多个后件多个前件，也可以有多个后件，如树型、图形结构属于非，如树型、图形结构属于非线性结构线性结构三三.数据结构的存储结构（数据结构的存储结构（P27-P28）1.1.定义：定义：2.特点特点3.3.实现方式：实现方式：(1)顺序存储方顺序存储方式式：逻辑上逻辑上相邻的元素存储在相邻的元素存储在物理位置相邻物理位置相邻的存的存储单元中储单元中。主要用于线性结构。主要用于线性结构。通常借助于数组来实现。通常借助于数组来实现。顺序存储结

20、构的线性表顺序存储结构的线性表线性表线性表(a1,a2,a3,a4)存储单元的存储单元的地址即物理地址即物理地址地址逻辑上相邻的元素存储在物理位置逻辑上相邻的元素存储在物理位置相邻的存储单元中相邻的存储单元中。1.1基本数据结构与算法1.1.11.1.1数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 （P27P27）根据数据结构中各数据元素之间的前后件根据数据结构中各数据元素之间的前后件关系的复杂程度关系的复杂程度,一般将数据结构分为一般将数据结构分为:线性结构与非线性结构线性结构与非线性结构线性结构：线性结构：数据元素之间存在数据元素之间存在一个对一个一个对一个的前

21、后次序关系的前后次序关系 特点特点:有且只有一个根结点有且只有一个根结点 每个结点最多有一个前件，也最多有一个后件每个结点最多有一个前件，也最多有一个后件非线性结构：非线性结构：一个数据结构如果不是线性结构，则称之为一个数据结构如果不是线性结构，则称之为非线性结构。非线性结构。特点特点：数据元素的前后关系复杂，数据元素的前后关系复杂，一个结点既可以有一个结点既可以有多个前件，也可以有多个后件多个前件，也可以有多个后件，如树型、图形结构属于非，如树型、图形结构属于非线性结构线性结构三.数据结构的存储结构（P27-P28）1.1.定义：定义：2.特点特点3.3.实现方式：实现方式：(1)顺序存储方

22、顺序存储方式式：逻辑上逻辑上相邻的元素存储在相邻的元素存储在物理物理位置相邻位置相邻的存储单元中的存储单元中。主要用于线性结构。主要用于线性结构。通通常借助于数组来实现。常借助于数组来实现。(2)链式链式存储方存储方式式：对逻辑上相邻的元素对逻辑上相邻的元素不要求其不要求其物理地址相邻，物理地址相邻，元素间逻辑关系通过附加的指针元素间逻辑关系通过附加的指针字段来表示。通常借助于字段来表示。通常借助于指针类型指针类型实现。实现。链式链式存储结构的线性表存储结构的线性表指针域：用于存指针域：用于存放结点所在的存放结点所在的存储单元的地址储单元的地址a1,a2在逻辑在逻辑上相邻上相邻,而在而在机内存

23、储时机内存储时,存储单元的存储单元的地址地址(100,105)并并不相邻不相邻.链式链式存储方存储方式特点式特点：每个每个结点结点由两部分组成：一部分存放数据，另一部由两部分组成：一部分存放数据，另一部分分存储存储指向前件或后件结点的指针域。指向前件或后件结点的指针域。逻辑上相邻的结点物理上不必相连。逻辑上相邻的结点物理上不必相连。数据运算数据运算(插入和删除等插入和删除等)灵活。灵活。存储单元存储单元的地址即的地址即物理地址物理地址链式存储结构的线性表链式存储结构的线性表线性表线性表(a1,a2,a3,a4)链式链式存储结构的线性表存储结构的线性表逻辑结构为线性结构的线性表（逻辑结构为线性结

24、构的线性表（a1,a2,a3,a4)存储方式比较：存储方式比较：顺序顺序存储结构存储结构顺序存储结构：顺序存储结构：逻辑上相邻的结点物理上必相连。逻辑上相邻的结点物理上必相连。链式存储结构的线性表：链式存储结构的线性表：逻辑上相邻的结点物理上逻辑上相邻的结点物理上不不必相连。必相连。1.1基本数据结构与算法1.1.11.1.1数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 （P27P27）根据数据结构中各数据元素之间的前后件根据数据结构中各数据元素之间的前后件关系的复杂程度关系的复杂程度,一般将数据结构分为一般将数据结构分为:线性结构与非线性结构线性结构与非线性结构线

25、性结构：线性结构：数据元素之间存在数据元素之间存在一个对一个一个对一个的前后次序关系的前后次序关系 特点特点:有且只有一个根结点有且只有一个根结点 每个结点最多有一个前件，也最多有一个后件每个结点最多有一个前件，也最多有一个后件非线性结构：非线性结构：一个数据结构如果不是线性结构，则称之为一个数据结构如果不是线性结构，则称之为非线性结构。非线性结构。特点特点：数据元素的前后关系复杂，数据元素的前后关系复杂，一个结点既可以有一个结点既可以有多个前件，也可以有多个后件多个前件，也可以有多个后件，如树型、图形结构属于非，如树型、图形结构属于非线性结构线性结构三三.数据结构的存储结构（数据结构的存储结

26、构（P27-P28）1.1.定义：定义：2.特点特点3.3.实现方式：实现方式：(1)顺序存储方顺序存储方式式：(2)链式链式存储方存储方式式：(3)索引索引存储存储方法和散列存储方法：方法和散列存储方法：1.1基本数据结构与算法一一.数据结构的定义数据结构的定义1.数据：2.数据项:3.数据元素：1.数据对象:5.数据结构1.1.11.1.1数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 （P27P27）二二.数据结构的逻辑结构：数据结构的逻辑结构：线性和非线性线性和非线性根据数据结构中各数据元素之间的前后件根据数据结构中各数据元素之间的前后件关系的复杂程度关系的复

27、杂程度,一般将数据结构分为一般将数据结构分为:线性结构与非线性结构线性结构与非线性结构线性结构：线性结构：数据元素之间存在数据元素之间存在一个对一个一个对一个的前后次序关系的前后次序关系 特点特点:有且只有一个根结点有且只有一个根结点 每个结点最多有一个前件，也最多有一个后件每个结点最多有一个前件，也最多有一个后件非线性结构：非线性结构：一个数据结构如果不是线性结构，则称之为一个数据结构如果不是线性结构，则称之为非线性结构。非线性结构。特点特点：数据元素的前后关系复杂，数据元素的前后关系复杂，一个结点既可以有一个结点既可以有多个前件，也可以有多个后件多个前件，也可以有多个后件，如树型、图形结构

28、属于非，如树型、图形结构属于非线性结构线性结构三三.数据结构的存储结构：数据结构的存储结构：顺序、链式等顺序、链式等四四.数据的运算数据的运算定义：定义：在数据的逻辑结构上定义的操作算法在数据的逻辑结构上定义的操作算法常见运算：常见运算：插入、删除、查找、排序和更新等插入、删除、查找、排序和更新等分类：分类：加工型运算：加工型运算：运算运算改变了数据结构改变了数据结构的值的值引用型运算：引用型运算：不改变值，只查询或求得结构值。不改变值，只查询或求得结构值。注意：注意：数据的运算定义在逻辑结构上，而具体的数据的运算定义在逻辑结构上，而具体的实现都要在数据的存储结构上即计算机内进行。实现都要在数

29、据的存储结构上即计算机内进行。1.1基本数据结构与算法一一.数据结构的定义数据结构的定义1.数据：2.数据项:3.数据元素：1.数据对象:5.数据结构1.1.11.1.1数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 （P27P27）二二.数据结构的逻辑结构数据结构的逻辑结构：线性和非线性线性和非线性根据数据结构中各数据元素之间的前后件根据数据结构中各数据元素之间的前后件关系的复杂程度关系的复杂程度,一般将数据结构分为一般将数据结构分为:线性结构与非线性结构线性结构与非线性结构线性结构：线性结构：数据元素之间存在数据元素之间存在一个对一个一个对一个的前后次序关系的前后

30、次序关系 特点特点:有且只有一个根结点有且只有一个根结点 每个结点最多有一个前件，也最多有一个后件每个结点最多有一个前件，也最多有一个后件非线性结构：非线性结构：一个数据结构如果不是线性结构，则称之为一个数据结构如果不是线性结构，则称之为非线性结构。非线性结构。特点特点：数据元素的前后关系复杂，数据元素的前后关系复杂，一个结点既可以有一个结点既可以有多个前件，也可以有多个后件多个前件，也可以有多个后件，如树型、图形结构属于非，如树型、图形结构属于非线性结构线性结构三三.数据结构的存储结构：数据结构的存储结构：顺序、链式等顺序、链式等四四.数据的运算数据的运算:插入、删除、查找、排序等插入、删除

31、、查找、排序等五五.数据类型及其分类数据类型及其分类1.定义：定义：数据类型是一个值的数据类型是一个值的集合集合和定义在这个和定义在这个2.值集上的值集上的一组操作一组操作的总称。的总称。例：例：VB语言中的整型变量，其值为某个区间上整语言中的整型变量，其值为某个区间上整数，定义在其上的操作为：加，减、乘、除和数，定义在其上的操作为：加，减、乘、除和求余数等算术运算。求余数等算术运算。2.分类：分类：（1）非结构的原子类型）非结构的原子类型（2）结构类型）结构类型（2 2）结构类型：）结构类型：结构类型的值是由结构类型的值是由若干成分按某种结构若干成分按某种结构组成组成的，因此是可分解的，并且

32、它的成分可以是非结构的，也可的，因此是可分解的，并且它的成分可以是非结构的，也可以是结构的。以是结构的。（1 1）非结构的原子类型：）非结构的原子类型：原子类型的值是不可分解的。如：程原子类型的值是不可分解的。如：程序设计语言中的基本类型（整型，实型，字符型，指针类型和序设计语言中的基本类型（整型，实型，字符型，指针类型和空类型）。空类型）。VB结构类型举例：结构类型举例：PublicTypeID类型名称为类型名称为ID,包含两个数据项包含两个数据项NameAsString*6存姓名存姓名numasstring*8存学号存学号sexasstring*1存性别存性别EndTypeDimperso

33、n1asID定义自定义类型的变量定义自定义类型的变量总结总结数据类型数据类型-分类分类数据数据-数据元素数据元素具有特定关系的数据元素集合具有特定关系的数据元素集合-数据结构数据结构数据结构的逻辑表示与物理存储数据结构的逻辑表示与物理存储-逻辑结构与存储结构逻辑结构与存储结构人们不仅关心数据的逻辑结构、存储结构，还关心数据人们不仅关心数据的逻辑结构、存储结构，还关心数据的处理方法（算法）与处理结果的处理方法（算法）与处理结果-数据类型数据类型一一.算法的基本概念算法的基本概念1.定义：定义：为解决某个特定问题而采取的确定且为解决某个特定问题而采取的确定且有限的步骤有限的步骤。1.1基本数据结构

34、与算法1.1.2 1.1.2 算法及算法分析算法及算法分析（P30）u首先要从具体问题抽象出一个适当的数学模型；首先要从具体问题抽象出一个适当的数学模型；u然后设计一个解此数学模型的算法；然后设计一个解此数学模型的算法；u最后采用一种计算机语言编出程序，调试、修改最后采用一种计算机语言编出程序，调试、修改 直至得到最终答案。直至得到最终答案。用计算机解决一个具体问题时，大用计算机解决一个具体问题时，大致需要经过下列几个步骤：致需要经过下列几个步骤：一.算法的基本概念1.定义：定义：为解决某个特定问题而采取的确定且为解决某个特定问题而采取的确定且有限的步骤有限的步骤。1.1基本数据结构与算法1.

35、1.2 1.1.2 算法及算法分析算法及算法分析（P30）2.算法特性：算法特性：有穷性：有穷性：一个算法应包含有限个操作步骤，而且每一步一个算法应包含有限个操作步骤，而且每一步都应在有限时间内完成。都应在有限时间内完成。确定性确定性：算法中每一条指令必须有确切的含义，确保不会：算法中每一条指令必须有确切的含义，确保不会产生二义性。产生二义性。可行性：可行性：算法中指定的操作都是可以通过基本运算执行有算法中指定的操作都是可以通过基本运算执行有限次后实现。限次后实现。输入：输入：一个算法有零个或多个的输入，一个算法有零个或多个的输入，这些输入取自于某这些输入取自于某个特定的对象集合。个特定的对象

36、集合。输出输出：一个算法有一个或多个的输出，：一个算法有一个或多个的输出，这些输出是同输入这些输出是同输入有着某些特定关系的量。有着某些特定关系的量。一.算法的基本概念二.算法的基本要素及描述1.1基本数据结构与算法基本数据结构与算法1.1.2 1.1.2 算法及算法分析算法及算法分析（P30）1.算法基算法基本要素构本要素构成成对数据对对数据对象的象的运算运算和和操作操作算法的算法的控控制结构制结构算术运算算术运算:加、减、乘、除加、减、乘、除逻辑运算：与、或、非等运算逻辑运算：与、或、非等运算关系运算：大于、小于、等于等关系运算：大于、小于、等于等数据传输：赋值、输入、输出数据传输：赋值、

37、输入、输出顺序顺序选择选择循环（重复）循环（重复）2.算法的描述算法的描述:自然语言，伪代码，流程图自然语言，伪代码，流程图,N-S图图,类类C一一.算法的基本概念算法的基本概念1.1基本数据结构与算法1.1.2 1.1.2 算法及算法分析（P30）二二.算法的基本要素及描述算法的基本要素及描述三.算法设计要求算法设计要求（评价算法标准）（评价算法标准）1.正确性：正确性：执行结果应满足预先的功能和性能要求执行结果应满足预先的功能和性能要求2.可读性：可读性：思路清晰、层次分明、简单明了、易读易懂。思路清晰、层次分明、简单明了、易读易懂。3.健壮性：健壮性：输入数据非法时，算法能作适当处理，不

38、致于引输入数据非法时，算法能作适当处理，不致于引 起严重后果起严重后果4.效率：效率：有效使用存储空间和较高的时间效率有效使用存储空间和较高的时间效率。1.1基本数据结构与算法1.1.2 1.1.2 算法及算法分析算法及算法分析（P30）四、算法设计的基本方法四、算法设计的基本方法1.列举法：列举法：列举出所有可能情况，用给定条件检验哪些是需要的，哪列举出所有可能情况，用给定条件检验哪些是需要的，哪些是不需要的些是不需要的(如用循环解决百元买百鸡问题）。如用循环解决百元买百鸡问题）。2.归纳法：归纳法：列举少量简单而又特殊的情况，分析归纳出一般结论。列举少量简单而又特殊的情况，分析归纳出一般结

39、论。3.递推法：递推法：从已知初始条件出发，逐步推出各种中间结果和最后结果从已知初始条件出发，逐步推出各种中间结果和最后结果（如猴子吃桃）。（如猴子吃桃）。1.递归法：递归法：解决复杂问题时，将问题逐层分解，归纳为一些简单问题，解决复杂问题时，将问题逐层分解，归纳为一些简单问题，解决了最后简单问题后，再沿原来的逆过程逐步综合（如求某解决了最后简单问题后，再沿原来的逆过程逐步综合（如求某数的阶乘）。数的阶乘）。1.1基本数据结构与算法1.1.2 1.1.2 算法及算法分析算法及算法分析（P30）四、算法设计的基本方法四、算法设计的基本方法P315.减半递推技术（分治法）：减半递推技术（分治法）：

40、(补充）补充）减少：把问题规模减半，而性质不变减少：把问题规模减半，而性质不变递推：重复减半的过程。递推：重复减半的过程。6.回溯法回溯法（补充）（补充）在工程上有些实际问题很难归纳出一组简单的递推在工程上有些实际问题很难归纳出一组简单的递推公式或直关的求解步骤，并且也不能进行无限的列举。公式或直关的求解步骤，并且也不能进行无限的列举。对于这类问题，一种有效的方法是对于这类问题，一种有效的方法是“试试”，通过对问题，通过对问题的的分析分析，找出一个解决问题的，找出一个解决问题的线索线索，然后沿着这个线索，然后沿着这个线索逐步试探逐步试探，若，若试探成功试探成功，就得到问题的，就得到问题的解解，

41、若试探失败，若试探失败，就就逐步回退逐步回退，换其他路线再逐步试探。，换其他路线再逐步试探。一一.算法的基本概念算法的基本概念二二.算法的基本要素及描述算法的基本要素及描述三.算法设计要求算法设计要求（评价算法标准）（评价算法标准）四.算法设计的基本方法算法设计的基本方法1.1基本数据结构与算法1.1.2 1.1.2 算法及算法分析（P30）五.算法的分析算法的分析五.算法的分析算法的分析1.1.评价算法标准评价算法标准 算法所占用计算机资源，即算法所占用计算机资源，即时间代价时间代价(算法所需算法所需要的时间）和要的时间）和空间代价空间代价（算法所需要的存储空间）。（算法所需要的存储空间）。

42、算法所需要的时间包括：算法所需要的时间包括：源程序进行编译所需要的时间；源程序进行编译所需要的时间；计算机执行每条指令所需要的时间；计算机执行每条指令所需要的时间；程序中指令程序中指令重复执行的次数重复执行的次数，而本条正是讨论算法，而本条正是讨论算法中的重点内容中的重点内容五.算法的分析算法的分析2.2.相关名词：相关名词：(1)问题规模：问题规模：不同种类问题，问题规模含义不同。不同种类问题，问题规模含义不同。如矩阵运算取决于矩阵阶数，多项式运算取决于如矩阵运算取决于矩阵阶数，多项式运算取决于项数。项数。(2)算法运行时间：算法运行时间：大致等于其所有语句大致等于其所有语句执行时间执行时间

43、 的总和的总和。(3)语句频度：语句频度：该语句在算法中该语句在算法中重复执行的次数重复执行的次数。五.算法的分析算法的分析3.3.算法的时间复杂度：算法的时间复杂度：1)定义：定义：算法运行从开始到结束所需要的算法运行从开始到结束所需要的计算工作量计算工作量.说明说明:同一个算法使用不同的语言实现同一个算法使用不同的语言实现,或者用不同的或者用不同的编译程序进行编译编译程序进行编译,或者在不同的计算机上运行或者在不同的计算机上运行,效效率均不同率均不同,这表明使用绝对的时间单位衡量算法的效这表明使用绝对的时间单位衡量算法的效率是不合适的率是不合适的,撇开这些与计算机硬件、软件有关的撇开这些与

44、计算机硬件、软件有关的因素因素,可以认为一个特定算法可以认为一个特定算法 “运行工作量运行工作量”的大的大小小,只依赖于问题的规模只依赖于问题的规模(通常用整数通常用整数n n表示表示),),它是问它是问题的规模函数题的规模函数,即即 算法的工作量算法的工作量=f(n)=f(n)五.算法的分析算法的分析3.3.算法的时间复杂度：算法的时间复杂度：1)定义：定义：T(n)=O(f(n)T(n)：算法中所有语句频度之和算法中所有语句频度之和n：问题规模。：问题规模。T(n)是是n的某个函数。的某个函数。O：数量级。：数量级。当问题规模趋向无穷时，当问题规模趋向无穷时，T(n)的数量的数量级称为时间

45、复杂度。级称为时间复杂度。2）表示：）表示：x=X+5;单个语句的频度为单个语句的频度为1，则，则 程序段的时间复杂度为程序段的时间复杂度为 一个算法是由一个算法是由控制结构控制结构和和原操作原操作构成构成的，则算法时间取决于两者的的综合效果。的，则算法时间取决于两者的的综合效果。为了便于比较同一个问题的不同算法，通为了便于比较同一个问题的不同算法，通常的做法是，从算法中选取一种对于所研常的做法是，从算法中选取一种对于所研究的问题究的问题(或算法类型）来说是基本操作的或算法类型）来说是基本操作的原操作原操作，以该基本操作，以该基本操作重复执行的次数作重复执行的次数作为算法的时间度量。为算法的时

46、间度量。T(n)=O(1)五.算法的分析算法的分析3.3.算法的时间复杂度：算法的时间复杂度：1)定义：定义：T(n)=O(f(n)T(n)：算法中所有语句频度之和算法中所有语句频度之和n：问题规模。：问题规模。T(n)是是n的某个函数。的某个函数。O：数量级。：数量级。当问题规模趋向无穷时，当问题规模趋向无穷时，T(n)的数量的数量级称为时间复杂度。级称为时间复杂度。2）表示：）表示：For i=0 TO n For j=0 to n a(i,j)=i*j next j next i 一个算法是由一个算法是由控制结构控制结构和和原操作原操作构成构成的，则算法时间取决于两者的的综合效果。的，则

47、算法时间取决于两者的的综合效果。为了便于比较同一个问题的不同算法，通为了便于比较同一个问题的不同算法，通常的做法是，从算法中选取一种对于所研常的做法是，从算法中选取一种对于所研究的问题究的问题(或算法类型）来说是基本操作的或算法类型）来说是基本操作的原操作原操作，以该基本操作，以该基本操作重复执行的次数作重复执行的次数作为算法的时间度量。为算法的时间度量。最优算法：最优算法：随随n的增大，的增大，T(n)增长增长较慢的算法。较慢的算法。则：则：T(n)=O(n2)五.算法的分析算法的分析3.3.算法的时间复杂度：算法的时间复杂度：1)定义：定义：2）表示：）表示：3）平均时间复杂度：）平均时间

48、复杂度：所有可能的输入实例均以等所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。概率出现的情况下，算法的期望运行时间。4）最坏时间复杂度：）最坏时间复杂度：最坏情况下算法的时间复杂最坏情况下算法的时间复杂度。度。五.算法的分析算法的分析3.3.算法的时间复杂度：算法的时间复杂度：1.1.算法的空间复杂度：算法的空间复杂度：1)1)定义：定义：算法运行从开始到结束所需的存储空间算法运行从开始到结束所需的存储空间量量,包括包括 固定部分和可变部分。固定部分和可变部分。固定部分：固定部分：此部分空间与所处理数据的大小和规此部分空间与所处理数据的大小和规模无关。通常用来保存本身所用的程序

49、代码、常模无关。通常用来保存本身所用的程序代码、常量、变量等。量、变量等。可变部分：可变部分：此部分空间与处理的数据的大小和规此部分空间与处理的数据的大小和规模有关，即模有关，即执行算法执行算法时所需额外空间。时所需额外空间。1.1基本数据结构与算法思考题1.研究数据结构的目的是什么？研究数据结构的目的是什么？2.数据结构研究哪三方面的问题数据结构研究哪三方面的问题?关系如何关系如何?3.在数据结构中数据项、数据元素及数据对象的关系？在数据结构中数据项、数据元素及数据对象的关系？4.数据的逻辑结构分为哪两大类？各有何特点？数据的逻辑结构分为哪两大类？各有何特点？5.数据的存储结构中的顺序存储与

50、链式存储各有什么特点？数据的存储结构中的顺序存储与链式存储各有什么特点？6.什么是算法？有何特点？什么是算法？有何特点？7.算法设计的基本要求？算法设计的基本要求？8.算法设计的方法？算法设计的方法？9.如何评价算法？如何评价算法？10.什么是时间复杂度？时间复杂度与哪些因素有关？什么是时间复杂度？时间复杂度与哪些因素有关？11.什么是空间复杂度？包括哪两部分？什么是空间复杂度？包括哪两部分？1.1数据结构与算法补充习题讲解1.数据处理的最小单位是数据处理的最小单位是_。A.数据数据B.数据元素数据元素C.数据项数据项D.数据结构数据结构2.数据结构中，与所使用的计算机无关的是数据的数据结构中