[数据结构与算法]使用树结构存储医院楼房结构

题目描述：

? ? ? 该结构应该是通过读取文件definition.txt文件创建，格式如“hospital 10 floor”，表示hospital有10层floor。将树形结构创建后，可以读取queries.txt中的查询完成对应的操作。操作有两种：“whatis connecting_corridor”意思是查询connecting_corridor有几个子部件。

输出示例：

Part long_corridor subparts are:

21 patient_room

Part floor subparts are:

4 wing

1 central_lobby

“howmany floor hospital”是查询hospital有几个floor

输出示例：

Hospital has 10 floor

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//根孩子结点链表
typedef struct subNode{
    struct TreeNode *subTreeNode; //该链表中所含数据结构为树结点
    struct subNode *nextNode;  //下一孩子结点指针
}LinkList;

//树结点结构定义
typedef struct TreeNode
{
    char name[25];  //结点名
    int num;  //含此结点的数量
    LinkList *firstChild; //存放孩子结点的链表
    struct TreeNode *parentNode; //双亲节点指针
} TreeNode, *Node;

//常量定义
#define LINE 1024
#define CMDLEN 7
#define HOWMANY "howmany"
#define WHATIS "whatis"

//全局变量
char temp[LINE]; //存放字符串分割后结果

//函数声明
Node buildTree();
Node createNewNode();
void findNode(Node root, char *name, Node * result);
void execute(Node root);
void assignment(char *content, Node tempNode, Node root);
void whatIsOperation(Node root, char content[]);
void howManyOperation(Node root, char content[]);
char* strCopy(int startIndex, int endIndex, char source[]);



//测试函数
int main()
{
    Node root = buildTree();
    execute(root);
    return 0;
}


//读取文件，识别问题
void execute(Node root)
{
    int endIndex; //存放问题类型字符串截止位置
    FILE *file = fopen("queries.txt", "r");//读取问题文档
    char content[LINE];
    while (!feof(file))
    {
        fgets(content, LINE, file);//得到文档中一行
        char cmd[CMDLEN + 1];
        for (int i = 0; content[i] != "\n"; i++)//得到问题类型
        {
            if (content[i] == ' ')
            {
                endIndex = i;
                break;
            }
        }
        strcpy(cmd, strCopy(0, endIndex-1, content));

        if (strcmp(cmd, WHATIS) == 0)//判断问题提问方式
        {
            whatIsOperation(root, content);
        }
        else if (strcmp(cmd, HOWMANY) == 0)
        {
            howManyOperation(root, content);
        }
    }
}

//创建树
Node buildTree()
{
    FILE *file = fopen("definitions.txt", "r");
    Node root = createNewNode(); //创建根结点
    char content[LINE];
    fgets(content, LINE, file);
    assignment(content, root, root);
    Node tempNode; //创建根结点的第一个子结点
    tempNode = createNewNode();
    assignment(content, tempNode, root);

    while (!feof(file)) //读取文件其他行创建其它结点
    {
        fgets(content, LINE, file);
        tempNode = createNewNode();
        assignment(content, tempNode, root);
    }
    return root;
}


//递归先序遍历树查找某结点，name为待查找结点的名字，result返回查找后结果
void findNode(Node root, char *name, Node *result)
{
    LinkList *tempNode = root->firstChild;
    if (strcmp(root->name, name) == 0)
    {
        *result = root;
        return;
    }
    else
    {
        while(tempNode != NULL)
        {
            findNode(tempNode->subTreeNode, name, result);//递归调用
            tempNode = tempNode->nextNode;
        }
    }
}


