数据结构与算法课件

算法与数据结构刘楚雄第一章绪论第六章字典与检索第二章线性表第七章排序第三章串第五章树与二叉树第八章图第四章栈和队列第九章算法分析与设计第十章稀疏矩阵与广义表教学大纲算法设计的重要性：例1：从n个数中找出第k大的那个数

例2：百钱买百鸡问题第一章绪论程序设计的要求：1。正确性2。有效性3。可维护性4。可靠性5。可重用性〔包括可移植性〕6。简明性数学代数系统编码理论算子关系数据类型数据表示法数据的运算数据结构数据存取机器组织文件系统数据组织信息检索存储装置硬件（计算机系统设计）软件（计算机程序设计）“数据结构〞所处的地位用计算机解决问题的步骤：问题分析：这阶段的任务是弄清所要解的问题是什么； 并且把它用一种语言〔自然语言、说明语言或数 学语言〕清楚地描述出来。算法设计：这阶段的任务是建立程序系统的结构，重点 是算法的设计和数据结构的设计。对于大型的复 杂的程序系统，这一阶段往往还包括模块的设计。程序设计：采用适当的程序设计语言，编写出可执行的 程序。程序测试和维护：发现和排除在前几个阶段中产生的错 误，经测试通过的程序便可投入运行，在运行过 程中还可能发现隐含的错误和问题，因此还必须 在使用中不断维护和完善。1.1问题求解问题分析例如为了设计一个交通信号灯的管理系统，首先需要分析一下所有车辆的行驶路线的冲突问题。这个问题可以归结为对车辆的可能行驶方向作某种分组，对分组的要求是使任一个组中各个方向行驶的车辆可以同时平安行驶而不发生碰撞。根据这个路口的实际情况可以确定13个可能通行方向：A→B，A→C，A→D，B→A，B→C，B→D，D→A，D→B，D→C，E→A，E→B，E→C，E→D。可以把A→B简写成AB，用一个结点表示，在不能同时行驶问题分析的结点间画一条连线(表示它们互相冲突)，便可以得到如右图所示的表示。这样得到的表示可以称之为“图〞。如果把上图中的一个结点理解为一个国家，结点之间的连线看作两国有共同边界，上述问题就变成著名的“着色问题〞：即求出最少要几种颜色可将图中所有国家着色，使得任意两个相邻的国家颜色都不相同。通过上面的分析，我们就获得了该交通管系统的数学模型，下面就可以着手进行算法的设计。程序设计一、算法设计 1。穷举法 2。贪心法二、程序设计

首先，为问题中所有有关数据设计适当的表示形式，不仅包括需要表示的结点和连接，可能还有为计算过程的实现而用的辅助性数据结构。然后选择一种适当的程序设计语言实现这些数据结构，并在设计好的数据结构上精确地描述上面提出的算法，完成一个程序，使之能在计算机上运行。假设需要着色的图是G，集合V1包括图中所有未被着色的结点，着色开始时V1是G所有结点集合。NEW表示已确定可以用新颜色着色的结点集合。从G中找出可用新颜色着色的结点集的工作可以用下面的程序框架描述：

置NEW为空集合;for每个vV1doifv与NEW中所有结点间都没有边从V1中去掉v;将v参加NEW;这个程序片段里涉及对集合和图的操作，包括由集合中去掉一个元素，向集合里增加一个元素，检查两个结点之间在图中是否有边连接等。有了这些结构和操作，程序的实现非常简单。但是，常见程序设计语言并不直接支持图和集合等数据结构，通常只提供了一些根本数据类型(例如整数、实数、字符等)和一些数据构造手段(例如数组、记录、指针等)。要解决这个计算问题，我们必须自己用选定的语言所提供的机制实现这些结构(集合、图等)和操作(对集合的元素增删、对图的边的判断等)，这些正是本课程将要讨论的根本内容。1.2数据结构

数据结构主要关心的是下面三个方面：1。结构中各元素之间的逻辑关系 线性结构：如图书馆的书目索引

树形结构：

图形结构：2。结构中各元素的存储方式3。结构具有的行为特征例2：问题：计算机和人对弈模型：树形结构树形结构返回例3：问题：多叉路口交通灯的管理模型：图形结构图形结构返回数据(Data)：在计算机科学中是至所有能输入到计算机中并 被计算机程序处理的符号的总称。数据元素(DataElement)：数据的根本单位，在计算机程序 中通常作为一个整体进行考虑和处理。一个数据元素可以由假设干个数据项(DataItem)组成。数据对象(DataObject)：是性质相同的数据元素的集合。数据结构(DataStructure)：是相互之间存在一种或多种特 定关系的数据元素的集合。逻辑结构：表示数据元素之间的逻辑关系。物理结构：数据结构在计算机中的表示〔影响〕，又称存 储结构。数据类型〔DataType)：是一个值的集合和定义在这个值 集上的一组操作的总称。原子类型(AtomType)结构类型(StructureType)作用：实现信息的隐蔽抽象数据类型(AbstractDataType)：是数据类型的延伸。 是一个三元组(D,S,P)。在计算机中的表示：数据元素数据项（节点）(DataElement)(DataItem)orNode)元素数据域（Element)(DataField)映象映象本课程涉及的主要结构线性表：线性表是一种逻辑上十分简单但应用非常广泛的数据结构，线性表中各元素之间是一种简单的“线性〞关系。顺序表和链表是两种常用的实现线性表的数据结构，它们也是许多复杂结构的根本表示形式。

