#include <cstdio>
#include <stdlib.h>

typedef struct LinkNode {
    int data;
    struct LinkNode *next;
} LinkNode;

typedef struct {
    LinkNode *front, *rear;
} LinkQueue;

// 链队列的初始化（带头结点）
bool InitQueue(LinkQueue &Q)
{
    Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));

    if (Q.front == NULL || Q.rear == NULL) return false;

    Q.front->next = NULL;

    return true;
}

/*
// 链队列的初始化（带头结点）
bool InitQueue(LinkQueue &Q)
{
    Q.front = NULL;
    Q.rear = NULL;
}
*/

// 判空
bool isEmpty(LinkQueue Q)
{
    if (Q.front == Q.rear) return true;

    else return false;
}

/*
// 判空（不带头结点）
bool isEmpty(LinkQueue Q)
{
    if (Q.front == NULL) return true;

    else return false;
}
*/

// 入队（带头结点）
bool EnQueue(LinkQueue &Q, int e)
{
    LinkNode *s = (LinkNode *) malloc(sizeof(LinkNode));
    if (s == NULL) return false;

    s->data = e;
    s->next = NULL;
    Q.rear->next = s;
    Q.rear = s;

    return true;
}

/*
// 入队（不带头结点）
bool EnQueue(LinkQueue &Q, int e)
{
    LinkNode *s = (LinkNode *) malloc(sizeof(LinkNode));
    if (s == NULL) return false;

    s->data = e;
    s->next = NULL;
    if (Q.front == NULL)  // 对第一个元素进行特殊处理
    {
        Q.front = s;
        Q.rear = s;
    }
    else
    {
        Q.rear->next = s;
        Q.rear = s;
    }

    return true;
}
*/

// 出队（带头结点）
bool DeQueue(LinkQueue &Q, int &x)
{
    if (isEmpty(Q)) return false;

    LinkNode *q = Q.front->next;
    x = q->data;
    Q.front->next = q->next;
    // 如果出队的是最后一个元素
    if (q == Q.rear) Q.rear = Q.front;
    free(q);

    return true;
}

/*
// 出队（不带头结点）
bool DeQueue(LinkQueue &Q, int &x)
{
    if (isEmpty(Q)) return false;

    LinkNode *q = Q.front;
    x = q->data;
    Q.front->next = q->next;
    if (q == Q.rear)
    {
        Q.front = NULL;
        Q.rear = NULL;
    }
    free(q);

    return true;
}
*/

void test()
{
    LinkQueue Q;
    InitQueue(Q);

    EnQueue(Q, 1);
    EnQueue(Q, 2);
    EnQueue(Q, 3);
    int x = 0;
    DeQueue(Q, x);
    printf("%d\n", x);

    if (isEmpty(Q)) printf("This LinkQueue is empty!\n");
    else printf("It is not empty!\n");
}

int main()
{
    test();   

    return 0;
}

#include <cstdio>
#include <stdlib.h>

#define MaxSize 10

// 循环队列
typedef struct {
    int data[MaxSize];
    int front, rear;
    int size;
    int tag;
} SqQueue;

// 初始化
void InitQueue(SqQueue &Q)
{
    Q.front = 0;
    Q.rear = 0;  // 队尾指针指向的是队尾元素的下一个位置
    Q.size = 0;
    Q.tag = 0;
}

// 判空
bool EmptyQueue(SqQueue Q)
{
    if (Q.front == Q.rear && Q.tag == 0) return true;
    // if (Q.size == 0) return true;
    // if (Q.front == Q.rear) return true;
    else return false;
}

