第 3 章 栈与队列 3.4.ppt

Status InitQueue_L(LinkQueue Q) { //建一个空队列Q.from=Q.rear=(QueuePtr)malloc (sizeof(QNode)); //为链队列的头结点分配空间  if (!Q.front) exit(OVERFLOW); Q.front-next=NULL; return OK;} //InitQueue_L 链队列基本操作算法 Q.front Q.rear ∧ 空链队列 链队列的 头结点 1）初始化操作InitQueue_L(LinkQueue Q)  2) 销毁操作DestroyQueue_L(LinkQueue Q) Q.front Q.rear J1 ∧ Q.front Q.rear J2 ∧ null null 销毁前 销毁后 Status DestroyQueue_L(LinkQueue Q) { //销毁队列Q if (!Q.front) return ERROR; // 链队列不存在 while(Q.front-next) { // 回收链队列的所有元素结点空间 p=Q.front-next; Q.front-next=p-next; free(p); } free(Q.front ); // 回收链队列头结点空间 Q.front=Q.rear=null; return OK; }//DestroyQueue_L Q.front ∧ J1 ∧ Q.rear e ∧ e入队前 e入队后 J1 ∧ Q.front Q.rear 3）入队操作EnQueue_L(LinkQueue Q, QElemType ) 入队操作图示 Status EnQueue_L(LinkQueue Q, QElemType ) { //在链队列Q队尾，插入新的队尾结点 p=(QueuePtr)malloc(sizeof(QNode)); //为新元素e分配结点空间  if (!p) exit (OVERFLOW); //存储分配失败 p-date=e; p-next=NULL; Q.rear-next=p; //修改队尾指针，插入新队尾结点 Q.rear=p; return OK; } Q.front Q.rear ∧ J1 ∧ e ∧ J1 在链队列Q队尾，插入新的元素e 4）出队操作DeQueue_L(LinkQueue Q, QElemTypee) Q.front Q.rear 元素J1出队列图示 J1 J2 ∧ J1 e Status DeQueue_L(LinkQueue Q, QElemType e) { //若队列不空，则删除Q的队头元素结点，用e返回其值，并返回OK；否则返回ERROR if (Q.front = =Q.rear) return ERROR; //若队列空，返回ERROR p=Q.front-next; // p指向队头元素结点 e=p-data; Q.front-next=p-next; // 修改链队列头结点指针 if(Q.rear= =p)Q.rear=Q.front; // 对于链队列只有一个元素结点的情况,要同时修改队尾指针 free(p); return OK; } 作业 1.有A,B,C,D四辆列车顺序进入栈式结构的站台,问这四辆列车开出站台序列有多少种,并写出具体序列. 2.假设Q[1…10]是一个顺序队列,初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状态变化情况,若不能入队,请指出其元素,并说明理由. d,e,b,g,h入队，d,e出对，I,j,k,l,m入队 3.编写一个算法，利用队列的基本运算返回指定队列中的最后一个元素。 * 1．什么是递归 递归是一个很有用的工具，在数学和程序设计等许多领域中都用到了递归。递归定义：简单地说，一个用自己定义自己的概念,称为递归定义。 例 n!= 1*2*3*4*…*(n-1)*n n!递归定义 n!= 1 当