C数据结构：栈 功能：递推关系用栈和递归实现
手工带入数据具体体会过程，易于理解并选择栈来处理递归问题
2. m = 3, n = 4时候 如果栈大小只为100的时候，是不够用的
（这个开始发现不了 是后面突然想到的，复杂度的问题）
01 typedef int Type;
02 #include <Stack.h>
03 #include <stdio.h>
04 #include <stdlib.h>
05 #define ERROR 0
06 #define OK 1
07 www.2cto.com
08 int Akm_Recur(int m, int n)//对于递归来说 本身就是一个压栈的过程，直接易懂
09 {
10 if (m == 0)
11 return n + 1;
12 else if (n == 0)
13 Akm_Recur(m - 1, 1);
14 else
15 Akm_Recur(m - 1, Akm_Recur(m, n - 1));
16 }
17
18 int Akm(int m, int n)//建立空栈 数据入栈用于保存 先入后出符合条件
19 {
20 int result = 0;
21 int len = 0;
22 Stack S;
23
24 Creat(&S);
25
26 do
27 {
28 while (m)
29 {
30 while (n)
31 {
32 Push(&S, m - 1);
33 len ++;
34 n -= 1;
35 }
36 n = 1;
37 m -= 1;
38 }
39
40 if (!Isempty(S))
41 {
42 Pop(&S, &m);
43 n += 1;
44 }
45 }while((m != 0) || (Isempty(S) != OK));
46
47 return n + 1;
48 }
49
50 int main()
51 {
52 int m, n;
53 int result;
54
55 while (1)
56 {
57
58 title: test Akm(3_27)
59 scanf("%d%d", &m, &n);
60 result = Akm_Recur(m, n);
61 printf("%d ", result);
62 result = Akm(m, n);
63 printf("%d/n", result);
64
65 }
66 return 0;
67 }
view sourceprint?001 #include <stdio.h>
002 #include <malloc.h>
003 #include <stdlib.h>
004 #define MAX 10000
005 #define IN 10
006 #define ERROR 0
007 #define OK 1
008
009 typedef struct stack
010 {
011 Type *base;
012 Type *top;
013 int size;
014 }Stack, *LinkStack;
015
016
017 void Creat(LinkStack S)
018 {
019 S->base = (Type *)malloc(sizeof(Stack) * MAX);
020 if (!S->base)
021 exit(0);
022 S->top = S->base;
023 S->size = MAX;
024 }
025
026 int Push(LinkStack S, Type c)
027 {
028 if (S->top - S->base >= S->size)
029 {
030 S->base = (Type *)malloc(sizeof(Stack) * (S->size + IN));
031 if (!S->base)
032 return ERROR;
033 S->top = S->base + S->size;
034 S->size += IN;
035 }
036 *(S->top++) = c;
037 return OK;
038 }
039
040 int Pop(LinkStack S, Type *c)
041 {
042 if (S->top == S->base)
043 return ERROR;
044 *c = *(--S->top);
045 return OK;
046 }
047
048 int Gettop(Stack S, Type *c)
049 {
050 if (S.top == S.base)
051 return ERROR;
052 *c = *(S.top - 1);
053 return OK;
054 }
055
056 int Isempty(Stack S)
057 {
058 if (S.top == S.base)
059 return OK;
060 return ERROR;
061 }
062
063
064 void Clear(LinkStack S)
065 {
066 S->top = S->base;
067 }
068
069 void Destroy(LinkStack S)
070 {
071 free(S->base);
072 }
073
074 int PrintT(Stack S)//栈顶输出
075 {
076 Type e;
077 if (Isempty(S))
078 return ERROR;
079 while (S.top != S.base)
080 {
081 if (Pop(&S, &e))
082 printf("%c ", e);
083 }
084 putchar('/n');
085 return OK;
086 }
087
088 int PrintB(Stack S)//从栈底输出
089 {
090 Type e;
091 Stack SD;
092
093
094 if (Isempty(S))
095 return ERROR;
096
097 Creat(&SD);
098 while (S.top != S.base)
099 {
100 if (Pop(&S, &e))
101 Push(&SD, e);
102 }
103 PrintT(SD);
104 Destroy(&SD);
105 return OK;
106 }
107
108 int Reserve(Stack S, LinkStack SR)//栈的倒置
109 {
110 Type e;
111 if (Isempty(S))
112 return ERROR;
113 while (!Isempty(S))
114 {
115 if (Pop(&S, &e))
116 Push(SR, e);
117 }
118 return OK;
119 }