實驗任務(wù)

(1) 掌握順序循環(huán)隊列及其C語言的表示；
(2) 掌握入隊、出隊等基本算法的實現(xiàn)；
(3) 掌握順序循環(huán)隊列的基本應(yīng)用（求解迷宮通路）。

實驗內(nèi)容

• 使用C語言實現(xiàn)順序循環(huán)隊列的類型定義與算法函數(shù)；
• 編寫main()函數(shù)并根據(jù)需要修改、補充相關(guān)的類型定義與函數(shù)，以實現(xiàn)“求解迷宮通路”問題：
• 求解迷宮通路問題描述：
  • 給定一個M×N的迷宮圖，指定一個入口與一個出口；
  • 規(guī)定行走規(guī)則為：按“上右下左”優(yōu)先順序向相鄰空位移動1格，用（i，j）表示迷宮中的第i行第j列的一個方塊
  • 在迷宮外圍加上圍墻；
• 實現(xiàn)指定入口和出口的固定迷宮；
• 實現(xiàn)隨機入口和出口的固定迷宮；
• 實現(xiàn)障礙、入口和出口都隨機的迷宮。

實驗源碼

注意：必須在Dos窗口下運行，并且以管理員身份打開Dos窗口最佳

#include <stdio.h>
#include <time.h>
#include "windows.h"

#define MAXSIZE 1000
#define ROW 15
#define LINE 15
#define RATIO 0.6875 // 44/64的比例
#define COORDINATE -1 // 坐標默認 值
#define DISTOP 5 // 迷宮距離頂端距離格數(shù)

#define PASS 0 // 通路
#define WALL 1 // 墻
#define ENTRY 2 // 入口
#define EXIT 3 // 出口
#define DEAD 5 // 死路

// 延時設(shè)置
int walkDelay = 500;
int dirDelay = 1000;

typedef struct Box {
    int x;           // 點的橫坐標（行）
    int y;           // 點的縱坐標（列）
    int pre;         // 上一個點的下標
} Box;

typedef struct {
    Box *base;
    int front;
    int rear;
} SqQueue;

void Map(int map[][LINE]); // 生成地圖

void KnuthShuffle(int map[], int length); // 洗牌算法

void swapInt(int *a, int *b); // 輔助洗牌算法 交換

void PrintMap(int map[][LINE]); // 打印迷宮地圖

boolean InitQueue(SqQueue *queue); // 循環(huán)隊列的初始化

void Walk(SqQueue *queue, int in_x, int in_y, int map[][LINE]); // 移動迷宮

boolean EnQueue(SqQueue *queue, Box node); // 循環(huán)隊列入隊列

boolean IsFull(SqQueue *queue); // 判隊滿

boolean IsEmpty(SqQueue *queue); // 判隊空

Box DeQueue(SqQueue *queue); // 循環(huán)隊列出隊列

void ShowPath(SqQueue *queue, int end); // 求解最短路徑

void Color(short x); // 自定義函根據(jù)參數(shù)改變顏色

void DirTest(int map[][LINE], int dir, int j, int k); // 方向試探

void DeadPath(int j, int k); // 置為死路

void GotoXY(int x, int y); // 將光標移至屏幕 第x列，第y行 處

void DisplayQueue(SqQueue *queue); // 隊列動態(tài)展示

void HideCursor(void); // 隱藏光標

/**
 * <h2>順序隊列實驗</h2>
 * <h3>隨機迷宮問題</h3>
 * <h3>注意：請在Dos窗口下運行</h3>
 * <h4>非循環(huán)隊列，并不是真的退出隊列</h4>
 * @return 0
 */
int main() {

    GotoXY(0, 0);
    Color(9);
    printf("  使用隊列解決迷宮通路問題 \n");
    GotoXY(0, 1);
    printf("==============================\n");
    GotoXY(0, 2);
    Color(12);
    printf("Ｘ--走過的無效通路");
    Color(9);
    printf("  囚--起點\n");
    GotoXY(0, 3);
    Color(13);
    printf("Ｏ--走過的有效通路");
    Color(11);
    printf("  口--終點\n");
    GotoXY(0, 4);
    printf("------------------------------\n");

    srand(time(NULL));

    int map[ROW][LINE];
    Map(map);
    PrintMap(map);

    SqQueue queue;
    if (!(InitQueue(&queue))) {
        printf("隊列初始化失敗~~\n");
        return 0;
    }

    int in_x, in_y;
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < LINE; j++) {
            if (map[i][j] == ENTRY) {
                in_x = i;
                in_y = j;
            }
        }
    }

    HideCursor();
    DisplayQueue(&queue);
    Walk(&queue, in_x, in_y, map);

    getchar();
}

