寻找给定电话号码中是否有包含关系的程序
这是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;
}