第三单元：

第三章部分习题答案

3.2试证明：若借助栈由输入序列12…n得到输出序列为p₁p₂…p_n(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i<j<k使p_j<p_k<p_i。

证明：如果有j<k且p_j<p_k，则必须在p_k进栈之前将p_j退栈；如果j<k且p_j>p_k，则必须把p_j留在栈中，直到p_k进栈之后。将这两条规则结合起来，条件i<j<k和p_j<p_k<p_i是不可能的，因为这意味着p_j必须在p_k之前和p_i之后退栈，而p_i又出现在p_k之后。

 

3.3设单链表中存放着n个字符，试编写算法，判断该字符串是否有中心对称关系，例如xyzzyx、xyzyx都算是中心对称的字符串。要求用尽可能少的时间完成判断。（提示：将一半字符先依次进栈。）

Comp(linklist *head,int n)

{linklist *p;

Seqstack *s;

Int i;

P=head;

s->top=-1;

for(i=0;i<n/2;i++)

{p=p->next;

 s->top++;

 s->data[s->top]=p->data;

}

If(n%2==0)  p=p->next;

Else  p=p->next->next;

While((p!=null)&&(s->data[s->top]==p->data))

{p=p->next;

 s->top--;

}

If(p!=null||s->top!=-1)

Printf(＂The %d chars are not balanced by central!\n＂,n);

Else  Printf(＂The %d chars are balanced by central!\n＂,n);

}

3.4设计算法判断一个算术表达式的圆括号是否正确配对。（提示：对表达式进行扫描，凡遇到‘（’就进栈，遇到‘）’就退掉栈顶的‘）’，表达式被扫描完毕，栈应为空。）

Int comp(seqstack *s)

{char ch;

 s->top=-1;

 ch=getchar();

 while(ch!=‘#’)

 {if(ch==‘(’)

   {s->top++;

s->data[s->top]=ch;

   }

If(ch==‘)’)

 If(s->top<0)

  {printf(＂\n underflow!＂);

   Return 0;

  }

 Else s->top--;

Ch=getchar();

}

If(s->top==-1)   return 1;

Else return 0;

}

3.5两个栈共享向量空间v[m]，它们的栈底分别设在向量的两端，每个元素占一个分量，试写出两个栈公用的栈操作算法：push(i,x)，pop(i)和top(i)，其中i为0或1，用以指示栈号。

Typedef struct

            {datatype V[maxsize];

             Int LeftTop, RightTop;

            }Dseqstack;

Dseqstack *s;

(1)初始化

Void  setnull(Dseqstack *s)

{s->LeftTop=-1;

 s->RightTop=maxsize;

}

(2)进栈运算

Int  push(Dseqstack *s,int i,datatype x)

{if((s->LeftTop)>=(s->RightTop)-1)

 {printf(＂\n overflow!＂);   return 0;}

 If(i!=0&&i!=1)

  { printf(＂\n error!＂);   return 0;}

 If(i==0)

  {s->LeftTop++;   s->V[s->LeftTop]=x;}

 Else

{s->RightTop--;  s->V[s->RightTop]=x;}

Return 1;

}

(3)退栈

Datatype pop(Dseqstack *s, int i)

{if(i!=0&&i!=1)

 { printf(＂\n error!＂);   return 0;}

 If(i==0)

  {if(s->LeftTop<0)

{printf(＂\n left stack underflow!＂);    return  null;}

   Else

     {s->LeftTop--;  return(s->V[s->LeftTop+1]);}

   }

 Else

  {if(s->RightTop>=maxsize)

{printf(＂\n right stack underflow!＂);    return  null;}

   Else

     {s->RightTop++;  return(s->V[s->RightTop-1]);}

   }

}

(4)取栈顶

Datatype top(Dseqstack *s, int i)

{if(i!=0&&i!=1)

 {printf(＂\n error!＂);  return 0;}

 If(i==0)

 {if(s->LeftTop<0)

{printf(＂\n left stack is empty!＂);    return  null;}

  Else  return(s->V[s->LeftTop]);

  }

  Else

{if(s->RightTop>=maxsize)

   {printf(＂\n right stack is empty!＂);    return  null;}

 Else  return(s->V[s->RightTop];

}

}

3.7假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的置空对、入队和出队的算法。

Typedef struct linknode

 {int data;

  Struct linknode *next;

 }circlelinkqueue;

Setnull(circlelinkqueue *rear)

{rear=malloc(sizeof(circlelinkqueue));

 Rear->next=rear;

}

Enqueue(circlelinkqueue *rear,datatype x)

{ circlelinkqueue *s;

 S=malloc(sizeof(circlelinkqueue));

 s->data=x;

 s->next=rear->next;

 rear->next=s;

 rear=s;

}

Void dequeue(circlelinkqueue *rear)

{ circlelinkqueue *p;

if(rear==rear->next)    printf(＂\n link queue is empty!＂);

 Else

  {p=rear->next;

   Rear->next=p->next;

   Free(p);

  }

}

3.8对于循环向量中循环队列，写出求队列长度的公式。

Int cirqueuelengh(sequeue *sq)

{if(sq->rear==sq->front)  return 0;

Else return(((sq->rear)-(sq->front)+maxsize)%maxsize);

}