数据结构第1章绪论

1、第一章第一章 绪论绪论1. 了解数据结构研究的主要内容了解数据结构研究的主要内容2. .掌握数据结构中涉及的基本概念掌握数据结构中涉及的基本概念3. 掌握算法、算法的时间复杂度及其分析的掌握算法、算法的时间复杂度及其分析的简易方法简易方法 教学目标教学目标1.1 数据结构的研究内容数据结构的研究内容1.2 基本概念和术语基本概念和术语1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现 1.4 算法与算法分析算法与算法分析教学内容教学内容&N.N.沃思（沃思（Niklaus Wirth)Niklaus Wirth)教授提出：教授提出： 程序程序=算法算法+数据结构数据结构&

2、计算机的主要用途：计算机的主要用途： 早期：早期： 主要用于数值计算。主要用于数值计算。 后来：后来： 处理逐渐扩大到非数值计算领域，能处理处理逐渐扩大到非数值计算领域，能处理多种复杂的具有一定结构关系的数据多种复杂的具有一定结构关系的数据1.1 1.1 数据结构的研究内容数据结构的研究内容例：例： 例例1 线性结构线性结构 学学 号号 姓姓 名名 数数据据结结构构 系系统统结结构构 数数学学 1 20001 刘刘扬扬 89 69 67 2 20002 李李平平 70 83 89 3 20003 王王方方 86 81 78 4 20004 张张策策 69 69 78 5 20005 董董立立

3、79 89 68 6 20006 谢谢平平 80 88 79 7 20007 高高月月 81 81 80 8 20008 刘刘平平 89 85 87 9 20009 好好园园 86 80 84 例例2 树型结构：树型结构： 学校组织形式学校组织形式学校学校计算机学院计算机学院理学院理学院。外语院外语院计算机系计算机系信管系信管系数学系数学系 物理系物理系 化学系化学系英语系英语系 公外公外张三张三李四。李四。李洪。李洪。王五王五吴梅吴梅AFCBDE例例3 图型结构：图型结构： 城市交通道路图城市交通道路图4550683025801004070&求解非数值计算的问题：求解非数值计算的问题

4、： 设计出合适的数据结构及相应的算法设计出合适的数据结构及相应的算法 即：首先要考虑即：首先要考虑对相关的各种信息如何表示、组织对相关的各种信息如何表示、组织和存储？和存储？ 数据结构的研究内容为：数据结构的研究内容为： 研究非数值计算的程序设计问题中计算机的研究非数值计算的程序设计问题中计算机的操作操作对象对象以及它们之间的以及它们之间的关系和操作关系和操作。 三要素：操作对象、关系、操作（算法）三要素：操作对象、关系、操作（算法）是数据的基本单位，是数据的基本单位，通常作为一个整体来处理。通常作为一个整体来处理。data item)：组成数据元素的、有独立含组成数据元素的、有独立含义的义的

5、最小单位最小单位，也称域，也称域( (field)field)。四者之间的关系：四者之间的关系： 数据数据 数据对象数据对象 数据元素数据元素 数据项数据项例：例： 学生表学生表 个人记录个人记录 学号、姓名学号、姓名是相互之间存在一种或多是相互之间存在一种或多种特定关系的数据元素的集合。种特定关系的数据元素的集合。 逻辑结构：逻辑结构： 从解决问题的需要出发，为实现必要的功能所建立的数据模从解决问题的需要出发，为实现必要的功能所建立的数据模型。用于描述数据元素之间的逻辑关系，与数据的存储无关。型。用于描述数据元素之间的逻辑关系，与数据的存储无关。 物理（存储）结构：物理（存储）结构： 数据元

6、素及其关系在计算机存储器中的存储方式。数据元素及其关系在计算机存储器中的存储方式。即数据逻即数据逻辑结构的物理存储方式。辑结构的物理存储方式。划分方法一划分方法一 （1 1）线性结构）线性结构- 有且仅有一个开始和一个终端结点，并且有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。所有结点都最多只有一个直接前趋和一个后继。 例如：线性表、栈、队列、串例如：线性表、栈、队列、串 （2 2）非线性结构）非线性结构- 一个结点可能有多个直接前趋和直接后继。一个结点可能有多个直接前趋和直接后继。 例如：树、图例如：树、图逻辑结构逻辑结构线性结构线性结构一对一，如线性表、栈、

7、队列一对一，如线性表、栈、队列树形结构树形结构一对多，如树一对多，如树集合集合数据元素间除数据元素间除“同属于一个集合同属于一个集合”外，无其它关系外，无其它关系图形结构图形结构多对多，如图多对多，如图逻辑结构逻辑结构划分方法二划分方法二数据结构示例：数据结构示例： 工号工号 姓名姓名 性别性别 出生年月出生年月 职务职务 班排班排 01 张三张三 男男 1972.3.20 连长连长 二连二连 02 李四李四 男男 1978.6.14 排长排长 一排一排 03 王五王五 男男 1974.12.7 排长排长 二排二排 04 赵一赵一 女女 1982.8.5 排长排长 三排三排 05 赵二赵二 男

