数据结构之汉诺塔

落日映苍穹つ 2022-05-06 16:28 157阅读 0赞

*  汉诺塔栈

#include <stdio.h>
    #include <stack>
    
    
    //递归实现
    void hanoi_With_Recursion(int n, char x, char y, char z)
    {
        if (n == 1)
        {
            printf("%d from %c to %c\n", n,x,z);
        }
        else
        {
            /* 将x 上编号1 至n-1 的圆盘移到y，z 作辅助塔*/
            hanoi_With_Recursion(n - 1, x, z, y);
            /* 将编号为n 的圆盘从x 移到z */
            printf("%d from %c to %c\n", n, x, z);
            /* 将y 上编号1 至n-1 的圆盘移到z，x 作辅助塔*/
            hanoi_With_Recursion(n - 1, y, x, z);
        }
    }
    int main()
    {
        int n;
        scanf("%d", &n);
        printf("%d\n", (1 << n) - 1); /* 总次数*/
        hanoi_With_Recursion(n, 'A', 'B', 'C');
        return 0;
    }

*  汉诺塔队列
 *      #include <stdio.h>
        #include <math.h>
        #include <stdlib.h>
        #include <string.h>
        #include <windows.h>
        
        
        #define FALSE 0
        #define TRUE 1
        
        
        char graph[10][43]={
        {" ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? \n"},
        {" ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? \n"},
        {" ? ? ? | ? ? ? ? ? ?| ? ? ? ? ? ?| ? ? ? \n"},
        {" ? ? ? | ? ? ? ? ? ?| ? ? ? ? ? ?| ? ? ? \n"},
        {" ? ? ? | ? ? ? ? ? ?| ? ? ? ? ? ?| ? ? ? \n"},
        {" ? ? ? | ? ? ? ? ? ?| ? ? ? ? ? ?| ? ? ? \n"},
        {" ? ? ? | ? ? ? ? ? ?| ? ? ? ? ? ?| ? ? ? \n"},
        {" ? ? ? | ? ? ? ? ? ?| ? ? ? ? ? ?| ? ? ? \n"},
        {" ? ? ? | ? ? ? ? ? ?| ? ? ? ? ? ?| ? ? ? \n"},
        {"-----------------------------------------\n"},
        };
        
        typedef struct QNode {
        int data; //存放数据
        struct QNode *next;//存放直接后继的指针
        } QNode, *QueuePtr;
        
        typedef struct {  //辅助队列 ?广度优先扩展时用到
        QueuePtr front;
        QueuePtr rear;
        } LinkQueue;
        
        /* 初始化队列 */
        int InitQueue(LinkQueue *Q)
        {
        /* 申请头结点空间，赋值给头/尾指针 */
        Q->rear = Q->front = (QueuePtr)malloc(sizeof(QNode));
        if (Q->front == NULL)
        exit(-1);
        Q->front->next = NULL;//头结点的next域
        return TRUE;
        }
        
        /* 销毁队列 */
        int DestroyQueue(LinkQueue *Q)
        {
        /* 整个链表(含头结点)依次释放
        没有像链表、栈等借助 QNode *p, *q; 而直接借用了front和rear */
        while (Q->front) { //若链表为空，则循环不执行
        Q->rear = Q->front->next; //抓住链表的下一个结点
        free(Q->front);
        Q->front = Q->rear;
        }
        
        Q->rear = Q->front = NULL;
        return TRUE;
        }
        
        /* 判断是否为空队列 */
        int QueueEmpty(LinkQueue Q)
        {
        /* 判断front和rear指针是否相等 */
        if (Q.front == Q.rear)
        return TRUE;
        else
        return FALSE;
        }
        
        /* 元素入队列 */
        int EnQueue(LinkQueue *Q, int e)
        {
        QueuePtr p;
        p = (QueuePtr)malloc(sizeof(QNode));
        if (p == NULL)
        return FALSE;
        
        p->data = e;
        p->next = NULL;//新结点的next必为NULL
        Q->rear->next = p;//接在当前队尾的后面
        Q->rear = p; //指向新的队尾
        
        return TRUE;
        }
        
        /* 元素出队列 */
        int DeQueue(LinkQueue *Q, int *e)
        {
        QueuePtr p;
        /* 空队列则返回 */
        if (Q->front == Q->rear) //用Q->front->next==NULL也可以
        return FALSE;
        
        p = Q->front->next;//指向首元
        Q->front->next = p->next;//front指向新首元，可能为NULL
        /* 如果只有一个结点，则必须修改尾指针 */
        if (Q->rear == p)
        Q->rear = Q->front;
        /* 返回数据并释放结点 */
        *e = p->data;
        free(p);
        return TRUE;
        }
        
        
        void IsExist(int *state,int tnum,int num,LinkQueue &Q)
        { // 四个参数的意义: 状态记录数组，下一个状态值，当前状态值，状态值队列
        if (state[tnum] == -1) // 如果下一个状态值未被分配:未取得(对应状态标记为-1:初始化标记),将该状态入队列
        {
        state[tnum] = num; // 修改下一个状态值为下标对应状态值数组的值(从-1变为上一状态值) ?(这里就包含了所求可行状态值之间的关系)
        EnQueue(&Q, tnum); //元素入队列
        }
        }
        /* --------- 图像输出函数集 ------------ */
        
        void PrintGraph()
        {
        system("cls");
        printf("过程演示：\n");
        int i;
        printf("\n");
        for (i=0; i<10; i++)
        printf("%s", graph[i]);
        }
        
        void InitGraph(int n)
        {// 形成n对应的盘子叠加图形
        int i,j,k;
        for (i=0,j=8; i<n; i++,j--)
        {
        for(k=7-n+i; k<=7+n-i; k++)
        graph[j][k]='@';
        }
        }
        
        void Moveto(int from, int to, int size)//from to 只有0,1,2
        {
        //bool moved=false;//判断是否已移动
        int i,j,k,m,slen;
        int from1=from*13+7;
        int to1=to*13+7;
        for (i=2; i<9; i++)//找到起始层
        if (graph[i][from1+1]=='@')//层数记录
         break;
         
        for (j=2; j<=9; j++)//找到目标层数
        if (graph[j][to1+1]=='@'||graph[j][to1+1]=='-')//层数记录
         {
         j--;
         break;
         }
        // i 为当前层, j 为目标层
        
        for(k=i-1; k>=0; k--)//上移
        {
        for (m=from1-size; m<=from1+size; m++){
        graph[k][m]='@';
        if (m==from1&&k>=1)
        graph[k+1][m]='|';
        else
        graph[k+1][m]=' ';
        }
        PrintGraph();
        }
        
        slen=size*2+1;
        if (from1<to1)//平移
        for(k=from1; k<=to1; k++)//右移
        {
        for(m=k-size; m<k-size+slen; m++)
        graph[0][m]='@';
        graph[0][k-size-1]=' ';
        PrintGraph();
        }
        else//左移
        for(k=from1; k>=to1; k--)
        {
        for(m=k+size; m>k+size-slen; m--)
        graph[0][m]='@';
        graph[0][k+size+1]=' ';
        PrintGraph();
        }
        //平移结束
        /* 下移 */
        for(k=1; k<=j; k++)
        {
        for (m=to1-size; m<=to1+size; m++){
        graph[k][m]='@';
        if (m==to1&&k>2)
        graph[k-1][m]='|';
        else
        graph[k-1][m]=' ';
        }
        PrintGraph();
        }
        
        }
        
        void Display(int **recd, int num, int len)//演示函数
        {
        int i,j,k=0;
        int tmp[100][3];
        //analysize recd
        for(i=1; i<=num; i++)//compare with last one
        {
         for (j=0; j<len; j++)
        if (recd[i][j]!=recd[i-1][j])
        {
        tmp[k][0]=len-j;//变化的盘号
        tmp[k][1]=recd[i-1][j];//变化的起始位置
        tmp[k][2]=recd[i][j];//变化的终止位置
        k++;
        }
        }
        InitGraph(len);//根据层数进行初始化图像
        PrintGraph();
        i=0;
        do
        {
        Moveto(tmp[i][1], tmp[i][2], tmp[i][0]);
        i++;
        }while(i<k);
        
        printf("Over...");
        getchar();
        getchar();
        }
        
        /* ------------------------------------- */
        
        /* 起始状态为0.....0 终止状态为2......2 */
        int main()
        {
        /* -------------- 变量定义 ------------ */
        int BRICKNUM;  //圆盘数
        printf("请输入汉诺塔层数：");
        scanf("%d",&BRICKNUM);
        
        LinkQueue Q;
        int i, j, k;
        int n;
        int num;
        int temp_of_num;
        int temp_of_add;
        int num_of_state=1;//总状态数
        
        for (int count=0; count<BRICKNUM; count++) //计算总状态数
        num_of_state *= 3; // 每个盘子有3种状态(状态之间关联，有些没有用会被筛除掉)
         // 状态值数组表示了状态值之间的单向羁绊！状态值数组下标与状态值元素值是上下(前后)关系，当前状态值是以下一状态值为下标的状态元素的值
        // 当前状态数组元素值是其上一个状态值
        int *record_of_state = (int*)malloc(num_of_state*sizeof(int));  //每种状态的记录,-1代表未分配，否则为其父节点的下标 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(总状态数为:num_of_state,状态分配状态值在相应数组中记录)
        int *temp = (int*)malloc(BRICKNUM*sizeof(int)); // 定义存放n个盘子数，整型大小的存储空间
        int *order_of_state = (int *)malloc(num_of_state*sizeof(int));//记录状态变化顺序
        
        //此次汉诺塔问题借助三进制表示方法，0代表的是存在a柱子，1代表放在b柱子上，2代表放在c柱子上，位高的代表大盘，位低代表小盘，如? ? ? ? ?0000代表 ? ? ? ? ? ? ? 四个盘全部放在a柱子上
        
        
        for (i = 0; i < num_of_state; i++)//初始化record_of_state
        {
        record_of_state[i] = -1; //-1状态表示未分配
        }
        
        InitQueue(&Q); // 初始化队列
        num = 0; // num记录的是所有盘子元素状态序列对应的整数，可转化为一串0,1,2数字序列。
        EnQueue(&Q, num); //状态1入栈，即0000(此时所有的盘子的状态都是0)
        record_of_state[num] = -2; // 状态数的大小是根据n的取值来确定的(num代表一个状态的取值，num的最大值即为最大状态数)
        /*
        ? ? ? ?这里是在出队列状态值的基础上,获取每一个盘子的状态(由整数得到一个数字序列)，在逐位来判断，确定下一状态值
        ? ? ? ?这里的规律:确定最底盘后(序列下标相对最小)，该位就一直不变
        ? ?*/
        
        /* ?这里会筛选所需的状态值，以及他们的先后关系(每个状态值都进入了队列，有些被排除了，最后得到? ? ? ? 关键的状态值路径) ?*/
        while (QueueEmpty(Q) == FALSE) //状态空间的生成（如果队列不为空，扩展状态空间）
        {
        DeQueue(&Q, &num); // 元素出队列，出队元素的值记录到了num中
        
        n = num; // n获得的是当前盘子对应的状态序列整数(将整数整除3(三种摆放方式)得到序列：状态序列)
        
        
        for (i = BRICKNUM - 1; i >= 0; i--) // 分解成三进制形式(从后往前存储，大盘子的状态再最前面=>整数的高位，对应数组下标越小)
        {// 这里n个盘片，进行n次循环，temp对应是n个整型数据大小区间
        temp[i] = n % 3; // 对应temp区间存储的是：n个盘子的状态序列
        n /= 3;
        }
        
        if (temp[BRICKNUM - 1] == 0) //最后一位是0=>最上层盘子状态(该状态下:最小的盘子在a柱子上)
        { // 一个状态可以有多个子状态(关系记录在状态值数组中)
        temp_of_num = num + 1; // 记录下一状态值(在当前出队列的状态值的基础上)
        IsExist(record_of_state, temp_of_num,num, Q); //若下一状态值未被分配,将其入队列
        temp_of_num = num + 2;
        IsExist(record_of_state, temp_of_num,num, Q);
        
        
        for (i = BRICKNUM - 2, temp_of_add = 3; i >= 0; i--)
        { //扫描当前状态值后续对应3进制的每一位
        if (temp[i] == 1)
        {
        temp_of_num = num + temp_of_add;
        IsExist(record_of_state, temp_of_num,num, Q);
        break;
        }
        else if (temp[i] == 2)
        {
        temp_of_num = num - temp_of_add;
        IsExist(record_of_state, temp_of_num,num, Q);
        break;
        }
        temp_of_add *= 3;
        }
        }
        else if (temp[BRICKNUM - 1] == 1) //最后一位是1(该种状态下:最小的盘子在b柱子上)
        {
        temp_of_num = num - 1;
        IsExist(record_of_state, temp_of_num,num, Q);
        
        temp_of_num = num + 1;
        IsExist(record_of_state, temp_of_num,num, Q);
        
        for (i = BRICKNUM - 2, temp_of_add = 3; i >= 0; i--)
        {
        if (temp[i] == 0)
        {
        temp_of_num = num + temp_of_add * 2;
        IsExist(record_of_state, temp_of_num,num, Q);
        break;
        }
        else if (temp[i] == 2)
        {
        temp_of_num = num - temp_of_add * 2;
        IsExist(record_of_state, temp_of_num,num, Q);
        break;
        }
        temp_of_add *= 3;
        }
        }
        else // 该状态下:最小的盘子在c柱子上
        {
        temp_of_num = num - 2;
        IsExist(record_of_state, temp_of_num,num, Q);
        
        temp_of_num = num - 1;
        IsExist(record_of_state, temp_of_num,num, Q);
        
        for (i = BRICKNUM - 2, temp_of_add = 3; i >= 0; i--)
        {
        if (temp[i] == 0)
        {
        temp_of_num = num + temp_of_add;
        IsExist(record_of_state, temp_of_num,num, Q);
        break;
        }
        else if (temp[i] == 1)
        {
        temp_of_num = num - temp_of_add;
        IsExist(record_of_state, temp_of_num,num, Q);
        break;
        }
        temp_of_add *= 3;
        }
        }
        }
        
        /*
        1: 如何完成的所有状态值无序入队列
        2: 前后结点（状态值之间联系）查找，筛选的算法
        */
        
         /* ?order_of_state 数组装载的是筛选的路径中入队的状态值,虽然所有的状态值都入过对列，但从中选择出了最短需要路径*/
        num = num_of_state - 1; // 状态值数组最大下标
        // 初始record_of_state数组的值都被赋值为-1，如果要入队列就将其值赋值为上一状态值的大小
        i = 0; // 从后往前遍历状态值数组:如果当前状态值入过队列,则其值为上一状态值
        while (record_of_state[num] != -2) // 跳出口为第一个状态值0...0，其对应状态值数组值为-2.它是作为起点单独处理的
        {
        order_of_state[i] = num; // 这里记录着入过队列:即为分配过的状态值元素下标?
        num = record_of_state[num]; // num记录上一状态值，也即上上状态值对应下标 (应该可以将值与下标转化为相差为1的关系)
        i++;
        }
        order_of_state[i] = num; // 在num=0时并没有装入order_of_state就跳出了循环
        
        int mycount=0;
        int **recd = (int **)malloc((i+1)*sizeof(int *));//记录状态变化顺序
        for (j=0; j<=i; j++)
        recd[j] = (int *)malloc(BRICKNUM*sizeof(int));
        // int **recd= new int[i][BRICKNUM];//记录状态变化，以便图像演示使用
        for (j=i; j>=0; j--)
        {
        n = order_of_state[j];
        for (k = BRICKNUM - 1; k >= 0; k--) //分解成三进制形式
        {
        temp[k] = n % 3;
        n /= 3;
        }
        memcpy(recd[mycount], temp, BRICKNUM*sizeof(int));
        mycount++;
        for (k = 0; k < BRICKNUM; k++)
        printf("%d", temp[k]);
        printf("\n");
        }
        getchar();
        getchar();
        //输出演示
        if(BRICKNUM!=0)
         Display(recd, i, BRICKNUM);
        //释放变量
        free(temp);
        free(record_of_state);
        free(order_of_state);
        for (k=0; k<=i; k++)
        free(recd[k]);
        free(recd);
        getchar();
        return 0;
        }