关于#c语言#的问题：输出这张地图上可以有多少个岛屿[目的]将实际问题转换成图，将地图中的土地和水看作图中顶点

岛屿数量统计
[问题描述] 在一张地图上，标注有土地和水域两个状态，其中相连接的土地可以连到一起，连到一起的土地可以建造一个岛屿。
[要求] 输入一张地图，输出这张地图上可以有多少个岛屿
[目的] 将实际问题转换成图，将地图中的土地和水看作图中顶点。运用DFS和BFS解决问题。
[ 实现提示 ]
可以用二维数组实现地图，用深度优先和广度优先两种算法实现

遇到的问题：运行代码出不了统计结果，求解决方法（队列要求用自己写的）

img

img

#include
#include
#include<assert.h>

typedef int DataType;    //便于修改数据类型 
//定义队列
typedef struct Queue
{
    DataType data;
    struct Queue* next;
}QNode;
//设置头尾指针
typedef struct PQueue
{
    QNode* head;
    QNode* tail;
}PQ;
//初始化队列
void InitQueue(PQ* pq)
{
    pq->head=NULL;
    pq->tail=NULL;
} 
//删除队列
void DeleQueue(PQ* pq)
{
    QNode* p=pq->head;
    while(p!=NULL)
    {
        QNode* temp=p->next;
        free(p);
        p=temp;
    }
} 
//队列尾部插入
void Push_Queue(PQ* pq,DataType data)     //确保队列已经存在 
{
    assert(pq);
    QNode* temp=(QNode*)malloc(sizeof(QNode));
    temp->data=data;
    if(pq->head==NULL)
    {
        pq->tail=temp;
        pq->head=pq->tail;
    }
    else
    {
        pq->tail->next=temp;
        pq->tail=temp;
    } 
}
//队列头部删除
void Pop_Queue(PQ* pq)          //确保队列已经存在且不为空 
{
    assert(pq);
    QNode* temp=pq->head->next;
    free(pq->head);
    pq->head=temp;
}
//判断是否队空
int EmptyQueue(PQ* pq)
{
    if(pq->head==NULL)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
//队首
DataType Front_Queue(PQ* pq)
{
    int f=EmptyQueue(pq);
    if(f)
    {
        printf("队列为空！！！\n");
        exit(-1);
    }
    return pq->head->data;
}
//队尾
DataType Rear_Queue(PQ* pq)
{
    int f=EmptyQueue(pq);
    if(f)
    {
        printf("队列为空！！！\n");
        exit(-1);
    }
    return pq->tail->data;
} 
 



//BFS实现 
void BFS(int **str,int row,int col,int x,int y)
{
    PQ q;
    InitQueue(&q);                       //初始化 
    str[row][col]=0;                    //将当前所在位置置0 
    int c=row*10+col;                   //队列中存储一个数字，将两个数字转化为一个存储
    Push_Queue(&q,c);                  //入队
    while(!EmptyQueue(&q))
    {
        c=Front_Queue(&q);
        Pop_Queue(&q);               //出队
        int i=c/10,j=c%10;                
        if(i>0 && str[i-1][j]==1)       //上
        {
            str[i-1][j]=0;
            Push_Queue(&q,(i-1)*10+j);
        }
        if(i>0 && str[i+1][j]==1)       //下 
        {
            str[i+1][j]=0;
            Push_Queue(&q,(i+1)*10+j);
        }
        if(i>0 && str[i][j-1]==1)       //左 
        {
            str[i][j-1]=0;
            Push_Queue(&q,i*10+j-1);
        }
        if(i>0 && str[i][j+1]==1)       //右 
        {
            str[i][j+1]=0;
            Push_Queue(&q,i*10+j+1);
        } 
    } 
}

DataType SumIslands1(int **str,int x,int y)
{
    if(!str || x==0 || y==0)      //判断边界 
    {
        return 0;
    }
    int i,j,n=0;    //n代表统计岛屿的个数 
    for(i=0;ifor(j=0;jif(str[i][j]==1)        //判断当前是否为1，若是则岛屿数量+1，并将其置0 
            {
                BFS(str,i,j,x,y);
                n++;
            }
        }
    }
    return n;
}




//DFS实现 
void DFS(int **str,int row,int col,int x,int y)
{
    str[row][col]=0;                    //将当前所在位置置0 
    if(row-1>=0&&str[row-1][col]==1){
        DFS(str,row-1,col,x,y);
    }
    if(row+1<=x-1&&str[row+1][col]==1){
        DFS(str,row+1,col,x,y);
    }
    if(col+1<=y-1&&str[row][col+1]==1){
        DFS(str,row,col+1,x,y);
    }
    if(col-1>=0&&str[row][col-1]==1){
        DFS(str,row,col-1,x,y);
    }

}

DataType SumIslands2(int **str,int x,int y)
{
    int i,j,n=0;    //n代表统计岛屿的个数
    if(!str || x == 0 || y==0)      //判断边界
    {
        return n;
    }
    for(i=0;ifor(j=0;jif(str[i][j]==1)        //判断当前是否为1，若是则岛屿数量+1，并将其置0
            {
                DFS(str,i,j,x,y);
                n++;
            }
        }
    }
    return n;
}





int main()
{
    int f=1,i,j,x,y;
    printf("------------岛屿数量统计系统------------\n");
    printf("请输入地图\n"); 
    printf("------------岛屿数量统计系统------------\n");
    printf("请分别输入地图大小x,y(空格键开)：");       //地图大小，用二维数组实现地图 
    scanf("%d%d",&x,&y); 
    DataType map[x][y];
    DataType *a[x];
    for(i=0;i[i]=map[i];   //a[i]=&map[i][0]
    }
    printf("请输入地图相对位置（1表示土地，0表示水域）：");
    for(i=0;ifor(j=0;j"%d",&map[i][j]);
        } 
    } 
    printf("------------岛屿数量统计系统------------\n");
    for(i=0;ifor(j=0;j"%d  ",map[i][j]);
        }
        printf("\n");
    }
    printf("------------岛屿数量统计系统------------\n");
    while(f)
    {
        printf("------------岛屿数量统计系统------------");
        printf("\n1.BFS统计结果；\n2.DFS统计结果。\n"); 
        printf("------------岛屿数量统计系统------------");
        printf("\n请输入对应序号（输入0结束运行）：");
        int choice;       //输入序号进入各功能 
        scanf("%d",&choice);
        switch(choice)
        {
            case 0:
                exit(0);
            case 1:
                printf("------------岛屿数量统计系统------------\n");
                printf("经计算，岛屿的数量：%d\n",SumIslands1(a,x,y));
                printf("------------岛屿数量统计系统------------");
                break;
            case 2:
                printf("------------岛屿数量统计系统------------\n");
                printf("经计算，岛屿的数量：%d\n",SumIslands2(a,x,y));
                printf("------------岛屿数量统计系统------------");
                break;
            default:
               printf("输入错误！！！请重新输入！！！\n");
               break;
        } 
    }
    return 0;
}