8、男 1969.8.15 士兵士兵 一排一排 06 赵七赵七 男男 1985.4.1 士兵士兵 一排一排 07 赵八赵八 男男 1982.6.28 士兵士兵 二排二排 08 钱一钱一 男男 1977.317 士兵士兵 二排二排 09 钱二钱二 男男 1985.10.12 士兵士兵 二排二排 10 钱三钱三 女女 1986.7.5 士兵士兵 三排三排 工号工号 姓名姓名 性别性别 出生年月出生年月 职务职务 班排班排 01 张三张三 男男 1972.3.20 连长连长 二连二连 02 李四李四 男男 1978.6.14 排长排长 一排一排 03 王五王五 男男 1974.12.7 排长排长 二排二

9、排 04 赵一赵一 女女 1982.8.5 排长排长 三排三排 05 赵二赵二 男男 1969.8.15 士兵士兵 一排一排 06 赵七赵七 男男 1985.4.1 士兵士兵 一排一排 07 赵八赵八 男男 1982.6.28 士兵士兵 二排二排 08 钱一钱一 男男 1977.317 士兵士兵 二排二排 09 钱二钱二 男男 1985.10.12 士兵士兵 二排二排 10 钱三钱三 女女 1986.7.5 士兵士兵 三排三排定义：定义：data_structure=( D , S ) D= 01,02,03,04,05,06,07,08,09,10S= 0102030405060708091

10、0集合集合不考虑该表中记录之间的任何次序不考虑该表中记录之间的任何次序定义：定义：data_structure=( D , S ) D= 01,02,03,04,05,06,07,08,09,10S=, , 05010308020704060910线性结构线性结构考虑按人员出生年月从大到小排列组织数据考虑按人员出生年月从大到小排列组织数据 工号工号 姓名姓名 性别性别 出生年月出生年月 职务职务 班排班排 01 张三张三 男男 1972.3.20 连长连长 二连二连 02 李四李四 男男 1978.6.14 排长排长 一排一排 03 王五王五 男男 1974.12.7 排长排长 二排二排 04

11、 赵一赵一 女女 1982.8.5 排长排长 三排三排 05 赵二赵二 男男 1969.8.15 士兵士兵 一排一排 06 赵七赵七 男男 1985.4.1 士兵士兵 一排一排 07 赵八赵八 男男 1982.6.28 士兵士兵 二排二排 08 钱一钱一 男男 1977.317 士兵士兵 二排二排 09 钱二钱二 男男 1985.10.12 士兵士兵 二排二排 10 钱三钱三 女女 1986.7.5 士兵士兵 三排三排定义：定义：data_structure=( D , S ) D= 01,02,03,04,05,06,07,08,09,10S=, , 05010308020704060910

12、树形结构树形结构考虑领导与被领导之间的关系考虑领导与被领导之间的关系 工号工号 姓名姓名 性别性别 出生年月出生年月 职务职务 班排班排 01 张三张三 男男 1972.3.20 连长连长 二连二连 02 李四李四 男男 1978.6.14 排长排长 一排一排 03 王五王五 男男 1974.12.7 排长排长 二排二排 04 赵一赵一 女女 1982.8.5 排长排长 三排三排 05 赵二赵二 男男 1969.8.15 士兵士兵 一排一排 06 赵七赵七 男男 1985.4.1 士兵士兵 一排一排 07 赵八赵八 男男 1982.6.28 士兵士兵 二排二排 08 钱一钱一 男男 1977.

13、317 士兵士兵 二排二排 09 钱二钱二 男男 1985.10.12 士兵士兵 二排二排 10 钱三钱三 女女 1986.7.5 士兵士兵 三排三排定义：定义：data_structure=( D , S ) D= 01,02,03,04,05,06,07,08,09,10S=, , , 05010302070406图形结构图形结构考虑好朋友关系考虑好朋友关系 工号工号 姓名姓名 性别性别 出生年月出生年月 职务职务 班排班排 01 张三张三 男男 1972.3.20 连长连长 二连二连 02 李四李四 男男 1978.6.14 排长排长 一排一排 03 王五王五 男男 1974.12.7

