Trie樹，題目不難，但還是WA了一次，沒有考慮后輸入的字符串是前輸入的字符串的前綴的情況，真是太粗心了。不過做了幾道Trie樹的題目以后，代碼寫得還是比較通用了，慢慢再改進吧

/*
* hdu1671/win.c
* Created on: 2011-8-19
* Author : ben
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define CHAR_NUM 10
#define BASE '0'

typedef struct Trie {
unsigned char isaend;
struct Trie * br[CHAR_NUM];
} Trie;

int flag;

Trie* newTrieNode() {
int i;
Trie* node = (Trie *) malloc(sizeof(Trie));
for (i = 0; i < CHAR_NUM; i++) {
node->br[i] = NULL;
}
node->isaend = 0;
return node;
}

void insert(Trie *root, char *str, int len) {
int i;
if (root->isaend) {
flag = 0;
}
if (len <= 0) {
root->isaend = 1;
for (i = 0; i < CHAR_NUM; i++) {
if(root->br[i]) {
flag = 0;
return ;
}
}
return;
}
i = (*str) - BASE;
if (!root->br[i]) {
root->br[i] = newTrieNode();
}
insert(root->br[i], str + 1, len - 1);
}

void destroy(Trie *root) {
int i;
for (i = 0; i < CHAR_NUM; i++) {
if (root->br[i] != NULL) {
destroy(root->br[i]);
}
}
free(root);
}

void work() {
Trie *root = newTrieNode();
int n;
char str[100];
scanf("%d", &n);
flag = 1;
while (n--) {
scanf("%s", str);
insert(root, str, strlen(str));
}
if (flag) {
puts("YES");
} else {
puts("NO");
}
destroy(root);
}

int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int T;
scanf("%d", &T);
while (T--) {
work();
}
return 0;
}

轉載于:https://www.cnblogs.com/moonbay/archive/2011/08/19/2146199.html

總結

以上是生活随笔為你收集整理的hdu 1671的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。