数据结构实践教程-栈、队列

博主：酱油瓶
发布时间：2021 年 10 月 26 日
2925 次浏览
暂无评论
814字数
分类：学习软件工程

本文为本人按照书本要求所写作业，算法并非最优，仅供参考
</div>

书为：《数据结构实践教程》清华大学出版社 主编：徐慧
</div>

# 试验3.1 表达式括号匹配配对判断问题

姓名：郁闷的酱油瓶

班级：软嵌

学号：114514

实验时间：2021.10.24

## 1.问题描述

假设一个算法表达式中包括圆括号、方括号两种，设计判别表达式中括号是否正确匹配的算法。

## 2.数据结构设计

### (1)结构设计

从节省空间的角度看，栈采用顺序表，栈元素类型为字符型

```c++
template<class T>
    class SqStack
    {
        private:
        T* base;		//栈底指针
        int top;		//栈顶
        int stacksize;		//栈容量
        public:
        SqStack(int m);		//构造函数
        void Push(T x);		//入栈
        T Pop();		//出栈
        T GetTop();		//获取栈顶元素
        int StackEmpty();	//测栈空
    };
```

### (2)函数设计

本实验需要用到以下函数

```c++
//构造函数
template<class T>
    SqStack<T>::SqStack(int m)
    {
        base = new T[m];
        if (base == NULL)
        {
            cout << "栈创建失败，退出!" << endl;
            exit(1);
        }
        stacksize = m;
        top = -1;
    }
//入栈
template<class T>
    void SqStack<T>::Push(T x)
    {
        if (top == stacksize - 1)
            throw "栈满，无法入栈";
        top++;
        base[top] = x;
    }
//出栈
template<class T>
    T SqStack<T>::Pop()
    {
        T x;
        if (top == -1)throw"栈空，不能出栈";
        x = base[top--];
        return x;
    }
//获取栈顶元素
template<class T>
    T SqStack<T>::GetTop()
    {
        if (top == -1) throw "空栈，栈顶无元素";
        return base[top];
    }
//测表空
template<class T>
    int SqStack<T>::StackEmpty()
    {
        if (top == -1)
            return 0;
        else
            return 1;
    }
```

## 3.算法设计

### step 1

创建一个栈,并从键盘输入表达式

```c++
SqStack<char>s(20);
string str;
cout << "请输入公式:";
cin >> str;
```

### step 2

从左到右扫描表达式，知道表达式结束

```c++
for (int i = 0; i < str.length(); i++) {}
```

#### 2.1

如果是左括号，入栈；取下一个字符

```c++
if (str[i] == '{' || str[i] == '(' || str[i] == '[') {s.Push(str[i]);}
```

#### 2.2

如果是右括号

```c++
if (str[i] == '}' || str[i] == ')' || str[i] == ']') {}
```

##### 2.2.1

与栈顶括号不匹配，则出栈，消去一个左括号；取下一个字符

```c++
else if ((str[i] == '}' && s.GetTop() == '{')
         || (str[i] == ']' && s.GetTop() == '[')
         || (str[i] == ')' && s.GetTop() == '('))
{
    s.Pop();
}
```

##### 2.2.2

与栈顶括号不匹配，得到"不匹配"结论，结束

```C++
else if(!((str[i] == '}' && s.GetTop() == '{')
	|| (str[i] == ']' && s.GetTop() == '[')
	|| (str[i] == ')' && s.GetTop() == '(')))
{
    cout <<"不匹配:" << s.GetTop() << "与" << str[i] << "匹配错" << endl;
    return 0;
}
```

##### 2.2.3

栈空，得到“不匹配”结论，结束

```c++
if(!s.StackEmpty())
{
    cout << "不匹配:"<<"多右括号"<<str[i] << endl;
    return 0;
}
```

### step 3

若栈空，则表达式中括号匹配；否则，不匹配。

```c++
if (!s.StackEmpty())
    cout << "匹配" << endl;
else
    cout << "不匹配:"<<"多左括号"<<s.GetTop() << endl;
```

## 4.测试与运行

### (1)测试1

1. 运行程序

