教学课件·数据结构与算法(第2版)1.ppt

1、数据结构与算法1第第1章章 概述概述 1节节2内容提要2基本概念和算法表现形式了解即可基本概念和算法表现形式了解即可算法评价标准、正确性、时间复杂性算法评价标准、正确性、时间复杂性最坏情况和平均情况，很重要最坏情况和平均情况，很重要 主要内容：主要内容：数据结构和算法的基本概念数据结构和算法的基本概念算法的表现形式和评价方法算法的表现形式和评价方法3内容提要3抽象数据类型抽象数据类型结合对表树图的类化示例加以理解结合对表树图的类化示例加以理解 难点：难点：抽象数据类型抽象数据类型算法时间复杂性的计算算法时间复杂性的计算算法时间复杂性的计算方法算法时间复杂性的计算方法通过后续各章对众多算法的分析

2、、评价、通过后续各章对众多算法的分析、评价、时间空间复杂性计算，逐步加以理解时间空间复杂性计算，逐步加以理解41.1 基本概念41数据和数据结点数据和数据结点 n数据是对客观事物的描述形式和编码形式数据是对客观事物的描述形式和编码形式的统称的统称 n是计算机算法和程序的处理对象（输入数是计算机算法和程序的处理对象（输入数据）和计算结果（输出数据）据）和计算结果（输出数据）1.1.1 数据结构的概念数据结构的概念51.1 基本概念1.1.1 数据结构的概念5数据的种类数据的种类n数值型数据（整数、实数等）数值型数据（整数、实数等）n文字型数据（字符、字符串、程序代码）文字型数据（字符、字符串、程

3、序代码）n矩阵、记录矩阵、记录n声音、图像声音、图像数据总是以某种数据总是以某种编码编码形式出现的形式出现的61.1 基本概念1.1.1 数据结构的概念6数据元素（数据元素（data element）数据结点，简称结点（数据结点，简称结点（node）描述描述一个一个独立事物的名称、数量、特征、性质的独立事物的名称、数量、特征、性质的一组相关信息组成一个数据结点一组相关信息组成一个数据结点通常，一个结点含有多个数据项（通常，一个结点含有多个数据项（data item）结点的类型：结构型结点的类型：结构型关键字（关键字（key）单值类型的结点：只含一个数据项单值类型的结点：只含一个数据项71.1.

4、1 数据结构的概念2数据结构的定义 数据结构（data structure）B =(D，R)7数据结构有穷的结点集合D中结点间的有穷关系集合数据的逻辑结构（数据的逻辑结构（logical form）存储形式：物理存储形式：物理结构（结构（physical form）81.1.1 数据结构的概念8物理结构物理结构存储结构存储结构n数据结构的存储形式（存储表示）数据结构的存储形式（存储表示）n存储数据结点和结点之间的关系存储数据结点和结点之间的关系n顺序存储、非顺序存储顺序存储、非顺序存储n存储结点存储结点n用于存储一个数据结点的存储单元用于存储一个数据结点的存储单元n一个数据结点对应一个存储结点

5、一个数据结点对应一个存储结点n数据结点和存储结点统称结点数据结点和存储结点统称结点 n空白结点（空结点、自由结点）空白结点（空结点、自由结点）预留的存储结点（即尚未存储数据的存储结点）预留的存储结点（即尚未存储数据的存储结点）91.1.1 数据结构的概念2数据结构的定义数据结构与算法研究的对象9数据元素的数据元素的集合集合元素元素之间之间的的关系关系对数据集合进行哪些对数据集合进行哪些运算运算实现运算的实现运算的算法算法算法效率算法效率10示例 设D为某专业开设的计算机课程，R是定义在D上的关系 D=C1、C2、C3、C4、C5 R=(x,y)|x课程是y课程的先修课，x,y D 若R1=(C

6、1,C2),(C2,C3),(C3,C4),(C4,C5)，则DS=(D,R1)就是一种数据结构（线性表）若R2=(C1,C2),(C2,C3),(C2,C4),(C2,C5),(C3,C5),，则DS=(D,R2)也是一种数据结构10数据元素、结点逻辑结构逻辑结构111.1.1 数据结构的概念3数据结构的种类11表结构、树结构、图结构、散结构表结构、树结构、图结构、散结构 表：描述结点之间简单的先后次序关系表：描述结点之间简单的先后次序关系树：描述结点之间的层次关系、嵌套关系树：描述结点之间的层次关系、嵌套关系图：描述结点之间的图：描述结点之间的“多对多多对多”关系关系散结构：结点之间松散的

