数据结构-迷宫全解与栈-YH三角与队列

发表于

PB2215xxxx-magichear

本次作业中，在文件头加入了以下内容：

1
2
3
4
5
6
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;

以尽量模仿课程环境，其他结构也尽可能参考了课程教学，请放心食用
正文中每个问题的结构为：$$问题\Rightarrow主文件\Rightarrow头文件$$

迷宫问题

本题我编写了一个名为 sqstack.h 的头文件，用于存放与栈有关的操作，以免主文件过于冗长。

经测试，在不影响到通路路径的情况下，将(3,3)、(6,1)等明显死胡同的道路堵住后，解的个数不变。

主文件

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<stdio.h>
#include "sqstack.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define m 8     // 迷宫的行
#define n 8     // 迷宫的列

typedef int Status;
typedef int MazeType;           // 迷宫数组定义

PosType dire[4] = { {0,1},{1,0},{0,-1},{-1,0} }; //{行增量，列增量}
PosType start,end;              // 起止位置

MazeType maze[m+2][n+2] = {     // 迷宫数组内容
    {1,1,1,1,1,1,1,1,1,1},
    {1,0,0,1,0,0,0,1,0,1},
    {1,0,0,1,0,0,0,1,0,1},
    {1,0,0,1,0,1,1,0,0,1},	// (3,3)位置堵住，最终结果不变
    {1,0,1,1,1,0,0,0,0,1},
    {1,0,0,0,1,0,0,0,0,1},
    {1,1,1,0,0,0,1,0,0,1},	// (6,1)位置堵住，最终结果不变
    {1,0,1,1,1,0,1,1,0,1},
    {1,1,0,0,0,1,0,0,0,1},
    {1,1,1,1,1,1,1,1,1,1},
};	// 除上述两点外，与PPT中给出的是同一个迷宫

Status printPath(SqStack *p, int* PathCount);   // 打印函数声明
Status MazePath(int maze[][n+2], int* PathCount, int x, int y, SqStack *p); // 求解函数声明
Status MarkPrint(SElemType e);                  // 标记经过路径

Status main() {
	SqStack mazeStack;
	InitStack(&mazeStack);  // 创建、初始化栈

	int PathCount = 0; 		// 路径计数
    start.x = 1;            // 设定起止条件
    start.y = 1;
    end.x = m;
    end.y = n;

	MazePath(maze, &PathCount,start.x,start.y,&mazeStack);    // 求解迷宫

	DestroyStack(&mazeStack);                                 // 销毁栈
    return OK;
}

Status printPath(SqStack *p, int* PathCount) {
	*PathCount += 1;
	printf("Path %d :\n", *PathCount);
	SElemType e;
	for (SElemType* i = p->base; i < p->top; i++) {
		e = *i;
		printf("(%d,%d)->", e.seat.x, e.seat.y);
	}
	printf("Exit Found!\n\n");
	return OK;
}

// 标记迷宫块不可通过
Status MarkPrint(SElemType e)
{
    maze[e.seat.x][e.seat.y] = -1;
    return OK;
}

Status MazePath(int maze[][n+2], int* PathCount, int x, int y, SqStack *p) {

    // 走到终点
	if (x == end.x && y == end.y) {
		maze[x][y] = -1;

		// 将终点存入路径中
		SElemType e;
		e.seat.x = x;
		e.seat.y = y;
		Push(p, e);

        //输出路径
		printPath(p, PathCount);

        // 输出完毕
		Pop(p, &e);     // 弹出end point
		maze[x][y] = 0; // 标记end point为未访问

		return TRUE;
	}
	else {
		// 若当前位置为0(未被标记)
		if (maze[x][y] == 0) {
			int di = 0;

            //4个方向都进行试探
			while (di < 4) {

				//储存当前位置
				SElemType e;
				e.seat.x = x;
				e.seat.y = y;

				//标记为-1，表示已经走过
 				MarkPrint(e);
				Push(p, e);

				//改变方向
				int i, j;
				i = x + dire[di].x;
				j = y + dire[di].y;

				MazePath(maze, PathCount, i, j, p);

				// 抹除当前位置
				Pop(p, &e);
				maze[x][y] = 0;

				di++;//改变方向
			}
		}
		//不能走的话就返回，回到上一个位置
		else
			return OK;
	}
    return OK;
}

栈操作头文件

sqstack.h，动态分配内存

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#pragma once
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100//储存空间初始分配量
#define STACKINCREMENT  10//存储空间分配增量
#define OK 1
#define ERROR 0
typedef struct {
    int x;  //行值
    int y;  //列值
}PosType;  //迷宫坐标位置类型
typedef struct
{
    int ord;      //序号
    PosType seat; //位置
    int di;       //方向
} SElemType; //栈元素类型

typedef struct {
    SElemType *base;   //在构造之前和销毁之后，base的值为NULL
    SElemType *top;    //栈顶指针
    int stacksize;     //当前已分配的存储空间，以元素为单位

}SqStack; //顺序栈

