数据结构（7-2广度~~7-15）所有代码

7-2 迷宫-广度策略

一个陷入迷宫的老鼠如何找到出口的问题。老鼠希望系统性地尝试所有的路径之后走出迷宫。如果它到达一个死胡同，将原路返回到上一个位置，尝试新的路径。在每个位置上老鼠可以向八个方向运动，顺序是从正东开始按照顺时针进行。无论离出口多远，它总是按照这样的顺序尝试，当到达一个死胡同之后，老鼠将进行“回溯”。迷宫只有一个入口，一个出口，设计程序要求输出迷宫的一条通路。迷宫采用二维存储结构表示，1表示障碍，0表示通路；要求如下： 1、实现队列的相关操作； 2、利用队列进行广度策略搜索算法输出路径；
输入格式:
输入包括三部分：第一个输入是迷宫大小；第二个输入是迷宫的状态；第三个输入是入口和出口位置

输出格式:
反向输出探索的路径，注意包括入口和出口位置。每个位置之间用分号;分隔

输入样例:
9
1 1 1 1 1 1 1 1 1
1 0 0 1 1 0 1 1 1
1 1 0 0 0 0 0 0 1
1 0 1 0 0 1 1 1 1
1 0 1 1 1 0 0 1 1
1 1 0 0 1 0 0 0 1
1 0 1 1 0 0 0 1 1
1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1
1 1 7 7
解题思路：
1.创建两个空队列LinkQueueX和LinkQueueX
2.将入口entreX和entryY分别压入队列LinkQueueX和LinkQueueX。
3.当队列不空
①取队头元素，出队
②for(mov=0;mov<8;mov++),即还存在可以探索的相邻的方向。
a.按照顺时针依次探索各个位置（X,Y）。
b.如果（posX,posY）是出口，则输出路径，返回。
c.如果（posX,posY）是没有走过的通路；
设置标志位mark[posX][posY]=1。
当前位置入队。
记录前驱位置，方便输出路径。
输出样例:
7 7;6 6;5 6;4 5;3 4;2 3;1 2;1 1;