7、散结构：结点之间松散的“无关关系无关关系”比如散列表比如散列表 一对一的关系，比如学生成绩单一对一的关系，比如学生成绩单比如城市交通网比如城市交通网 一对多的关系，比如某部门的组织机构一对多的关系，比如某部门的组织机构 121.1.1 数据结构的概念3数据结构的种类12图示：圆圈图示：圆圈表示结点，表示结点，连线连线表示结点之间关系表示结点之间关系 表结构表结构 树结构树结构 散 结 构散 结 构图结构图结构 树、散是图的特例，表是树的特例树、散是图的特例，表是树的特例131.1.2 抽象数据类型 1抽象的意义 抽取事物的共性，忽略个性 体现外部特征，掩盖具体细节 132抽象数据类型的含义抽象

8、数据类型的含义 ADT（Abstract Data Types）将数据连同）将数据连同对其的处理操作封装在一起对其的处理操作封装在一起 3抽象数据类型的实现方法抽象数据类型的实现方法 封装法、半封装法、分散法封装法、半封装法、分散法141.1.3 算法的概念 1算法的定义 14计算机科学家计算机科学家D.E.Knuth（克努特）在其经典巨著（克努特）在其经典巨著计算机程序设计艺术计算机程序设计艺术(The Art of Computer Programming)第一卷中对算法的定义第一卷中对算法的定义 算法，就是算法，就是有穷规则有穷规则的集合，其中的规则规定了的集合，其中的规则规定了解决某特

9、定类型问题的解决某特定类型问题的运算序列运算序列有穷性、确定性、可行性、输入、输出有穷性、确定性、可行性、输入、输出151.1.3 算法的概念 15n有穷性有穷性：一个算法在执行有限步之后必须结束：一个算法在执行有限步之后必须结束n确定性确定性：算法的每一步骤必须确切定义。执行者可：算法的每一步骤必须确切定义。执行者可根据该算法的每一步要求进行操作，并最终得出正根据该算法的每一步要求进行操作，并最终得出正确的结果（即无歧义）确的结果（即无歧义）n可行性可行性：算法中所有的运算都可以精确地实现：算法中所有的运算都可以精确地实现n输入输入：算法有零个或多个输入，即在算法开始之前：算法有零个或多个输

10、入，即在算法开始之前，对算法给定的初始量，对算法给定的初始量n输出输出：算法有一个或多个输出，即与输入有某个特：算法有一个或多个输出，即与输入有某个特定关系的量，简单地说就是算法的最终结果定关系的量，简单地说就是算法的最终结果161.1.3 算法的概念 2算法、数据结构与程序的关系 1616给定问题给定问题设计求解问题的算法设计求解问题的算法 抽象出数据，建立数据结构抽象出数据，建立数据结构 满意满意？正确正确？有错有错 交付使用交付使用正确正确 对算法不满意对算法不满意对数据结构不满意对数据结构不满意不满意不满意满意满意 对算法的性能进行评价对算法的性能进行评价 将算法分解成对数据结构的运算

11、将算法分解成对数据结构的运算 编程实现，并上机调试编程实现，并上机调试 16 本 节 结 束17第第1章章 概述概述 1节节数据结构与算法18第第1章章 概述概述 2节节191.2 算法的描述和评价 191描述形式描述形式 n自然语言自然语言n流程图（流程图（flowchart）n类语言类语言伪代码（伪代码（pseudocode）1.2.1 算法的描述算法的描述 描述形式、描述形式、程序形式（算法的实现形式）程序形式（算法的实现形式）程序中含有算法程序中含有算法2.示例示例 20示例1-1 自然选择排序算法（1）文字叙述从n个数据中选出一个最小元素作为第一项再从剩下的n-1个数据中选出一个最小

12、元素作为第二项重复上述，直至选择最后一项不依赖数据结构，不考虑如何存储数据不依赖数据结构，不考虑如何存储数据 21示例1-1 自然选择排序算法（1）文字叙述从n个数据中选出一个最小元素作为第一项再从剩下的n-1个数据中选出一个最小元素作为第二项重复上述，直至选择最后一项不依赖数据结构，不考虑如何存储数据不依赖数据结构，不考虑如何存储数据 进一步叙述进一步叙述 将数据存储在将数据存储在数组数组an中中从从n个元素中选择最小元个元素中选择最小元aj，换到，换到a0处；处；再从剩下的再从剩下的n-1个元素中选择最小元，换到个元素中选择最小元，换到a1处；处；22示例1-1 自然选择排序算法（1）文字

