二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(11)

不能入队列。 8Q.front Q.rear Q.front Q.rear 8

9 不准确的说法，只为便于理解和记忆，不要在正式场合引用。 不准确的说法，只为便于理解和记忆，不要在正式场合引用。

q) 队列不空也不满

tag:0

tag:1

r) 加一标志区分队列空和队列满的情况

可以用满所有空间。队列空和队列满时都有Q.front==Q.rear，再用标志区分。

队列空：Q.front==Q.rear and Q.tag==0；队列满：Q.front==Q.rear and Q.tag==1。 基本算法

s) 入队列

前提：队列不满。

bool EnQueue ( SqQueue &Q, DataType x )

{

if ( (Q.rear+1)%MAXSIZE==Q.front ) return false; // 队列满

// 入队列

Q.elem [Q.rear] = x;

Q.rear = (Q.rear+1)%MAXSIZE;

return true;

}

t) 出队列

前提：队列非空。

bool DeQueue ( SqQueue &Q, DataType &x )

{

if ( Q.front==Q.rear ) return false; // 队列空

// 出队列

x = Q.elem [Q.front];

Q.front = (Q.front+1)%MAXSIZE;

return true;

}

u) 队列中元素个数

结论：(Q.rear-Q.front+MAXSIZE)%MAXSIZE。

注：Q.rear-Q.front可能小于0，需要加上MAXSIZE。

int QueueLength ( SqQueue Q )

{

return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;

}

v) 用标志区分队列空和满

用标志区分队列空和满时，队列初始化、入队列、出队列和队列长度的算法如下： void InitQueue ( SqQueue &Q ) {

Q.front = Q.rear = 0; Q.tag = 0;

}

bool EnQueue ( SqQueue &Q, DataType x ) {

if ( Q.front==Q.rear and Q.tag==1 ) return false;

Q.elem[ Q.rear ] = x;

Q.rear = (Q.rear+1)%MAXSIZE;

if ( Q.tag==0 ) Q.tag = 1; // 队列非空

return true;

}

bool DeQueue ( SqQueue &Q, DataType &x ) {

if ( Q.front==Q.rear and Q.tag==0 ) return false;

x = Q.elem[ Q.front ];

Q.front = (Q.front+1)%MAXSIZE;

if ( Q.front==Q.rear ) Q.tag = 0; // 队列空

return true;

}

int QueueLength ( SqQueue Q )

{

if ( Q.front==Q.rear and Q.tag==1 )

return MAXSIZE; // 队列满

else

return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; // 队列不满(包含队列空的情况) }

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-11.html