字符串：字符串也是一种特殊的线性结构，它以字符为元素。本书中讨论的字符串，主要采用顺序表示的形式，因此每个字符可以直接访问。

堆栈与队列：堆栈和队列是两种十分重要的数据结构。堆栈元素的存入和取出按照后进先出原那么，最先取出的总是在此之前最后放进去的那个元素；而队列实现先进先出的原那么，最先到达的元素也最先离开队列。树与二叉树：树和二叉树都属“树形结构〞，在逻辑上表示了结点的层次关系，是一种非线性结构。树最上面一层只有一个元素，称为“树根〞。每个元素可以有假设干相关联的下层元素，这些元素被称为是该上层元素的“子结点〞；每个下层元素至多有一个对应的上层元素，称为它的“父结点〞。许多实际的和理论的问题中都可以抽象出某种树形结构来。

字典：字典可以看作是一种二元组的集合，每个二元组包含着一个关键码和一个值。抽象地看，一个字典就是由关键码集合到值集合的一个映射。按关键码进行检索是字典中最常用的操作。根据对字典中进行元素插入、删除频率的不同，有所谓“动态字典〞和“静态字典〞之分。“散列表〞是实现字典的有效结构，散列表的主要特点是可以实现对大量离散元素的有效存储和快速访问。由于树形结构便于灵活地执行插入和删除，所以经常用来表示动态字典。

图：图是一种较复杂的结构，它包括一个结点集合和一个边集合，边集合中每条边联系着两个结点。信息可以存储在结点里，也可以存储在边里。许多实际问题中的数据可以用图表示，如公路网络、通信网络、不同事物间的联系，等等。

1.3算法算法是为实现某个计算过程而规定的根本动作的执行序列。重要特性：〔1〕有穷性〔2〕确定性〔3〕可行性〔4〕输入〔5〕输出设计要求〔1〕正确性a.不含语法错b.对于机组数据能够输出正确结果c.对于典型、苛刻数据能得出正确结果d.对于一切合法数据能得出正确结果〔2〕可读性〔3〕健壮性〔4〕效率与低存储量要求在实际应用中，算法的表现形式千变万化，但是算法的情况也和数据结构类似，许多算法的设计思想具有相似之处，我们可以对它们分类进行学习和研究。本课程提到的算法大致有如下一些：贪心法分治法：如二分法检索回溯法动态规划法局部搜索法分支限界法1.4算法分析评价一个程序优劣的重要依据是看这个程序的执行需要占用多少机器资源。在各种机器资源中，时间和空间是两个最主要的方面。因此，在进行程序分析时人们最关心的就是程序所用算法运行时所要花费的时间代价和程序中使用的数据结构占有的空间代价。

算法的空间代价(或称空间复杂性)：当被解决问题的规模(以某种单位计算)由1增至n时，解该问题的算法所需占用的空间也以某种单位由f(1))增至f(n)，这时我们称该算法的空间代价是f(n)。算法的时间代价(或称时间复杂性)：当问题规模以某种单位由1增至n时，对应算法所消耗的时间也以某种单位由g(1)增至g(n)，这时我们称该算法的时间代价是g(n)。空间单位一般规定为一个简单变量(如整型、实型等)所占存储空间的大小；时间单位那么一般规定为执行一个简单语句(如赋值语句、判断语句等)所用时间。

在描述算法分析的结果时，人们通常采用“大O〞表示法：说某个算法的时间代价(或者空间代价)为O(f(n))，那么表示如果存在正的常数c和n0，当问题的规模n≥n0后，该算法的时间(或空间)代价T(n)≤c·f(n)。这时也称该算法的时间(或空间)代价的增长率为f(n)。这种说法意味着：当n充分大时，该算法的复杂性不大于f(n)的一个常数倍。常用的计算规那么：1。加法准那么 T(n)=T1(n)+T2(n)=O(f1(n))+O(f2(n))=O(max(f1(n),f2(n)))2。乘法准那么 T(n)=T1(n)×T2(n)=O(f1(n))×O(f2(n))=O(f1(n)×f2(n))采用大O表示法简化了时间和空间代价的度量，其根本思想是主要关注复杂性的量级，而忽略量级的系数，这使我们在分析算法的复杂度时，可以忽略零星变量的存储开销和循环外个别语句的执行时间，重点分析算法的主要代价。用同一个算法处理两个规模相同的问题，所花费的时间和空间代价也不一定相同。要全面分析一个算法，应该考虑它在最坏情况下的代价(对同样规模的问题所花费的最大代价)、最好情况下的代价和平均情况下的代价等。然而要全面准确地分析每个算法是相当困难的，因此本书中在分析算法的性质时将主要考虑它们在最坏情况下的代价，个别地方也涉及到其他情况。1.5抽象数据类型模块化设计的思想：抽象数据类型是模块化的思想的开展，它为模块的划分提供了理论依据抽象数据类型(AbstractDataType简称为ADT)可以看作是定义了一组操作的一个抽象模型。例如，集合与集合的并、交、差运算就可以定义为一个的抽象数据类型。一个抽象数据类型要包括哪些操作，这一点由设计者根据需要确定。例如，对于集合，如果需要，也可以把判别一个集合是否空集或两个集合是否相等作为集合上的操作。

从使用的角度看，一个抽象数据类型隐藏了所有使用者不关心的实现细节。使用抽象数据类型观点，可以使程序模块的实现与使用别离，从而能够独立地考虑模块的外部界面和内部算法和数据结构的实现。这也可以使应用程序只要按抽象数据类型的观点统一其调用方式，不管其内部换用其他的任何数据表示方式和运算实现算法，对应用程序都没有影响。这个特征对系统的维护和修改非常有利。在许多程序设计语言中预定义的类型，例如整数类型、浮点类型、指针类型等，都可以看作是简单的抽象数据类型。