13、叙述从n个数据中选出一个最小元素作为第一项再从剩下的n-1个数据中选出一个最小元素作为第二项重复上述，直至选择最后一项 循环形式：循环形式：步骤步骤1 1）置）置i=0i=0；步骤步骤2 2）从）从aian-1aian-1选出最小元素选出最小元素akak；步骤步骤3 3）交换）交换aiai与与akak；步骤步骤4 4）i=i+1;i=i+1;步骤步骤5 5）如果）如果i i等于等于n-1n-1，则算法结束；，则算法结束；否则，转步骤否则，转步骤2 2。23示例1-1 自然选择排序算法（2）流图 否 是 结束 i=n1？i=0 交换 ai与 ak 开始 从 ai至 an1选出最小元 ak i=i

14、+1 24示例1-1 自然选择排序算法（3）伪代码）伪代码for(i=0;in-1;i+)从从ai到到an-1中选出最小元素中选出最小元素ak;使使ak与与ai交换交换;25示例1-1 自然选择排序算法for(i=0;in-1;i+)k=i;for(j=i+1;jn;j+)if(ajrightleft=0;right=n-1;i=-1mid=(left+right)/2比较比较x与与amidx=amidxamidi=mid;left=right+1开始开始29示例1-2 二分查找（binary search）（3）伪代码）伪代码 left0，rightn-1;while(leftamid)没找

15、到没找到x，返回，返回-1;mid=(left+right)/2;if(x=amid)找到找到x，返回，返回x的下标的下标mid;if(x n0，T(n)cf(n)都成立都成立 那么，就记作那么，就记作 T(n)=O(f(n)381.2.2 算法的评价标准和评价方法 3时间复杂性T(n)=O(f(n)T(n)是是f(n)的的大大O函数函数只求只求T(n)的最高阶的最高阶忽略其低阶项和常系数忽略其低阶项和常系数f(n)：运行时间运行时间 增长率的上界增长率的上界简化简化T(n)的计算；较客观地反映当的计算；较客观地反映当n很大时，很大时，算法的时间性能算法的时间性能 391.2.2 算法的评价标

16、准和评价方法 3时间复杂性n示例示例设设T(n)=n2+4n，有，有f(n)=n2，则：，则：n2+4n=O(n2)证明：证明：因为存在因为存在c=2，n0=4，使对于一切，使对于一切nn0，恒有恒有 n2+4n2 n2注意：注意：f(n)越小，越接近越小，越接近T(n)401.2.2 算法的评价标准和评价方法 3时间复杂性都是都是n的平方阶的的平方阶的又例：算法又例：算法A的时间耗用函数的时间耗用函数 T1(n)=20n2+100n 算法算法B的时间耗用函数的时间耗用函数 T2(n)=0.5n23n+18于是于是 T1(n)=O(n2)T2(n)=O(n2)41常用阶（由低到高）O(1)O(

17、logn)O(n)O(n logn)O(n2)O(n3)O(nc)常数阶常数阶最快最快对数阶对数阶底数无关底数无关线性阶线性阶很理想的阶很理想的阶平方阶平方阶c是常数，多项式阶是常数，多项式阶O(2n)O(n!)指数阶指数阶阶乘阶阶乘阶（无效算法）（无效算法）（均为有效算法）均为有效算法）42示例 某算法T(n)=2n，当n=1000时，其工作量（执行基本语句条数）将达到21000 假定每执行一条基本语句需要花费1毫微秒（10-9秒）时间，那么解此问题共需要：设计算法时，应当选用有效算法，并且尽量设计算法时，应当选用有效算法，并且尽量设法降低它的时间耗用量，以提高算法的运设法降低它的时间耗用量

18、，以提高算法的运行速度行速度 ()1000288921.22 1010360024365淮创年434.最坏情况和平均情况（1）为什么要区分两种情况 有些算法因分支等因素，对不同的输入数据（即使输入数据量都是n）耗用时间会有所不同，而且往往相差很大 为使评价更客观，更有说服力，通常需要分几种情况讨论算法的时间性能 在算法理论分析上，最常见的是分别计算出最坏情况下和平均情况下算法的时间复杂性（也称最坏性态和平均性态）44具有相同输入数据量的不同输入数据算法时间用量的最大值 用TW(n)表示（2）最坏情况（最坏情况（worst-case）说一个算法是说一个算法是“好好”的，总是希望它在任何的，总是希

19、望它在任何情况下运行速度都快情况下运行速度都快最坏情况下算法的最坏情况下算法的时间性态可以表述算法的这一特征时间性态可以表述算法的这一特征4.最坏情况和平均情况最坏情况和平均情况 45对于所有相同输入数据量的各种不同数据，对于所有相同输入数据量的各种不同数据，算法耗用时间的算法耗用时间的“平均值平均值”用用TE(n)表示表示（3）平均情况）平均情况等概率：平均情况（等概率：平均情况（average-case）加概率：期望情况（加概率：期望情况（expected-case）4.最坏情况和平均情况最坏情况和平均情况 46（3）平均情况）平均情况从实用角度看，有些算法遇到最坏情况的可能从实用角度看，

20、有些算法遇到最坏情况的可能性极小极小，在大多数情况下是快的。算法的性极小极小，在大多数情况下是快的。算法的平均性态可以表述算法的这一特征平均性态可以表述算法的这一特征从最坏情况和平均情况两个角度分析算法的时从最坏情况和平均情况两个角度分析算法的时间性能，可以给算法作出更为客观的评价间性能，可以给算法作出更为客观的评价 对于所有相同输入数据量的各种不同数据，对于所有相同输入数据量的各种不同数据，算法耗用时间的算法耗用时间的“平均值平均值”用用TE(n)表示表示 4.最坏情况和平均情况最坏情况和平均情况 475.算法的选用原则 n当数据量不大时，低阶算法未必就快当数据量不大时，低阶算法未必就快 例

21、如，算法例如，算法A1和和A2的时间复杂性分别为的时间复杂性分别为 T1(n)=1000n 和和 T2(n)=n2 虽然虽然O(T1(n)1000时，时，A1好于好于A2 当当n1000时，时，A2好于好于A1，因为，因为T2(n)T1(n)485.算法的选用原则 n总原则：能满足客观要求即可用总原则：能满足客观要求即可用n需要考虑如下因素：需要考虑如下因素：1）算法实现的难易程度）算法实现的难易程度2）算法使用的次数，否实时处理）算法使用的次数，否实时处理 （如通信、天气预报等）（如通信、天气预报等）3）算法运行环境）算法运行环境 输入数据量的大小范围输入数据量的大小范围491.2.2 算法

22、的评价标准和评价方法 算法空间用量函数S(n)时空折中方案（时空折中方案（space versus time trade-offs）算法执行时所需空间（占用内存单元数）算法执行时所需空间（占用内存单元数）通常只计算辅助空间用量通常只计算辅助空间用量不计原始数据所占的空间不计原始数据所占的空间 为了节省时间，先作为了节省时间，先作“预处理预处理”，多记，多记一些信息（多占空间）一些信息（多占空间）时空转换时空转换501.2.3 计算时间复杂性的一般方法 1支配性语句度量法 其他语句花费时间的总和将不超过这个语句花费时间的常数倍用典型语句的执行次数作为程序段花费时间的阶 起支配性作用511支配性语

23、句度量法示例：for(i=1,c=0,s=a0;in;i+)1.if(aia0)2.c+;3.s+=ai;1，2，3：语句序号：语句序号用于讲解算法用于讲解算法可选句可选句1、3作为典型语句作为典型语句T(n)=O(n)522分段计算法若一段耗时为O(f(n)另一段耗时为O(g(m)两段共耗费O(f(n)+O(g(m)=O(f(n)+g(m)取最高阶例 O(n2)+O(n)=O(n2)O(n)+O(n)=O(n)533分层计算法分层计算，相乘，再化简外层循环共执行O(f(n)次内层循环O(g(m)次两层共执行O(f(n)O(g(m)=O(f(n)g(m)次543分层计算法示意性程序1：for(

24、i=0;in;i+)x=y=0;for(j=0;jai)x+=1;if(ajai)y+=1;printf(%d,%dn,x,y);O(n)*O(n/2)=O(n2)553分层计算法直接计算内层总的执行时间 例for(i=1;i=n;i+)for(j=1;j()21nT n=-575数学模型法 利用“便于”计算的数学模型，和复杂的数学演算（包括微分和积分运算），计算T(n)58内容小结58第第1.1节节介绍了数据结构和算法的概念、抽介绍了数据结构和算法的概念、抽象数据类型象数据类型其中，抽象数据类型虽然在程序设计实践其中，抽象数据类型虽然在程序设计实践中很重要，但不是本书的训练重点，属于中很重要

25、，但不是本书的训练重点，属于了解内容和扩展内容了解内容和扩展内容对于数据结构和算法的概念，也无须强记，对于数据结构和算法的概念，也无须强记，理解即可理解即可59内容小结59第1.2节，算法的存在形式分为描述形式和实现形式（即程序形式）描述形式简单直观，易于阅读理解，又便于对算法分析评价，需要好好掌握程序形式往往过于繁杂，尤其是类的实现程序极为冗长，一般不需要全面掌握，当然上机实验是不可缺少的60内容小结60第1.2节算法的评价标准和评价方法占有较大篇幅，既是重点，也是难点尤其是算法时间复杂性的计算方法难度较大，需要循序渐进地学习逐步掌握61内容小结61基本要求基本要求了解了解数据结构和算法的概

26、念、抽象数据类数据结构和算法的概念、抽象数据类型的含义；掌握算法的表示形式、评价标型的含义；掌握算法的表示形式、评价标准、最坏情况和平均情况等内容准、最坏情况和平均情况等内容不要求不要求全面掌握算法的时间复杂性一般计全面掌握算法的时间复杂性一般计算方法，但在后续学习中能够读懂各章给算方法，但在后续学习中能够读懂各章给出的计算步骤和计算结果出的计算步骤和计算结果62内容小结62进一步要求进一步要求：了解抽象数据类型的一般实：了解抽象数据类型的一般实现方法；对于结构简单的算法能够对其进现方法；对于结构简单的算法能够对其进行较为恰当的评价行较为恰当的评价提高要求提高要求：掌握算法的时间复杂性一般计：

27、掌握算法的时间复杂性一般计算方法，对于结构简单的算法能够对其进算方法，对于结构简单的算法能够对其进行准确评价行准确评价应用要求应用要求：掌握抽象数据类型的实现方法，：掌握抽象数据类型的实现方法，对后续章节给出的数据结构和算法能够进对后续章节给出的数据结构和算法能够进行类化处理行类化处理63第第1章章 概述概述 2节节 本 节 结 束数据结构与算法64第2章 表结构 1节第2章 表 结 构内容提要内容提要普通表结构、受限的表结构、近似表普通表结构、受限的表结构、近似表结构、扩展表结构、用类实现表结构结构、扩展表结构、用类实现表结构的程序示例的程序示例针对各结构的特点、存储方法、常见针对各结构的特

28、点、存储方法、常见的运算，给出相应的处理算法，分析的运算，给出相应的处理算法，分析其效率其效率第2章 表 结 构前两节：普通线性表的顺序存储（顺前两节：普通线性表的顺序存储（顺序表）和链式存储（链表），是序表）和链式存储（链表），是重点重点链表是重中之重，也是难点链表是重中之重，也是难点内容提要内容提要第2章 表 结 构2.3节节栈和队，只能在指定端点进行插栈和队，只能在指定端点进行插入删除（受限的表结构），常用、重入删除（受限的表结构），常用、重要，难度不太大要，难度不太大循环队的进退队算法有难度循环队的进退队算法有难度内容提要内容提要第2章 表 结 构2.4节节 矩阵和字符串矩阵和字符串与

29、普通表结构有共同处（近似表结构）与普通表结构有共同处（近似表结构）稀疏矩阵的转置算法和相乘算法中使稀疏矩阵的转置算法和相乘算法中使用的技术值得关注用的技术值得关注KMP算法则具有较大的难度算法则具有较大的难度BM算法和算法和KR算法稍作了解即可算法稍作了解即可内容提要内容提要第2章 表 结 构2.5节节 散列表散列表与普通表差距大，有点像与普通表差距大，有点像具有非常大的实用价值，具有非常大的实用价值，重点重点！散列表的性能分析难度较大，了解散列表的性能分析难度较大，了解内容提要内容提要第2章 表 结 构2.6节节广义表（扩展表结构），非重点广义表（扩展表结构），非重点内容提要内容提要2.7节

30、节表结构的类程序设计示例表结构的类程序设计示例（3 个）个）引导大家如何进行面向对象的程序设计引导大家如何进行面向对象的程序设计实现标准数据结构的类实现标准数据结构的类第2章 表 结 构2.1 基本概念和顺序表基本概念和顺序表 2.1.1 基本概念 线性表线性表（linear list）:具有具有n（n0）个数据结）个数据结点（元素）的序列点（元素）的序列 A=(a1，a2，an)n首结点和尾结点首结点和尾结点 n表的长度表的长度 n空表空表 n前驱和后继（左邻和右邻）前驱和后继（左邻和右邻）n有序表有序表 1.定义和示例定义和示例示例 学生成绩单学生成绩单 财务流水账财务流水账 商品供货单、

31、库存单商品供货单、库存单 name number chinese math eng sgrade 张 一 1201 76 84 吴小宁 1202 45 68 王君明 1203 93 96 尚静静 1250 77 69 2.主要运算（1）查找（）查找（search）按按关键字关键字x查查查找结果：查找结果：成功，返回成功，返回x的地址的地址 不成功：返回无效地址不成功：返回无效地址按非按非关键字查关键字查结果：可能找出多个符合条件的结点结果：可能找出多个符合条件的结点2.主要运算（2）插入（）插入（insert）指定条件插入（比如，有序插入）指定条件插入（比如，有序插入）指定位置插入（插在表头、

32、表尾、第指定位置插入（插在表头、表尾、第i个位置）个位置）无条件插入（随便插在何处）无条件插入（随便插在何处）2.主要运算（3）删除（）删除（delete）删除值为删除值为x的结点的结点 删除表头结点、表尾结点、或第删除表头结点、表尾结点、或第i个结点个结点插入和删除都是对表结构的修改插入和删除都是对表结构的修改 查找、插入、删除最基本、最常用查找、插入、删除最基本、最常用 2.主要运算（4）存取（）存取（access）（5）更新（）更新（update）（6）合并（）合并（merge）（7）分裂（）分裂（split）（8）复制（）复制（copy）（9）排序（）排序（sorting）3.基本存储

33、方法 顺序存储（顺序表）顺序存储（顺序表）链式存储（链表）链式存储（链表）1）顺序存储 按结点在表中的次序依次存储按结点在表中的次序依次存储特点：结点的逻辑次序与物理次序一致特点：结点的逻辑次序与物理次序一致()(1)(1,2,)loc iitcin=-*+=鬃结点结点i的存储地址公式：的存储地址公式：c：首地址：首地址t：结点长度（占内存单元数）：结点长度（占内存单元数）用高级语言描述顺序存储用高级语言描述顺序存储用数组存储用数组存储数组的一个元素便是一个存储结点数组的一个元素便是一个存储结点下标作为结点的存储地址（相对地址）下标作为结点的存储地址（相对地址）1）顺序存储顺序存储 单值结点单

34、值结点示例示例：15以内的素数以内的素数 2 3 5 7 11 13 存储结构图式存储结构图式Prime=(2，3，5，7，11，13)1）顺序存储顺序存储 单值结点单值结点示例示例：15以内的素数以内的素数存储结构图式存储结构图式Prime=(2，3，5，7，11，13)多值结点多值结点示例示例：学生情况登记表学生情况登记表结点结构结点结构：name number Chinese math eng sgrade 1）顺序存储顺序存储 某班级的学生情况登记表 下标 name number chinese math eng sgrade 0 张 一 1201 76 85 84 B 1 吴小宁 1

35、202 45 56 68 D 3 王君明 1203 93 89 96 A n-1 尚静静 1250 77 67 69 C 2）链式存储 值域（数据域）值域（数据域）：存储表元素值：存储表元素值 链域（指针域）：存储后继结点的存储地址链域（指针域）：存储后继结点的存储地址 值 域 链 域 单向链表的结点结构单向链表的结点结构表头指针：指向链表的第一个结点的指针变量表头指针：指向链表的第一个结点的指针变量 最后一个结点的链域值为空（最后一个结点的链域值为空（NULL）一个一个链表链表就是就是表头指针表头指针和一串和一串相继链接的结点相继链接的结点的总称的总称 王 head 张 陈 李 赵 刘 链表

36、的逻辑结构图链表的逻辑结构图2）链式存储链式存储 3）存储结构的封装 将一个结构的所有信息定义成一个存储结构将一个结构的所有信息定义成一个存储结构增加程序的易读性增加程序的易读性容易检查程序错误容易检查程序错误易于扩充易于扩充 顺序表的封装定义定义list类型：类型：typedef struct /定义表的存储结构类型定义表的存储结构类型 char list_namename_length;/表名称表名称 int length;/表长度表长度 element_type dN;/存储表元素的数组存储表元素的数组 list /表的类型别名表的类型别名 用用list类型定义表变量类型定义表变量tea

37、m list team;team list_name length d0 d1 dN-1 链表的封装定义定义link_listlink_list类型：类型：typedef structtypedef struct char list_namename_length;/char list_namename_length;/表名称域表名称域 int length;int length;/表长度域表长度域 ptr head;ptr head;/表头指针域表头指针域 link_list;link_list;/链表类型名链表类型名 list_name length head list_name leng

38、th head list_name length head list_name length head 4.数据结点的存储方法 存储一个结点时，要体现两方面信息：存储一个结点时，要体现两方面信息：结点的数值，结点之间的次序关系结点的数值，结点之间的次序关系两方面信息集中在一个存储结点两方面信息集中在一个存储结点简单明了，易于理解，便于操作简单明了，易于理解，便于操作适用于：适用于：结点较小（数据域所占空间不大）结点较小（数据域所占空间不大）表长较短（结点数目不多）表长较短（结点数目不多）表结构变化不大（很少进行插入删除）表结构变化不大（很少进行插入删除）4.数据结点的存储方法 当表长很大，结点

39、很大，臃肿当表长很大，结点很大，臃肿内存中不能容纳一个完整的线性表内存中不能容纳一个完整的线性表频繁地在顺序表中进行插入删除，频繁地在顺序表中进行插入删除，大段大段的结点移动，影响速度大段大段的结点移动，影响速度存储结点存储结点分成两分成两个：个：表结点表结点：表示结点之间的次序关系：表示结点之间的次序关系数值结点数值结点：存储结点的数据值：存储结点的数据值表结点含有指向数值结点的指针表结点含有指向数值结点的指针表结点变短，消除臃肿，只移动指向数值结点的指针。表结点变短，消除臃肿，只移动指向数值结点的指针。4.数据结点的存储方法 当表长很大，结点很大，臃肿当表长很大，结点很大，臃肿内存中不能容

40、纳一个完整的线性表内存中不能容纳一个完整的线性表频繁地在顺序表中进行插入删除，频繁地在顺序表中进行插入删除，大段大段的结点移动，影响速度大段大段的结点移动，影响速度表结点存储在线性表中，表结点变短，不臃肿表结点存储在线性表中，表结点变短，不臃肿数值结点存储在数据区数值结点存储在数据区表结点含有指向数值结点的指针表结点含有指向数值结点的指针插入删除表结点时，只移动指向数值结点的指针插入删除表结点时，只移动指向数值结点的指针目录存储和索引目录存储 1）等长结点的目录存储等长结点的目录存储目录存储结构：目录区、数据区目录存储结构：目录区、数据区目录区：存储表结点（目录表，代替原线性表）目录区：存储表

41、结点（目录表，代替原线性表）数据区：存储数值结点数据区：存储数值结点表结点中存储数值结点在数据区中的存储地址表结点中存储数值结点在数据区中的存储地址目录表：顺序表，或链表目录表：顺序表，或链表数据区：数值结点无序随意存储数据区：数值结点无序随意存储1）等长结点的目录存储目录表是目录表是顺序表顺序表的存储方法的存储方法目录存储结构：目录区、数据区目录存储结构：目录区、数据区目录区：存储表结点（目录表，代替原线性表）目录区：存储表结点（目录表，代替原线性表）数据区：存储数值结点数据区：存储数值结点表结点中存储数值结点在数据区中的存储地址表结点中存储数值结点在数据区中的存储地址存储结构包括：目录表，

42、数据区，自由队列存储结构包括：目录表，数据区，自由队列1）等长结点的目录存储目录表是目录表是顺序表顺序表的存储方法的存储方法存储结构定义：存储结构定义：int am;/目录表目录表element_type dm;/数据区数据区int avm,avtop;/自由队列及其首指针自由队列及其首指针m：存储空间大小：存储空间大小element_type：数据元素类型：数据元素类型1）等长结点的目录存储目录表是目录表是顺序表顺序表的存储方法的存储方法图示图示 目录表 数组 a 数据区 数组 d 0 1 n-1 m-1 x0 x1 xn-1 0 1 m-1 xi i 目录表：目录表：int am;数据表数

43、据表 element_type dm;自由队列及其首指针自由队列及其首指针 int avm,avtop;自由队列：辅助机构自由队列：辅助机构 1）等长结点的目录存储自由队列初始化自由队列初始化for(i=0;im;i+)avi=i;/所有结点都放入自由队列（即进栈）所有结点都放入自由队列（即进栈）avtop=m;/自由队列首指针初值自由队列首指针初值2）不等长结点的目录存储（1）若结点长度差别不大，或短结点极少）若结点长度差别不大，或短结点极少按照最长结点的大小将短结点按照最长结点的大小将短结点“凑成凑成”长结点长结点变成等长结点变成等长结点（2）若结点长度参差不齐且差别较大）若结点长度参差不

44、齐且差别较大可以采用可以采用“不等长结点的目录存储不等长结点的目录存储”方法方法将数据表改为数据区将数据表改为数据区需要设计专门的需要设计专门的“数据区管理程序数据区管理程序”3）索引目录存储索引目录存储要点：目录表中带关键字要点：目录表中带关键字变成变成索引目录表索引目录表 便于通过关键字便于通过关键字访问表元素访问表元素 索引表 数据表 x0 x1 xn-1 0 1 m-1 xi 0 1 n-1 m-1 i k0 k1 ki 2.1.2 顺序表的插入和删除长度为长度为n的顺序表占据数组的顺序表占据数组am的前的前n个单元：个单元：a0an-1（nm）1.插入（插入元素插入（插入元素x）（1

45、）无条件（不指定插入点）无条件（不指定插入点）插在表尾最方便：插在表尾最方便：an+x;每插一个结点，只需用每插一个结点，只需用O(1)时间时间（2）指定位置插入指定位置插入ka5041126382i3i+197k-1 m将将x插插在此处在此处右移一位右移一位当前表长当前表长n=k7ka504112638xi2i+139k-1 m插入后，表长变成插入后，表长变成n=k+17ka5041126382i2i+139k-1 m先移动成这样，再插入先移动成这样，再插入x完成插入的程序段：完成插入的程序段：for(i=n-1;x=0;i-)ai+1=ai;/边边查边移查边移ai=x;/插入插入x 共移动

46、共移动n-i个元素个元素n+;/表长增表长增1 时间复杂性时间复杂性O(n-i)ka20314263812 13 1921k-1 m找找9的有序序位置的有序序位置21ka2031426389 12 1319k-1 m右移右移（3）有序有序插入（插入（x=9)插入的时间复杂性 插在尾部：插在尾部：T(n)=1 （最快）最快）插入插入ai处：处：T(n)=n-i（i=0插在表头最慢插在表头最慢）插入前，必须判断数组是否已经占满：插入前，必须判断数组是否已经占满：if(n=m)返回空间已用完的信息返回空间已用完的信息;/由请求插入者进行处理由请求插入者进行处理 else 执行具体的插入操作执行具体的

47、插入操作;建议建议：使用动态数组避免产生：使用动态数组避免产生溢出溢出2.1.2 顺序表的插入和删除长度为长度为n的顺序表占据数组的顺序表占据数组am的前的前n个单元：个单元：a0an-1（nm）2.删除删除（1）删除指定结点）删除指定结点指定指定元素值元素值x，指定，指定存储位置存储位置i前者，则先找到前者，则先找到x的位置（变成后者）的位置（变成后者）删除删除aika5041126382i3i+197k-1 m删除删除ai左移一位左移一位当前表长当前表长n=k表长变为表长变为n=k-1左移，抹去左移，抹去2，7变成多余的，最后变成：变成多余的，最后变成：ka5041126383i9i+17

48、7k-1 m2简单简单删除删除（指定位置）（指定位置）ka5041126382i3i+197k-1 m删除删除ai左移一位左移一位当前表长当前表长n=k完成删除的程序段：完成删除的程序段：for(j=i;jn-1;j+)aj=aj+1;/左移，抹去左移，抹去ain-;/表长减表长减1 共移动共移动n-1-i个元素个元素ka5041126383i9i+177k-1 m表长变为表长变为n=k-k-12简单简单删除删除（指定位置）（指定位置）ka5041126382i3i+197k-1 m删除删除ai左移一位左移一位当前表长当前表长n=k完成删除的程序段：完成删除的程序段：for(j=i;jn-1;

49、j+)aj=aj+1;/左移，抹去左移，抹去ain-;/表长减表长减1 时间复杂性时间复杂性：O(n-1-i)O(n-i)ka5041126383i9i+177k-1 m表长变为表长变为n=k-k-12.1.2 顺序表的插入和删除长度为长度为n的顺序表占据数组的顺序表占据数组am的前的前n个单元：个单元：a0an-1（nm）2.删除删除（2）删除非指定结点）删除非指定结点删除任一个结点，不定删哪个（罕见）删除任一个结点，不定删哪个（罕见）删除表尾结点最方便，只需要删除表尾结点最方便，只需要O(1)时间时间3插入删除的效率分析 1）在表尾处插）在表尾处插/删，最好，删，最好，T(n)=O(1)2

50、）在表头处插）在表头处插/删，最坏情况，删，最坏情况，T(n)=O(n)3）平均情况，移动半数表元素）平均情况，移动半数表元素，T(n)=O(n)4）如果表很长）如果表很长，频繁插，频繁插/删，效率不高删，效率不高 5）仅适于下列情况之一：）仅适于下列情况之一：v表长不大表长不大v不做，或很少做插不做，或很少做插/删删 v只在表的端点处插只在表的端点处插/删删6）顺序存储结构简单，空间利用率高）顺序存储结构简单，空间利用率高2.1.3 顺序表的查找 顺序查找、二分查找（针对有序表）顺序查找、二分查找（针对有序表）1顺序查找顺序查找（sequential search）从表的一端，向另一端，逐个