#include <stdio.h>
#include <stdlib.h>
struct Maze_width
{
    int size;
    int** data;
};
typedef struct Maze_width* Maze;
struct Node
{
    int data;
    struct Node*link;
};
typedef struct Node *PNode;
struct Queue
{
    PNode f;
    PNode r;
};
typedef struct Queue *linkQueue;
Maze SetMaze(int size)
{
    Maze maze=(Maze)malloc(sizeof(struct Maze_width));
    maze->size=size;
    maze->data=(int**)malloc(sizeof(int*)*maze->size);
    for(int i=0;i<maze->size;i++)
    {
        maze->data[i]=(int*)malloc(sizeof(int)*maze->size);
    }
    return maze;
}
void ReadMaze(Maze maze)
{
    int i,j;
    for(i=0;i<maze->size;i++)
    {
        for(j=0;j<maze->size;j++)
        scanf("%d",&maze->data[i][j]);
    }
}
linkQueue SetNullQueue_link()
{
    linkQueue lqueue;
    lqueue=(linkQueue)malloc(sizeof(struct Queue));
    if(lqueue!=NULL)
    {
        lqueue->f=NULL;
        lqueue->r=NULL;
    }
    else
        printf("Alloc failure! \n");
    return lqueue;
}
int IsNullQueue_link(linkQueue lqueue)
{
    return lqueue->f==NULL;
}
void EnQueue_link(linkQueue lqueue,int x)
{
    PNode p;
    p=(PNode)malloc(sizeof(struct Node));
    if(p==NULL)
        printf("Alloc failure!\n");
    else{
        p->data=x;
        p->link=NULL;
        if(lqueue->f ==NULL)
        {
            lqueue->f=p;
            lqueue->r=p;
        }
        else
        {
            lqueue->r->link=p;
            lqueue->r=p;
        }
    }
}
void DeQueue_link(linkQueue lqueue)
{
    struct Node *p;
    if(lqueue->f==NULL)
        printf("it is empty queue\n");
    else
    {
        p=lqueue->f;
        lqueue->f=lqueue->f->link;
        free(p);
    }
}
int FrontQueue_link(linkQueue lqueue)
{
    if(lqueue->f==NULL)
    {
        printf("it is empty queue!\n");
        return 0;
    }
    else
        return lqueue->f->data;
}
int MazeBSF(int entryX,int entryY,int exitX,int exitY,Maze maze)
{
    int direction[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
    linkQueue linkQueueX=NULL;
    linkQueue linkQueueY=NULL;
    int posX,posY;
    int preposX,preposY;
    int **preposMarkX;
    int **preposMarkY;
    int **mark;
    int i,j,mov;
    preposMarkX=(int**)malloc(sizeof(int*)*maze->size);
    for(i=0;i<maze->size;i++)
    {
        preposMarkX[i]=(int*)malloc(sizeof(int)*maze->size);
    }
    preposMarkY=(int**)malloc(sizeof(int*)*maze->size);
    for(i=0;i<maze->size;i++)
    {
        preposMarkY[i]=(int*)malloc(sizeof(int)*maze->size);
    }
    mark=(int**)malloc(sizeof(int*)*maze->size);
    for(i=0;i<maze->size;i++)
    {
        mark[i]=(int*)malloc(sizeof(int)*maze->size);
    }
     for(i=0;i<maze->size;i++)
    {
        for(j=0;j<maze->size;j++)
        {
            preposMarkX[i][j]=-1;
            preposMarkY[i][j]=-1;
            mark[i][j]=0;
         }
    }
    linkQueueX=SetNullQueue_link();
    linkQueueY=SetNullQueue_link();
    EnQueue_link(linkQueueX,entryX);
    EnQueue_link(linkQueueY,entryY);
    mark[entryX][entryY]=1;
    while(!IsNullQueue_link(linkQueueX))
    {
        preposX=FrontQueue_link(linkQueueX);
        DeQueue_link(linkQueueX);
        preposY=FrontQueue_link(linkQueueY);
        DeQueue_link(linkQueueY);
        for(mov=0;mov<8;mov++)
        {
            posX=preposX+direction[mov][0];
            posY=preposY+direction[mov][1];
            if (posX == exitX && posY == exitY)
            {
            preposMarkX[posX][posY] = preposX;
                preposMarkY[posX][posY] = preposY;
                printf("%d %d;",exitX,exitY);
            while(!(posX==entryX&&posY==entryY))
            {
                preposX=preposMarkX[posX][posY];
                preposY=preposMarkY[posX][posY];
                posX=preposX;
                posY=preposY;
                printf("%d %d;",posX,posY);
            }
            return 1;
        }
        if(maze->data[posX][posY]==0&&mark[posX][posY]==0)
        {
            EnQueue_link(linkQueueX,posX);
            EnQueue_link(linkQueueY,posY);
            mark[posX][posY]=1;
            preposMarkX[posX][posY]=preposX;
            preposMarkY[posX][posY]=preposY;
        }
        }
    }
    return 0;
}
int main()
{
    Maze maze;
    int Size,result;
    scanf("%d",&Size);
    maze=SetMaze(Size);
    int entryX,entryY,exitX,exitY;
    ReadMaze(maze);
    scanf("%d%d%d%d",&entryX,&entryY,&exitX,&exitY);
    result=MazeBSF(entryX,entryY,exitX,exitY,maze);
    if(result==0)
        printf("无法找到出口");
    return 0;
}

7-3 农夫过河-广度策略

一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。遗憾的是他只有一只小船，小船只能容下他和一件物品。这里只能是农夫来撑船。同时因为狼吃羊，而羊吃白菜，所以农夫不能留下羊和狼或者羊和白菜单独在河的一边，自己离开。好在狼属于肉食动物，不吃白菜。农夫怎样才能把所有的东西安全运过河呢？
为了表示每个物品的位置，采用二进制位来区分南岸和北岸，0表示在南岸，1表示在北岸。用四个二进制位XXXX分别表示农夫、狼、菜和羊四个物品所在的位置。例如1110表示农夫、狼和菜在北岸，菜在南岸。农夫过河问题的初始状态为0000，结束状态为1111。
输入格式:
无输入
输出格式:
输出农夫移动物品的中间状态的逆序
输入样例:
无
输出样例:
15 6 14 2 11 1 9 0
审题：使用顺序队列算法。
程序设计思想：
1、从起点开始，用十六进制数一一穷举
2、判断穷举出的元素是否符合安全且不重复
3、将符合的元素放入队列中并一一输出出来
实现流程：
(1) 初始状态0000入队
(2) 当队列不空且没有到达结束状态1111时循环以下操作：
①队头状态出队。
②按照农夫一个人走、农夫分别带上3个走循环以下操作：
如果农夫和他们在同一岸，则计算新的状态。
如果新的状态是安全的并且是没有处理过的，则更新status[ ]，并将新状态入队。
③当状态为1111时逆向输出staus[ ]数组。

需要注意的是状态能否入队，要判断以下3条，满足任何一条都不能入队。
不可能：通过判断是否在同一岸；
不安全：通过安全函数判断；
处理过：记录处理过的状态。

#include<stdio.h>
#include<stdlib.h>
//四者的位置为农夫 狼 白菜 羊
typedef char DataType;
struct Queue    //队列
{
int Max;  
int f;   
int r;  
DataType *elem; 
};
typedef struct Queue *SeqQueue;

struct Node     //结点
{
DataType  data;
struct Node*  next;
};
typedef struct Node  *PNode;

SeqQueue SetNullQueue_seq(int m) 
{
SeqQueue squeue;
squeue = (SeqQueue)malloc(sizeof(struct Queue));
if (squeue == NULL)
{
printf("Alloc failure\n");
return NULL;
}
squeue->elem = (char*)malloc(sizeof(DataType)*m);
if (squeue->elem != NULL)
{
squeue->Max = m;
squeue->f = 0;
squeue->r = 0;
return squeue;
}
}

int IsNullQueue_seq(SeqQueue squeue) 
{
return (squeue->f == squeue->r);
}

void EnQueue_seq(SeqQueue squeue, DataType x)
{
if((squeue->r+1)%(squeue->Max) == (squeue->f))
printf("It is FULL Queue!");
else{
squeue->elem[squeue->r] = x;
squeue->r = (squeue->r+1) % (squeue->Max);
}
}

void DeQueue_seq(SeqQueue squeue)
{
if(IsNullQueue_seq(squeue))
printf("It is empty queue!");
else
{
squeue->f = (squeue->f+1) %(squeue->Max);
}
}

DataType FrontQueue_seq(SeqQueue squeue)
{
DataType result;
if(IsNullQueue_seq(squeue))
printf("It is empty queue!");
else
return squeue->elem[squeue->f];
}

int FarmerOnRight(int status) //判断当前状态下农夫是否在右岸
{
return (0 != (status & 0x08));   // status为int型（2个字节，16位），0000 1000，&为按位与操作
}

int WolfOnRight(int status) //判断当前状态下狼是否在右岸
{
return (0 != (status & 0x04));   //0000 0100
}

int CabbageOnRight(int status) //判断当前状态下白菜是否在右岸
{
return (0 != (status & 0x02));    //0000 0010
}

int GoatOnRight(int status) //判断当前状态下羊是否在右岸
{
return (0 != (status & 0x01));   //0000 0001
}

int IsSafe(int status)
{
if((GoatOnRight(status) == CabbageOnRight(status)) && (GoatOnRight(status) != FarmerOnRight(status)))
return (0);   /* 羊吃白菜*/
if((GoatOnRight(status) ==  WolfOnRight(status)) && (GoatOnRight(status) != FarmerOnRight(status)))
return (0);    /* 狼吃羊*/
return (1);       /* 其他状态是安全的*/
}

int main()
{
int i,movers,nowstatus,newstatus;
int status[16];     //用于记录已考虑的状态路径
SeqQueue moveTo;    //用于记录可以安全到达的中间状态
moveTo = SetNullQueue_seq(20);     //创建空队列
EnQueue_seq(moveTo,0x00);    //初始状态时所有物品在右岸，初始状态0000入队
for(i = 0;i<16;i++)      //数组status初始化为-1
status[i] = -1;
status[0] = 0;

while(!IsNullQueue_seq(moveTo) && (status[15] == -1))    //队列非空且没有到达结束状态
{
nowstatus = FrontQueue_seq(moveTo);            //取队头状态为当前状态
DeQueue_seq(moveTo);
for(movers = 1;movers<=8;movers <<= 1)     //遍历三个要移动物品，<<=为左移运算
//考虑各种物品移动
if((0 != (nowstatus & 0x08)) == (0 != (nowstatus & movers))) //农夫与移动的物品在同一侧
{
    newstatus = nowstatus ^ (0x08|movers); //计算新状态。^为按位异或运算操作符，相同为0、相异为1；|为按位或运算操作符，只要有1就是1，两个都是0才是0。
if(IsSafe(newstatus) && (status[newstatus] == -1)) //新状态是安全的且之前没有出现过
{
status[newstatus] = nowstatus;         //记录新状态
EnQueue_seq(moveTo,newstatus);    //新状态入队
}
}
}

if(status[15] != -1)   //到达最终状态，输出经过的状态路径
{
    for(nowstatus = 15;nowstatus >= 0;nowstatus = status[nowstatus])
{
printf("%d ",nowstatus);
if(nowstatus == 0)
exit(0);
}
}
else
printf("No solution.\n");    //问题无解
return 0;
}

7-4 “聪明的学生”

问题描述：一位逻辑学的教授有三个非常聪明善于推理且精于心算的学生，Alice、Bob和Charles。一天教授给他们出了一个题。教授在每个人脑门上帖了一个纸条，每个纸条上写了一个正整数，Alice、Bob和Charles分别是3，5，8，并且告诉学生某两个数的和等于第三个，每个学生只能看见另外两个同学头上的正整数，但是看不见自己的。
教授问的顺序是Alice—Bob—Charles—Alice……经过几次提问后，当教授再次询问到Charles时，Charles露出了得意的笑容，准确的报出了自己头上的数。
输入格式:
本题输入为Alice、Bob和Charles头上的数字
输出格式:
教授在第几次提问时，轮到回答问题的那个人猜出了自己头上的数（要求用递归程序解决）。
输入样例:
在这里给出一组输入。例如：
3,5,8
示例1：每个学生都能知道另外两个学生的的数字，但不清楚自己的数字，这里用1、2、3作为例子来分析。A有两种情况，一种是（3-2），另外一种是（2+3），但是A不能确定是哪一种情况，所以A猜不出来。再来看看B，两种情况分别是（1+3）和（3+1），但是B仍然不能确定。最后是C，两种情况是（1+2）和（2-1），但是C可以排除（2-1）这个情况的，因为如果C是（2-1），那么B是在看到A是1，C是1的情况下可以猜出来自己是2，但是B没有猜出来，故C可以排除的是（2-1）这种情况，因此C只能是（2+1），也就是3。
示例2：假设三个人为A、B、C，他们的数字分别是2、8、6，则在第五次猜测，也就是B进行第二次猜测的时候，猜到自己的数是8。因为在第五次猜测的时候，他看到的是A的2和C的6，则他可能的数字是8或者4，但是如果是4，则C在第三次猜测的时候，就能猜出答案（这种情况下，C拥有最大的数6）。因为C看到的是A的2和B的4，则C的可能数字是2或者6，但是如果是2，则B在第二次猜测的时候，就可以得到答案，因为B看到的是2和2。所以逆推回去可知，B的数是8。
综上，每个人只知道另外两个人头上的数字，因此他的头上只可能是另外两个数相加或者相减两种情况，如果能排除掉一种情况，那么他就知道了自己头上的数字。这样的推理是假设——排除的过程。即假设自己的数是两个数种的其中一种，如果另两个人可以在自己之前猜出，则这种可能性就可以排除。
此外，可以分析和总结出最大数字总会被先猜出来，是因为只有最大数字可以排除相减的情况，因为如果他是相减得到的，前面一定有人可以猜出来。
实现流程：在知道上面的推理后，先来解决【已知A、B、C三人的三个数分别为x、y、z时，最少需要几次，才会有人猜到自己的数字】这个问题。由于总是数字最大的人最先猜到结果，所以给定x、y、z的时候，结果就已经定下了。假设其中z最大，则x+y=z。C得到结果的依据是排除了z=|x-y|这种可能性，即假设z=|x-y|，则A和B中数字较大的那个人将在上一次猜测的时候得到结果。（如果x>y，则A会在C进行本次猜测之前2次得到结果；如果x<y，则B会在C进行本次猜测之前1次得到结果。）
所以我们能得到下面的递推式：
假设times(i,j,a,b,c)表示a,b,c三人的数字分别是i,j,i+j时，猜到结果所需的次数，而p(x,y)表示从人x问到人y所需要提问的次数（比如在上例中，p(A,C)=2），则有
在这里插入图片描述上式中第二种情况表示，但最大的数是j时所需要的提问次数加上从b问到c所需要问的次数。

实现流程：现在将问题抽象，即A、B、C头上的数字分别为X1、X2、X3。上述结论可知，最大的数总会先猜出来。不妨假设，B是先猜出来的学生，即X2=X1+X3，而B能排除|X1-X3|这种可能性的依据有两个：一是X1=X3，那么B只能是X1+X3，因为三个都是正整数；另外一个依据是假设X2=|X1-X3|，那么在前面提问中A或C已经先猜出来了（如果X1>X3，则A会在B进行本次猜测之前2次得到结果；如果X1<X3，则C会在B进行本次猜测之前1次得到结果。），但他们没有猜出来，可以确定自己是两数之和，而非两数之差。至于A先猜出来还是C先猜出来，如果A>C，那么A先猜出来，否则C先猜出来。那么问题可以转化为，找出x1、|x1-x3|、x3中第一个猜出数字的人所用的次数。这个问题不断地重复成一个子问题，不断的重复这个过程，直到某个学生能够猜出这个数字来。这样可以归结为如下的一个递归函数：
在这里插入图片描述
其中，T1编号的人头上数字为I，T2编号的人头上数字为J，编号T3的头上数字为I+J（即T3将最先猜出来自己的数字），教授提问的次数是P(T1, T3)，表示按照1-2-3的顺序，从T1问到T3所用的最少次数。
补充：对于一个局面 (x, y, x+y)，不妨设 x > y，那么 x+y 那个人能猜出自己脑袋上的数当且仅当他能排除自己脑袋上的数是 x-y 的可能性。怎么排除？就是假设自己脑袋上是 x-y，那么由于他知道另外两个人的数是啥（即 x 和 y），他也知道 x > y，那么就是说 (x, y, x-y) 中最大的是 x，那么如果在轮到头上是 x 的那个人在他理应猜出来的那步时还回答不出来，就说明自己头上的数不可能是 x-y，那么就可以从 (x, y, x-y) 这个局面的答案推出 (x, y, x+y) 这个局面的答案了。
以下程序的主要思想在于：
1、先确定可以一次就得出结果的情形，并根据该情况一一推理
2、将输入的情况一一递归，最后得到可一次就得出的情况
3、将每次递归的次数相加

7-5 非递归方式统计二叉树中右孩子结点的个数

本题要求采用非递归方式统计二叉树中右孩子结点的个数。
输入格式:
这里采用递归方式建立二叉树，输入的先序序列
输出格式:
输出是二叉树右孩子结点的个数
输入样例:
AB@D@@C@@
输出样例:
2
本题要求采用非递归方式统计二叉树中右孩子结点的个数。
输入格式:这里采用递归方式建立二叉树，输入的先序序列
输出格式:输出是二叉树右孩子结点的个数
输入样例:AB@D@@C@@
输出样例:2
实现流程：
①非递归遍历二叉树：
 从根结点bt开始，将根结点压入栈lstack中；
 如果栈lstack不空，从栈lstack中弹出一个元素p，并访问；
 如果p的右孩子不为空，入栈
 如果p的左孩子不为空，入栈
 重复一直到栈为空为止
②统计右孩子的数目。
因为栈具有后进先出的特点，而先序遍历的顺序为根-左-右，所以在代码当中先把右节点入栈，再把左结点入栈。当遍历到的结点的右结点不为空时，将右孩子的数目加一。

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100

typedef char DataType;
typedef struct BTreeNode
{
	DataType data;
	struct BTreeNode *leftchild;
	struct BTreeNode *rightchild;
}BinTreeNode;
typedef BinTreeNode *BinTree;

//函数功能： 递归建立二叉树
//输入参数： 无
//返回值： 二叉树的根
BinTree CreateBinTree_Recursion()//采用递归方式建立二叉树，输入的先序序列；特别注意返回值。
{ 
char ch;
BinTree bt;
scanf("%c", &ch);
if (ch == '@')
bt = NULL;
else
{
bt = (BinTreeNode *)malloc(sizeof(BinTreeNode));
bt->data = ch;
bt->leftchild = CreateBinTree_Recursion();
bt->rightchild = CreateBinTree_Recursion();
}
return bt;
}

//函数功能：自上而下，从左到右依次遍历（非递归层序遍历），并统计右节点数量。
//输入参数：二叉树的根
//返回值：二叉树右孩子结点的个数
int NumRightChild_NonRecursion(BinTree bt)
{
int count=0;   //用于统计右孩子节点个数
BinTree queue[MAXSIZE],node;//队列
node = bt;
int front = 0;//模拟队列队头
int rear = 0;//模拟队列队尾
queue[rear++] = node;
if (bt == NULL) {
printf("树为空树！\n");
return count;
}
while (front != rear) {     //队列不为空
node = queue[front++];      //先获取队头元素，然后再指向队列的下一位元素
if (node-> leftchild) {
queue[rear++] = node-> leftchild; //此节点左孩子不空，则入队列
}
if (node->rightchild) {
count++;   //此节点右孩子不空，计数+1
queue[rear++] = node->rightchild; //此节点右孩子不空，则入队列
}
}
printf("%d", count);
}

int main()
{
BinTree bt = NULL;
//printf("输入二叉树的先序序列：\n");
bt = CreateBinTree_Recursion();
//printf("二叉树的链式存储结构建立完成！\n");
//printf("该二叉树中右节点的数量为：\n");
NumRightChild_NonRecursion(bt);
}

7-6 二叉树的非递归遍历

本题要求采用栈实现对二叉树的非递归遍历，包括先序、中序和后序三种遍历方式。
输入格式:
输入序列是按照先序序列输入，以@表示空结点
输出格式:
先序、中序和后序遍历序列分别按行输出
输入样例:
ABC@@D@@E@FG@@@
输出样例:
ABCDEFG
CBDAEGF
CDBGFEA
本题要求采用栈实现对二叉树的非递归遍历，包括先序、中序和后序三种遍历方式。
输入格式:输入序列是按照先序序列输入，以@表示空结点
输出格式:先序、中序和后序遍历序列分别按行输出
输入样例:ABC@@D@@E@FG@@@
输出样例:
ABCDEFG
CBDAEGF
CDBGFEA

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100

//定义二叉树的结构体
typedef struct BiNode {
    char data;
    struct BiNode* lchild;
    struct BiNode* rchild;
}BiNode, * BiTree;
 
//先序创建二叉树
BiTree CreateBiTree() {
    BiNode* T = NULL;
    char ch;
    ch = getchar();//先序输入树的各个节点值
    if (ch != '@') {
        T = (BiNode*)malloc(sizeof(BiNode));
        T->data = ch;
        T->lchild = CreateBiTree();
        T->rchild = CreateBiTree();
    }
    else {
        T = NULL;
    }
    return T;
}
 
//非递归先序遍历二叉树
void PreOrder(BiTree T) {
    BiTree stack[MAXSIZE], node;//模拟栈
    int top = 0;

    if (T == NULL) {
        printf("树为空树!\n");
        return;
    }
    else {
        top++;
        stack[top] = T;
        while (top > 0) {
            node = stack[top--];            //出栈
            printf("%c", node->data);
 
            //先把右子树放进去，再放左子树，栈后进先出，左先出
            if (node->rchild != NULL) {
                stack[++top] = node->rchild;//入栈
            }
            if (node->lchild != NULL) {
                stack[++top] = node->lchild;
            }
        }
    }
}
//非递归中序遍历二叉树
void InOrder(BiTree T) {
    BiTree stack[MAXSIZE], node;
    int top = 0;
 
    if (T == NULL) {
        printf("树为空树!\n");
        return;
    }
    node = T;
    while (node != NULL || top > 0) {//将所有的左子树节点入栈
        while (node != NULL) {
            stack[++top] = node;
            node = node->lchild;
        }
        node = stack[top--];        //此时指针指向节点的左孩子为空节点，访问节点
        printf("%c", node->data);
        node = node->rchild;        //指针指向右孩子
    }
}
//非递归后序遍历二叉树
void PostOrder(BiTree T) {
    BiNode* p = T;
    BiNode* stack[MAXSIZE];
    BiNode* r = NULL;         //辅助指针,记录被访问过的节点
    int top = 0;
    if (T == NULL) {
        printf("树为空树!\n");
        return;
    }
    while (p || top > 0) {
        while (p) {     //走到最左边
            stack[top++] = p;
            p = p->lchild;
        }
        p = stack[top - 1]; //指针指向最后一个入栈的左节点
        if (NULL== p->rchild || p->rchild == r) {//此节点没有右孩子或者右孩子已经访问过
            printf("%c", p->data);//访问该节点值
            top--;
            r = p;                //记录最近访问过的节点
            p = NULL;          //节点访问完后重置p指针
        }
        else {
            p = p->rchild; //右孩子存在，则指向右孩子，重复上面操作
        }
    }
}


int main() {
    BiTree T = CreateBiTree();
    //printf("非递归先序遍历二叉树：\n");
    PreOrder(T);
    printf("\n");
    //printf("非递归中序遍历二叉树：\n");
    InOrder(T);
    printf("\n");
    //printf("非递归后序遍历二叉树：\n");
    PostOrder(T);
    printf("\n");
    return 0;
}

7-7 线索二叉树的建立和遍历

本题要求实现对建立中序线索二叉树和中序遍历中序线索二叉树。

在这里插入图片描述

输入格式:
输入为先序序列
输出格式:
输出为中序遍历线索树的结点值以及结点的左右指针信息。
输入样例:
在这里给出一组输入。例如：
AB@D@@CE@@@
输出样例:

B 1 0
D 1 1
A 0 0
E 1 1
C 0 1

本题要求实现对建立中序线索二叉树和中序遍历中序线索二叉树。

输入格式:输入为先序序列
输出格式:输出为中序遍历线索树的结点值以及结点的左右指针信息。
建立中序线索二叉树：

创建两个指针p和pr，pr为前驱p为当前结点。中序遍历二叉树，如果左子孩子不空，左标志位不变（依旧为0），左指针指向下一个结点。左孩子空，则将左指针指向前驱结点，即pr指向的结点，并把左标志位修改为1。右子树同左子树一样，但是有没有右孩子的时候将右指针指向后继结点，并把右标志位修改为1.

中序遍历线索二叉树:

在中序遍历的第一个结点是沿着左分支的最下面的结点；在线索二叉树中，一个结点的后继分为两种情况；

如果该结点的右标志位是线索，则右指针指向该结点的后继结点；如果该结点的右标志位不是线索，则右指针指向该结点的右子树的根结点，根据中序遍历的定义，该结点的后继是右子树的最左下结点。

实现流程：
(1)建立中序线索二叉树：
①在线索二叉树初始化时，线索都设置为0，通过对二叉树的中序遍历添加线索。设置指指向正在访问的结点，指针pr指向刚刚访问过的结点，即p的前驱结点。修改中序遍历的非递归算法，将遍历过程中的访问结点步骤修改为添加线索。
If(pr!=NULL)
{
If(pr->rightchild== NULL)//pr的右孩子为空，设置pr的rtag
{pr->rightchild=p;pr->rthread=1;}
If{p->leftchild== NULL}//pr的左孩子为空，设置pr的rtag
{p->leftchild=pr;pr->lthread=1;}
}
②如果pr的右指针为空，则令pr的右指针指向其后继结点p，修改pr的右线索为1，p->lthread=1,如果p的左指针为空，则令p的左指针指向其前驱结点pr，并修改p的左线索,p->rthread=1。
(2)中序遍历线索二叉树:
①在中序遍历的第一个结点是沿着左分支的最下面的结点；
while(p->leftchild!=NULL&&p->lthread==0)
②在线索二叉树中，一个结点的后继分为两种情况；
 如果该结点的rthread是线索，则右指针指向该结点的后继结点；
 如果该结点的rthread不是线索，则右指针指向该结点的右子树的根结点，根据中序遍历的定义，该结点的后继是右子树的最左下结点。

#include <stdio.h>
#include <stdlib.h>
//线索标志位
//link表示指向左右孩子
//thread表示指向前驱后继
enum{link, thread};
//二叉树结构体
struct btree
{
char data;
struct btree *lchild, *rchild;
int ltag, rtag;
};
//全局变量，指向刚访问过的结点
struct btree *pre;
//用户按照前序遍历方式创建二叉树
void create_btree(struct btree **T)
{
char c;
*T = (struct btree *)malloc(sizeof(struct btree));
scanf("%c", &c);
if(c=='@')
{
*T = NULL;
}
else
{
(*T)->data = c;
//线索标志位全部初始化为link
(*T)->ltag = link;
(*T)->rtag = link;
create_btree(&(*T)->lchild);
create_btree(&(*T)->rchild);
}
}
//中序遍历二叉树，更改线索标志位以及前驱后继
void inthread(struct btree *T)
{
if(T)
{
inthread(T->lchild);
//如果左孩子为空，线索标志位改为thread，lchild指向前驱
//中序遍历二叉树的第一个结点的前驱为头结点
if(!(T->lchild))
{
T->ltag = thread;
T->lchild = pre;
}
//如果右孩子为空，线索标志位改为thread，rchild指向后继
//中序遍历二叉树的最后一个结点的后继为头结点
if(!(pre->rchild))
{
pre->rtag = thread;
pre->rchild = T;
}
//pre为刚访问过的结点
pre = T;
inthread(T->rchild);
}
}
//创建头节点，并让pre初始化为头结点
void inordthread(struct btree **P, struct btree *T)
{
//初始化头结点
(*P) = (struct btree *)malloc(sizeof(struct btree));
//头结点左标志位为link，左孩子为二叉树根结点
//头结点右标志位为thread，后继初始化为自己，后面会设置为二叉树最后一个结点
(*P)->ltag = link;
(*P)->rtag = thread;
(*P)->lchild = T;
(*P)->rchild = *P;
if(!T)
{
(*P)->lchild = *P;
}
else
{
//pre初始化为头结点
pre = *P;

inthread(T);
//中序遍历二叉树的最后一个结点的标志位为thread
//后继为头结点
pre->rtag = thread;
pre->rchild = *P;
//头结点的后继为最后一个结点
(*P)->rchild = pre;
}
}
//使用线索中序遍历二叉树
void inordtraversal(struct btree *P)
{
//临时结点p2，初始化为根结点
struct btree *p2;
p2 = P->lchild;
//若p2不等于头结点，说明遍历没有完成
while(p2 != P)
{
//p2有左孩子，一直往下遍历
while(p2->ltag == link)
{
p2 = p2->lchild;
}
printf("%c  %d  %d\n",p2->data,p2->ltag,p2->rtag);
//若没有右孩子且后继不为头结点，p2等于p2的后继(一直往后走)
while(p2->rtag == thread  && p2->rchild != P)
{
p2 = p2->rchild;
printf("%c  %d  %d\n",p2->data,p2->ltag,p2->rtag);
}
//若没有后继，p2等于p2的右孩子
p2 = p2->rchild;
}
}
int main()
{
struct btree *P, *T;
create_btree(&T);
inordthread(&P, T);
inordtraversal(P);
return 0;
}

7-8 哈夫曼编码

本题要求字符的哈夫曼编码，注意建立的哈夫曼树严格按照左小右次小的顺序，并且哈夫曼编码时严格按照左‘0’右‘1’进行编码。
输入格式:
输入是各个字符在通信中出现的频率
输出格式:
输出是各个字符的哈夫曼编码，每个字母占一行
输入样例:
A:2
B:3
C:6
D:7
E:10
F:19
G:21
H:32
输出样例:
A:10000
B:10001
C:1001
D:1010
E:1011
F:00
G:01
H:11
本题要求字符的哈夫曼编码，注意建立的哈夫曼树严格按照左小右次小的顺序，并且哈夫曼编码时严格按照左‘0’右‘1’进行编码。

输入格式:输入是各个字符在通信中出现的频率

输出格式:输出是各个字符的哈夫曼编码，每个字母占一行

采用顺序存储，根据扩充二叉树的性质，如果有n个外部结点，则右n-1个内部结点，总结点个数为2n-1，故此的数组大小为2n-1。

分配2n-1大小的数组空间；存放n个外部结点和n-1个内部结点，设置parent为-1，设置左孩子为-1，设置右孩子为-1。对于外部结点，weight为权值大小，对于内部结点，设置weight为-1；

找到权值最小和次小的元素，并根据这两个结点构造父结点；

令父结点的权值是最小和次小结点的权值之和，父结点和左孩子即x1的数组下标，父结点的右孩子即x2的数组下标；

对于最小和次小的元素，修改其parent为新生成的父结点的数组下标。

实现流程：
设计采用顺序存储的数据结构实现哈夫曼算法，由于哈夫曼树是扩充二叉树，根据扩充二叉树的性质可知，如果有n个外部结点，则右n-1个内部结点，总结点个数为2n-1，因此设计的数组大小为2n-1。
(1) 分配2n-1大小的数组空间；
(2) 初始化数组，存放n个外部结点和n-1个内部结点，设置parent为-1，设置leftchild为-1，设置rightchild为-1。对于外部结点，是指weight为权值大小，对于内部结点，设置weight为-1；
(3) 找到权值最小和次小的元素，并根据这两个结点构造父结点；
(4) 设置父结点的权值是这两个结点的权值之和，父结点和做孩子leftchild等于x1的数组下标，父结点的右孩子rightchild等于x2的数组下标；
(5) 对于最小和次小的元素，修改其parent为新生成的父结点的数组下标。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
//字符串数组类型
typedef char **HuffmanCode;
 
typedef struct
{
    int weight;
    char name;
    int parent, lchild, rchild;
}HTNode, *HuffmanTree;
 
//构造哈夫曼树
void Select(HuffmanTree HT, int len, int *s1, int *s2)
{
    int i, min1 = 0x3f3f3f3f, min2 = min1;
    for(i = 1; i <= len; i++)
    {
        //当parent值为0时说明是未合并过的结点
        if(HT[i].parent == 0)
        {
            //比最小值小的时候
            if(HT[i].weight < min1)
            {
                //把最小值赋给次最小值
                min2 = min1;
                //把最小值下表赋给次最小值的下标
                *s2 = *s1;
                //把新的最小值赋给最小值min
                min1 = HT[i].weight;
                //把新的最小值下标赋给s1
                *s1 = i;
            }
            //没有最小值小的时候，比较他和次最小值
            else if(HT[i].weight < min2)
            {
                min2 = HT[i].weight;
                *s2 = i;
            }
        }
    }
}
 
//n为叶结点个数
void CreateHuffmanTree(HuffmanTree *HT, int n)
{
    if(n<=1) return;
    int i;
    //计算要开辟的结点数
    int m = 2*n-1;
    *HT = (HTNode*)malloc(sizeof(HTNode)*(m+1));
    //将所有结点的双亲、左子树右子树全初始化为0
    for(i = 1; i <= m; i++)
    {
        (*HT)[i].parent = 0;
        (*HT)[i].lchild = 0;
        (*HT)[i].rchild = 0;
    }
    //输入各个结点的权值和名字
    for(i = 1; i <= n; i++)
    {
        scanf("%c", &((*HT)[i].name));
        getchar();
        scanf("%d", &((*HT)[i].weight));
        getchar();
 
    }
    //开始创建哈夫曼树
    for(i = n+1; i <= m; i++)
    {
        int s1,s2;
        //找出当前的最小值和次最小值
        Select(*HT, i-1, &s1, &s2);
        //把权值合并的值从n+1的位置开始赋值
        (*HT)[s1].parent = i;
        (*HT)[s2].parent = i;
 
        (*HT)[i].lchild = s1;
        (*HT)[i].rchild = s2;
        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
    }
}
 
void CreateHuffmanCode(HuffmanTree HT, HuffmanCode *HC, int n)
{
    //分配n个字符串编码的空间
    *HC = (HuffmanCode)malloc(sizeof(char*)*(n+1));
    //开辟一个长度为n的字符数组用来临时存放编码
    char* cd = (char*)malloc(sizeof(char)*n);
    cd[n-1] = '\0';  //字符串结束符
    int i;
    for(i = 1; i <= n; i++)
    {
        int start = n-1; //从字符数组的末尾开始赋值
        int c = i;       //
        int f = HT[i].parent; //找出父节点
        //当父结点为0时，说明到达根节点，编码结束
        while(f != 0)
        {
            start--;
            //结点c是f的左孩子，则生成代码0
            if(HT[f].lchild == c)
                cd[start] = '0';
            else
                cd[start] = '1';
            //将原父结点看作新的子树
            c = f;
            f = HT[f].parent;
        }
        //为第i个字符串编码分配大小合适的空间,把临时存放的复制进去
        (*HC)[i] = (char*)malloc(sizeof(char)*(n-start));
        //从start的位置开始复制
        strcpy((*HC)[i], &cd[start]);
    }
    free(cd);
}
 
int main()
{
    int i;
int n=8;
HuffmanTree HT;   //哈夫曼树指针变量
HuffmanCode HC;   //哈夫曼编码指针（二重指针）
CreateHuffmanTree(&HT,n);    //创建哈夫曼树
CreateHuffmanCode(HT,&HC,n);  //创建哈夫曼编码表
for(i=1;i<=n;i++)   //位置一样的，所以遍历即可
{
printf("%c:",HT[i].name);
printf("%s\n",HC[i]);  //HC[i]是编码串首地址值，%s格式时首地址就可以
}
return 0;
 
}

7-9 判断两点之间是否存在路径

本题要求输出两个顶点之间是否存在路径
输入格式:
输入包括两部分，第一部分是邻接矩阵表示方法中对应1的两个顶点，用0 0 表示结束
第二部分是两个顶点，例如 Vi和Vj
输出格式:
如果Vi和Vj存在路径，输出1；否则输出0
输入样例:
0 1
1 0
0 4
4 0
1 4
4 1
1 2
2 1
1 3
3 1
2 3
3 2
4 5
5 4
4 6
6 4
0 0
0 5
输出样例:
1
使用邻接矩阵存储路径，对起始节点使用深度优先搜索，并将所有访问到的节点赋值为1，代表已经访问，一方面防止后续重复访问陷入死循环，另一方面在结束搜索后，如果终点节点未访问到，则代表不存在路径，如果访问到，则代表存在路径。

解题思路：使用深度优先搜索

#include <stdio.h>
#include <stdlib.h>
#define MAX 0
typedef struct GRAPHMATRIX_STRU
{
    int size;
    int **graph;
}GraphMatrix;

GraphMatrix* InitGraph(int num)
{
    int i,j;
    GraphMatrix *graphMatrix=(GraphMatrix*)malloc(sizeof(GraphMatrix));
    graphMatrix->size=num;
    graphMatrix->graph=(int**)malloc(sizeof(int*)*graphMatrix->size);
    for(i=0;i<graphMatrix->size;i++)
        graphMatrix->graph[i]=(int*)malloc(sizeof(int)*graphMatrix->size);
    for(i=0;i<graphMatrix->size;i++)
    {
        for(j=0;j<graphMatrix->size;j++)
        graphMatrix->graph[i][j]=MAX;

    }
    return graphMatrix;
}
void ReadMatrix(GraphMatrix*graphMatrix)
{
    int vex1,vex2;
    scanf("%d%d",&vex1,&vex2);
    while(vex1!=0||vex2!=0)
    {
        graphMatrix->graph[vex1][vex2]=1;
        scanf("%d%d",&vex1,&vex2);
    }

}
void IsOrNot(GraphMatrix *graphMatrix,int *visited,int source)
{
    int j;
    visited[source]=1;//若i节点被访问到，visited[i]=1
    for(j=0;j<graphMatrix->size;j++)
    {
        if(graphMatrix->graph[source][j]!=MAX&&!visited[j])
            IsOrNot(graphMatrix,visited,j);
    }
}

/*void DFS(GraphMatrix*graphMatrix,int* visited,int source)
{
    int j;
    visited[source]=1;
    printf("%d",source)
    for(j=0;j<graphMatrix;j++)
    {
        if(graphMatrix->graph[soure][j]!=MAX&&!visited[j])
            DFS(graphMatrix,visited,j);
    }
}*/
int main()
{
    int num=7;//节点个数可以自己定义，可以改为输入的方式
    int *visited=(int*)malloc(sizeof(int)*num);
   int head,tail;
   GraphMatrix *graphMatrix;
   graphMatrix=InitGraph(num);
   ReadMatrix(graphMatrix);
   scanf("%d%d",&head,&tail);//判断head节点和tail节点是否来连通
   IsOrNot(graphMatrix,visited,head);
   if(visited[tail]==1)//若head节点和tail节点连通，则输出1，否则输出0；
    printf("1");
   else
    printf("0");
   return 0;
}

7-10 判断一个有向图是否存在回路

本题要求编程判断一个有向图是否存在回路
输入格式:
输入是有向图的邻接矩阵表示中的1的相邻顶点，以-1 -1 结束
输出格式:
如果存在回路，输出1，否则输出0
输入样例:
0 3
0 2
0 1
1 5
1 4
1 2
2 5
4 5
5 3
-1 -1
输出样例:
0
解题思路：
设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列V1，V2，V3…Vn，满足若从顶点Vi到Vj有一条路径，则在顶点序列中顶点Vi必在顶点Vj之前。这种顶点序列即为拓扑排序。
拓扑排序的基本思路是：从图中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到全部顶点或者图中不存在入度为0的顶点为止。

#include <stdio.h>
#include <stdlib.h>
#define MAX 0
typedef struct GRAPHMATRIX_STRU
{
    int size;
    int **graph;
}GraphMatrix;

GraphMatrix* InitGraph(int num)
{
    int i,j;
    GraphMatrix *graphMatrix=(GraphMatrix*)malloc(sizeof(GraphMatrix));
    graphMatrix->size=num;
    graphMatrix->graph=(int**)malloc(sizeof(int*)*graphMatrix->size);
    for(i=0;i<graphMatrix->size;i++)
        graphMatrix->graph[i]=(int*)malloc(sizeof(int)*graphMatrix->size);
    for(i=0;i<graphMatrix->size;i++)
    {
        for(j=0;j<graphMatrix->size;j++)
        graphMatrix->graph[i][j]=MAX;

    }
    return graphMatrix;
}
void ReadMatrix(GraphMatrix*graphMatrix)
{
    int vex1,vex2;
    scanf("%d%d",&vex1,&vex2);
    while(vex1!=-1||vex2!=-1)
    {
        graphMatrix->graph[vex1][vex2]=1;
        scanf("%d%d",&vex1,&vex2);
    }

}
void loop(GraphMatrix *graphMatrix,int *visited,int source,int s,int *count)
{
    int j;
    visited[source]=1;//源节点被遍历到，记录为1
    for(j=0;j<graphMatrix->size;j++)
    {
        if(graphMatrix->graph[source][j]!=MAX&&j==s)//在每一次使用loop函数中，count[0]++其实只执行一次
        {   count[0]++;
            printf("%d",count[0]);
        }

        if(graphMatrix->graph[source][j]!=MAX&&!visited[j])//若有节点还为遍历到，则继续递归
            loop(graphMatrix,visited,j,s,count);
    }
}

/*void DFS(GraphMatrix*graphMatrix,int* visited,int source)
{
    int j;
    visited[source]=1;
    printf("%d",source)
    for(j=0;j<graphMatrix;j++)
    {
        if(graphMatrix->graph[soure][j]!=MAX&&!visited[j])
            DFS(graphMatrix,visited,j);
    }
}*/
int main()
{
    int num=7;//节点个数为7个，可将num改为输入方式，节点个数动态定义
    int i=0,j;
    int count[1]={0};//count[1]=0则不存在回路，count[1]=1则存在回路
    int *visited=(int*)malloc(sizeof(int)*num);
   GraphMatrix *graphMatrix;
   //初始化邻接矩阵
   graphMatrix=InitGraph(num);
   ReadMatrix(graphMatrix);
   //从0开始判断每一个节点是否能存在回路
   for(i=0;i<(graphMatrix->size);i++)
   {
       if(count[0]!=0)//若oount变为1，则已存在回路，不需要再进行下去了
       break;
       for(j=0;j<graphMatrix->size;j++)//每一次都 visited数组元素全部初始化，因为每次循环都是不同的源接待你
       {
           visited[j]=0;
       }
       loop(graphMatrix,visited,i,i,count);

   }
   if(count[0]==0)
    printf("0");
   return 0;
}

7-11 计算最小生成树权值

本题要求采用prim算法求最小生成树，输出其权值之和
输入格式:
输入为顶点顶点权值，以 0 0 0表示结束
输出格式:
输出为最小生成树的权值大小
输入样例:
0 1 5
1 0 5
0 2 30
2 0 30
0 3 14
3 0 14
1 2 24
2 1 24
2 3 17
3 2 17
1 4 14
4 1 14
1 5 10
5 1 10
4 5 25
5 4 25
2 5 17
5 2 17
3 5 8
5 3 8
0 0 0
输出样例:
在这里给出相应的输出。例如：
54
解题思路：先将0号节点视为一棵树，从与其相邻的节点里，选择权值最小的节点，合并入该树，并更新其他节点如果要加入该树，所需的权值大小。使用for循环重复该步骤，注意每次选择的节点不可以是已经在树上的节点，直到所有节点全部加入树中。

#include <bits/stdc++.h>
using namespace std;
const int N=521,INF=0x3f3f3f3f;
int d[N][N],dist[N];
bool st1[N],st2[N];//记录当前点在集合内还是集合外
int n,m;
int prim()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    int i,j,res=0;
    for(i=0;i<n;i++)//要遍历n个点，找一个最短边权的点 
    {
        int t=-1;// 初始化为没有找到的点 
        for(j=1;j<=n;j++)
        {
            if(!st1[j]&&(t==-1||dist[t]>dist[j])) t=j;
        }//不是第一个取出的结点 ，并且当前结点的距离为INF,则表示没有和集合中点相连的边 
        if(dist[t]==INF) return INF;
        st1[t]=1;
        res += dist[t];
      //更新当前最短边权点t到集合的距离（保留最小的值，如果比之前最短t到集合的距离还小，更新） 
        for(j=1;j<=n;j++)
        {
            if(!st1[j]) dist[j] = min(dist[j],d[t][j]);
        }
    }
    return res;
}
int main()
{
    memset(d,0x3f,sizeof d);
    int x,y,z,i,j;
    while(~scanf("%d %d %d",&x,&y,&z))
    {
        if(x==0&&y==0&&z==0) break;
        st2[x] = st2[y] = 1;
        d[x+1][y+1] = d[y+1][x+1] = min(d[x+1][y+1],z);
    }
    for(i=0;i<500;i++)
    {
        if(st2[i]) n++;
    }
    int t=prim();
    cout<<t;
    return 0;
}

