Yester07 2022-06-29 11:53 采纳率: 48.5%
浏览 82
已结题

对邻接表进行深度优先遍历

问题:
将文本文件中的文本数据提取,并以此建立邻接表,再进行树的深度优先搜索。
遇到的问题:
在创建邻接表的时候,感觉逻辑有点混乱。
我先是把邻接表的头节点都先加载出来,再将子节点接到头节点上。
子节点接到头结点这个环节,感觉有点乱。
文本文件内容:

img

目标:
将该内容变成存储内的邻接表

img

并对该邻接表进行深度优先遍历

求指教!
以下为我的屎山代码XD(目前程序还是有问题的,问题在子节点连接到头节点那一块):

#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define MAXSIZE 20
typedef struct Branch
{
    int index;
    struct Branch* next;
}branch;

typedef struct Tnode
{
    char data[MAXSIZE];
    branch* first;
}tnode;

void create(tnode tree[],char str[],int cnt)  //创建邻接表
{
    int j = 0, t = 0;
    char string[MAXSIZE];
    branch* p;
    printf("一共有%d个头节点\n", cnt);
    for (int i = 0; i < cnt; i++)
    {
        j = 0;
        while (str[t] != '/')  //遇到/就开始找换行符\n,并跳转到下一行,录入下一行头节点
        {
            tree[i].data[j] = str[t];
            j++;
            t++;
        }
        tree[i].data[j] = '\0';  //为tree[i].data加入终止符
        tree[i].first = NULL;
        while (str[t] != '\n'&&str[t]!=EOF)  //跳转至下一行,准备录下一行的头节点
            t++;
        t++;
        puts(tree[i].data);  //将该行的头节点中的串打印出来以检验头节点的串是否成功录入
    }
    //头节点初始化完成,接下来将子节点连接到
    t = 0;
    for (int i = 0; i < cnt; i++)
    {
        while (str[t] != '/')  //先跳过头节点
            t++;
        t++;
        p = (branch*)malloc(sizeof(branch));
        while (t != '\n')
        {
            j = 0;
            for (int n = 0; n < strlen(string); n++)//字符串清空
                string[n] = '\0';
            while (str[t] != '/')//将字符串截取出来
            {
                string[j] = str[t];
                j++;
                t++;
            }
            //此时str[t]=='/'
            string[j] = '\0';
            printf("子串为:");
            puts(string);
            for (int n = 0; n < cnt; n++)
            {
                if (!strcmp(tree[n].data, string))
                    p->index = n;
            }
            p->next = tree[i].first;//将p接入头节点中
            tree[i].first = p;
            t++;  //使t指向下一个单词开头
            p = (branch*)malloc(sizeof(branch));
        }
        //此时t指向\n
        t++;  //将t指向下一行第一个字符
    }
}

void DFS(tnode tree[])  //对邻接表进行深度优先遍历
{

}

void visit(tnode* node,char str[])  //对结点进行访问
{
    if (!strcmp(node->data, str))
    {
        printf("该结点存在!");
    }
}

void FillInText(char str[], FILE* fp)  //将文件中内容传入str中
{
    char ch;
    int length = 0;
    ch = fgetc(fp);
    while (ch != EOF)
    {
        str[length] = ch;
        ch = fgetc(fp);
        length++;
    }
    str[length] = '\0';
}

int getCount(char str[])  //获取邻接表头节点个数
{
    int cnt = 0;
    for (int i = 0; i < strlen(str); i++)
    {
        if (str[i] == '\n')
            cnt++;
    }
    return cnt + 1;
}

int main()
{
    FILE* fp;
    tnode tree[MAXSIZE];
    char ch, str[100];
    fp = fopen("test.txt", "r");
    if (fp == NULL)
    {
        printf("文件打开失败\n");
        exit(0);
    }
    FillInText(str, fp);
    printf("文件中的文本内容为:\n");
    puts(str);
    create(tree, str,getCount(str));
    fclose(fp);
    return 0;
}

  • 写回答