![运行](https://snz04pap001files.storage.live.com/y4m4FHUPjXApvLId1W4wCSvoO0L37IZAh-d1dGmPapagtRGLnj7Llekh_g1T0ps-kT4_CIbbxx_XO5SEDrP-vpQyOKiGr3cAgeAe3n5j41BLPt1_MhgHmHRpyRjmYzM0dNeFXsguGRmZcPYdnHTnhk7bklvlDxFcgfuMfpzd5EE-Esvr4QTEb_CQQbK05DOQrLH?width=1470&height=766&cropmode=none)
2. 输入表达式

![输入](https://snz04pap001files.storage.live.com/y4mrxsF_qF8wBkQqbtGogVr2K3-jdBXeCiQ0TCwDveSZdp4mF6nT1sIDmbP4iFbB--PeN11YOjNJ2Rpd3LfBeZRSS0ql6hIfoPfVdugmHm1-H_gRh1ycNa-yVlcEmBAvc4tP2mEQ__MWKQlKx3omauxuw-9Ecdrp3H_Yf1ykzWAr6hzYt3k2WQkc_Nak6d-2duz?width=1470&height=766&cropmode=none)
3. 输出

![输出](https://snz04pap001files.storage.live.com/y4mVMDHXcXNda5J0DTFWgyBjtUxQXKR-9KguzYaeQHZIVbVFko8Rd7b7UtErrS0vvb6Xsj5P1s3xLgjnz6Ol6DEjOix1YJMtumkHo9FXzSn4VzTOqX3l-lmsFttGE3LyuiYiDH6kunameLhQBJHp3fuCkPNETIxZtUOEVdVZcEDf5yzf62n-H3JcsWlqVH7aid4?width=1470&height=768&cropmode=none)

### (2)测试2

![2](https://snz04pap001files.storage.live.com/y4mknEtDpd8dUluWY4zCKpK0uJ5ycWdMFittdw_fs2p0HZk7EKHDEHT758jQWVa7sIJD8H0T_chNIz_RMH5stVDnW8RFByQJXdTr6ddeXdF7qssTRNV7leR8ZFT4iZ4lvmSLMi-aU_XE2U86QIEosAVJjDmcnOEYKXV0R6RdDNFIVl571Dm7Ows8XDv0qxm1rva?width=1470&height=768&cropmode=none)

### (3)测试3

![3](https://snz04pap001files.storage.live.com/y4mfXhecHy3ncUg--NyiJ0rCm3DRi1GeguaSDxDfdtLLGzkJx_M2VRHjaGWkDI3AJnN588JhkbEbEJx7Ikd_RGq2AvC0twz0OSOXMIbSRsUb9qQ2YpCCIFWlmXazZKXNdWCgC7puGTPsB54RlpX6Zmpk7CUOA8TRXWpXVzRUi7NHe6RQxxnbUh8bNQyZKIfbAb9?width=1470&height=768&cropmode=none)

### (4)测试4

![4](https://snz04pap001files.storage.live.com/y4msgBLUisjN89Xkdi6nfpNsaejovJVoXst6U4rn0dVT7r5GioizgqyFFf8S2MGgiEPuPb6QWcNEUIfslAvuVKZ1BCyUE-enJMFIths31McFBwyervqz4BfOJk4c-ali3_uBIlHw4hygdOQEZrwwdb3QnHlKZPNUN6QOotEqiQ-eI7xeCm67YcsZgbq9-ZrHVUB?width=1470&height=766&cropmode=none)

### (5)测试5

![5](https://snz04pap001files.storage.live.com/y4mKUwca6Wltda5dLbadzC8nqdFfHh1QNuKBSRygt2zwAKpe7ODDzqmnFwBZIY_mLCdvKWeK26ncEo36yEeZnTXWqO75KaktkFFLfU64Uug7qiFgSxHhaCauPPD2HASJEVl9pPLlg3upc-va1LguT8sf8GvR1DGt3qPzhrJ3W4PG9Ehvzg6JnIglsw6NANSYtYO?width=1470&height=768&cropmode=none)

## 5.调试记录与收获

1. 源文件清单

- 头文件`SqStack.h`

```c++
     #pragma once
     #include<iostream>
     using namespace std;
     template<class T>
         class SqStack
         {
             private:
             T* base;		//栈底指针
             int top;		//栈顶
             int stacksize;		//栈容量
             public:
             SqStack(int m);		//构造函数
             void Push(T x);		//入栈
             T Pop();		//出栈
             T GetTop();		//获取栈顶元素
             int StackEmpty();	//测栈空
         };

//构造函数
     template<class T>
         SqStack<T>::SqStack(int m)
         {
             base = new T[m];
             if (base == NULL)
             {
                 cout << "栈创建失败，退出!" << endl;
                 exit(1);
             }
             stacksize = m;
             top = -1;
         }
     //入栈
     template<class T>
         void SqStack<T>::Push(T x)
         {
             if (top == stacksize - 1)
                 throw "栈满，无法入栈";
             top++;
             base[top] = x;
         }
     //出栈
     template<class T>
         T SqStack<T>::Pop()
         {
             T x;
             if (top == -1)throw"栈空，不能出栈";
             x = base[top--];
             return x;
         }
     //获取栈顶元素
     template<class T>
         T SqStack<T>::GetTop()
         {
             if (top == -1) throw "空栈，栈顶无元素";
             return base[top];
         }
     //测表空
     template<class T>
         int SqStack<T>::StackEmpty()
         {
             if (top == -1)
                 return 0;
             else
                 return 1;
         }

```
   - 主程序`main.cpp`

```c++
     #include<iostream>
     #include"SqStack.h"
     using namespace std;

int main()
     {
         SqStack<char>s(20);
         string str;
         cout << "请输入公式:";
         cin >> str;
         for (int i = 0; i < str.length(); i++)
         {
             if (str[i] == '{' || str[i] == '(' || str[i] == '[')
             {
                 s.Push(str[i]);
             }
             if (str[i] == '}' || str[i] == ')' || str[i] == ']')
             {
                 if(!s.StackEmpty())
                 {
                     cout << "不匹配:"<<"多右括号"<<str[i] << endl;
                     return 0;
                 }
                 else if ((str[i] == '}' && s.GetTop() == '{')
                          || (str[i] == ']' && s.GetTop() == '[')
                          || (str[i] == ')' && s.GetTop() == '('))
                 {
                     s.Pop();
                 }
                 else if(!((str[i] == '}' && s.GetTop() == '{')
                           || (str[i] == ']' && s.GetTop() == '[')
                           || (str[i] == ')' && s.GetTop() == '(')))
                 {
                     cout <<"不匹配:" << s.GetTop() << "与" << str[i] << "匹配错" << endl;
                     return 0;
                 }
             }
         }
         if (!s.StackEmpty())
             cout << "匹配" << endl;
         else
             cout << "不匹配:"<<"多左括号"<<s.GetTop() << endl;
         return 0;
     }
     ```
2. 收获：

- 在进行栈顶元素的获取操作时(即step2.2)，应先判断栈是否为空，否则会引发内存异常报错

# 试验4.2 单指针链队问题

姓名：郁闷的酱油瓶

班级：软嵌

学号：114514

实验时间：2021.10.25

## 1.问题描述

队列采用链式存储方式，但只允许设置一个指针。在其上实现：初始化、入队、出队、队元素显示、求队长、测队空、清空队等基本操作。

## 2.数据结构设计

### (1)结构设计

根据题目要求，使用带头节点的单指针循环链队

```c++
//结点设计
template<class T>
    struct QNode
    {
        T data;			//数据元素
        QNode<T>* next;		//指针域，指向下一个指针
    };
```

### (2)链表设计

根据要求，实现：初始化、入队、出队、队元素显示、测队空、清空队的操作

```c++
template<class T>
    struct LinkQueue
    {
        private:
        QNode<T>* Head;			//头结点指针
        public:
        LinkQueue();			//初始化
        void EnQueue(T x);		//元素x入队
        T DeQueue();			//队长出队
        T GetHead();			//取队首元素
        T GetLast();			//取队尾元素
        int QueueEmpty();		//测队空
        void ClearQueue();		//清空队
        void QueueTranverse();		//遍历队列
    };
```

## 3.算法设计

### (1)函数实现

- 初始化

```c++
  //构造函数
  template<class T>
      LinkQueue<T>::LinkQueue()
      {
          Head = new QNode<T>;
          Head->next = Head;//创建空的循环单链
      }
  ```
- 元素x入队

```c++
  template<class T>
      void LinkQueue<T>::EnQueue(T x)
      {
          QNode<T>* p = new QNode<T>;	//创建新的结点p
          p->data = x;				//赋值
          p->next = Head->next;
          Head->next = p;
      }
  ```
- 队长出队

```c++
  //队长出队
  template<class T>
      T LinkQueue<T>::DeQueue()
      {
          QNode<T>* p,*q;			//创建指针p,q
          T x;
          p = Head;
          while (p->next->next != Head)	//定位到队尾结点的前驱
          {
              p = p->next;
          }
          if (Head->next != Head)		//判断是否为空队
          {
              q = p->next;
              p->next = q->next;
              x = q->data;
              delete q;
              return x;
          }
          else
          {
              cout<<"队列为空"<<endl;
          }
      }
  ```
- 取队首元素

```c++
  //获取队头元素
  template<class T>
      T LinkQueue<T>::GetHead()
      {
          QNode<T>* p;
          p = Head;
          if (p->next == Head)
          {
              cout << "队列为空,无法删除" << endl;
          }
          else
          {
              while (p->next != Head)		//定位队长
              {
                  p = p->next;
              }
              cout << "队头元素为:";
              return p->data;
          }
      }
  ```
- 取队尾元素

```c++
  //获取队尾元素
  template<class T>
      T LinkQueue<T>::GetLast()
      {
          QNode<T>* p;
          p = Head->next;
          if (p == Head)
          {
              cout << "队列为空,无队尾" << endl;
          }
          else
          {
              cout << "队尾元素为:";
              return Head->next->data;
          }
      }
  ```
- 测队空

```c++
  //测队空
  template<class T>
      int LinkQueue<T>::QueueEmpty()
      {
          if (Head->next == Head)
              return 1;
          else
              return 0;
      }
  ```
- 清空队

```c++
  //清空队
  template<class T>
      void LinkQueue<T>::ClearQueue()
      {
          if (Head->next == Head)
              cout << "表为空，无需清空" << endl;
          else 
          {
              Head->next = Head;
              cout << "队列已清空" << endl;
          }
      }
  ```
- 遍历队列

```c++
  //遍历队列
  template<class T>
      void LinkQueue<T>::QueueTranverse()
      {
          QNode<T>* p;
          p = Head;
          cout << "队元素:" << endl;
          while (p->next != Head)
          {
              p = p->next;
              cout << p->data << '\t';
          }
          cout << endl;
      }
  ```

### (2)测试操作

1. 创建一个空队，并测队空

```c++
   LinkQueue<char>q;
   if (q.QueueEmpty())
       cout << "队空" << endl;
   else
       cout << "队不空" << endl;
   ```
2. A、B、C、D、显示队长和队元素

```c++
   q.EnQueue('A');
   q.EnQueue('B');
   q.EnQueue('C');
   q.EnQueue('D');
   cout << q.GetHead() << endl;
   q.QueueTranverse();
   ```
3. 出队两次，显示队长和队元素

```c++
   q.DeQueue();
   q.DeQueue();
   cout << q.GetHead() << endl;
   q.QueueTranverse();
   ```
4. 执行出队操作3次

```c++
   q.DeQueue();
   q.DeQueue();
   q.DeQueue();
   ```
5. 执行入队操作若干次，显示列队元素，这里从键盘输入字符入队

```c++
   char x;
   int n;
   cout << "输入字符数量：";
   cin >> n;
   cout << "请输入字符(空格空开，回车结束)：" << endl;
   for (int i = 0; i < n; i++)
   {
       cin >> x;
       q.EnQueue(x);
   }
   q.QueueTranverse();
   ```
6. 清空队后，再测队空

```c++
   q.ClearQueue();
   if (q.QueueEmpty())
       cout << "队空" << endl;
   else
       cout << "队不空" << endl;
   ```

## 4.测试运行

### 测试1

基本操作已经分割开，第5项操作输入

输入字符数量：`5`
请输入字符(空格空开，回车结束)：`A B C D E`

![测试1](https://snz04pap001files.storage.live.com/y4mVXm-Pc09W99NF79tPPY6-DnVAOk9isu0pVcVeJIoHk7eglrH_h2tnqgzVpJzNKhtcR6cC4QzLthgwabBVM9qLg4fzQ49vcOVBzFb3ba1vgcnVD9eOvpBJxMhxantvqXMZ_vSU0oaztabANz2i---MYn6m7gNjItfV2ynCbTOUwN24o-8rUhFwd3Z0l7xfSWs?width=1470&height=766&cropmode=none)

### 测试2

输入字符数量：`0`
请输入字符(空格空开，回车结束)：``

![测试2](https://snz04pap001files.storage.live.com/y4mk3qAyiiiVVzoxN0nC21LSnHwwTOD_qAY1r0R0el-DrW5epabZgGAjLpNHoaqNhSNKTBhjhMjDvShfb4lINm0Wq4dAA3E32RLTR43EHNZut3bbRxKgmgzLgTXpSyCU-uWNd_6U3DQ6iNAlSn7lh9uukNZ7DNZfktyA-XVv-oSfHB_B0qnKcBG2pdPZLMPHwyo?width=1470&height=675&cropmode=none)

## 5.调试记录与收获

1. 源文件清单

- 头文件`LinkQueue.h`

```c++
     #pragma once
     #include<iostream>
     using namespace std;

template<class T>
         struct QNode
         {
             T data;				//数据元素
             QNode<T>* next;			//指针域，指向下一个指针
         };

template<class T>
         struct LinkQueue
         {
             private:
             QNode<T>* Head;			//头结点指针
             public:
             LinkQueue();			//初始化
             void EnQueue(T x);		//元素x入队
             T DeQueue();			//队长出队
             T GetHead();			//取队首元素
             T GetLast();			//取队尾元素
             int QueueEmpty();		//测队空
             void ClearQueue();		//清空队
             void QueueTranverse();		//遍历队列
         };
     //构造函数
     template<class T>
         LinkQueue<T>::LinkQueue()
         {
             Head = new QNode<T>;
             Head->next = Head;//创建空的循环单链
         }
     //元素x入队
     template<class T>
         void LinkQueue<T>::EnQueue(T x)
         {
             QNode<T>* p = new QNode<T>;		//创建新的结点p
             p->data = x;				//赋值
             p->next = Head->next;
             Head->next = p;
         }
     //队长出队
     template<class T>
         T LinkQueue<T>::DeQueue()
         {
             QNode<T>* p,*q;				//创建指针p,q
             T x;
             p = Head;
             while (p->next->next != Head)		//定位到队尾结点的前驱
             {
                 p = p->next;
             }
             if (Head->next != Head)			//判断是否为空队
             {
                 q = p->next;
                 p->next = q->next;
                 x = q->data;
                 delete q;
                 return x;
             }
             else
             {
                 cout<<"队列为空"<<endl;
             }
         }
     //获取队头元素
     template<class T>
         T LinkQueue<T>::GetHead()
         {
             QNode<T>* p;
             p = Head;
             if (p->next == Head)
             {
                 cout << "队列为空,无法删除" << endl;
             }
             else
             {
                 while (p->next != Head)		//定位队长
                 {
                     p = p->next;
                 }
                 cout << "队头元素为:";
                 return p->data;
             }
         }
     //获取队尾元素
     template<class T>
         T LinkQueue<T>::GetLast()
         {
             QNode<T>* p;
             p = Head->next;
             if (p == Head)
             {
                 cout << "队列为空,无队尾" << endl;
             }
             else
             {
                 cout << "队尾元素为:";
                 return Head->next->data;
             }
         }
     //测队空
     template<class T>
         int LinkQueue<T>::QueueEmpty()
         {
             if (Head->next == Head)
                 return 1;
             else
                 return 0;
         }
     //清空队
     template<class T>
         void LinkQueue<T>::ClearQueue()
         {
             if (Head->next == Head)
                 cout << "表为空，无需清空" << endl;
             else 
             {
                 Head->next = Head;
                 cout << "队列已清空" << endl;
             }
         }
     //遍历队列
     template<class T>
         void LinkQueue<T>::QueueTranverse()
         {
             QNode<T>* p;
             p = Head;
             cout << "队元素:" << endl;
             while (p->next != Head)
             {
                 p = p->next;
                 cout << p->data << '\t';
             }
             cout << endl;
         }

```
   - 主函数`main.cpp`

```c++
     #include<iostream>
     #include"LinkQueue.h"
     using namespace std;

int main()
     {
         //1.创建一个空队，并测队空
         LinkQueue<char>q;
         if (q.QueueEmpty())
             cout << "队空" << endl;
         else
             cout << "队不空" << endl;
         cout << "=======================================" << endl;
         //2.A、B、C、D、显示队长和队元素
         q.EnQueue('A');
         q.EnQueue('B');
         q.EnQueue('C');
         q.EnQueue('D');
         cout << q.GetHead() << endl;
         q.QueueTranverse();
         cout << "=======================================" << endl;
         //3.出队两次，显示队长和队元素
         q.DeQueue();
         q.DeQueue();
         cout << q.GetHead() << endl;
         q.QueueTranverse();
         cout << "=======================================" << endl;
         //4.执行出队操作3次
         q.DeQueue();
         q.DeQueue();
         q.DeQueue();
         cout << "=======================================" << endl;
         //5.执行入队操作若干次，显示列队元素
         char x;
         int n;
         cout << "输入字符数量：";
         cin >> n;
         cout << "请输入字符(空格空开，回车结束)：" << endl;
         for (int i = 0; i < n; i++)
         {
             cin >> x;
             q.EnQueue(x);
         }
         q.QueueTranverse();
         cout << "=======================================" << endl;
         //6.清空队后，再测队空
         q.ClearQueue();
         if (q.QueueEmpty())
             cout << "队空" << endl;
         else
             cout << "队不空" << endl;
     }
     ```
2. 收获

- 使用`throw`抛出错误会引发内存问题，不知道如何解决，暂时改用`cout`输出信息
   - 链队的入队即循环单链表的头插法，出队则是相当于单链表定位到队尾删除。

# 试验4.3 显示杨辉三角形

姓名：郁闷的酱油瓶

班级：软嵌

学号：114514

实验时间：2021.10.26

## 1.问题描述

杨辉三角形如图2.4.3所示，其特点是两个腰上数值是1，其他位置上的每一个整数都是它的上一行相邻两个整数之和。问题是：对于指定的最大行数rmax，要求从第一行到第rmax逐行显示杨辉三角形的所有元素。

## 2.数据结构设计

### (1)储存设计

使用队列存放每行的元素，但随着行数的增加，队列会很长。所以采用循环队列，队长不小于rmax+2.

```c++
template <class DT>
struct SqQueue   		//顺序队类
{
	DT* base; 		//队列首址
	int front; 		//队头指针
	int rear; 		//队尾指针
	int queuesize;		//队容量
};
```

### (2)函数设计

需要用的操作：构造函数，析构函数，入队，出队，获取队首，输出，测队长。

```c++
//构造函数
template <class DT>
void InitQueue(SqQueue<DT>& Q, int m)	//构建函数，创建一栈容量为m的空队
{
    Q.base = new DT[m];			// 申请队列空间
    if (Q.base == NULL)
    {
        cout << "未创建成功！";
        exit(1);
    }
    Q.front = Q.rear = 0;
    Q.queuesize = m;
}

//析构函数
template <class DT>
void DestroyQueue(SqQueue<DT>& Q)	//析构函数
{
    delete[] Q.base;			//释放队列空间
    Q.front = Q.rear = 0;
    Q.queuesize = 0;
}

//入队
template<class DT>
bool EnQueue(SqQueue<DT>& Q, DT e)
{
    if ((Q.rear + 1) % Q.queuesize == Q.front)     	//队满
        return false;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % Q.queuesize;
    return true;    					// 插入成功，返回true
}

//出队
template<class DT>
bool DeQueue(SqQueue<DT>& Q, DT& e)
{
    if (Q.front == Q.rear)  				//队空
        return false;
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % Q.queuesize;
    return true;   					// 删除成功，返回true
}

//获取队首
template<class DT>
bool GetHead(SqQueue<DT> Q, DT& e)
{
    if (Q.front == Q.rear)  				//队空
        return false;
    e = Q.base[Q.front];
    return true;    					//返回true
}

//按行输出，不显示0
template<class DT>
void TraverseQueue(SqQueue<DT> Q)
{
    int i = Q.front;
    while (i != Q.rear)
    {
        if (Q.base[i] != 0) 
        {
            cout << Q.base[i] << "\t";
        }
        i = (i + 1) % Q.queuesize;
    }
    cout << endl;
}
//测队列长度
template<class DT>
int LengthQueue(SqQueue<DT> Q)
{
    int i = Q.front;
    int flag = 0;
    while(i!=Q.rear)
    {
        flag++;
        i = (i + 1) % Q.queuesize;
    }
    return flag;
}
```

## 3.算法设计

考虑到要对第i-1行和第i行操作，所以使用两个队列来运算

#### Step 1

用int声明队列和变量

```c++
SqQueue<int>q1, q2;	//使用两个队列，q1存放i-1行，q2存放i行
int rmax, t1, t2;	//声明最大行数rmax，变量t1,t2
```

#### Step 2

输入行数，并用rmax+2初始化队列

```c++
cout << "请指定杨辉三角的最大行数：";
cin >> rmax;			//输入最大行数
InitQueue(q1, rmax+2);		//初始化列队q1，大小为rmax+2
InitQueue(q2, rmax+2);		//初始化列队q2，大小为rmax+2
```

#### Step 3

i从1到rmax行，循环操作求第i行数据

```c++
for (int i = 0; i < rmax; i++) {}
```

##### Step 3.1

第一行即i=0时，输入第一行的数据

```c++
if (i == 0)		//第一行
{
    EnQueue(q1, 0);	//0入队
    EnQueue(q1, 1);	//1入队
    EnQueue(q1, 0);	//0入队
}
```

##### Step 3.2

第二行及以上，q1出队一个元素与出队后的队首相加存入q2，最后留下一个0。操作完成后将q2复制到q1。

```c++
else					//第2及以上行数
{
    while (LengthQueue(q1) != 1)	//保留一个0
    {
        DeQueue(q1, t1);		//删除队首并保存到t1
        GetHead(q1, t2);		//获取队首并保存到t2
        EnQueue(q2, t1 + t2);		//t1+t2入队q2
    }
    while (LengthQueue(q2) != 0)	//将q2复制到q1
    {
        DeQueue(q2, t2);
        EnQueue(q1, t2);
    }
    EnQueue(q1, 0);			//0入队
}
```

##### Step 3.3

输出第i行

```c++
TraverseQueue(q1);//输出队列
```

## 4.测试运行

### 测试1

#### (1)运行程序

![运行](https://snz04pap001files.storage.live.com/y4mNLB_ogCm0z8QWqwGtRJQqD0FIbZDe9BmabUCFP2UKSpblQkTE1FGsgJNLPULXMOhBqcIcPOIGNkoP0NI-j7pA_mhH_DquwHmEC7puPfMvX3PvGdZFmwjGy0FlvoLIZKSG4kjs8gKvuixBOnmdjr_2z9_kENA8Zac1dqhBHmGf8-vOamkxohszpNn6sm5BwIO?width=1470&height=768&cropmode=none)

#### (2)输入10

![测试1](https://snz04pap001files.storage.live.com/y4m8CuouO6xmpqzZWyPQ0AYYM3tZAmlkINqKbFyvirnCwf8-BXrS_pwxsLdAM00gIj2dtoyFZFrlRSJur_xRNlKlfl4J4p-JQtKbyXM5Dgad7uKo5m5zt3mpgwbnwTEtXPNPO6af2HyH2fTPtP31HwHvUqqJodYqPWmsM9CQzpYctRvfYhlDI1SKbfnUEEo6LQd?width=1470&height=766&cropmode=none)

### 测试2

输入4

![测试2](https://snz04pap001files.storage.live.com/y4mojsa2Q1MOsiDsasAnj_QJFydUtIfU5sLLtSAmnMFRmi4qBTZHIxqMPWA5ltpkMdr4vPsYsqIKeBRJIVpcduL0_Lv5-ZRbL4pQ9_Y4_iO5R7s7uz_abjMJe4sAvLlh-5RBA9KrW8Iii6NoTfprGgA9T_qNq_aSGhaNfYaLQbRX1BumJ6TftFBdL5wxMWie1yj?width=1470&height=766&cropmode=none)

### 测试3

输入0

![测试3](https://snz04pap001files.storage.live.com/y4mQLMGcOtpFGNlSbNILxjfdLL32h9_YZLn8iIn0hyjSz0sVpdsi2FUxep8NyCvmwfNtdmJ28Rd-NbuxAcq3Zozre0HNLiKFUFT8GxP6poKZPNJe17pJ2tJlhoZ98XSLqQeC-yyNCSEWJKKhItypQIqVySUwSZW0CUlZUItcT2Pj7_sz2yfjFGgZDQ1eNCgx_6B?width=1470&height=768&cropmode=none)

## 5.调试记录与收获

1. 源程序清单

- `SqQueue.h`

```c++
     #pragma once
     #include<iostream>
     using namespace std;
     template <class DT>
     struct SqQueue   		//顺序队类
     {
     	DT* base; 		//队列首址
     	int front; 		//队头指针
     	int rear; 		//队尾指针
     	int queuesize;		//队容量
     };

//构造函数
     template <class DT>
     void InitQueue(SqQueue<DT>& Q, int m)
     {						//构建函数，创建一栈容量为m的空队
     	Q.base = new DT[m];			// 申请队列空间
     	if (Q.base == NULL)
     	{
     		cout << "未创建成功！";
     		exit(1);
     	}
     	Q.front = Q.rear = 0;
     	Q.queuesize = m;
     }

//析构函数
     template <class DT>
     void DestroyQueue(SqQueue<DT>& Q)		//析构函数
     {						//释放队列空间
     	delete[] Q.base;
     	Q.front = Q.rear = 0;
     	Q.queuesize = 0;
     }

//入队
     template<class DT>
     bool EnQueue(SqQueue<DT>& Q, DT e)
     {
     	if ((Q.rear + 1) % Q.queuesize == Q.front)     //队满
     		return false;
     	Q.base[Q.rear] = e;
     	Q.rear = (Q.rear + 1) % Q.queuesize;
     	return true;    				// 插入成功，返回true
     }

//出队
     template<class DT>
     bool DeQueue(SqQueue<DT>& Q, DT& e)
     {
     	if (Q.front == Q.rear)  			//队空
     		return false;
     	e = Q.base[Q.front];
     	Q.front = (Q.front + 1) % Q.queuesize;
     	return true;    				// 删除成功，返回true
     }

//获取队首
     template<class DT>
     bool GetHead(SqQueue<DT> Q, DT& e)
     {
     	if (Q.front == Q.rear)  			//队空
     		return false;
     	e = Q.base[Q.front];
     	return true;    				//返回true
     }

//按行输出，不显示0
     template<class DT>
     void TraverseQueue(SqQueue<DT> Q)
     {
     	int i = Q.front;
     	while (i != Q.rear)
     	{
     		if (Q.base[i] != 0) 
     		{
     			cout << Q.base[i] << "\t";
     		}
     		i = (i + 1) % Q.queuesize;
     	}
     	cout << endl;
     }
     //测队列长度
     template<class DT>
     int LengthQueue(SqQueue<DT> Q)
     {
     	int i = Q.front;
     	int flag = 0;
     	while(i!=Q.rear)
     	{
     		flag++;
     		i = (i + 1) % Q.queuesize;
     	}
     	return flag;
     }
     ```
   - `main.cpp`

```c++
     #include<iostream>
     #include"SqQueue.h"
     using namespace std;

int main()
     {
     	SqQueue<int>q1, q2;		//使用两个队列，q1存放i-1行，q2存放i行
     	int rmax, t1, t2;		//声明最大行数rmax，变量t1,t2
     	cout << "请指定杨辉三角的最大行数：";
     	cin >> rmax;			//输入最大行数
     	InitQueue(q1, rmax+2);		//初始化列队q1，大小为rmax+2
     	InitQueue(q2, rmax+2);		//初始化列队q2，大小为rmax+2
     	for (int i = 0; i < rmax; i++)	//计算每行元素
     	{
     		if (i == 0)		//第一行
     		{
     			EnQueue(q1, 0);	//0入队
     			EnQueue(q1, 1);	//1入队
     			EnQueue(q1, 0);	//0入队
     		}
     		else			//第2及以上行数
     		{
     			while (LengthQueue(q1) != 1)	//保留一个0
     			{
     				DeQueue(q1, t1);	//删除队首并保存到t1
     				GetHead(q1, t2);	//获取队首并保存到t2
     				EnQueue(q2, t1 + t2);	//t1+t2入队q2
     			}
     			while (LengthQueue(q2) != 0)	//将q2复制到q1
     			{
     				DeQueue(q2, t2);
     				EnQueue(q1, t2);
     			}
     			EnQueue(q1, 0);			//0入队
     		}
     		TraverseQueue(q1);			//输出队列
     	}
     	return 0;
     }
     ```
2. 收获：

- 掌握了顺序存储的循环队列的构造和使用

最后修改：2022 年 06 月 03 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

数据结构实践教程-栈、队列

酱油瓶 • 2021 年 10 月 26 日

本文为本人按照书本要求所写作业，算法并非最优，仅供参考
</div>

书为：《数据结构实践教程》清华大学出版社 主编：徐慧
</div>

# 试验3.1 表达式括号匹配配对判断问题

姓名：郁闷的酱油瓶

班级：软嵌

学号：114514

实验时间：2021.10.24

## 1.问题描述

假设一个算法表达式中包括圆括号、方括号两种，设计判别表达式中括号是否正确匹配的算法。

## 2.数据结构设计

### (1)结构设计

从节省空间的角度看，栈采用顺序表，栈元素类型为字符型

### (2)函数设计

本实验需要用到以下函数

## 3.算法设计

### step 1

创建一个栈,并从键盘输入表达式

```c++
SqStack<char>s(20);
string str;
cout << "请输入公式:";
cin >> str;
```

### step 2

从左到右扫描表达式，知道表达式结束

```c++
for (int i = 0; i < str.length(); i++) {}
```

#### 2.1

如果是左括号，入栈；取下一个字符

```c++
if (str[i] == '{' || str[i] == '(' || str[i] == '[') {s.Push(str[i]);}
```

#### 2.2

如果是右括号

```c++
if (str[i] == '}' || str[i] == ')' || str[i] == ']') {}
```

##### 2.2.1

与栈顶括号不匹配，则出栈，消去一个左括号；取下一个字符

```c++
else if ((str[i] == '}' && s.GetTop() == '{')
         || (str[i] == ']' && s.GetTop() == '[')
         || (str[i] == ')' && s.GetTop() == '('))
{
    s.Pop();
}
```

##### 2.2.2

与栈顶括号不匹配，得到"不匹配"结论，结束

##### 2.2.3

栈空，得到“不匹配”结论，结束

```c++
if(!s.StackEmpty())
{
    cout << "不匹配:"<<"多右括号"<<str[i] << endl;
    return 0;
}
```

### step 3

若栈空，则表达式中括号匹配；否则，不匹配。

```c++
if (!s.StackEmpty())
    cout << "匹配" << endl;
else
    cout << "不匹配:"<<"多左括号"<<s.GetTop() << endl;
```

## 4.测试与运行

### (1)测试1

1. 运行程序

### (2)测试2

### (3)测试3

### (4)测试4

### (5)测试5

## 5.调试记录与收获

1. 源文件清单

- 头文件`SqStack.h`

```
   - 主程序`main.cpp`

```c++
     #include<iostream>
     #include"SqStack.h"
     using namespace std;

- 在进行栈顶元素的获取操作时(即step2.2)，应先判断栈是否为空，否则会引发内存异常报错

# 试验4.2 单指针链队问题

姓名：郁闷的酱油瓶

班级：软嵌

学号：114514

实验时间：2021.10.25

## 1.问题描述

队列采用链式存储方式，但只允许设置一个指针。在其上实现：初始化、入队、出队、队元素显示、求队长、测队空、清空队等基本操作。

## 2.数据结构设计

### (1)结构设计

根据题目要求，使用带头节点的单指针循环链队

```c++
//结点设计
template<class T>
    struct QNode
    {
        T data;			//数据元素
        QNode<T>* next;		//指针域，指向下一个指针
    };
```

### (2)链表设计

根据要求，实现：初始化、入队、出队、队元素显示、测队空、清空队的操作

## 3.算法设计

### (1)函数实现

- 初始化

```c++
  //构造函数
  template<class T>
      LinkQueue<T>::LinkQueue()
      {
          Head = new QNode<T>;
          Head->next = Head;//创建空的循环单链
      }
  ```
- 元素x入队

### (2)测试操作

1. 创建一个空队，并测队空

```c++
   LinkQueue<char>q;
   if (q.QueueEmpty())
       cout << "队空" << endl;
   else
       cout << "队不空" << endl;
   ```
2. A、B、C、D、显示队长和队元素

```c++
   q.EnQueue('A');
   q.EnQueue('B');
   q.EnQueue('C');
   q.EnQueue('D');
   cout << q.GetHead() << endl;
   q.QueueTranverse();
   ```
3. 出队两次，显示队长和队元素

```c++
   q.DeQueue();
   q.DeQueue();
   cout << q.GetHead() << endl;
   q.QueueTranverse();
   ```
4. 执行出队操作3次

```c++
   q.DeQueue();
   q.DeQueue();
   q.DeQueue();
   ```
5. 执行入队操作若干次，显示列队元素，这里从键盘输入字符入队

```c++
   q.ClearQueue();
   if (q.QueueEmpty())
       cout << "队空" << endl;
   else
       cout << "队不空" << endl;
   ```

## 4.测试运行

### 测试1

基本操作已经分割开，第5项操作输入

输入字符数量：`5`
请输入字符(空格空开，回车结束)：`A B C D E`

### 测试2

输入字符数量：`0`
请输入字符(空格空开，回车结束)：``

## 5.调试记录与收获

1. 源文件清单

- 头文件`LinkQueue.h`

```c++
     #pragma once
     #include<iostream>
     using namespace std;

template<class T>
         struct QNode
         {
             T data;				//数据元素
             QNode<T>* next;			//指针域，指向下一个指针
         };

```
   - 主函数`main.cpp`

```c++
     #include<iostream>
     #include"LinkQueue.h"
     using namespace std;

# 试验4.3 显示杨辉三角形

姓名：郁闷的酱油瓶

班级：软嵌

学号：114514

实验时间：2021.10.26

## 1.问题描述

## 2.数据结构设计

### (1)储存设计

使用队列存放每行的元素，但随着行数的增加，队列会很长。所以采用循环队列，队长不小于rmax+2.

```c++
template <class DT>
struct SqQueue   		//顺序队类
{
	DT* base; 		//队列首址
	int front; 		//队头指针
	int rear; 		//队尾指针
	int queuesize;		//队容量
};
```

### (2)函数设计

需要用的操作：构造函数，析构函数，入队，出队，获取队首，输出，测队长。

//析构函数
template <class DT>
void DestroyQueue(SqQueue<DT>& Q)	//析构函数
{
    delete[] Q.base;			//释放队列空间
    Q.front = Q.rear = 0;
    Q.queuesize = 0;
}

//获取队首
template<class DT>
bool GetHead(SqQueue<DT> Q, DT& e)
{
    if (Q.front == Q.rear)  				//队空
        return false;
    e = Q.base[Q.front];
    return true;    					//返回true
}

## 3.算法设计

考虑到要对第i-1行和第i行操作，所以使用两个队列来运算

#### Step 1

用int声明队列和变量

```c++
SqQueue<int>q1, q2;	//使用两个队列，q1存放i-1行，q2存放i行
int rmax, t1, t2;	//声明最大行数rmax，变量t1,t2
```

#### Step 2

输入行数，并用rmax+2初始化队列

#### Step 3

i从1到rmax行，循环操作求第i行数据

```c++
for (int i = 0; i < rmax; i++) {}
```

##### Step 3.1

第一行即i=0时，输入第一行的数据

```c++
if (i == 0)		//第一行
{
    EnQueue(q1, 0);	//0入队
    EnQueue(q1, 1);	//1入队
    EnQueue(q1, 0);	//0入队
}
```

##### Step 3.2

第二行及以上，q1出队一个元素与出队后的队首相加存入q2，最后留下一个0。操作完成后将q2复制到q1。

##### Step 3.3

输出第i行

```c++
TraverseQueue(q1);//输出队列
```

## 4.测试运行

### 测试1

#### (1)运行程序

#### (2)输入10

### 测试2

输入4

### 测试3

输入0

## 5.调试记录与收获

1. 源程序清单

- `SqQueue.h`

//入队
     template<class DT>
     bool EnQueue(SqQueue<DT>& Q, DT e)
     {
     	if ((Q.rear + 1) % Q.queuesize == Q.front)     //队满
     		return false;
     	Q.base[Q.rear] = e;
     	Q.rear = (Q.rear + 1) % Q.queuesize;
     	return true;    				// 插入成功，返回true
     }

//出队
     template<class DT>
     bool DeQueue(SqQueue<DT>& Q, DT& e)
     {
     	if (Q.front == Q.rear)  			//队空
     		return false;
     	e = Q.base[Q.front];
     	Q.front = (Q.front + 1) % Q.queuesize;
     	return true;    				// 删除成功，返回true
     }

//按行输出，不显示0
     template<class DT>
     void TraverseQueue(SqQueue<DT> Q)
     {
     	int i = Q.front;
     	while (i != Q.rear)
     	{
     		if (Q.base[i] != 0) 
     		{
     			cout << Q.base[i] << "\t";
     		}
     		i = (i + 1) % Q.queuesize;
     	}
     	cout << endl;
     }
     //测队列长度
     template<class DT>
     int LengthQueue(SqQueue<DT> Q)
     {
     	int i = Q.front;
     	int flag = 0;
     	while(i!=Q.rear)
     	{
     		flag++;
     		i = (i + 1) % Q.queuesize;
     	}
     	return flag;
     }
     ```
   - `main.cpp`

```c++
     #include<iostream>
     #include"SqQueue.h"
     using namespace std;

- 掌握了顺序存储的循环队列的构造和使用

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

数据结构实践教程-栈、队列

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款