7-12 求一个顶点到其他顶点的最短路径

本题要求计算一个顶点v0到其他顶点的最短路径，并输出该路径
输入格式:
输入为顶点顶点权值，以 0 0 0表示输入结束
输出格式:
输出为v0到其他各个顶点的最短路径长度和路径
输入样例:
在这里给出一组输入。例如：
0 1 5
0 2 30
0 3 35
1 2 24
1 5 10
1 4 29
2 5 17
3 0 15
4 5 25
5 4 12
5 3 8
0 0 0
输出样例:
0->1:5
0->1
0->2:29
0->1->2
0->3:23
0->1->5->3
0->4:27
0->1->5->4
0->5:15
0->1->5
解题思路：使用Dijkstra算法，从0节点开始寻找与之距离最小的节点，并以找到后的节点为媒介，更新其他节点与0节点的距离，创建数组用以存储最短路径。

#define size 6
#define N  1000

typedef struct{
int arc[size][size];
int numVertexes;
}MGraph;

void CreateMGraph(MGraph *G){
G->numVertexes = size;
int v1,v2,len;
    scanf("%d%d%d",&v1,&v2,&len);
    for(int i=0;i<size;i++){
    for(int j=0;j<size;j++){
    G->arc[i][j] = N;
}
}
    while(v1!=0||v2!=0||len!=0){//如果输入都是0，则停止存入 
        G->arc[v1][v2] = len;
        scanf("%d%d%d",&v1,&v2,&len);
    }
}
void Dijkstra(int cost[size][size],int v){
int dist[size],s[size],rear[size];//dist[i]当前源点到顶点i的最小距离,s表示并入集合标识 
int q[size][size]; 

int i,j,k,mmin,m;
//初始化s和rear 
for(i = 0;i < size;i ++){
s[i] = 0;
rear[i] = -1;
}
//初始化 dist和q
for(i = 0;i < size;i ++){
dist[i] = cost[v][i];
if(dist[i] < N){
q[i][++ rear[i]] = v;
q[i][++ rear[i]] = i;
}
}
s[v] = 1;//v并入 集合 
//源点以及并入，再并入 size - 1个结点 
for(k = 0;k < size - 1;k ++){
mmin = N;j = v;
for(i = 0;i < size;i ++){//选出最小的dist[j] 
if(s[i] == 0 && dist[i] < mmin){//如果标识为0（没有被处理），且有到 i 的 路径 
j = i; //待处理index 赋值为i 
mmin = dist[i];//更新 dist   
}
}
if(j != i){
            s[j] = 1;//处理后标识 为 1，避免重复处理 		
if(dist[j] == N){//dist[j] 等于无穷大，说明 没有到达该 点的路径,剔除源点到其 没有路径的index 
break;
}
//printf("\nthe %d shortestdistance is %d\n",j,dist[j]);
//for(i = 0;i <= rear[j];i ++){//查看 path 
//printf("-->%d",q[j][i]);//打印从源点到j的最短路径 
//}
for(i = 0;i < size;i ++){//修改从源点到其余各店的最短距离 
if( s[i] == 0 && ( (dist[j] + cost[j][i]) < dist[i] ) ){
dist[i] = dist[j] + cost[j][i];    //更新源点 到每个点的 最短路径 
for(m = 0;m <= rear[j];m ++){
q[i][m] = q[j][m]; //修改相应的路径 
}
rear[i] = rear[j];
q[i][++ rear[i]] = i;
                }
            }
}
}
for(i=1;i<size;i++){
printf("0->%d:%d\n",i,dist[i]);
for(j=0;j<=rear[i];j++){//打印从源点到j的最短路径 
if(j==0){
printf("%d",q[i][j]);
}else{
printf("->%d",q[i][j]);
}
}
printf("\n");
}
}
int main(){
MGraph *G = (MGraph*) malloc(sizeof(MGraph));
CreateMGraph(G);
Dijkstra(G->arc,0);
return 0;
}

