Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

树的做法,贴个代码

Posted by lizimeng at 2016-02-24 13:12:34 on Problem 2503
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct item
{
    char a[11],b[11];            //a存储方言,b存储英文
    struct item*lchild,*rchild;
};

void ruin(struct item*root)
{
    if(root!=NULL)
    {
        ruin(root->lchild);
        ruin(root->rchild);
        free(root);
    }
}

int main()
{
    int i,j,t;
    struct item*head,*p,*r;
    char s[50];

    //创建根节点
    head = (struct item*)malloc(sizeof(struct item));
    head->lchild = NULL;
    head->rchild = NULL;
    gets(s);
    if(s[0]!='\0')
    {
        for(i=0;s[i]!=' ';i++)
            head->b[i] = s[i];
        head->b[i] = '\0';
        j = i+1;
        for(i=0;s[j]!='\0';i++,j++)
            head->a[i] = s[j];
        head->a[i] = '\0';
    }

    //建立字典树
    gets(s);
    while(s[0]!='\0')
    {
        //做节点r
        r = (struct item*)malloc(sizeof(struct item));
        r->lchild = NULL;
        r->rchild = NULL;
        for(i=0;s[i]!=' ';i++)
            r->b[i] = s[i];
        r->b[i] = '\0';
        j = i + 1;
        for(i=0;s[j]!='\0';i++,j++)
            r->a[i] = s[j];
        r->a[i] = '\0';

        //将结点r添加到字典树
        p = head;
        while(1)
        {
            if(strcmp(r->a,p->a)<0)
            {
                if(p->lchild!=NULL)
                    p = p->lchild;
                else
                {
                    p->lchild = r;
                    break;
                }
            }
            else
            {
                if(p->rchild!=NULL)
                    p = p->rchild;
                else
                {
                    p->rchild = r;
                    break;
                }
            }
        }
        //读入下一行
        gets(s);
    }

    //进行查询
    while(gets(s)!=NULL)
    {
        p = head;
        while(p!=NULL)
        {
            t = strcmp(s,p->a);
            if(t==0)
            {
                puts(p->b);
                break;
            }
            else if(t<0)
                p = p->lchild;
            else
                p = p->rchild;
        }
        if(p==NULL)
            printf("eh\n");
    }

    //销毁二叉树
    ruin(head);

    return 0;
}

//用的二叉排序树,400多ms

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator