数据结构 第1章 绪论

1、数据结构 与 算法第一讲：绪论我是谁?08/08/20222郑炜 老师现在：厦门大学计算机系讲师之前：清华大学计算机系本科硕士-英国曼彻斯特大学博士欢迎提问；欢迎提建议。学好数据结构与算法的理由08/08/20223数据结构很枯燥，不好学下列情况中，你属于哪一种？我想拿学位核心基础专业课程我想考研必考科目我想当优秀的程序员内功心法我喜欢计算机科学向你致敬，请感受编程之美打酱油的如果有一天，你真的在写程序比如，有一个客服电话系统需要开发。你负责编写客户排队模块的代码如果你用数据库设计一张客户排队表你的数据结构白学了。杀鸡焉用宰牛刀？如果你直接用数组去实现一张客户排队表你的数据结构白学了。溢出怎么

2、办？新增和删除怎么办？所以学了这门课你应该知道在这种情况下用哪种数据结构合适。我们所学的数据结构在编程语言的开发工具包里好像都实现了，还有必要上这门课吗？是的，授人以鱼不如授人以渔。08/08/20224本课程的主要内容数据结构的基本概念线性表栈和队列串数组树图查找排序08/08/20225学习方法认真听讲，积极互动阅读/分析大量例程序勤于思考，善于联系身边的例子独立完成各算法的程序设计和调试训练手写伪代码的能力08/08/20226今天的任务数据结构研究的主要内容08/08/20227数据结构中涉及的基本概念算法的概念、描述方法以及评价标准学习要点了解数据结构有关概念的含义，特别是数据的逻辑

3、结构和存储结构之间的关系；（重点）熟悉类C语言的书写规范；了解计算算法时间复杂度的方法。（难点）08/08/20228数据结构是什么08/08/20229数据结构的起源和发展从计算器到计算机从“不可编程”到“可编程”从“纯数值计算”到“非数值计算”数据结构问题起源于程序设计程序设计主要关心数据如何表示：数据的组织和存储数据如何处理：求解问题的步骤非数值计算涉及的信息如何表示、组织、存储和处理？1968年，数据结构课程元年。（D. E. Kruth）70年代后，大型程序软件的开发使数据结构受到更多重视关于数据结构的研究并不曾结束GIS，空间数据库，多维数据结构08/08/202210基本概念和术

4、语【数据】是对信息的一种符号表示。是可以输入计算机中，能被计算机识别处理和输出的一切符号集合。【数据元素】是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。也称为记录。【数据项】一个数据元素可由若干个数据项组成。是数据不可分割的最小单位。【数据对象】是性质相同的数据元素的集合。是数据的一个子集。08/08/202211【数据结构】相互之间存在一种或多种特定关系的数据元素的集合从不同的视角看数据结构08/08/202212数据结构人的思考：如何组织计算机：如何存储逻辑结构存储（物理）结构逻辑结构08/08/202213数据元素之间的逻辑关系。即从逻辑关系上描述数据，与数据的存储无关，是

5、独立于计算机的。 逻辑结构的例子（1）学籍管理问题信息的组织？各表项之间的关系？通常进行的操作？08/08/202214学号姓名性别出生年月政治面貌0001张 三男1991/10团员0002李 四男1990/03团员0003王老五女1992/08党员。逻辑结构的例子（2）人机对弈问题树结构各棋盘格局之间是什么关系？通常进行的操作？08/08/202215.逻辑结构的例子（3）教学计划安排图结构课程之间是什么关系？通常进行的操作？08/08/202216C4, C5, C6数据库原理C7C2, C4计算机原理C6C3, C4数据结构C5C1, C2程序设计C4C1离散数学C3无计算机导论C2无高

6、等数学C1先修课课程名称编号C1C2C3C4C6C5C7四种基本逻辑结构08/08/202217【集合】 数据元素间除了“同属于一个集合”外，无其他关系。【线性结构】 1对1的关系比如线性表、栈、队列。【树形结构】 1对多的关系比如树。【图形结构】 多对多的关系比如图。数据（逻辑）结构的形式定义数据结构是一个二元组 Data_Structure = (D, R) 其中:D 是数据元素的有限集，R 是 D 上关系的有限集。例如: 一维数组a1, a2, a3, a4, a5, a6的形式定义D = a1, a2, a3, a4, a5, a6R =| i=1, 2, 3, 4, 508/08/2

