Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

实在没办法了，谁帮我看看我的为什么ＷＡ

Posted by hanhui8301 at 2017-05-24 23:24:52 on Problem 1002

我的代码是字符串保存完整形式的电话号码，以平衡二叉树结构存储不同的号码结点，以便快速查找和插入，我的查找函数就是插入函数，自测100000 条输入运行时间不超过0.3s，随机样本，一直没有发现哪里有问题，但提交总是ＷＡ， 谁帮我看一下，万分感谢了 
ＧＣＣ 代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TELEPHONE_LEN 10
#define MAX(a, b) ((a) > (b) ? (a) : (b))
struct telephone_num_s
{
	char telephone[TELEPHONE_LEN];
	int count;
    int depth;
	struct telephone_num_s *left;
	struct telephone_num_s *right;
};
char *format_telephone_num(char *input, char *telephone)
{
	int i = 0;
	int j = 0;
	int len = strlen(input);
	memset(telephone, 0, TELEPHONE_LEN);
	for(i = 0; i < len && j < TELEPHONE_LEN; i++)
	{
		switch(input[i])
		{
			case '0':
			case '1':
				telephone[j] = input[i];
				break;
			case 'A':
			case 'B':
			case 'C':
			case '2':
				telephone[j] = '2';
				break;
			case 'D':
			case 'E':
			case 'F':
			case '3':
				telephone[j] = '3';
				break;
			case 'G':
			case 'H':
			case 'I':
			case '4':
				telephone[j] = '4';
				break;
			case 'J':
			case 'K':
			case 'L':
			case '5':
				telephone[j] = '5';
				break;
			case 'M':
			case 'N':
			case 'O':
			case '6':
				telephone[j] = '6';
				break;
			case 'P':
			case 'R':
			case 'S':
			case '7':
				telephone[j] = '7';
				break;
			case 'T':
			case 'U':
			case 'V':
			case '8':
				telephone[j] = '8';
				break;
			case 'W':
			case 'X':
			case 'Y':
			case '9':
				telephone[j] = '9';
				break;
			default:
				break;
		}
		if(telephone[j])
		{
			j++;
		}
		if(j == 3)
		{
			telephone[j] = '-';
			j++;
		}
	}
	return telephone;
}
int get_tree_depth(struct telephone_num_s *num_list)
{
    if(!num_list)
    {
        return 0;
    }
    return num_list->depth;
}
struct telephone_num_s *search_from_list(struct telephone_num_s *num_list, int *dup_count, char *telephone)
{
		if(!num_list)
		{
				struct telephone_num_s *new_node = malloc(sizeof(struct telephone_num_s));
                if(!new_node)
                {
                    return NULL;
                }
                memset(new_node, 0, sizeof(struct telephone_num_s));
                new_node->count = 1;
                new_node->depth = 1;
                strcpy(new_node->telephone, telephone);
                return new_node;
		}
		else 
		{
			int cmp = strcmp(num_list->telephone, telephone);
			if(!cmp)
			{
                if(num_list->count == 1)
                {
                    (*dup_count)++;
                }
                num_list->count++;
				return num_list;
			}
			else if(cmp > 0)
			{
                if(!num_list->left)
                {
                    struct telephone_num_s *new_node = malloc(sizeof(struct telephone_num_s));
                    if(!new_node)
                    {
                        return num_list;
                    }
                    memset(new_node, 0, sizeof(struct telephone_num_s));
                    new_node->count = 1;
                    new_node->depth = 1;
                    strcpy(new_node->telephone, telephone);
                    num_list->left = new_node;
                    if(num_list->depth < 2)
                    {
                        num_list->depth = 2;
                    }
                    return num_list;
                }
                else
                {
				    struct telephone_num_s *tmp_node = search_from_list(num_list->left, dup_count, telephone);
                    int left_depth = get_tree_depth(tmp_node);
                    int right_depth = get_tree_depth(num_list->right);
                    if(left_depth >= right_depth+2)
                    {
                        struct telephone_num_s *left = tmp_node;
                        int ll_depth = get_tree_depth(left->left);
                        int lr_depth = get_tree_depth(left->right);
                        if(ll_depth > lr_depth)
                        {
                            num_list->left = left->right;
                            left->right = num_list;
                            int lr_depth = get_tree_depth(num_list->left);
                            num_list->depth = MAX(right_depth, lr_depth) + 1;
                            left->depth = MAX(ll_depth, num_list->depth) + 1;
                            num_list = left;
                        }
                        else
                        {
                            tmp_node = left->right;
                            left->right = tmp_node->left;
                            left->depth = MAX(ll_depth, 
                                    get_tree_depth(left->right)) + 1;
                            tmp_node->left = left;
                            num_list->left = tmp_node->right;
                            num_list->depth = MAX(right_depth, get_tree_depth(num_list->left)) + 1;
                            tmp_node->right = num_list;
                            tmp_node->depth = MAX(left->depth, num_list->depth) + 1;
                            num_list = tmp_node;
                        }
                    }
                    else
                    {
                        num_list->left = tmp_node;
                        if(num_list->depth - 1 < tmp_node->depth)
                        {
                            num_list->depth = tmp_node->depth + 1;
                        }
                    }
                    return num_list;
                }
			}
			else
			{
                if(!num_list->right)
                {
                    struct telephone_num_s *new_node = malloc(sizeof(struct telephone_num_s));
                    if(!new_node)
                    {
                        return num_list;
                    }
                    memset(new_node, 0, sizeof(struct telephone_num_s));
                    new_node->count = 1;
                    new_node->depth = 1;
                    strcpy(new_node->telephone, telephone);
                    num_list->right = new_node;
                    if(num_list->depth < 2)
                    {
                        num_list->depth = 2;
                    }
                    return num_list;
                }
                else
                {
				    struct telephone_num_s *tmp_node = search_from_list(num_list->right, dup_count, telephone);
                    int right_depth = get_tree_depth(tmp_node);
                    int left_depth = get_tree_depth(num_list->right);
                    if(right_depth >= left_depth+2)
                    {
                        struct telephone_num_s *right = tmp_node;
                        int rr_depth = get_tree_depth(right->right);
                        int rl_depth = get_tree_depth(right->left);
                        if(rr_depth > rl_depth)
                        {
                            struct telephone_num_s *right_left = tmp_node->left;
                            num_list->right = right->left;
                            num_list->depth = MAX(left_depth, rl_depth) + 1;
                            right->left = num_list;
                            right->depth = MAX(num_list->depth, rr_depth) + 1;
                            num_list = right;
                        }
                        else
                        {
                            tmp_node = right->left;
                            right->left = tmp_node->right;
                            right->depth = MAX(rr_depth, 
                                    get_tree_depth(right->left)) + 1;
                            tmp_node->right = right;
                            num_list->right = tmp_node->left;
                            num_list->depth = MAX(left_depth, 
                                    get_tree_depth(num_list->right)) + 1;
                            tmp_node->left = num_list;
                            tmp_node->depth = MAX(right->depth, num_list->depth) + 1;
                            num_list = tmp_node;
                        }
                    }
                    else
                    {
                        num_list->right = tmp_node;
                        if(num_list->depth - 1 < tmp_node->depth)
                        {
                            num_list->depth = tmp_node->depth + 1;
                        }
                    }
                    return num_list;
                }
            }

		}
}
void call_back(struct telephone_num_s *num_list)
{
    if(num_list->count > 1)
    {
        printf("%s %d\n", num_list->telephone, num_list->count);
    }
    return;
}
void traverse_telephone_tree(struct telephone_num_s *num_list, void (*call_back)(struct telephone_num_s *))
{
    if(!num_list)
    {
        return;
    }
    else
    {
        traverse_telephone_tree(num_list->left, call_back);
        call_back(num_list);
        traverse_telephone_tree(num_list->right, call_back);
        return;
    }
}
int main()
{
	int num = 0;
	char inputline[32] = {0};
	char *line = inputline;
	struct telephone_num_s *num_list = NULL;
	int index = 0;
	int currlen = 0;
	int dup_count = 0;
	int input_count = 0;

	scanf("%d", &num);
	while(input_count < num)
	{
		char telephone[TELEPHONE_LEN] = {0};
		scanf("%s", line);
		format_telephone_num(line, telephone);
        //printf("get telephone %s input count %d\n", telephone, input_count);
		num_list = search_from_list(num_list, &dup_count, telephone);
		input_count++;
		memset(inputline, 0, 32);
	}
	if(dup_count == 0)
	{
		printf("No dumplicates.\n");
	}
	else
	{
        traverse_telephone_tree(num_list, call_back);
	}		
    //printf("dup_count %d\n", dup_count);
	return 0;

}