该回答引用GPTᴼᴾᴱᴺᴬᴵ
这份代码有一些错误：

  1. 在 BFS 函数中，在上下左右四个方向的判断中，都写成了 i>0 的形式，这应该改成 i>=0 才能正确访问到最上边和最左边的位置。
  2. 在 DFS 函数中，在上下左右四个方向的判断中，检查上和左方向的代码都写反了。
  3. 在 SumIslands1 函数中，统计岛屿数量的变量 n 的初始值应该是 0，而不是 1。
  4. 在调用 BFS 函数或 DFS 函数之前，应该先检查当前位置的值是否为 1，如果为 0 就不需要进行 BFS 或 DFS。

修改后的代码如下：

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

typedef int DataType;
typedef struct Queue {
    DataType data;
    struct Queue* next;
} QNode;
typedef struct PQueue {
    QNode* head;
    QNode* tail;
} PQ;

void InitQueue(PQ* pq) {
    pq->head = NULL;
    pq->tail = NULL;
}
void DeleQueue(PQ* pq) {
    QNode* p = pq->head;
    while (p != NULL) {
        QNode* temp = p->next;
        free(p);
        p = temp;
    }
}
void Push_Queue(PQ* pq, DataType data) {
    assert(pq);
    QNode* temp = (QNode*)malloc(sizeof(QNode));
    temp->data = data;
    if (pq->head == NULL) {
        pq->tail = temp;
        pq->head = pq->tail;
    }
    else {
        pq->tail->next = temp;
        pq->tail = temp;
    }
}
void Pop_Queue(PQ* pq) {
    assert(pq);
    QNode* temp = pq->head->next;
    free(pq->head);
    pq->head = temp;
}
int EmptyQueue(PQ* pq) {
    if (pq->head == NULL) {
        return 1;
    }
    else {
        return 0;
    }
}
DataType Front_Queue(PQ* pq) {
    int f = EmptyQueue(pq);
    if (f) {
        printf("队列为空！！！\n");
        exit(-1);
    }
    return pq->head->data;
}
DataType Rear_Queue(PQ* pq) {
    int f = EmptyQueue(pq);
    if (f) {
        printf("队列为空！！！\n");
        exit(-1);
    }
    return pq->tail->data;
}

void BFS(int **str, int row, int col, int x, int y) {
    PQ q;
    InitQueue(&q);
    str[row][col] = 0;
    int c = row * 10 + col;
    Push_Queue(&q, c);
    while (!EmptyQueue(&q)) {
        c = Front_Queue(&q);
        Pop_Queue(&q);
        int i = c / 10, j = c % 10;
        if (i >= 1 && str[i - 1][j] == 1) {
            str[i - 1][j] = 0;
            Push_Queue(&q, (i - 1) * 10 + j);
        }
        if (i < x - 1//DFS实现
void DFS(int **str,int row,int col,int x,int y)
{
str[row][col]=0; //将当前所在位置置0
if(row-1>=0&&str[row-1][col]==1){
DFS(str,row-1,col,x,y);
}
if(row+1<=x-1&&str[row+1][col]==1){
DFS(str,row+1,col,x,y);
}
if(col+1<=y-1&&str[row][col+1]==1){
DFS(str,row,col+1,x,y);
}
if(col-1>=0&&str[row][col-1]==1){
DFS(str,row,col-1,x,y);
}
}

DataType SumIslands2(int **str,int x,int y)
{
if(!str || x==0 || y==0) //判断边界
{
return 0;
}
int i,j,n=0; //n代表统计岛屿的个数
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
{
if(str[i][j]==1) //判断当前是否为1，若是则岛屿数量+1，并将其置0
{
DFS(str,i,j,x,y);
n++;
}
}
}
return n;
}

int main()
{
int i,j,x,y;
DataType p=NULL;
printf("输入地图的行数和列数：");
scanf("%d%d",&x,&y);
p=(DataType)malloc(sizeof(DataType*)x);
for(i=0;i<x;i++)
{
p[i]=(DataType)malloc(sizeof(DataType)*y);
}
printf("请输入地图：\n");
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
{
scanf("%d",&p[i][j]);
}
}
printf("使用BFS算法计算岛屿的数量为：%d\n",SumIslands1(p,x,y));
printf("使用DFS算法计算岛屿的数量为：%d\n",SumIslands2(p,x,y));
for(i=0;i<x;i++)
{
free(p[i]);
}
free(p);
return 0;
}