从原那么上讲，数据结构课程中讨论的各种表、栈、队列、二叉树和字典等，也可以像整数、浮点数等一样定义为程序设计语言预定义的抽象数据类型复数抽象数据类型ADTComplex{ 数据对象：D={c1,c2|c1,c2R(R为实数集〕} 数据关系：S={<c1,c2>〔c1为实部，c2为虚部〕} 根本操作： voidAssign(*A,c1,c2〕 voidAdd(*A,B) voidMinus(*A,B) voidMultiply(*A,B) voidDivide(*A,B) ...}ADTComplex抽象数据类型例如typedefItemType double;typedefstruct{ ItemType r; ItemType v;}Complex; /*复数抽象数据类型*/voidAssign(Complex*A,ItemTyper,ItemTypev); /*赋值*/voidAdd(Complex*A,ComplexB); /*A+B*/voidMinus(Complex*A,ComplexB); /*A-B*/voidMultiply(Compex*A,ComplexB); /*A*B*/voidDivide(Complex*A,ComplexB); /*A/B*/...复数抽象数据类型的C语言定义voidAssign(Complex*A,ItemTypereal,ItemTypevirtual){ A->r=real; A->v=virtual;} /*Assign()*/voidAdd(Complex*A,ComplexB){ A->r+=B.r; A->v+=B.v;} /*Add()*/复数抽象数据类型的C语言实现〔1〕事后统计法缺陷：a.必须先运行程序b.所得时间统计量依赖于计算机软硬件等环境因素〔2〕事前估算法因素：a.算法的策略〔以百钱买百鸡问题为例)b.问题的规模〔n〕c.程序语言d.编译程序所产生的机器代码的质量e.机器执行指令的速度算法时间效率的度量例：两个N*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]; /*原操作*/ }问题规模：n原操作：c[I][j]+=a[I][k]*b[k][j];根本操作重复执行的次数：f(n)=n3该算法时间度量记作T(n)=O(f(n))=O(n3)时间复杂度：O(n3)矩阵相乘算法的分析有的情况下，算法中根本操作重复执行的次数还随问题的输入数据集的不同而不同。例如：voidBubble_Sort(inta[],intn){ int I,change=TRUE; for(I=n-1;I>1&&change;--I) { change=FALSE; for(j=0;j<I;j++) if(a[j]>a[j+1]) { swap(&a[j],&a[j+1]); change=TRUE; } }}

冒泡排序法百钱买百鸡问题100元钱买100只鸡，母鸡每只5元，公鸡每只3元，小鸡3只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？求解：设母鸡、公鸡、小鸡各为x,y,z只。那么有： x+y+z=100 5x+3y+z/3=100 只需要解出本方程就可以得到答案。方法1：用三重循环： for(I=0;I<=100;I++) for(j=0;j<=100;j++) for(k=0;k<=100;k++) { if(k%3==0&&I+j+k==100 \ &&5*I+3*j+k/3==100) printf(“%d,%d,%d\n〞,I,j,k); }方法2：用两重循环：因总共买100只鸡，所以小鸡的数目可以由母鸡数和公鸡数得到。For(I=0;I<100;I++) for(j=0;j<100;j++) { k=100–i–j; if(k%3==0&&5*I+3*j+k/3==100) printf(“%d,%d,%d\n〞,I,j,k); }方法3：用两重循环：钱共100元，而母鸡5元1只，所以母鸡数不可能超过20只，同样，公鸡数也不超过33只。For(I=0;I<=20;I++) for(j=0;j<33;j++) { k=100–i–j; if(k%3==0&&5*I+3*j+k/3==100) printf(“%d,%d,%d\n〞,I,j,k); }方法4：用一重循环由x+y+z=100和5*x+3*y+z/3=100可以合并为一个方程： 14*x+8*y=200,进一步简化为:7*x+4*y=100从上面方程可见，x不超过14，并可以进一步判断x必为4的倍数，于是有：For(I=0;I<=14;I+=4)

{ j=(100–7*I)/4; k=100–i–j; printf(“%d,%d,%d\n〞,I,j,k);}上面四个方法中，第一个方法的循环次数为： 100*100*100即一百万次；第二个方法的循环次数为：100*100，1万次；第三个方法为：20*34，680次，第四个方法为：4次，由此可见，算法的设计至关重要。返回小结在用计算机解题过程中，算法和数据结构是相辅相成、缺一不可的两个方面。数据结构是算法处理的对象也是设计算法的根底。一个具体问题的数据在计算机中往往可以采用多种不同的数据结构来表示；一个计算过程的实现又常常有多种可用的算法。因此选择什么样的算法和数据结构就成为实现程序过程中最重要的一个课题。抽象数据类型的引入，提高了程序设计的抽象层次，也为数据结构和算法的研究提供了一种分层的模型。重点掌握数据结构和算法的根本知识，理解它们在问题求解中的作用；了解下述概念：数据的逻辑结构、存储结构和操作，静态结构和动态结构，抽象数据类型，数据结构和算法的分类，算法的分析，空间代价和时间代价等。练习题随机产生n个整数，然后用一种排序算法将它们从小到大排序。