// 入队
bool EnQueue(SqQueue &Q, int e)
{
    // 因为是循环队列 所以判断队列是否满的条件只能看队尾的下一个位置是否为队头 必须牺牲一个存储单元
    // 要解决这个问题可以直接增加一个size变量 利用判断元素个数来判断是否满或空
    // 或者加入一个tag变量 如果插入令tag为1如果删除令为0 判断是由于插入还是删除导致的队头队尾指针相遇
    // if ((Q.rear + 1) % MaxSize == Q.front) return false;
    // if (Q.size == MaxSize) return false;
    if (Q.rear == Q.front && Q.tag == 1) return false;

    Q.data[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MaxSize;
    Q.size ++;
    Q.tag = 1;

    return true;
}

// 出队
bool DeQueue(SqQueue &Q, int &x)
{
    if (EmptyQueue(Q)) return false;

    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    Q.size --;
    Q.tag = 0;

    return true;
}

// 取队头元素
bool GetHead(SqQueue &Q, int &x)
{
    if (EmptyQueue(Q)) return false;

    x = Q.data[Q.front];
    return true;
}

// 返回队列中元素个数
int getNums(SqQueue Q)
{
    return (Q.rear + MaxSize - Q.front) % MaxSize;
}

void test()
{
    SqQueue Q;
    InitQueue(Q);

    int x = 0;
    EnQueue(Q, 1);
    EnQueue(Q, 2);
    EnQueue(Q, 3);
    DeQueue(Q, x);

    printf("nums:%d\n", getNums(Q));
}

int main()
{
    test();   

    return 0;
}

#include <stdio.h>
#include <stdlib.h>

typedef struct Linknode{
    int data;
    struct Linknode *next;
} LNode, *LinkStack;

// 链栈的初始化(不带头结点)
void InitLinkStack(LinkStack &S)
{
    S = NULL;
}

// 判空
bool StackEmpty(LinkStack S)
{
    if (S == NULL) return true;
    else return false;
}

// 入栈
bool Push(LinkStack &S, int e)
{
    LNode *p = (LNode *) malloc(sizeof(LNode));
    if (p == NULL) return false;

    p->data = e;
    p->next = S;
    S = p;

    return true;
}

// 出栈
bool Pop(LinkStack &S, int &x)
{
    if (StackEmpty(S)) return false;  // 此时是空栈

    LNode *p = S;
    x = p->data;
    S = S->next;
    free(p);

    return true;
}

// 读取栈顶元素
bool GetTop(LinkStack S, int &x)
{
    if (StackEmpty(S)) return false;

    x = S->data;

    return true;
}

void test()
{
    LinkStack S;

    InitLinkStack(S);

    // Push(S, 1);
    // Push(S, 2);
    // Push(S, 3);
    // int i = 0;
    // Pop(S, i);

    // int x = 0;
    // if (GetTop(S, x)) printf("%d\n", x);
    // else printf("The Stack is empty!\n");
}

int main()
{
    test();

    return 0;
}

#include <stdio.h>
#include <stdlib.h>

typedef struct Linknode{
    int data;
    struct Linknode *next;
} LNode, *LinkStack;

// 链栈的初始化(带头结点)
bool InitLinkStack(LinkStack &S)
{
    S = (LNode *) malloc(sizeof(LNode));
    if (S == NULL) return false;

    S->next = NULL;

    return true;
}

// 判空
bool StackEmpty(LinkStack S)
{
    if (S->next == NULL) return true;
    else return false;
}

// 入栈
bool Push(LinkStack &S, int e)
{
    LNode *p = (LNode *) malloc(sizeof(LNode));
    if (p == NULL) return false;

    p->data = e;
    p->next = S->next;
    S->next = p;

    return true;
}

// 出栈
bool Pop(LinkStack &S, int &x)
{
    if (StackEmpty(S)) return false;  // 此时是空栈

    LNode *p = S->next;
    x = p->data;
    S->next = p->next;
    free(p);

    return true;
}

// 读取栈顶元素
bool GetTop(LinkStack S, int &x)
{
    if (StackEmpty(S)) return false;

    x = S->next->data;

    return true;
}

void test()
{
    LinkStack S;

    InitLinkStack(S);

    // Push(S, 1);
    // Push(S, 2);
    // Push(S, 3);
    // int i = 0;
    // Pop(S, i);

    // int x = 0;
    // if (GetTop(S, x)) printf("%d\n", x);
    // else printf("The Stack is empty!\n");
}

int main()
{
    test();

    return 0;
}

#include <stdio.h>

#define MaxSize 10

typedef struct {
    int data[MaxSize];
    int top0;
    int top1;
} SqSList;

// 共享栈的初始化
void InitStack(SqSList &S)
{
    S.top0 = -1;
    S.top1 = MaxSize;
}

// 判空
bool StackEmpty(SqSList S)
{
    if (S.top0 == -1 && S.top1 == MaxSize) return true;
    else return false;
}

// 入栈
bool Push(SqSList &S, int e)
{
    if (S.top1 - S.top0 == 1) return false;

    S.data[++ S.top0] = e;
    // S.data[-- S.top1] = e;

    return true;
}

// 出栈
bool Pop(SqSList &S, int &x)
{
    if (S.top0 == -1 || S.top1 == MaxSize) return false;

    x = S.data[S.top0 --];
    // x = S.data[S.top1 ++];

    return true;
}

// 读取栈顶元素
bool GetTop(SqSList S, int &x)
{
    if (S.top0 == -1 || S.top1 == MaxSize) return false;

    x = S.data[S.top0];
    // x = S.data[S.top1];

    return true;
}

void test()
{
    SqSList S;

    InitStack(S);
}

int main()
{
    test();

    return 0;
}

#include <stdio.h>

#define MaxSize 10

typedef struct {
    int data[MaxSize];
    int top;  // 栈顶指针
} SqList;

// 初始化
void InitStack(SqList &S)
{
    S.top = -1;
}

// 判空
bool StackEmpty(SqList S)
{
    if (S.top == -1) return true;
    else return false;
}

// 入栈
bool Push(SqList &S, int e)
{
    if (S.top == MaxSize - 1) return false;

    S.data[++ S.top] = e;

    return true;
}

// 出栈
bool Pop(SqList &S, int &x)
{
    if (S.top == -1) return false;

    x = S.data[S.top --];

    return true;
}

// 读取栈顶元素
bool GetTop(SqList S, int &x)
{
    if (S.top == -1) return false;

    x = S.data[S.top];

    return true;
}

void test()
{
    SqList S;

    InitStack(S);
}

int main()
{
    test();

    return 0;
}

#include <cstdio>
#include <stdlib.h>

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

typedef struct DNode {
    int data;
    struct DNode *prior, *next;
} DNode, *DLinkList;

// 单链表从一个结点出发只能找到后续的各个结点，但是循环单链表从一个结点出发可以找到其他任何一个结点
// 初始化一个循环单链表
bool InitCirLinkList(LinkList &L)
{
    L = (LNode *) malloc(sizeof(LNode));
    if(L == NULL) return false;

    L->next = L;

    return true;
}

// 初始化一个循环双链表
bool InitCirDLinkList(DLinkList &L)
{
    L = (DNode *) malloc(sizeof(DNode));
    if (L == NULL) return false;

    L->next = L;
    L->prior = L;

    return true;
}

// 循环单链表判空
bool isEmpty1(LinkList L)
{
    if (L->next == L) return true;
    else return false;
}

// 循环双链表判空
bool isEmpty2(DLinkList L)
{
    if (L->next == L) return true;
    else return false;
}

// 判断循环单链表的结点p是否为表尾结点
bool isTail1(LinkList L, LNode *p)
{
    if (p->next == L) return true;
    else return false;
}

// 判断循环双链表的结点p是否为表尾结点
bool isTail2(DLinkList L, DNode *p)
{
    if (p->next == L) return true;
    else return false;
}

// 在循环双链表的结点p后插入一个结点s 此时不要考虑表尾的特殊情况
bool InsertNextDNode(DLinkList L, DNode *p, DNode *s)
{
    s->next = p->next;
    s->prior = p;
    p->next->prior = s;
    p->next = s;
}

// 在循环双链表中删除结点p的后继结点 同样不需要考虑特殊情况
bool DeleteNextDNode(DLinkList L, DNode *p)
{
    DNode *q = p->next;
    p->next = q->next;
    q->next->prior = p;
    free(q);

    return true;
}

void test()
{
    LinkList L1;
    InitCirLinkList(L1);

    DLinkList L2;
    InitCirDLinkList(L2);
}

int main()
{
    test();   

    return 0;
}

#include <stdio.h>
#include <stdlib.h>

typedef struct DNode {
    int data;
    struct DNode *prior, *next;
} DNode, *DLinkList;

bool InitDLinkList(DLinkList &L)
{
    L = (DNode *) malloc(sizeof(DNode));  // 分配一个头结点
    if (L == NULL) return false;

    L->next = NULL;
    L->prior = NULL;

    return true;
}

// 实现在给定结点p之后插入一个结点s
bool InsertNextDNode(DNode *p, DNode *s)
{
    if (p == NULL && s == NULL) return false;

    s->next = p->next;
    s->prior = p;
    if (p->next != NULL) p->next->prior = s;
    p->next = s;

    return true;
}

// 实现在给定结点p之前插入一个结点s
bool InsertPriorDNode(DNode *p, DNode *s)
{
    if (p == NULL && s == NULL) return false;

    s->next = p;
    s->prior = p->prior;
    if (p->prior != NULL) p->prior->next = s;
    p->prior = s;

    return true;
}

// 删除指定结点p的后继结点
bool DeleteNextDNode(DNode *p, int &e)
{
    if (p == NULL) return false;
    if (p->next == NULL) return false;

    DNode *q = p->next;
    p->next = q->next;
    if (q->next != NULL) q->next->prior = p;
    free(q);

    return true;
}

// 销毁双链表
void destoryDLinkList(DLinkList &L)
{
    while (L->next != NULL)
    {
        DeleteNextDNode(L);
    }

    free(L);
    L = NULL;
}

// 遍历
void ergodic(DLinkList L)
{
    DNode *p = L->next;
    while (p != NULL)
    {
        /*
            操作
        */
        p = p->next;  // 向后
        // p = p->prior;  向前
    }
}

void testDLinkList()
{
    DLinkList L;

    InitDLinkList(L);
}

int main()
{
    testDLinkList();

    return 0;
}

#include <cstdio>
#include <stdlib.h>

typedef struct LNode {
    int data;
    struct LNode *next;  // 指针
} LNode, *LinkList;  // 意义相同 加强自己理解 - LNode *表示结点 LinkList表示此单链表

/*
// 初始化没有头结点的单链表
bool InitLinkList(LinkList &L)
{
    L = NULL;
    return true;
}

bool isEmpty(LinkList L)
{
    if (L == NULL) return true;
    else return false;
}
*/

// 初始化有头结点的单链表
bool InitLinkList(LinkList &L)
{
    L = (LNode *) malloc(sizeof(LNode));
    if (L == NULL) return false;  // 内存不足 分配失败
    L->next = NULL;
    return true;
}

bool isEmpty(LinkList L)
{
    if (L->next == NULL) return true;
    else return false;
}

// 按位查找(返回第i个元素 带头结点)
LNode* GetElem(LinkList L, int i)
{
    if (i < 0) return NULL;

    LNode *p;
    int j = 0;
    p = L;

    while (p != NULL && j < i)
    {
        p = p->next;
        j ++;
    }

    return p;
}

/*
按位查找(不带头结点)
LNode* GetElem(LinkList L, int i)
{

}
*/

// 按值查找
LNode* LocateElem(LinkList L, int e)
{
    LNode *p = L->next;

    while (p != NULL && p->data != e)
    {
        p = p->next;
    }

    return p; 
}

/*
按值查找(不带头结点)
LNode* LocateElem(LinkList L, int e)
{

}
*/

// 求表长(带头结点)
int Length(LinkList L)
{
    int len = 0;
    LNode *p = L;
    while (p->next != NULL)
    {
        p = p->next;
        len ++;
    }

    return len;
}

/*
// 求表长(不带头结点)
int Length(LinkList L)
{
    int len = 0;

    if (L == NULL) return 0;

    else
    {
        len = 1;
        LNode *p = L->next;
        while (p != NULL)
        {
            p = p->next;
            len ++;
        }
    }

    return len;
}
*/

// 指定结点的后插操作
bool InsertNextNode(LNode *p, int e)
{
    if (p == NULL) return false;

    LNode *s = (LNode *) malloc(sizeof(LNode));
    if (s == NULL) return false;

    s->data = e;
    s->next = p->next;
    p->next = s;

    return true;
}

// 尾插法建立单链表(带头结点)
LinkList ListTailInsert(LinkList &L)
{
    int x;
    L = (LinkList) malloc(sizeof(LNode));
    LNode *s, *r = L;  // s为新建结点 r为尾结点

    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LNode *) malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;

    return L;
}

