线行链表及其运算.ppt

2.3线性表的链式存储及其运算,线性表的顺序存储结构存在缺点 是：插入与删除操作，需大量移动数据元素；再者，在顺序存储结构下，线性表的长度估计困难，并且当有多个顺序表同时共享计算机的存储空间时，不便于对存储空间进行动态分配。,由于线性表的顺序存储结构存在以上缺点，因此，对于大的线性表，特别是元素变动频繁的大线性表，不宜采用顺序存储结构，而是采用下面介绍的链式存储结构。,2.3.1线性表的链式存储,假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。若每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点。通过每个结点的指针域将n个结点按其逻辑顺序连接在一起而构成的数据存储结构，称为链式存储结构。,链式存储结构，既可用来表示线性结构，也可用来表示非线性结构。线性表的链式存储结构，称为线性链表。 对线性链表而言，它不要求逻辑上相邻的元素在物理位置上也相邻。其存储单元既可以是连续的，也可以是不连续的，甚至可以零散分布在内存中的任何位置上。,通常，为了适应线性链表的存储，计算机的存储空间被划分成一个一个的小块，每一小块占若干字节，这些小块就是存储结点。存储结点的结构。,在图中，data域就是数据域（或称值域），next域就是指针域（或称链域）,在线性链表中，用一个专门的头指针 head指向线性链表中第一个数据元素的结点（ 即存放线性链表中第一个数据元素的存储序号 ）。线性链表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空（用NULL 或0表示），表示链表终止。,用下面例子，来说明线性链表的存储结构。 设线性表为(a1，a2，a3，a4), 存储空间具有9个存储结点。,线性链表的物理存储状态举例,2.3.2线性链表的基本运算,1.单链表的基本运算 单链表结构类型定义如下： typedef struct node ElemType data; /*数值域*/ struct node *next; /*指针域*/ ListNode,*LinkList;,为了便于实现插入、删除结点的操作，通常在单链表的第一个结点之前增设一个表头结点。该结点的结构与表中其他结点的结构相同，其数据域可以不存储任何信息，也可以存储如线性表的表名、长度等附加信息；其指针域用来存放线性表中的第一个结点的地址。若线性表为空表，则表头结点的指针域为空，设H为单链表的头指针，指向头结点；存储单链表的第一个元素的结点称为开始结点（或称首结点），其指针域存放第二个结点的地址；称存储最后一个元素的结点称终端结点（或称尾结点），其指针域为空，如图3-5所示。,1）建立单链表,依据新结点插入位置的不同，将生成的单链表分为先进先出、后进先出及有序三种。 先进先出单链表：在建立单链表时，将每次生成的新结点，总是插入到当前链表的表尾作为尾结点。,若用换行符n作为输入结束标志，用rear作为总是指向链表尾结点的尾指针，则建立带表头结点的先进先出单链表的算法如下：,LinkList CreateList_ff( ) LinkList H,p,rear; char ch; 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作为输入结束标志，则建立带表头结点的后进先出单链表的算法如下：,LinkList CreateList_fr( ) LinkList H,p; char ch; 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为指向当前结点的指针，则建立带表头结点的有序单链表的算法如下：,LinkList CreateList_or( ) LinkList H,pre,cur; /*pre将指向当前结点的前件，cur将指向当前结点*/ char ch; 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个结点的算法如下：,LinkList GetElem(LinkList H, int i ) int j=1; /*j累计当前扫描的结点数*/ LinkList p; p=H-next; /*p指向第一个结点*/ while(p ,if(j=i /*第i个结点不存在，返回NULL*/ 在单链表中查找给定值的结点 依据给定的数据项的值x，在带表头结点的单链表中查找。若找到，则通过i返回首次找到的结点的位置，同时，返回指向该结点的指针p。若查找失败，则返回NULL。,在带表头结点的单链表H中查找x的算法： LinkList LocateElem(LinkList H, ElemType x,int *i) LinkList p; /*p为指针*/ p=H-next; /*p指向第一个结点*/ *i=1; while(p,if(p-data=x) return(p); /*找到返回结点位置*/ else return(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(LinkList H,int i,ElemType x) LinkList pre,cur; pre=GetElem(H ,i-1);/*调用查找函数使pre指向第i-1个结点*/,if(!pre) printf(“n i值不合法“); 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(LinkList H, ElemType x) LinkList cur,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(LinkList H,int i, ElemType *x) LinkList pre,cur; pre=GetElem(H,i-1); /*用GetElem函数找第i-1个结点并使pre指向它*/,if(pre=NULL|pre-next=NULL) /*判断i值是否合法*/ printf(“n i值不合法!“); 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(LinkList H , ElemType x) LinkList p,pre; p=H-next;/*p指向链表的第1个结点*/ pre=H; /*pre指向第1个结点的前件*/,while(p/*释放值为x的结点空间*/ ,else printf(“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链表之后。,定义链表结点结构如下： typedef struct node float coef; /*coef为多项式项的系数*/ int exp; /*exp为多项式项的x幂指数*/ struct node *next; ListNode, *LinkList; /*说明ListNode为结构体变量,LinkList为结构体指针*/,3.栈的链式存储结构及运算 栈的链式存储结构可通过单链表来实现，在单链表中，每一个结点表示栈中的一个元素。由于栈是在链表头部进行操作的，故链式栈不需要设置头结点。栈顶指针就是链表的头指针，它唯一的确定了一个栈。假设将元素a1,a2,a3,an顺序进栈，则a1为栈底元素，an为栈顶元素。,对链式栈的基本操作与顺序栈相类同，通常进栈和出栈，相对使用较多。 进栈就是向链栈的栈顶插入一个元素。此时，可使该元素结点的指针域，指向原来的栈顶结点，而栈顶指针则修改为指向该元素的结点，这样，该结点就成为新的栈顶结点。 出栈就是从链栈的栈顶删除一个元素。此时可取出栈顶元素并使栈顶指针指向原栈顶结点的后继结点。链栈的类型说明及其常见基本操作如下： 1） 链栈的类型说明,typedef char ElemType; /* 新类型ElemType是字符型*/ typedef struct stacknode ElemType data;/*栈的值域是字符型*/ struct stacknode *next; StackNode; /*StackNode为结构型*/ typedef struct StackNode *top;/*栈顶指针*/ LinkStack; /*LinkStack为结构类型*/,2) 链栈的基本操作 构造一个空链栈 void InitStack(LinkStack *s) s-top=NULL; /*栈顶指针置空*/ 判断链栈是否为空栈 int StackEmpty(LinkStack *s) /*若栈空，则返回1否则返回0*/ return s-top=NULL; ,进栈（入栈或压栈） void push(LinkStack *s,ElemType x) 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; /*修改栈顶指针*/ ,退栈（出栈） ElemType pop(LinkStack *s) ElemType x; StackNode *p; p=s-top; if(StackEmpty(s) /*调用判断栈是否为空的函数，若栈空，则下溢*/ printf(“n 栈已空，下溢！“); exit(1); ,x=p-data; /*x赋值欲删的栈顶结点数据*/ s-top=p-next; /*删除栈顶结点，修改栈顶指针*/ free(p); /*释放已删结点的空间*/ return x;/*返回已删结点的数据*/ ,读链栈的栈顶元素 ElemType GetTop(LinkStack *s) if(StackEmpty(s) printf(“n 栈已空！“); exit(1); return s-top-data; /*若链栈非空，则返回栈顶元素，但不删除*/ ,4. 栈的应用举例 数制转换过程是栈的典型应用。例如将一个十进制整数n转换为r进制数，通常采用“除基数r取余法”的转换方法（即先将n逐次除以r，然后倒序写出余数）。在转换过程中依次所得的余数，就是由低到高得到的r进制数中的每一位数字。系统将余数存储到一个栈中，第一个余数存在栈底、最后一个余数存在栈顶。输出时，系统从栈顶依次释放余数所占存储区，也就是说由高到低输出每一数位的值，最终得到转换结果。图4-4所示的是将十进制数74转换为八进制数的过程，结果为八进制数112。,下面给出将十进制正整数n转换为r进制数的程序。,#include #include /*头文件stdlib.h中含有exit()*/ #define MaxSize 100 /*说明欲分配的栈空间最多为100个元素*/ typedef int ElemType; /*说明栈元素的数据类型为整型*/,typedef struct ElemType stackMaxSize; int top; SeqStack;/* SeqStack为结构类型*/ void InitStack(SeqStack *s) /*将顺序栈s初始化为空栈*/ s-top=-1; int StackEmpty(SeqStack *s) /*判断栈s是否为空若为空则返回1*/ return s-top=-1; ,void push(SeqStack *s,ElemType x) /*进栈，即向栈s中插入元素*/ if(s-top=MaxSize-1) printf(“n stack overflow!“); exit(1); +s-top; s-stacks-top=x; ,int pop(SeqStack *s) /*退栈，即删除栈s的栈顶元素*/ if(StackEmpty(s) printf(“n stack underflow!“); exit(1); return s-stacks-top-; ,void conversion(long num,int r) /*用除r取余法将结果保存到栈s中*/ SeqStack s; int k; int x; InitStack(/*修改num的值为被r除的商*/ ,printf(“n“) ; while(!StackEmpty( ,void main() /*主函数*/ long n;,int r; printf(“n inpute n,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所指单元始终为空）先给出循环队列类型的定义；再给出用此方法实现循环队列的几种基本操作。,#define MAXSIZE 100 /*符号常量MAXSIZE代表队列的最大容量100*/ typedef char ElemType; /*说明新类型ElemType是字符型*/ typedef struct ElemType dataMAXSIZE; int front; int rear; CircularQueue; /*新类型CircularQueue是结构体*/,1） 构造一个空队列 Void InitQueue(CircularQueue *q) q-front=q-rear=0; 2）判断队列空 int QueueEmpty(CircularQueue *q) /*队列为空返回1，否则返回0*/ if(q-front=q-rear) exit(1); else exit(0); ,3）入队 void InsertQueue(CircularQueue *q, ElemType x) if(q-rear+1)%MAXSIZE=q-front) printf(“n 队满，上溢！“); exit(1); q-dataq-rear=x; /*新元素插入到队尾*/ q-rear=(q-rear+1)%MAXSIZE; /*尾指针加1*/ ,4）出队 ElemType DeleteQueue(CircularQueue *q) ElemType x; if(QueueEmpty(q) printf(“n 队空，下溢！“); exit(1); x=q-dataq-front; /*取出队头元素*/ q-front=(q-front+1)%MAXSIZE; /*队头指针加1*/ return x; ,5）读取队头元素 ElemType GetHead(CircularQueue *q) ElemType x; if(QueueEmpty(q) printf(“n 队空，下溢！“); exit(1); x=q-dataq-front; /*取出队头元素*/ return x; ,4.链队列 队列的链式存储结构称为链队列。因为需要在表头进行删除操作和在表尾进行插入操作，所以在链队列中，需要使用队头和队尾两个指针。其中队尾指针指向链队列的最后一个结点。于是，一个链队列就由一个头指针和一个尾指针唯一地确定了。链队列和线性表的单链表一样，为了操作方便，可以给链队列增加一个头结点，并令头指针指向头结点，如图4-8所示。 链队列的类型定义如下：,typedef char ElemType; typedef struct queuenode /*链队列中的结点类型 */ ElemType data; struct queuenode *next; QueueNode; typedef struct /*将两个指针封装在一起*/ QueueNode *front;/*队头指针*/ QueueNode *rear; /*队尾指针*/ LinkQueue;,图4-8（a）是空链队列的示意图，图中q为LinkQueue型指针；图4-8（b）是非空链队列的示意图。,链队列的基本操作有5种，相应的算法如下： 1）构造一个空队列 void InitQueue(LinkQueue *q) q-front=q-rear=(QueueNode *) malloc(sizeof(QueueNode); /*建新结点*/ if(!q-front) printf(“n 存储分配失败!“); exit(1); q-front-next=NULL; ,2）判断空队列 int QueueEmpty(LinkQueue *q) if(q-front=q-rear 3）入队 void InsQueue(LinkQueue *q, ElemType x), 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）出队 ElemType DelQueue(LinkQueue *q) QueueNode *p; ElemType x; if(QueueEmpty(q) printf(“n 队列空，下溢！“); exit(1); ,p=q-front-next; /*指向队头结点*/ x=p-data; /*取出队头结点的数据*/ q-front-next=p-next; /*修改队头指针即将队头指针从链上摘下*/ if(q-rear=p) q-rear=q-front; /*若取出队头元素后，原队列为空，修改队尾指针*/ free(p); /*释放被删的队头结点*/ return(x); /*返回队头结点的数据*/ ,5）读取队头元素 ElemType GetHead(LinkQueue *q) QueueNode *p; ElemType x; if(QueueEmpty(q) printf(“n 队列空，下溢！“)； exit(1); p=q-front-next; /*指向队头结点*/ x=p-data; /*取出队头结点的数据*/ return(x); /*返回队头结点的数据*/ ,5.队列应用举例,例如，某银行储蓄所有一个服务窗口，该窗口在某个时刻只能接待一位顾客，假设为一位顾客服务的时间为定值，在顾客人数众多时需要在窗口排队，若队列用q表示，顾客到达的