线性结构的特点：在数据元素的非空有限集中，〔1〕存在唯一的一个被称为“第一个〞的数据元素〔2〕存在唯一的一个被称为“最后一个〞的数据元素〔3〕除第一个之外，集合中的每个数据元素均只有一个 前驱〔4〕除最后一个之外，集合中的每个数据元素均只有一 个后继第二章线性表“线性表〞简称为表，是零个或多个元素的有穷序列，通常可以表示成k0，k1,…，kn-1〔n≥1〕。表中所含元素的个数称为表的“长度〞。长度为零的表称为“空表〞。表中的元素又称“表目〞。线性表中的数据元素在不同的情况下可以有不同的具体含义，它可以是一个数、一个符号，也可是其它更复杂的信息。2.1线性表的概念通常线性表有以下几种根本运算：1.在线性表中插入一个元素；2.在线性表中删除某个元素；3.在线性表中查找某个特定元素；4.在线性表中查找某个元素的后继元素；5.在线性表中查找某个元素的前驱元素；6.创立空线性表；7.判别一个线性表是否为空表。……由上面的根本运算还可以构成其它较为复杂的运算，如创立线性表。线性表的根本运算#include<stdio.h>#include<alloc.h>/*符号常量*/#defineMAXNUM 100/*线性表空间大小*/#defineFALSE 0#defineTRUE 1#defineSPECIAL 2147483647/*与DataType类型有关 ，32位机上的最大整数为231-1*/#definePI 3.1415926/*常用结构*/typedefint DataType; /*定义数据类型为整型，也 可定义为其他类型*/typedefint ElemType; /*定义元素类型为整型，也 可定义为其他类型*/typedefint KeyType; 以元素在计算机内存中的“物理位置相邻〞来表示线性表中数据元素之间的逻辑关系，如下所示： Locate(ai+1)=Locate(ai)+sizeof(DataType) Locate(ai)=Locate(a0)+sizeof(DataType)*I只要确定了首地址，线性表中任意数据元素都可以随机存取。2.2线性表的顺序表示和实现逻辑地址数据元素存储地址数据元素0k0Loc(k0)k01k1Loc(k0)+ck1…………ikiLoc(k0)+i*cki……n-1kn-1Loc(k0)+(n-1)*ckn-1线性表的顺序存储结构示意图顺序表的定义在C语言中可以用以下方式定义一个顺序表：DataTypeelement[MAXNUM];intn;这种定义的缺点在于没有反映出element和ｎ的内在联系：即没有指出ｎ是顺序表element本身的属性。在这个定义中，ｎ和element完全处于独立平等的地位，所以程序中完全可以将ｎ作为一个自由变量来使用。

为次，引进SeqList类型，它的定义为：typedefstructSeqList{ DataTypeelement[MAXNUM]; intn; /*n<MAXNUM*/};在实际应用中，为了使用方便，通常定义一个structSeqList类型的指针类型和别名： typedefstructSeqList*PSeqList; typedefstructSeqList SeqList;比较这两种定义顺序表的方法，后者概念较为清晰，符合数据抽象的原那么，今后我们的定义一般采用后者。根据顺序表的存储特点，顺序表的根本运算可具体为如下定义：1.

intinsert_seq(PSeqListpalist,DataTypex,intp)在palist所指顺序表中下标为ｐ的位置上插入一个值为ｘ的元素，并返回插入成功与否的标志。此运算在0≤p≤l->n时有意义。2.

intdelete_seq(PSeqListpalist,intp)在palist所指顺序表中删除下标为ｐ的元素，并返回删除成功与否的标志。此运算在0≤p＜l->n时有意义。3.

intfirst_seq(PSeqListpalist)求palist所指顺序表中第一个元素的下标。当palist为空表时返回一个特殊的下标值-1。4.intlocate_seq(PSeqListpalist,DataTypex)在palist所指顺序表中寻找值为ｘ的元素的下标，假设palist中不存在值为ｘ的元素，那么返回一个特殊的下标值-1。5.DataTyperetrieve_seq(PSeqListpalist,intp)在palist所指顺序表中，寻找下标为ｐ〔0≤p＜l->n〕的元素，并将该元素的值作为函数值返回，假设palist中无下标为ｐ的元素，那么返回一个特殊的值。6.intnext_seq(PSeqListpalist,intp)求palist所指顺序表中下标为ｐ的元素的后继元素下标，当不存在下标为ｐ的元素或虽有该元素但无后继时，返回一个特殊的下标值-1。7.intprevious_seq(PSeqListpalist,intp,)求palist所指顺序表中下标为ｐ的元素的前驱元素下标，当不存在下标为ｐ的元素，或虽有该元素但无前驱时，本函数返回一个特殊的下标值-1。8.voidcreateNullList_seq(PSeqListpalist)置palist所指顺序表为空表。9.intisNullList_seq(PSeqListpalist)判别palist所指顺序表是否为空表。假设为空那么返回1,否那么返回0。intinsert_seq(PSeqListpalist,DataTypex,intp)/*在palist所指顺序表中下标为ｐ的位置上插入元素ｘ*/{ intq; if(palist->n==MAXNUM) /*溢出*/ { printf("Overflow!\n"); return(FALSE); } if(p<0||p>palist->n)/*不存在下标为ｐ的元素*/{printf("notexist!\n");return(FALSE);} /*将ｐ及以后的元素后移一个下标位置*/for(q=palist->n-1;q>=p;q--) palist->element[q+1]=palist->element[q]; palist->element[p]=x; /*在p下标位置上放元素x*/ palist->n=palist->n+1; /*元素个数加１*/ return(TRUE);}

