用链表和迭代的思维实现的汉诺塔，循环次数太多，效率有些差，但总是比递归要好一些的。
思路是：在任何条件下，需要被移动的圆盘以及其被移动的目标位置都是可知且唯一的，所以可以通过迭代的方式实现。
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
//非递归实现的汉诺塔 #include<stdio.h> #include<stdlib.h> #define A 0 #define B 1 #define C 2 struct pan { int no; int from; struct pan* next; }; int main() { struct pan *p_pan[3], *p_temp; int i = 0, number, destintion_temp, total, latest_moved = -1, which_can_move,k; int is_complete(struct pan*, int); int count(struct pan*); int can_move(struct pan**, int); int move(struct pan**, int, int); printf("请输入个数（默认从A经由B移动到C）：\n"); scanf("%d", &number); for (i = 0; i<3; i++) { p_pan[i] = (struct pan*)malloc(sizeof(struct pan)); p_pan[i]->next = NULL; p_pan[i]->no = 0; p_pan[i]->from = A; } for (i = number; i>0; i--) { p_temp = (struct pan*)malloc(sizeof(struct pan)); *p_temp = *p_pan[0]; p_temp->no = i; p_temp->next = p_pan[0]; p_pan[0] = p_temp; printf("%d\n", p_pan[0]->no); } destintion_temp = C; while (1) { if (is_complete(p_pan[2], number)) break; for (i = 0; i<3; i++) { if (p_pan[i]->no<1) continue; which_can_move = can_move(p_pan, i); if (i == latest_moved) { continue; } if (which_can_move == 4) { continue; } if (p_pan[i]->no == 1) { total = count(p_pan[i])-1; //printf("%d\n", total); if (latest_moved != -1) { if(total%2) which_can_move=latest_moved; else { for(k=0;k<3;k++) { if(k==latest_moved||k==i) continue; else { which_can_move=k; } } } } else { if(total%2) which_can_move = destintion_temp; else { destintion_temp=B; which_can_move = destintion_temp; } } move(p_pan, i, which_can_move); latest_moved=which_can_move; } else { move(p_pan, i, which_can_move); latest_moved=which_can_move; } } } } int is_complete(struct pan* p_pan, int n) { int i; struct pan *temp = p_pan; for (i = 1; i <= n; i++) { if (temp == NULL&&i!=n) return 0; if (temp->no != i) return 0; temp = temp->next; } return 1; } int can_move(struct pan** p_pan, int n) { int i; for (i = 0; i <= 2; i++) { if (i == n) continue; if ((p_pan[n]->no)<(p_pan[i]->no)&&p_pan[n]->from != i) return i; else if(p_pan[i]->no<1&&p_pan[n]->from != i) return i; } return 4; } int count(struct pan* p_pan) { int sum = 0; struct pan* temp = p_pan; for(sum=1;temp->no==sum;sum++) temp = temp->next; return sum; } int move(struct pan** p_pan, int i, int destintion) { struct pan* temp; int j; printf("Move No.%d from %c to %c. \n", p_pan[i]->no, i + 65, destintion + 65); temp = p_pan[i]; p_pan[i] = p_pan[i]->next; temp->next = p_pan[destintion]; temp->from = i; p_pan[destintion] = temp; for (j = 0; j<3; j++) { if (j == destintion) continue; p_pan[j]->from = -1; } return 0; } |