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

第2部分 习题解析 亱店↘打烊oO

rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。

5. 若以1、2、3、4作为双端队列的输入序列，试分别求出以下条件的输出序列：

（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；

（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；

（3）既不能由输入受限双端队列得到，也不能由输出受限双端队列得到的输出序列。

【答案】（1）4132 （2）4213 （3）4231

3.5 程序设计题

1．设表达式以字符形式已存入数组E[n]中， # 为表达式的结束符，试写出判断表达式中括号（ （ 和 ） ）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。)

【算法分析】判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。

【算法源代码】

int EXYX (char E[]){

/*E[]存放字符串表达式，以‘#’结束*/

char s[30]; /*s是一维数组，容量足够大，用作存放括号的栈*/

int top=0,i; /*top用作栈顶指针*/

s[top]='#'; /*‘#’先入栈，用于和表达式结束符号‘#’匹配*/

i=0; /*字符数组E的工作指针*/

while(E[i]!='#') /*逐字符处理字符表达式的数组*/

switch (E[i])

{case '(': s[++top]= '('; i++ ; break ;

case ')': if(s[top]=='('){top--; i++; break;}

else{printf("括号不配对");exit(0);}

case '#': if(s[top]=='#'){printf("括号配对\n");return (1);}

else {printf(" 括号不配对\n");return (0);} /*括号不配对*/

default : i++; /*读入其它字符，不作处理*/

}

}/*算法结束*/

2．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列和出队列算法。

【算法分析】

根据队列的先进先出的性质，队列的入队操作在队尾进行，出队操作在队头进行。而题目所采用的数据结构是只设一个尾指针的循环链表。我们可以根据循环链表的特点找到头指针。

【算法源代码1】

void EnQueue (LinkList rear, ElemType x)

/* rear是带头结点的循环链队列的尾指针，本算法将元素x插入到队尾*/

{ s=(LinkList)malloc(sizeof(LNode)); /*申请结点空间*/

s->data=x; s->next=rear->next; /*将s结点链入队尾*/

rear->next=s; rear=s; /*rear指向新队尾*/

}

【算法源代码2】

void DeQueue (LinkList rear)

/* rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元

素；否则给出出错信息*/

{ if(rear->next==rear) {printf("队空\n"); exit(0);}

s=rear->next->next; /*s指向队头元素*/

rear->next->next=s->next; /*队头元素出队*/

printf ("出队元素是:%d",s->data);

if(s==rear) rear=rear->next; /*空队列*/