7-13 判断一个有向图是否能够完成拓扑排序

本题要求输出一个有向图是否能够完成拓扑排序，要求图采用邻接表表示
输入格式:
输入为顶点vi 顶点vj ，表示vj邻接于vi；以-1 -1 表示输入结束
注意邻接表建立时采用头插法创建
输出格式:
如果能够完成拓扑排序输出1，否则输出0
输入样例:
在这里给出一组输入。例如：
0 1
0 2
0 3
1 2
1 5
1 4
2 5
4 5
5 3
-1 -1
输出样例:
1
解题思路：
本题与有向图中找闭环思路相同，如果有闭环，则不能够完成拓扑排序。采用邻接表表示，可以先将信息存在邻接矩阵中，然后将邻接矩阵转换成邻接表即可。

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

#define MAXSIZE 10

typedef struct{
int vexs[MAXSIZE];
int arc[MAXSIZE][MAXSIZE];
int numVertexes;
}MGraph;

typedef struct EdgeNode{
int adjVex;
int weight;
struct EdgeNode* next;
}EdgeNode;

typedef struct VertexNode{
int in;
int data;
EdgeNode* firstEdge;
}VertexNode,AdjList[MAXSIZE];

typedef struct GraphAdjList{
AdjList adjList;
int vertexNums,edgeNums;
}GraphAdjList;
//构建图 
void CreateMGraph(MGraph *G){
G->numVertexes = MAXSIZE;
for(int i=0;i<G->numVertexes;i++){
G->vexs[i] = i;
}
int vex1,vex2;
scanf("%d%d",&vex1,&vex2);
while(vex1!=-1||vex2!=-1){//如果输入都是0，则停止存入 
G->arc[vex1][vex2] = 1;
scanf("%d%d",&vex1,&vex2);
    }
}