7、02218不同的“关系”构成不同的“结构”！集合的形式定义SET = (D, R)D = 01, 02, 03, 04, 05, 06, 07R = 08/08/20221901050304020607线性结构的形式定义08/08/202220LINEAR = (D, R)D = 01, 02, 03, 04, 05, 06, 07R = ,01020304050607树结构的形式定义08/08/202221TREE = (D, R)D = 01, 02, 03, 04, 05, 06, 07R = ,01020304050607图结构的形式定义08/08/202222GRAPH = (D,

8、R)D = 01, 02, 03, 04, 05, 06, 07R = ,01020304050607存储结构08/08/202223亦称物理结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。 存储结构（1）顺序存储结构用一组地址连续的存储单元依次存储数据元素数据间的逻辑关系由元素的存储位置来决定优点：简单缺点：不易变动08/08/202224ABCDEFGH001002003004005006007008数据(虚拟)地址存储结构（2）链式存储结构用一组任意的存储单元存储数据元素数据之间的逻辑关系用指针来表示优点：修改灵活缺点：复杂08/08/202225AHGFBCDE

9、001042043044105106107108数据(虚拟)地址复数 3.0-2.3i 的两种存储方式08/08/2022263.0-2.33.00415-2.303000302041506110613数据(虚拟)地址数据(虚拟)地址逻辑结构与存储结构的关系逻辑结构是数据关系在人脑中的抽象存储结构是逻辑结构在计算机中的实现两者综合起来建立了数据元素之间的结构关系，即数据结构08/08/202227数据运算如何在数据的各种（逻辑的和存储的）结构的基础上对数据实施一系列有效的基本操作。常用的数据运算：插入：添加一个数据元素删除：移除一个数据元素修改：更改一个数据元素查找：寻找一个数据元素排序：把数

10、据元素按照某种顺序关系排列起来08/08/202228数据结构课程学什么08/08/202229数据结构课程学习的主要内容08/08/202230如何对数据进行逻辑组织（逻辑结构）一个具体问题的逻辑数据结构是什么？如何把数据存储到计算机中去（存储结构）适宜选用什么样的存储结构？相关的数据运算的定义与实现（算法）采用什么样的操作实现算法效率更高？“程序 = 数据结构 + 算法” （Niklaus Wirth)课程内容的组织08/08/202231线性表栈和队列串数组树图查找排序数据结构逻辑结构存储结构数据运算线性结构（线性表/栈/队列/串/数组）非线性结构树结构图结构顺序结构链式结构插入运算删除

11、运算修改运算查找运算排序运算用什么形式来定义一个具体的数据结构08/08/202232数据类型最早出现于高级语言中，是指一组性质相同的值的集合及定义在集合上的一些操作的总称。在高级语言中，每个变量、常量、表达式都有各自的类型类型用来说明变量或表达式的取值范围和允许施加的操作数据类型的分类原子类型：不可再分解的基本类型，如整型、字符型结构类型：由若干个类型组成、可分解，如整型数组。可看成由一种数据结构和定义在其上的一组操作组成。08/08/202233抽象数据类型抽象是指抽取出事物具有的普遍性本质。抽象数据类型（Abstract Data Type, ADT)是指一个数学模型及定义在该模型上的一

12、组操作，与其在计算机内部如何表示无关。实际上和数据类型是一个概念。“整型”就是一个抽象数据类型不同计算机硬件系统实现整数和整数运算的细节是不一样的编程者看来它们的定义和操作却是相同的范畴更广，包括自定义数据类型比如 ，复数类型以数据为中心的软件开发思路。抽象数据类型的特征：使用与实现分离，实行封装和信息隐藏08/08/202234抽象数据类型的定义抽象数据类型实际上就是对该数据结构的定义。用三元组描述如下:ADT = (D, S, P)其中：D 是数据对象，S 是 D 上的关系的集合， P 是对 D 的基本操作的集合。ADT抽象数据类型名数据对象：数据关系：基本操作：ADT 抽象数据类型名08