//栈的初始化
int InitStack(SqStack *p) {


    p->base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if (p->base == NULL)
        return ERROR;  //内存分配失败
    p->top = p->base;     //栈顶与栈底相同表示一个空栈
    p->stacksize = STACK_INIT_SIZE;
    return OK;

}
//判断栈是否为空
int EmptyStack(SqStack *p) {
    //若为空栈 则返回OK，否则返回ERROR
    if (p->top == p->base)
        return OK;
    else return ERROR;
}
//顺序栈的压入
int Push(SqStack *p, SElemType e) {
    //插入元素e为新的栈顶元素
    if ((p->top - p->base) >= p->stacksize)   //栈满，追加储存空间
    {
        p->base = (SElemType*)realloc(p->base, (p->stacksize + STACKINCREMENT) * sizeof(SElemType));
        if (p->base == NULL)
            return ERROR;// 储存空间分配失败
        p->top = p->base + p->stacksize;
        p->stacksize += STACKINCREMENT;
    }
    *(p->top) = e;
    (p->top)++;
    return OK;
}


// 顺序栈的弹出
int Pop(SqStack *p, SElemType *e) {
    //若栈不空，则删除p的栈顶元素，用e返回其值
    if (p->top == p->base)
        return ERROR;
    --(p->top);
    *e = *(p->top);
    return OK;


}
//将顺序栈置空 栈还是存在的，栈中的元素也存在，
//如果有栈中元素的地址任然能调用
int ClearStack(SqStack *p) {
    p->top = p->base;
    return OK;
}
//顺序栈的销毁
int DestroyStack(SqStack *p) {
    //释放栈底空间并置空
    free(p->base);
    p->base = NULL;
    p->top = NULL;
    p->stacksize = 0;

    return OK;
}

打印杨辉三角

本题同样编写了一个名为SeqQueue.h的头文件用于处理与队列有关的操作

主代码中，对 PPT 里的提示做了些改边，使用了do-while语句。//–//之间的内容为我额外添加，其余部分与 PPT 中的基本类似。
PPT 中内容：

1
2
3
4
5
6
7
EnQueue (q,0);	//各行间插入一个0
for ( j=1; j<=i+2; j++ ) {
    DeQueue (q,t );	  //一个系数出队
    EnQueue (q, s+t );	//计算下一行系数，并进队
    s = t;
    if ( j != i+2 ) cout << s << ' ';	//第i+2个0 }

我的改写（部分）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
k=1;
while(k<n){
    // 0 作为转行符，入队列
    EnQueue(&Q,0);
    do{
        //队头元素出队列
        DeQueue(&Q,&s);
    // -----------------------------------------------
        //取新的队头元素
        GetHead(&Q,&e);
        //如果所取元素非 0，则输出，否则做转行操作
        if(e){
            printf("%4d ",e);
        }else{
            printf(" \n");
        }
    // -----------------------------------------------
        EnQueue(&Q,s+e);
    }while(e!=0);//一旦 e 值为 0，即做转行操作，退出循环，开始新一行的排列
    k++;
}

主代码

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
#include <stdio.h>
#include <stdlib.h>
#include "SeqQueue.h"

//杨辉三角实现函数
void yanghui(int n){
    SeqQueue Q;
    int s,e,k;
    //输出 1
    printf("%4d\n",1);
    //初始化队列
    InitQueue(&Q);
    // 将三角的第二行作为起始行，向下推导
    EnQueue(&Q,0);
    EnQueue(&Q,1);
    EnQueue(&Q,1);
    k=1;
    while(k<n){
        // 0 作为转行符，入队列
        EnQueue(&Q,0);
        do{
            //队头元素出队列
            DeQueue(&Q,&s);
        // -----------------------------------------------
            //取新的队头元素
            GetHead(&Q,&e);
            //如果所取元素非 0，则输出，否则做转行操作
            if(e){
                printf("%4d ",e);
            }else{
                printf(" \n");
            }
        // -----------------------------------------------
            EnQueue(&Q,s+e);
        }while(e!=0);//一旦 e 值为 0，即做转行操作，退出循环，开始新一行的排列
        k++;
    }
    //出循环后，队列中还存有下一行的数据
    DeQueue(&Q,&e);
    while(!IsEmpty(&Q)){
        DeQueue(&Q,&e);
        printf("%4d ",e);
    }
    DestroyQueue(&Q);
}
int main(){
    yanghui(15);
    return 0;
}

队列操作头文件

SeqQueue.h，同样动态分配内存，不过本题没有设置初始分配量

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#pragma once
#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;
typedef int QElemType;

typedef struct QNode
{
    QElemType data;
    struct QNode *next;
}QNode, *QueuePtr;

typedef struct
{
    QueuePtr front;//队头
    QueuePtr rear;//队尾
}SeqQueue;

void InitQueue(SeqQueue *Q)//初始化
{
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
    if (!Q->front) exit(OVERFLOW);
    Q->front->next = NULL;
}

Status EnQueue(SeqQueue *Q, QElemType e)//入队
{
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if (!p) exit(OVERFLOW);
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
    return OK;
}

Status DeQueue(SeqQueue *Q, QElemType *e)//出队
{
    if (Q->front == Q->rear)
        return ERROR;
    QueuePtr p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if (Q->rear == p) Q->rear = Q->front;
    free(p);
    return OK;
}

Status GetHead(SeqQueue *Q, QElemType *e)//取队头元素
{
    if (Q->front == Q->rear)
        return ERROR;
    *e = Q->front->next->data;
    return OK;
}

Status IsEmpty(SeqQueue *Q)
{
    if (Q->rear == Q->front)
        return OK;
    else
        return ERROR;
}

Status DestroyQueue(SeqQueue *Q)//销毁队列
{
    while (Q->front)
    {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
    return OK;
}