// 利用邻接矩阵构建邻接表
void InitGraphADjList(MGraph *G, GraphAdjList *GL)
{
    GL->vertexNums = G->numVertexes;
    //GL->edgeNums = G->numEdges;

    for (int i = 0; i < G->numVertexes; i++) /* 读入顶点信息，建立顶点表 */
    {
        GL->adjList[i].in = 0;
        GL->adjList[i].data = G->vexs[i];
        GL->adjList[i].firstEdge = NULL; /* 将边表置为空表 */
    }

    for (int i = 0; i < G->numVertexes; i++) /* 建立边表 */
    {
        for (int j = 0; j < G->numVertexes; j++)
        {
            if (G->arc[i][j] == 1)
            {
                EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode));
                e->adjVex = j;                      /* 邻接序号为j  */
                e->next = GL->adjList[i].firstEdge; /* 将当前顶点上的指向的结点指针赋值给e */
                GL->adjList[i].firstEdge = e;       /* 将当前顶点的指针指向e  */
                GL->adjList[j].in++;
            }
        }
    }
}

int TopologicalSort(GraphAdjList *GL)
{
    int count = 0; // 用于统计输出顶点的个数
    // 用于存放入度为0的顶点
    int *stack = (int *)malloc(sizeof(int) * GL->vertexNums);
    int top = 0;
    // 入度为0的顶点入栈
    for (int i = 0; i < GL->vertexNums; i++)
    {
        if (GL->adjList[i].in == 0)
        {
            stack[++top] = i;
        }
    }
    while (top != 0)
    {
        // 栈顶出栈并将其邻接结点入度-1
        int k = stack[top--];
        //printf("%d, ", GL->adjList[k].data);
        count++;
        EdgeNode *p = GL->adjList[k].firstEdge;
        while (p != NULL)
        {
            GL->adjList[p->adjVex].in--;
            // 顶点入度只会在这里变化，因此在此处判断入度是否为0
            if (GL->adjList[p->adjVex].in == 0)
            {
                stack[++top] = p->adjVex;
            }
            p = p->next;
        }
    }
    if (count < GL->vertexNums) // 若输出的顶点个数少了，则说明这个网存在环路，不是AOV网
        return 0;
    else
        return 1;
}