13、/08/202235抽象数据类型表示的示例ADT 抽象数据类型名Data数据对象的定义数据元素之间逻辑关系的定义Operation操作 1初始条件操作结果描述操作 2操作 n endADT08/08/202236ADT ComplexD = r1, r2 | r1, r2 都是实数S = | r1是实部，r2是虚部assign (&C, v1, v2) 初始条件：复数C已存在 操作结果：构造复数C，r1, r2分别 被赋以参数v1, v2的值。destroy (&C) 初始条件：复数C已存在 操作结果：复数C被销毁。 ADT Complex用C语言定义抽象数据类型typedef double

14、ItemType/* 定义数据项类型 */typedef structItemType r;/* 实部 */ItemType m;/* 虚部 */ Complex/* 定义复数抽象类型 */void assign(Complex *A, ItemType r, ItemType m);/* 赋值 */void add (Complex *A, Complex B);/* A + B */void minus (Complex *A, Complex B);/* A - B */void multiply (Complex *A, Complex B);/* A * B */void divid

15、e (Complex *A, Complex B);/* A / B */08/08/202237用C语言实现抽象数据类型08/08/202238Void assign (Complex * A, ItemType real, ItemType imaginary)A-r = real;/* 实部赋值 */A-m = imaginary;/* 虚部赋值 */ /* End of assign()*/void add (Complex *A, Complex B);/* A = A + B */ A-r += B.r; /* 实部相加*/ A-m += B.m; /* 虚部相加*/ /* End

16、 of Add() */有没有更合适的方法描述抽象数据类型08/08/202239抽象数据类型的表示和实现表示和实现抽象数据类型时可以使用固有的数据类型（如整型、实型、字符型等）。抽象数据类型有些类似C语言中的结构（struct）类型，但增加了相关的服务。我们采用类C语言（介于伪代码和C语言之间）作为描述工具。不拘泥于C语言的细节又容易实现。注意：上机时仍要用具体的编程语言实现，如C或C+。08/08/202240类C语言简要说明（一）1、预定义常量和类型/函数结果状态代码 #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#def

17、ine INFEASIBLE -1#define OVERFLOW -2/Status 是函数的类型，其值是函数结果状态代码typedef int Status;2、数据结构的表示(数据的存储结构) 用C的类型定义(typedef)描述，数据元素类型约定为ElemType, 由用户在使用该数据类型时自行定义。类C语言简要说明（二）3、基本操作的算法的函数描述 函数类型 函数名(函数参数表) /算法说明 语句序列 /函数名(1)除了函数的参数需要说明类型外，算法中使用的辅助变量可以不作变量说明，必要时对其作用给予注释。(2)一般而言，a、b、c、d、e等用作数据元素名，i、j、k、l、m、n等用

18、作整型变量名，p、q、r等用作指针变量名。(3)当函数返回值为函数结果状态代码时，函数定义为Status类型。(4)除了值调用方式外，增添了C+语言的引用调用的参数传递方式。在形参表中，以&打头的参数即为引用参数。类C语言简要说明（三）4、赋值语句简单赋值 变量名=表达式；串联赋值 变量名1=变量名2= 变量名k=表达式；成组赋值（变量名1,变量名k）=（表达式1,表达式k）；结构赋值 结构名=结构名；结构赋值 结构名 =（值1,值k）；数组赋值 变量名=表达式；数组赋值 变量名始下标.终下标=变量名起始下标.终止下标；交换赋值 变量名变量名；条件赋值 变量名=条件表达式？表达式T;表达式F；

19、类C语言简要说明（四）5、选择语句条件语句1 if(表达式)语句； 条件语句2 if（表达式）语句；else 语句；开关语句1 switch（表达式） case值1： 语句序列1；break；case值n： 语句序列n；break；default：语句序列n+1； 开关语句2 switch case条件1：语句序列1；break；case条件n：语句序列n；break；default：语句序列n+1；类C语言简要说明（五）6、循环语句for语句 for(赋初值表达式序列；条件；修改表达式序列) 语句序列；while语句 while(条件) 语句序列；do-while语句 do 语句序列； wh