14、排长排长 二排二排 04 赵一赵一 女女 1982.8.5 排长排长 三排三排 05 赵二赵二 男男 1969.8.15 士兵士兵 一排一排 06 赵七赵七 男男 1985.4.1 士兵士兵 一排一排 07 赵八赵八 男男 1982.6.28 士兵士兵 二排二排 08 钱一钱一 男男 1977.317 士兵士兵 二排二排 09 钱二钱二 男男 1985.10.12 士兵士兵 二排二排 10 钱三钱三 女女 1986.7.5 士兵士兵 三排三排两种：两种：顺序顺序存储结构存储结构 借助元素在存储器中的借助元素在存储器中的相对位置相对位置来表示数据元素来表示数据元素间的逻辑关系。要求用地址连续的一

15、整片存储空间间的逻辑关系。要求用地址连续的一整片存储空间（数组）。（数组）。链式链式存储结构存储结构 借助指示元素存储地址的借助指示元素存储地址的指针指针表示数据元素间的表示数据元素间的逻辑关系。无需一整块存储空间。逻辑关系。无需一整块存储空间。存储结构存储结构元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=L0+（i-1)*m顺序存储顺序存储每个元素占每个元素占m个字节个字节L0为整片存储空间的起始地址为整片存储空间的起始地址1536元素元素2 21400元素元素1 1134

16、6元素元素3 3 元素元素4 41345h存储地址存储地址 存储内容存储内容 指针指针 13451345 元素元素1 1 1400 1400 13461346 元素元素4 4 . . . . . 14001400 元素元素2 2 1536 1536 . . . . . 15361536 元素元素3 3 1346 1346 链式存储链式存储 h后继元素后继元素所在地址所在地址记住首元记住首元素地址素地址对于一种数据结构对于一种数据结构, , 常见的运算包括：常见的运算包括： 插入插入 删除删除 修改修改 查找查找 排序排序 逻辑结构和存储结构都相同逻辑结构和存储结构都相同, , 但运算不同但运算

17、不同, , 则数据则数据结构不同。结构不同。 例如例如, , 栈与队列栈与队列数据结构关心的三个方面：数据结构关心的三个方面： 1数据的逻辑结构数据的逻辑结构 2、数据的存储结构、数据的存储结构 A线性结构线性结构 B非线性结构非线性结构A 顺序存储顺序存储 B 链式存储链式存储 线性表线性表 栈、队列栈、队列树形结构树形结构图形结构图形结构数据结构的三个方面数据结构的三个方面 3、数据的运算：插入、删除、修改、查找、排序等。、数据的运算：插入、删除、修改、查找、排序等。 串、数组串、数组集合结构集合结构1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现一个数据的集合一个数据的集

18、合, , 以及定义于这个数以及定义于这个数据集合上的一组操作的总称。据集合上的一组操作的总称。 C C语言中的数据类型：语言中的数据类型： 基本数据类型、指针类型、数组类型、结构基本数据类型、指针类型、数组类型、结构体类型、公用体类型、枚举类型体类型、公用体类型、枚举类型(ADT: Abstract Data Types) 是指是指用户定义的用户定义的一个数学模型以及定义在此数一个数学模型以及定义在此数学模型上的一组操作的总称。学模型上的一组操作的总称。 （仅（仅定义定义数据的逻辑结构和操作说明，不考虑在数据的逻辑结构和操作说明，不考虑在计算机内部的表示和实现）计算机内部的表示和实现）抽象数据

19、类型抽象数据类型可以用以下的三元组来表示：可以用以下的三元组来表示： ADT = （D，S，P） 数据对象数据对象 D上的关系集上的关系集 D上的操作集上的操作集 ADTADT抽象数据类型名抽象数据类型名 数据数据对象对象： 数据数据关系关系： 基本基本 ： ADT ADT抽象数据类型抽象数据类型名名ADT常用常用定义定义格式格式 抽象数据类型可以通过固有的数据类型（如整型、抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。实型、字符型等）来表示和实现。 教材中用的是类教材中用的是类C C语言作为描述工具，语言作为描述工具，p8p8。例题：例题： 定义矩形的抽象数据类型

20、，其数据包括矩形的长和宽，定义矩形的抽象数据类型，其数据包括矩形的长和宽，操作包括初始化矩形的长和宽，计算矩形的周长与面积。操作包括初始化矩形的长和宽，计算矩形的周长与面积。 ADT Rectangle 数据对象数据对象：D=e1,e2|e1,e2是实数是实数 数据关系：数据关系：S=|e1是矩形长，是矩形长，e2是矩形宽是矩形宽 基本操作基本操作： InitRectangle (&R, len, wid); 操作结果：构造矩形操作结果：构造矩形R，长与宽分别被赋予参数，长与宽分别被赋予参数 len 与与wid的值的值 Circumference (R); 初始条件：初始条件：R已存在