2条回答 默认 最新

  • 广大菜鸟 2022-06-29 14:02
    关注
    #define _CRT_SECURE_NO_WARNINGS
    #include "stdio.h"
    #include "stdlib.h"
    #include "string.h"
    #define MAXSIZE 3
    #define MAXNODESIZE 10
    
    typedef struct Branch
    {
        int index;
        struct Branch* next;
    }branch;
    
    typedef struct Tnode
    {
        char data[MAXSIZE]="\0";
        branch* first;
    }tnode;
    
    void create(tnode tree[], char str[], int cnt)  //创建邻接表
    {
        int j = 0, t = 0;
       
    
        //printf("一共有%d个头节点\n", cnt);
        for (int i = 0; i < cnt; i++)
        {
            j = 0;
            while (str[t] != '/')  //遇到/就开始找换行符\n,并跳转到下一行,录入下一行头节点
            {
                tree[i].data[j] = str[t];
                j++;
                t++;
            }
            tree[i].data[j] = '\0';  //为tree[i].data加入终止符
            tree[i].first = NULL;
            while (str[t] != '\n' && str[t] != EOF)  //跳转至下一行,准备录下一行的头节点
                t++;
            t++;
            //puts(tree[i].data);  //将该行的头节点中的串打印出来以检验头节点的串是否成功录入
        }
        //头节点初始化完成,接下来将子节点连接到
        t = 0;
        int size = strlen(str);
        for (int i = 0; i < cnt && t < size; i++)
        {
            while (t < size && str[t] != '/')  //先跳过头节点
                t++;
            t++;
            // p = (branch*)malloc(sizeof(branch));
            while (t < size &&str[t] != '\n' && str[t] != '\0') // 这里是bug1: t是数字, 也要可能是空了
            {
                j = 0;
                char string[MAXSIZE];
                while (t < size && str[t] != '/' && str[t] != '\n')//将字符串截取出来 bug2:不能处理换行符
                {
                    string[j] = str[t];
                    j++;
                    t++;
                }
                //此时str[t]=='/'
                string[j] = '\0';
                //printf("子串为:");
                //puts(string);
                int target = -1;
                for (int n = 0; n < cnt; n++)
                {
                    if (!strcmp(tree[n].data, string)) {
                        target = n;
                        break;
                    }
                }
                branch* p = tree[i].first;
                //bug3:插入方式不正确,应该后插入
                if (p == NULL) {
                    p = (branch*)malloc(sizeof(branch));
                    p->index = target;
                    p->next = NULL;
                    tree[i].first = p;
                }
                else {
                    while (p->next != NULL) {
                        p = p->next;
                    }
                    p->next = (branch*)malloc(sizeof(branch));
                    p->next->index = target;
                    p->next->next = NULL;
                }
                if (t >= size ||str[t] == '\n') {
                    break;
                }
                t++;  //使t指向下一个单词开头 
            }
            //此时t指向\n
            t++;  //将t指向下一行第一个字符
        }
    }
    
    void dfs(int visited[], tnode tree[], int v);
    
    void DFS(tnode tree[])  //对邻接表进行深度优先遍历
    {
        int cnt = 0;
        int visited[MAXNODESIZE];
      
        for (int i = 0; i < MAXNODESIZE; i++) {
            if (strlen(tree[i].data)>=2){
                cnt++;
            }
            else {
                break;
            }
        }
        for (int i = 0; i < cnt; i++) visited[i] = 0;
        
        for (int i = 0; i < cnt; i++) {
            if (!visited[i]) {
                //没有遍历过
                dfs(visited, tree,   i);
            }
        }
    }
    void dfs(int visited[], tnode tree[],   int v) {
        tnode t = tree[v];
        puts(t.data);
        visited[v] = 1;
     
        for (branch* w = t.first; w != NULL; w = w->next) {
            if (!visited[w->index]) { 
                dfs(visited, tree, w->index);
            }
        }
    
    }
     
    
    void visit(tnode* node, char str[])  //对结点进行访问
    {
        if (!strcmp(node->data, str))
        {
            printf("该结点存在!");
        }
    }
    
    void FillInText(char str[], FILE* fp)  //将文件中内容传入str中
    {
        char ch;
        int length = 0;
        ch = fgetc(fp);
        while (ch != EOF)
        {
            str[length] = ch;
            ch = fgetc(fp);
            length++;
        }
        str[length] = '\0';
    }
    
    int getCount(char str[])  //获取邻接表头节点个数
    {
        int cnt = 0;
        for (int i = 0; i < strlen(str); i++)
        {
            if (str[i] == '\n')
                cnt++;
        }
        return cnt + 1;
    }
    
    int main()
    {
        FILE* fp;
        tnode tree[MAXNODESIZE];
        
        char ch, str[100];
        fp = fopen("C:\\Users\\Lenovo\\Desktop\\1\\test.txt", "r");
        if (fp == NULL)
        {
            printf("文件打开失败\n");
            exit(0);
        }
        FillInText(str, fp);
        fclose(fp);
        //printf("文件中的文本内容为:\n");
        //puts(str);
        create(tree, str, getCount(str)); 
        DFS(tree);
        return 0;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 7月7日
  • 已采纳回答 6月29日
  • 创建了问题 6月29日

悬赏问题

  • ¥15 esp8266控制共阳极wrgb灯板无法关闭所有led灯
  • ¥100 python读取速度问题
  • ¥15 stm32f407使用DMA问题
  • ¥15 您好 这个API接口该怎么弄 网站搭建好了 API也有 现在就不知道该怎么填写API 不知道怎么用
  • ¥88 用uniapp写一个多端的程序,用到高德地图,用高德的JSAPI吗?
  • ¥20 关于#c++#的问题:水果店管理系统
  • ¥30 dbLinq最新版linq sqlite
  • ¥20 对D盘进行分盘之前没有将visual studio2022卸载掉,现在该如何下载回来
  • ¥15 完成虚拟机环境配置,还有安装kettle
  • ¥15 2024年全国大学生数据分析大赛A题:直播带货与电商产品的大数据分析 问题5. 请设计一份优惠券的投放策略,需要考虑优惠券的数量、优惠券的金额、投放时间段和投放商品种类等因素。求具体的python代码