Followed by:

Re:实在没办法了，谁帮我看看我的为什么ＷＡ (10491) hanhui8301 2017-05-25 01:05:01

Post your reply here:

User ID:
Password:
Title:

Content:

> 我的代码是字符串保存完整形式的电话号码，以平衡二叉树结构存储不同的号码结点，以便快速查找和插入，我的查找函数就是插入函数，自测100000 条输入运行时间不超过0.3s，随机样本，一直没有发现哪里有问题，但提交总是ＷＡ， 谁帮我看一下，万分感谢了 
> ＧＣＣ 代码
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> #define TELEPHONE_LEN 10
> #define MAX(a, b) ((a) > (b) ? (a) : (b))
> struct telephone_num_s
> {
> 	char telephone[TELEPHONE_LEN];
> 	int count;
>     int depth;
> 	struct telephone_num_s *left;
> 	struct telephone_num_s *right;
> };
> char *format_telephone_num(char *input, char *telephone)
> {
> 	int i = 0;
> 	int j = 0;
> 	int len = strlen(input);
> 	memset(telephone, 0, TELEPHONE_LEN);
> 	for(i = 0; i < len && j < TELEPHONE_LEN; i++)
> 	{
> 		switch(input[i])
> 		{
> 			case '0':
> 			case '1':
> 				telephone[j] = input[i];
> 				break;
> 			case 'A':
> 			case 'B':
> 			case 'C':
> 			case '2':
> 				telephone[j] = '2';
> 				break;
> 			case 'D':
> 			case 'E':
> 			case 'F':
> 			case '3':
> 				telephone[j] = '3';
> 				break;
> 			case 'G':
> 			case 'H':
> 			case 'I':
> 			case '4':
> 				telephone[j] = '4';
> 				break;
> 			case 'J':
> 			case 'K':
> 			case 'L':
> 			case '5':
> 				telephone[j] = '5';
> 				break;
> 			case 'M':
> 			case 'N':
> 			case 'O':
> 			case '6':
> 				telephone[j] = '6';
> 				break;
> 			case 'P':
> 			case 'R':
> 			case 'S':
> 			case '7':
> 				telephone[j] = '7';
> 				break;
> 			case 'T':
> 			case 'U':
> 			case 'V':
> 			case '8':
> 				telephone[j] = '8';
> 				break;
> 			case 'W':
> 			case 'X':
> 			case 'Y':
> 			case '9':
> 				telephone[j] = '9';
> 				break;
> 			default:
> 				break;
> 		}
> 		if(telephone[j])
> 		{
> 			j++;
> 		}
> 		if(j == 3)
> 		{
> 			telephone[j] = '-';
> 			j++;
> 		}
> 	}
> 	return telephone;
> }
> int get_tree_depth(struct telephone_num_s *num_list)
> {
>     if(!num_list)
>     {
>         return 0;
>     }
>     return num_list->depth;
> }
> struct telephone_num_s *search_from_list(struct telephone_num_s *num_list, int *dup_count, char *telephone)
> {
> 		if(!num_list)
> 		{
> 				struct telephone_num_s *new_node = malloc(sizeof(struct telephone_num_s));
>                 if(!new_node)
>                 {
>                     return NULL;
>                 }
>                 memset(new_node, 0, sizeof(struct telephone_num_s));
>                 new_node->count = 1;
>                 new_node->depth = 1;
>                 strcpy(new_node->telephone, telephone);
>                 return new_node;
> 		}
> 		else 
> 		{
> 			int cmp = strcmp(num_list->telephone, telephone);
> 			if(!cmp)
> 			{
>                 if(num_list->count == 1)
>                 {
>                     (*dup_count)++;
>                 }
>                 num_list->count++;
> 				return num_list;
> 			}
> 			else if(cmp > 0)
> 			{
>                 if(!num_list->left)
>                 {
>                     struct telephone_num_s *new_node = malloc(sizeof(struct telephone_num_s));
>                     if(!new_node)
>                     {
>                         return num_list;
>                     }
>                     memset(new_node, 0, sizeof(struct telephone_num_s));
>                     new_node->count = 1;
>                     new_node->depth = 1;
>                     strcpy(new_node->telephone, telephone);
>                     num_list->left = new_node;
>                     if(num_list->depth < 2)
>                     {
>                         num_list->depth = 2;
>                     }
>                     return num_list;
>                 }
>                 else
>                 {
> 				    struct telephone_num_s *tmp_node = search_from_list(num_list->left, dup_count, telephone);
>                     int left_depth = get_tree_depth(tmp_node);
>                     int right_depth = get_tree_depth(num_list->right);
>                     if(left_depth >= right_depth+2)
>                     {
>                         struct telephone_num_s *left = tmp_node;
>                         int ll_depth = get_tree_depth(left->left);
>                         int lr_depth = get_tree_depth(left->right);
>                         if(ll_depth > lr_depth)
>                         {
>                             num_list->left = left->right;
>                             left->right = num_list;
>                             int lr_depth = get_tree_depth(num_list->left);
>                             num_list->depth = MAX(right_depth, lr_depth) + 1;
>                             left->depth = MAX(ll_depth, num_list->depth) + 1;
>                             num_list = left;
>                         }
>                         else
>                         {
>                             tmp_node = left->right;
>                             left->right = tmp_node->left;
>                             left->depth = MAX(ll_depth, 
>                                     get_tree_depth(left->right)) + 1;
>                             tmp_node->left = left;
>                             num_list->left = tmp_node->right;
>                             num_list->depth = MAX(right_depth, get_tree_depth(num_list->left)) + 1;
>                             tmp_node->right = num_list;
>                             tmp_node->depth = MAX(left->depth, num_list->depth) + 1;
>                             num_list = tmp_node;
>                         }
>                     }
>                     else
>                     {
>                         num_list->left = tmp_node;
>                         if(num_list->depth - 1 < tmp_node->depth)
>                         {
>                             num_list->depth = tmp_node->depth + 1;
>                         }
>                     }
>                     return num_list;
>                 }
> 			}
> 			else
> 			{
>                 if(!num_list->right)
>                 {
>                     struct telephone_num_s *new_node = malloc(sizeof(struct telephone_num_s));
>                     if(!new_node)
>                     {
>                         return num_list;
>                     }
>                     memset(new_node, 0, sizeof(struct telephone_num_s));
>                     new_node->count = 1;
>                     new_node->depth = 1;
>                     strcpy(new_node->telephone, telephone);
>                     num_list->right = new_node;
>                     if(num_list->depth < 2)
>                     {
>                         num_list->depth = 2;
>                     }
>                     return num_list;
>                 }
>                 else
>                 {
> 				    struct telephone_num_s *tmp_node = search_from_list(num_list->right, dup_count, telephone);
>                     int right_depth = get_tree_depth(tmp_node);
>                     int left_depth = get_tree_depth(num_list->right);
>                     if(right_depth >= left_depth+2)
>                     {
>                         struct telephone_num_s *right = tmp_node;
>                         int rr_depth = get_tree_depth(right->right);
>                         int rl_depth = get_tree_depth(right->left);
>                         if(rr_depth > rl_depth)
>                         {
>                             struct telephone_num_s *right_left = tmp_node->left;
>                             num_list->right = right->left;
>                             num_list->depth = MAX(left_depth, rl_depth) + 1;
>                             right->left = num_list;
>                             right->depth = MAX(num_list->depth, rr_depth) + 1;
>                             num_list = right;
>                         }
>                         else
>                         {
>                             tmp_node = right->left;
>                             right->left = tmp_node->right;
>                             right->depth = MAX(rr_depth, 
>                                     get_tree_depth(right->left)) + 1;
>                             tmp_node->right = right;
>                             num_list->right = tmp_node->left;
>                             num_list->depth = MAX(left_depth, 
>                                     get_tree_depth(num_list->right)) + 1;
>                             tmp_node->left = num_list;
>                             tmp_node->depth = MAX(right->depth, num_list->depth) + 1;
>                             num_list = tmp_node;
>                         }
>                     }
>                     else
>                     {
>                         num_list->right = tmp_node;
>                         if(num_list->depth - 1 < tmp_node->depth)
>                         {
>                             num_list->depth = tmp_node->depth + 1;
>                         }
>                     }
>                     return num_list;
>                 }
>             }
> 
> 		}
> }
> void call_back(struct telephone_num_s *num_list)
> {
>     if(num_list->count > 1)
>     {
>         printf("%s %d\n", num_list->telephone, num_list->count);
>     }
>     return;
> }
> void traverse_telephone_tree(struct telephone_num_s *num_list, void (*call_back)(struct telephone_num_s *))
> {
>     if(!num_list)
>     {
>         return;
>     }
>     else
>     {
>         traverse_telephone_tree(num_list->left, call_back);
>         call_back(num_list);
>         traverse_telephone_tree(num_list->right, call_back);
>         return;
>     }
> }
> int main()
> {
> 	int num = 0;
> 	char inputline[32] = {0};
> 	char *line = inputline;
> 	struct telephone_num_s *num_list = NULL;
> 	int index = 0;
> 	int currlen = 0;
> 	int dup_count = 0;
> 	int input_count = 0;
> 
> 	scanf("%d", &num);
> 	while(input_count < num)
> 	{
> 		char telephone[TELEPHONE_LEN] = {0};
> 		scanf("%s", line);
> 		format_telephone_num(line, telephone);
>         //printf("get telephone %s input count %d\n", telephone, input_count);
> 		num_list = search_from_list(num_list, &dup_count, telephone);
> 		input_count++;
> 		memset(inputline, 0, 32);
> 	}
> 	if(dup_count == 0)
> 	{
> 		printf("No dumplicates.\n");
> 	}
> 	else
> 	{
>         traverse_telephone_tree(num_list, call_back);
> 	}		
>     //printf("dup_count %d\n", dup_count);
> 	return 0;
> 
> }

Home Page Go Back To top