20、ile(条件);7、结束语句函数结束语句 return 表达式； return;case结束语句 break;异常结束语句 exit(异常代码)类C语言简要说明（六）8、输入和输出语句有 输入语句 scanf (格式串， 变量1，变量n); 输出语句 printf(格式串，表达式1，表达式n);通常省略格式串。9、注释 单行注释 /文字序列10、基本函数有 求最大值 max (表达式1，表达式n) 求最小值 min(表达式1，表达式n) 求绝对值 abs(表达式) 求不足整数值floor(表达式) 求进位整数值ceil(表达式) 判定文件结束eof(文件变量) 或eof 判定行束 eoln(文

21、件变量)或eoln11、逻辑运算约定 与运算& 对于A&B，当A的值为0时，不再对B求值。 或运算| 对于A|B，当A的值为非0时，不再对B求值。课程名数据结构与算法，什么叫算法？08/08/202247数据结构和算法的关系08/08/202248不能只谈数据结构而不谈算法老师下周就可以结课学生不知道数据结构有什么用不可能涉及算法的全部内容算法可以独立开一门新课这里，学习算法是为了更好的理解数据结构算法的概念算法是解决某个特定问题的求解步骤的描述。算法在计算机中表现为指令的有限序列，每条指令表示一个或多个操作。计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运

22、算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。程序不等于算法：计算机程序是算法的具体实现。08/08/202249（1）有穷性：一个算法必须在执行有穷步之后结束。（2）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。（3）可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。（4）输入：一个算法应该有零个或多个输入。（5）输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。算法的性质算法设计的要求正确性（四个境界）没有语法错误对于合法的输入数据能够产生满足要求的输出对于非法的输入数据能够得出满足规格说明的结果对于

23、任何测试数据都有满足要求的输出结果可读性：便于阅读、理解和交流健壮性：不合法数据也能合理处理时间效率高和存储量低08/08/202251算法的基本结构顺序结构表示程序执行的流程确定地按照某一次序进行。08/08/2022算法与算法描述52ABABCAC选择结构表示程序的流程可能有多种选择，只有结合输入才知道究竟按哪一个流程执行。循环结构表示程序的流程在某些步骤上要反复执行，直到满足某条件。TrueTrueFalse算法的六种表示方法算法的自然语言表示算法的流程图表示算法的N-S图表示算法的PAD图表示算法的伪代码表示算法的类C语言表示08/08/202253算法表示方法(1)用自然语言表示算法

24、S1：输入s与v；S2：判断v是否为0，若v=0，则输出错误信息；否则计算s/vt，且输出t问题：计算并输出t=s/v。点评：优点- 直白缺点- 层次结构不清晰，容易发生歧义， 不适合描述大规模程序08/08/202254算法表示方法(2)用流程图表示算法问题：计算并输出t=s/v。V=0计算s/v t08/08/202255输入s与v输出t输入错误信息成立不成立算法表示方法(3)用N-S流程图表示算法问题：计算并输出t=s/v。输入s与vV=0输出错误信息 计算s/v t成立不成立08/08/202256输出t算法表示方法(4)用PAD图表示算法问题：计算并输出t=s/v。输入s与v输出错误

25、信息 计算s/v t，且输出tV=0点评：优点- 直观、易懂、逻辑关系清晰。 缺点- 费事，难改。08/08/202257成立不成立算法表示方法(5)用伪代码表示算法INPUT s,vIF(v=0) THENOUTPUT “ERROR”ELSEt = s/vOUTPUT t问题：计算并输出t=s/v。点评：容易理解；不必画图；接近程序设计风格，容易转化为程序08/08/202258算法表示方法(6)用类C语言表示算法scanf(“%d,%d”, &s, &v);if(v=0)printf(“ERROR”);elset = s/vprintf(“t = %d”,t);问题：计算并输出t=s/v。