算法2.1顺序表的插入算法2.2顺序表的删除intdelete_seq(PSeqListpalist,intp)/*在palist所指顺序表中删除下标为ｐ的元素*/{intq;if(p<0||p>palist->n–1) /*不存在下标为ｐ的元素*/ {printf("notexist!\n"); return(FALSE); }for(q=p;q<palist->n-1;q++)/*将ｐ以后的元素前移一个位置*/ palist->element[q]=palist->element[q+1];palist->n=palist->n-1; /*元素个数减１*/return(TRUE);};

算法2.3求第一个元素的下标位置intfirst_seq(PSeqListpalist){if(palist->n==0) return-1;else return0;}

算法2.4在顺序表中求某元素的下标位置intlocate_seq(PSeqListpalist,DataTypex)/*求ｘ在palist所指顺序表中的下标位置*/{intq;for(q=0;q<palist->n;q++) if(palist->element[q]==x) return(q);return(-1);}算法2.5求palist所指顺序表中第ｐ个元素的值DataTyperetrieve_seq(PSeqListpalist,intp)/*求palist所指顺序表中第ｐ个〔即下标为p-1〕 的元素的值*/{if(p>0&&p<=palist->n) /*存在下标为 ｐ-1的元素*/ return(palist->element[p-1]);printf("Notexist.\n");returnSPECIAL; /*返回一个顺序表中没有 的特殊元素值*/};算法2.6求下一个元素的下标位置intnext_seq(PSeqListpalist,intp)/*求palist所指顺序表中下标为p的元素的后继元素的下标位置 */{if((p>=0)&&(p<palist->n-1)) return(p+1);else return(-1);}算法2.7求前一个元素的下标位置intprevious_seq(PSeqListpalist,intp)/*求palist所指顺序表中下标为p的元素的前驱元素的下标位置 */{if(p>0&&p<palist->n) return(p-1);else return(-1);}算法2.8创立空线性表PSeqListcreateNullList_seq(void){ PSeqListpalist; palist=(PSeqList)malloc(sizeof(structSeqList)); if(palist!=NULL) palist->n=0; else printf("Outofspace!!\n"); returnpalist;};

算法2.9判断线性表是否为空intisNullList_seq(PSeqListpalist){return(palist->n==0);}说明：上述算法在具体上机实现时，要将下面的类型说明、常量说明及类型定义包含在文件中。#defineMAXNUM100/*线性表空间大小*/#defineFALSE0#defineTRUE1typedefintDataType; /*定义元素类型为整型 ，也可定义为其他类型*/#defineSPECIAL2147483647/*与DataType类型有关，32位机上的最大整数 为231-1*/structSeqList{ DataTypeelement[MAXNUM]; intn;};typedefstructSeqListSeqList,*PSeqList;顺序表的元素插入删除操作和定位操作的时间复杂度分析。考察插入元素时的时间效率：设pi是在第i个元素之前插入一个元素的概率，那么在长度为n的线性表中插入一个元素时所需移动元素的次数的期望值〔平均次数〕为：设那么有以上的顺序表的实现中，表的大小是固定不变的，但有时我们不能确定表的大小，这时就需要可变大小的顺序表。于是我们可以如下定义并实现顺序表：typedefstructSeqList{ DataType *element; int n; /*表中元素的个数*/ int size; /*表的大小*/}SeqList,*PSeqList;BOOLInitList(PSeqListpList){pList->element=(PSeqList)malloc(sizeof(DataType)*INITSIZE);assert(pList); /*判断是否申请成功*/pList->size=INITSIZE;pList->n=0;}不固定大小的顺序表的实现StatusInsertElem(PSeqListpList,inti,ElemTypeelem){ int j,pos; ElemType*newList; if(i<0||i>pList->elems) { printf("Insertpositionerror!\n"); returnERROR; } /*Ifnoenoughspace,reallocmorespace*/ if(pList->n+1>pList->size){ newList=(DataType*)realloc(pList->elem, (pList->size+Increment)*sizeof(DataType)); assert(newList!=NULL); pList->element=newList; pList->size+=Increment; } /*Movetheelememtswhichlocatebehindelement‘I’apositionforward*/ for(j=pList->elems;j>i;j--) pList->element[i]=pList->element[i-1]; pList->element[i]=elem; ++pList->n; returnOK;} /*EndofInsertElem()*//*Constructablanklist*/voidInitList(PSeqListpList){ pList->elem=(ElemType*)malloc(InitSize*sizeof(ElemType)); /*Testwhetherallocationissuccessful*/ assert(pList->elem!=NULL); pList->size=InitSize; pList->elems=0;} /*EndofInitList()*/StatusDeleteElem(PSeqListpList,inti){ int j; if(i<0||i>=pList->elems) { printf("Deletepositionerrorornoelements!\n"); returnERROR; } for(j=i;j<pList->elems;j++) pList->elem[i]=pList->elem[i+1]; --pList->elems; returnOK;} /*EndofDeleteElem()*/voidMergeList_Seq(SeqListla,SeqListlb,SeqList*lc){ ElemType *pa,*pb,*pc,*pa_last,*pb_last; pa=la.elem; pb=lb.elem; lc.size=la.size+lb.size; pc=lc->elem=(ElemType*)malloc(sizeof(ElemType)*lc.size); assert(pc) pa_last=pa+la.elems-1; pb_last=pb+lb.elems-1; while(pa<=pa_last&&pb<=pb_last) { if(*pa<=*pb) *pc++=*pa++; else *pc++=*pb++; } while(pa<=pa_last) *pc++=*pa++; while(pb<=pb_last) *pc++=*pb++;} /*EndofMergeList_Seq()*/两个顺序表的合并链式存储和顺序存储各自的优缺点：结点：数据元素的存储映象，由数据域和指针域构成。数据域指针域存储地址数据域指针域1 Li 437 Qian 1313 Sun 1 19 Wang NULL25 Wu 3731 Zhao 737 Zheng1943 Zhou 2531头指针H1。定义单链表2.3线性表的链式表示及实现线性链表的逻辑状态LiZhaoQianSunZhouWuZhengWang^Ha1an^a2...头指针H头结点H^非空表空表单链表结构

