DFS非递归问题不知道逻辑错在那了
# include<stdio.h>
# include<stdlib.h>
typedef struct E{
    int place;   //顶点下标
    struct E*Pnext;//指针指向连接下一个边
}E;
typedef struct{
    char data[4]; //存放顶点信息
    E *Phead;//链表头
}V;
typedef struct{
    V*v; //顶点
    char *vertex;//顶点数据
    int Vlen, Elen;//顶点长度//边长度
}G;
typedef struct{//模拟栈
    int top;
    E**STACK;
}Stack;
void found(G *g,int**sign);//创建
int LocateVex(G *g, char *t);//顶为顶点函数;
void dfs(G*g, int*sign);
void dfs_f(G*g, int*sign, int v);
void dfs2(G*g, int*sign, int y);
void printfG(G*g);
int main(void)
{
    G g;
    int *sign;
    found(&g,&sign);
    printfG(&g);
    //dfs(&g, sign);
    dfs_f(&g, sign, 0);
    system("pause");
    return 0;
}
void found(G *g,int**sign)
{
    int i, j, k; E*p; char v1[5], v2[5];
    printf("输入你要创建多少个顶点多少个边比如(3,3):\n");
    scanf("%d,%d", &g->Vlen, &g->Elen);
    if (!((*sign)= (int*)malloc(sizeof(int)*(g->Vlen))))exit;//动态创建数组
    if (!(g->v = (V*)malloc(sizeof(V)*(g->Vlen))))exit;//动态创建边因为不懂用户需要多少个顶点和边
    if (!(g->vertex = (char*)malloc(sizeof(char)*(g->Vlen))))exit;//动态创建顶点数据
    printf("输入你要输入的顶点数据比如 A B C D E:\n");
    for (i = 0; i < g->Vlen; i++){
        scanf("%s", g->v[i].data);
        (*sign)[i] = 0;
        g->v[i].Phead = NULL;
        g->vertex[i] = 0;
        g->vertex[i] = g->v[i].data[0];
    }
    printf("顶点数据为%s\n", g->vertex);
    printf("输入无向图在第A和B的边比如(a b代表a到b有边):\n");
    for (k = 0; k < g->Elen; k++){//因为是无向图所有A到B有边 B到A也应该有边
        scanf("%s%s", v1, v2);
        i = LocateVex(g, v1);
        j = LocateVex(g, v2);
        if (!(p = (E*)malloc(sizeof(E))))exit;
        p->place = j;
        p->Pnext = g->v[i].Phead;
        g->v[i].Phead = p;
        if (!(p = (E*)malloc(sizeof(E))))exit;
        p->place = i;
        p->Pnext = g->v[j].Phead;
        g->v[j].Phead = p;
    }
}
int LocateVex(G *g, char *t){
    int i;
    for (i = 0; i < g->Elen; i++){
        if (t[0] == g->v[i].data[0]){
            return i;
        }
    }
    printf("没有找的匹配项:");
    exit;
}
void dfs(G*g, int*sign){
    int i;
    for (i = 0; i < g->Vlen; i++){
        if (sign[i] != 1){
            dfs2(g,sign,i);
        }
    }
}
void dfs2(G*g, int*sign, int y){
    sign[y] = 1;
    E*P = g->v[y].Phead;
    printf("深度遍历为:%c\n", g->vertex[y]);
    while (P != NULL){
        if (P->place > 0 && sign[P->place] != 1){
            dfs2(g, sign, P->place);
        }
        else{
            P = P->Pnext;
        }
    }
}
void printfG(G*g){
    int i;
    for (i = 0; i < g->Vlen; i++){
        E*P = g->v[i].Phead;
        while (P != NULL){
            printf("%5d", P->place+1 );
            P = P->Pnext;
        }
        printf("\n");
    }
}
void dfs_f(G*g, int*sign, int v){//前面的没什么问题主要这断没有达到深度非递归的算法我好头疼
    Stack S; E*P;
    S.STACK = (E**)malloc(sizeof(E*)*g->Vlen);
    S.top = -1;
    printf("深度遍历为:%c", g->vertex[v]);
    sign[v] = 1;
    S.STACK[++S.top] = g->v[v].Phead;
    while (S.top != -1){
        P = S.STACK[S.top];
        while (P != NULL){
            if (sign[P->place] != 1){
                printf("深度遍历为:%c", g->vertex[P->place]);
                sign[P->place] = 1;
                S.STACK[++S.top] = P;
            }
            else{
                P = P->Pnext;       
            }

        }
        S.STACK[S.top--] = NULL;
    }



}


1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