3.6 实训例题

3.6.1 实训例题1：顺序循环队列的操作

【问题描述】

对顺序循环队列，将自然数按序入队、出队。具体的操作是：队列未满时，入队、入队、出队，输出出队元素的值；队列满时，执行连续的出队操作，输出出队元素的值（应与队列未满时所输出的有不同标识），直至队列为空。编写算法实现以上操作。

【基本要求】

队列采用顺序存储结构，涉及的操作有队列的初始化，判断队列是否为空，入队和出队。

• 功能：

（1）初始化队列；

（2）判断队列是否为空；

（3）入队；

（4）出队。

• 输入：自动生成入队值（自然数）。

• 输出：出队值与入队值相同。

【测试数据】

若MaxSize定义为20，则预期的输出结果是：

1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19#20#21#22#23#24#25#26#27#28#29#30#31#32#33#34#35#36#37#

队列未满时，出队的值后跟一个星号（*），具体是从1到18（队列中的值从19到37共19个元素）；队列满后，执行连续出队，出队的值后跟一个井号（#），从19到37。

【数据结构】

顺序循环队列的定义如下。

#define MaxSize 20
typedef struct
{ int elem[MaxSize];
  int front,rear;
} CirQueue;

【算法思想】初始化队列，当队列未满时，自然数按序入队、入队、出队，并输出出队元素的值，后跟一个星号；当队列满时，出队，并输出出队元素的值，后跟一个井号，直到队空。

【模块划分】

① 初始化队列InitQueue。

② 判断队列是否为空QueueEmpty。

③ 入队AddQueue。

④ 出队DeleteQueue。

⑤ 主函数main。

【源程序】

#include <stdio.h>
#define MaxSize 20
typedef struct
{ int elem[MaxSize];
  int front,rear;
} CirQueue;
CirQueue InitQueue() /*队列初始化*/
{
   CirQueue q;
   q.front=q.rear=0;
   return(q);
}/* InitQueue */
int QueueEmpty(CirQueue q) /*判断队列是否为空*/
{
     return(q.front==q.rear);
}/* QueueEmpty */
void AddQueue(CirQueue *q,int e) /*入队列*/
{
     if (q->front==(q->rear+1) % MaxSize) /*队满*/
         printf("\nFull");
     else
     {
         q->rear=(q->rear+1) % MaxSize;
         q->elem[q->rear]=e ;
     }
} /* AddQueue */
int DeleteQueue(CirQueue *q) /*出队列*/
{
     int e;
     if (QueueEmpty(*q))
          return(0);/*返回空值*/
     else
     {
         e=q->elem[(q->front+1) % MaxSize];
         q->front=(q->front+1) % MaxSize;
         return (e);
     }
}/* DeleteQueue */
main()
{
     CirQueue *q;
     int e,i=1;
     q=(CirQueue *)malloc(sizeof(CirQueue));
     *q=InitQueue();
     printf("\n");
     while (q->front !=(q->rear+1) % MaxSize) /*队列未满时*/
     {
         AddQueue(q,i);
         i++;
         if (q->front !=(q->rear+1) % MaxSize)
         {
               AddQueue(q,i);
               i++;
               e=DeleteQueue(q);
               printf("%d*",e);
         }
     }
     while (!QueueEmpty(*q)) /*队列不空时*/
     {
         e=DeleteQueue(q);
         printf("%d#",e);
     }
}/*main*/

【测试情况】

运行程序得到的实际输出如下。

1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19#20#21#22#23#24#25#26#27#28#29#30#31#32#33#34#35#36#37#

【心得】

学生可以根据程序在计算机上调试运行，并结合自己在上机过程中遇到的问题和解决方法的体会，写出调试分析过程、程序使用方法和测试结果，提交实训报告。

3.6.2 实训例题2：括号配对

【问题描述】

输入任一表达式，“#”为表达式的结束符，试写一判断表达式中圆括号（“(”与“)”）是否配对的算法。

【基本要求】

• 功能：将表达式串存入字符数组，借助堆栈，判断字符数组中圆括号是否配对。

• 输入：表达式字符串。

• 输出：判断结果（Matched或Unmatched）。