26、08/08/202259点评：特点同伪代码，更容易转化为C程序怎样衡量算法的效率？08/08/202260算法效率的度量方法事后统计方法通过设计好的测试程序和数据，利用计算机测量其运行时间。缺陷：需要先编写程序；和计算机软硬件相关；和测试数据相关。事前分析估算方法（我们的选择）依据统计方法对算法进行估算。m = f(n)，m是语句总的执行次数，n是输入的规模。和问题输入规模相关，独立于程序设计语言和计算机软硬件08/08/202261事先分析估算方法的例子int i, sum = 0, n = 100;/ 执行了1次；for (i = 1; i N，f(n)总是比g(n)大，那么，我们说f(n

27、)的渐进增长快于g(n)。08/08/202263输入规模算法A (4n+8)算法B (n)算法C (2n2 +1)算法 D (n3)n = 112131n = 216298n = 32031927n = 1048102011000n = 100408100200011000000n = 10004008100020000011000000000算法时间复杂度08/08/202264在进行算法分析时，语句的总执行次数 T(n)是关于问题规模 n 的函数，进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。算法的时间复杂度，也就是算法的时间量度，用“大O记法”记作：T(n)=O(f

28、(n)。由此得到的 T(n) 的数量级叫“大O阶”。它表示随问题规模 n 的增大，算法执行时间增长率和 f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。其中 f(n) 是问题规模 n 的某个函数。一般情况下，T(n)增长越慢，算法越优。大O阶的数学定义 当n时，有f(n)/g(n)=常数0， 则称函数f(n)与g(n)同阶,或者说，f(n)与g(n)同一 个数量级，记作 f(n)=O(g(n) 称上式为算法的时间复杂度,或称该算法的时间复杂 度为O(g(n) 。其中, n为问题的规模(大小)的量度。若lim(f(n)/g(n) =lim(2n3 + 3n2 + 2n + 1)/

29、n3) =2nn则算法的时间复杂度为O(n3)推导大O阶的方法08/08/202266用常数 1 取代运行时间中的所有加法常数。在修改后的运行次数函数中，只保留最高阶项。如果最高阶项存在且不是 1，则移除与这个项相乘的常数。由此得到的结果就是大O阶。常数阶 O(1)08/08/202267int i, sum = 0, n = 100;/ 执行了1次；sum = (1+n)*n/2;/ 执行了1次；printf (“%d”,sum);/ 执行了1次；3次注意：不管常数是什么，我们都记作O(1)。没有O(3)，只有O(1)!线性阶 O(n)08/08/202268int i;for (i = 1

30、; i = n; i+)/* 时间复杂度为O(1)的程序步骤序列 */int i = 0;while (i n) i+;/* 时间复杂度为O(1)的程序步骤序列 */对数阶 O(logn)08/08/202269int count = 1;while (count n) count = count * 2;/* 时间复杂度为O(1)的程序步骤序列 */平方阶 O(n)08/08/202270int i, j;for (i = 0; i n; i+) for (j=0; ji; j+) /* 时间复杂度为O(1)的程序步骤序列 */ (a) 如果第二行 i n 换成 i m 呢？(b) 如果第四

31、行 j = 0 换成 j = i 呢？时间复杂度的叠加08/08/202271int i,j,k;for (i = 0; i n; i+) for (j=0; jn; j+) /* 时间复杂度为O(1)的程序步骤序列 */ for (k = 1; k = n; k+)/* 时间复杂度为O(1)的程序步骤序列 */O(n2)+O(n)=O(n2)函数调用对时间复杂度的影响08/08/202272int i;for (i = 1; i = n; i+)function(i);/ 执行步骤为 n(n+1)/2void function (int count) int j; for (j = 0; j

32、count; j+) /* 时间复杂度为O(1)的程序步骤序列 */ 常见的时间复杂度08/08/202273执行次数函数阶非官方名称12O(1)常数阶2n+3O(n)线性阶3n2 +2n+1O(n2)平方阶5log 2n +20O(log n)对数阶2n+3nlog 2n +19O(nlog n)nlog n阶6n3 +3n2 +3n+4O(n3)立方阶2nO(2n)指数阶O(1)O(log n)O(n)O(nlog n)O(n2)O(n3)O(2n)O(n!)O(nn)最好情况、最坏情况 与 平均情况时间复杂度一般指的都是最坏情况的运行时间。为什么？平均情况的运行时间有什么意义？为什么不使用最好情况的运行时间来衡量算法效率？08/08/202274算法空间复杂度08/0