21、已存在 操作结果：返回矩形操作结果：返回矩形R的周长的周长 Area (R); 初始条件：初始条件：R已存在已存在 操作结果：返回矩形操作结果：返回矩形R的面积的面积 ADT Rectangle 表示部分：表示部分： typedef struct Rect float length, width; Rectangle;实现部分：实现部分： void InitRectangle(&Rectangle r, float len, float wid) r. Length = len; r. Width = wid; float Circumference (Rectangle r) ret

22、urn 2*(r.length + r.width); float Area (Rectangle r) return r.length * r.width; void Main() Rectangle x; InitRectangle(x,10,5); cout Area (x)endl; .( algorithm)1.4 1.4 算法和算法分析算法和算法分析算法效率分析方法：算法效率分析方法： 事后统计：事后统计： 事前分析估算：事前分析估算：通常采用这种方法，计算渐进复杂度通常采用这种方法，计算渐进复杂度 同一个算法用不同的语言、不同的编译程序、同一个算法用不同的语言、不同的编译程序、在

23、不同的计算机上运行，效率均不同，在不同的计算机上运行，效率均不同，使用使用绝对时间单位绝对时间单位衡量算法效率不合适衡量算法效率不合适算法的时间复杂度算法的时间复杂度是一个算法运行时间的相对量度是一个算法运行时间的相对量度算法的运行时间算法的运行时间 = = 计算机执行一种简单操作的时间计算机执行一种简单操作的时间* *简单操作的执行次数简单操作的执行次数 （与机器有关，不考虑）（与机器有关，不考虑）如：如：t=x; x=y; y=t;t=x; x=y; y=t; 运行时间运行时间 = = 一条赋值语句的执行时间一条赋值语句的执行时间* *3 3 通常把算法中包含简单操作次数的多少叫做该算法通

24、常把算法中包含简单操作次数的多少叫做该算法的时间复杂度，用它来衡量一个算法的运行时间性能。的时间复杂度，用它来衡量一个算法的运行时间性能。 若解决一个问题的规模为若解决一个问题的规模为n n，即表示待处理的数据中即表示待处理的数据中包含有包含有n n个元素，则算法的个元素，则算法的时间复杂度时间复杂度通常是通常是n n的一个函的一个函数，记为数，记为f(n)f(n)。例例1 1：分析以下程序的时间复杂度：分析以下程序的时间复杂度 int Sum(int b, int n) int i, s=0; /频度为频度为1 for ( i=0; in; i+ ) /频度为频度为(n+1) s=s+bi;

25、 /频度为频度为n return s; /频度为频度为1 （一条语句重复执行的次数称语句的频度）（一条语句重复执行的次数称语句的频度） 时间复杂度时间复杂度: : f(n) = 2 2n+3 = O(n)例例2 2：分析以下程序段的时间复杂度：分析以下程序段的时间复杂度 for ( i=1; i=n; i+) /n+1次次 y+ ; /n次次 for ( j=1; j= n0n = n0时，时， T(n)T(n)=M=M* *f(n)|f(n)| 表示随问题规模表示随问题规模n n的增大，算法执行时间的增长率的增大，算法执行时间的增长率与函数与函数f(n)f(n)的增长率相同。的增长率相同。

26、当当 f(n)= c0nm+c1nm-1+cm-1n+cm 时，时， T(n)= O(nm) 采用数量级的形式表示后采用数量级的形式表示后，时间复杂度不必计算出时间复杂度不必计算出简单操作的精确次数，只要计算出相应的简单操作的精确次数，只要计算出相应的数量级数量级即可。即可。 例：例：lx =x+1; y =y+1; O(1)lfor (i=1;i=n;i+) x=x+1 O(n)lfor (i=1;i=n;i+) for (j=1; j=i-1; j+) x=x+1 O(n2)算法的时间复杂度是由算法的时间复杂度是由嵌套最深层嵌套最深层语句的频度决定的语句的频度决定的算法的时间复杂度通常具有

27、形式：算法的时间复杂度通常具有形式：O(1)、 O(log2n) 、 O(n) 、O(n*log2n)、O(n2)、O(n3)、O(2n) 、O(n!)随着随着n n的增大，各种数量级对应值的增长速度大不相同，的增大，各种数量级对应值的增长速度大不相同，对应关系如下：对应关系如下： P14 图图1.7 O(1) O(log2n) O(n) O(n*log2n) O(n2) O(2n) O(n!) 一个算法的一个算法的时间复杂度时间复杂度还可以具体分为还可以具体分为最好最好、最最差差和和平均平均三种情况来讨论三种情况来讨论 。例：顺序查找算法例：顺序查找算法 int SequenceSearch(int a , int n, int item) /若查找成功则返回元素的下标，否则返回若查找成功则返回元素的下标，否则返回-1。 for (int i=0; in; i+) if (ai=item) return i; return -1; 第