【测试数据】

输入(a+((a+b)*c)-d/c)*e#，预期的输出是Matched。

输入(a+((a+b)*c)-d/c))*e#，预期的输出是Unmatched。

输入((a+((a+b)*c)-d/c)*e#，预期的输出是Unmatched。

【数据结构】

所有链栈LinkStack类型定义如下。

typedef struct snode
{ char data;
  struct snode *next;
}StackNode;
typedef StackNode *LinkStack;

【算法思想】

输入表达式字符串，将其存入字符数组中，借助堆栈判断字符数组中的括号是否匹配。

• 逐一处理字符数组中的字符；

• 对除“(”、“)”之外的其他字符不作处理；

• 遇左括号，左括号进栈；

• 遇右括号，则出栈，并判断出栈字符是否为左括号；

• 不是，说明括号不配对；

• 是，继续处理剩余的字符，直到表达式结束（遇“#”字符），此时若栈为空则括号配对，否则括号不配对。

【模块划分】

① 接收输入字符串EnterStr。

② 判断字符串中括号是否配对Judge。

③ 主函数main，循环调用函数EnterStr和函数Judge，当用户要求继续判断时则继续循环执行，否则结束。

【源程序】

#include "string.h"
#include "stdio.h"
typedef struct snode
{ char data;
  struct snode *next;
}StackNode;
typedef StackNode *LinkStack;
LinkStack StackInit() /*初始化堆栈*/
{
    LinkStack s;
    s=(LinkStack)malloc(sizeof(StackNode));
    s->next=0;
    return (s);
}/* StackInit */
int StackEmpty(LinkStack s) /*判断栈s是否为空*/
{
     if (s->next)
          return (0);
     else
          return(1);
}/* StackEmpty */
void Push(LinkStack s,char e) /*进栈*/
{
     LinkStack p;
     p=( StackNode *)malloc(sizeof(StackNode));/*生成新结点，并由p指向它*/
     p->data=e;
     p->next=s->next;
     s->next=p;
} /* Push*/
char Pop(LinkStack s) /*出栈*/
{
     char e;
     LinkStack p;
     if (StackEmpty(s))  /*栈空*/
         return('\0');  /* 返回空值*/
     else
     {
        p=s->next;
        s->next=p->next;
        e=p->data;
        free(p);
        return(e);
     }
} /* Pop*/
void EnterStr(char str[])
{
     printf("Input the expression string ended with '#' (length≤80):\n");
     scanf("%s",str);
}/*EnterStr*/
int Judge(char st[])
{
     int i;
     LinkStack s;
     s=StackInit();
     i=0;      /*字符数组st的工作指针*/
     while(st[i]!='#')  /*逐字符处理字符表达式的数组*/
        switch(st[i])
        {
            case '(' : {Push(s,'(');i++;break ;}
            case ')' : if (Pop(s)=='(')
                              { i++;break;}
                       else
                               return (0);
            default : i++; /*其他字符不作处理*/
        }
   if (StackEmpty(s))
        return (1);
   else
        return (0);
} /*Judge*/
main()
{
     char ch,str[80];
     int flag=1;
     while (flag)
     {
        EnterStr(str);
        if (Judge(str))
             printf("Matched\n ");
        else
             printf("Unmatched\n ");
        printf("\nDo you want to continue?(y/n):\n");
        scanf("%c",&ch);scanf("%c",&ch);
if (ch==′n′||ch==′N′) flag=0;
}
}/*main*/

【测试情况】

Input the expression string ended with '#' (length≤80):
(a+((a+b)*c)-d/c)*e#
Matched




Do you want to continue?(y/n):
y
Input the expression string ended with '#' (length≤80):
(a+((a+b)*c)-d/c))*e#
Unmatched




Do you want to continue?(y/n):
y
Input the expression string ended with '#' (length≤80):
((a+((a+b)*c)-d/c)*e#
Unmatched
Do you want to continue?(y/n):
n

【心得】

学生可以根据程序在计算机上调试运行，并结合自己在上机过程中遇到的问题和解决方法的体会，写出调试分析过程、程序使用方法和测试结果，提交实训报告。