自考数据结构笔记(超级详细-可做考试条).doc

88更多优质自考资料尽在百度贴吧自考乐园俱乐部（/club/5346389）欢迎加入.欢迎交流.止不住的惊喜等着你. 自考数据结构笔记(详尽版) 感谢热心自考人：liuii322 笔记特点：图例丰富，超级详细，几乎涵盖本课程所有要求掌握的知识点，。用于复习和做小条概论- 学习数据结构的意义5概论- 算法的描述和分析(一)5线性表 - 链式存储结构- 单链表的运算（一）14三 栈和队列 - 栈 - 栈的定义及基本运算22三栈和队列 - 队列 - 队列的定义及基本运算25三栈和队列 - 队列 - 顺序队列25栈和队列 - 队列 - 链队列26三栈和队列 - 栈和队列的应用实例 - 栈的应用实例（一）27四串的基本概念（一）30图 - 图的概念（一）63图 - 图的存储结构 - 邻接矩阵表示法67图 - 图的遍历 - 深度优先遍历（一）72图 - 图的遍历 - 广度优先遍历 （一）75图 - 生成树和最小生成树 - 生成树77图 - 生成树和最小生成树 - 最小生成树（一）79图 - 最短路径 （一）82图 - 拓扑排序 （一）84排序 - 排序基本概念 （一）86排序 - 插入排序 - 直接插入排序（一）87排序 - 插入排序 - 直接插入排序（二）88排序 - 插入排序 - 希尔排序89排序 - 交换排序 - 冒泡排序（一）90排序 - 交换排序 - 快速排序 （一）92排序 - 选择排序 - 堆排序（一）96排序 - 归并排序（一）98排序 - 分配排序 - 基数排序101排序 - 各种内部排序方法的比较和选择（一）102查找 - 查找的基本概念103查找-线性表的查找-顺序查找104查找 - 线性表的查找 - 二分查找（一）105查找 - 线性表的查找 - 分块查找107查找 - 树上的查找 - 二叉排序树（一）109查找 - 树上的查找 - 树114查找 - 散列技术 - 散列表的概念121查找 - 散列技术 - 散列函数的构造方法122文件 - 文件的基本概念（一）123文件 - 顺序文件125文件 - 索引文件（一）126文件 - 索引顺序文件 - ISAM文件（一）127文件 - 索引顺序文件 - VSAM文件 （一）130文件 - 散列文件131文件 - 多关键字文件 - 多重表文件132文件 - 多关键字文件 - 倒排文件133概论-基本概念和术语数据：数据：指能够被计算机识别、存储和加工处理的信息载体。数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。数据结构：指的是数据之间的相互关系，即数据的组织形式。1数据结构一般包括以下三方面内容： 数据元素之间的逻辑关系，也称数据的逻辑结构；数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 数据元素及其关系在计算机存储器内的表示称数据的存储结构； 数据的运算，即对数据施加的操作。数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。（1）逻辑结构：表中每一行是一个数据元素(或记录、结点)，由学号、姓名等数据项组成。数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点称直接前趋最多只有一个； （2）存储结构：该表的存储结构是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是用指针将这些结点链接在一起？2数据的逻辑结构分类：逻辑结构简称为数据结构。 （1）线性结构：逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前 趋和一个直接后继。 线性表,栈,队列,串等都是线性结构。（2）非线性结构：逻辑特征是：一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 3数据的四种基本存储方法（1）顺序存储方法：该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。（如数组）（2）链接存储方法：该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称链式存储结构,通常借助于程序语言的指针类型描述。（3）索引存储方法：该方法通常在储存结点信息的同时，还建立附加的索引表。 索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。索引项的一般形式是：(关键字、地址)关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。（4）散列存储方法：根据结点关键字直接计算出该结点存储地址。 四种存储方法可单独使用也可组合起来对数据结构进行存储映像。 同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。4数据结构三方面的关系：数据的逻辑结构、存储结构及数据的运算这三方面是一个整体。存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠不同数据结构名称来标识。 【例】线性表是一种逻辑结构，用顺序方法的存储表示，称其为顺序表；用链式存储方法，称为链表；用散列存储方法，称为散列表。数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。按值是否可分解，可将数据类型划分为两类：原子类型：其值不可分解。通常是由语言直接提供。结构类型：其值可分解为若干个成分（或称为分量）。抽象数据类型（简称ADT）：是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。抽象数据类型可以看作是描述问题的模型，它独立于具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在ADT里定义的某些操作来访问其中的数据，从而实现信息隐藏。ADT和类的概念实际上反映了程序或软件设计的两层抽象：ADT相当于是在概念层（或称为抽象层）上描述问题，而类相当于是在实现层上描述问题。不采用ADT的形式来描述数据结构 概论- 学习数据结构的意义1 计算机处理问题的分类 （1）数值计算问题 （2）非数值性问题 2非数值问题求解 瑞士计算机科学家沃思教授曾提出： 算法+数据结构=程序 数据结构是数据的逻辑结构和存储结构，算法是对数据运算的描述 概论- 算法的描述和分析(一) 数据的运算通过算法(Algorithm)描述 1算法 ：非形式地说，算法是任意一个良定义的计算过程。它以一个或多个值作为输入，并产生一个或多个值作为输出。（1）一个算法可以被认为是用来解决一个计算问题的工具。 （2）一个算法是一系列将输入转换为输出的计算步骤。 2算法的描述 ；一个算法可以用自然语言、计算机程序语言或其它语言来说明，惟一的要求是该说明必须精确地描述计算过程。 描述算法最合适的语言是介于自然语言和程序语言之间的伪语言。算法分析 算法分析的目的是（评价算法的效率）1评价算法好坏的标准：首先应是正确的。此外主要考虑三点： 执行算法所耗费的时间；执行算法所耗费的存储空间，主要考虑辅助存储空间；算法应易于理解，易于编码，易于调试等。 算法的效率分为时间效率和空间效率真3算法的时间性能分析 （1）算法所耗费的时间=算法中每条语句的执行时间之和 每条语句的执行时间=语句的执行次数(即频度)语句执行一次所需时间的乘积。【例】求两个n阶方阵的乘积 C=AB,其算法如下: # define n 100 / n 可根据需要定义,这里假定为100 void MatrixMultiply(int Aa，int B nn，int Cnn) int i ,j ,k; (1) for(i=0; in;j+) n+1 (2) for (j=0;jn;j+) n(n+1) (3) Cij=0; n 2 (4) for (k=0; kn; k+) n 2 (n+1) (5) Cij=Cij+Aik*Bkj; n 3 该算法中所有语句的频度之和为： T(n)=2n 3 +3n 2 +2n+1 分析：算法MatrixMultiply的时间耗费T(n)是矩阵阶数n的函数。 （2）问题规模和算法的时间复杂度 算法求解问题的输入量称为问题的规模(Size),用一个整数表示。 【例】一个图论问题的规模则是图中的顶点数或边数。 一个算法的时间复杂度(也称时间复杂性)T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。 【例3】算法MatrixMultidy的时间复杂度T(n)如(1.1)式所示，当n趋向无穷大时，显然有 当n充分大时，T(n)和n 3 之比是一个不等于零的常数。即T(n)和n 3 是同阶的，或者说T(n)和n 3 的数量级相同。记作T(n)=O(n 3)是算法MatrixMultiply的渐近时间复杂度。 数学符号O的严格的数学定义： 若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n)表示存在正的常数C和n0，使得当nn0时都满足0T(n)Cf(n)。 （3）渐进时间复杂度评价算法时间性能 ：主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。 将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。 当有若干个循环语句时，算法的时间复杂度由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。 （4）算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。 【例312】在数值A0.n-1中查找给定值K的算法大致如下： (1)i=n-1; (2)while(i=0&(Ai!=k) (3) i-; (4)return i; 此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关: 若A中没有与K相等的元素，则语句(3)的频度f(n)=n； 若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。 （5） 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。 常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(log 2 n)、线形阶0(n)、线形对数阶0(nlog 2 n)、平方阶0(n 2 )立方阶0(n 3 )、k次方阶0(n k )、指数阶0(2 n )。 一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。算法的时间复杂度和空间复杂度合称为算法的复杂度。 线性表的逻辑结构 线性表的逻辑定义线性表是由n个数据元素（结点）a1，a2，an组成的有限序列。线性表的逻辑结构特征（对于非空的线性表:）仅有一个开始结点a1，没有直接前趋，仅有一个直接后继a2；仅有一个终结结点an，没有直接后继，仅有一个直接前趋an-1； 其余的内部结点ai都有且仅有一个直接前趋和一个直接后继。常见的线性表的基本运算1 InitList（L） ：构造一个空的线性表L，即表的初始化。2 ListLength（L） ：求线性表L中的结点个数，即求表长。3 GetNode（L，i） ：取线性表L中的第i个结点，1iListLength(L)4LocateNode（L，x）：在L中查找值为x 的结点,并返回x在L中的位置。若L中没结点的值为x，返回个特殊值表示查找失败。5InsertList（L，x，i）：在表L的第i个位置上插入一个值x 6 DeleteList（L，i） ：删除线性表L的第i个结点 顺序表1顺序表的定义：用顺序存储方法存储的线性表。(随机存取结构)(1) 顺序存储方法：即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。2 结点ai 的存储地址： 设线性表中所有结点类型相同，每个结点占用存储空间大小亦相同。假设每个结点占用c个存储单元，其中第一个单元的存储地址则是该结点的存储地址，并设开始结点a1的存储地址（简称基地址）是LOC（a1），那么结点ai的存储地址LOC（ai）可通过下式计算：LOC（ai）= LOC（a1）+（i-1）*c 1in3顺序表类型定义 #define ListSize 100 /表空间的大小假设为100 typedef int DataType; /DataType的类型假设为int typedef struct DataType dataListSize；/向量data用于存放表结点 int length；/当前的表长度 SeqList； 注意：用结构类型来定义顺序表类型。 存放线性表结点的向量空间的大小ListSize应仔细选值，既满足表结点的数目动态增加需求，又不致于过大浪费存储空间。 若L是SeqList类型的顺序表，则线性表的开始结点a1和终端结点an分别存储在Ldata0和LDataLlength-1中。 若L是SeqList类型的指针变量，则a1和an分别存储在L-data0和L-dataL-length-1中。4顺序表的特点 顺序表是用向量实现的线性表，向量的下标可以看作结点的相对地址。顺序表的的特点是逻辑上相邻的结点其物理位置亦相邻。顺序表上实现的基本运算1.表的初始化: void InitList（SeqList *L）顺序表的初始化即将表的长度置为0 L-length=0；2.求表长 : int ListLength（SeqList *L）求表长只需返回L-length return L-length3.取表中第i个结点 只需返回L-datai-1即可 DataType GetNode（L，i） if (i L-length-1) Error(position error)； return L-datai-1；5. 插入（1） 插入运算的逻辑描述线性表的插入运算是指在表的第i（1in+1）个位置上，插入一个新结点x，使长度为n的线性表变成长度为n+1的线性表注意： 由于向量空间大小在声明时确定，当L-lengthListSize时，表空间已满，不可再做插入操作（2） 顺序表插入操作过程在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此将表中位置为n上的结点，依次后移到位置n+1上，空出第i个位置，然后在该位置上插入新结点x。仅当插入位置i=n+1时，才无须移动结点，直接将x插入表的末尾。（3）具体算法描述 void InsertList(SeqList *L，DataType x，int i) /将新结点 x插入L所指的顺序表的第i个结点ai的位置上 int j; if (iL-length+1) Error(position error);/非法位置，退出运行 if (L-length=ListSize) Error(overflow); /表空间溢出，退出运行 for(j=L-length-1;j=i-1;j-) L-dataj+1=L-dataj;/结点后移 L-datai-1=x; /插入x L-Length+; /表长加1 （4）算法分析 问题的规模： 表的长度L-length（设值为n）是问题的规模。 移动结点的次数由表长n和插入位置i决定： 算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1。 当i=n+1：移动结点次数为0，即算法在最好时间复杂度是0(1)当i=1：移动结点次数为n，即算法在最坏情况下时间复杂度是0(n) 移动结点的平均次数Eis(n)：其中：在表中第i个位置插入一个结点的移动次数为n-i+1，pi表示在表中第i个位置上插入一个结点的概率。不失一般性，假设在表中任何合法位置（1in+1）上的插入结点的机会是均等的，则p1=p2=pn+1=1/(n+1)因此，在等概率插入的情况下， 即在顺序表上进行插入运算，平均要移动一半结点6 删除（1）删除运算的逻辑描述 线性表的删除运算是指将表的第i（1in）个结点删去，使长度为n的线性表变成长度为n-1的线性表（2）顺序表删除操作过程 在顺序表上实现删除运算必须移动结点，才能反映出结点间的逻辑关系的变化。若i=n，则只要简单地删除终端结点，无须移动结点；若1in-1，则必须将表中位置i+1，i+2，n的结点，依次前移到位置i，i+1，n-1上，以填补删除操作造成的空缺。（3）具体算法描述 void DeleteList(SeqList *L,int i) /从L所指的顺序表中删除第i个结点ai int j; if(iL-length) Error(position error); /非法位置 for(j=i;jlength-1;j+) L-dataj-1=L-dataj; /结点前移 L-length-; /表长减小 （4）算法分析结点的移动次数由表长n和位置i决定： i=n时，结点的移动次数为0，即为0(1) i=1时，结点的移动次数为n-1，算法时间复杂度分别是0(n)移动结点的平均次数EDE(n) 其中： 删除表中第i个位置结点的移动次数为n-i，pi表示删除表中第i个位置上结点的概率。不失一般性，假设在表中任何合法位置（1in）上的删除结点的机会是均等的，则 p1=p2=pn=1/n因此，在等概率插入的情况下，顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是0(n)。 单链表1、链接存储方法：链接方式存储的线性表简称为链表。链表的具体存储表示为： 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的） 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针或链）注意：链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。2、链表的结点结构datanextdata域-存放结点值的数据域next域-存放结点的直接后继的地址（位置）的指针域（链域）注意： 链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。 每个结点只有一个链域的链表称为单链表。【例】线性表（bat，cat，eat，fat，hat，jat，lat，mat）的单链表示如示意图3、头指针head和终端结点指针域的表示 单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。注意：链表由头指针唯一确定，单链表可以用头指针的名字来命名。【例】头指针名是head的链表可称为表head。终端结点无后继，故终端结点的指针域为空，即NULL。4、单链表的一般图示法 由于我们常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用箭头来表示链域中的指针，线性表（bat，cat，fat，hat，jat，lat，mat）的单链表就可以表示为下图形式。单链表一般图未法5、单链表类型描述 typedef char DataType; /假设结点的数据域类型为字符 typedef struct node /结点类型定义 DataType data; /结点的数据域 struct node *next;/结点的指针域 ListNode; typedef ListNode *LinkList; ListNode *p; LinkList head; 注意：LinkList和ListNode *是不同名字的同一个指针类型（命名的不同是为了概念上更明确） LinkList类型的指针变量head表示它是单链表的头指针 ListNode *类型的指针变量p表示它是指向某一结点的指针6、指针变量和结点变量指针变量P（值是结点地址）和结点变最*P（值是结点内容）关系指针变量结点变量定义在变量说明部分显式定义在程序执行时,通过标准函数malloc生成取值非空时,存放某类型结点的地址实际存放结点各域内容操作方式通过指针变量名访问通过指针生成,访问和释放生成结点变量的标准函数：p=( ListNode *)malloc(sizeof(ListNode)；/函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中释放结点变量空间的标准函数： free(p)；/释放p所指的结点变量空间结点分量的访问 ：利用结点变量的名字*p访问结点分量方法一：(*p).data和(*p).next 方法二：p-data和p-next指针变量p和结点变量*p的关系 ：指针变量p的值结点地址 结点变量*p的值结点内容 (*p).data的值p指针所指结点的data域的值 (*p).next的值*p后继结点的地址*(*p).next)*p后继结点注意： 若指针变量p的值为空（NULL），则它不指向任何结点。此时，若通过*p来访问结点就意味着访问一个不存在的变量，从而引起程序的错误。线性表 - 链式存储结构- 单链表的运算（一）单链表的运算 1、建立单链表 假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符n为输入条件结束标志符。动态地建立单链表的常用方法有如下两种： （1） 头插法建表 算法思路：从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表头上,直到读入结束标志为止。 注意：头插法建表生成的链表的结点次序与输入顺序相反。 具体算法实现 LinkList CreatListF(void) /返回单链表的头指针 char ch; LinkList head;/头指针 ListNode *s; /工作指针 head=NULL; /链表开始为空 ch=getchar(); /读入第1个字符 while(ch!=n) s=(ListNode *)malloc(sizeof(ListNode);/生成新结点 s-data=ch; /将读入的数据放入新结点的数据域中 s-next=head; head=s; ch=getchar(); /读入下一字符 return head; 2） 尾插法建表 算法思路：从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志为止。 注意：1.必须增加一个尾指针r,使其始终指向当前链表的尾结点2.采用尾插法建表，生成的链表中结点的次序和输入顺序一致 具体算法实现 LinkList CreatListR(void) /返回单链表的头指针 char ch; LinkList head;/头指针 ListNode *s,*r; /工作指针 head=NULL; /链表开始为空 r=NULL;/尾指针初值为空 ch=getchar(); /读入第1个字符 while(ch!=n) s=(ListNode *)malloc(sizeof(ListNode);/生成新结点 s-data=ch; /将读入的数据放入新结点的数据域中 if (head!=NULL) head=s;/新结点插入空表 else r-next=s;/将新结点插到*r之后 r=s;/尾指针指向新表尾 ch=getchar(); /读入下一字符 /endwhile if (r!=NULL) r-next=NULL;/对于非空表，将尾结点指针域置空head=s; return head; 注意：开始结点插入的特殊处理 ：由于开始结点的位置是存放在头指针(指针变量)中,而其余结点的位置是在其前趋结点的指针域中，插入开始结点时要将头指针指向开始结点。 空表和非空表的不同处理 ：若读入的第一个字符就是结束标志符,则链表head是空表,尾指针r亦为空,结点*r不存在;否则链表head非空,最后一个尾结点*r是终端结点,应将其指针域置空。 （3） 尾插法建带头结点的单链表 头结点及作用 头结点是在链表的开始结点之前附加一个结点。它具有两个优点: 由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理; 无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了带头结点的单链表 注意： 头结点数据域的阴影表示该部分不存储信息。在有的应用中可用于存放表长等附加信息。 尾插法建立带头结点单链表算法 LinkList CreatListR1(void) /用尾插法建立带头结点的单链表 char ch; LinkList head=(ListNode *)malloc(sizeof(ListNode);/生成头结点 ListNode *s,*r; /工作指针 r=head; / 尾指针初值也指向头结点 while(ch=getchar()!=n) s=(ListNode *)malloc(sizeof(ListNode);/生成新结点 s-data=ch; /将读入的数据放入新结点的数据域中 r-next=s; r=s; r-next=NULL;/终端结点的指针域置空，或空表的头结点指针域置空 return head; 注意： 上述算法里，动态申请新结点空间时未加错误处理，这对申请空间极少的程序而言不会出问题。但在实用程序里，尤其是对空间需求较大的程序，凡是涉及动态申请空间，一定要加入错误处理以防系统无空间可供分配。 （4） 算法时间复杂度 以上三个算法的时间复杂度均为0(n)。 2.单链表的查找运算 （1）按序号查找 链表不是随机存取结构 ： 在链表中，即使知道被访问结点的序号i，也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构。 查找的思想方法 ： 计数器j置为0后，扫描指针p指针从链表的头结点开始顺着链扫描。当p扫描下一个结点时，计数器j相应地加1。当j=i时，指针p所指的结点就是要找的第i个结点。而当p指针指为null且ji时，则表示找不到第i个结点。 注意： 头结点可看做是第0个结点。 具体算法实现 ListNode* GetNode(LinkList head,int i) /在带头结点的单链表head中查找第i个结点，若找到（0in）， /则返回该结点的存储位置，否则返回NULL。 int j; ListNode *p; p=head;j=0;/从头结点开始扫描 while(p-next&jnext为NULL或i=j为止p=p-next; j+; if(i=j) return p;/找到了第i个结点 else return NULL;/当i0时，找不到第i个结点 在等概率假设下，平均时间复杂度为： 0(n)（2） 按值查找 思想方法 ：从开始结点出发，顺着链逐个将结点的值和给定值key作比较，若有结点的值与key相等，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。 具体算法实现 ListNode* LocateNode (LinkList head,DataType key) /在带头结点的单链表head中查找其值为key的结点 ListNode *p=head-next;/从开始结点比较。表非空，p初始值指向开始结点while(p&p-data!=key)/直到p为NULL或p-data为key为止p=p-next;/扫描下一结点 return p;/若p=NULL，则查找失败，否则p指向值为key的结点 算法时间复杂度：以上二个算法的时间复杂度均为0(n)。3.插入运算 （1）思想方法：插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到a i-1 与a i 之间。 步骤： （1）找到a i-1存储位置p （2）生成一个数据域为x的新结点*s （3）令结点*p的指针域指向新结点（4）新结点的指针域指向结点a i （2）具体算法实现 void InsertList(LinkList head,DataType x,int i) /将值为x的新结点插入到带头结点的单链表head的第i个结点的位置上ListNode *p; p=GetNode(head,i-1);/寻找第i-1个结点 if (p=NULL)/in+1时插入位置i有错 Error(position error)； s=(ListNode *)malloc(sizeof(ListNode); s-data=x;s-next=p-next;p-next=s; （3）算法分析 算法的时间主要耗费在查找操作GetNode上，时间复杂度为O(n)4.删除运算 （1）思想方法 ：删除运算是将表的第i个结点删去。 步骤： （1）找到a i-1 的存储位置p（因为在单链表中结点a i 的存储地址是在其直接前趋结点a i-1 的指针域next中） （2）令p-next指向a i 的直接后继结点（即把a i 从链上摘下） （3）释放结点a i 的空间，将其归还给存储池。 （2）具体算法实现 void DeleteList(LinkList head,int i) /删除带头结点的单链表head上的第i个结点 ListNode *p,*r; p=GetNode(head,i-1);/找到第i-1个结点 if (p=NULL|p-next=NULL)/in时，删除位置错 Error(position error);/退出程序运行 r=p-next;/使r指向被删除的结点a i p-next=r-next;/将a i 从链上摘下 free(r);/释放结点a i 的空间给存储池 注意：设单链表的长度为n，则删去第i个结点仅当1in时是合法的。 当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在（即p！=NULL）且*p不是终端结点（即p-next！=NULL）时，才能确定被删结点存在。 （3）算法分析 ：算法的时间复杂度也是O（n）。 链表上实现的插入和删除运算，无须移动结点，仅需修改指针。 循环链表1、循环链表：循环链表是一种首尾相接的链表（1）单循环链表在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。（2）多重链的循环链表将表中结点链在多个环上。2、带头结点的单循环链表注意：判断空链表的条件是head=head-next;3、仅设尾指针的单循环链表 用尾指针rear表示的单循环链表对开始结点a1和终端结点an查找时间都是O(1)。而表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。注意：判断空链表的条件为rear=rear-next;4、循环链表的特点：无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。【例】在链表上实现将两个线性表（a1，a2，an）和（b1，b2，bm）连接成一个线性表（a1，an，b1，bm）分析：若在单链表或头指针表示的单循环表上做这种链接操作，都需要遍历第一个链表，找到结点an，然后将结点b1链到an的后面，其执行时间是O(n)。若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O(1)。两个单循环链表的链接操作示意图 相应的算法如下： LinkList Connect(LinkList A,LinkList B) /假设A，B为非空循环链表的尾指针 LinkList p=A-next;/保存A表的头结点位置 A-next=B-next-next;/B表的开始结点链接到A表尾 free(B-next);/释放B表的头结点 B-next=p;/ return B;/返回新循环链表的尾指针 注意：循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。 在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。双链表1、双向链表：双链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。（A）结点结构 （B）空的双循环链表（C）非空的双循环链表双链表示意图（如上图ABC）注意：双链表由头指针head惟一确定的。 带头结点的双链表的某些运算变得方便。 将头结点和尾结点链接起来，为双（向）循环链表。2、双向链表的结点结构和形式描述结点结构(见上图a)形式描述 typedef struct dlistnode DataType data; struct dlistnode *prior,*next; DListNode; typedef DListNode *DLinkList; DLinkList head;双向循环链表结构的对称性可描述为：P-prior-next=p=p-next-prior3、双向链表的前插和删除本结点操作由于双链表的对称性，双链表中能方便地完成各种插入、删除操作。双链表的前插操作 void DInsertBefore(DListNode *p,DataType x) /在带头结点的双链表中，将值为x的新结点插入*p之前，设pNULL DListNode *s=malloc(sizeof(DListNode);/ s-data=x;/ s-prior=p-prior;/ s-next=p;/ p-prior-next=s;/ p-prior=s;/ 双链表上删除结点*p自身的操作 void DDeleteNode(DListNode *p) /在带头结点的双链表中，删除结点*p，设*p为非终端结点 p-prior-next=p-next;/ p-next-prior=p-prior;/ free(p);/ 注意：与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。 上述两个算法的时间复杂度均为O(1)。顺序表和链表的比较顺序表链表基于空间考虑分配方式静态分配,程序执行之前必须明确规定存储规模,若线性表长度N变化较大,则存储规模难于预先确定估计过大将造成空间浪费,估计太不又将使空间溢出机会增多动态分配只要内存空间尚有空闲,就不会产生溢出.因此,当其线性表的长度变化较大,难以估计其存储规模时,以采用动态链表作为存储结构为好存储密度为1.当线性表的长度变化不大,易于事先确定其大小时,为了节约存储空间,宜采用顺序表作为存储结构.1基于时间考虑存取方法随机存取结构,对表中任一结点都可在0(1)时间内直接取得,线性表的操作主要是进行查找,很少做插入和删除操作时,采用顺序表做存储结构为宜.顺序存取结构,链表中的结点,需从头指针起顺着链扫描才能取得.插入删除操作在顺序表中进行插入和删除,平均要移动表中近一半的结点,尤其是当每个结点的信息一较大时,移动结点的时间开销就相当可观在链表中的任何位置上进行插入和删除,都只需要修改指针,对于频繁进行插入和删除的线性表,宜采用链表做存储结构.若表的插入和删除主要发生在表的首尾两端,则采用尾指针表示的单循环链表为宜存储密度是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即存储密度=（结点数据本身所占的存储量）/（结点结构所占的存储总量）三 栈和队列 - 栈 - 栈的定义及基本运算栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故称为运算受限的线性表。 栈的定义及基本运算 1、栈的定义 栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。 (1)通常称插入、删除的这一端为 栈顶，另一端称为 栈底。 (2)当表中没有元素时称为 空栈 。 (3)栈为后进先出的线性表，简称为 LIFO表 。 2、栈的基本运算 （1）InitStack（S）：构造一个空栈S。 （2）StackEmpty（S）： 判栈空。（3）StackFull（S）：判栈满。若