2.3 线行链表及其运算.ppt

2.3线性表的链式存储及其运算,线性表的顺序存储结构存在缺点是：插入与删除操作，需大量移动数据元素；再者，在顺序存储结构下，线性表的长度估计困难，并且当有多个顺序表同时共享计算机的存储空间时，不便于对存储空间进行动态分配。,由于线性表的顺序存储结构存在以上缺点，因此，对于大的线性表，特别是元素变动频繁的大线性表，不宜采用顺序存储结构，而是采用下面介绍的链式存储结构。,2.3.1线性表的链式存储,假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。若每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点。通过每个结点的指针域将n个结点按其逻辑顺序连接在一起而构成的数据存储结构，称为链式存储结构。,链式存储结构，既可用来表示线性结构，也可用来表示非线性结构。线性表的链式存储结构，称为线性链表。对线性链表而言，它不要求逻辑上相邻的元素在物理位置上也相邻。其存储单元既可以是连续的，也可以是不连续的，甚至可以零散分布在内存中的任何位置上。,通常，为了适应线性链表的存储，计算机的存储空间被划分成一个一个的小块，每一小块占若干字节，这些小块就是存储结点。存储结点的结构。,在图中，data域就是数据域（或称值域），next域就是指针域（或称链域）,在线性链表中，用一个专门的头指针head指向线性链表中第一个数据元素的结点（即存放线性链表中第一个数据元素的存储序号）。线性链表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空（用NULL或0表示），表示链表终止。,用下面例子，来说明线性链表的存储结构。设线性表为(a1，a2，a3，a4),存储空间具有9个存储结点。,线性链表的物理存储状态举例,2.3.2线性链表的基本运算,1.单链表的基本运算单链表结构类型定义如下：typedefstructnodeElemTypedata;/*数值域*/structnode*next;/*指针域*/ListNode,*LinkList;,为了便于实现插入、删除结点的操作，通常在单链表的第一个结点之前增设一个表头结点。该结点的结构与表中其他结点的结构相同，其数据域可以不存储任何信息，也可以存储如线性表的表名、长度等附加信息；其指针域用来存放线性表中的第一个结点的地址。若线性表为空表，则表头结点的指针域为空，设H为单链表的头指针，指向头结点；存储单链表的第一个元素的结点称为开始结点（或称首结点），其指针域存放第二个结点的地址；称存储最后一个元素的结点称终端结点（或称尾结点），其指针域为空，如图3-5所示。,1）建立单链表,依据新结点插入位置的不同，将生成的单链表分为先进先出、后进先出及有序三种。先进先出单链表：在建立单链表时，将每次生成的新结点，总是插入到当前链表的表尾作为尾结点。,若用换行符n作为输入结束标志，用rear作为总是指向链表尾结点的尾指针，则建立带表头结点的先进先出单链表的算法如下：,LinkListCreateList_ff()LinkListH,p,rear;charch;H=(LinkList)malloc(sizeof(ListNode);/*生成表头结点*/,if(!H)printf(n存储分配失败);exit(1);H-next=NULL;/*表初值为空*/rear=H;/*尾指针指向表头结点*/while(ch=getchar()!=n)p=(LinkList)malloc(sizeof(ListNode);/*生成新结点*/,if(!p)printf(n存储分配失败);exit(1);p-data=ch;p-next=p;/*新结点插入表尾*/rear=p;/*尾指针指向新结点*/return(H);/*返回头指针*/,后进先出表：在建立单连表时，将每次生成的新结点，总是插入到当前链表的表头结点之后作为当前链表的首结点。若用换行符n作为输入结束标志，则建立带表头结点的后进先出单链表的算法如下：,LinkListCreateList_fr()LinkListH,p;charch;H=(LinkList)malloc(sizeof(ListNode);/*生成表头结点*/,if(!H)printf(n存储分配失败);exit(1);H-next=NULL;/*表初值为空*/while(ch=getchar()!=n)p=(LinkList)malloc(sizeof(ListNode);/*生成新结点*/,if(!p)printf(n存储分配失败);exit(1);p-data=ch;p-next=H-next;H-next=p;/*插入表头结点之后*/return(H);/*返回头指针*/,有序单链表：是指原表中结点的数据值，按从小到大（或从大到小）的顺序排列。为了建立一个有序单链表，每次生成的新结点，总是插入到当前链表的合适位置。在带表头结点的单链表中，所有位置上的插入操作都是一致的，不需要做特殊处理。,若用换行符n作为输入结束标志，pre为指向当前结点前件的指针、cur为指向当前结点的指针，则建立带表头结点的有序单链表的算法如下：,LinkListCreateList_or()LinkListH,pre,cur;/*pre将指向当前结点的前件，cur将指向当前结点*/charch;H=(LinkList)malloc(sizeof(ListNode);/*生成表头结点*/if(!H)printf(n存储分配失败);exit(1);,H-next=NULL;/*表初值为空*/while(ch=getchar()!=n)pre=H;/*pre指向当前结点的前件*/cur=H-next;/*cur指当前结点*/while(cur,cur=(LinkList)malloc(sizeof(ListNode);/*生成新结点*/if(!cur)printf(n存储分配失败);exit(1);cur-data=ch;cur-next=pre-next;/*新结点插在pre所指结点的后面*/,pre-next=cur;/*尾指针指向新结点*/return(H);/*返回头指针*/容易看出，以上3个算法的时间复杂度均为O(n)。,2）查找结点在对单链表进行插入或删除运算时，总是首先要找到插入或删除的位置，这就需要对线性链表进行扫描查找。,通常，有查找第i个结点或查找具有给定元素值的结点，两种情况。查找单链表中的第i个结点在带表头结点的单链表中，查找第i个结点。不能像在顺序表中那样，只能从单链表的头指针出发，沿着结点的链域逐个向下，直到搜索到第i个结点为止。此时，p指向第i个结点。在带表头结点的单链表H中，查找第i个结点的算法如下：,LinkListGetElem(LinkListH,inti)intj=1;/*j累计当前扫描的结点数*/LinkListp;p=H-next;/*p指向第一个结点*/while(p,if(j=i/*第i个结点不存在，返回NULL*/在单链表中查找给定值的结点依据给定的数据项的值x，在带表头结点的单链表中查找。若找到，则通过i返回首次找到的结点的位置，同时，返回指向该结点的指针p。若查找失败，则返回NULL。,在带表头结点的单链表H中查找x的算法：LinkListLocateElem(LinkListH,ElemTypex,int*i)LinkListp;/*p为指针*/p=H-next;/*p指向第一个结点*/*i=1;while(p,if(p-data=x)return(p);/*找到返回结点位置*/elsereturn(NULL);/*没找到返回NULL*/以上两个，查找算法的时间复杂度均为O(n)。3）单链表的插入单链表的插入，是指在单链表中插入一个新结点。有两种情况：在单链表的第i个位置插入一个新结点和在有序单链表中插入一个新结点。,在单链表的第i个位置插入一个新结点假设单链表中有n个结点，插入位置i的允许取值范围为1至n+1。在第i个位置插入一个新结点，首先，要找到第i-1个结点，然后将新结点插入到第i-1个结点之后。若指针pre指向第i-1个结点，cur指向新结点，插入就是让新结点的指针域指向原来的第i个结点，即cur-next=pre-next，并且修改第i-1个结点的指针域，让其指向新结点。即pre-next=cur。插入过程如图3-6所示：,在第i个位置，插入一个值为x的新结点算法：InsertList(LinkListH,inti,ElemTypex)LinkListpre,cur;pre=GetElem(H,i-1);/*调用查找函数使pre指向第i-1个结点*/,if(!pre)printf(ni值不合法);exit(1);cur=(LinkList)mallco(sizeof(ListNode);/*生成新结点*/if(!cur)printf(n存储分配失败);exit(1);,cur-data=x;/*新结点的值为x*/cur-next=pre-next;/*新结点的指针域值指向原来的第i个结点*/pre-next=cur;/*第i-1个结点的指针域值指向新结点*/,在有序单链表中插入一个新结点要在一个带表头结点的有序单链表H中插入一个值为x的新结点。就必须对生成的新结点，依据值x的大小在表中找到合适的插入位置，然后将其插入到链表中。算法如下：,InsertOrder(LinkListH,ElemTypex)LinkListcur,pre;pre=H;cur=H-next;while(cur/*cur指向当前结点*/,cur=(LinkList)malloc(sizeof(ListNode);/*生成新结点*/if(!cur)printf(n存储分配失败);exit(1);cur-data=x;/*新结点值为x*/cur-next=pre-next;/*插入新结点*/pre-next=cur;/*pre指向新结点*/,从单链表插入新结点的过程中，可以看出对线性链表进行插入操作时，没有发生数据元素的移动，只是改变了有关结点的指针域。在以上两个插入结点的算法中，时间复杂度的数量级均为O(n)。,4）单链表的删除操作单链表的删除操作，是指在单链表中，删除包括指定元素的结点。有两种情况：一是删除单链表的第i个结点，二是删除单链表中，具有给定值x的结点。均不移动表中的数据元素，只需改变，被删除结点的前一个结点指针。,删除单链表的第i个结点设单链表中有n个结点，删除第i个结点时，i的允许取值范围为1至n。与插入类似，首先要找到第i-1个结点。再用指针pre指向该结点，用指针cur指向第i个结点。然后使第i-1个结点的指针指向第i+1个结点(pre-next=cur-next)。最后用函数free释放第i个结点所占空间。在带表头结点的单链表H中，删除第i个结点的算法如下：,DeleteList1(LinkListH,inti,ElemType*x)LinkListpre,cur;pre=GetElem(H,i-1);/*用GetElem函数找第i-1个结点并使pre指向它*/,if(pre=NULL|pre-next=NULL)/*判断i值是否合法*/printf(ni值不合法!);exit(1);cur=pre-next;/*cur指第i个结点*/pre-next=cur-next;/*使第i-1个结点的指针指向第i+1个结点*/*x=cur-data;/*第i个结点的值由x返回*/free(cur);/*释放第i个结点所占的空间*/,删除单链表中具有给定值的结点在带表头结点的单链表H中，搜索具有给定值x的结点，若找到，就删除该结点。这种删除情况的算法如下：,DeleteList2(LinkListH,ElemTypex)LinkListp,pre;p=H-next;/*p指向链表的第1个结点*/pre=H;/*pre指向第1个结点的前件*/,while(p/*释放值为x的结点空间*/,elseprintf(n链表中没有具有值为x的结点);此算法的时间复杂度的数量级为O(n)。,2.循环链表及其基本运算从单链表任一结点出发查找其前面的结点是很困难的。为了克服这一缺点，我们使带表头结点的单链表中的最后一个结点的指针指向头结点，使整个链表构成一个环形，这种链式存储结构被称为循环链表。特别地，只有头结点的循环链表称为空循环链表。,带头结点的循环链表中，可看出循环链表的结构与前面所讨论的单链表相比，具有以下两个特点：,1）头结点的数据域为任意或者根据需要来设置，头结点的指针域指向线性表的第一个元素的结点，头指针指向表头结点。2）最后一个结点的指针域不是NULL，而是指向表头结点。即在循环链表中没有空指针，所有结点的指针构成了一个环状链。在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这一点。,循环链表的插入和删除的方法与线性单链表基本相同，不再赘述。只须注意一点：在单链表的结构中，空表的条件是H-next=NULL,而在循环链表结构中，空表的条件是H-next=H。,3.双向链表从循环链表的结构特征可看出，若要找一个结点的直接前件结点需要兜一个圈子才行，这当然是很不方便的。就像乘单向环行的公交车一样，若坐过了站，就要多坐许多站,才能到达预定的地点。因此，任何城市的公交车，除单行道外，都是双向行驶的。为类似的目的，可以将单向链表改为双向链表。,双向链表的每个结点含有两个指针域：一个指向其直接前件结点，称为prior；一个指向其直接后件结点，称为next。,有了两个方向的链指针之后，在链表上进行访问非常方便，但是在双向链表上进行插入和删除运算，要涉及两个指针的链接，故比单链表的插入与删除运算复杂些。,2.3.3线性链表应用举例,设多项式Pn(x)=a0+a1x+a2x2+anxn其中ai(i=0,1,2,n)是x的i次幂的系数（即x的幂指数为i）。线性表（a0,a1,a2,an）可唯一确定多项式Pn(x)。两个多项式相加，如果采用顺序存储结构来存储此线性表，由于多项式中可能有多项的系数为0，顺序存储就会浪费大量存储空间。故应采用单链表来存储该线性表。在单链表中，每个结点设3个域，分别为系数域coef，指数域exp和指针域next。,例如，多项式a(x)=4+3x+7x5+8x7与多项式b(x)=3-7x5+6x6相加，所得的和，为多项式c(x)=a(x)+b(x)=7+3x+6x6+8x7的单链表形式。,从图可清楚地看出，多项式a(x)与b(x)相加的结果为多项式c(x)，变成由单链表Ha和Hb，求单链表Hc了。,假设单链表是以x的幂指数值的递增顺序排列。指针pa、pb分别指向Ha、Hb当前正被考察的两个结点。,比较两个结点的指数域，有以下3种情况：,pa-expexp，将pa所指的结点插入到Hc链表中，移动指针pa指向下一结点。pa-exppb-exp，将pb所指的结点插入到Hc链表中，移动指针pb指向下一结点。pa-exp=pb-exp，将两个结点中的系数相加，若和不为0，则插入到Hc链表中，移动指针pa、pb，指向下一结点。重复上述过程，直至pa或pb的值为NULL。当其中一个为空时，说明该表的结点已经处理完，只要将另一表的剩余部分链接到Hc链表之后。,定义链表结点结构如下：typedefstructnodefloatcoef;/*coef为多项式项的系数*/intexp;/*exp为多项式项的x幂指数*/structnode*next;ListNode,*LinkList;/*说明ListNode为结构体变量,LinkList为结构体指针*/,3.栈的链式存储结构及运算栈的链式存储结构可通过单链表来实现，在单链表中，每一个结点表示栈中的一个元素。由于栈是在链表头部进行操作的，故链式栈不需要设置头结点。栈顶指针就是链表的头指针，它唯一的确定了一个栈。假设将元素a1,a2,a3,an顺序进栈，则a1为栈底元素，an为栈顶元素。,对链式栈的基本操作与顺序栈相类同，通常进栈和出栈，相对使用较多。进栈就是向链栈的栈顶插入一个元素。此时，可使该元素结点的指针域，指向原来的栈顶结点，而栈顶指针则修改为指向该元素的结点，这样，该结点就成为新的栈顶结点。出栈就是从链栈的栈顶删除一个元素。此时可取出栈顶元素并使栈顶指针指向原栈顶结点的后继结点。链栈的类型说明及其常见基本操作如下：1）链栈的类型说明,typedefcharElemType;/*新类型ElemType是字符型*/typedefstructstacknodeElemTypedata;/*栈的值域是字符型*/structstacknode*next;StackNode;/*StackNode为结构型*/typedefstructStackNode*top;/*栈顶指针*/LinkStack;/*LinkStack为结构类型*/,2)链栈的基本操作构造一个空链栈voidInitStack(LinkStack*s)s-top=NULL;/*栈顶指针置空*/判断链栈是否为空栈intStackEmpty(LinkStack*s)/*若栈空，则返回1否则返回0*/returns-top=NULL;,进栈（入栈或压栈）voidpush(LinkStack*s,ElemTypex)StackNode*p;p=(StackNode*)malloc(sizeof(StackNode);if(!p)printf(n存储分配失败！);exit(1);p-data=x;/*新结点值域赋值x*/p-next=s-top;/*新结点*p插入到栈顶*/s-top=p;/*修改栈顶指针*/,退栈（出栈）ElemTypepop(LinkStack*s)ElemTypex;StackNode*p;p=s-top;if(StackEmpty(s)/*调用判断栈是否为空的函数，若栈空，则下溢*/printf(n栈已空，下溢！);exit(1);,x=p-data;/*x赋值欲删的栈顶结点数据*/s-top=p-next;/*删除栈顶结点，修改栈顶指针*/free(p);/*释放已删结点的空间*/returnx;/*返回已删结点的数据*/,读链栈的栈顶元素ElemTypeGetTop(LinkStack*s)if(StackEmpty(s)printf(n栈已空！);exit(1);returns-top-data;/*若链栈非空，则返回栈顶元素，但不删除*/,4.栈的应用举例数制转换过程是栈的典型应用。例如将一个十进制整数n转换为r进制数，通常采用“除基数r取余法”的转换方法（即先将n逐次除以r，然后倒序写出余数）。在转换过程中依次所得的余数，就是由低到高得到的r进制数中的每一位数字。系统将余数存储到一个栈中，第一个余数存在栈底、最后一个余数存在栈顶。输出时，系统从栈顶依次释放余数所占存储区，也就是说由高到低输出每一数位的值，最终得到转换结果。图4-4所示的是将十进制数74转换为八进制数的过程，结果为八进制数112。,下面给出将十进制正整数n转换为r进制数的程序。,#include#include/*头文件stdlib.h中含有exit()*/#defineMaxSize100/*说明欲分配的栈空间最多为100个元素*/typedefintElemType;/*说明栈元素的数据类型为整型*/,typedefstructElemTypestackMaxSize;inttop;SeqStack;/*SeqStack为结构类型*/voidInitStack(SeqStack*s)/*将顺序栈s初始化为空栈*/s-top=-1;intStackEmpty(SeqStack*s)/*判断栈s是否为空若为空则返回1*/returns-top=-1;,voidpush(SeqStack*s,ElemTypex)/*进栈，即向栈s中插入元素*/if(s-top=MaxSize-1)printf(nstackoverflow!);exit(1);+s-top;s-stacks-top=x;,intpop(SeqStack*s)/*退栈，即删除栈s的栈顶元素*/if(StackEmpty(s)printf(nstackunderflow!);exit(1);returns-stacks-top-;,voidconversion(longnum,intr)/*用除r取余法将结果保存到栈s中*/SeqStacks;intk;intx;InitStack(/*修改num的值为被r除的商*/,printf(n);while(!StackEmpty(,voidmain()/*主函数*/longn;,intr;printf(ninputen,r:);scanf(%ld,%d,/*调用转换函数并输出转换结果*/注：r可为8、2、16等。例如，当运行此程序时，n为74，r为2，则转换结果为二进制数1001010。,4.2队列及其基本运算,1.什么是队列,队列（queue）是一种只允许在表的一端进行插入，而在另一端进行删除的线性表。允许插入（入队）的一端称为队尾（rear），允许删除（出队）的一端称为队头（front）。不含元素的队列称为空队列。若将元素按a1,a2,a3,an的顺序入队，则a1为队头元素，an为队尾元素，如图4-5所示。,退出队列时，也只能按a1,a2,a3,an的顺序出队。这和日常生活中的排队是一致的。,在队列中，最先插入的元素，将最先能够被删除。反之，最后插入的元素，将最后才能被删除。因此，队列又称为“先进先出”或后进后出的线性表。,队列也有顺序存储和链式存储两种情况。,2.队列的顺序存储结构和基本运算,队列的顺序存储结构称为顺序队列。顺序队列通常用一个一维数组来存放队列中的数据元素。此外，还需设置两个整形变量front和rear作为队头指示器和队尾指示器，分别指示队头和队尾元素在向量空间中的位置。,我们约定在队列初始化时，这两个指示器均置0值。入队时，将新元素插入到rear所指位置后，再将rear的值加1；出队时，删除front所指位置的元素后，再将front的值加1并返回被删元素。由此可见，当队头和队尾指示器值相等时，队列为空。在非空队列里，front始终指向队头元素，而rear始终指向队尾元素的下一位置。在队列中，队尾指示器rear与队头指示器front共同反映了队列中元素动态变化的情况。,假设给队列分配的最大存储空间为4(如图4-6所示)。在图4-6(b)所示满队列状态下，如果还有新元素请求入队，则会出现“上溢”错误。,在图4-6(c)所示状态下，如果还有新元素请求入队，这时，虽然队列的实际可用空间没有占满，但由于尾指针已超越存储空间的上界，故不能做入队操作，否则会出现“假上溢”的错误；在图4-6(d)所示状态下，如果还要进行出队操作，由于这时队列已空，队列的头、尾指针均已超越存储空间的上界，故不能进行出队操作，否则会出现“下溢”的错误。,3.循环队列及其运算为避免发生顺序队列的“假上溢”现象，充分利用队列的存储空间，可以将顺序队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，我们称这样的队列为循环队列，如图4-7所示。,在循环队列中进行出队、入队操作时，头、尾指针仍要加1，只不过当头尾指针指向上界时，其加1的操作结果是指向下界0。假设当前循环队列最多能容纳MAXSIZE个元素，这种循环意义下的加1操作可表示为：,i=(i+1)%MAXSIZE/*i表示front或rear*/,在图4-7所示的循环队列中，队列的最大容量是4。在图4-7(b)所示的状态下，再插入元素D，则队列空间就会被占满，变成图4-7(c)所示的状态。此时，存在与4-7(a)相,同的front=rear关系。由此可知，在循环队列中，仅依据头尾指针相等，是无法判断队列是“空”还是“满”。要解决这个问题，常用的方法是：少用一个元素空间，约定入队前，若尾指针加1后等于头指针，则认为队列满（rear所指单元始终为空）先给出循环队列类型的定义；再给出用此方法实现循环队列的几种基本操作。,#defineMAXSIZE100/*符号常量MAXSIZE代表队列的最大容量100*/typedefcharElemType;/*说明新类型ElemType是字符型*/typedefstructElemTypedataMAXSIZE;intfront;intrear;CircularQueue;/*新类型CircularQueue是结构体*/,1）构造一个空队列VoidInitQueue(CircularQueue*q)q-front=q-rear=0;2）判断队列空intQueueEmpty(CircularQueue*q)/*队列为空返回1，否则返回0*/if(q-front=q-rear)exit(1);elseexit(0);,3）入队voidInsertQueue(CircularQueue*q,ElemTypex)if(q-rear+1)%MAXSIZE=q-front)printf(n队满，上溢！);exit(1);q-dataq-rear=x;/*新元素插入到队尾*/q-rear=(q-rear+1)%MAXSIZE;/*尾指针加1*/,4）出队ElemTypeDeleteQueue(CircularQueue*q)ElemTypex;if(QueueEmpty(q)printf(n队空，下溢！);exit(1);x=q-dataq-front;/*取出队头元素*/q-front=(q-front+1)%MAXSIZE;/*队头指针加1*/returnx;,5）读取队头元素ElemTypeGetHead(CircularQueue*q)ElemTypex;if(QueueEmpty(q)printf(n队空，下溢！);exit(1);x=q-dataq-front;/*取出队头元素*/returnx;,4.链队列队列的链式存储结构称为链队列。因为需要在表头进行删除操作和在表尾进行插入操作，所以在链队列中，需要使用队头和队尾两个指针。其中队尾指针指向链队列的最后一个结点。于是，一个链队列就由一个头指针和一个尾指针唯一地确定了。链队列和线性表的单链表一样，为了操作方便，可以给链队列增加一个头结点，并令头指针指向头结点，如图4-8所示。链队列的类型定义如下：,typedefcharElemType;typedefstructqueuenode/*链队列中的结点类型*/ElemTypedata;structqueuenode*next;QueueNode;typedefstruct/*将两个指针封装在一起*/QueueNode*front;/*队头指针*/QueueNode*rear;/*队尾指针*/LinkQueue;,图4-8（a）是空链队列的示意图，图中q为LinkQueue型指针；图4-8（b）是非空链队列的示意图。,链队列的基本操作有5种，相应的算法如下：1）构造一个空队列voidInitQueue(LinkQueue*q)q-front=q-rear=(QueueNode*)malloc(sizeof(QueueNode);/*建新结点*/if(!q-front)printf(n存储分配失败!);exit(1);q-front-next=NULL;,2）判断空队列intQueueEmpty(LinkQueue*q)if(q-front=q-rear3）入队voidInsQueue(LinkQueue*q,ElemTypex),QueueNode*p;p=(QueueNode*)malloc(sizeof(QueueNode);if(!p)printf(n存储分配失败！);exit(1);p-data=x;p-next=NULL;q-rear-next=p;/*新结点插入到队尾*/q-rear=p;/*队尾指针指向新结点*/,4）出队ElemTypeDelQueue(LinkQueue*q)QueueNode*p;ElemTypex;if(QueueEmpty(q)printf(n队列空，下溢！);exit(1);,p=q-front-next;/*指向队头结点*/x=p-data;/*取出