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

时间:2025-07-11

数据结构上机实验与习题解析 亱店↘打烊oO

int FullStack( DuStack *S)

/*判栈满,满时肯定两头相遇*/

{return (S->top[0] == S-top1-1);

}

void Push(DuStack *S, int i, ElemType x)

/*进栈(栈号i) */

{if (FullStack( S ))

Error("Stack overflow");/*上溢、退出运行*/

if ( i == 0) S->Data[ ++ S->top0]= x; /*栈0入栈*/

if ( i == 1) S->Data[ -- S->top[1] ]= x; /* 栈1入栈*/

}

ElemType Pop(DuStack *S, int i)

/*出栈(栈号i) */

{if (EmptyStack ( S,i) )

Error("Stack underflow");/*下溢退出*/

if( i==0 )

return ( S->Data[ S->top0--] );/*返回栈顶元素,指针值减1*/

if( i==1 )

return ( S->Data[ S->top[1] ++] ); /*该栈是以另一端为底的,所以指针加1*/

}

8.回文是指正读反读均相同的字符序列,如"abba"和"abdba"均是回文,但"good"不是回文。设计一个算法判定给定的字符向量是否为回文。(提示:将一半字符入栈)

【算法源代码】

void sympthy(LinkList head, stack *s)/*判断长为n的字符串是否中心对称*/

{ int i=1;

LinkList p=head->next;

while(i<=n/2) /* 前一半字符进栈*/

{ push(s,p->data); p=p->next; }

if(n%2!==0) p=p->next;/* 奇数个结点时跳过中心结点*/

while(p&&p->data==pop(s)) p=p->next;

if (p==NULL)

printf("链表中心对称");

else printf("链表不是中心对称");

} /* 算法结束*/

9.用标志位方式设计出在循环队列中进行插入和删除运算的算法。

【算法分析】

可引入标志位flag,且规定当flag=0时表示队列空,当flag=1时表示队列非空。同时设front,rear和MAXSIZE分别为队头指针,队尾指针和队列的长度。其中,队头指针指向队头元素所在的实际存储单元的前一个位置,队尾指针指向队尾元素所在的位置。从而可得队满的条件是:(rear==front)&&(flag==1)

【算法源代码】

int flag; /*设置全局变量flag作为标志位*/

enqueue(SqQueue*sq,ElemType x) {

/*将x插入循环队列sq中,sq具有队头和队尾指针*/

if((flag==1)&&(sq->rear==sq->front)) /*判断队满*/

printf("queue is full!\n");

else

{sq->rear=(sq->rear+1)%MAXSIZE;

sq->data[sq->rear]=x;

}

if(flag==0) flag=1;

}

ElemType dequeue(SqQueue*sq) /*删除队列sq的队头元素,并返回该元素*/

{ElemType x;

if(flag==0) printf("queue is empty!\n"); /*判断队空*/

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

精彩图片

热门精选

大家正在看

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

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

支付方式:

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

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