logo资料库

数据结构与算法(严蔚敏).pdf

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：1.76M 资料格式：pdf 举报 版权申诉
第1页 / 共136页
第2页 / 共136页
第3页 / 共136页
第4页 / 共136页
第5页 / 共136页
第6页 / 共136页
第7页 / 共136页
第8页 / 共136页
资料共136页，剩余部分请下载后查看
    2018/11/12 算法与数据结构 教材：《数据结构(C语言版)》。严蔚敏，吴伟民 编 著。清华大学出版社。 参考文献： 1 《数据结构》 。张选平，雷咏梅 编， 严蔚敏 审。 机械工业出版社。 2 《数据结构与算法分析》。Clifford A. Shaffer著， 张 铭，刘晓丹 译。电子工业出版社。 3 《数据结构习题与解析(C语实言版)》。李春葆。 清华大学出版社。 4 《数据结构与算法》。夏克俭 编著。国防工业出 版社。 1.1 数据结构及其概念 《算法与数据结构》是计算机科学中的一门综合性 专业基础课。是介于数学、计算机硬件、计算机软件三 者之间的一门核心课程，不仅是一般程序设计的基础， 而且是设计和实现编译程序、操作系统、数据库系统及 其他系统程序和大型应用程序的重要基础。 第1章 绪 论 目前，计算机已深入到社会生活的各个领域，其应 用已不再仅仅局限于科学计算，而更多的是用于控制， 管理及数据处理等非数值计算领域。计算机是一门研究 用计算机进行信息表示和处理的科学。这里面涉及到两 个问题：信息的表示，信息的处理。 信息的表示和组织又直接关系到处理信息的程序的 效率。随着应用问题的不断复杂，导致信息量剧增与信 息范围的拓宽，使许多系统程序和应用程序的规模很大， 结构又相当复杂。因此，必须分析待处理问题中的对象 的特征及各对象之间存在的关系，这就是数据结构这门 课所要研究的问题。 1.1.1 数据结构的例子 例1：电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其 相应的电话号码，假定按如下形式安排：(a1, b1)，(a2, b2)，…(an, bn)，其中ai, bi(i=1，2…n) 分别表示某人的 名字和电话号码。 本问题是一种典型的表格问题。如 表1-1，数据与数据成简单的一对一的线性关系。 姓名 陈海 李四锋 电话号码 13612345588 13056112345 。。。 。。。 表1-1 线性表结构 计算机求解问题的一般步骤 编写解决实际问题的程序的一般过程： • 如何用数据形式描述问题?—即由问题抽象出一个适当的数学模型; • 问题所涉及的数据量大小及数据之间的关系; • 如何在计算机中存储数据及体现数据之间的关系? • 处理问题时需要对数据作何种运算? • 所编写的程序的性能是否良好? 上面所列举的问题基本上由数据结构这门课程来回答。 例2：磁盘目录文件系统 磁盘根目录下有很多子目录及 文件，每个子目录里又可以包含 多个子目录及文件，但每个子目 录只有一个父目录，依此类推： 本问题是一种典型的树型结 构问题，如图1-1 ，数据与数据 成一对多的关系，是一种典型的 非线性关系结构—树形结构。 图1-1 树形结构 1
    2018/11/12 例3：交通网络图 从一个地方到另外一个地方可以有多条路径。本问 题是一种典型的网状结构问题，数据与数据成多对多的 关系，是一种非线性关系结构。 佛山 广州 中山 珠海 惠州 东莞 深圳 图1-2 网状结构 图1-3 四类基本结构图 1.1.3 数据结构的形式定义 数据结构的形式定义是一个二元组： Data-Structure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有限集。 例2：设数据逻辑结构B=（K，R） K={k1, k2, …, k9} R={ ，，，，，，，，，， } 画出这逻辑结构的图示，并确定那些是起点，那些是终点 1.1.2 基本概念和术语 数据(Data) ：是客观事物的符号表示。在计算机科学 中指的是所有能输入到计算机中并被计算机程序处理的 符号的总称。 数据元素(Data Element) ：是数据的基本单位，在程 序中通常作为一个整体来进行考虑和处理。 一个数据元素可由若干个数据项(Data Item)组成。数 据项是数据的不可分割的最小单位。数据项是对客观事 物某一方面特性的数据描述。 数据对象(Data Object)：是性质相同的数据元素的集 合，是数据的一个子集。如字符集合C={‘A’,’B’,’C,…} 。 数据元素之间的关系可以是元素之间代表某种含义 的自然关系，也可以是为处理问题方便而人为定义的 关系，这种自然或人为定义的 “关系”称为数据元素 之间的逻辑关系，相应的结构称为逻辑结构。 1.1.4 数据结构的存储方式 数据结构在计算机内存中的存储包括数据元素的存 储和元素之间的关系的表示。 元素之间的关系在计算机中有两种不同的表示方法： 顺序表示和非顺序表示。由此得出两种不同的存储结构： 顺序存储结构和链式存储结构。 • 顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑 结构(关系)。 数据结构(Data Structure)：是指相互之间具有(存在) 一定联系(关系)的数据元素的集合。元素之间的相互联 系(关系)称为逻辑结构。数据元素之间的逻辑结构有四 种基本类型，如图1-3所示。 ① 集合：结构中的数据元素除了“同属于一个集合” 外，没有其它关系。 ② 线性结构：结构中的数据元素之间存在一对一的 关系。 ③ 树型结构：结构中的数据元素之间存在一对多的 关系。 ④ 图状结构或网状结构：结构中的数据元素之间存 在多对多的关系。 • 链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针 (pointer )，用该指针来表示数据元素之间的逻辑结构(关系)。 例：设有数据集合A={3.0,2.3,5.0,-8.5,11.0} ，两种不同的 存储结构。 • 顺序结构：数据元素存放的地址是连续的； • 链式结构：数据元素存放的地址是否连续没有要求。 数据的逻辑结构和物理结构是密不可分的两个方面， 一个算法的设计取决于所选定的逻辑结构，而算法的实 现依赖于所采用的存储结构。 在C语言中，用一维数组表示顺序存储结构；用结构 体类型表示链式存储结构。 2
    2018/11/12 数据结构的三个组成部分： 逻辑结构： 数据元素之间逻辑关系的描述 D_S=（D，S） 存储结构： 数据元素在计算机中的存储及其逻辑 关系的表现称为数据的存储结构或物理结构。 数据操作： 对数据要进行的运算。 本课程中将要讨论的三种逻辑结构及其采用的存储 结构如图1-4所示。 1.1.6 数据结构的运算 数据结构的主要运算包括： ⑴ 建立(Create)一个数据结构； ⑵ 消除(Destroy)一个数据结构； ⑶ 从一个数据结构中删除(Delete)一个数据元素； ⑷ 把一个数据元素插入(Insert)到一个数据结构中； ⑸ 对一个数据结构进行访问(Access)； ⑹ 对一个数据结构(中的数据元素)进行修改(Modify)； ⑺ 对一个数据结构进行排序(Sort)； ⑻ 对一个数据结构进行查找(Search)。 逻辑结构 线性表 树 图 物理结构 顺序存储结构 链式存储结构 复合存储结构 图1-4 逻辑结构与所采用的存储结构 数据的逻辑结构 线性结构 非线性结构 受限线性表 线性表推广 集合 树形结构 图状结构 一般线性表 栈和队列 串 数组 广义表 一般树 二叉树 有向图 无向图 图1-5 数据逻辑结构层次关系图 1.2 抽象数据类型 抽象数据类型(Abstract Data Type ，简称ADT)：是指 一个数学模型以及定义在该模型上的一组操作。 ADT的定义仅是一组逻辑特性描述， 与其在计算机 内的表示和实现无关。因此，不论ADT的内部结构如何 变化，只要其数学特性不变，都不影响其外部使用。 ADT的形式化定义是三元组：ADT=(D，S，P) 其中：D是数据对象，S是D上的关系集，P是对D的基本 操作集。 1.1.5 数据类型 数据类型(Data Type)：指的是一个值的集合和定义 在该值集上的一组操作的总称。 数据类型是和数据结构密切相关的一个概念。 在C 语言中数据类型有：基本类型和构造类型。 数据结构不同于数据类型，也不同于数据对象，它 不仅要描述数据类型的数据对象，而且要描述数据对象 各元素之间的相互关系。 ADT的一般定义形式是： ADT <抽象数据类型名>{ 数据对象： <数据对象的定义> 数据关系： <数据关系的定义> 基本操作： <基本操作的定义> } ADT <抽象数据类型名> • 其中数据对象和数据关系的定义用伪码描述。 • 基本操作的定义是： <基本操作名>(<参数表>) 初始条件： <初始条件描述> 操作结果： <操作结果描述> 3
    2018/11/12 – 初始条件：描述操作执行之前数据结构和参数应 满足的条件;若不满足，则操作失败，返回相应的出 错信息。 – 操作结果：描述操作正常完成之后，数据结构的 变化状况和 应返回的结果。 1.3.2 算法设计的要求 评价一个好的算法有以下几个标准 ① 正确性(Correctness )： 算法应满足具体问题的需求。 ② 可读性(Readability)： 算法应容易供人阅读和交流。可读性好的算法有助于对 算法的理解和修改。 ③ 健壮性(Robustness)： 算法应具有容错处理。当输入非法或错误数据时，算法 应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。 ④ 通用性(Generality)： 算法应具有一般性 ，即算法的处理结果对于一般的数据 集合都成立。 1.3 算法分析初步 1.3.1 算法 算法(Algorithm)：是对特定问题求解方法(步骤)的一种描 述，是指令的有限序列，其中每一条指令表示一个或多 个操作。 算法具有以下五个特性 ① 有穷性： 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内 完成。 ② 确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一 个入口和一个出口。 ③ 可行性： 一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运 算执行有限次来实现。 ⑤ 效率与存储量需求： 效率指的是算法执行的时 间；存储量需求指算法执行过程中所需要的最大存 储空间。一般地，这两者与问题的规模有关。 1.3.3 算法效率的度量 算法执行时间需通过依据该算法编制的程序在计算 机上运行所消耗的时间来度量。其方法通常有两种： 事后统计：计算机内部进行执行时间和实际占用空间的 统计。 问题：必须先运行依据算法编制的程序；依赖软硬 件环境，容易掩盖算法本身的优劣；没有实际价值。 事前分析：求出该算法的一个时间界限函数。 ④ 输入： 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 ⑤ 输出： 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的 量。 一个算法可以用多种方法描述，主要有：使用自然 语言描述；使用形式语言描述；使用计算机程序设计语 言描述。 算法和程序是两个不同的概念。一个计算机程序是 对一个算法使用某种程序设计语言的具体实现。算法必 须可终止意味着不是所有的计算机程序都是算法。 在本门课程的学习、作业练习、上机实践等环节， 算法都用C语言来描述。在上机实践时，为了检查算法 是否正确，应编写成完整的C语言程序。 与此相关的因素有： • 依据算法选用何种策略； • 问题的规模； • 程序设计的语言； • 编译程序所产生的机器代码的质量； • 机器执行指令的速度； 撇开软硬件等有关部门因素，可以认为一个特定算 法“运行工作量”的大小，只依赖于问题的规模（通 常用n表示），或者说，它是问题规模的函数。 4
    2018/11/12 定理：若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0是一个m次多项 式，则A(n)=O(n m) 例５ for(i=2;i<=n;++i) for(j=2;j<=i-1;++j) {++x; a[i,j]=x; } 语句频度为： 1+2+3+…+n-2=(1+n-2) ×(n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 ∴时间复杂度为O(n2)，即此算法的时间复杂度为平方阶。 • 一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的 时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二 次多项式来限界。 算法分析应用举例 算法中基本操作重复执行的次数是问题规模n的某 个函数，其时间量度记作 T(n)=O(f(n))，称作算法的渐 近时间复杂度(Asymptotic Time complexity)，简称时间 复杂度。 一般地，常用最深层循环内的语句中的原操作的执 行频度(重复执行的次数)来表示。 “O”的定义： 若f(n)是正整数n的一个函数，则 O(f(n)) 表示 M≥0 ，使得当n ≥ n0时，| f(n) | ≤ M | f(n0) | 。 表示时间复杂度的阶有： O(1) ：常量时间阶 O(㏒n) ：对数时间阶 O(n㏒n) ：线性对数时间阶 O (n)：线性时间阶 O (nk)： k≥2 ，k次方时间阶 例１ 两个n阶方阵的乘法 for(i=1，i<=n; ++i) for(j=1; j<=n; ++j) { c[i][j]=0 ; for(k=1; k<=n; ++k) c[i][j]+=a[i][k]*b[k][j] ; } 由于是一个三重循环，每个循环从1到n，则总次数为： n×n×n=n3 时间复杂度为T(n)=O(n3) 例２ {++x; s=0 ;} 将x自增看成是基本操作，则语句频度为１，即时 间复杂度为Ｏ(1) 。 以下六种计算算法时间的多项式是最常用的。其关 系为： O(1)sqrt(n) ) printf(“&d 是一个素数\n” , n) ; printf(“&d 不是一个素数\n” , n) ; 嵌套的最深层语句是i++；其频度由条件( (n% i)!=0 && i*1.0< sqrt(n) ) 决定，显然i*1.0< sqrt(n) ，时间复杂 度O(n1/2)。 5
    2018/11/12 例2：冒泡排序法。 Void bubble_sort(int a[]，int n) { change=false; for (i=n-1; change=TURE; i>1 && change; --i) for (j=0; ja[j+1]) } • 最好情况：0次 • 最坏情况：1+2+3+⋯+n-1=n(n-1)/2 • 平均时间复杂度为： O(n2) { a[j] ←→a[j+1] ; change=TURE ; } ⑴ Sum1( int n ) { int p=1, sum=0, m ; for (m=1; m<=n; m++) { p*=m ; sum+=p ; } return (sum) ; } ⑶ 递归函数 fact( int n ) { if (n<=1) return(1) ; else return( n*fact(n-1)) ; } } ⑵ Sum2( int n ) { int sum=0, m, t ; for (m=1; m<=n; m++) { p=1 ; for (t=1; t<=m; t++) p*=t ; sum+=p ; } return (sum) ; 1.3.4 算法的空间分析 空间复杂度(Space complexity) ：是指算法编写成 程序后，在计算机中运行时所需存储空间大小的度量。 记作： S(n)=O(f(n)) 其中： n为问题的规模(或大小) 该存储空间一般包括三个方面： • 指令常数变量所占用的存储空间; • 输入数据所占用的存储空间; • 辅助(存储)空间。 一般地，算法的空间复杂度指的是辅助空间。 • 一维数组a[n]： 空间复杂度 O(n) • 二维数组a[n][m]： 空间复杂度 O(n*m) 第2章 线性表 线性结构是最常用、最简单的一种数据结构。而线 性表是一种典型的线性结构。其基本特点是线性表中的 数据元素是有序且是有限的。在这种结构中： ① 存在一个唯一的被称为“第一个”的数据元素； ② 存在一个唯一的被称为“最后一个”的数据元素； ③ 除第一个元素外，每个元素均有唯一一个直接前 驱； ④ 除最后一个元素外，每个元素均有唯一一个直接 后继。 习 题 一 1 简要回答术语：数据，数据元素，数据结构，数据 类型。 2 数据的逻辑结构？数据的物理结构？逻辑结构与物 理结构的区别和联系是什么？ 3 数据结构的主要运算包括哪些？ 4 算法分析的目的是什么？算法分析的主要方面是什 么？ 5 分析以下程序段的时间复杂度，请说明分析的理由 或原因。 2.1 线性表的逻辑结构 2.1.1 线性表的定义 线性表(Linear List) ：是由n(n≧0)个数据元素(结 点)a1，a2， …an组成的有限序列。该序列中的所有结 点具有相同的数据类型。其中数据元素的个数n称为线 性表的长度。 当n=0时，称为空表。 当n>0时，将非空的线性表记作： (a1，a2，…an) a1称为线性表的第一个(首)结点，an称为线性表的最后 一个(尾)结点。 6
    2018/11/12 a1，a2，…ai-1都是ai(2≦i≦n)的前驱，其中ai-1是ai的直 接前驱; ai+1，ai+2，…an都是ai(1≦i ≦n-1)的后继，其中ai+1是ai 的直接后继。 2.1.2 线性表的逻辑结构 线性表中的数据元素ai所代表的具体含义随具体应 用的不同而不同，在线性表的定义中，只不过是一个抽 象的表示符号。 ◆ 线性表中的结点可以是单值元素(每个元素只有一 个数据项) 。 例1: 26个英文字母组成的字母表： (A，B，C、…、Z） ListLength( L ) 初始条件：线性表L已存在； 操作结果：若L为空表，则返回TRUE，否则返回 FALSE； …. GetElem( L, i, &e ) 初始条件：线性表L已存在，1≦i≦ListLength(L)； 操作结果：用e返回L中第i个数据元素的值； ListInsert ( L, i, &e ) 初始条件：线性表L已存在，1≦i≦ListLength(L) ； 操作结果：在线性表L中的第i个位置插入元素e； … } ADT List 例2 ： 某校从1978年到1983年各种型号的计算机拥有量 的变化情况：(6，17，28，50，92，188） 例3 ： 一副扑克的点数 (2，3，4，…，J，Q，K，A) ◆ 线性表中的结点可以是记录型元素，每个元素含有多个数据项 ，每个项称为 结点的一个域 。每个元素有一个可以唯一标识每个结点的数据项组，称为关键字。 例4 ： 某校2001级同学的基本情况：{(‘2001414101’， ‘张里户’，‘男’，06/24/1983)， (‘2001414102’， ‘张化司’，‘男’，08/12/1984) …， (‘2001414102’， ‘李利辣’，‘女’，08/12/1984) } ◆ 若线性表中的结点是按值(或按关键字值)由小到大(或由大到小)排列的，称线 性表是有序的。 2.2 线性表的顺序存储 2.2.1 线性表的顺序存储结构 顺序存储 ：把线性表的结点按逻辑顺序依次存放 在一组地址连续的存储单元里。用这种方法存储的线性 表简称顺序表。 顺序存储的线性表的特点： ◆ 线性表的逻辑顺序与物理顺序一致; ◆ 数据元素之间的关系是以元素在计算机内“物理 位置相邻”来体现。 设有非空的线性表：(a1，a2，…an) 。顺序存储如图 2-1所示。 ◆ 线性表是一种相当灵活的数据结构，其长度可根 据需要增长或缩短。 ◆ 对线性表的数据元素可以访问、插入和删除。 2.1.3 线性表的抽象数据类型定义 ADT List{ 数据对象：D = { ai | ai∈ElemSet, i=1,2,…,n, n≧0 } 数据关系：R = { | ai-1, ai∈D, i=2,3,…,n } 基本操作： InitList( &L ) 操作结果：构造一个空的线性表L； Loc(a1) Loc(ai)+(i-1)* l … a1 a2 … ai … an … 图2-1 线性表的顺序存储表示 在具体的机器环境下：设线性表的每个元素需占用l 个存储单元，以所占的第一个单元的存储地址作为数据 元素的存储位置。则线性表中第i+1个数据元素的存储 位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满 足下列关系： LOC(ai+1)=LOC(ai)+l 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(i-1)*l 7
    2018/11/12 算法描述 Status Insert_SqList(Sqlist *L，int i ，ElemType e) { int j ; if ( i<0||i>L->length-1) return ERROR ; if (L->length>=MAX_SIZE) { printf(“线性表溢出!\n”); return ERROR ; } for ( j=L->length–1; j>=i-1; --j ) L->Elem_array[j+1]=L->Elem_array[j]; /* i-1位置以后的所有结点后移 */ L->Elem_array[i-1]=e; /* 在i-1位置插入结点 */ L->length++ ; return OK ; } 在高级语言(如C语言)环境下：数组具有随机存取 的特性，因此，借助数组来描述顺序表。除了用数组来 存储线性表的元素之外，顺序表还应该有表示线性表的 长度属性，所以用结构类型来定义顺序表类型。 #define OK 1 #define ERROR -1 #define MAX_SIZE 100 typedef int Status ; typedef int ElemType ; typedef struct sqlist { ElemType Elem_array[MAX_SIZE] ; int length ; } SqList ; 2.2.2 顺序表的基本操作 顺序存储结构中，很容易实现线性表的一些操作：初 始化、赋值、查找、修改、插入、删除、求长度等。 以下将对几种主要的操作进行讨论。 1 顺序线性表初始化 Status Init_SqList( SqList *L ) { L->elem_array=( ElemType * )malloc(MAX_SIZE*sizeof( ElemType ) ) ; if ( !L -> elem_array ) return ERROR ; else { L->length= 0 ; return OK ; } } 时间复杂度分析 在线性表L中的第i个元素之前插入新结点，其时间主 要耗费在表中结点的移动操作上，因此，可用结点的移 动来估计算法的时间复杂度。 设在线性表L中的第i个元素之前插入结点的概率 为Pi，不失一般性，设各个位置插入是等概率，则 Pi=1/(n+1)，而插入时移动结点的次数为n-i+1。 总的平均移动次数： Einsert=∑pi*(n-i+1) (1≦i≦n) ∴ Einsert=n/2 。 即在顺序表上做插入运算，平均要移动表上一半结 点。当表长n较大时，算法的效率相当低。因此算法的 平均时间复杂度为O(n)。 2 顺序线性表的插入 在线性表 L= (a1，…a i-1，ai， ai+1，…，an) 中的第 i(1≦i≦n)个位置上插入一个新结点e，使其成为线性表： L=(a1，…a i-1，e，ai，ai+1，…，an) 实现步骤 (1) 将线性表L中的第i个至第n个结点后移一个位置。 (2) 将结点e插入到结点ai-1之后。 (3) 线性表长度加1。 3 顺序线性表的删除 在线性表 L=(a1，…a i-1，ai， ai+1，…，an) 中删除结 点ai(1≦i≦n)，使其成为线性表： L= (a1，…ai-1，ai+1，…，an) 实现步骤 (1) 将线性表L中的第i+1个至第n个结点依此向前移动一个位置。 (2) 线性表长度减1。 算法描述 ElemType Delete_SqList(Sqlist *L，int i) { int k ; ElemType x ; 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料