一区二区三区欧美成人,欧美日韩另类一区,欧美日韩中文

數(shù)據(jù)結(jié)構(gòu)中棧的應(yīng)用--迷宮問題

迷宮問題可以說是很經(jīng)典的問題,也算是棧的一個(gè)應(yīng)用吧,在談到這道題目時(shí),我首先想到的是迷宮存儲(chǔ)問題,我將他初始化成一個(gè)數(shù)組,為了模擬迷,我將1代表不可走,0代表可走.

然后定義迷宮類型,當(dāng)讓包括方向dir,行row,列col.而dir則包括了4個(gè)方向:即東南西北,當(dāng)然也可以設(shè)置成8個(gè)方向!
寫好了這些,就開始寫迷宮算法吧!代碼我都加上了注釋,以下程序均通過gcc4.1版本測試,運(yùn)行結(jié)果及代碼如下:

#include<stdio.h>
#include<stdbool.h>
#define MAX_STACK_SIZE 100
#define EXIT_ROW 9
#define EXIT_COL 9

int maze[10][10] = {
        {1,0,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,0,0,1,1,0,0,1},
        {1,0,1,1,1,0,0,0,0,1},
        {1,0,0,0,1,0,0,0,0,1},
        {1,0,1,0,0,0,1,0,0,1},
        {1,0,1,1,1,1,1,1,0,1},
        {1,1,0,0,0,0,0,0,0,1},
        {1,1,1,1,1,1,1,1,0,1}};/*初始化迷宮*/
int mark[10][10] = {0};/*初始化標(biāo)志位,0代表沒走過,1代表走過*/

/*方向*/
typedef struct{
    short int vert;
    short int horiz;
}offsets;

offsets move[4] = {{0,1},{1,0},{0,-1},{-1,0}};/*北,東,南,西*/

/*迷宮類型*/
typedef struct {
    short int row;
    short int col;
    short int dir;
}element;

element stack[MAX_STACK_SIZE];

void path(void);
element delete(int* top);
void add(int* top,element item);

element delete(int* top)/*出棧,top指向棧頂元素*/
{
    if(*top == -1)
    {
        printf("stack is empty!\n");
    }
    return stack[(*top)--];
}

void add(int* top,element item)/*入棧*/
{
    if(*top >= MAX_STACK_SIZE - 1)
    {
        printf("stack is full!\n");
        return;
    }
    stack[++*top] = item;
}

void path(void)/*迷宮函數(shù)*/
{
    element position;
    int i,row,col,next_row,next_col,dir,top;
    _Bool found = 0;
    mark[1][1] = 1,top = 0;/*初始化標(biāo)志數(shù)組元素以及棧*/
    stack[0].row = 1,stack[0].col = 1,stack[0].dir = 0;
    while(top > -1 && !found)
    {
        position = delete(&top);    /*將棧頂元素取出,*/
        row = position.row;            /*利用中間變量row,col,dir等候判斷*/
        col = position.col;
        dir = position.dir;
        while(dir < 4 && !found)
        {
            next_row = row + move[dir].vert;
            next_col = col + move[dir].horiz;
            if(next_row == EXIT_ROW && next_col == EXIT_COL)
                found = 1;
            else if(!maze[next_row][next_col] && !mark[next_row][next_col])/*判斷下一步可走并且沒走過,則入棧*/
                    {
                        mark[next_row][next_col] = 1;
                        position.row = row;
                        position.col = col;
                        position.dir = ++dir;
                        add(&top,position);/*合理則入棧*/
                        row = next_row;/*繼續(xù)向下走*/
                        col = next_col;dir = 0;
                    }
                    else
                        dir++;/*dir<4時(shí),改變方向*/
        }
        if(found)/*判斷是否有出口*/
        {
            printf("the path is:\n");
            printf("row col\n");
            for(i = 0;i <= top;++i)
                printf("%2d%5d",stack[i].row,stack[i].col);
            printf("%2d%5d\n",row,col);
            printf("%2d%5d\n",EXIT_ROW,EXIT_COL);
        }
    }
}

int main(void)
{
    path();
    return 0;
}

注釋:參見Fundamentals of Data STRUCTURES In C 中文版數(shù)據(jù)結(jié)構(gòu)(C語言版)

posted on 2007-04-28 23:22 honker 閱讀(5642) 評(píng)論(2) 編輯收藏引用所屬分類: c/c++

評(píng)論

# re: 數(shù)據(jù)結(jié)構(gòu)中棧的應(yīng)用--迷宮問題[未登錄] 2008-03-28 13:26 1

垃圾回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 數(shù)據(jù)結(jié)構(gòu)中棧的應(yīng)用--迷宮問題 C++課程設(shè)計(jì)

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

# re: 數(shù)據(jù)結(jié)構(gòu)中棧的應(yīng)用--迷宮問題[未登錄] 2008-03-28 13:26 1

數(shù)據(jù)結(jié)構(gòu)中棧的應(yīng)用--迷宮問題

評(píng)論

導(dǎo)航

常用鏈接

留言簿(3)

隨筆分類(10)

隨筆檔案(14)

相冊(cè)

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