线性链表的定义typedefintDataType;/*定义元素类型为整型，也可定义为其他类型*/structNode; /*单链表结点类型*/typedefstructNode*PNode; /*结点指针类型*/structNode /*单链表结点结构*/{ DataType info; PNode link;};structLinkList /*单链表类型定义*/{ PNodehead; /*指向单链表中的第一个结点*/};typedefstructLinkListLinkList,*PLinkList; /*单链表类型的指针类型*/PLinkListpllist; /*pllist是指向单链表的一个指针变量*/

根据单链表的存储特点，线性表的根本运算可具体为如下定义：1.voidinsert_link(DataTypex,PNodep)在单链表中ｐ位置的后面插入元素ｘ。2.voiddelete_link(PLinkListpllist,DataTypex)在pllist所指的单链表中删除一个元素为x的结点。3.

PNodefirst_link(PLinkListpllist)在pllist所指的单链表中求第一个结点的位置。4.

PNodelocate_link(PLinkListpllist,DataTypex)在pllist所指的单链表中求元素为x的结点位置。5.DataTyperetrieve_link(PNodep) 在pllist所指的单链表中求p位置上的元素。6.

PNodenext_link(PNodep)在pllist所指的单链表中求p位置的后继元素的位置。7.PNodeprevious_link(PLinkListpllist,DataTypex)在pllist所指的单链表中求元素为x的结点的前驱元素的位置。8.

PLinkListcreateNullList_link(void)创立空链表。9.

