题解 | #火车进站#

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char list[6000][10]; //出站
int stack[10];       //车站
int train[10];       //火车
int kind = 0;
int n;
//用回溯算法遍历可能情况,保存为字符串数组,用qsort进行排序
void DFS(int pos, int top, int index);
int cmp_char(const void *_a, const void *_b);
int main()
{
  while (scanf("%d", &n) != EOF)
  {
    for (int i = 0; i < n; i++)
    {
      scanf("%d", &train[i]);
    }
    int top = -1;
    int index = 0;
    DFS(0, top, index);
    qsort(list + 1, kind, sizeof(list[1]), cmp_char);

    for (int i = 1; i <= kind; i++)
    {
      for (int j = 0; j < n; j++)
      {
        printf("%c ", list[i][j]);
      }
      printf("\n");
    }
  }

  return 0;
}

void DFS(int pos, int top, int index) //出站数组中位置,站顶,火车数组位置
{
  if (pos == n)
  {
    kind++;
    for (int i = 0; i < n; i++)
    {
      list[kind][i] = list[0][i];
    }
    return;
  }
//进站
  if (index < n)
  {
    stack[++top] = train[index++];
    DFS(pos, top, index);
    top--;
    index--;
  }
//出站
  if (top >= 0)
  {
    list[0][pos++] = stack[top--] + '0';
    DFS(pos, top, index);
    stack[++top] = list[0][--pos] - '0';
  }
}

int cmp_char(const void *_a, const void *_b)
{
  char *a = (char *)_a;
  char *b = (char *)_b;
  return strcmp(a, b);
}