数据结构第二章线性表.pptVIP

,DATA,10,65,865,姓名学号成绩班级李红976105995机97.6,数据结构,概念,1.数据（Data）数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述。简而言之，数据就是计算机化的信息。,例如对C源程序，数据概念不仅是源程序所处理的数据，相对于编译程序来说，C编译程序相对于源程序是一个处理程序，它加工的数据是字符流的源程序（.c），输出的结果是目标程序(.obj)；对于链接程序来说，它加工的数据是目标程序(.obj)，输出的结果是可执行程序(.exe)，如图1.1所示。,图1.1编译程序示意图,2.数据元素（DataElement）数据元素是组成数据的基本单位,是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。,表1-1学籍表,数据项,记录,3.数据对象（DataObject）数据对象是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N=0，1，2，字母字符数据对象是集合C=A，B，Z，表1-1所示的学籍表也可看作一个数据对象。由此可看出，不论数据元素集合是无限集（如整数集）、有限集（如字符集），还是由多个数据项组成的复合数据元素（如学籍表），只要性质相同，都是同一个数据对象。,综上13所述，再分析数据概念：,4.数据结构（DataStructure）数据结构是指相互之间存在一种或多种特定关系的数据元素集合，,图1.2学校组织层次结构图,图1.3交通流量图,5.数据类型(DataType)数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。数据类型中定义了两个集合，即该类型的取值范围，以及该类型中可允许使用的一组运算。例如高级语言中的数据类型就是已经实现的数据结构的实例。从这个意义上讲，数据类型是高级语言中允许的变量种类，是程序语言中已经实现的数据结构（即程序中允许出现的数据形式）。在高级语言中，整型类型可能的取值范围是-32768+32767，可用的运算符集合为加、减、乘、除、乘方、取模（如C语言中+，-，*，/，%）。,6.数据抽象与抽象数据类型,）数据的抽象计算机中使用的是二进制数，汇编语言中则可给出各种数据的十进制表示，如98.65、9.6E3等,它们是二进制数据的抽象;使用者在编程时可以直接使用,不必考虑实现细节。在高级语言中，则给出更高一级的数据抽象，出现了数据类型，如整型、实型、字符型等。到抽象数据类型出现，可以进一步定义更高级的数据抽象，如各种表、队、栈、树、图、窗口、管理器等，这种数据抽象的层次为设计者提供了更有利的手段，使得设计者可以从抽象的概念出发，从整体考虑，然后自顶向下、逐步展开，最后得到所需结果。可以这样看，高级语言中提供整型、实型、字符、记录、文件、指针等多种数据类型，可以利用这些类型构造出像栈、队列、树、图等复杂的抽象数据类型。,）抽象数据类型(AbstractDataType)抽象数据类型（简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。抽象数据类型的定义取决于客观存在的一组逻辑特性，而与其在计算机内如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。从某种意义上讲，抽象数据类型和数据类型实质上是一个概念。整数类型就是一个简单的抽象数据类型实例。“抽象”的意义在于教学特性的抽象。一个ADT定义了一个数据对象，数据对象中各元素间的结构关系，以及一组处理数据的操作。ADT通常是指由用户定义且用以表示应用问题的数据模型，通常由基本的数据类型组成，并包括一组相关服务操作。,抽象数据类型是近年来计算机科学中提出的最重要的概念之一，它集中体现了程序设计中一些最基本的原则：分解、抽象和信息隐藏。一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏起来。,数学模型抽象数据类型数据结构，恰好反应了信息结构转换的三个重要阶段，而在这个转换过程中，数据结构是基础，抽象数据类型是中枢。一个线性表的抽象数据类型的描述如下：ADTLinear-list数据元素所有ai属于同一数据对象，i=1，2，n,n0；逻辑结构所有数据元素ai（i=1，2，n-1）存在次序关系，ai无前趋，an无后继；,操作设L为Linear-list:Initial(L):初始化空线性表;Length(L):求线性表的表长;Get(L,i):取线性表的第i个元素；Insert(L,i,b):在线性表的第i个位置插入元素b；Delete(L,i):删除线性表的第i个元素。,）抽象数据类型实现,第一种情况：传统的面向过程的程序设计。第二种情况：“包”、“模型”的设计方法。第三种情况：面向对象的程序设计（ObjectOrientedProgramming，简称OOP）。,）ADT的表示与实现ADT的定义ADT的定义格式不唯一,我们采用下述格式定义一个ADT:ADT数据对象:结构关系:基本操作:ADT,其中数据对象和结构关系的定义采用数学符号和自然语言描述,而基本操作的定义格式为:(参数表)操作前提:操作结果:,关于参数传递参数表中的参数有两种：第一种参数只为操作提供待处理数据,又称值参；第二种参数既能为操作提供待处理数据,又能返回操作结果，也称变量参数。操作前提描述了操作执行之前数据结构和参数应满足的条件,操作结果描述操作执行之后,数据结构的变化状况和应返回结果。ADT可用现有计算机语言中已有的数据类型,即固有数据类型来表示和实现。不同语言的表示和实现方法不尽相同，如ADT中“返回结果的参数”，PASCAL语言用“变参”实现,C+语言通过“引用型参数”实现,而C语言用“指针参数”实现。,用标准C语言表示和实现ADT描述时，主要包括以下两个方面:(1)通过结构体将int、float等固有类型组合到一起,构成一个结构类型,再用typedef为该类型或该类型指针重新起一个名字。(2)用C语言函数实现各操作。,基本操作主要有以下几种：(1)插入：在数据结构中的指定位置上增添新的数据元素；(2)删除：删去数据结构中某个指定数据元素；(3)更新：改变数据结构中某个元素的值，在概念上等价于删除和插入操作的组合；(4)查找：在数据结构中寻找满足某个特定要求的数据元素（的位置和值)；(5)排序：（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使数据元素按值由小到大或由大到小的次序排列。,1.2数据结构的内容,1.逻辑结构,图1.5四类基本数据结构示意,(1)集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。(2)线性结构：结构中的数据元素之间存在着一对一的线性关系。(3)树形结构：结构中的数据元素之间存在着一对多的层次关系。(4)图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。,逻辑结构,线性结构线性表、栈、队、字符串、数组、广义表非线性结构树、图,2.存储结构存储结构（又称物理结构）是逻辑结构在计算机中的存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。形式化描述：D要存入机器中，建立一从D的数据元素到存储空间M单元的映象S，DM，即对于每一个d，dD,都有唯一的zM，使S（D）=Z,同时这个映象必须明显或隐含地体现关系R。,逻辑结构与存储结构的关系为：存储结构是逻辑关系的映象与元素本身的映象。逻辑结构是数据结构的抽象，存储结构是数据结构的实现，两者综合起来建立了数据元素之间的结构关系。,顺序映象（顺序存储结构）非顺序映象（非顺序存储结构）,数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。,第二章线性表,2.1线性表的基本概念,1线性表的定义线性表是n（n0）个数据元素a1，a2，an组成的有限序列。其中n称为数据元素的个数或线性表的长度。当n=0时称为空表，n0时称为非空表。通常将非空的线性表记为（a1，a2，,an），其中的数据元素ai（1in）是一个抽象的符号，其具体含义在不同情况下是不同的。,例：（星期一，星期二，星期三，星期四，星期五，星期六，星期天）,例：线性表（1，2，3，4，5，6，7）3的直接前驱为2。直接后继为4。1没有直接前驱。7没有直接后继。,线性表（a1，a2，,an）中，一个元素ai的直接前驱是ai-1,它的直接后继是ai+1,2线性表的特征从线性表的定义可以看出线性表的特征：（1）有且仅有一个开始结点(表头结点)a1，它没有直接前驱，只有一个直接后继;（2）有且仅有一个终端结点(表尾结点)an，它没有直接后继，只有一个直接前驱;（3）其它结点都有一个直接前驱和直接后继；（4）元素之间为一对一的线性关系。a1a2an(5)线性表中的元素可以是各样的,但是同一线性表中的元素必定有相同特性,即属于统一数据对象.,3、线性表的形式定义线性表是一种典型的线性结构，用二元组表示为：linear_list=(A,R)其中A=aii=1,2,3,n,n0,aielemtypeR=rr=1in-1,例：给出线性表（1，2，3，4，5，6）的形式定义。linear_list=(A,R)A=1，2，3，4，5，6R=rr=，,a1a2an,返回,在线性表上常用的运算有：初始化、求长度、取元素、修改、前插、删除、检索、排序。,4.线性表的抽象数据类型定义,ADTLinearList数据元素：D=ai|aiD0,i=1,2,，n,n0，D0为某一数据对象关系：|ai,ai+1D0，i=1,2,n-1基本操作：（1）InitList（L）操作前提：L为未初始化线性表。操作结果：将L初始化为空表。,（2）DestroyList(L)操作前提：线性表L已存在。操作结果：将L销毁。（3）ClearList(L)操作前提：线性表L已存在。操作结果：将表L置为空表。（4）EmptyList（L）操作前提：线性表L已存在。操作结果：如果L为空表则返回真，否则返回假。,（5）ListLength（L）操作前提：线性表L已存在。操作结果：如果L为空表则返回0，否则返回表中的元素个数。（6）Locate(L,e)操作前提：表L已存在，e为合法元素值。操作结果：如果L中存在元素e，则将“当前指针”指向元素e所在位置并返回真，否则返回假。（7）GetData(L,i)操作前提：表L存在，且i值合法，即1iListLength（L）。操作结果：返回线性表L中第i个元素的值。,（8）InsList(L,i,e)操作前提：表L已存在，e为合法元素值且1iListLength(L)+1。操作结果：在L中第i个位置插入新的数据元素e，L的长度加1。（9）DelList(L,i,/*V是数组的名字，假设数组中的元素是整型类型*/,第i个元素的ai存储地址：Loc(ai)=Loc(a1)+(i-1)*m,V,V,Vi,Vm-1,2.2.2线性表顺序存储结构上的基本运算,1.查找操作线性表有两种基本的查找运算。按序号查找GetData(L,i):要求查找线性表L中第i个数据元素，其结果是L.elemi-1或L-elemi-1。按内容查找Locate（L,e）:要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。查找运算可采用顺序查找法实现，即从第一个元素开始，依次将表中元素与e相比较，若相等，则查找成功，返回该元素在表中的序号；若e与表中的所有元素都不相等，则查找失败，返回“-1”。,算法描述：intLocate(SeqListL，ElemTypee)/*在顺序表L中依次存放着线性表中的元素，在表中查找与e相等的元素，若Li=e，则找到该元素，并返回i值，若找不到，则返回“-1”*/i=0;/*i为扫描计数器，初值为0，即从第一个元素开始比较*/while(ilast+1，i的合法取值范围是1iL-last+2*/intk;if(iL-last+2)/*首先判断插入位置是否合法*/printf(插入位置i值不合法)；return(ERROR);,if(L-last=maxsize-1)printf(表已满无法插入)；return(ERROR);for(k=L-last;k=i-1;k-)/*为插入元素而移动位置*/L-elemk+1=L-elemk;L-elemi-1=e;/*在C语言数组中，第i个元素的下标为i-1*/L-last+;return(OK);,【算法2.2线性表的插入运算】,可以看出，当i=L-last+2时，语句L-elemk+1=L-elemk将不会执行，因为循环的终值大于初值，此时不需要移动元素，可直接在表尾插入e。当i=1时，语句L-elemk+1=L-elemk需执行n次，即将表中已存在的n个元素依次后移一个位置才能将e插入。因此，语句L-elemk+1=L-elemk的频度与插入位置i有关。,3.删除操作线性表的删除运算是指将表的第i(1in)个元素删去，使长度为n的线性表(e1，,ei-1，ei，ei+1，en)变成长度为n-1的线性表(e1，,ei-1，ei+1，en)。例如：线性表(4,9,15,21,28,30,30,42,51,62)删除第5个元素，则需将第6个元素到第10个元素依次向前移动一个位置，如图2.4所示。,图2.4顺序表中删除元素,算法描述：,intDelList(SeqList*L,inti,ElemType*e)/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1iL.last+1*/intk;if(iL-last+1)printf(删除位置不合法！)；return(ERROR);,*e=L-elemi-1;/*将删除的元素存放到e所指向的变量中*/for(k=i;ilast;k+)L-elemk-1=L-elemk;/*将后面的元素依次前移*/L-last-;Return(OK);,【算法2.3线性表的删除运算】,与插入运算类似，在顺序表上实现删除运算也必须移动结点，这样才能反映出结点间的逻辑关系的变化。若i=L-last+1，则移位语句L-elemk-1=L-elemk不执行，因为循环变量的初值大于终值，此时不需要移动元素，仅将表长度减1即可。显然，删除算法中移位语句L-elemk-1=L-elemk的执行频度也与删除位置i有关。,在顺序表中插入或删除一个数据元素时，其时间主要耗费在移动数据元素上。对于插入算法而言，设Pi为在第i个元素之前插入元素的概率，并假设在任何位置上插入的概率相等，即Pi=1/(n+1),i=1,2,，n+1。设Eins为在长度为n的表中插入一元素所需移动元素的平均次数，则,同理，设Qi为删除第i个元素的概率，并假设在任何位置上删除的概率相等，即Qi=1/n,i=1,2,，n。删除一个元素所需移动元素的平均次数Edel为,例2-1有两个顺序表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排列。例如LA=(2,2,3),LB=(1,3,3,4),则LC=(1,2,2,3,3,3,4)。,算法思想：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、j分别指向表LA和LB中的元素，若LA.elemiLB.elemj，则当前先将LB.elemj插入到表LC中;若LA.elemiLB.elemj，则当前先将LA.elemi插入到表LC中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。,voidmerge(SeqList*LA,SeqList*LB,SeqList*LC)inti,j,k,l;i=0;j=0;k=0;while(ilastelse,LC-elemk=LB-elemj;j+;k+;while(ilast)/*当表LA比表LB长时，则将表LA余下的元素赋给表LC*/LC-elemk=LA-elemi;i+;k+;while(jlast)/*当表LB比表LA长时，则将表LB余下的元素赋给表LC*/LC-elemk=LB-elemj;j+;k+;LC-last=LA-last+LB-last;,【算法2.4线性表的合并运算】,由上面的讨论可知，线性表顺序表示的优点是：(1）无需为表示结点间的逻辑关系而增加额外的存储空间（因为逻辑上相邻的元素其存储的物理位置也是相邻的）；(2）可方便地随机存取表中的任一元素。其缺点是：(1）插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低；(2)由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配，因此当表长变化较大时，难以确定合适的存储规模。若按可能达到的最大长度预先分配表空间，则可能造成一部分空间长期闲置而得不到充分利用；若事先对表长估计不足，则插入操作可能使表长超过预先分配的空间而造成溢出。,intinsq(inti，intx,intV,intM,int*p）/*顺序表插入子函数*/*在线性表V中第i个元素之前插入x，i的合法值为1in*/intn，j：n=*p;/*获取表长*/if（n=M)/*M是存储空间的大小，p是指向存储表长的指针变量*/printf(overflown);return(0);if(in+1)printf(iiserrorn);return(0);/*i值不合法*/elsefor(j=n;j=i;j-)Vj=Vj-1;/*插入位置后的元素依次右移*/Vj=x;/*插入x*/p=+n;/*表长加1,由p返回到函数调用处*/return(1);,注意数组元素从0开始,实现顺序表插入元素的主函数viodmain()intM=10;n=4;/*M是数组的大小,n是表中已有元素个数,即表长*/intresult,k;staticintV10=3,5,7,10;/*数组赋初值*/result=insq(2,4,V,10,运行结果:success!345710,1-2删除运算intdelsq(inti,intV,int*p）/*在线性表V中删除第i个元素*/intn,j;n=*p;if（in）printf(Thiselementisnotinthelistn);return(0);elsefor(j=i;jnext=NULL），则表示单链表为一个空表，其长度为0。若不是空表，则可以通过头指针访问表中结点，找到要访问的所有结点的数据信息。对于带头结点的单链表L，p=L-next指向表中的第一个结点a1，即p-data=a1，而p-next-data=a2。其余依此类推。,2.3.2单链表上的基本运算,1.建立单链表,图2.9头插法建立单链表图示,用头插法建立单链表的算法：,LinklistCreateFromHead()LinkListL;Node*s;charc;intflag=1;/*设置一个标志变量flag，初值为1，当输入“$”时，将flag置为0，建表结束*/L=(Linklist)malloc(sizeof(Node);/*为头结点分配存储空间*/L-next=NULL;While(flag),c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);/*为读入的字符分配存储空间*/s-data=c;s-next=L-next;L-next=s;elseflag=0;returnL;=,【算法2.5用头插法建立单链表】,2）尾插法建表,图2.10尾插法建表图示,该算法的实现与头插法建表的不同之处在于指针的变化，其具体实现如下：,LinklistCreateFromTail()/*将新增的字符追加到链表的末尾*/LinkListL;Node*r,*s;intflag=1;/*设置一个标志，初值为1，当输入“$”时，flag为0，建表结束*/L=(Node*)malloc(sizeof(Node);/*为头结点分配存储空间*/L-next=NULL;r=L;/*r指针始终动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/while(flag),c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=s；elseflag=0;r-next=NULL;/*将最后一个结点的next链域置为空，表示链表的结束*/*while*/returnL;/*CreateFromTail*/,【算法2.6尾插法建表】,2.查找1）按序号查找在单链表中，由于每个结点的存储位置都放在其前一结点的next域中，因而即使知道被访问结点的序号i，也不能像顺序表那样直接按序号i访问一维数组中的相应元素，实现随机存取，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直至搜索到第i个结点为止。,算法描述：设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针L出发，从头结点（L-next）开始顺着链域扫描，用指针p指向当前扫描到的结点,初值指向头结点，用j做计数器，累计当前扫描过的结点数（初值为0），当j=i时，指针p所指的结点就是要找的第i个结点。,Node*Get(LinkListL,inti)/*在带头结点的单链表L中查找第i个结点，若找到(1in)，则返回该结点的存储位置;*/*否则返回NULL*/intj；Node*p；p=L；j=0；/*从头结点开始扫描*/while(p-next!=NULLp=L-next;/*从表中第一个结点比较*/while(p!KG-*2=NULL)if(p-data!KG-*2=key)p=p-next;elsebreak;/*找到结点key，退出循环*/returnp;/*Locate*/,【算法2.8在单链表L中查找值等于key的结点】,3.单链表插入操作算法描述：要在带头结点的单链表L中第i个位置插入一个数据元素e，需要首先在单链表中找到第i-1个结点并由指针pre指示，然后申请一个新的结点并由指针s指示，其数据域的值为e，并修改第i-1个结点的指针使其指向s，然后使s结点的指针域指向原第i个结点。插入结点的过程如图2.11所示。,L,.,线性表的链式存储结构可用C语言中的“结构指针”来描述,2.线性表的链式存储结构,带头结点的线性链表,data,next,typedefstructLNodeintdata;StructLNode*next;JD;,P,P,单链表的插入运算,S,在P所指向的结点之后插入新的结点,P,P,L,单链表的插入运算,S,单链表的插入运算,voidlbcr(JD*p,intx)/*在P所指向的结点之后插入新的结点*/JD*s;/*定义指向结点类型的指针*/s=(JD*)malloc(sizeof(JD);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;returnOK;,P,L,单链表的插入运算,voidlbcr(JD*p,intx)/*在P所指向的结点之后插入新的结点*/JD*s;/*定义指向结点类型的指针*/s=(JD*)malloc(sizeof(JD);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;returnOK;,P,L,单链表的插入运算,voidlbcr(JD*p,intx)/*在P所指向的结点之后插入新的结点*/JD*s;/*定义指向结点类型的指针*/s=(JD*)malloc(sizeof(JD);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;returnOK;,S,P,L,单链表的插入运算,voidlbcr(JD*p,intx)/*在P所指向的结点之后插入新的结点*/JD*s;/*定义指向结点类型的指针*/s=(JD*)malloc(sizeof(JD);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;returnOK;,S,P,L,单链表的插入运算,voidlbcr(JD*p,intx)/*在P所指向的结点之后插入新的结点*/JD*s;/*定义指向结点类型的指针*/s=(JD*)malloc(sizeof(JD);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;returnOK;,S,P,L,单链表的插入运算,voidlbcr(JD*p,intx)/*在P所指向的结点之后插入新的结点*/JD*s;/*定义指向结点类型的指针*/s=(JD*)malloc(sizeof(JD);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;returnOK;,voidlbsc(JD*p)/*删除p指针指向结点的后一个结点*/JD*q;if(p-next!=NULL)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/,单链表的删除运算,L,p,voidlbsc(JD*p)/*删除p指针指向结点的后一个结点*/JD*q;if(p-next!=NULL)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/,单链表的删除运算,L,p,voidlbsc(JD*p)/*删除p指针指向结点的后一个结点*/JD*q;if(p-next!=NULL)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/,单链表的删除运算,q,L,p,q,voidlbsc(JD*p)/*删除p指针指向结点的后一个结点*/JD*q;if(p-next!=NULL)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/,单链表的删除运算,L,p,q,voidlbsc(JD*p)/*删除p指针指向结点的后一个结点*/JD*q;if(p-next!=NULL)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/,单链表的删除运算,L,p,voidlbsc(JD*p)/*删除p指针指向结点的后一个结点*/JD*q;if(p-next!=NULL)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/,单链表的删除运算,例2-2编写一个算法，求单链表的长度。算法描述：可以采用“数”结点的方法来求出单链表的长度，用指针p依次指向各个结点,从第一个元素开始“数”，一直“数”到最后一个结点（p-next=NULL）。,intListLength(LinkListL)/*本算法用来求带头结点的单链表L的长度*/Node*p;p=L-next;j=0;/*用来存放单链表的长度*/while(p!=NULL)p=p-next;j+;returnj;/*EndoffunctionListLength*/,【算法2.11求单链表的长度】,例2-3如果以单链表表示集合，假设集合A用单链表LA表示，集合B用单链表LB表示，设计算法求两个集合的差，即A-B。算法思想：由集合运算的规则可知，集合的差A-B中包含所有属于集合A而不属于集合B的元素。具体做法是，对于集合A中的每个元素e，在集合B的链表LB中进行查找，若存在与e相同的元素，则从LA中将其删除。,voidDifference(LinkListLA,LinkListLB)/*此算法求两个集合的差集*/Node*pre;*p,*r;pre=LA;p=LA-next;/*p指向LA表中的某一结点，而pre始终指向p的前驱*/while(p!=NULL)q=LB-next;/*依次扫描LB中的结点，看是否有与LA中*p结点的值相同的结点*/while(q!=NULLif(q!=NULL),r=p;pre-next=p-next;p=p-next;free(r);elsepre=p;p=p-next;/*while(p!=NULL)*/,线性链表的查找操作：设无表头结点的线性链表的头指针为h,沿着链表的开始往后找结点x，若找到，则返回该结点在链表中的位置，否则返回空地址。JD*lbcz(JD*h,intx)JD*p;p=h;wh