问题:
从文本文件中提取出树的邻接表,求指定结点到指定结点的路径。
需求:
我已经完成从文本文件中提取出树的邻接表,但是不知道指定结点到指定结点的如何求解。
请求代码!(堆栈实现)
比如b2到g3无路径,a1到g3的路径为a1-》d2-》g3
以下是文本文件的内容:
以下是我目前已经完成的代码:
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define MAXSIZE 3
#define MAXNODESIZE 10
//ADT
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;
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++;
}
//头节点初始化完成,接下来将子节点连接到头结点
t = 0;
int size = strlen(str);
for (int i = 0; i < cnt && t < size; i++) //这里需要做两个限制:1.遍历字符串的指针t不能超过字符串长度 2.头结点个数有限制
{
while (t < size && str[t] != '/') //先跳过头节点
t++;
t++;
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++;
}
string[j] = '\0'; //为该截取出来的字符串添加终止符
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 = 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 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];
for (int i = 0; i < MAXNODESIZE; i++) //对头节点全部赋\0
{
for (int t = 0; t < MAXSIZE; t++)
{
tree[i].data[t] = '\0';
}
}
char str[100];
fp = fopen("Tree.txt", "r");
if (fp == NULL)
{
printf("文件打开失败\n");
exit(0);
}
FillInText(str, fp);
fclose(fp);
printf("");
puts(str);
create(tree, str, getCount(str));
return 0;
}