nanodesu~ > 数据结构试验报告-栈和队列

数据结构试验报告-栈和队列

2019-10-21

数据结构, c/c++, 算法, 栈, 队列

数据结构试验报告-栈和队列

[toc]

一、试验题目与目的

  • 以一个 m*n 的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
  • 分别用栈和队列作为数据结构，使用非递归的dfs和bfs算法，找出路径。

二、试验环境

  • 操作系统： Ubuntu 18.04 LTS
  • IDE：CLion
  • Online Judge：vjudge & POJ
  • 题目：https://vjudge.net/problem/POJ-3984
    注：这里找了一道相似的题用于测试提交，代码最终结果仍然以该实验题目为准

三、实验问题

1.选择如何实现数据结构出现错误
我先选择的是stl中的stack和queue来作为栈和队列，但发现最后需要输出路径时，由于stack和queue不提供迭代器，无法直接遍历元素。于是我在dfs算法中用deque双端队列模拟栈，在bfs算法中用数组来模拟栈。

2.关于方向处理的问题
起初我选择不同方向走用了四个if来判断，然后用一个变量来记录判过哪个方向，使得代码十分冗余，后来，我使用d数组来存储不同的方向，简化了代码。

3.bfs算法中对路径的存储问题
最后采用链表结构

四、试验小结

这次实验我收获了许多：
1.我更加熟悉了stl中deque，stack，queue的操作方法和适用条件，并且能针对实际问题用数组去替代实现。
2.我学会不使用指针，用结构体的一个整型变量来记录下一个节点的地址来实现链表的功能。
3.我学会了用栈写非递归的dfs算法，并且能与递归的dfs算法相互转换。
4.我学会了用队列实现bfs算法，并能用链表记录路径。
5.我还明白了，在写程序代码前首先要设计好数据结构，尽可能考虑全数据结构要实现的功能，是否选择现成的stl也值得考虑。

五、数据结构

1.dfs算法：

  • Road结构体记录坐标

    1
    2
    3
    4
    5
    6
    7
    8
      struct Road {
            int r,c;
            Road(){}
            Road(int x,int y){
                r=x,c=y;
            }
    };

  • 使用stl中deque模拟栈

    1
    deque<Road> st;

2.bfs算法：

  • Road结构体记录坐标

    1
    2
    3
    4
    struct Road {
            int r,c;
            int f;
    };

  • 结构体中f记录上一个节点在队列中的索引，方便之后的输出路径，实为链表结构

  • 直接用数组模拟队列

    1
    2
    3
      const int MAXN=1001;
    Road q[MAXN];//队列
    int head=0,tail=0;

六、主要算法

1.dfs算法

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <deque>
using namespace std;
struct Road {
    int r,c;
    Road(){}
    Road(int x,int y){
        r=x,c=y;
    }
};
bool maze[5][5];//迷宫
bool visited[5][5];//是否被访问过
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//方向
int m,n;
int startx,starty,endx,endy;
deque<Road> st;
void dfs(int x,int y){
    st.push_back(Road(x,y));
    while(!st.empty()){
        Road front = st.back();
        int i;
        for(i=0; i<4; i++){
            Road last;
            last.r=front.r+d[i][0];
            last.c=front.c+d[i][1];
            if(last.r>=m||last.c>=n||last.r<0||last.c<0)continue;
            if(maze[last.r][last.c]==0&&visited[last.r][last.c]==0){
                visited[last.r][last.c]=1;
                st.push_back(last);
                break;
            }
        }
        if(st.back().r == endx && st.back().c==endy){
            for(deque<Road>::iterator it=st.begin();it!=st.end();it++){
                printf("(%d, %d)\n",it->r,it->c);
            }
            st.pop_back();
            continue;
        }
        if(i==4)st.pop_back();
    }
}
int main(){
    scanf("%d%d%d%d%d%d",&m,&n,&startx,&starty,&endx,&endy);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d",&maze[i][j]);
        }
    }
   dfs(startx,starty);
   return 0;
}

2.bfs算法

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
struct Road {
    int r,c;
    int f;
};
const int MAXN=1001;
Road q[MAXN];//队列
int head=0,tail=0;
bool maze[5][5];//迷宫
bool visited[5][5];//是否被访问过
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//方向
int m,n;
int startx,starty,endx,endy;

void bfs(){
    while (head<tail) {
        Road front=q[head];//保存队头
        if (front.c==endx&&front.r==endy) {
            //达到终点退出循环
            break;
        }
        for (int i=0;i<4;i++) {
            Road last;
            last.r=front.r+d[i][0];
            last.c=front.c+d[i][1];
            if (last.r>=0&&last.r<m&&last.c<n&&last.c>=0) {
                if (!visited[last.r][last.c]&&!maze[last.r][last.c]) {
                    last.f=head;//记录入队前head值方便之后打印路径
                    q[tail++]=last;//入队
                    visited[last.r][last.c]=true;//已经访问，做上标记
                }
            }
        }
        //出队
        head++;
    }
}

int main(){
    int path[30];
    scanf("%d%d%d%d%d%d",&m,&n,&startx,&starty,&endx,&endy);
    for (int i=0;i<5;i++) {
        for (int j=0;j<5;j++) {
            scanf("%d",&maze[i][j]);
        }
    }
    Road a={0,0,-1};
    q[tail++]=a;
    visited[0][0]=1;
    bfs();
    int i=0;
    while (q[head].f>=0) {
        path[i++]=q[head].f;
        head=path[i-1];
    }
    for (int j=i-1;j>=0;j--) {
        printf("(%d, %d)\n",q[path[j]].r,q[path[j]].c);
    }
    printf("(%d, %d)",endx,endy);
    return 0;
}