数据结构实用教程（C语言版）上ppt.ppt

数据结构实用教程（C语言版）上,第一章 绪论 第二章 线性表 第三章 栈和队列 第四章 多维数组和广义表,第一章 绪论,11 基本术语 12 数据结构的定义及研究的内容 121 数据的逻辑结构 122 数据的存储结构 123 数据的运算 13 算法 131 算法的概念及特性 132 算法的描述 133 算法的评价 14 学习数据结构的意义和目的,11 基本术语 数据（Data）是人们约定的符号，用它来表示客观事物及其活动，是信息的载体。数据是计算机程序加工处理的对象。 数据元素（Data Element）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，在不同的情况下，又可以称为元素、结点、顶点或记录。数据是由数据元素构成的。 数据项（Data Item）是构成数据元素不可分割的具有独立含义的最小标识单位。若数据元素可再分，则数据元素是由若干个数据项组成；如数据元素不可再分，数据元素和数据项是同一概念，如整型数据就是不可再分的。 数据类型（Data Type）是一个值的集合和定义在这个值集上一组操作的总称。按值的不同特性，高级程序设计语言中的数据类型可分为原子类型和结构类型两类。,第一章 绪论,12 数据结构的定义及研究的内容 数据结构的定义及研究的内容 数据结构（Data Structure）：按照某种逻辑关系组织起来的一批数据，用一定的存储方式存储在计算机的存储器中，并在这些数据上定义一个运算的集合，就称为一个数据结构（Data Structure）。 数据结构重点研究的内容： （1）数据的逻辑结构：即数据之间的逻辑关系。 （2）数据的存储结构：即数据及数据之间的关系在计算机存储器中的表示。 （3）数据的运算：即对数据施加的各种操作。,数据的逻辑结构 数据的逻辑结构（Logical Structure：的是数据元素之间的逻辑关系。它是人们根据实际问题的需要和问题本身所含数据之间的内在联系而抽象出来的数学模型，与如何利用计算机存储和处理无关，所以被称为数据的逻辑结构。 由于数据的逻辑结构是数学模型，可以借助数学方法来表示，具体的可以用离散数学中关系代数的二元组表示： Data_Structure =（D，S） 通常取S中的一个关系rj来进行讨论，rj可以表示为数据元素的序偶的集合。如果集合中有序偶，表示数据元素di和dj之间有rj这种关系。 用二元组表示的数据的逻辑结构，有如下的常用术语 （1）前趋结点、后继结点、相邻结点 （2）开始结点、终端结点、内部结点 数据的逻辑结构还能够利用更形象的图形表示,数据的逻辑结构有两大类： （1）线性结构：经典的线性结构是线性表。 线性结构的逻辑特征是：有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋结点和一个后继结点，也就是说结构中的数据元素间存在着一对一的相互关系。 （2）非线性结构：经典的非线性结构有树形结构和图形结构。 树形结构的逻辑特征是：有且仅有一个开始结点，可有若干个终端结点，其余的内部结点都有且仅有一个前趋结点，可以有若干个后继结点，也就是说结构中的数据元素间存在着一对多的层次关系。 图形结构的逻辑特征是：可有若干个开始结点和终端结点，其余的内部结点可以有若干个前趋结点和若干个后继结点，也就是说结构中的数据元素间存在着多对多的网状关系。,表1.1 某校围棋社团学生简表,例1.1 在表1.1中，八名学生按学号从小到大排列，形成一个线性结构。假设表示这种逻辑结构的关系为r1，则r1可以定义为学生按学号顺序递增排列的关系，该线性结构的逻辑结构可用二元组表示为： L =（D，S），r1S D =01，02，03，04，05，06，07，08 r 1 =， ，,图1.1 线性结构的图示,例1.2 在表1.1中，学生之间还存在着领导与被领导关系，其中01号学生为团长，直接领导02和03号学生，他们分别是组长，02号学生直接领导04和05号学生，03号学生直接领导06、07和08号学生，假设表示这种逻辑结构的关系为r2，则r2可以定义为学生之间的领导与被领导关系，该数据结构的逻辑结构可用二元组表示为： T =（D，S），r2S D =01，02，03，04，05，06，07，08 r2 =， ， ,图1.2 树形结构的图示,例1.3 在表1.1中，学生之间还有好友关系，如01和02、03、05号是好友，02和04号是好友，03和05号是好友，04和05、06号是好友，06和07之间是好友，08无好友，假设表示这种逻辑结构的关系为r3，则r3可以定义为学生之间的好友关系，该数据结构的逻辑结构可用二元组表示为： G =（D，S），r3S D =01，02，03，04，05，06，07，08 r3 =，,数据的存储结构 数据的存储结构（Storage Structure），是指数据的逻辑结构到计算机存储器的映射。 对于数据的逻辑结构G =（D，S），在映射中，一方面要将数据集D中的数据元素存放到存储器中，另一方面还要体现关系集S，常见的体现关系S的方式有显示和隐含两种。 常用的实现数据存储结构的方法有如下四种： 1顺序存储 2链接存储 3索引存储 4散列存储 四种存储方法，可以单独使用，也可以组合起来对数据结构进行存储映象。同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。针对具体的应用，某种数据结构选择何种存储结构主要考虑运算的方便及效率。 存储结构的描述：数据的存储结构是数据的逻辑结构用计算机语言的实现，它是依赖于计算机语言的，因此可以借用高级语言中提供的数据类型（如数组、指针等）来描述它。,1顺序存储 基本思想是：把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里。 数据元素间的逻辑关系由存储单元的邻接关系来体现，也就是说逻辑关系上相邻物理位置上也相邻，数据元素的逻辑次序与物理次序一致。这是一种隐含体现关系的存储方法，关系隐含在存储位置上。 数据元素在存储区域中是连续存放的，这种存储方法称为顺序存储结构（Sequential Storage Structure），通常用计算机高级语言中的数组来描述。 2链接存储 基本思想是：通过附加指针域表示数据元素之间的关系。 这种存储方法不要求逻辑上相邻的数据元素存储位置上也相邻，数据元素间的逻辑关系是通过附加指示其他数据元素位置的地址信息（指针）而得到的，这是一种显示体现关系的存储方法。 数据元素在存储区域中可以是连续的，也可以是不连续的，通常用计算机高级语言中的指针来描述，称为链接存储结构（Linked Storage Structure）。 由于不要求存储空间的连续性，很适合动态存储管理,例1.4 用上述两种方法存储有序序列A=（99， 123，134），假设每个数据元素占2个字 节，即一个存储单元为两个字节。,图1.4 关系的映像方法,3索引存储 基本思想是：除了存储数据元素，还要建立一个或若干个附加的索引表来标识数据元素的地址。 索引表中的每一项称为索引项，是用来标识一个或一组数据元素的存储位置。索引项一般形式为（关键字，地址），其中的关键字是用来标识数据元素的数据项。 若每个数据元素对应一个索引项，则该索引表为稠密索引（Dense Index）。若一组数据元素对应一个索引项，则该索引表称为稀疏索引（Sparse Index）。 索引存储方法主要是用于实现快速查找而设计的一种存储方式。 4散列存储 基本思想是：根据数据元素的关键字直接计算出该结点的存储地址，通常称为关键字地址转换法。在此方法中需要设计一个散列函数，以关键字为自变量，散列函数值即为地址。 用这种存储方法设计的存储结构最适合按关键字进行查找，但数据元素之间的关系已经无法在存储结构上体现。,数据的运算 数据的运算（也称操作）是指对数据元素进行加工和处理。 运算的种类很多，具体视应用的要求而设置运算的种类。 对每种数据结构设置一些基本运算（操作），使得不同应用都能通过这些操作实现对数据结构的各种访问，是数据结构中研究的一个重要方面。数据结构的基本操作一般包括查找、插入、删除、更新、排序等。 这些基本运算实际是在抽象的数据上所施加的一系列抽象的操作，所谓抽象的操作，就是不涉及具体的应用，只知道这些操作应该完成的功能，但无须考虑“如何完成”。这些运算的粒度很小，是构造复杂运算的基础。 数据基本运算的定义是基于数据的逻辑结构，每种经典的逻辑结构都有一个运算的集合。 数据的运算是定义在数据的逻辑结构上而实现在数据的存储结构上的 。 数据的运算是通过算法来描述的 。 在讨论任何一种数据结构时，都应该将数据的逻辑结构、数据的存储结构和数据的运算这三方面看成一个整体，不要孤立地理解一个方面，而要注意它们之间的联系,13 算法 算法的概念及特性 算法（Algorithm）是解决特定问题的方法和步骤，是由若干条指令组成的有限序列。 一个算法必须具有以下五个特性： （1）有穷性：对于任意一组合法输入值，一个算法必须总是在执行有穷步骤后结束，有限时间内完成。 （2）确定性：算法中每条指令都确切地规定了所应执行的操作，使算法的执行者或阅读者能明确其含义及如何执行，不致产生二义性或多义性；另外，在同一条件下，一个算法只能有一条执行路径。 （3）可行性：算法中的每一步都是可行的，都可以通过手工或机器可以接受的有限次操作在有限时间内完成。 （4）输入：一个算法有0个或多个输入，这些输入是算法所需的初始量或待处理的对象，来自某个特定的对象集合。 （5）输出：一个算法有1个或多个输出，这些输出与输入有着某种特定的关系。,算法的描述 算法一般可以采用自然语言、程序流程图、伪码、高级程序设计语言等描述。 算法的评价 通常从定性和定量两方面来评价一个算法 算法的定性评价，是从算法的设计者和使用者角度来衡量优劣的 （1）正确性（Correctness）是指算法应当满足具体问题的需求，即对合理的输入，算法都会得出正确的结果，这是设计和评价一个算法的首要条件，否则其他的评价标准也就无从谈起。 （2）可读性（Readablity）是指算法被理解的难易程度。 （3）健壮性（Robustness）是指算法对输入的非法数据恰当地作出反映或进行相应处理的能力。 （4）简单性（Simplicity）是指一个算法所采用的逻辑结构、存储结构以及处理过程的简单程度。,算法的定量评价 （1）时间复杂度（Time Complexity）是一个算法运行时所耗费的系统时间，也就是算法的时间效率。 每条语句重复执行的次数称为语句的频度（Frenquency count） 当不考虑算法运行的软硬件环境时，算法所耗费的时间就是该算法中所有简单语句的频度之和。 一般情况，在讨论算法的时间效率时，主要考虑当问题规模n趋向无穷大时，时间复杂度T(n)的数量级，亦称为算法的渐近时间复杂度，则T(n)= O(f(n) 。 记号“O”是一个数学符号，其数学定义是： 设T(n)和f(n)均为正整数n的函数，若存在两个正整数M和n0，使得当nn0时，都有 | T(n)| M | f(n)| 存在，则T(n)= O(f(n)。,在多数情况下，当一个算法中有若干个循环语句时，算法的时间复杂度是由嵌套循环中最内层循环语句的频度决定的。需要注意的是，如果算法中包括对其他函数或算法的调用，计算算法的时间复杂度时还要分析被调用算法或函数的时间复杂度。,例1.5 求一维数组元素中的最大值 int sum(int a,int n) int i,s; （1） s= a0; /*1次*/ （2） for(i=1;in; i+; ) /*n次*/ （3） if (s ai) s= ai; /*n-1次*/ （4） return s; /*1次*/ T1(n)= 1+n+n-1+1=2n+1 T1(n)=O(n) ，即f(n)=n,例1.6 两个n阶方阵相加 void Matrixadd(int a ,int b ,int c ,int n) int i,j; （1） for (i=0;in;i+) /*n+1次*/ （2） for (j=0;jn;j+) /* n(n+1)次*/ （3） cij=aij+bij; /* n2次*/ T2(n)= n+1+ n(n+1)+ n2=2n2+2n+1 T2(n)=O(n2)，即f(n)=n2,例1.7 求两个n阶方阵的乘积 void Matrixmlt(int a ,int b ,int c ,int n) int i,j,k; （1） for (i=0;in;i+) /*n+1次*/ （2） for (j=0;jn;j+) /* n(n+1)次*/ （3） cij=0; /* n2次*/ （4） for (k=0;kn;k+) /* n2(n+1)次*/ （5） cij= cij+aik*bkj; /* n3次*/ T3(n)= n+1+ n(n+1)+ n2+ n2(n+1)+ n3=2n3+3n2+2n+1 T3(n)= O(n3) ，即f(n)=n3,最好时间复杂度、最坏时间复杂度和平均时间复杂度 例1.8 在一维数组中查找指定的元素 int search(int a,int x,int n) int i; （1） for(i=0;in; i+; ) （2） if (ai=x) ruturn i+1; （3） return 0; 最好时间复杂度为O(1) 最坏时间复杂度为O(n) 平均时间复杂度为O(n)：在查找各个元素概率相等的情况下，平均的比较次数为：（1+2+3+4+(n-1)+n）/n=(n+1)/2，平均时间复杂度为O(n)。,常见的时间复杂度，按数量级从小到大的顺序依次为： 常数级O(1) 对数级O(log2n) 线性级O(n) 线性对数级O（nlog2n） 平方级O（n2） 立方级O(n3) k次方级O(nk) 指数级O(2n) 阶乘级O(n!) 其中指数级O(2n)和阶乘级O(n!)常称为不可实现的算法时间复杂度,空间复杂度（Space Complexity） 空间复杂度（Space Complexity）是一个算法运行时所耗费的存储空间，也就是算法的空间效率。 解决同一个问题的不同算法，占存储空间少的效率高。 一般情况下，算法占用的存储空间包括三个部分：算法本身占的存储空间、算法所处理的数据占的存储空间和算法运行过程中需要的辅助空间。 对解决同一个问题的不同算法，前两个部分所占存储空间差别不会很大，所以在讨论算法的空间复杂度时，只考虑算法运行过程中需要的辅助空间，它也是问题规模n的函数，渐近空间复杂度也简称为空间复杂度。 常见的空间复杂度有：常数级O(1)、对数级O(log2n)、线性级O(n)。,14 学习数据结构的意义和目的,第二章 线性表,21 线性表的定义及运算 211 线性表的定义及逻辑特征 212 线性表上运算的定义 213 线性表的存储结构 22 顺序表 221 顺序表的定义及表示 222 线性表运算在顺序表上的实现 223 顺序表应用举例 23 链表 231 链表的定义及形式 232 单链表 233 循环链表 234 双链表 *235 静态链表 236 单链表的应用举例 24 顺序表和链表的比较,21 线性表的定义及运算 线性表的定义及逻辑特征 线性表（Linear List）:是具有相同属性的n（n0）个数据元素的有限序列。 线性表的长度:数据元素的个数n。当n0时称为空表，即表中不含任何元素。通常将非空的线性表（n0）记为： L =（a1，a2，ai-1，ai，ai+1，an） 线性表是线性结构，它的逻辑特征：有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋和一个后继。对于一个非空的线性表，有且仅有一个表头元素a1，即开始结点，它没有前趋但有后继；对于ai，当 i=2，n-1 时，有且仅有一个前趋 ai-1，有且仅有一个后继 ai+1；有且仅有一个表尾元素an，即终端结点，它无后继有前趋。,第二章 线性表,线性表可以用二元组表示为： linear_list =（D，S），rS， D =a1，a2，ai-1，ai，ai+1，an r =， ， 线性表的逻辑结构图示,通用类型标识符 DataType 来表示数据元素的类型 例：typedef char DataType;,线性表上运算的定义 （1）线性表初始化initList（L）：构造一个空的线性表。 （2）求线性表的长度lengthList（L）：返回线性表L中所含元素的个数。 （3）取第i个元素getElem（L，i）：当1in，返回线性表L中第个元素的值。 （4）按值查找locateElem（L，x）：与表中元素的类型相同，在表L中查找值为的数据元素，若找到，返回L中第一次出现的值为的那个元素的序号，称为查找成功；否则，返回一特殊值（0）表示查找失败。 （5）插入insertElem（L，i，x）：在线性表L的第个位置插入一个值为的新元素，这样使原序号为 i，i+1，的数据元素的序号变为i+1，i+2，n+1，插入后表长等于原表长加1，插入位置可以为1in+1。 （6）删除操作deleteElem（L，i）：在线性表L中删除序号为的数据元素，删除后使序号为 i+1，i+2，n 的元素的序号变为 i，i+1，n-1，新表长等于原表长减，删除位置可以为1in。,线性表的存储结构 顺序存储、链接存储、索引存储、散列存储，这四种方法都可以用来存储线性表。 顺序存储和链接存储是线性表最常用的两种存储方法。 线性表用顺序方式存储就称为顺序表。 线性表用链接方式存储就称为链表。,22 顺序表 顺序表的定义及表示 顺序表（Sequential List）是采用顺序存储结构的线性表。也就是将线性表中逻辑上相邻的结点存储在物理上相邻的单元中，使得线性表的所有元素按逻辑次序依次存放到一组地址连续的存储空间内。 顺序表存储结构用语言描述如下： #define MAXSIZE 1024 typedef int DataType; typedef struct DataType dataMAXSIZE; int last; SeqList; SeqList SL;,线性表的顺序存储结构图示 线性表第个数据元素的地址公式： LOC(ai) = LOC(a1)(i1)k 1in 顺序表L一般定义为SeqList类型的指针变量： SeqList *L =&SL； 用L来引用结构体SeqList类型变量的各个域 线性表的表长为：（*L）last+1 或 L-last+1 线性表中第一个数据元素为： （*L）data0或 L-data0 最后一个元素表示为： （*L）data（*L）last 或 L-dataL-last 第个元素表示为： （*L）datai-1 或 L-datai-1,线性表运算在顺序表上的实现 1. 插入 插入后使原长度为的表 （a1，a2，ai-1，ai，ai+1，an） 成为长度为+1 的表 （a1，a2，ai-1，x，ai，ai+1，an） 算法中的主要步骤： 步骤1：由于是插入运算，首先要检查是否有插入位置，即顺序表是否已满，若顺序表已满（L-last=MAXSIZE1），则产生溢出错误，返回插入失败； 步骤2：在有插入位置的前提下，还要检查插入位置是否合适，即是否满足1in+1，若不满足条件，则插入位置错误，返回插入失败； 步骤3：在步骤1、2都顺利通过的前提下，实现后移操作； 步骤4：插入新结点； 步骤5：将表长加1；返回插入成功。,图2.3 顺序表中插入元素的过程,插入算法的函数如下： int insertElem (SeqList *L,int i,DataType x) int j; if(L-last=MAXSIZE-1) printf(“overflow“); return(0); /*检查表空间是否已满*/ if(iL-last +2) printf(“error“);return 0; /*检查插入位置的正确性*/ for(j=L-last;j=i-1;j-) L-dataj+1=L-dataj; /* 结点后移 */ L-datai-1=x; /*新元素插入*/ L-last + +; /*表长加1，last仍指向最后元素*/ return 1; /*返回插入成功*/ ,时间复杂度分析 最好情况下时间复杂度为O(1) 最坏情况下时间复杂度为O(n) 算法的平均时间复杂度 在长度为的线性表中插入一个元素时所需移动数据元素次数的期望值（平均移动次数）为：,等概率情况下，平均移动次数为：,2.删除 删除后使原表长为的线性表 （a1，a2，ai-1，ai，ai+1，an） 变成长度为1 的线性表 （a1，a2，ai-1， ai+1，an）,图2. 4 顺序表中删除元素的过程,删除算法的函数如下： int deleteElem (SeqList *L,int i) int j; if(iL-last+1) /*检查空表及删除位置的合法性*/ printf (“第%d个元素不存在“,i); return 0; for(j=i;jlast;j+) L-dataj-1=L-dataj; /*向前移动元素*/ L-last -; /*表长减1*/ return 1; /*删除成功*/ 删除时要检查删除位置的有效性，空表和大于表长的位置是不能删除的。 时间复杂度分析 最好情况下时间复杂度为O(1) 最坏情况下时间复杂度为O(n) 在等概率情况下，平均时间复杂度也为(n),3. 按值查找 按值查找算法的函数如下： int LocateElem (SeqList *L, DataType x) int i; for(i=0;ilast ;i+) if( L-datai= x) return i+1; /*返回的是序号*/ return 0; 时间复杂度分析 最好情况下时间复杂度为O(1) 最坏情况下时间复杂度为O(n) 在等概率情况下，平均比较次数为（n+1）/2，平均时间复杂度为O(n)。,23 链表 线性表的顺序存储方法的优缺点 线性表的顺序存储方法有明显的优点： （1）这种方法最简单，最容易被大多数人理解和使用。 （2）可以随机存取表中任一元素，存储位置可以通过一个简单直观的公式来表示，访问元素速度快。 （3）不需要增加额外的空间来表示结点间的逻辑关系，存储利用率高。 线性表的顺序存储方法的弱点： （1）除表尾的位置外，在做插入、删除时需要移动大量数据元素，效率较低。 （2）由于顺序表要求分配一块连续的存储区域，不能利用小块存储区。 （3）一般采用静态存储分配方法。在程序执行前，要预先分配存储空间，当表长变化较大时，难以确定合适的存储规模。若按可能达到的最大长度进行分配，则可能一部分空间不能得到充分利用；若事先对表长估计不足，则插入操作又可能造成表空间的溢出。,链表的定义及形式 链表（Linked List）是采用链接方式存储的线性表。链接存储需要通过附加指针来表示结点之间的关系。 线性表链接存储的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。 数据元素ai的存储映象：对每个数据元素ai来说，除了存储其自身的信息之外，还需要和ai一起存放表示元素间逻辑关系的信息（后继或前趋的指针，即附加的指针域）。这两部分信息组成数据元素ai的存储映象，称为结点（node）。 根据链表附加指针域个数的不同，可以将链表分成不同的形式。 最常用的链表形式是每个结点附加一个指针域，指向后继结点，称为单链表； 如果每个结点附加两个指针域，分别指向前趋结点和后继结点，则称之为双链表； 在单链表上进行简单的改进（利用终端结点的空指针域指向表头）可以得到单循环链表； 在双链表上进行简单的改进（也是利用空指针域）可以得到双循环链表。 根据链表存储空间分配方式的不同，可以将链表分为动态链表和静态链表。,单链表 单链表的定义 单链表中第一个数据元素的存储地址保存在头指针里，而其它数据元素的地址都保存在前趋结点的指针域中，所以整个链表的存取必须从头指针开始 单链表可由头指针唯一确定，通常用 “头指针”来标识一个单链表，如 单链表L是指某链表的头指针为。 例：=（a，b，c，d，e，f，g） 采用单链表存储,单链表结点结构,单链表的存储结构用语言描述如下： typedef struct Node /*结点类型定义*/ DataType data; /*数据域*/ struct Node *next;/*指针域*/ LinkList; LinkList *L，*p； /*定义指针变量*/ 调用标准函数malloc()和free(p)申请和释放空间 申请空间：p =（LinkList *）malloc（sizeof（LinkList）； 释放空间：free(p) 单链表结构的一般形式,假设指针变量p指向单链表中第i个结点，请区分以下几种表示法： p：是一个LinkList *类型的指针，它保存的是数据域为ai的 结 点的首地址； *p：是一个LinkList类型的结构体变量，它的值包括两个分量 p-data和p-next； p-data：是一个DataType类型的变量，表示p所指结点中的 数据域，它的值是元素ai； p-next：是一个LinkList *类型的指针，表示p所指结点的指针域，它的值是数据域为ai+1的结点的首地址，即q=p-next。p-next是指向线性表中第i+1个结点的指针，即p-next-data的值是 ai+1 。同理r=p-next-next，即r=q-next。 p=p-next，它的作用是将p所指结点中的指针域的值赋给指针p，形象的可表示为指针p沿着“链”向后移动了一个结点。,单链表上基本运算的实现 （1）建立单链表- 头插法和尾插法 头插法 基本思想：头插法即在链表的头部插入结点建立单链表。建立单链表从空表开始，重复读入数据，每读入一个数据即向系统申请存储空间建立一个新结点，并将读入的数据存放在新结点的数据域中，然后插在链表的头部，直到读入结束标志-1为止。,头插法建立单链表算法的函数如下： LinkList *createHeadList( ) /*以头插法建立不带头结点的单链表*/ LinkList *L=NULL; /*置空表*/ LinkList *s; int x; /*设数据元素的类型为int*/ scanf(“%d“, /*返回表头指针*/ ,尾插法 基本思想：尾插法是在单链表的尾部插入结点建立单链表。尾插法建立单链表时每次将新结点插入到链表的尾部，此时可设置一个尾指针r，用来指向链表中的尾结点，能够方便的实现将新结点插入到链表的尾部，而不用每次插入时都从头到尾扫描一遍单链表来找到尾结点。,尾插法建立单链表算法的函数如下： LinkList *createTailList( ) /*以尾插法建立不带头结点的单链表*/ LinkList *s, *r , *L; int x; /*设数据元素的类型为int*/ L=NULL; /*置空表*/ r=NULL; scanf(“%d“, ,头结点的作用 头结点的加入使得链表一经建立就非空（至少有头结点），从而解决了“空表”问题。 在第一个结点前插入一个结点，或者删除第一个结点，都与头指针无关，只需修改头结点的指针域即可，与在表的其他位置上的操作完全一致，无须特殊处理。,引入头结点后的头插法和尾插法 尾插法建立带头结点的单链表算法的函数如下： LinkList *createTailList ( ) /*以尾插法建立带头结点的单链表*/ LinkList *L=( LinkList *)malloc(sizeof (LinkList); /*建立头结点，申请结点存储空间*/ LinkList *s, *r=L; /*尾指针指向头结点*/ int x; /*设数据元素的类型为int*/ scanf(“%d“, ,用头插法建立带头结点的单链表，算法的函数如下： LinkList *CreateHeadList( ) /*以头插法建立带头结点的单链表*/ LinkList *L=( LinkList *)malloc(sizeof(LinkList); /*建立头结点，申请结点存储空间*/ LinkList *s; int x; /*设数据元素的类型为int*/ L-next=NULL; /*置空表*/ scanf(“%d“, ,（2）查找运算-按序号查找 和按值查找（即定位） 按序号查找 基本思想：在单链表中查找第个数据元素，需从链表的 头指 针开始，顺着结点的next域依次“走过”前i1个结点， 然后从第i1个结点的指针域中取出第i个结点的地址 返回即可。 按序号查找算法的函数如下： LinkList *getElem(LinkList *L, int i) /*在带头结点的单链表L中查找第i个结点*/ LinkList *p=L; int j=0; /*从头结点开始扫描*/ while (p 在等概率假设下，算法的平均时间复杂度为O(n)，平均查找长度为：,例2.1 求带头结点的单链表的表长。 int lengthList (LinkList *L) /*求带头结点的单链表的表长*/ LinkList * p=L-next; /* p指向表头结点*/ int j=0; while (p) p=p-next; j+ ; /* p所指的是第 j 个结点*/ return j; ,按值查找（即定位） 基本思想：在单链表中查找给定的元素值，需顺着链表的头指针扫描单链表，在扫描过程中，判断当前结点数据域的值是否等于x，若是，返回该结点的指针，查找成功；否则继续扫描下一个结点。如果扫描过程一直进行到表尾，此时p=NULL，表示在单链表中不存在值为的结点，查找失败，返回空（NULL）。 按值查找算法的函数如下： LinkList *locateElem(LinkList *L, DataType x) /*在带头结点单链表L中查找值为x的结点*/ LinkList *p=L-next; while ( p 时间复杂度也是O(n),（3）插入运算 根据给定的初始条件不同，可以分指定结点和指定位置两种情况下进行插入操做。 从给定的插入条件，还可以将插入运算分成前插和后插两种，一般后插比前插更容易。,在指定结点情况下进行插入运算 后插： s=( LinkList *)malloc(sizeof(LinkList)； s-data=x； s-next=p-next； p-next=s;,前插： s=( LinkList *)malloc(sizeof(LinkList)； s-data=x； while (q-next!=p ) q = q -next； s-next=p； q-next=s；,在指定结点时后插运算的函数如下： void insertElemAfNode (LinkList * p, DataType x) /*在带头结点的单链表L中p所指的结点后插入值为x的元素*/ LinkList *s; s=( LinkList *)malloc(sizeof(LinkList)； s-data=x； s-next=p-next； p-next=s; 后插算法的时间复杂度为O(1)。,在指定结点时前插运算的函数如下： void insertElemBeNode ( LinkList *L, LinkList * p, DataType x) /*在带头结点的单链表L中p所指的结点前插入值为x的元素*/ LinkList * q,*s; s=( LinkList *)malloc(sizeof(LinkList); s-data=x; q=L; /*从头结点开始查找结点p的前趋结点q */ while (q-next!=p ) q = q -next; s-next=p; q-next=s; 平均时间复杂度为O(n),在指定位置情况下进行插入运算 若已知结点序号i，在第个结点后或前插入一个数据元素， 也就是在元素ai前或后插入元素，即为给定位置的插入运算。 在第个结点前插入一个数据元素的实现过程,在第个结点前进行插入运算的函数如下： int insertElem ( LinkList *L, int i, DataType x) /*在带头结点的单链表L中第i个元素前插入值为x的元素*/ LinkList * p,*s; int j; p=L; j=0; while (p 在等概率情况下，时间复杂度为O(n)。,例2.2 在带头结点的单链表中值为y的结点前插入值为x的结点。 int inserty_x ( LinkList *L, DataType y, DataType x) /*在带头结点的单链表L中值为y的结点前插入值为x的结点*/ LinkList * p,*q,*s; /* 结点*q为*p的前趋结点*/ p=L-next; q=L; while (p 在等概率情况下，算法的平均时间复杂度为O(n)。,（4）删除运算-在给定结点和给定位置删除 在给定结点情况下进行删除,在给定结点时删除运算的函数如下： void deleteElemNode (LinkList * L, LinkList *p) /*在带头结点的单链表L上删除结点*p */ LinkList *q; q=L; while (q-next!=p ) q = q -next; /*从头结点开始查找结点*p的前趋结点*q */ q-next =p-next; /*q指向结点p的后继结点*/ free(p); /*释放q占用空间 */ 平均时间复杂度为O(n),在给定位置情况下进行删除 在给定位置时删除第个结点运算的函数如下： int deleteElem (LinkList *L, int i, DataType *e) /*在带头结点的单链表L上删除第i个结点*/ LinkList *p,*q; int j; p=L; j=0; while (p-next) 平均时间复杂度为O(n),例2.3 写一算法，删除带头结点的单链表L中的重复结点，即实现如图所示的操作，图（a）为初始的单链表，图（b）为删除重复结点后的单链表。,例2.4 写一算法逆置带头结点的单链表L，要求逆置后的单链表利用L中的原结点，不可以重新申请结点空间。 void reverse (Linklist *L) Linklist *p,*q; /*p为剩余结点形成单链表的头指针，q保存欲插入L头的结点的地址*/ p=L-next; /*p指向第一个数据结点*/ L-next=NULL; /*将原链表置为空表L*/ while (p) q=p; p=p-next; q-next=L-next; /*将当前结点插到头结点的后面*/ L-next=q; ,例2.5 假设有两个带头结点的单链表A、B，按元素值非递减有序，编写算法将A、B归并成一个按元素值非递增有序的链表C，要求链表C利用A、B中的原结点空间，不可以重新申请结点。 LinkList *union(LinkList *A,LinkList *B) LinkList *C, *p,*q,*s; p=A-next;q=B-next; /*p、q分别指向单链表A、B的第一个结点*/ C=A; /*C表的头结点利用A表头结点的空间*/ C-next=NULL; while (p 算法的时间复杂度为O(m+n)。,循环链表 循环链表（Circular Linked List）是利用链表中某些结点的指针域的值为空（NULL）的特点，将空指针域改存一些更有意义的信息而形成的。 在单循环链表上的操作基本与单链表相同，稍微不同的是p，将原来运算中的循环结束条件由判断指针是否为空，变为判断是否等于头指针。 空表的条件是L-next=L而非L-next=NULL。 指针p到达表尾的条件是p-next=L而非p-next=NULL,将指向头结点的指针改为指向尾结点的单循环链表,将指向头结点的指针改为指向尾结点的单循环链表 尾结点的指针为r，头结点的指针为 r-next，链表为空的条件是r-next=r 查找开始结点和尾结点的时间都是O(1),将两个单链表L1、L2合并成一个单链表，即将L2的第一个结点链接到L1的尾结点上 。 操作步骤如下： p= r1 next; /*保存L1 的头结点地址*/ r1-next=r2-next-next; /*把L2链到L1的尾部*/ free(r2-next); /*释放L2的头结点*/ r2-next=p; /*形成循环链表*/,双链表 每个结点附加两个指针域，一个指向后继结点、一个指向前趋结点。由这种结点组成的链表中有两条方向不同的链，因此称为双（向）链表（Double Linked List） 双链表的存储结构用语言描述如下： typedef struct DNode DataType data; struct DNode *prior,*next; DLinkList; DLinkList *L; 双链表的对称特性 ：p-prior-next = p = p-next-prior,带头结点的双循环链表,双链表上的运算 在进行插入、删除操作时，除了要修改后继结点的next域，还需修改前趋结点的prior域 （1）插入 将*s插入到*p的前面，插入过程： s=（DLinkList *）malloc(sizeof(DLinkList); s-data=x; s-prior=p-prior; s-next=p; p-prior-next=s; p-prior=s; 需要注意的是在修改指针的过程中要保证不要断链了 算法的时间复杂度为O(n),双链表上的运算 （2）删除 删除*p，操作如下： p-prior-next=p-next; p-next-prior=p-prior; free(p); 算法的时间复杂度为O(n),24 顺序表和链表的比较 1 逻辑关系的表示 2存储密度 3存储分配方式 4存取方法 5插入、删除操作 6实现语言,第三章 栈和队列,31 栈 32 队列 33 栈与队列的比较,第三章 栈和队列,31 栈 栈的定义及运算 栈（Stack）是运算受限的线性表，限制它的插入和删除操作仅在表的一端进行。 栈顶（Top）,栈顶元素，栈底（Bottom),空栈,进栈或入栈，出栈或退栈。 后进先出的线性表（Last In First Out），简称 LIFO表,栈的基本运算有五种： （1）初始化栈 initStack（s）：构造了一个空栈s。 （2）判栈空empty（s）：若栈s为空栈，返回值为“真” （1），否则返回值为“假”（0）。 （3）入栈push（s，x）：在栈s的顶部插入一个新元素x ， x成为新的栈顶元素。 （4）出栈pop（s）：删除栈s的栈顶元素。 （5）读栈顶元素top（s）：栈顶元素作为结果返回， 不改变栈的状态。,顺序栈及运算的实现 采用顺序方式存储的栈称为顺序栈（Sequential Stack）。 顺序栈用C语言描述如下： #define MAXSIZE 1024 /*栈可能达到的最大容量*/ typedef int DataType; typedef struct DataType dataMAXSIZE; int top; SeqStack ; SeqStack *s; /*定义s是一个指向顺序栈的指针*/,栈的操作及栈顶指针变化情况,在顺序栈上实现五种基本运算的C函数 （1）初始化栈 首先建立栈空间，然后初始化栈顶指针。 SeqStack *initSeqStack() SeqStack *s; s=(SeqStack*)malloc(sizeof(SeqStack); s-top= -1; return s; （2）判栈空 int empty (SeqStack *s) if (s-top= -1) return 1; else return 0; ,在顺序栈上实现五种基本运算的C函数 （3）入栈 int push (SeqStack *s, DataType x) if (s-top=MAXSIZE-1) /*栈满不能入栈*/ printf(“overflow“); return 0; s-top+; s-datas-top=x; return 1; ,在顺序栈上实现五种基本运算的C函数 （4）出栈 void pop (SeqStack *