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

【心得】

學生可以根據程序在計算機上調試運行，并結合自己在上機過程中遇到的問題和解決方法的體會，寫出調試分析過程、程序使用方法和測試結果，提交實訓報告。