数据结构C++描述).ppt

(2) 进队列 Void enqueue (seqqueue q, elemtype x) { if ((q.rear+1)%maxsize = = q.front) cout”overflow”; else { q.rear=(q.rear+1)%maxsize; q.queue[q.rear]=x; } } (3) 出队列 Void dlqueue(seqqueue q ) { if (q.rear= =q.front) cout”underflow”; else q.front =(q.front+1)%maxsize; } (4) 取队头元素（注意得到的应为头指针后面一个位置值） elemtype gethead(seqqueue q ) { if (q.rear= =q.front) { cout”underflow”；return NULL;} else return q.queue[(q.front+1)%maxsize]; } (5) 判队列空否 int empty(seqqueue q ) { if (q.rear= =q.front) reurn 1; else return 0; } 3.2.5 链队列 1 。链队列的数据类型描述 队列的链式存储，称为链队列，与前面介绍的单链表类似，但为了使头指针，尾指针统一起来，另外定义一种数据类型如下。 Struct link //定义单链表数据类型 { elemtype data; link *next;}; ?struct linkqueue //定义链队列数据类型 { link *front,*rear; //定义头指针和尾指针 }; 2 。链队列上的基本运算 同样，链队列上也可以给出五种运算如下： （1）链队列上的初始化 void INIQUEUE(linkqueue( s) { link *p; p=new link; p-next=NULL; s.front=p; s.rear=p; } (2) 入队列 void push(linkqueue s, elemtype x) { link *p; 　 p=new link; p-data=x; p-next=s.rear-next; s.rear-next=p; s.rear=p; } (3) 判队空 int empty(linkqueue s) { if (s.front= =s.rear) return 1; else return 0; } ?(4) 取队头元素 elemtype gethead(linkqueue s) { if (s.front= =s.rear) return NULL; else retuen s.front-next-data; } (5) 出队列 void pop(linkqueue s) { link *p; p=s.front-next; if (p-next= =NULL)　　//链队列中只有一个队头元素,无其它元素 {s.front-next=NULL; s.rear=s.front;} else s.front-next =p-next; delete (p);} 从上述出队列算法中可知，若链队列中只有一个元素时，需作特殊处理(用if语句判断)，修改队尾指针。为了避免修改队尾指针，我们可以采用一种改进的出队列算法。其基本思想是：出队列时，修改头指针，删除头结点而非队头结点，这时，将队头结点成为新的头结点，队列中第二个结点成为队头结点。这时，不管队列中有多少个元素，都不需作特殊处理（不需用if语句来判断），这种改进的算法如下： void pop(linkqueue s) { link *p; p=s.front; s.front=p-next; delete (p);} 3.2.6 队列的应用 队列在日常生活中和计算机程序设计中，有着非常重要的作用，在此，仅举出两个方面例子来说明它，其它应用在后面章节中将会遇到。 第一个例子就是