/*
// 尾插法建立单链表(不带头结点)
LinkList ListTailInsert(LinkList &L)
{
    int x;
    LNode *s, *r = L;

    // 单独对第一个结点特殊处理
    scanf("%d", &x);
    L = (LNode *) malloc(sizeof(LNode));
    L->data = x;
    L->next = NULL;
    r = L;

    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LNode *) malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;

    return L;
}
*/

// 头插法建立单链表(带头结点)
LinkList ListHeadInsert(LinkList &L)
{
    int x;
    L = (LinkList) malloc(sizeof(LNode));
    LNode *s;
    L->next = NULL;

    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LNode *) malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }

    return L;
}

/*
// 头插法建立单链表(不带头结点)
LinkList ListHeadInsert(LinkList &L)
{
    int x;
    LNode *s;

    scanf("%d", &x);
    L = (LNode *) malloc(sizeof(LNode));
    L->data = x;
    L->next = NULL;

    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LNode *) malloc(sizeof(LNode));
        s->data = x;
        s->next = L;
        L = s;
        scanf("%d", &x);
    }

    return L;
}
*/

// 在第i个位置插入值为e的元素
// 如果是不带头结点的需要对第一个元素进行特殊处理
bool ListInsert(LinkList &L, int i, int e)
{
    if (i < 1) return false;

    // LNode *p = GetElem(L, i - 1);  封装
    LNode *p;  // 指针p指向当前扫描到的结点
    int j = 0;  // j表示当前结点的位序
    p = L;  // 初始位置为头结点

    // 寻找第i-1个位置
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j ++;
    }

    // return InsertNextNode(p, e);  封装

    if (p == NULL) return false;

    // 找到第i个位置后创建新结点
    LNode *s = (LNode *) malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;


    return true;
}