void Map(int map[][LINE]) {
    int length = (ROW - 2) * (LINE - 2); // 8 * 8 內(nèi)區(qū)域
    int randArr[length];
    for (int i = 0; i < length; i++) {
        if (i == 0) {
            randArr[i++] = ENTRY;
            randArr[i++] = EXIT;
        }
        if (i < (length * RATIO) + 2) {
            randArr[i] = PASS;
        } else {
            randArr[i] = WALL;
        }
    }
    KnuthShuffle(randArr, length); // 打亂 內(nèi)區(qū)域
    // 賦值整張地圖
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < LINE; j++) {
            // 這里一個小技巧：只要前面四個表達式一個為假，說明未到邊界賦值，保證Length不會越界
            if (i != 0 && i != ROW - 1 && j != 0 && j != LINE - 1 && length--) {
                map[i][j] = randArr[length];
            } else {
                map[i][j] = WALL;
            }
        }
    }
}

void KnuthShuffle(int map[], int length) {
    for (int i = length - 1; i >= 1; i--) {
        swapInt(&map[i], &map[rand() % (i + 1)]);
    }
}

void swapInt(int *a, int *b) {
    int t;
    t = *a;
    *a = *b;
    *b = t;
}

void PrintMap(int map[][LINE]) {
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < LINE; j++) {
            GotoXY(j * 2, i + DISTOP);
            switch (map[i][j]) {
                case PASS:
                    printf("　");
                    break;
                case WALL:
                    Color(10);
                    printf("圍");
                    break;
                case ENTRY:
                    Color(9);
                    printf("囚");
                    break;
                case EXIT:
                    Color(11);
                    printf("口");
                    break;
            }
        }
        printf("\n");
    }
    Sleep(3000);
}

boolean InitQueue(SqQueue *queue) {
    queue->base = (Box *) malloc(sizeof(Box) * MAXSIZE);
    if (!(queue->base)) {
        return FALSE;
    }
    queue->front = queue->rear = 0;
    return TRUE;
}

void Walk(SqQueue *queue, int in_x, int in_y, int map[][LINE]) {
    // 起點先入隊列
    Box node; // 生成當前位置(起點)
    node.x = in_x;
    node.y = in_y;
    node.pre = COORDINATE; // 起點位置下標 -1

    EnQueue(queue, node); // 起點入隊列

    while (!(IsEmpty(queue))) { // 無路可走的情況，回到起點
        node = DeQueue(queue); // 取出隊頭位置 隊頭指針front++

        if (map[node.x][node.y] == EXIT) { // 判斷當前位置是否是終點
            ShowPath(queue, queue->front);
            return;
        }
        int dir; // 裝方向
        Box tNode; // 生成下一個位置
        for (dir = 0; dir < 4; dir++) { // 判斷當前位置各個方向是否可走
            switch (dir) {
                case 0:
                    tNode.x = node.x - 1;
                    tNode.y = node.y;
                    DirTest(map, dir, node.x, node.y);
                    break;
                case 1:
                    tNode.x = node.x;
                    tNode.y = node.y + 1;
                    DirTest(map, dir, node.x, node.y);
                    break;
                case 2:
                    tNode.x = node.x + 1;
                    tNode.y = node.y;
                    DirTest(map, dir, node.x, node.y);
                    break;
                case 3:
                    tNode.x = node.x;
                    tNode.y = node.y - 1;
                    DirTest(map, dir, node.x, node.y);
                    break;
            }
            if (map[tNode.x][tNode.y] == PASS || map[tNode.x][tNode.y] == EXIT) { // 判斷這個方向 是否可走
                tNode.pre = queue->front - 1; // 把節(jié)點位置的下標給 新位置
                EnQueue(queue, tNode); // 入隊
                if (map[tNode.x][tNode.y] == PASS) {
                    map[tNode.x][tNode.y] = DEAD;
                    DeadPath(tNode.x, tNode.y);

                }
            }
        }
    }
    // 這里加二號條件的原因是：此程序使用的是終點出隊列即停止，但是也不排除 到終點即為空
    if (IsEmpty(queue) && map[node.x][node.y] != EXIT) {
        GotoXY(0, ROW + DISTOP + 2);
        Color(12);
        printf("\t無路可走，死翹翹了~~\n");
    }
}

boolean EnQueue(SqQueue *queue, Box node) {
    if (IsFull(queue)) {
        return FALSE;
    }
    queue->base[queue->rear] = node; // 新元素插入隊尾
    queue->rear = queue->rear + 1; // 隊尾指針加 1
    DisplayQueue(queue);
    return TRUE;
}

boolean IsFull(SqQueue *queue) {
    return queue->rear + 1 == queue->front; // 非循環(huán)隊列
}

boolean IsEmpty(SqQueue *queue) {
    return queue->rear == queue->front;
}

Box DeQueue(SqQueue *queue) {
    Box box = queue->base[queue->front++];
    DisplayQueue(queue);
    return box; // 取出隊頭元素，并把其出隊列
}

