2011-07-11 08:40:10Morris
鏈結 Stack (堆疊)
原本用遞迴寫堆疊就可以了, 但是有些電腦的遞迴深度一超過某一個限制
馬上就會出現遞迴溢滿, stack overflow
此時手動的 stack 就不得不出現了
做手動的堆疊的時候, 必須將所有的狀態變數, 塞進 stack 的變數中
我不是什麼大牛, 僅僅提供我的寫法
那麼我就給一個範例
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;
}
上面是最原先的程式碼, 在紅色的部分, 你可以很明顯的發現到,
我使用內建的遞迴, 來實踐 stack, 現在需要更改成手動的
typedef struct Stack {
struct Stack *prev;
struct TrieNode *now, *curr;
int dv;
char work;
}Stack;
我需要一個 Stack 的結構, 但是我不知道有多深, 因此採用 linked list
struct Stack *prev; //堆疊退回來的時候使用
struct TrieNode *now, *curr; //原本出現在遞迴中的變數, 塞進 stack 變數中
int dv; //原本出現在遞迴中的變數, 塞進 stack 變數中
char work; //工做到哪裡, 遞迴中, 分成遞迴前的宣告 0, 遞迴後的處理 1
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), stack = temp;
}
}
第一次改寫 遞迴 成 手動 stack
若寫得不好, 請多多見諒
馬上就會出現遞迴溢滿, stack overflow
此時手動的 stack 就不得不出現了
做手動的堆疊的時候, 必須將所有的狀態變數, 塞進 stack 的變數中
我不是什麼大牛, 僅僅提供我的寫法
那麼我就給一個範例
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;
}
上面是最原先的程式碼, 在紅色的部分, 你可以很明顯的發現到,
我使用內建的遞迴, 來實踐 stack, 現在需要更改成手動的
typedef struct Stack {
struct Stack *prev;
struct TrieNode *now, *curr;
int dv;
char work;
}Stack;
我需要一個 Stack 的結構, 但是我不知道有多深, 因此採用 linked list
struct Stack *prev; //堆疊退回來的時候使用
struct TrieNode *now, *curr; //原本出現在遞迴中的變數, 塞進 stack 變數中
int dv; //原本出現在遞迴中的變數, 塞進 stack 變數中
char work; //工做到哪裡, 遞迴中, 分成遞迴前的宣告 0, 遞迴後的處理 1
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), stack = temp;
}
}
第一次改寫 遞迴 成 手動 stack
若寫得不好, 請多多見諒
上一篇：Trie (單詞查找樹)