1、 2011年春季年春季 数据结构数据结构和算法和算法Data Structure青岛理工青岛理工大学大学通信学通信学院院课前的话课前的话计算机系列课程之间的联系计算机系列课程之间的联系 计算机概论与上机操作（对 21 世纪公民要求）程序设计与算法语言（BASIC FORTRAN PASCAL C 等，怎样使用计算机）计算机组成原理（所有计算机的共性）微机原理及应用（特定机型介绍，单片机或 8086 PC 机，怎样应用计算机）控制之路 数据处理之路 汇编语言程序设计 数据结构数据结构 单片机技术/微机接口 操作系统 软件技术基软件技术基础础 数据库理论 计算机网络 软件工程 应用系统设计 计算机
2、网络 芯片无所不在的时代芯片无所不在的时代n日本地震对中国汽车业影响：n主要存在问题的是微处理器芯片短缺(日立)芯片的广泛使用导致编程无所不在芯片的广泛使用导致编程无所不在n普通机床n数控机床您将来到社会做什么？如何生存呢？您将来到社会做什么？如何生存呢？您需要编程序吗？您需要编程序吗？90%的可能性。的可能性。您需要了解程序和相关的实现吗？您需要了解程序和相关的实现吗？100%的可能性。的可能性。课前的话课前的话-通信专业学生学习数据结构的意义通信专业学生学习数据结构的意义n从实用的角度讲，通信无非是做硬件或做软件，两者都要用到数据结构。因为任何一个系统里都有数据，如何合理有效地组织数据，使
3、系统速度更快，数据访问方式更灵活，这都严重依赖于是否选择了合适的数据结构。n从专业课程的角度讲，数据结构的知识点在后继课程中会用到，例如计算机通信与网络、信息论与编码、现代通信与技术等等。n从就业的角度，从以往学生的情况来看，从事软件开发是一个比较容易找到工作的出口。学时数：学时数：32（248）学学 分：分：2教教 材：材：严蔚敏、吴伟民严蔚敏、吴伟民，数据结构（，数据结构（C语言版），清华大语言版），清华大学出版社，学出版社，1997年年4月第月第1版版 和和2007年第二版都行年第二版都行参考书：参考书：1 严蔚敏、吴伟民、米宁，数据结构题集（严蔚敏、吴伟民、米宁，数据结构题集（C语言版
4、），语言版），清华大学出版社，清华大学出版社，1999年年7月月许小可Email:如何看待不同老师的作用：与时俱进内内 容容 安安 排排章章内内 容容 学时学时 章章 内内 容容 学时学时 1绪绪 论论27图图62线性表线性表68动态存储管理动态存储管理略讲略讲3栈和队列栈和队列49查找查找44串串210内部排序内部排序55数组和广义表数组和广义表 211外部排序外部排序略讲略讲6树和二叉树树和二叉树 512文件文件略讲略讲考试成绩考试成绩n平时成绩（20%）（考勤、作业）n上机+综合程序设计（30%）n期末考试（50%）课程要求课程要求n第一层次：每种数据结构的适用性n第二层次：n每种数据结
5、构和算法的白话实现n第三层次：n每种数据结构和算法的C语言编程实现n思考题：n数据结构的学习是否依赖于编程语言？n这门课和C语言程序设计的关系是什么？第第1章章 绪论绪论第第2章章 线性表线性表第第3章章 栈和队列栈和队列 第第4章章 串串第第5章章 数组和广义表数组和广义表第第6 6章章 树和二叉树树和二叉树 第第7章章 图图第第9章章 查找查找第第10章章 排序排序目目 录录第一章第一章 绪论绪论讨论讨论5个问题：个问题：1.1什么是数据结构什么是数据结构n例 某人骑自行车从A地先以每小时12千米的速度下坡后，以每小时9千米的速度走平路到B地，共用55分钟.回来时，他以每小时8千米的速度通
6、过平路后，以每小时4千米的速度上坡，从B地到A地共用1.5小时，求A、B两地相距多少千米？n答案：设坡路长为x千米，A、B两地相距为y千米，依题意列如下方程组：n求解步骤：审题 设未知元设未知元列方程列方程解方程解方程检验作结论建立数学模型建立数学模型设计算法设计算法建立数学模型建立数学模型 设计算法设计算法 编程编程 测试调整测试调整数值计算问题操作对象：实型、整型、布尔型数据数学模型：数学方程式（计算机的主要操作是解方程）1.1.1非数值计算问题非数值计算问题例例1 学生信息管理问题学生信息管理问题 学号姓名性别籍贯出生日期 班级880001丁一男北京1987-2-19通信071班8800
7、02马二女青岛1988-3-13通信071班880036张三女济南1988-7-17通信072班880037李四男上海1987-2-27通信072班线性人机对弈背景资料人机对弈背景资料卡斯帕罗夫与“深蓝”对弈(右为“深蓝”操作者)“人机对弈人机对弈”诸宸最终诸宸最终负于紫光之负于紫光之星星 例2 人机对奕问题树非数值计算问题非数值计算问题非数值计算问题非数值计算问题姓名姓名项目项目1项目项目2项目项目3丁一跳高跳远100米马二标枪铅球张三标枪100米200米6李四铅球200米跳高王五跳远200米n例例3 田径赛时间安排问题田径赛时间安排问题 n例例3 田径赛时间安排问题田径赛时间安排问题 n问
8、题：设有六个比赛项目，规定每个选手至多可参加三问题：设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如表个项目，有五人报名参加比赛（如表1所示）设计比赛日所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。程表，使得在尽可能短的时间内完成比赛。表1（2）用顶点代表比赛项目）用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边（3）某选手比赛的项目必定有边相连）某选手比赛的项目必定有边相连 （不能同时比赛）（不能同时比赛）AEBFDCAEBFDC比赛时间比赛时间比赛项目比赛项目1A,C2B,D3E4F图表3姓名姓名项目项目1项目项目2项目项目3丁一ABE马二CD张三CE
9、F李四DFA王五BF表2n解法：解法：（1）设用如下六个不同的代号代表不同的项）设用如下六个不同的代号代表不同的项目：目：跳高 跳远 标枪 铅球 100米 200米 A B C D E F1.1.2数据结构学科定义数据结构学科定义数学软件硬件n数据结构是一门学科，它针对数据结构是一门学科，它针对非数值计算非数值计算的的程序设计问题，研究计算机的程序设计问题，研究计算机的操作对象操作对象以及以及它们之间的它们之间的关系关系（数学模型）和操作等等。（数学模型）和操作等等。n数据结构是介于数据结构是介于数学数学、计算机硬件计算机硬件和和计算计算机软件机软件三者之间的一门核心课程。三者之间的一门核心课
10、程。1.1.3术语简介术语简介:数据、数据元素、数据项数据、数据元素、数据项n数据数据(data)对客观事物的符号表示对客观事物的符号表示，所有能被计算机所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息、图像等信息）。）。n数据元素数据元素(data element)是数据的是数据的基本基本单位，具有单位，具有完完整确定的实际意义整确定的实际意义(又称元素、结点，顶点、记录等）。又称元素、结点，顶点、记录等）。n数据项数据项(Data item)构成数据元素的项目，是构成数据元素的项目，是具有独立具有独立含义的最小含
11、义的最小标识单位（又称字段、域、属性标识单位（又称字段、域、属性 等）。等）。三者之间的关系：三者之间的关系：数据数据 数据元素数据元素 数据项数据项学号姓名性别籍贯出生日期 班级880001丁一男北京1987-2-19通信071班1.1.4基本概念基本概念n数据结构数据结构是相互之间存在一种或多种特定相互之间存在一种或多种特定关系关系的的数据元素数据元素的的 集合，表示为：集合，表示为：Data_Structure=（D,R）元素有限集元素有限集关系有限集关系有限集（数值或非数值数值或非数值）n数据对象数据对象(data object)-是性质相同的数据元素的集合，是数据的一个子集。例如，字
12、母字符对象是集合C=A,B,Zn结构结构是指同一数据元素类型中各元素之间存在的关系的是指同一数据元素类型中各元素之间存在的关系的集合。集合。n数据结构数据结构是是带结构的数据元素带结构的数据元素的集合的集合.n思考：数据结构和算法之间的关系思考：数据结构和算法之间的关系例 在2行3列的二维数组a1,a2,a3,a4,a5,a6中六个元素之间存在两个关系:a1 a2 a3 a4 a5 a6行的次序关系行的次序关系:列的次序关系列的次序关系:row=,col=,a1 a3 a5 a2 a4 a6 a1 a2 a3a4 a5 a6数据结构示例1.2学习数据结构的意义学习数据结构的意义n选择合适的数据
13、结构解决应用问题n程序设计程序设计=好算法好算法+好结构好结构n例 学生信息查询问题 班级地址通信061班通信062班学号姓名性别籍贯出生日期 班级880001丁一男北京1988-2-19通信061班880002马二女青岛1989-3-13通信061班880036张三女济南1988-7-17通信062班880037李四男上海1989-2-27通信062班n计算机内的数值运算依靠方程式，而非数值运算（如计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。表、树、图等）则要依靠数据结构。n同样的数据对象，用不同的数据结构来表示，运算效同样的数据对象，用不同的数据结构来表示
14、，运算效率可能有明显的差异率可能有明显的差异。索引表1.3 数据结构涵盖的内容数据结构涵盖的内容集合结构：集合结构：仅同属一个集合仅同属一个集合线性结构线性结构:一对一（一对一（1:1)树树 结结 构构:一对多（一对多（1:n)图图 结结 构构:多对多多对多 (m:n)非线性非线性线线 性性逻辑结构可细分为逻辑结构可细分为4类：类：答：指数据元素之间的逻辑关系。即从逻辑关系上描述答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它数据，它与与数据的存储无关数据的存储无关，是，是独立于计算机独立于计算机的。的。解释解释1：什么叫数据的逻辑结构？什么叫数据的逻辑结构？（1）S=(D,R)D=a
15、,b,c,d,e,f R=(a,e),(b,c),(c,a),(e,f),(f,d)解解：上述表达式可用图形表示为：上述表达式可用图形表示为：b c a e f d此结构为此结构为线性线性的的。例例：用图形表示下列数据结构，并指出它们是属于线性结：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。构还是非线性结构。课堂练习课堂练习课堂练习（2）S=(D,R)D=di|1i5 R=(di,dj),ij解：上述表达式可用图形表示为：解：上述表达式可用图形表示为：d1 d5 d2 d4 d3该结构是非线性的。该结构是非线性的。解释解释2：什么叫数据的存储结构？：什么叫数据的存储结构？答
16、：存储结构（亦称物理结构），是数据答：存储结构（亦称物理结构），是数据的逻辑结构在计算机存储器内的的逻辑结构在计算机存储器内的表示（或映表示（或映像）像）。它依赖于计算机。它依赖于计算机。“数据元素数据元素”的映像的映像？“关系关系”的映像的映像？用二进制位(bit)的位串表示数据元素(321)10 =(501)8 =(101000001)2 A =(101)8 =(001000001)2数据元素的映象方法：数据元素的映象方法：数据元素的映象方法：从黑客帝国说起数据元素的映象方法：从黑客帝国说起隐喻隐喻黑客帝国讲了个啥事呀？那盗梦空间呢？存储结构可分为存储结构可分为4大类：大类：顺序、链式、索
17、引、散列顺序存储结构借助元素在存储器中的相对位 置来表示数据元素间的逻辑关系链式存储结构借助指示元素存储地址的指针表示数据元素间的逻辑关系关系的映象方法：关系的映象方法：（表示x,y的方法）元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=L0+（i-1)*m顺序存储顺序存储1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 .1400 元素2 1536 .1536 元
18、素3 1346 链式存储链式存储 n答：在数据的逻辑结构上定义的操作算法。答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。它在数据的存储结构上实现。n最常用的数据运算有最常用的数据运算有 5 种：种：插入、删除、修改、查找、排序插入、删除、修改、查找、排序解释解释3：什么是数据的运算？：什么是数据的运算？n数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构1.4.1 数据类型与抽象数据类型的区别？数据类型与抽象数据类型的区别？1.4.2 抽象数据类型如何定义？抽象数据类型如何定义？1.4.3 抽象数据类型如何表示和实现？抽象数据类型如何表示和实现？讨论：讨
19、论：抽象数据类型抽象数据类型和和C伪码伪码是学习数据结构的工具是学习数据结构的工具数据类型高级语言中指数据变量的取值范围及其上可进行的操作的总称例 C语言中，提供int,char,float,double等基本 数据类型，数组、结构体、共用体、枚举 等构造数据类型，还有指针、空(void)类 型等。用户也可用typedef 自己定义数据类型typedef struct int num;char name20;float score;STUDENT;STUDENT stu1,stu2,*p;1.4.1 数据类型与抽象数据类型的区别【例】从键盘输入两个整数，输出它们的和。#include main
20、()int a,b,c,d;/a,b,c,d是四个整型变量，分别是四个整型变量，分别对应于内存中一块对应于内存中一块16bit的区的区域，取值范围为域，取值范围为-215 215-1；printf(输入两个整数：);scanf(%d%d,&a,&b);c=a+b;/”+”和和”-”是是int型变量的操作；型变量的操作；d=a-b;printf(和=%dn,c);1.4.1 数据类型与抽象数据类型的区别数据类型：数据类型：是一个是一个值的集合值的集合和定义在该值上的和定义在该值上的一组操作一组操作的总称。的总称。抽象数据类型：抽象数据类型：由由用户定义用户定义，用以表示，用以表示应用问题的数应用
21、问题的数据模型据模型。它由基本的数据类型构成，并包括一组相关。它由基本的数据类型构成，并包括一组相关的的服务服务（或称操作）（或称操作）它与数据类型实质上是一个概念，其特征是它与数据类型实质上是一个概念，其特征是使用使用与与实现分离实现分离，实行，实行封装封装和和信息隐蔽信息隐蔽（独立于计算机）。（独立于计算机）。但是范畴更广，包括用户在设计软件系统时自己定但是范畴更广，包括用户在设计软件系统时自己定义的数据类型，可用于软件复用。义的数据类型，可用于软件复用。抽象的意义在于数据类型的数学抽象特性。1.4.2 抽象数据类型如何定义抽象数据类型抽象数据类型可以用以下的三元组来表示：可以用以下的三元
22、组来表示：ADT=ADT=（D D，R R，P P）ADTADT抽象数据类型名抽象数据类型名 数据数据对象对象：数据数据关系关系：基本基本操作操作 ：ADT ADT抽象数据类型抽象数据类型名名ADT常用常用定义定义格式格式数据对象数据对象D D上的关系集上的关系集D D上的操作集上的操作集ADT 有两个重要特征:数据抽象数据抽象 用ADT描述程序处理的实体时，强调的是其本质的特征本质的特征、其所能完成的其所能完成的功能功能以及它和外部用户的接口外部用户的接口（即外界外界使用它的方法使用它的方法）。数据封装数据封装 将实体的外部特性和其内部外部特性和其内部实现细节分离实现细节分离，并且对外部用户
23、隐藏对外部用户隐藏其内部实现细节其内部实现细节。例如，例如，抽象数据类型复数复数的定义：数据对象：数据对象：De1,e2e1,e2RealSet 数据关系：数据关系：R1|e1是复数的实数部分|e2 是复数的虚数部分 ADT Complex 基本操作：基本操作：AssignComplex(&Z,v1,v2)操作结果：构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。DestroyComplex(&Z)操作结果：复数Z被销毁。GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。GetImag(Z,&ImagPart)初始条
24、件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2 的 和值。ADT Complex假设:z1和z2是上述定义的复数则 Add(z1,z2,z3)操作的结果z3=z1+z2即为用户企求的结果1.4.3 抽象数据类型如何表示和实现但上机时要用具体语言实现，如但上机时要用具体语言实现，如C C或或C+C+等等n 抽象数据类型可以通过抽象数据类型可以通过固有的固有的数据类型（如整数据类型（如整型、实型、字符型等）来表示和实现。型、实型、字符型等）来表示和实现。注注1：它有些类似：它有些类似
25、C语言中的语言中的结构（结构（struct)类型类型，但增加了，但增加了相关的相关的服务服务。注注2：教材中用：教材中用类类C语言（介于伪码和语言（介于伪码和C语言之间）作为描述语言之间）作为描述工具。其描述语法汇总在教材工具。其描述语法汇总在教材P10-11上。上。思考思考1 1：数据结构的学习依赖于编程语言吗？：数据结构的学习依赖于编程语言吗？思考思考2 2：哪门语言是最好的编程语言？：哪门语言是最好的编程语言？提示：提示：教材中教材中例例1-61-6和例和例1-71-7分别给出了抽象数据类型分别给出了抽象数据类型“三元组三元组”的定义、表示和实现，请自己先试的定义、表示和实现，请自己先试
26、读一遍。读一遍。1.5.1 什么是算法？如何评判算法的好坏？什么是算法？如何评判算法的好坏？1.5.2 时间复杂度和空间复杂度如何表示？时间复杂度和空间复杂度如何表示？1.5.3 计算举例计算举例讨论：讨论：1.5.1 什么是算法？如何评判一个算法的好坏？常用常用时间复杂度时间复杂度来衡量来衡量算法的基本特性：算法的基本特性：算法评价指标：算法评价指标：有穷性、确定性、可行性、有穷性、确定性、可行性、输入、输入、输出输出正确性、可读性、健壮性、正确性、可读性、健壮性、效率效率与与低存储量低存储量需求需求常用常用空间复杂度空间复杂度来衡量来衡量程序设计的实质：好算法好结构程序设计的实质：好算法好
27、结构算法算法是对特定问题求解步骤的一种描述，它是指令的是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。有限序列，是一系列输入转换为输出的计算步骤。4 4个层次个层次例1.4、例1.5例1.4 一个不是算法的例子(1)begin(2)n=0(3)n=n+1(4)repeat(3)(5)end例1.5 一个不超过100次计数的算法(1)begin(2)n=0(3)n=n+1(4)if n=100 do(5),else repeat(3)(5)output n(6)end用依据该算法编制的程序在计算机上执行所消耗的时间来度量。算法效率：算法效率：1.事后统计：利
28、用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分。缺点：必须先运行依据算法编制的程序。所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣。2.事前分析估计：一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略 问题的规模 程序语言 编译程序产生机器代码质量 机器执行指令速度n设解决一个问题的规模为n（比如排序问题中，n表示待排序元素的个数；在矩阵运算中，n表示矩阵的阶数；在图的遍历中，n表示图中的顶点数），那么算法的时间量度可记为T(n).当n不断变化时,T(n)也会不断变化,但有时我们想知道它变化时呈什么规律.n一般情况下,T(n)与算法中简
29、单操作执行次数之和f(n)成正比。注：注：O（）为渐近符号（）为渐近符号，表示表示T(n)与f(n)是同数量级函数。可记作：T(n)=O(f(n)1.5.2 时间复杂度和空间复杂度如何表示？3n+2=O(n)因为因为 3n+2 4n for n 26*2n+n2=O(2n)因为因为6*2n+n2 7*2n for n 4例：例：渐进符号渐进符号（O）的形式定义：）的形式定义：当且仅当存在一个正当且仅当存在一个正的常数的常数 M M，使得对所有的，使得对所有的 n n n n0 0 ，有，有|x|x(n)(n)|Mf|Mf(n)(n)|，则：，则：x x(n)=(n)=O O(f f(n)(n)
30、什么是同数量级函数？什么是同数量级函数？若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。例如，若T(n)=n(n+1)/2,则有 1/4T(n)/n21，故可以说，辅助函数f(n)=n2是(n)的同数量级函数。注：注：空间复杂度空间复杂度S(n)按数量级递增顺序也与上表类似。按数量级递增顺序也与上表类似。复杂度高复杂度高复杂度低复杂度低时间复杂度时间复杂度T(n)按数量级递增顺序为：按数量级递增顺序为：1.5.2 时间复杂度和空间复杂度如何表示？多项式阶多项式阶1.5.3 计算举例该算法的运行时间由程序中所有该
31、算法的运行时间由程序中所有简单语句简单语句的的频度（频度（即即该语句重复执行的次数）该语句重复执行的次数）之和之和构成。构成。解：解：分析：分析：显然，语句显然，语句的频度是的频度是1。设语句。设语句2的频度是的频度是g(n)，则有：，则有：算法的时间复杂度由算法的时间复杂度由嵌套最深层语句的频度嵌套最深层语句的频度决定决定例例1 1：分析以下程序段的时间复杂度。：分析以下程序段的时间复杂度。i=1;while(i=n)i=i*2;即即g(n)log2n，取最大值取最大值g(n)=log2n所以该程序段的时间复杂度所以该程序段的时间复杂度T(n)=1+g(n)=1+log2n=O(log2n)
32、例2 分析以下程序段的时间复杂度for(i=1;in;i+)y=y+1;for(j=0;j=(2*n);j+)x+;/*1 */*2 */分析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。语句1的频度是：n-1语句2的频度是：12)12)(1(2nnnn则该程序段的时间复杂度：T(n)=)(2222nOn 空间复杂度空间复杂度 与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:l S(n)=O(f(n)l 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。n 注意：算法的所有性
33、能之间都存在着或多或少的相互影响，因此，当设计一个算法，特别是大型算法时，要综合考虑算法的各项性能、算法的使用频率、算法处理的数据量的大小、算法描述语言的特性及算法运行的机器系统环境等各方面因素，才能设计出比较好的算法。n时间和空间复杂性之间的关系：用空间来换时间，这是并发信号处理的核心思想。本章小结本章小结数据结构课程数据结构课程 数据结构算法程序，涉及数数据结构算法程序，涉及数学、计算机硬件和软件。学、计算机硬件和软件。数据结构定义数据结构定义指互相有关联的数据元素的集合，指互相有关联的数据元素的集合，可用可用data_Structure=(D,R)表示。表示。数据结构内容数据结构内容数据的逻辑结构、存储结构和基数据的逻辑结构、存储结构和基本运算本运算 数据结构学习工具数据结构学习工具抽象数据类型和伪码（类抽象数据类型和伪码（类C）算法效率指标算法效率指标时间效率和空间效率时间效率和空间效率第第1章结束章结束
