注册 登录
编程论坛 数据结构与算法

寻找给定电话号码中是否有包含关系的程序

li362490567 发布于 2015-10-03 10:33, 2065 次点击
这是OJ的一个题目:输入n个电话号码。判断n个电话号码,是否有包含关系,比如n=2,输入1769  和176954123 。则存在包含关系,输出NO
若输入1769 和176542234 则不存在包含关系,输出YES  我的代码 在编译器上跑没问题,但放到OJ上,出现在runtime error
以下是代码:
#include<stdio.h>
#include<string.h>
#define MAX 10
/*用字典树进行遍历*/
typedef struct Trienode  
{
    int nCount;// 创建了结点,ncount变为1,字符串的最后一个结点,ncount变为负值
    struct Trienode* next[MAX];//代表0到9 的指针,指向下一结点
}TrieNode;

TrieNode Memory[1000000];
int allocp = 0;//使用Memory数组的循环数
TrieNode* CreateTrieNode()//创建一个新的结点
{
    int i;
    TrieNode *p;
    p = &Memory[allocp++];
    p->nCount = 1;
    for (i = 0; i<MAX; i++)
    {
        p->next[i] = NULL;
    }
    return p;
}
int InsertTrie(TrieNode**pRoot,char *s)
{
    int i,k;
    TrieNode*p;
    if(!(p=*pRoot))    //若指向根结点的指针为NULL,创建根结点
    {
        p=*pRoot=CreateTrieNode();
    }
    i=0;
    while(s[i])          //插入结点
    {
     k=s[i++]-'0';
     if(p->next[k]==NULL) p->next[k]=CreateTrieNode();
     else (p->next[k]->nCount)++;
     p=p->next[k];
     if(p->nCount<0)   //若当前字符串比存在树中的字符串长,判断树中字符串是否存在当前字符串中
         return -1;
    }
     p->nCount=-1002; //字符串最后一个结点的标志
     for(i=0;i<MAX;i++)
        if(p->next[i]!=NULL) //若当前字符串比存在树中的字符串短,判断当前字符串是否包含在前面字符串中
        return 1;
        return 0;// 当前字符串和存在树中的字符串互不包含
}
int main(void)
{
    int num, i,j;
    scanf("%d",&num); //输入 要输入的电话号码的个数
    getchar();
    char pnum[num][50]; //存储电话号码
    TrieNode *pRoot; //指向根结点的指针
    pRoot=NULL;
    while (num != 0)
    {
        for (i = 0; i < num; i++)
            gets(pnum[i]);  //输入电话号码
        for (i = 0; i < num;i++)
            {
                j=InsertTrie(&pRoot,pnum[i]); // 将电话号码存入树中,并比较
             if(j==1||j==-1)
             {
                 printf("NO\n");  //若存在包含关系,输出NO
                 break;
             }
            }
            if(j==0)
                printf("YES\n");  //不存在包含关系 输出YES
        scanf("%d",&num);
        getchar();
    }
    return 0;
}
0 回复
1