数据结构与实训
上QQ阅读APP看本书，新人免费读10天
设备和账号都新为新人
上一章目录下一章

3.2 栈典型题例

【例3-3】若某堆栈的输入序列为1,2,3,…,n-1,n，输出序列的第1个元素为n，问第i个输出元素是什么?

【分析与解答】堆栈的输入序列为1,2,3,…,n-1,n，堆栈的特性是后进先出，输出序列的第1个元素为n，那么第2个元素为n-1，第3个元素为n-2，依次类推，第i个输出元素是n-i+1。

【例3-4】简述以下算法的功能。

void Reverse (SeqStack s)

{

n=0;

while (!StackEmpty (s))

{
a[n]=Pop(s);
n++;
}
for(i=0;i<n;i++)
Push(s,a[i]);
} /*Reverse*/
void Remove (LinkStack s,ElementType e)
{
while (!StackEmpty (s))
{
d=Pop(s);
if (d!=e) Push(t,d);
}
while (!StackEmpty (t))
     {
        d=Pop(t);
        Push(s,d);
     }
} /* Remove */

【分析与解答】算法Reverse中，堆栈s的元素从栈底到栈顶的序列设为e1,e2,…,en，while循环将s的元素出栈，存入a数组，a数组中各元素的值如表3-1所示，for循环将a数组元素依a[0],a[1],…,a[n-1]（即en,en-1,…,e1）的顺序入s栈，从栈底到栈顶的序列为en,en-1,…,e1。因此，该算法借助数组a实现了堆栈s的逆置。

表3-1 数组a中元素的值

算法Remove中，第1个while循环将s的元素（除元素e）出栈进入t栈，t栈是s栈不包括e元素的逆置；第2个while循环则将t的元素出栈后又进入s栈，s栈是t栈的逆置，最终s经过两次逆置又恢复成原来的元素序列（不包括元素e），因此该算法借助堆栈t将堆栈s中的数据元素e删除。

【例3-5】图3-5所示是一组n条带头结点的链表表示的堆栈（n个链栈），top[0],top[1],…, top[n-1]分别是各堆栈栈顶指针，试给出该组堆栈的数据类型定义，并写一算法对这组堆栈初始化。

【分析与解答】数据类型（链表中结点类型StackNode与链指针类型LinkStack）定义如下。

#define MaxSize 栈顶指针数组的最大长度
typedef struct snode
    { ElementType data;
      struct snode *next;
    }StackNode;
typedef StackNode *LinkStack;
    / * LinkStack为指向StackNode的指针类型* /

图3-5 一组n条带头结点的链表示的堆栈

构成n个栈顶指针的数组数据类型定义如下。

LinkStack top[MaxSize];

堆栈组初始化算法如下。

void StackInit(LinkStack top[],int n)
{
    for (i=0;i<n;i++)
    {
        p=(LinkStack)malloc(sizeof(StackNode));/*生成堆栈头结点*/
        p->next=NULL;/*堆栈头结点指针为空*/
        top[i]=p;/*各数组元素为指向头结点的头指针*/
    }
}/* StackInit */

【例3-6】写一算法，将十进制数转换为十进制以下进制的数。

【分析与解答】将十进制数转换成其他进制数有一种简单的方法，即利用公式：

N=(N div d)*d+N mod d

其中div为整除运算，mod为求余运算，N是十进制数，d表示要转换到的目标进制（其他进制）。公式中十进制数N转换为d进制数的过程就是，N除以d取其余数，最先得到的余数就是最低位，依次到最高位。

例如，将十进制数67转换为二进制数，其转换过程如下。

67 div 2=33余数为1

33 div 2=16余数为1

16 div 2=8余数为0

8 div 2=4余数为0

4 div 2=2余数为0

2 div 2=1余数为0

1 div 2=0余数为1

结果为余数的逆序1000011，即(67)10=(1000011)2。

算法描述如下。

int Conversion(int n,int d)
/*将十进制数n转换为d进制（十进制以下进制）数*/
{
    SeqStack s;
    result=0;
    s.top=-1;
    while (n)
    {
       Push(s,n%d); /*余数入栈*/
       n=n/d;
    }
    while (!StackEmpty (s))
       result=result*10+Pop(s);
    return(result);
} /*conversion */

【例3-7】一个简单的行编辑程序的功能是接收用户的终端输入，并允许用户对输入的错误及时修改。约定“#”为退格符，表示前一个输入的字符无效，“@”为退行符，表示当前行的输入无效。若用户的终端输入为while##le (s1#!=0)，则对应的有效输入为while(s!=0)。写一模拟行编辑程序的算法。

【分析与解答】可借用两个堆栈s、t来模拟行编辑程序的工作过程。

（1）堆栈s用来接收用户输入的普通字符，如果输入的是特殊字符“#”或“@”，则对s栈做一次出栈或清空操作。

（2）当一行字符输入结束后，将s栈中的字符依次出栈并压入t栈，t栈中存放有s栈字符的逆序列。

（3）将t栈中的字符依次出栈存放在数组str中，数组str中存放有t栈字符的逆序列，即s栈字符的正序列，并且每行字符都存入str。

（4）当输入结束时，输出字符数组str的值，也就输出了用户输入、编辑后的有效字符。

void LineEdit()
/*行编辑程序模拟算法*/
{  s=StackInit ();
   t=StackInit ();
   strlen=0；
   ch=getchar();
   while(ch!=EOF) /*EOF表示输入结束符*/
      {  while(ch!=EOF && ch!='\n') /*接收一行字符*/
        {  switch(ch)
        {  case '#' : ch=Pop(s);break;
           case '@' : StackClear (s);break;/*将s栈置空*/
           default : Push(s,ch);break;  /*输入字符存入s栈*/
         }
         ch=getchar();
      }
      if (ch=='\n') Push(s,ch);/*换行符进栈*/
      while(!StackEmpty(s))
      {  x=Pop(s);
         Push(t,x);/* t栈存放s栈中字符序列的逆序*/
      }
      while(!Empty(t))
      {  x=Pop(t);
         str[strlen++]=x;
      }
      if (ch!=EOF) ch=getchar();
     }
     str[strlen]='\0';
     printf(str);
} /* LineEdit */
上一章目录下一章