// 指定结点的前插操作
bool InsertPriorNode(LNode *p, int e)
{
    if (p == NULL) return false;

    LNode *s = (LNode *) malloc(sizeof(LNode));
    if (s == NULL) return false;

    s->data = p->data;
    s->next = p->next;
    p->data = e;
    p->next = s;
}

// 按位序删除并且将删除的值返回给e
bool ListDelete(LinkList &L, int i, int &e)
{
    if (i < 1) return false;

    // LNode *p = GetElem(L, i - 1);  封装
    LNode *p;
    int j = 0;
    p = L;

    // 寻找第i-1个位置
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j ++;
    }

    if (p == NULL) return false;
    if (p->next == NULL) return false;

    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);

    return true;
}

// 删除指定结点 - 但如果要删除的结点是最后一个结点则会出现空指针的错误 那样的话就只能从表头开始遍历
bool DeleteNode(LNode *p)
{
    if (p == NULL) return false;

    LNode *q = p->next;
    p->data = q->data;
    p->next = q->next;
    free(q);

    return true;
}

// 带头结点
void PrintList(LinkList L)
{
    if (isEmpty(L)) printf("This LinkList is empty!\n");
    else
    {
        LNode *p = L->next;
        while (p != NULL)
        {
            printf("%d ", p->data);
            p = p->next;
        }
        printf("\n");
    }
}

/*
// 不带头结点
void PrintList(LinkList L)
{
    if (isEmpty(L)) printf("This LinkList is empty!\n");
    else
    {
        LNode *p = L;
        while (p != NULL)
        {
            printf("%d ", p->data);
            p = p->next;
        }
        printf("\n");
    }
}
*/

void test()
{
    LinkList L;
    InitLinkList(L);

    ListTailInsert(L);

    printf("%d\n", Length(L));
    PrintList(L);
}

int main()
{
    test();   

    return 0;
}

#include <iostream>

using namespace std;

const int N = 10;

int n;
int path[N];
bool st[N];

void dfs(int u)
{
    if (u == n)
    {
        for (int i = 0; i < n; i ++) printf("%d ", path[i]);
        puts("");
        return;
    }

    for (int i = 1; i <= n; i ++)
    {
        if (!st[i])
        {
            st[i] = true;
            path[u] = i;
            dfs(u + 1);
            st[i] = false;
        }
    }
}

int main()
{
    scanf("%d", &n);

    dfs(0);

    return 0;
}