做了三種版本, 優化只是在輸出的方面優化而已, 請多多見諒
第一次非遞迴的東西
[非遞迴版+優化]
/**********************************************************************************/
/* Problem: a177 "逆逆向思考" from Trie */
/* Language: C */
/* Result: AC (648ms, 6352KB) on ZeroJudge */
/* Author: morris1028 at 2011-07-11 00:13:50 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
typedef struct TrieNode {
char c;
struct TrieNode *kid, *peer;
}TrieNode;
typedef struct Trie {
struct TrieNode *root;
}Trie;
typedef struct Stack {
struct Stack *prev;
struct TrieNode *now, *curr;
int dv;
char work;
}Stack;
void Trieinit(Trie*);
void InsTrie(Trie*, char s[]);
void TriePrint(TrieNode*, int);
void Trieinit(Trie *tree) {
tree->root = (TrieNode*)malloc(sizeof(TrieNode));
tree->root->c = ' ';
tree->root->kid = tree->root->peer = NULL;
}
void TriePrint(TrieNode *now, int dv) {
Stack *stack, *temp;
stack = (Stack*)malloc(sizeof(Stack));
stack->prev = NULL, stack->now = now, stack->dv = dv, stack->work = 0;
int a, Atop = 0;
char Ans[30005], flag, flag2;
while(stack != NULL) {
if(stack->work == 0) {
if(flag == 1) {
for(a = 0, flag = 0; a < stack->dv; a++)
Ans[Atop++] = ' ', Ans[Atop++] = ' ', Ans[Atop++] = ' ';
}
stack->curr = stack->now->kid, stack->work = 1;
Ans[Atop++] = '[', Ans[Atop++] = stack->now->c, Ans[Atop++] = ']';
}
flag2 = 0;
while(stack->curr != NULL) {
temp = (Stack*)malloc(sizeof(Stack));
temp->now = stack->curr, temp->prev = stack, temp->dv = stack->dv+1;
temp->work = 0;
stack->curr = stack->curr->peer;
stack = temp, flag2 = 1;
break;
}
if(flag2) continue;
if(stack->now->kid == NULL) Ans[Atop] = '\0', puts(Ans), flag = 1, Atop = 0;
temp = stack->prev, free(stack->now), free(stack), stack = temp;
}
}
void InsTrie(Trie *tree, char s[]) {
TrieNode *curr = tree->root, *prev = NULL, *temp, *p;
int a;
for(a = 0; s[a]; a++) {
p = curr, curr = p->kid, prev = NULL;
while(curr != NULL && curr->c < s[a]) {
if(curr->c < s[a]) prev = curr, curr = curr->peer;
}
if(curr == NULL) {
temp = (TrieNode*)malloc(sizeof(TrieNode));
temp->c = s[a], temp->kid = temp->peer = NULL;
if(prev == NULL) p->kid = temp;
else prev->peer = temp;
curr = temp;
}
else {
if(curr->c == s[a]) {continue;}
temp = (TrieNode*)malloc(sizeof(TrieNode));
temp->c = s[a], temp->kid = NULL;
if(curr == p->kid) p->kid = temp, temp->peer = curr;
else prev->peer = temp, temp->peer = curr;
curr = temp;
}
}
}
main() {
int N;
char s[10001];
while(scanf("%d", &N) == 1) {
Trie Tree;
Trieinit(&Tree);
getchar();
while(N--)
gets(s), InsTrie(&Tree, s);
TriePrint(Tree.root, 0);
}
return 0;
}
[遞迴版 + 優化]
/**********************************************************************************/
/* Problem: a177 "逆逆向思考" from Trie */
/* Language: C */
/* Result: AC (624ms, 6660KB) on ZeroJudge */
/* Author: morris1028 at 2011-07-10 22:04:56 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
typedef struct TrieNode {
char c;
struct TrieNode *kid, *peer;
}TrieNode;
typedef struct Trie {
struct TrieNode *root;
}Trie;
void Trieinit(Trie*);
void TrieFree(TrieNode*);
void InsTrie(Trie*, char s[]);
void TriePrint(TrieNode*, int);
void Trieinit(Trie *tree) {
tree->root = (TrieNode*)malloc(sizeof(TrieNode));
tree->root->c = ' ';
tree->root->kid = tree->root->peer = NULL;
}
void TrieFree(TrieNode *now) {
if(now == NULL) return;
TrieNode *curr = now->kid, *prev;
while(curr != NULL) {
prev = curr, curr = curr->peer;
TrieFree(prev);
}
free(now);
}
int flag, Atop = 0;
char Ans[30001];
void TriePrint(TrieNode *now, int dv) {
if(now == NULL) return;
TrieNode *curr = now->kid;
if(flag == 1) {
int a;
for(a = 0, flag = 0; a < dv; a++)
Ans[Atop++] = ' ', Ans[Atop++] = ' ', Ans[Atop++] = ' ';
}
Ans[Atop++] = '[', Ans[Atop++] = now->c, Ans[Atop++] = ']';
while(curr != NULL) {
TriePrint(curr, dv+1);
curr = curr->peer;
}
if(now->kid == NULL) Ans[Atop] = '\0', puts(Ans), flag = 1, Atop = 0;
}
void InsTrie(Trie *tree, char s[]) {
TrieNode *curr = tree->root, *prev = NULL, *temp, *p;
int a;
for(a = 0; s[a]; a++) {
p = curr, curr = p->kid, prev = NULL;
while(curr != NULL && curr->c < s[a])
prev = curr, curr = curr->peer;
if(curr == NULL) {
temp = (TrieNode*)malloc(sizeof(TrieNode));
temp->c = s[a], temp->kid = temp->peer = NULL;
if(prev == NULL) p->kid = temp;
else prev->peer = temp;
curr = temp;
}
else {
if(curr->c == s[a]) continue;
temp = (TrieNode*)malloc(sizeof(TrieNode));
temp->c = s[a], temp->kid = NULL;
if(curr == p->kid) p->kid = temp, temp->peer = curr;
else prev->peer = temp, temp->peer = curr;
curr = temp;
}
}
}
main() {
int N;
char s[10001];
while(scanf("%d", &N) == 1) {
Trie Tree;
Trieinit(&Tree);
getchar();
while(N--)
gets(s), InsTrie(&Tree, s);
flag = 0, TriePrint(Tree.root, 0);
TrieFree(Tree.root);
}
return 0;
}
[遞迴版(裸)]
/**********************************************************************************/
/* Problem: a177 "逆逆向思考" from Trie */
/* Language: C */
/* Result: AC (680ms, 6668KB) on ZeroJudge */
/* Author: morris1028 at 2011-07-10 22:01:11 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
typedef struct TrieNode {
char c;
struct TrieNode *kid, *peer;
}TrieNode;
typedef struct Trie {
struct TrieNode *root;
}Trie;
void Trieinit(Trie*);
void TrieFree(TrieNode*);
void InsTrie(Trie*, char s[]);
void TriePrint(TrieNode*, int);
void Trieinit(Trie *tree) {
tree->root = (TrieNode*)malloc(sizeof(TrieNode));
tree->root->c = ' ';
tree->root->kid = tree->root->peer = NULL;
}
void TrieFree(TrieNode *now) {
if(now == NULL) return;
TrieNode *curr = now->kid, *prev;
while(curr != NULL) {
prev = curr, curr = curr->peer;
TrieFree(prev);
}
free(now);
}
int flag, Atop = 0;
char Ans[30001];
void TriePrint(TrieNode *now, int dv) {
if(now == NULL) return;
TrieNode *curr = now->kid;
if(flag == 1) {
int a;
for(a = 0, flag = 0; a < dv; a++)
Ans[Atop++] = ' ', Ans[Atop++] = ' ', Ans[Atop++] = ' ';
}
Ans[Atop++] = '[', Ans[Atop++] = now->c, Ans[Atop++] = ']';
while(curr != NULL) {
TriePrint(curr, dv+1);
curr = curr->peer;
}
if(now->kid == NULL) Ans[Atop] = '\0', puts(Ans), flag = 1, Atop = 0;
}
void InsTrie(Trie *tree, char s[]) {
TrieNode *curr = tree->root, *prev = NULL, *temp, *p;
int a;
for(a = 0; s[a]; a++) {
p = curr, curr = p->kid, prev = NULL;
while(curr != NULL && curr->c < s[a]) {
if(curr->c < s[a]) prev = curr, curr = curr->peer;
}
if(curr == NULL) {
temp = (TrieNode*)malloc(sizeof(TrieNode));
temp->c = s[a], temp->kid = temp->peer = NULL;
if(prev == NULL) p->kid = temp;
else prev->peer = temp;
curr = temp;
}
else {
if(curr->c == s[a]) continue;
temp = (TrieNode*)malloc(sizeof(TrieNode));
temp->c = s[a], temp->kid = NULL;
if(curr == p->kid) p->kid = temp, temp->peer = curr;
else prev->peer = temp, temp->peer = curr;
curr = temp;
}
}
}
main() {
int N;
char s[10001];
while(scanf("%d", &N) == 1) {
Trie Tree;
Trieinit(&Tree);
while(N--)
scanf("%s", s), InsTrie(&Tree, s);
flag = 0, TriePrint(Tree.root, 0);
TrieFree(Tree.root);
}
return 0;
}
文章定位：