//为结点赋值，并将结点加入树中 content为文件中一行，tempNode为待赋值结点
void assignment(char *content, Node tempNode, Node root)
{
    int result[2]; //记录分割位置数组
    int k = -1;
    for (int i = 0; content[i] != '\n' && content[i] != '\0'; i++)
    {
        if (content[i] == ' ')
        {
            //得到分割字符串位置
            result[++k] = i;
        }
    }

    if(strcmp(tempNode->name, root->name) == 0){//根节点
        strcpy(tempNode->name,strCopy(0, result[0]-1, content));
    } else {//其他结点

        strcpy(tempNode->name, strCopy(result[1] + 1, strlen(content) - 2, content));//读取文件得到name及num值并赋值
        char num[4];
        strcpy(num, strCopy(result[0] + 1, result[1] - 1, content));
        tempNode->num = atoi(num);
        Node father;
        char name[25];
        strcpy(name, strCopy(0, result[0] - 1, content));

        findNode(root, name, &father); //遍历树找到其根节点，将根节点赋值给tempNode
        tempNode->parentNode = father;

        //将tempNode加入到树中（即将tempNode插入到根节点孩子链表中）
        if(father->firstChild == NULL){ //若孩子链表为空，tempNode作为头结点
            father->firstChild = (LinkList*)malloc(sizeof(LinkList));
            father->firstChild->subTreeNode = tempNode;
            father->firstChild->nextNode = NULL;
        } else { //若孩子链表不为空，将tempNode插入链表尾
            LinkList *t = father->firstChild;
            while(t->nextNode != NULL){
                t = t->nextNode;
            } //找到表尾位置
            LinkList * k = (LinkList*)malloc(sizeof(LinkList));
            k->subTreeNode = tempNode;
            k->nextNode = NULL;
            t->nextNode = k; //插入该节点
        }

        /*
        //测试树是否创建成功
        printf(tempNode->parentNode->name);
        printf("\t");
        printf("%d", tempNode->num);
        printf("\t");
        printf(tempNode->name);
        printf("\n");
        */
    }
}


//创建树结点
Node createNewNode()
{
    Node node = (Node)malloc(sizeof(TreeNode));
    //对树结点值初始化
    node->name[0] = '\0';
    node->num = 0;
    node->firstChild = NULL;
    return node;
}

//字符串分割函数,返回分割后得到字符串，startIndex, endIndex为起始位置，source中存放待分割字符串
char* strCopy(int startIndex, int endIndex, char source[])
{
    for (int i = startIndex; i <= endIndex; i++)
    {
        temp[i - startIndex] = source[i];
    }
    temp[endIndex - startIndex + 1] = '\0';

    return temp;
}

//回答节点有几个子部件
void whatIsOperation(Node root, char content[])
{
    char name[25]; //得到根结点名字
    int startIndex = strlen(WHATIS) + 1;
    for (int i = startIndex; i <= strlen(content) - 2; i++)
    {
        name[i - startIndex] = content[i];
    }
    name[strlen(content) - startIndex - 1] = '\0';

    Node subNode;
    findNode(root, name, &subNode);
    printf(" %s subparts are\n", subNode->name);
    LinkList * tempNode = subNode->firstChild;
    if(tempNode == NULL){
        printf("None\n");
        return;
    }
    while(tempNode != NULL){
        printf("%d %s\n", tempNode->subTreeNode->num, tempNode->subTreeNode->name);
        tempNode = tempNode->nextNode;
    }
}

//查询某结构所含子部件数量
void howManyOperation(Node root, char content[])
{
    int sum ; //存放所含数量
    int space[2]; //存放需要分割的位置
    int k = -1;
    for (int i = 0; content[i] != '\n' && content[i] != '\0'; i++)
    {
        if (content[i] == ' ')
        {
            space[++k] = i;
        }
    }

    char name[25]; //得到祖宗结点名字
    strcpy(name,strCopy(space[1] + 1, strlen(content) - 2, content));
    char subName[25]; //得到子孙结点名字
    strcpy(subName,strCopy(space[0] + 1, space[1] - 1 , content));

    Node subRoot = NULL; //得到祖宗结点
    findNode(root, name, &subRoot);
    Node subNode = NULL; //得到子孙结点
    findNode(subRoot, subName, &subNode);

    int state = -1; //判断是否含该子孙标志位
    if(subNode != NULL){ //该祖宗结点不含该子孙
        state = 1;
    }
    if (state == -1) //该祖宗结点不含该子孙
    {
        char name[25];
        strcpy(name, subRoot->name);
        name[0] = toupper(name[0]);
        printf("%s has %d %s\n\n", name, 0, subNode->name);
    }
    else //含该子孙
    {
        sum = subNode->num;
        Node temp = subNode->parentNode;
        while(strcmp(temp->name, subRoot->name) != 0){ //向上查询其双亲，直到查询到该祖先结点
              sum = sum*(temp->num);
              temp = temp->parentNode;
              }
        char name[25];
        strcpy(name, subRoot->name);
        name[0] = toupper(name[0]);
        printf("%s has %d %s\n", name, sum, subNode->name);
    }
}

学习内容：

1. 树存储结构如何定义 -----双亲，孩子表示法

2.如何递归遍历树查找某一特定结点

3.C语言中的部分字符串操作函数（strcpy、strcmp）、字符串作为函数返回值时用法（如何返回字符串--全局变量、作为参数传入等）、如何自己写字符串分割函数