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

时间: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) ;

}

专升本数据结构试题解析(17).doc 将本文的Word文档下载到电脑

精彩图片

热门精选

大家正在看

× 游客快捷下载通道(下载后可以自由复制和排版)

限时特价:7 元/份 原价:20元

支付方式:

开通VIP包月会员 特价:29元/月

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信:fanwen365 QQ:370150219