intisNullList_link(PLinkListpllist)判断pllist所指的单链表是否是空链表。10.PNodefind_link(PLinkListpllist,inti)在pllist所指的单链表中求第i(i>0)个结点的位置。voidinsert_link(PLinkListpList,DataTypex,PNodep)/*在单链表中ｐ所指结点的后面插入元素ｘ*/{ PNode q; q=(PNode)malloc(sizeof(structNode)); if(q==NULL) printf("Outofspace!!!\n"); else{ q->info=x; q->link=p->link; p->link=q; }}/*算法2.10单链表的插入*//*算法2.11单链表的删除*/voiddelete_link(PLinkListpllist,DataTypex)/*在pllist所指的带有头结点的单链表中删除元素为x的结点*/{ PNode p,q; p=pllist->head; /*在pllist所指的带有头结点的单链表中找元素为x的结点的前驱结点位置*/ while(p->link!=NULL&&p->link->info!=x) p=p->link; if(p->link==NULL) /*没找到元素为x的结点*/ printf("Notexist!\n"); else{ q=p->link; /*找到元素为x的结点*/ p->link=q->link; free(q); }}/*算法2.12求第一个元素的位置*/PNodefirst_link(PLinkListpllist)/*在pllist所指的带有头结点的单链表中求第一个结点的位置*/{ returnpllist->head->link;}/*算法2.13在单链表中求某元素的位置*/PNodelocate_link(PLinkListpllist,DataTypex)/*在pllist所指的带有头结点的单链表中找元素为x的结点位置*/{ PNode p;

p=pllist->head->link; while(p!=NULL&&p->info!=x) p=p->link; returnp;}/*算法2.14求单链表中某位置的元素*/DataTyperetrieve_link(PNodep){ returnp->info;}/*算法2.15求前一个元素的位置*/PNodeprevious_link(PLinkListpllist,DataTypex)/*在pllist所指的带有头结点的单链表中找元素为x的结点的前驱结点位置*/{ PNode p; p=pllist->head; while(p->link!=NULL&&p->link->info!=x) p=p->link; if(p==pllist->head||p->link==NULL)/*x是第一个结点的值或者不存在值为x的结点*/ returnNULL; else returnp;}/*算法2.17创立空链表*/PLinkListcreateNullList_link(void)/*创立一个带头结点的空链表*/{ PLinkList pllist; PNode p; pllist=(PLinkList)malloc(sizeof(structLinkList)); if(pllist!=NULL){ p=(PNode)malloc(sizeof(structNode)); if(p!=NULL) { pllist->head=p; p->link=NULL; } else{ printf("Outofspace!\n"); pllist->head=NULL; } } elseprintf("Outofspace!\n"); returnpllist;}/*算法2.16求下一个元素的位置*/PNodenext_link(PNodep){ if(p!=NULL) returnp->link; else returnNULL;}/*算法2.18判断单链表是否为空*/intisNullLink_link(PLinkListpllist)/*判断pllist所指的带有头结点的单链表是否是空链表*/{ returnpllist->head->link==NULL;}/*算法2.19求单链表中第i个元素的位置*/PNodefind_link(PLinkListpllist,inti)/*在带有头结点的单链表pllist中求第i个结点的位置*//*当表中无第i个元素时，返回值为NULL*/{ PNode p; int j; if(i<1){ printf("Thevalueofi=%disnotreasonable.\n",i); returnNULL;} p=pllist->head; for(j=0;j<i;j++){ p=p->link; if(p==NULL) returnNULL; } returnp;}abpabpc单链表单链表插入结点时的情况s->next=p->next;p->next=s;注：顺序不能反单链表删除结点时的情况p->next=p->next->next;abxsp单链表结点插入和删除时的情形voidMergeList_L(LinkListla,LinkListlb,PLinkListlc){ PNode pa,pb,pc;

pa=la.head->link; pb=lb.head->link; pc=lc->head=la.head; /*用la的头结点作为lc的头结点*/ while(pa&&pb) { if(Compare(pa->info,pb->info)<=0) { pc->link=pa; pc=pa; pa=pa->link; } else{ pc->link=pb; pc=pb; pb=pb->link; } } pc->link=pa?pa:pb; free(lb.head);}两个单链表的合并，使合并后的链表按照从小到大的顺序排列voidMergeList_L(LinkListla,LinkListlb,PLinkListlc){ PNode pa,pb,pc; pa=la.head; pb=lb.head; pc=lc->head; while(pa&&pb) { if(Compare(pa->info,pb->info)<=0){ if(pc==NULL) lc->head=pc=pa; else { pc->link=pa; pc=pa; pa=pa->link; } } else{ if(pc==NULL) lc->head=pc=pb; else{ pc->link=pb; pc=pb; pb=pb->link; } } } pc->link=pa?pa:pb;}单链表的时间复杂度单链表与顺序表的比较：(1)单链表的存储密度比顺序表低，它多占用了存储空间。但在许多情况下，链式的分配比顺序分配有效，顺序表必须分配足够大的连续的存储空间，而链表可以利用零星的存储单元。(2)在单链表里进行插入、删除运算比在顺序表里容易得多。(3)对于顺序表，可随机访问任一个元素，而在单链表中，需要顺着链逐个进行查找，因此单链表适合于在成批地、顺序地处理线性表中的元素时采用。#defineMaxSize 1000 /*Themaxlengthofthelinklist*/typedefstruct{ DataType data; int cursor;}Component,SLinkList[MaxSize];voidInitList(SLinkListlist); /*use'0'todeputeblankpointer*//*Allocmemory,returnthesubscriptionoftheallocatednode,ifnospaceavialable,return0*/intMalloc(SLinkListlist);/*Retractthespacewhichsubscriptionis'k'*/voidFree(SLinkListlist,intk);静态链表012345678910123456780ZhaoQianSunLiZhouWuZhengWang0123456789101234968805ZhaoQianSunLiZhouWuZhengWangShi静态链表例如修改前修改后voidInitList(SLinkListlist){ int i; for(i=0;i<MaxSize-1;i++) list[i].cursor=i+1; list[MaxSize-1].cursor=0;} /*EndofInitList()*/intMalloc(SLinkListlist){/*Alwaysreturnthefirstavailableunit*/ int i; i=list[0].cursor; if(list[0].cursor!=0) list[0].cursor=list[i].cursor; returni;} /*EndofMalloc()*//*Inserttherecyclespaceintothefirstplaceofthelist*/voidFree(SLinkListlist,intk){ list[k].cursor=list[0].cursor; list[0].cursor=k;}实现：循环条件：pNode==pList->head表空条件：pList->head->next==pList->head操作与线性链表根本一致。循环链表优点：既可以找前驱，也可以找后继。双向链表和双向循环链表描述双链表及其结点类型的说明为：typedefstructDoubleNode /*双链表结点结构*/{ DataType info; structDoubleNode* llink,rlink;}DoubleNode,*PDoubleNode;typedefstructDoubleList /*双链表类型*/{ PDoubleNodehead; /*指向第一个结点*/ PDoubleNoderear; /*指向最后一个结点*/};PDoubleListpdlist; /*pdlist是指向双链表类型的 指针变量*/^^A^空双向链表非空双向链表删除双向链表的结点p->llink->rlink=p->rlinkp->rlink->llink=p->llink往双向链表中插入结点s->llink=p->llink;p->llink->rlink=s;s->rlink=p;p->llink=s;ABCpABCsp双向链表的表示2.4应用举例—Josephus问题设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此反复直到所有的人全部出列为止。Josephus问题是：对于任意给定的n,s和m，求出按出列次序得到的n个人员的序列。现以n=8，s=1，m=4为例，问题的求解过程如图2-10所示。图中s1指向开始报数位置，带圆圈的是本次应该出列的人员。假设初始的顺序为n1，n2，n3，n4，n5，n6，n7，n8，那么问题的解为n4，n8，n5，n2，n1，n3，n7，n6。(c)n4n8n5(d)n4n8n5n2(a)n4(b)n4n8(e)n4n8n5n2n1(f)n4n8n5n2n1n3(g)n4n8n5n2n1n3n7(h)n4n8n5n2n1n3n7n6顺序表表示步骤：1。建立顺序表2。出列循环链表表示1。建立循环单链表2。寻找第s个结点，输出并删除第m个节点。Pn(x)=pn+p1x+p2x2++pnxn在计算机中可以用一个线性表P来表示：P=(p0,p1,p2,,pn)每一项的指数都隐含在系数pi的序号里。这种表示方法对于所有项都比较全的时候是很好的，但是如果指数很高并且变化很大时，这种表示方法就不适宜了。这时我们可以把每一项的系数和直属都存储下来，也就是对于每一项都用两个数据项来存储。即为如下的形式：P=((p1,e1),(p2,e2),(pm,em〕)对于这种表示方法也有两种存储方法：即顺序存储和链式存储。2.5*一元多项式的表示及相加typedefstruct_ElemType{ float coef; /*XiShu多项式系数*/ int expn; /*ZhiShu多项式指数*/}ElemType;/*NodeType结点类型*/typedefstruct_Polyn{ ElemType data; /*数据域*/ struct_Polyn *next; /*指针域*/}Node,*Link; /*Nodetype&NodePointertype结点类型及结点指针类型*//**************************************************************************** 为了便于对链表进行操作定义的一个结构类型: 因为我们是用LinkList类型的变量来指向该链表的，而该变量的成员变量head 就是该链表的头结点。用这种方法来实现链表，符合面向对象编程中的封装的 概念，因为对该链表的操作都是通过LinkList类型的变量来进行的。****************************************************************************/typedefstruct{ Link head,tail; /*用作链表的结节点和尾指针*/ int len; /*可以用来记录链表的长度*/}LinkList,*PLinkList;一元多项式抽象数据类型的实现：/*Initializealinklist*/voidInitList(PLinkList*pList);/*所用到的函数的原型化声明*//*把两个一元多项式相加*/PLinkListAddPolyn(PLinkListpa,PLinkListpb);/*创立一个一元多项式*/voidCreatePolyn(PLinkListpList);/*实现两个一元多项式的相乘*/PLinkListMultiplyPolyn(PLinkListpa,PLinkListpb);/*打印该链表的结果*/voidPrintPolyn(PLinkListpList);/*比较两个节点的指数的大小*/Intcmp(ElemTypea,ElemTypeb);/*删除一个链表*/voidFreeList(PLinkListpList);/*MultiplyaLinkListwithanelement*/voidMultiItem(PLinkListpResultList,PLinkListpList,LinkItem);/*Multiplytwolinklist*/PLinkListMultiLinkList(PLinkListpList1,PLinkListpList2);PLinkListAddPolyn(PLinkListpa,PLinkListpb){ Link ha; /*用来指向新链表的尾结点的*/ Link hb; /*指向第二个链表的头结点〔为了最后删除它〕*/ Link qa; /*指向第一个链表的当前结点*/ Link qb; /*指向第二个链表的当前结点*/ Link temp; /*删除结点时做临时变量用*/ ElemType a,b; /*分别存放两个链表当前结点的数据*/ float sum; /*存放两个链表中当前结点的系数和*/ ha=pa->head; qa=ha->next; hb=pb->head; qb=hb->next; while(qa&&qb) { a=qa->data;b=qb->data; switch(cmp(a,b)) {

