全排列（C语言）数据结构

全排列
【全排列（C语言）】输入一个数n，输出1-n的全排列，这里我们将其形象化，举个例子，加入有编号1、2、3的3张扑克牌分别放在3个盒子里面，并且每个盒子有且只能放一张扑克牌。那么一共有多少种放法呢？

好，第一步：小张手拿三张扑克牌，首先走到1号盒子面前，我们规定一个顺序，每次到一个盒子时，都先放1号，再放2号，最后放3号，于是小张走到一号盒子前，将1号扑克牌放在了1号盒子中。
接下来，小张将2号扑克牌放在了2号盒子里面；顺着，将3号扑克牌放在了3号盒子里面。
然后来到了4号盒子千，其实扑克牌已经放完了。那么前三个盒子就产生了一个排列“123”。
现在当然没有完，于是小张取回3号盒子中的3号扑克牌，当小张想要再往3号盒子里面放别的扑克牌的时候，却发现手中只有3号扑克牌，没有别的选择。于是小张只好回到2号盒子面前。
小张回到2号盒子面前后，收回了2号扑克牌。现在小张手里面有两张扑克牌，分别是2号和3号扑克牌。按照之前的规定，现在需要往2号盒子里放3号扑克牌（上一次放的是2号扑克牌）。放好以后小张又向后走一步，再次来到3号盒子面前，将手中仅剩的2号扑克牌放入了3号盒子，又一次来到4号盒子前。
当然了，并没有4号盒子。我的意思是每次来到4号盒子的时候，我们会发现已经产生了一个新的排列。所以，当来到4号盒子，直接输出前3个盒子的扑克牌就好了。
还有一点就是我们需要标记那些牌已经用过了，那些牌还没有被用过。
还有一点就是你可以发现，我们在这里采取了递归的方式。好，来看代码：

int a[10], book[100], n; void dfs(int step) { int i; if (step == n + 1)//如果站在n+1个盒子面前，则表示前n个盒子已经放好了扑克牌 {//输出前n个盒子中扑克牌的编号 for (i = 1; i <= n; i++) { printf("%d", a[i]); } printf("\n"); return; } for (i = 1; i <= n; i++) { if (book[i] == 0)//判断扑克牌i是否还在手上 { a[step] = i; //将i号扑克牌放入第step个盒子中 book[i] = 1; //将book[i]设为1，表示i号扑克牌已经不在手上 dfs(step + 1); //函数递归 book[i] = 0; //一定要将刚才尝试的扑克牌收回，才能进行下一步尝试 } } return; }int main() { scanf("%d", &n); //注意我给n的取值范围是9（包括9）以内， dfs(1); //首先站在1号小盒子面前 system("pause"); }