专升本数据结构试题解析(17)

第2部分 习题解析 亱店↘打烊oO

push(s2,x);

}

while(!stackempty(s2)) /*如果栈不空，将s2栈中的内容移到s栈中*/

{pop(s2,x);

push(s,x);

}

}

6．假设循环队列中只设rear和length来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。

【算法分析】

该题的关键问题是如何确定头指针，根据为指针rear和元素个数length很容易确定头指针。front=(rear-length+MAXSIZE)%MAXSIZE

【算法源代码】

#define MAXQSIZE 100 //最大队列长度

typedef int ElemType;

typedef struct {

ElemType data[MAXSIZE]; //队列存储空间

int rear; //尾指针，若队列不空，指向队列尾元素

int length; //队列内含元素的个数

}CyQueue;

int FullQueue( CyQueue *Q)

{/*判队满,队中元素个数等于空间大小*/

return Q->length==Maxsize;

}

void EnQueue( CyQueue *Q, ElemType x)

{/* 入队

if(FullQueue( Q)) {printf("队已满，无法入队");return;} */

Q->Data[Q->rear]=x;

Q->rear=(Q->rear+1)%MAXSIZE /*在循环意义上的加1*/

Q->length++;

}

ElemType DeQueue( CyQueue *Q)

{/*出队*/

int front; /*设一个临时队头指针*/

if(Q->length==0)

Error("队已空，无元素可出队");

front=(Q->rear + MAXSIZE - Q->length)%MAXSIZE;

Q->length --;

return Q->Data[front];

}

7．一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法， 其中i为0 或1， 用以表示栈号。

【算法分析】

双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。

【算法源代码】

void InitStack( DuStack *S )/*初始化双向栈*/

{S->top[0] = -1;

S->top[1] = STACKSIZE;

}

int EmptyStack( DuStack *S, int i )

/*判栈空(栈号 i) */

{return (i == 0 && S->top[0] == -1|| i == 1 && S->top[1] == STACKSIZE) ;

}