void ShowPath(SqQueue *queue, int end) {
    int i, tmp;
    for (i = end - 1; i >= 0;) {
        tmp = queue->base[i].pre;
        queue->base[i].pre = COORDINATE;
        i = tmp;
    }
    int count = 0, ti;
    for (i = 1; i < end; i++) { // i = 1, 保證不是終點即可
        if (queue->base[i].pre == COORDINATE) {
            if (count == 0) {
                GotoXY(LINE * 2 + 35, DISTOP - 1);
                printf("↓ 路徑打印 ↓");
                GotoXY(LINE * 2 + 35, DISTOP);
                printf("|__i__j__pre__|");
            }
            count++;
            GotoXY(LINE * 2 + 35, DISTOP + count);
            printf("|_____________|\n");
            Color(11);
            GotoXY(LINE * 2 + 35 + 3, DISTOP + count);
            printf("%d", queue->base[i].x);
            GotoXY(LINE * 2 + 35 + 7, DISTOP + count);
            printf("%d", queue->base[i].y);
            GotoXY(LINE * 2 + 35 + 10, DISTOP + count);
            printf("%d", queue->base[i].pre);
            if (count == 1) {
                ti = i;
                continue;
            }
            GotoXY(queue->base[ti].y * 2, queue->base[ti].x + DISTOP);
            Color(15);
            if (queue->base[i].x - queue->base[ti].x == -1 &&
                queue->base[i].y - queue->base[ti].y == 0) {
                printf("↑");
            } else if (queue->base[i].x - queue->base[ti].x == 0 &&
                       queue->base[i].y - queue->base[ti].y == 1) {
                printf("→");
            } else if (queue->base[i].x - queue->base[ti].x == 1 &&
                       queue->base[i].y - queue->base[ti].y == 0) {
                printf("↓");
            } else {
                printf("←");
            }
            ti = i;
        }
    }
}

void Color(short x) {
    if (x >= 0 && x <= 15) { // 參數(shù)在0-15的范圍顏色
        SetConsoleTextAttribute( // 調(diào)用設(shè)置控制臺文本屬性函數(shù)(調(diào)用獲取句柄函數(shù)(不理解), 不理解)
                GetStdHandle(STD_OUTPUT_HANDLE), x);    // 只有一個參數(shù)，改變字體顏色
    } else { // 默認的顏色白色
        SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);
    }
}

void DirTest(int map[][LINE], int dir, int j, int k) {
    GotoXY(k * 2, j + DISTOP);
    Color(15);
    switch (dir) {
        case 0:
            printf("↑");
            break;
        case 1:
            printf("→");
            break;
        case 2:
            printf("↓");
            break;
        case 3:
            printf("←");
            break;
    }
    Sleep(dirDelay);
    GotoXY(k * 2, j + DISTOP);
    Color(13);
    switch (map[j][k]) {
        case ENTRY:
            Color(9);
            printf("囚");
            break;
        case DEAD:
            Color(12);
            printf("Ｘ");
            break;
    }
}

void DeadPath(int j, int k) {
    GotoXY(k * 2, j + DISTOP);
    Color(12);
    printf("Ｘ");
    Sleep(walkDelay);
}

void GotoXY(int x, int y) {
    COORD pos = {x, y}; // 坐標
    HANDLE hOut = GetStdHandle(STD_OUTPUT_HANDLE); // 獲取句柄（標準輸出句柄）
    SetConsoleCursorPosition(hOut, pos); // 設(shè)置控制臺光標位置
}

void DisplayQueue(SqQueue *queue) {
    int len = ROW - 1;
    Color(12);
    GotoXY(LINE * 2 + 10, DISTOP);
    printf("|__i__j__di__| <- top");
    for (int j = 1; j <= len; j++) {
        GotoXY(LINE * 2 + 10, DISTOP + j);
        printf("|____________|\n");
    }
    int length = queue->rear;
    for (int i = 0; i < length; i++, len--) {
        if (len == 0) {
            len = ROW - 1;
            for (int j = 1; j <= len; j++) {
                GotoXY(LINE * 2 + 10, DISTOP + j);
                printf("|____________|\n");
            }
        }
        Color(11);
        GotoXY(LINE * 2 + 10 + 3, DISTOP + len);
        printf("%d", queue->base[i].x);
        GotoXY(LINE * 2 + 10 + 7, DISTOP + len);
        printf("%d", queue->base[i].y);
        GotoXY(LINE * 2 + 10 + 10, DISTOP + len);
        printf("%d", queue->base[i].pre);
    }
}

void HideCursor(void) {
    CONSOLE_CURSOR_INFO cursor_info = {1, 0};
    SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursor_info);
}

實驗結(jié)果

文章來源地址http://www.zghlxwxcb.cn/news/detail-609734.html

到了這里，關(guān)于C數(shù)據(jù)結(jié)構(gòu)與算法——隊列 應(yīng)用（C語言純享版 迷宮）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！