case-1: /*第一个链表中当前结点的指数值小*/ ha->next=qa; /*Linkthenodetotheendofha*/ ha=qa; /*movethetailpointertoqa*/ qa=qa->next; /*movetothenextnodeofqa*/ break; case0: /*指数值相等*/ sum=a.coef+b.coef; if(sum!=0.0) { qa->data.coef=sum; ha->next=qa; /*Linkqatotheresultpolyn*/ ha=qa; /*Lethastillpointtothetail*/ qa=qa->next; } else { /*释放qa所指向的结点的空间*/ temp=qa; /*qaistobedeleted,lettemppointtoit*/ qa=qa->next; /*Letqapointtothenextnode*/ free(temp); /*Freethespace*/ }

/*释放qb所指向的结点的空间*/ temp=qb; qb=qb->next; /*letqbpointtothenextnode*/ free(temp); break; case1: /*第一个链表中当前结点的指数值大*/ ha->next=qb; ha=qb; qb=qb->next; break; } /*EndofSwitch*/ } /*Endofwhile(!qa&&!qb)*/ ha->next=qa?qa:qb; /*Linktherestnodesofpolynomial1or2*/ free(hb);/*Freetheheadnodeofthe2ndpolynomial*/ return(pa);} /*EndofAddPolyn()*/本章主要讨论了线性表的概念、存储表示以及根本运算的实现，这些内容应熟练掌握，并能灵活应用，这对以后的几章学习是十分有益的。小结1。限制使用双向链表作存储结构，请根据用户输入的一个整数〔该整数表示精确到小数点后的位数，可能要求精确到小数点后500位〕，高精度计算值。可以利用反三角函数幂级展开式来进行计算：当x=1/2时，arcsinx=/6与是可以利用下面的关系式来求得值。作业2.设A与B分别为两个带有头结点的有序循环链表〔所谓有序是指链接点按数据域值大小链接，此题不妨设按数据域值从小到大排列〕，list1和list2分别为指向两个链表的指针。请写出将这两个链表合并为一个带头结点的有序循环链表的算法。1。正确实现所要求的功能〔能够通过测试〕2。界面友好3。程序注释〔可读性好〕4。良好的编程风格5。健壮性作业要求在具体语言环境中的实现：〔C语言〕#include“common.h〞#defineMaxSize100typedefintElemType;typedefElemTypeList[MaxSize];StatusInitList(Listl); /*构造一个空的线性表*/StatusDestroyList(Listl); /*销毁线性表*/StatusClearList(Listl); /*清空线性表*/BOOLIsListEmpty(Listl); /*判断线性表是否空*/intListLength(Listl); /*求线性表的长度*/StatusGetElem(Listl,intI,ElemType*e); /*返回第I个元素*/...例：将非递减有序排列的两个线性表la和lb归并为一个lc,仍保持非递减排列。voidMergeList(Listla,Listlb,Listlc){ int I,j,k; int la_len,lb_len; /*la和lb的长度*/ ElemType ai,bj; I=j=1; k=0; InitList(lc); la_len=ListLength(la); lb_len=ListLength(lb); while(I<=la_len&&