《《数据结构介绍》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构介绍》PPT课件.ppt（51页珍藏版）》请在金锄头文库上搜索。
1、返回返回数数 据据 结结 构构(Data Structure)任课教师：任课教师： 赵少卡赵少卡 E-MAIL: 数计系数计系20122012级计算机科学与技术、网络工程专业级计算机科学与技术、网络工程专业1返回返回课程性质：专业核心基础课课程性质：专业核心基础课教材教材: 严严蔚蔚敏敏、吴吴伟伟民民. 数数据据结结构构 (C语语言言版版).北北京京:清华大学出版社清华大学出版社,2011. 1981年初稿，使用面最广年初稿，使用面最广周学时：周学时：4（理论授课）（理论授课）+ 2（上机实践）（上机实践）考考核核：平平时时成成绩绩（作作业业、考考勤勤）20% +期期中成绩中成绩20% +期末
2、成绩期末成绩60% 数据结构数据结构数据库数据库人工智能人工智能软件工程软件工程操作系统操作系统编译原理编译原理算法设计与分析算法设计与分析离散数学离散数学语言程序设计语言程序设计高等数学高等数学2返回返回保持课堂安静，头脑清醒，思维活跃保持课堂安静，头脑清醒，思维活跃课后及时复习巩固课后及时复习巩固认真、独立、按时完成并提交作业认真、独立、按时完成并提交作业多思考多动手，重视上机实践多思考多动手，重视上机实践课程要求3返回返回讲授篇章讲授篇章第第1 1章章 绪论绪论第第7 7章章 图图第第2 2章章 线性表线性表 第第9 9章章 查找查找第第3 3章章 栈和队列栈和队列第第6 6章章 树和二
3、叉树树和二叉树第第10 10章章 内部排序内部排序5返回返回证明正确性证明正确性分析算法分析算法程序程序设计设计理解问题理解问题选择数据结构、选择数据结构、算法设计策略算法设计策略问题数学化问题数学化设计算法设计算法第第 1 章章 绪绪 论论 问题求解问题求解(Problem Solving)(Problem Solving)：6返回返回计算机求解问题的分类计算机求解问题的分类数数值值计计算算( (科科学学运运算算) ): :解解方方程程( (组组) )、 函函数数求求值值、 概率统计等。概率统计等。 应应用用：天天气气预预报报( (环环流流模模式式方方程程) )、结结构构静静力力分分析析（线
4、线性性代代数数方方程程组组）、水水库库大大坝坝的的应应力力计算、预报人口增长等。计算、预报人口增长等。非数值计算非数值计算：字符、表格、图像、声音等。：字符、表格、图像、声音等。7返回返回基本概念和术语基本概念和术语数数据据：计计算算机机程程序序处处理理的的符符号号的的总总称称，包包含含整整型型、实实型型、布布尔尔型型、图图象象、字字符符、声声音音等等一一切切可以输入到计算机中的符号集合可以输入到计算机中的符号集合。数数据据元元素素：数数据据的的基基本本单单位位（数数据据中中的的一一个个“个体个体”），通常作为一个整体进行处理。），通常作为一个整体进行处理。数数据据项项：数数据据的的具具有有意
5、意义义的的不不可可分分割割的的最最小小单单位位。一个数据元素可以由若干个数据项构成。一个数据元素可以由若干个数据项构成。数数据据元元素素数据项数据项. . . . . . 福州福州1993.111993.11福建福建男男 张三张三12101 住住 址址 出生年月出生年月 籍籍 贯贯性性 别别 姓姓 名名 学学 号号 8返回返回 数据对象数据对象：性质相同的：性质相同的数据元素数据元素的集合。的集合。如：整数数据对象如：整数数据对象 N = 0, 1, 2, （无限集）（无限集） 字母字符数据对象字母字符数据对象C= A, B, C, Z （有限集）（有限集）因此：因此： 数据元素是数据的一个数
6、据元素是数据的一个个体个体； 数据对象是数据的一个数据对象是数据的一个子集子集。9返回返回 例：例：a1,a2,a3,a4,a5,a6存在次序为：存在次序为：（1）| i=1，2，3，4，5（2）Row=, , Col =, , 所所谓谓结结构构就就是是数数据据元元素素之之间间的的关关系系，即即描描述述数据元素之间的运算与运算规则。数据元素之间的运算与运算规则。数数据据结结构构：相相互互间间存存在在一一种种或或多多种种特特定定关关系系的的数据元素数据元素的集合。的集合。10返回返回数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 （物理结构、映像）（物理结构、映像） 数据的运算：数据
7、的运算：查找、排序、插入、删除、修改等查找、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储链式存储链式存储线性表线性表栈栈队列队列树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面：集合结构集合结构串串索引存储索引存储散列存储散列存储11返回返回主要逻辑结构举例主要逻辑结构举例v集合集合：其中的数据元素：其中的数据元素之间除了之间除了“属于同一个集属于同一个集合合”的关系以外，别无其的关系以外，别无其他关系。他关系。v线性结构线性结构：其中的数据：其中的数据元素之间存在元素之间存在一对一一对一的关的关系。系。v树型结构树型结构：其中的数据
8、：其中的数据元素之间存在元素之间存在一对多一对多的关的关系。系。v图状结构图状结构（网状结构）：（网状结构）：其中的数据元素之间存在其中的数据元素之间存在多对多多对多的关系。的关系。 12返回返回v例例1 书目自动检索系统书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表13返回返回v例例2 人机对人机对弈弈问题问题树.14返回返回v例例3 多叉路口交通灯管理问题多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图有连线的节点用不同的颜有连线的节点用不同的颜色标记色标记, , 表示不能同时
9、通行。表示不能同时通行。要求使用的颜色数尽可能要求使用的颜色数尽可能少少, , 以使减少等待时间。以使减少等待时间。15返回返回逻辑结构与存储结构逻辑结构与存储结构逻辑结构逻辑结构: 数据元素间的逻辑关系，与数据元素的相数据元素间的逻辑关系，与数据元素的相对位置对位置无关无关。存储结构存储结构: 逻辑结构在计算机存储器中的表示，如：逻辑结构在计算机存储器中的表示，如：数据的逻辑结构与存储结构密切相关：算法设计 逻辑结构算法实现 存储结构顺序存储结构借助元素在存储器中的相对位置相对位置来表示 数据元素间的逻辑关系链式存储结构借助指示元素存储地址的指针指针表示数据 元素间的逻辑关系16返回返回元素
10、元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo +（i-1)*m顺序存储结构顺序存储结构17返回返回1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址存储地址 存储内容存储内容 指针指针 13451345 元素元素1 1 14001400 13461346 元素元素4 4 . . . 14001400 元素元素2 2 15361536 . . . 15361536 元素元素3 3 13461346 链式存储结构链式存储结构 h
11、18返回返回数据类型与抽象数据类型数据类型与抽象数据类型数据类型数据类型（Data Type）：值的集合以及定值的集合以及定义在这个集合上的一组操作义在这个集合上的一组操作。数据类型分类：数据类型分类：（1）原子类型：每个数据都无法再分割。（整）原子类型：每个数据都无法再分割。（整型、实型、字符型等）型、实型、字符型等）（2）结构类型：结构类型中的数据可以分解为）结构类型：结构类型中的数据可以分解为若干原子类型或结构类型数据。（数组、记录、若干原子类型或结构类型数据。（数组、记录、结构体、联合体、串、文件等）结构体、联合体、串、文件等）19返回返回 抽抽象象数数据据类类型型(Abstract
12、Data Type ，ADT):数数学学模模型型以以及及定定义义在在该该模模型型上上的的一一组组操操作作，与与其其在计算机中的表示和实现无关。在计算机中的表示和实现无关。 例例如如：矩矩阵阵 + 求求转转置置、加加、乘乘、求求逆逆、求求特特征征值等操作构成一个值等操作构成一个矩阵的抽象数据类型矩阵的抽象数据类型。 ADT 可用三元组表示：（可用三元组表示：（D,R,P）D 数据对象数据对象 R D上的关系的有限集上的关系的有限集 P 对对D的基本操作集的基本操作集20返回返回抽象数据类型的抽象数据类型的定义定义ADT抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义数据对象的定义
13、 数据关系：数据关系：数据关系的定义数据关系的定义 基本操作：基本操作： 基本操作名（参数表）基本操作名（参数表） 初始条件：初始条件描述初始条件：初始条件描述 操作结果：操作结果描述操作结果：操作结果描述ADT抽象数据类型名抽象数据类型名在在定义定义抽象数据类型中的数据部分和操作部分时，要抽象数据类型中的数据部分和操作部分时，要求只定义数据的逻辑结构和操作说明，不考虑数据的求只定义数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现。存储结构和操作的具体实现。21返回返回 基基本本操操作作有有两两种种参参数数：赋赋值值参参数数只只为为操操作作提提供供输输入入值值；引引用用参参数数以
14、以&打打头头，除除可可提提供供输输入入值值外外，还还将将返返回回操操作结果作结果。 “初初始始条条件件”描描述述了了操操作作执执行行之之前前数数据据结结构构和和参参数数应应满满足足的的条条件件，若若不不满满足足，则则操操作作失失败败，并并返返回回相相应应出出错信息。错信息。 “操操作作结结果果”说说明明了了操操作作正正常常完完成成之之后后，数数据据结结构构的的变变化化状状况况和和应应返返回回的的结结果果。若若初初始始条条件件为为空空，则则省省略略之。之。22返回返回抽象数据类型三元组的定义抽象数据类型三元组的定义ADT Tripletv 数数据据对对象象：D = e1,e2,e3 | e1,e
15、2,e3ElemsetElemset( (定定义义了了关关系系运运算算的某个集合的某个集合)v 数据关系：数据关系：R1 = e1,e2，e2,e3v 基本操作基本操作P：InitTriplet(&T,v1,v2,v3) 初始条件初始条件: 操操作作结结果果: 构构造造三三元元组组T,元元素素e1,e2和和e3分分别别被被赋赋予予参参数数v1,v2和和v3的值。的值。DestroyTriplet(&T) 初始条件初始条件: 三元组三元组T已经存在。已经存在。 操作结果操作结果: 销毁三元组销毁三元组T。Get(T,i,&e) 初始条件初始条件: 三元组三元组T已经存在已经存在,1=i=3。 操
16、作结果操作结果: 用用e返回三元组返回三元组T的第的第i个元素。个元素。23返回返回 Put(&T,i,e) 初始条件初始条件: 三元组三元组T已经存在已经存在,1=i0） 操作结果：构造一个圆操作结果：构造一个圆r，使其半径为，使其半径为c DestroyCircle(&r) 初始条件：圆初始条件：圆r已存在已存在 操作结果：撤消圆操作结果：撤消圆r（使其半径为（使其半径为0） AreaCircle(r，&A) 初始条件：圆初始条件：圆r已存在已存在 操作结果：用操作结果：用A返回圆的面积返回圆的面积 CircumferenceCircle(r，&C) 初始条件：圆初始条件：圆r已存在已存在
17、 操作结果：用操作结果：用C返回圆的周长返回圆的周长 ADT Circle25返回返回抽象数据类型的抽象数据类型的表示与实现表示与实现类类C语言语言（对（对C语言作了扩充和修改）表示。语言作了扩充和修改）表示。 如：预定义常量和类型如：预定义常量和类型 define TRUE 1define FALSE 0define OK 1define ERROR 0define INFEASIBLE -1define OVERFLOW -2 typedef int Status；26返回返回三元组基本操作实现三元组基本操作实现-举例举例Status InitTriplet(Triplet &T, Ele
18、mType v1, ElemType v2, ElemType v3) / 构造三元组构造三元组T,元素元素e1,e2和和e3分别被赋予参数分别被赋予参数v1,v2和和v3的值。的值。 T=(ElemType *)malloc(3*sizeof(ElemType); if(!T) exit(OVERFLOW); T0=V1; T1=V2; T2=V3; return OK;/InitTriplet27返回返回三元组基本操作实现三元组基本操作实现-举例举例Status Get(Triple T, int i, Elemtype &e) / 1=i=3，用，用e返回三元组返回三元组T的第的第i个元
19、素。个元素。 if (i3) return ERROR; e=Ti-1; return OK;/Get28返回返回 抽象数据类型（抽象数据类型（ADT）明确地把数据模型与该模型上的）明确地把数据模型与该模型上的运算紧密地联系起来。运算紧密地联系起来。从使用的角度看，从使用的角度看，ADT隐藏了所有使用者不关心的实现隐藏了所有使用者不关心的实现细节，对用户透明（提供接口），使程序模块的细节，对用户透明（提供接口），使程序模块的实现与实现与使用分离使用分离，从而能够独立地考虑模块的外部界面、内部，从而能够独立地考虑模块的外部界面、内部算法和数据结构的实现，做到了信息隐蔽与数据封装。算法和数据结构的
20、实现，做到了信息隐蔽与数据封装。 Abstract Data Type (ADT)user1user2usern.实现1实现2实现330返回返回算法与程序算法与程序算法算法（Algorithm）是对特定问题求解步骤的一种是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法的描述工具有：一个或多个操作。算法的描述工具有： （1） 自然语言自然语言 （2） 程序设计语言程序设计语言 （3） 流程图（框图）流程图（框图） （4） 伪码语言：是一种包括高级程序设计语言伪码语言：是一种包括高级程序设计语言的三种基本结构（顺序、
21、选择、循环）和自然语的三种基本结构（顺序、选择、循环）和自然语言成分的言成分的“面向读者面向读者”的语言。的语言。程序程序是用某种程序设计语言对算法的具体实现。是用某种程序设计语言对算法的具体实现。如果一个算法采用机器可执行的语言来书写，那如果一个算法采用机器可执行的语言来书写，那么它就是一个程序。么它就是一个程序。31返回返回算法的算法的5个特征个特征(1)有穷性有穷性：在有限步：在有限步(或有限时间或有限时间)之后算法终止。之后算法终止。 例：例：void suanfa1( ) int i,s=0； for (i=0；i=0；i+) s+； (2)确定性确定性：无二义性。：无二义性。 例：
22、例： x=5；y=10； z=x+y； printf(%d,%d,%d ,x,y,z)； x+y 解释为：解释为：x + (+y)？还是还是 (x+)+ y？ 32返回返回 (3)可行性可行性(正确性正确性)：可以在计算机上实现。：可以在计算机上实现。 for( i=1,s=0；i1000000000000；+i) s+；？；？ (4)输入输入：有：有0个（算法本身确定了初始条件）个（算法本身确定了初始条件） 或多个输入量。或多个输入量。 (5)输出输出：至少有一个输出量。：至少有一个输出量。33返回返回算法设计要求算法设计要求如何设计一个如何设计一个“好好”的算法的算法 (1)(1)正确性正
23、确性（4 4个层次）个层次） a.a.无语法错误；无语法错误； b.b.对对n n组输入产生正确结果；组输入产生正确结果； c.c.对特殊输入产生正确结果；对特殊输入产生正确结果； d.d.对所有输入产生正确结果。对所有输入产生正确结果。 (2)(2)可读性可读性：“算法主要是为了人的阅读与交流算法主要是为了人的阅读与交流”。 (3)(3)健壮性（鲁棒性）健壮性（鲁棒性） scanf(%d,&x)； y/=x；？；？ (4)(4)高效与低存储量高效与低存储量（如何度量？能（如何度量？能使用使用“绝对时间单位绝对时间单位”衡量算衡量算法效率吗？法效率吗？） 不能，因为同一个算法用不同的语言、不同
24、的编译程序、在不不能，因为同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同。同的计算机上运行，效率均不同。34返回返回算法效率的度量算法效率的度量(主要是度量程序的执行时间主要是度量程序的执行时间)通常有两种方法：通常有两种方法：(1) 事后统计法（缺点：事后统计法（缺点：a.必须执行程序，必须执行程序，b.软硬软硬件环境因素易掩盖算法本质）；件环境因素易掩盖算法本质）；(2) 事前分析估算法（根据与算法相关的因素估事前分析估算法（根据与算法相关的因素估算算法的执行工作量）。算算法的执行工作量）。35返回返回算法效率的度量算法效率的度量时间复杂度时间复杂度 算法的时间复
25、杂度是指：算法算法的时间复杂度是指：算法(或程序或程序)中中基本操作基本操作(或语句或语句)重重复执行的复执行的次数次数的总和。的总和。 设设n为求解的问题的规模，基本操作为求解的问题的规模，基本操作(或语句或语句)执行次数总和称执行次数总和称为为语句频度语句频度，记作，记作f(n)。 算法的时间量度算法的时间量度T(n)是随算法计算量是随算法计算量n而增长的趋势而增长的趋势(极限极限) 。如果存在正的常数。如果存在正的常数M和和n0，当问题的规模，当问题的规模nn0后，后，T(n)Mf(n)，那么该算法的时间复杂度，那么该算法的时间复杂度 T(n) =O(f(n) 表示随着问题规模表示随着问
26、题规模n n的的增大，算法运行所需时间增大，算法运行所需时间的增长率与的增长率与f(nf(n) )的增长率的增长率相同（在渐进意义下的阶数）。相同（在渐进意义下的阶数）。36返回返回例例1： int s； scanf(%d,&s)； s+； printf(%d,s)； 其中：语句频度为：其中：语句频度为：f(n)=3 时间复杂度为：时间复杂度为：T(n)=O(f(n)=O(1) O(1)称成为常量阶称成为常量阶/常量数量级常量数量级又如：又如：交换变量交换变量x和和y中的内容，中的内容，temp=x; x=y; y=temp; 时间复杂度也为时间复杂度也为O(1)。37返回返回例例2： voi
27、d sum(int a,int n) int s=0,i； / 1次次 for(i=0；in；i+) / n次次(严格为严格为2*(n+1)次）次） s=s+ai； / n次次 printf(%d,s)； / 1次次 其中其中：语句频度为：语句频度为：f(n)=1+n+n+1 时间复杂度为：时间复杂度为：T(n)=O(f(n)=O(2n+2)=O(n) O(n)称成为线性阶称成为线性阶/线性数量级线性数量级定理：定理：若若A(n)=amnm +a m-1nm-1 +a1n+a0是一个是一个m次多项式，次多项式， 则则A(n)=O(nm)。38返回返回例例3： 1. void sum (int
28、m,int n) 2. int i,j,s=0； / 1次次 3. for(i=1；i=m；i+) / m次次 4. for(j=1；j=n；j+) / m*n次次 5. s+； / m*n次次 6. printf(%d,s)； / m次次 7. 8. 其中其中: f(m,n)=1+m+2*m*n+m=2mn+2m+1 当当m=n时，时，f(n)=2n2+2n+1 T(n)=O(f(n)=O(2n2+2n+1)=O(n2) O(n2 ) 称成为平方阶称成为平方阶/平方数量级平方数量级39返回返回 1. void sum(int n) 2. int i,j,s=0； / 1次次 3. for(i
29、=1；i=n；i+) / n次次 4. for(j=1；j=i；j+) / ?次次 5. s+； / ?次次 6. printf(%d,s)； / n次次 7. 8. 其中：第其中：第4行的次数为行的次数为 1+2+.+n=n(1+n)/2 第第5行的次数为行的次数为 1+2+.+n=n(1+n)/2 f(n)=1+n+n(n+1)+n=n2+3n+1 T(n)=O(f(n)=O(n2)例例4：40返回返回例例5：1. void bubble1(int a,int n) 2. int i,j,temp； 3. for(i=0；in-1；i+) / n-1 次次 4. for(j=0；jaj+1
30、) / n(n-1)/2次次 6. temp=aj； / 0 或或n(n-1)/2次次 7. aj=aj+1； / 0 或或n(n-1)/2次次 8. aj+1=temp； / 0 或或n(n-1)/2次次 9. 10. for(i=0；i=1 & change；i-) /1 或或n-13. change=FALSE； /1 或或n-14. for(j=0；jaj+1) /n-1或或n*(n-1)/26. aj aj+1； /0或或n*(n-1)/27. change=TRUE； /0或或n*(n-1)/28. 9. 10. 在最好情况下：在最好情况下： T最好最好(n)=O(f最好最好(n)
31、= O(n) 在最坏情况下：在最坏情况下： T最坏最坏(n)=O(f最坏最坏(n)= O(n2)算法时间复杂度：算法时间复杂度： T(n)= T最坏最坏(n)= O(n2)课后思考：选择排序的时间复杂度。课后思考：选择排序的时间复杂度。43返回返回小结：小结：T(n) 的计算方法的计算方法（1 1）找出基本操作）找出基本操作( (若存在循环，一般取最深层若存在循环，一般取最深层循环内的语句所描述的操作循环内的语句所描述的操作) )，确定问题规模，确定问题规模n n；（2 2）计算出关于）计算出关于n n的语句频度函数的语句频度函数f(nf(n) )；（3 3）使用）使用“掐头去尾占高枝儿掐头去
32、尾占高枝儿”等方法得出等方法得出T(nT(n) )。44返回返回 思考：思考：int SequenceSearch(int a ,int n,int key) for(int i=0;in;i+) if(ai=key) return i； return -1；最好情况：最好情况：O(1)最坏情况：最坏情况：O(n)平均时间复杂度为平均时间复杂度为:O(n)45返回返回例例 6 ：fact(int n) if(n=1) return 1; else return (n*fact(n-1); O(1) （n1）T(n)=O(1)+T(n-1) =2*O(1)+T(n-2) =(n-1)*O(1)+
33、T(1) =n*O(1) =O(n)T(n)=利用递归跟踪或递推方程利用递归跟踪或递推方程46返回返回例例 7：设存在递归关系：设存在递归关系: 0 （n=1） T(n-1)+n-1 （n1） 分析其时间复杂度。分析其时间复杂度。 T(n)= T(n-1)+(n-1) =T(n-2)+(n-2)+(n-1) =T(n-3)+(n-3)+(n-2) +(n-1) =(T(1)+1)+2+(n-1) =0+1+2+(n-1) = n(n-1)/2 =O(n2)T(n)=47返回返回例例 8： i=1;while(i1)：2n , 3nnc(c1)：n3, n2nlog2 nnr(0r1.0)log
34、2 ncO(1)O(logn)O(n)O(nloglogn)O(nlogn)O(n2)O(n3)O(2n)O(n!)O(nn)49返回返回常用的时间复杂度频率计数常用的时间复杂度频率计数loglog2 2n nn nnlognlog2 2n nn n2 2n n3 32 2n n思考：这思考：这说明了什说明了什么？么？0 01 10 01 11 12 21 12 22 24 48 84 42 24 48 81616646416163 38 8242464645125122562564 4161664642562565096509665536655365 53232160160102410243
35、27683276821474836482147483648 50返回返回算法效率的度量算法效率的度量空间复杂度空间复杂度一般情况下，算法的复杂度指的是算法的一般情况下，算法的复杂度指的是算法的时间复杂度时间复杂度。算法的空间复杂度：算法的空间复杂度：S(n)=O(f(n) 其中其中n为问题的规模为问题的规模(或大小或大小)。表示随着问题规模。表示随着问题规模n的增的增大，算法运行所需存储量的增长率与大，算法运行所需存储量的增长率与f(n)的的增长率相同增长率相同。 若所需额外空间相对于输入数据量来说是常数，则称此若所需额外空间相对于输入数据量来说是常数，则称此算法为算法为原地工作（就地工作）原地工作（就地工作）。 若所需存储量依赖于特定的输入，则通常按若所需存储量依赖于特定的输入，则通常按最坏情况最坏情况考考虑。虑。有时候，可以用空间换时间，如判断给定的一系列年份是有时候，可以用空间换时间，如判断给定的一系列年份是否是闰年（两种做法）。否是闰年（两种做法）。51
