专升本数据结构试题解析(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;

}