int main(){
MGraph *G = (MGraph*) malloc(sizeof(MGraph));
CreateMGraph(G);
GraphAdjList *GL = (GraphAdjList *)malloc(sizeof(GraphAdjList));
InitGraphADjList(G, GL);
int flag = TopologicalSort(GL);
printf("%d\n",flag);
return 0;
}

7-14 选取医院建立的位置

设a、b、c、d、e、f表示一个乡的6个村庄,弧上的权值表示两村之间的距离。现要在这6个村庄中选择一个村庄建一所医院,问医院建在哪个村庄才能使离医院最远的村庄到医院的距离最短?
在这里插入图片描述

输入格式:
输入的第一行为村庄个数
输入的其他是多个存在组成网络的邻接矩阵表示
输出格式:
输出医院建立的位置
输入样例:
在这里给出一组输入。例如：
6
0 12 3 65535 9 10
12 0 65535 2 6 65535
3 65535 0 2 65535 6
65535 2 2 0 4 7
9 6 65535 4 0 4
10 65535 6 7 4 0
输出样例:
在这里给出相应的输出。例如：
c
解题思路：本体要求找到一个地点建医院，算出这个医院距离其它每个结点的最小距离，然后找到每个出发点这些最小距离中最远的那个作比较。找到最远距离最小的那个输出。由于要用到最小路径，需要迪杰斯特拉算法
1.初始化：
（1）创建S数组存放结点被选中的情况，选过为True，没选为False；初始化时先全部置为False。
（2）创建D数组存放到达从起点出发，到达其他顶点的距离，根据路径的发展，更小的权值会替换大的权值。初始化时先把出发点v0到其他结点的边赋给D。
（3）创建Path数组存放每个结点的上一个结点（前置结点），通常用来遍历最短路径，本题虽然不需要用到，但还是写上了。初始化时都置为-1代表没有边连接上一个。
（4）开始时把出发点v0的S[v0]改为True代表选过了，起点到自己的距离D[v0] = 0;
2.找到各个最小路径
（1）从第一个结点到最后一个结点都要找一次起点到它的最短路径，这是最外一层循环
（2）在当前的D数组中找到最小权值的边，记录下来用以链接到该边连接的下一个结点
（3）把新选出结点的S数组置为True，并且将新结点带来的新路径（边）和之前的路径权值进行比较，比之前小就替换掉D数组中对应的值，再将新结点的前置结点设置为上一个结点。
3.返回每组中最远值

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
#define bool char
#define true 1
#define false 0
 
