专升本数据结构试题解析(17)
时间:2025-07-11
时间:2025-07-11
第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) ;
}