数据结构与chapter3b .pptVIP

1）初始化操作 InitQueue(LinkQueue Q) { //构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); //为链队列的头结点分配空间 if(!Q.front)exit(OVERFLOW); Q.front-next=NULL; return OK; } 三 链队列基本操作算法 链队列的 头结点 Q.rear Q.front ^ 空链队列 2) 销毁操作DestroyQueue_L(LinkQueue Q) Status DestroyQueue_L(LinkQueue Q) {//销毁队列Q if (!Q.front) return ERROR; // 链队列不存在 while(Q.front) { Q.rear=Q.front-next;  free(Q.front); Q.front=Q.rear } return OK; } Q.front a1 an ^ … 销毁前 Q.rear Q.front=NULL Q.rear=NULL 销毁后 3）入队操作EnQueue(LinkQueue Q,QElemType e) { //队列Q存在,插入元素e为Q的队尾元素 p=(QueuePtr)malloc(sizeof(QNode)); //为新元素e分配结点空间 if(!p) exit(OVERFLOW); //存储分配失败 p-data=e; p-next=NULL; Q.rear-next=p; //插入新队尾结点 Q.rear=p; //修改队尾指针， return OK; } Q.front ∧ J1 ∧ Q.rear J1 在链队列Q队尾，插入新的元素e e ∧ Status DeQueue(LinkQueue Q,QElemType e) { //Q为非空队列,删除Q的队头元素,并用e返回其值 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; } 元素J1出队列图示 J1 Q.front Q.rear J2 ∧ 3.4.2 循环队列－队列的顺序表示和实现 　 队列的顺序存储结构称为顺序队列，和顺序栈一样，顺序队列也是用一组地址连续的存储单元依次存放从队列头到队列尾的元素。 由于队列的队头和队尾的位置是变化的，因而要设两个指针front和rear分别指示队头和队尾元素在队列中的位置。 Q.rear Q.front J1 J2 J3 队列的顺序存贮结构图示 　 由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。 每当插入新的队列尾元素时，“尾指针加1”; 初始化建空队列时，令front=rear=0。 每当删除队列头元素时，“头指针加1”。 j1 Q.rear Q.front j2 Q.rear Q.rear j3 Q.rear j4 Q.rear Q.front 4 3 2 1 0 j5 Q.rear 从图示中可看出，当J5 入队后, 队尾指针Q.rear越界，不可能再插入新的队尾元素，但是另一方面，队列的实际可用空间并未占满。 一个巧妙的办法是，将顺