专升本数据结构试题解析(18)
时间:2025-07-10
时间:2025-07-10
数据结构上机实验与习题解析 亱店↘打烊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"); /*判断队空*/