typedef char VerTexType; //字符型顶点数据类型
typedef int ArcType;     //边的权值类型为整型
#define MVNum 100        //最大顶点数
#define MaxInt 32767     //最大权值
 
//辅助数组，用来记录从顶点集到
struct{
    VerTexType adjvex;
    ArcType lowcost;
}closedge[MVNum];
 
//图的邻接矩阵存储表示
typedef struct{
    VerTexType vexs[MVNum];    //顶点表
    ArcType arcs[MVNum][MVNum];//邻接矩阵
    int vexnum, arcnum;        //节点数和边数
}AMGraph;
 
//找到出发点得位置
int LocateVex(AMGraph* G, VerTexType v){
    for(int i = 0; i < G->vexnum; i++){
    if(G->vexs[i] == v){
return i;
} 
    }
    return -1;
}
//输入题中给的邻接矩阵
void Scanf(AMGraph* G, int n){
    int i, j;
    for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
    scanf("%d", &G->arcs[i][j]);
} 
} 
    G->vexnum = n;
}
//测试用
void Print(AMGraph G){
    int i, j;
    for(i = 0; i < G.vexnum; i++){
        for(j = 0; j < G.vexnum; j++){
        printf("%d ", G.arcs[i][j]);
} 
        printf("\n");
    }
}
//从每个顶点出发，找最短路径
int Dijkstra(AMGraph G, int v0){
    //S放是否选中过，D放起点距离其他点的距离，path放前驱结点，n是顶点个数
    int S[6], D[6], Path[6];
    int n = 6, i, w, v;
 
    //初始化
    for(v = 0; v < n; v++){
        S[v] = false;    //先把S都置为未选中过
        D[v] = G.arcs[v0][v];   //把顶点距离其他结点的距离输入
        if(D[v] < MaxInt) Path[v] = v0;  //如果v0到v有边，那就把v的前置结点写上
        else Path[v] = -1;      //如果没边，就把前置结点设置为-1代表没有
    }
    S[v0] = true;  //起点设为选中过
    D[v0] = 0;     //起点到自己的距离为0
    //开始找最小距离
    int min;
    for(i = 1; i < n; i++){
        min = MaxInt;
        for(w = 0; w < n; w++){
            //没被选中 并且有边的 结点
            if(!S[w] && D[w] < min){
                //就记录下结点的位置
                v = w;
                //并把它的权值暂存为最小权值
                min = D[w];
            }
        }
        //最小边的结点改为被选中
        S[v] = true;
        //从新选中的结点开始寻找，
        for(w = 0; w < n; w++){
           //未被选中，并且从起始节点到目前能到达的结点的最小值
            if(!S[w] && D[v] + G.arcs[v][w] < D[w]){
                //总长度 = 之前长度的总和+到新结点的长度
                D[w] = D[v] + G.arcs[v][w];
                //新结点的前置结点设置
                Path[w] = v;
            }
        }
    }
    //找到每组最远的那个
    int max = 0;
    for(int s = 0; s < 6; s++){
        if(max < D[s])
            max = D[s];
    }
    return max;
}
int main(){
    //输入
    AMGraph G;
    int n;
    scanf("%d",&n);
    Scanf(&G, n);
 
    int temp[6];
    int min = 0;
    //先把每组的最远距离计算出来
    for(int i = 0; i < 6; i++){
        temp[i] = Dijkstra(G, i);
    }
    //找最远距离中最小的
    for(int i = 0; i < 6; i++){
        if(temp[min]>temp[i])
            min = i;
    }
    //转换字符
    char name = (char)min+97;
    printf("%c",name);
    return 0;
}

