用C++写一个A*算法

当您需要寻找从起点到终点的最短路径时，A *算法是一种常用的搜索算法。这是一个示例代码的框架，需要根据您具体的问题进行修改。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct Node {
    int x, y;
    int g, h;
    struct Node *parent;
} Node;

#define MAP_ROWS 10
#define MAP_COLS 10
int map[MAP_ROWS][MAP_COLS] = {
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,1,0,0,0,0,0},
    {0,0,0,1,1,1,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
};

Node *open_list[MAP_ROWS * MAP_COLS] = {NULL};
Node *close_list[MAP_ROWS * MAP_COLS] = {NULL};

int is_node_in_list(Node *node, Node **list);
void insert_node_to_list(Node *node, Node **list);
void delete_node_from_list(Node *node, Node **list);
int distance(Node *from, Node *to);
Node *get_lowest_f_in_list(Node **list);
Node *create_node(int x, int y);
void destroy_node(Node *node);
void destroy_list(Node **list);
void search_path(Node *start, Node *end);
void print_path(Node *node);

int main() {
    Node *start = create_node(1,1);
    Node *end = create_node(5,5);

    search_path(start, end);

    print_path(end);

    destroy_node(start);
    destroy_node(end);
    destroy_list(open_list);
    destroy_list(close_list);
    return 0;
}

int is_node_in_list(Node *node, Node **list) {
    for(int i = 0; i < MAP_ROWS * MAP_COLS - 1; i++) {
        if(list[i] == NULL) {
            return 0;
        }

        if(list[i]->x == node->x && list[i]->y == node->y) {
            return 1;
        }
    }

    return 0;
}

void insert_node_to_list(Node *node, Node **list) {
    int i = 0;
    while(list[i] != NULL) {
        i++;
    }

    list[i] = node;
}

void delete_node_from_list(Node *node, Node **list) {
    int i = 0;
    while(list[i] != NULL) {
        if(list[i] == node) {
            list[i] = NULL;
            break;
        }

        i++;
    }
}

int distance(Node *from, Node *to) {
    return abs(from->x - to->x) + abs(from->y - to->y);
}

Node *get_lowest_f_in_list(Node **list) {
    Node *lowest_node = NULL;
    for(int i = 0; i < MAP_ROWS * MAP_COLS - 1; i++) {
        if(list[i] == NULL) {
            break;
        }

        if(lowest_node == NULL || lowest_node->g + lowest_node->h >
           list[i]->g + list[i]->h) {
            lowest_node = list[i];
        }
    }

    return lowest_node;
}

Node *create_node(int x, int y) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->x = x;
    node->y = y;
    node->g = 0;
    node->h = 0;
    node->parent = NULL;

    return node;
}

void destroy_node(Node *node) {
    free(node);
}

void destroy_list(Node **list) {
    for(int i = 0; i < MAP_ROWS * MAP_COLS - 1; i++) {
        if(list[i] != NULL) {
            destroy_node(list[i]);
            list[i] = NULL;
        }
        else {
            break;
        }
    }
}

void search_path(Node *start, Node *end) {
    insert_node_to_list(start, open_list);

    while(open_list[0] != NULL &&
          !is_node_in_list(end, close_list)) {
        Node *current = get_lowest_f_in_list(open_list);
        delete_node_from_list(current, open_list);
        insert_node_to_list(current, close_list);

        Node *neighbor = create_node(current->x - 1, current->y);
        if(neighbor->x >= 0 && neighbor->y >= 0 &&
           map[neighbor->x][neighbor->y] == 0 &&
           !is_node_in_list(neighbor, close_list)) {
            int new_g = current->g + 1;
            if(!is_node_in_list(neighbor, open_list) ||
               new_g < neighbor->g) {
                neighbor->g = new_g;
                neighbor->h = distance(neighbor, end);
                neighbor->parent = current;

                if(!is_node_in_list(neighbor, open_list)) {
                    insert_node_to_list(neighbor, open_list);
                }
            }
            else {
                destroy_node(neighbor);
            }
        }
        else {
            destroy_node(neighbor);
        }

        //右
        neighbor = create_node(current->x + 1, current->y);
        if(neighbor->x < MAP_ROWS && neighbor->y < MAP_COLS &&
           map[neighbor->x][neighbor->y] == 0 &&
           !is_node_in_list(neighbor, close_list)) {
            int new_g = current->g + 1;
            if(!is_node_in_list(neighbor, open_list) ||
               new_g < neighbor->g) {
                neighbor->g = new_g;
                neighbor->h = distance(neighbor, end);
                neighbor->parent = current;

                if(!is_node_in_list(neighbor, open_list)) {
                    insert_node_to_list(neighbor, open_list);
                }
            }
            else {
                destroy_node(neighbor);
            }
        }
        else {
            destroy_node(neighbor);
        }

        //上
        neighbor = create_node(current->x, current->y - 1);
        if(neighbor->y >= 0 && neighbor->y < MAP_COLS &&
           map[neighbor->x][neighbor->y] == 0 &&
           !is_node_in_list(neighbor, close_list)) {
            int new_g = current->g + 1;
            if(!is_node_in_list(neighbor, open_list) ||
               new_g < neighbor->g) {
                neighbor->g = new_g;
                neighbor->h = distance(neighbor, end);
                neighbor->parent = current;

                if(!is_node_in_list(neighbor, open_list)) {
                    insert_node_to_list(neighbor, open_list);
                }
            }
            else {
                destroy_node(neighbor);
            }
        }
        else {
            destroy_node(neighbor);
        }

        //下
        neighbor = create_node(current->x, current->y + 1);
        if(neighbor->y < MAP_COLS && neighbor->y >= 0 &&
           map[neighbor->x][neighbor->y] == 0 &&
           !is_node_in_list(neighbor, close_list)) {
            int new_g = current->g + 1;
            if(!is_node_in_list(neighbor, open_list) ||
               new_g < neighbor->g) {
                neighbor->g = new_g;
                neighbor->h = distance(neighbor, end);
                neighbor->parent = current;

                if(!is_node_in_list(neighbor, open_list)) {
                    insert_node_to_list(neighbor, open_list);
                }
            }
            else {
                destroy_node(neighbor);
            }
        }
        else {
            destroy_node(neighbor);
        }
    }
}

void print_path(Node *node) {
    while(node->parent != NULL) {
        printf("(%d,%d)->", node->x, node->y);
        node = node->parent;
    }

    printf("(%d,%d)\n", node->x, node->y);
}

这是一个定义了常见数据类型的A *算法的骨架，需要根据您的具体问题进行进一步开发。