杭電ACM1671――Phone List~~字典樹
來源：程序員人生 發布時間：2015-06-04 07:35:43 閱讀次數：2524次
這1題，也是簡單的字典樹的利用，不過這里不是字母，而是數字。
題目的意思是判斷輸入的字符串會不會是其他字符串的前綴。就是這么的簡單。
下面是AC的代碼：
#include <iostream>
#include <cstring>
using namespace std;
class node //結點的結構體
{
public:
node* P[10];
};
node* root; //定義根節點
int ans; //葉子結點數
void insert(char* str) //插入操作的函數
{
int len = strlen(str);
node *q, *p;
q = root;
for(int i = 0; i < len; i++)
{
int id = str[i] - '0';
if(q->P[id] == NULL) //該位置不存在，new1個
{
p = new node;
for(int j = 0; j < 10; j++)
p->P[j] = NULL;
q->P[id] = p;
q = q->P[id];
}
else //存在，直接等于他的后繼
q = q->P[id];
}
}
void fun(node *a) //遞歸找有多少個葉子結點
{
int flag = 0;
for(int i = 0; i < 10; i++)
{
if(a->P[i] != NULL)
{
flag = 1;
break;
}
}
if(!flag) //該結點是葉子結點，ans++
{
ans++;
return;
}
for(int j = 0; j < 10; j++)
if(a->P[j] != NULL)
fun(a->P[j]);
}
void dele(node *a) //刪除操作的函數，也是遞歸完成
{
for(int i = 0; i < 10; i++)
if(a->P[i] != NULL)
dele(a->P[i]);
delete a;
}
int main()
{
// freopen("data.txt", "r", stdin);
int t, n;
char str[15];
cin >> t;
while(t--)
{
root = new node;
ans = 0;
for(int j = 0; j < 10; j++) //初始化根節點的指針數組P
root->P[j] = NULL;
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> str;
insert(str); //插入
}
fun(root); //算葉子結點數目
if(ans == n) //葉子結點等于輸入的n 的個數，則YES
cout << "YES" << endl;
else //否則NO
cout << "NO" << endl;
dele(root); //刪除
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
