程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> C數據結構:棧 功能:遞推關系用棧和遞歸實現

C數據結構:棧 功能:遞推關系用棧和遞歸實現

編輯:關於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 }

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved