Yester07 2022-06-29 11:53 采纳率: 48.5%

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

``````#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;
}
``````
本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

• 系统已结题 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代码