7-15迷宫变种-最短路径

下面图示表示一个迷宫，四周为-1表示围墙,内部为-1表示障碍,权值1、2、5、9表示经过需要消耗的能量代价。请找出从入口(3,6)到出口(8,8),老鼠消耗能量最小的路径(注意本题是四个方向的迷宫)
在这里插入图片描述

输入格式:
第一行：迷宫的大小m n ，分别表示迷宫的长和高
第二行：入口和出口
其余行：迷宫的矩阵表示
提示：用65535为无穷大
输出格式:
输出为老鼠消耗能量最小的路径，以逆序输出
输入样例:
在这里给出一组输入。例如：
10 10
3 6 8 8
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 2 1 1 1 1 1 5 1 -1
-1 1 9 9 9 1 1 -1 1 -1
-1 1 1 1 1 1 1 -1 1 -1
-1 1 -1 -1 -1 -1 -1 -1 1 -1
-1 1 9 9 9 1 1 1 1 -1
-1 1 1 1 1 1 1 1 1 -1
-1 1 1 1 1 1 1 1 1 -1
-1 1 1 1 1 1 1 1 2 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
输出样例:
在这里给出相应的输出。例如：
(8 8)(7 8)(6 8)(5 8)(4 8)(3 8)(2 8)(1 8)(1 7)(1 6)(2 6)(3 6)

#include<stdio.h>
#include<math.h>
#include<stdbool.h>
#include<stdlib.h>
int MINLENGTH;
typedef struct Link {
    int x, y;
    struct Link* next;
}LK,*L;
int times = 0;
int row, col;
L getLNode() {
    L LHead = (L)malloc(sizeof(LK));
    LHead->x = LHead->y = 0;
    LHead->next = NULL;
    return LHead;
}
bool IN(L LHead, L LNode) {
    L Lptr = LHead;
    while (Lptr && Lptr->next) {
        if ((Lptr->next->x == LNode->x) && (Lptr->next->y == LNode->y)) {
            return true;
        }
        Lptr = Lptr->next;
    }
    return false;
}
bool ADDLNode(L LHead,L LNode) {
    L NewNode = getLNode();
    NewNode->x = LNode->x;
    NewNode->y = LNode->y;
    NewNode->next = LHead->next;
    LHead->next = NewNode;
    return true;
}
int** getMap() {
    scanf("%d%d", &row, &col);
    MINLENGTH = row * col;
    int** arr = (int**)malloc(row*sizeof(int*));
    for (int i = 0; i < row; i++)
        arr[i] = (int*)malloc(col*sizeof(int));
    int sx, sy, ex, ey;
    scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            scanf("%2d", &arr[i][j]);
    return arr;
}
int showMap(int** arr, int row, int col) {
    printf("\n");
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++)
            printf("%2d ", arr[i][j]);
        printf("\n");
    }
    return 0;
}
void showLink(L LHead) {
    while (LHead && LHead->next) {
        printf("(%d %d)", LHead->next->x, LHead->next->y);
        LHead = LHead->next;
    }
    //printf("NULL\n");
}
void detect(int sx, int sy, int ex, int ey, int** arr,L PaPaNode) {
    if (sx == ex && sy == ey) {//添加节点到全局变量中
        /*
        printf("i Found!!! times:%d\n",times++);*/
        printf("(%d %d)", sx, sy);
        showLink(PaPaNode);
        //if(PaPaNode)
        //    printf("\nlength(%d)\n", PaPaNode->x+arr[sx,sy]);
        //else
        //    printf("\nlength(%d)\n", 0);
        MINLENGTH = PaPaNode->x + 1;
        //printf("%d %d %d %d\n", sx, sy, ex, ey);
    }
    else {
        if (sx == row || sx == -1 || sy == col || sy == -1 || arr[sx][sy] == -1)
            return;
        if (PaPaNode && PaPaNode->x == MINLENGTH||PaPaNode&&(MINLENGTH-PaPaNode->x<abs(sx-ex)+abs(sy-ey)))
            return;
        L NewNode = getLNode();
        NewNode->x = sx;
        NewNode->y = sy;
        if (IN(PaPaNode, NewNode)) {
//             delete NewNode;
            return;
        }
        L LHead = getLNode();
        if (PaPaNode)
            LHead->x = PaPaNode->x + arr[sx][sy];
        else
            LHead->x = 1;
        L Lptr = LHead;
        while (PaPaNode && PaPaNode->next) {
            Lptr->next = getLNode();
            Lptr->next->x = PaPaNode->next->x;
            Lptr->next->y = PaPaNode->next->y;
            Lptr = Lptr->next;
            PaPaNode = PaPaNode->next;
        }
        ADDLNode(LHead, NewNode);
        if (LHead && LHead->next) {
            if (LHead->next->next)
            {
                if (!(LHead->next->x == sx + 1 && LHead->next->y == sy))
                    detect(sx + 1, sy, ex, ey, arr, LHead);
                if (!(LHead->next->x == sx - 1 && LHead->next->y == sy))
                    detect(sx - 1, sy, ex, ey, arr, LHead);
                if (!(LHead->next->x == sx && LHead->next->y == sy + 1))
                    detect(sx, sy + 1, ex, ey, arr, LHead);
                if (!(LHead->next->x == sx && LHead->next->y == sy - 1))
                    detect(sx, sy - 1, ex, ey, arr, LHead);
            }
            else {
                detect(sx + 1, sy, ex, ey, arr, LHead);
                detect(sx - 1, sy, ex, ey, arr, LHead);
                detect(sx, sy + 1, ex, ey, arr, LHead);
                detect(sx, sy - 1, ex, ey, arr, LHead);
            }
        }
    }
}
int main() {
    int** arr = getMap();
//     showMap(arr, 10, 10);
    detect(3, 6, 8, 8, arr, NULL);
    return 0;
}