精华内容
下载资源
问答
  • C语言判断临界矩阵表示的图是否存在回路?请问代码怎么写,是数据结构里面的?
  • 如题,望各位高手不吝赐教
  • Problem Description After a long drastic struggle with himself, LL decide to go for some snack at last. But when steping out of the dormitory, he found a serious problem : he can't remember where is ...
  • Problem Description A group of K friends is going to see a movie. However, they are too late to get good tickets, so they are looking for a good way to sit all nearby. Since they are all science ...
  • Problem Description ...每行给定整数N (N),表示矩阵为 N*N.当N为0时,输入结束。 Output 输出答案,保留2位小数。 Sample Input 1 2 3 4 0 Sample Output 1.00 3.00 5.67 8.83
  • Problem Description ...每行给定整数N (N),表示矩阵为 N*N.当N为0时,输入结束。 Output 输出答案,保留2位小数。 Sample Input 1 2 3 4 0 Sample Output 1.00 3.00 5.67 8.83
  • c语言实现基本数据结构(图)

    千次阅读 2019-03-08 11:43:12
    c语言实现基本数据结构(图) ...邻接矩阵表示法 邻接表表示法 十字链表表示法 临界多重表表示法 我只写了邻接表表示法和十字链表表示法。第一个很简单,最后一个不经常用。 下面是邻接表表示法的结构体 ...

    c语言实现基本数据结构(图)

    图是基本的数据结构中比较复杂的了,相对于链表一类来说。因为忘了不少,于是参考了一下书上的代码。
    (ps:感觉第一个难点是不知道怎么命名变量名…… ╮(╯▽╰)╭ )
    图的表示方法有四种, 分别是

    1. 邻接矩阵表示法
    2. 邻接表表示法
    3. 十字链表表示法
    4. 临界多重表表示法

    我只写了邻接表表示法和十字链表表示法。第一个很简单,最后一个不经常用。
    下面是邻接表表示法的结构体

        /*
    *邻接表表示法的结构体
    */
    struct ArcNode{//边节点
    	int adjvex;//该条边的头节点在数组中的位置
    	struct ArcNode* nextarc;//与该条边的头节点的下一条边相连
    };
    
    struct VertexNode{//头节点
    	char* nodeinfo;//节点信息|名字
    	struct ArcNode* nextarc;//与该头节点相连的第一个边结点
    };
    
    typedef struct {//邻接表表示法的图结构
    	struct VertexNode vertex[MAX];
    	int vernum, arcnum;//节点数量和弧的数量
    	GraphKind kind;//图的种类
    }AdjList;
    
    

    十字链表表示法的结构体

    /*
    *十字链表表示法的结构体
    */
    typedef struct OrthArcNode{//弧节点
    	int headvex;//该弧出发的节点
    	int tailvex;//该弧结束的节点
    	struct OrthArcNode* hlink;//该弧出发的节点的下一条节点
    	struct OrthArcNode* tlink;//该弧结束的节点的下一条节点
    }OrthArcNode;
    
    typedef struct OrthVertexNode{//头节点
    	char* nodeinfo;//节点的信息|名字
    	struct OrthArcNode* firstin, *firstout;/*以该节点为出发点的第一条弧和以该节点为结束点的第一条弧*/
    }OrthVertexNode;
    
    typedef struct{//十字链表表示法的结构体
    	OrthVertexNode vertex[MAX];
    	int vernum, arcnum;//节点数量和弧的数量
    	GraphKind kind;//图的种类
    } OrthList;
    
    

    方法有创建图和深度遍历图,深度遍历只有十字链表的,因为感觉相似就只写了一个:)

    完整代码如下

    #include<stdio.h>
    #include<stdlib.h>
    
    #define MAX 100
    #define True 1
    #define False 0
    #define Error -1
    #define OK 1
    
    int visited[MAX];
    
    typedef enum{DG, DN, UDG, UDN} GraphKind;
    
    /*
    *邻接表表示法的结构体
    */
    struct ArcNode{//边节点
    	int adjvex;//该条边的头节点在数组中的位置
    	struct ArcNode* nextarc;//与该条边的头节点的下一条边相连
    };
    
    struct VertexNode{//头节点
    	char* nodeinfo;//节点信息|名字
    	struct ArcNode* nextarc;//与该头节点相连的第一个边结点
    };
    
    typedef struct {//邻接表表示法的图结构
    	struct VertexNode vertex[MAX];
    	int vernum, arcnum;//节点数量和弧的数量
    	GraphKind kind;//图的种类
    }AdjList;
    
    
    /*
    *十字链表表示法的结构体
    */
    typedef struct OrthArcNode{//弧节点
    	int headvex;//该弧出发的节点
    	int tailvex;//该弧结束的节点
    	struct OrthArcNode* hlink;//该弧出发的节点的下一条节点
    	struct OrthArcNode* tlink;//该弧结束的节点的下一条节点
    }OrthArcNode;
    
    typedef struct OrthVertexNode{//头节点
    	char* nodeinfo;//节点的信息|名字
    	struct OrthArcNode* firstin, *firstout;/*以该节点为出发点的第一条弧和以该节点为结束点的第一条弧*/
    }OrthVertexNode;
    
    typedef struct{//十字链表表示法的结构体
    	OrthVertexNode vertex[MAX];
    	int vernum, arcnum;//节点数量和弧的数量
    	GraphKind kind;//图的种类
    } OrthList;
    
    //创建一个邻接表表示法的图
    void CreateAdjGraph(AdjList * g, int len){
    	char* var;
    	int temp, i = 0, j = 0;
    	g->vernum = 0;
    	g->arcnum = 0;
    	for(int i = 0; i < len; i++){
    		 var = (char*)malloc(10);
    		scanf("%s", var);
    		struct VertexNode node = {var, NULL};
    		g->vertex[i] = node;
    		g->vernum++;
    	}
    	while(i != -1){
    		printf("please input arc-head\n");
    		scanf("%d", &i);
    		printf("please input arc-tail\n");
    		scanf("%d", &temp);
    		if(i > len || temp > len){
    			printf("crossed!please re-enter\n ");
    			continue;
    		}
    		struct ArcNode * arcnode = {temp, g->vertex[i].nextarc};
    		g->vertex[i].nextarc = arcnode;
    		g->arcnum++;
    	}
    }
    
    //创建一个十字链表表示法的图
    void CreateOrthGraph(OrthList *g, int len){
    	char* var;
    	int temp, i, j;
    	g->vernum = 0;
    	g->arcnum = 0;
    	for(int i = 0; i < len; i++){
    		var = (char*)malloc(10);
    		scanf("%s", var);
    		OrthVertexNode node = {var, NULL, NULL};
    		g->vertex[i] = node;
    		g->vernum++;
    	}
    	while(i != -1){
    		printf("please input arc-head\n");
    		scanf("%d", &i);
    		printf("please input arc-tail\n");
    		scanf("%d", &j);
    		if(i >= len || j >= len){
    			printf("crossed!please re-enter\n ");
    			continue;
    		}
    		if( i == -1){
    			break;
    		}
    		OrthArcNode * arcnode = (OrthArcNode *)malloc(sizeof(OrthArcNode));
    		arcnode->tailvex = j;
    		arcnode->headvex = i;
    		arcnode->tlink = g->vertex[j].firstout;
    		g->vertex[j].firstout = arcnode;
    		arcnode->hlink = g->vertex[i].firstin;
    		g->vertex[i].firstin = arcnode;
    		g->arcnum++;
    	}
    }
    
    //输出十字链表表示法的节点的信息|名称
    void PrintVer(OrthVertexNode vertex){
    	printf("%s ", vertex.nodeinfo);
    };
    
    void DepthFirstSearchOrth(OrthList *g,  int index,void (*visit)(OrthVertexNode vertex)){
    	visit(g->vertex[index]);
    	visited[index] = True;
    	OrthArcNode *p = g->vertex[index].firstin;
    	while(p != NULL){
    		if(!visited[p->tailvex]) DepthFirstSearchOrth(g, p->tailvex, visit);
    		p = p->hlink;
    	}
    }
    
    //深度遍历十字链表表示法的图
    void TraverseOrthGraph(OrthList *g, int len,void (*visit)(OrthVertexNode vertex)){
    	for(int i = 0; i< len; i++){
    		visited[i] = False;
    	}
    	for(int i = 0; i< len; i++){
    		if(!visited[i]) DepthFirstSearchOrth(g, i, visit);
    	}
    }
    
    
    

    未完待续

    展开全文
  • 对于每组数据第一行输入两个正整数n,m(0,m)表示矩阵的大小。 接下来有n行,每行m个整数h。 Output 对于每组输入输出一个整数表示容量。 Sample Input 1 4 4 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 ...
  • 你必须知道的495个C语言问题

    千次下载 热门讨论 2015-05-08 11:09:25
    1.3 因为C语言没有精确定义类型的大小,所以我一般都用typedef定义int16和int32。然后根据实际的机器环境把它们定义为int、short、long等类型。这样看来,所有的问题都解决了,是吗? 1.4 新的64位机上的64位类型...
  • 对于每组数据第一行输入两个正整数n,m(0,m)表示矩阵的大小。 接下来有n行,每行m个整数h。 Output 对于每组输入输出一个整数表示容量。 Sample Input 1 4 4 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 ...
  • 难道在C语言中一个结构不能包含指向自己的指针吗? o 2.7 怎样建立和理解非常复杂的声明?例如定义一个包含 N 个指向返回指向字符的指针的函数的指针的数组? o 2.8 函数只定义了一次, 调用了一次, 但编译器提示...
  • 度度熊是一只喜欢探险的熊,一次偶然落进了一个m*n矩阵的迷宫,该迷宫只能从矩阵左上角第一个方格开始走,只有走到右上角的第一个格子才算走出迷宫,每一次只能走一格,且只能向上向下向右走以前没有走过的格子,每...
  • 文本中还有一些不能走上去的位置,如上图中的石头,这些石头光标不管怎么样都没办法移动上去. 现在给你一段文本,要求你从起点位置按最少的按键将光标移动到终点位置. 其中ge算两次按键,大写字母如W可以按shift+w(算...
  • 《你必须知道的495个C语言问题》

    热门讨论 2010-03-20 16:41:18
    《你必须知道的495个C语言问题》以问答的形式组织内容,讨论了学习或使用C语言的过程中经常遇到的一些问题。书中列出了C用户经常问的400多个经典问题,涵盖了初始化、数组、指针、字符串、内存分配、库函数、C预...
  • 1.3 因为C语言没有精确定义类型的大小,所以我一般都用typedef定义int16和int32。然后根据实际的机器环境把它们定义为int、short、long等类型。这样看来,所有的问题都解决了,是吗? 2  1.4 新的64位机上的64位...
  • 你必须知道的495个C语言问题(PDF)

    热门讨论 2009-09-15 10:25:47
    难道在C语言中一个结构不能包含指向自己的指针吗? . . . . 3 1.7 怎样建立和理解非常复杂的声明?例如定义一个包含N 个指向返 回指向字符的指针的函数的指针的数组? . . . . . . . . . . . . . . 3 1.8 函数只定义...
  • matlab 已知二次函数系数 怎么画出二次函数图像x*x不正确,你是需要计算x的平方对吧,那么需要x.*x或者x.^2,点乘如果是x*x表示矩阵相乘,那么如果x是n*1的向量,[n*1]*[n*1]维度就不正确了画出它们的二次函数图像再答:y...

    matlab 已知二次函数系数 怎么画出二次函数图像

    x*x不正确,你是需要计算x的平方对吧,那么需要x.*x或者x.^2,点乘如果是x*x表示矩阵相乘,那么如果x是n*1的向量,[n*1]*[n*1]维度就不正确了

    画出它们的二次函数图像

    再答:y=kx^2,|k|越大,图像开口越小;相反|k|越小,图像开口越大。

    已知二次方程式函数图像,怎么画出对应的导数图像?

    1、二次函数的导数是一次函数,那么其导数的图像就是一根直线.对于直线就要确定两个关键的元素:斜率和一些特殊点(与坐标轴的交点)2、以开口向上的二次函数为例.对称轴处是函数的最小值,而且是极小值,那么该

    求初中一元二次函数的分类.图像.公式

    y=ax^2+bx+ca>0抛物线开口向上反之向下x=-b/2a为抛物线对称轴顶点坐标(-b/2a,(4ac-b^2)/4a)b^2-4ac0抛物线与x轴有两个交点两个交点x1,x2x1+x2=-b/

    1.在画出一个二次函数图像后,判断一些正误:a+c a>1怎么判断

    1没看明白2a1=-1/3a2=-3a3=a1a4=a2这是一个周期函数奇数项=-1/3偶数项=-3a2006=a2=-33配成顶点式y=2(x+m-1)^2-...后面的不重要然后他说x>2逐渐减小

    用c语言画数学函数图像(一次函数、二次函数、反比例函数)

    http://download.csdn.net/detail/himulakensin/5055276用c++写的(实际上和C区别不大,就用了类封装了一些成员函数,可以很简单改成C)

    “画出二次函数的图像”,“画出二次函数的大致图像”,“画出二次函数的草图”,这三种题目要求有什么区别?

    画出二次函数的图像是用尺子规矩的画画出二次函数的大致图像”,“画出二次函数的草图都是大致一画再问:要不要取很多值?取很多点,采用描点法?再答:不用,一般都是取5个,负的两个,正的两个,一个x=0

    用c语言绘制余弦函数图像

    没写过.graphics.h是TC里面的图形库,如果要用的话应该用TC来编译,VC++有他自己的另外图形库.分为:像素函数、直线和线型函数、多边形函数、填充函数等像素函数putpixel()画像素点函

    怎样用c语言解一元二次函数

    #include#includevoidmain(){floata,b,c,x1,x2,aif;while(scanf("%f%f%f",&a,&b,&c)){aif=b*b-4*a*c;if(aif

    在一个坐标系中画出这三个二次函数图像 该怎么取点啊

    第一个(0,0),(1,1),(-1,1),(2,4),(-2,4),(3,9),(-3,9)第二个(-2,0),(-1,1),(-3,1),(0,4),(-4,4),(1,9),(-5,9)第三个(

    已知一元二次函数的图像经过点A(1,6),B(2,5),C(-1,0)三点,求这个二次函数式

    一元二次函数的图像y=ax^+bx+c因为过A(1,6),B(2,5),C(-1,0)三点带入所以6=a+b+c①5=4a+2b+c②0=a-b+c③①*2-②7=-2a+c④①+③6=2a+2c3=

    怎么画一元二次方程的函数图像

    画一元二次方程的函数图像x²+x-2=y,顶点是(-1/2,0),于坐标轴的交点是(1,0)和(-2,0)开口向上的抛物线,对称轴是X=-1/2,

    如何用VB画出二次函数图像和波长图像

    在窗体上放置一个名为PicDraw的图片框,两个按钮,分别命名为CmdDrawQuad与CmdDrawWave,全部代码如下[VisualBasic6.0]:OptionExplicit'声明平面直角

    用matlab一元二次函数怎么解

    solve('a*x^2+b*x+c=0')ans=-1/2*(b-(b^2-4*a*c)^(1/2))/a-1/2*(b+(b^2-4*a*c)^(1/2))/a所以你如果带入直接的数字的话,出来的

    如何看图像解一元二次函数式

    根据抛物线的形状,开口方向,写出抛物线的通用函数表达式Y^2=±pX或X^2=±pY,然后在根据焦点坐标为(±p/2,0)或(0,±p/2)就可以了吧,焦点不在X轴或Y轴上就再平移一下焦点和交点可不一

    如何快速画出二次函数的图像

    设X为0求y列表设X为1等在图像上描点连线就ok了

    一元二次函数图像

    二次函数:y=ax^2+bx+c(a,b,c是常数,且a不等于0)a>0开口向上a0,ax^2+bx+c=0有两个不相等的实根b^2-4ac0)个单位,解析式为y=a(x+b/2a+d)^2+(4ac

    怎么画出反比例函数图像

    画出原函数的图像然后做关于Y=X对称的图像就是了

    二次函数y=-3x画出图像

    再问:我关键就是不会列表!再问:怎么列?再答:

    展开全文
  • 2019-07-02 23:04:45
    文章目录图什么是图抽象数据类型定义:怎么在程序中表示一个图:建立图的C语言实现:图的邻接矩阵表示法实现代码:图的邻接表表示法实现代码:图的遍历:DFS(Depth First Search):BFS(Breadth First Search):图不...

    什么是图

    1. 表示多对多的关系
    2. 包含:
    • 一组顶点:通常用V(Vertex)表示顶点集合
    • 一组边:通常用E(Edge)表示边的集合

    抽象数据类型定义:

    • 类型名称:
    • 数据对象集:G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成。
    • 操作集:对于任意图G\inGraph,以及v\inV,e\inE

    Graph Create():建立并返回空图;
    Graph InsertVertex(Graph G, Vertex v):将v插入G;
    Graph InsertEdge(Graph G, Edge e):将e插入G;
    void DFS(Graph G, Vertex v):从顶点v出发深度优先遍历图G;
    void BFS(Graph G, Vertex v):从顶点v出发宽度优先遍历图G;
    void Shortest Path(Graph G, Vertex v, int Dis[]):计算图G中顶点v到任意其他顶点的最短距离;
    void MST(Graph G):计算图G的最小生成树;

    怎么在程序中表示一个图:

    1. 邻接矩阵
      在这里插入图片描述
      在这里插入图片描述

    2. 邻接表:G[N]为指针数组,对应矩阵每行一个链表,只存非零元素

    在这里插入图片描述

    建立图的C语言实现:

    1. 用邻接矩阵表示图:思路
    • 图的定义
    typedef int WeightType;
    
    typedef struct GNode *PtrToGNode; // 指向GNode的指针
    struct GNode{
        int Nv; // 顶点数
        int Ne; // 边数
        WeightType G[MaxVertexNum][MaxVertexNum];
        DataType Data[MaxVertexNum]; // 存顶点的数据
    };
    typedef PtrToGNode MGraph; // MatrixGraph,以邻接矩阵存储的图类型
    
    • MGraph初始化
    // 初始化一个有VertexNum个顶点但没有边的图
    
    typedef int Vertex; //用顶点下标来表示顶点,为整型
    
    MGraph CreateGraph( int VertexNum )
    {
        Vertex V, W;
        MGraph Graph;
        
        Graph = (MGraph) malloc(sizeof(struct GNode));
        Graph->Nv = VertexNum;
        Graph->Ne = 0;
        
        // 这里默认顶点编号从0开始到(Graph->Nv-1)
        for ( V=0; V<Graph->Nv; V++)
            for ( W=0; W<Graph->Nv; W++)
                Graph->G[V][W] = 0; // 或INFINITY(有权图)
        
        return Graph;
    }
    
    • 向MGraph中插入边
    typedef struct ENode *PtrToENode;
    struct ENode{
        Vertex V1, V2; //有向边<V1,V2>
        WeightType Weight; //  权重
    };
    typedef PtrToENode Edge;
    
    void InsertEdge( MGraph Graph, Edge E )
    {
        // 插入边<V1,V2>
        Graph->G[E->V1][E->V2] = E->Weight;
        
        // 若是无向图,还要插入边<V2,V1>
        Graph->G[E->V2][E->V1] = E->Weight;
    }
    
    • 完整地建立一个MGraph
    // 输入格式:
    // Nv Ne
    // V1 V2 Weight
    // ...
    
    MGraph BuildGraph()
    {
        MGraph Graph;
        Edge E;
        Vertex V;
        int Nv, i;
        
        scanf("%d", &Nv);
        Graph = CreateGraph(Nv);
        scanf("%d", &(Graph->Ne));
        if (Graph->Ne != 0){
            E = (Edge) malloc(sizeof(struct ENode));
            for (i=0; i<Graph->Ne; i++)
                scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
            InsertEdge( Graph, E);
        }
        //如果顶点有数据的话,读入数据
        for (V=0; V<Graph->Nv ;V++)
            scanf("%c", &Graph->Data[V]);
        
        return Graph;
    }
    
    • 如果不要这么麻烦
    int G[MAXN][MAXN], Nv,Ne;
    void BuildGraph()
    {
        int i,j,v1,v2,w;
        scanf("%d",&Nv);
        for (i=0;i<Nv;i++)
            for(j=0;j<Nv;j++)
                G[i][j]=0;
        scanf("%d", &Ne);
        for (i=0;i<Ne;i++)
        {
            scanf("%d %d %d",&v1,&v2,&w);
            G[v1][v2]=w;
            G[v2][v1]=w;
        }
    }
    

    图的邻接矩阵表示法实现代码:

    /* 图的邻接矩阵表示法 */
     
    #define MaxVertexNum 100    /* 最大顶点数设为100 */
    #define INFINITY 65535        /* ∞设为双字节无符号整数的最大值65535*/
    typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
    typedef int WeightType;        /* 边的权值设为整型 */
    typedef char DataType;        /* 顶点存储的数据类型设为字符型 */
     
    /* 边的定义 */
    typedef struct ENode *PtrToENode;
    struct ENode{
        Vertex V1, V2;      /* 有向边<V1, V2> */
        WeightType Weight;  /* 权重 */
    };
    typedef PtrToENode Edge;
            
    /* 图结点的定义 */
    typedef struct GNode *PtrToGNode;
    struct GNode{
        int Nv;  /* 顶点数 */
        int Ne;  /* 边数   */
        WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
        DataType Data[MaxVertexNum];      /* 存顶点的数据 */
        /* 注意:很多情况下,顶点无数据,此时Data[]可以不用出现 */
    };
    typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
     
     
     
    MGraph CreateGraph( int VertexNum )
    { /* 初始化一个有VertexNum个顶点但没有边的图 */
        Vertex V, W;
        MGraph Graph;
         
        Graph = (MGraph)malloc(sizeof(struct GNode)); /* 建立图 */
        Graph->Nv = VertexNum;
        Graph->Ne = 0;
        /* 初始化邻接矩阵 */
        /* 注意:这里默认顶点编号从0开始,到(Graph->Nv - 1) */
        for (V=0; V<Graph->Nv; V++)
            for (W=0; W<Graph->Nv; W++)  
                Graph->G[V][W] = INFINITY;
                 
        return Graph; 
    }
            
    void InsertEdge( MGraph Graph, Edge E )
    {
         /* 插入边 <V1, V2> */
         Graph->G[E->V1][E->V2] = E->Weight;    
         /* 若是无向图,还要插入边<V2, V1> */
         Graph->G[E->V2][E->V1] = E->Weight;
    }
     
    MGraph BuildGraph()
    {
        MGraph Graph;
        Edge E;
        Vertex V;
        int Nv, i;
         
        scanf("%d", &Nv);   /* 读入顶点个数 */
        Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */ 
         
        scanf("%d", &(Graph->Ne));   /* 读入边数 */
        if ( Graph->Ne != 0 ) { /* 如果有边 */ 
            /* 读入边,格式为"起点 终点 权重",插入邻接矩阵 */
            for (i=0; i<Graph->Ne; i++) {
                E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */ 
                scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); 
                /* 注意:如果权重不是整型,Weight的读入格式要改 */
                InsertEdge( Graph, E );
            }
        } 
     
        /* 如果顶点有数据的话,读入数据 */
        for (V=0; V<Graph->Nv; V++) 
            scanf(" %c", &(Graph->Data[V]));
     
        return Graph;
    }
    
    1. 图的邻接表表示法
    • 定义
    // 图结点的定义
    typedef struct GNode *PtrToGNode;
    struct GNode{
        int Nv; // 顶点数
        int Ne; // 边数
        AdjList G; // 邻接表
    };
    typedef PtrToGNode LGraph; // 以邻接表方式存储的图类型
    
    // 邻接点的定义
    typedef struct AdjVNode *PtrToAdjVNode;
    struct AdjVNode{
        Vertex AdjV; // 邻接点下标
        WeightType Weight; //边权重
        PtrToAdjVNode Next;
    };
    
    // 顶点表头结点的定义
    typedef struct VNode{
        PtrToAdjVNode FirstEdge;
        DataType Data; // 存顶点的数据
    } AdjList[MaxVertexNum]; // AdjList是邻接表类型
    
    • LGraph 初始化
    typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
    LGraph CreateGraph ( int VertexNum )
    {
        Vertex V ;
        LGraph Graph;
        
        Graph = (LGraph) malloc(sizeof(struct GNode));
        Graph->Nv = VertexNum;
        Graph->Ne = 0;
        
        // 注意:这里默认顶点编号从0开始,到Graph->Nv-1
        for(V=0;V<Graph->Nv;V++)
            Graph->G[V].FirstEdge = NULL;
        
        return Graph;
    }
    
    • 向LGraph中插入边
    typedef struct ENode *PtrToENode;
    struct ENode{
        Vertex V1, V2;      /* 有向边<V1, V2> */
        WeightType Weight;  /* 权重 */
    };
    typedef PtrToENode Edge;
    
    void InsertEdge( LGraph Graph, Edge E )
    {
        PtrToAdjVNode NewNode;
        /************* 插入边<V1,V2>**********/
        // 为V2建立新的邻接点
        NewNode = (PtrToAdjVNode) malloc(sizeof(struct AdjVNode));
        NewNode->AdjV = E->V2;
        NewNode->Weight = E->Weight;
        // 将V2插入V1的表头
        NewNode->Next = Graph->G[E->V1].FirstEdge;
        Graph->G[E->V1].FirstEdge = NewNode;
        
        /* 若是无向图,还要插入边 <V2, V1> */
        /* 为V1建立新的邻接点 */
        NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
        NewNode->AdjV = E->V1;
        NewNode->Weight = E->Weight;
        /* 将V1插入V2的表头 */
        NewNode->Next = Graph->G[E->V2].FirstEdge;
        Graph->G[E->V2].FirstEdge = NewNode;
    }
    
    • 完整地一个建立一个LGraph

    图的邻接表表示法实现代码:

    /* 图的邻接表表示法 */
     
    #define MaxVertexNum 100    /* 最大顶点数设为100 */
    typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
    typedef int WeightType;        /* 边的权值设为整型 */
    typedef char DataType;        /* 顶点存储的数据类型设为字符型 */
     
    /* 边的定义 */
    typedef struct ENode *PtrToENode;
    struct ENode{
        Vertex V1, V2;      /* 有向边<V1, V2> */
        WeightType Weight;  /* 权重 */
    };
    typedef PtrToENode Edge;
     
    /* 邻接点的定义 */
    typedef struct AdjVNode *PtrToAdjVNode; 
    struct AdjVNode{
        Vertex AdjV;        /* 邻接点下标 */
        WeightType Weight;  /* 边权重 */
        PtrToAdjVNode Next;    /* 指向下一个邻接点的指针 */
    };
     
    /* 顶点表头结点的定义 */
    typedef struct Vnode{
        PtrToAdjVNode FirstEdge;/* 边表头指针 */
        DataType Data;            /* 存顶点的数据 */
        /* 注意:很多情况下,顶点无数据,此时Data可以不用出现 */
    } AdjList[MaxVertexNum];    /* AdjList是邻接表类型 */
     
    /* 图结点的定义 */
    typedef struct GNode *PtrToGNode;
    struct GNode{  
        int Nv;     /* 顶点数 */
        int Ne;     /* 边数   */
        AdjList G;  /* 邻接表 */
    };
    typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */
     
     
     
    LGraph CreateGraph( int VertexNum )
    { /* 初始化一个有VertexNum个顶点但没有边的图 */
        Vertex V;
        LGraph Graph;
         
        Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立图 */
        Graph->Nv = VertexNum;
        Graph->Ne = 0;
        /* 初始化邻接表头指针 */
        /* 注意:这里默认顶点编号从0开始,到(Graph->Nv - 1) */
           for (V=0; V<Graph->Nv; V++)
            Graph->G[V].FirstEdge = NULL;
                 
        return Graph; 
    }
            
    void InsertEdge( LGraph Graph, Edge E )
    {
        PtrToAdjVNode NewNode;
         
        /* 插入边 <V1, V2> */
        /* 为V2建立新的邻接点 */
        NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
        NewNode->AdjV = E->V2;
        NewNode->Weight = E->Weight;
        /* 将V2插入V1的表头 */
        NewNode->Next = Graph->G[E->V1].FirstEdge;
        Graph->G[E->V1].FirstEdge = NewNode;
             
        /* 若是无向图,还要插入边 <V2, V1> */
        /* 为V1建立新的邻接点 */
        NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
        NewNode->AdjV = E->V1;
        NewNode->Weight = E->Weight;
        /* 将V1插入V2的表头 */
        NewNode->Next = Graph->G[E->V2].FirstEdge;
        Graph->G[E->V2].FirstEdge = NewNode;
    }
     
    LGraph BuildGraph()
    {
        LGraph Graph;
        Edge E;
        Vertex V;
        int Nv, i;
         
        scanf("%d", &Nv);   /* 读入顶点个数 */
        Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */ 
         
        scanf("%d", &(Graph->Ne));   /* 读入边数 */
        if ( Graph->Ne != 0 ) { /* 如果有边 */ 
            E = (Edge)malloc( sizeof(struct ENode) ); /* 建立边结点 */ 
            /* 读入边,格式为"起点 终点 权重",插入邻接矩阵 */
            for (i=0; i<Graph->Ne; i++) {
                scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); 
                /* 注意:如果权重不是整型,Weight的读入格式要改 */
                InsertEdge( Graph, E );
            }
        } 
     
        /* 如果顶点有数据的话,读入数据 */
        for (V=0; V<Graph->Nv; V++) 
            scanf(" %c", &(Graph->G[V].Data));
     
        return Graph;
    }
    

    图的遍历:

    DFS(Depth First Search):

    类似于树的先序遍历。

    void DFS ( Vertex V )
    {
        visited[ V ] = true;
        for ( V 的每个临接点W )
            if ( !visited[W] )
                DFS( W );
    }
    

    若有N个顶点、N条边,时间复杂度是:

    • 用邻接表存储图,有O(N+E) (每个点访问了一次,每条边访问了一次)
    • 用邻接矩阵存储图,有O(N2N^2)

    BFS(Breadth First Search):

    类似于树的层序遍历。

    void BFS( Vertex V )
    {
        visited[V] = true;
        Enqueue( V, Q );
        while ( !IsEmpty(Q) ){
            V = Dequeue(Q);
            for ( V 的每个邻接点W ){
                visited[W] = true;
                Enqueue( W, Q );
            }
        }
    }
    

    若有N个顶点、E条边,时间复杂度是:

    • 用邻接表存储图,有O(N+E) (每个点访问了一次,每条边访问了一次)
    • 用邻接矩阵存储图,有O(N2N^2)

    图不连通

    连通
    路径/简单路径
    回路
    连通图
    连通分量:无向图的极大连通子图
    强连通
    强连通图
    强连通分量:有向图的极大强连通子图

    void ListComponents ( Graph G )
    {
        for ( each V in G )
            if ( !visited[V] )
                DFS( V ); /* or BFS(V) */
    }
    
    /* 邻接表存储的图 - DFS */
     
    void Visit( Vertex V )
    {
        printf("正在访问顶点%d\n", V);
    }
     
    /* Visited[]为全局变量,已经初始化为false */
    void DFS( LGraph Graph, Vertex V, void (*Visit)(Vertex) )
    {   /* 以V为出发点对邻接表存储的图Graph进行DFS搜索 */
        PtrToAdjVNode W;
         
        Visit( V ); /* 访问第V个顶点 */
        Visited[V] = true; /* 标记V已访问 */
     
        for( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
            if ( !Visited[W->AdjV] )    /* 若W->AdjV未被访问 */
                DFS( Graph, W->AdjV, Visit );    /* 则递归访问之 */
    }
    
    /* 邻接矩阵存储的图 - BFS */
     
    /* IsEdge(Graph, V, W)检查<V, W>是否图Graph中的一条边,即W是否V的邻接点。  */
    /* 此函数根据图的不同类型要做不同的实现,关键取决于对不存在的边的表示方法。*/
    /* 例如对有权图, 如果不存在的边被初始化为INFINITY, 则函数实现如下:         */
    bool IsEdge( MGraph Graph, Vertex V, Vertex W )
    {
        return Graph->G[V][W]<INFINITY ? true : false;
    }
     
    /* Visited[]为全局变量,已经初始化为false */
    void BFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) )
    {   /* 以S为出发点对邻接矩阵存储的图Graph进行BFS搜索 */
        Queue Q;     
        Vertex V, W;
     
        Q = CreateQueue( MaxSize ); /* 创建空队列, MaxSize为外部定义的常数 */
        /* 访问顶点S:此处可根据具体访问需要改写 */
        Visit( S );
        Visited[S] = true; /* 标记S已访问 */
        AddQ(Q, S); /* S入队列 */
         
        while ( !IsEmpty(Q) ) {
            V = DeleteQ(Q);  /* 弹出V */
            for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
                /* 若W是V的邻接点并且未访问过 */
                if ( !Visited[W] && IsEdge(Graph, V, W) ) {
                    /* 访问顶点W */
                    Visit( W );
                    Visited[W] = true; /* 标记W已访问 */
                    AddQ(Q, W); /* W入队列 */
                }
        } /* while结束*/
    }
    

    列出连通集

    给定一个有NN个顶点和EE条边的无向图,请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N1N−1编号。进行搜索时,假设我们总是从编号最小的顶点出发,按编号递增的顺序访问邻接点。

    输入格式:

    输入第1行给出2个整数N(0&lt;N10)N(0&lt;N≤10)和E,分别是图的顶点数和边数。随后EE行,每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

    输出格式:

    按照"{ v1v_1 v2v_2vkv_k }"的格式,每行输出一个连通集。先输出DFS的结果,再输出BFS的结果。

    输入样例:

    8 6
    0 7
    0 1
    2 0
    4 1
    2 4
    3 5
    

    输出样例:

    { 0 1 4 2 7 }
    { 3 5 }
    { 6 }
    { 0 1 2 7 4 }
    { 3 5 }
    { 6 }
    

    代码:

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MaxVertexNum 10
    
    typedef struct GNode *PtrToGNode;
    
    struct GNode{
        int Nv;
        int Ne;
        int G[MaxVertexNum][MaxVertexNum];
    };
    
    typedef PtrToGNode MGraph;
    
    typedef int Vertex;
    
    typedef struct ENode *PtrToENode;
    
    struct ENode{
        Vertex V1,V2;
    };
    
    typedef PtrToENode Edge;
    
    int DFSVisited[MaxVertexNum];
    int BFSVisited[MaxVertexNum];
    
    
    // 链表的头插入与删除均可,但链表的尾部只适合插入(删除找不到前一个结点在哪里),故而尾部Rear
    typedef int ElementType;
    typedef int Position;
    
    struct QNode {
        ElementType *Data;     /* 存储元素的数组 */
        Position Front, Rear;  /* 队列的头、尾指针 */
        int MaxSize;           /* 队列最大容量 */
    };
    typedef struct QNode *Queue;
    
    Queue CreateQueue( int MaxSize )
    {
        Queue Q = (Queue)malloc(sizeof(struct QNode));
        Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
        Q->Front = Q->Rear = 0;
        Q->MaxSize = MaxSize;
        return Q;
    }
    
    int IsFull( Queue Q )
    {
        return ((Q->Rear+1)%Q->MaxSize == Q->Front);
    }
    
    int AddQ( Queue Q, ElementType X )
    {
        Q->Rear = (Q->Rear+1)%Q->MaxSize;
        Q->Data[Q->Rear] = X;
        return 1;
    }
    
    int IsEmpty( Queue Q )
    {
        return (Q->Front == Q->Rear);
    }
    
    ElementType DeleteQ( Queue Q )
    {
        Q->Front =(Q->Front+1)%Q->MaxSize;
        return  Q->Data[Q->Front];
    }
    
    
    
    
    
    MGraph CreateGraph( int VertexNum )
    {
        Vertex V, W;
        MGraph Graph;
        
        Graph = (MGraph) malloc(sizeof(struct GNode));
        Graph->Nv = VertexNum;
        Graph->Ne = 0;
        
        for ( V=0; V<Graph->Nv; V++ )
            for ( W=0; W<Graph->Nv; W++ )
                Graph->G[V][W] = 0;
        
        return Graph;
    }
    
    
    
    void InsertEdge( MGraph Graph, Edge E )
    {
        Graph->G[E->V1][E->V2] = 1;
        Graph->G[E->V2][E->V1] = 1;
    }
    
    MGraph BuildGraph()
    {
        MGraph Graph;
        Edge E;
        int Nv, i;
        
        scanf("%d", &Nv);
        Graph = CreateGraph(Nv);
        scanf("%d", &Graph->Ne);
        if ( Graph->Ne != 0 ){
            for ( i=0; i<Graph->Ne; i++ )
            {
                E = (Edge) malloc(sizeof(struct ENode));
                scanf("%d %d", &E->V1, & E->V2 );
                InsertEdge( Graph, E );
            }
        }
        
        return Graph;
    }
    
    void PrintGraph( MGraph Graph )
    {
        Vertex V ,W;
        for ( V=0; V<Graph->Nv; V++ )
            for ( W=0; W<Graph->Nv; W++ )
                printf("Graph->G[%d][%d] = %d\n", V, W, Graph->G[V][W]);
    }
    
    int IsEdge( MGraph Graph, Vertex V, Vertex W )
    {
        return Graph->G[V][W];
    }
    
    void Visit( Vertex V )
    {
        printf(" %d", V);
    }
    
    void BFS( MGraph Graph, Vertex S )
    {
        // 以S为出发点堆邻接矩阵存储的图Graph进行BFS搜索
        Queue Q;
        Vertex V, W;
        
        Q = CreateQueue( MaxVertexNum );
        
        Visit (S);
        BFSVisited[S] = 1;
        AddQ(Q,S);
        
        while ( !IsEmpty(Q) ){
            V = DeleteQ(Q);
            for ( W=0; W<Graph->Nv; W++)
            {
                if ( !BFSVisited[W] && IsEdge(Graph, V, W))
                {
                    Visit( W);
                    BFSVisited[W] = 1;
                    AddQ(Q, W);
                }
            }
        }
    }
    
    void DFS( MGraph Graph, Vertex S )
    {
        Vertex W;
        Visit(S);
        DFSVisited[S] = 1;
        
        for ( W=0; W<Graph->Nv; W++ )
        {
            if ( S!=W && !DFSVisited[W] && IsEdge( Graph, S, W ) )
                DFS(Graph, W);
        }
    }
    
    
    void ListComponentsBFS ( MGraph Graph )
    {
        int V;
        for ( V=0; V<Graph->Nv; V++ )
        {
            if ( !BFSVisited[V] )
            {
                printf("{");
                BFS(Graph, V);
                printf(" }");
                printf("\n");
            }
        }
    }
    
    
    void ListComponentsDFS ( MGraph Graph )
    {
        int V;
        for ( V=0; V<Graph->Nv; V++ )
        {
            if ( !DFSVisited[V] )
            {
                printf("{");
                DFS(Graph, V);
                printf(" }");
                printf("\n");
            }
        }
    }
    
    
    
    int main()
    {
        MGraph Graph;
        
        Graph = BuildGraph();
        
        ListComponentsDFS ( Graph );
        ListComponentsBFS ( Graph );
    }
    

    Saving James Bond - Easy Version

    This time let us consider the situation in the movie “Live and Let Die” in which James Bond, the world’s most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape – he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head… Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).

    Assume that the lake is a 100 by 100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him whether or not he can escape.

    Input Specification:

    Each input file contains one test case. Each case starts with a line containing two positive integers N(100)N (≤100), the number of crocodiles, and DD, the maximum distance that James could jump. Then NN lines follow, each containing the (x,y)(x,y) location of a crocodile. Note that no two crocodiles are staying at the same position.

    Output Specification:

    For each test case, print in a line “Yes” if James can escape, or “No” if not.

    Sample Input 1:

    14 20
    25 -15
    -25 28
    8 49
    29 15
    -35 -2
    5 28
    27 -29
    -8 -28
    -20 -35
    -25 -20
    -13 29
    -30 15
    -35 40
    12 12
    

    Sample Output 1:

    Yes
    

    Sample Input 2:

    4 13
    -12 12
    12 12
    -12 -12
    12 -12
    

    Sample Output 2:

    No
    

    代码:

    这里没有采用邻接表或者邻接矩阵的方法存储图,而是采用一个结构体数组(包含横纵坐标)来存储图。此外,解决此题需要考虑到第一跳,与实际边界情况的问题。

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    #define MaxVertexNum 100
    
    typedef int Position;
    
    typedef struct GNode Vertex;
    
    struct GNode{
        Position x;
        Position y;
    }Graph[MaxVertexNum];
    
    
    int Visited[MaxVertexNum];
    
    int Jump( int i, int j ,int distance )
    {
        return pow(Graph[i].x-Graph[j].x,2) + pow(Graph[i].y-Graph[j].y,2) <= distance*distance;
    }
    
    int FirstJump( int i, int distance )
    {
        return pow(Graph[i].x,2)+pow(Graph[i].y,2) <= pow(distance+7.5,2);
    }
    
    int IsSafe( int i, int distance )
    {
        return(pow(Graph[i].x-50,2)<=pow(distance,2) ||
               pow(Graph[i].x+50,2)<=pow(distance,2) ||
               pow(Graph[i].y+50,2)<=pow(distance,2) ||
               pow(Graph[i].y-50,2)<=pow(distance,2) );
    }
    
    int DFS( int i ,int distance, int N)
    {
        int answer = 0;
        Visited[i] = 1;
        int j;
        if ( IsSafe(i, distance) ) answer = 1;
        else
        {
            for ( j=0; j<N; j++ )
                if ( !Visited[j] && Jump(i,j,distance) ){
                    answer = DFS(j,distance,N);
                    if (answer) break;
                }
        }
        return answer;
    }
    
    void Save007( int N ,int distance)
    {
        int i;
        int answer = 0;
        for ( i=0; i<N; i++ ){
            if ( !Visited[i] && FirstJump(i,distance) ){
                answer = DFS(i,distance, N);
                if (answer ) break;
            }
        }
        if (answer) printf("Yes\n");
        else printf("No\n");
    }
    
    int main()
    {
        int i, N, D;
        scanf("%d", &N);
        scanf("%d", &D);
        for ( i=0; i<N; i++)
            scanf("%d %d", &Graph[i].x, &Graph[i].y);
        Save007(N,D);
    }
    

    六度空间

    “六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如图所示。
    在这里插入图片描述
    “六度空间”理论虽然得到广泛的认同,并且正在得到越来越多的应用。但是数十年来,试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因,这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具,能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。

    假如给你一个社交网络图,请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。

    输入格式:

    输入第1行给出两个正整数,分别表示社交网络图的结点数NN1&lt;N1041&lt;N≤10^4​​,表示人数)、边数MM33×N≤33×N,表示社交关系数)。随后的MM对应MM条边,每行给出一对正整数,分别是该条边直接连通的两个结点的编号(节点从11NN编号)。

    输出格式:

    对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比,精确到小数点后2位。每个结节点输出一行,格式为“结点编号:(空格)百分比%”。
    输出格式:

    输入样例:

    10 9
    1 2
    2 3
    3 4
    4 5
    5 6
    6 7
    7 8
    8 9
    9 10
    

    输出样例:

    1: 70.00%
    2: 80.00%
    3: 90.00%
    4: 100.00%
    5: 100.00%
    6: 100.00%
    7: 100.00%
    8: 90.00%
    9: 80.00%
    10: 70.00%
    

    算法思路:

    • 对每个结点,进行BFS
    • 搜索过程中累计访问的结点数
    • 需要记录“层”数,仅计算6层以内的结点数

    在这里插入图片描述

    代码:

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MaxVerTexNum 10000
    
    typedef int Vertex;
    
    typedef struct ENode *PtrToENode;
    struct ENode{
        Vertex V1,V2;
    };
    typedef PtrToENode Edge;
    
    typedef struct GNode *PtrToGNode;
    struct GNode{
        int Nv;
        int Ne;
        int G[MaxVerTexNum][MaxVerTexNum];
    };
    typedef PtrToGNode MGraph;
    
    int Visited[MaxVerTexNum];
    
    MGraph CreateGraph( int VertexNum )
    {
        MGraph Graph;
        
        Graph = (MGraph) malloc(sizeof(struct GNode));
        Graph->Nv = VertexNum;
        Graph->Ne = 0;
        
        return Graph;
    }
    
    void InsertEdge( MGraph Graph, Edge E )
    {
        Graph->G[E->V1][E->V2] = 1;
        Graph->G[E->V2][E->V1] = 1;
    }
    
    MGraph BuildGraph()
    {
        MGraph Graph;
        Edge E;
        int Nv, i;
        
        scanf("%d", &Nv);
        Graph = CreateGraph( Nv);
        scanf("%d", &Graph->Ne);
        if (Graph->Ne !=0 )
            for ( i=0; i<Graph->Ne; i++ ){
                E = (Edge) malloc(sizeof(struct ENode));
                for ( i=0; i<Graph->Ne; i++ ){
                    scanf("%d %d", &E->V1, &E->V2);
                    E->V1--;
                    E->V2--; // 结点从1开始编号
                    InsertEdge( Graph, E );
                }
            }
        return Graph;
    }
    
    
    typedef int Position;
    typedef int ElementType;
    struct QNode {
        ElementType *Data;     /* 存储元素的数组 */
        Position Front, Rear;  /* 队列的头、尾指针 */
        int MaxSize;           /* 队列最大容量 */
    };
    typedef struct QNode *Queue;
    
    Queue CreateQueue( int MaxSize )
    {
        Queue Q = (Queue)malloc(sizeof(struct QNode));
        Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
        Q->Front = Q->Rear = 0;
        Q->MaxSize = MaxSize;
        return Q;
    }
    
    int IsFull( Queue Q )
    {
        return ((Q->Rear+1)%Q->MaxSize == Q->Front);
    }
    
    int AddQ( Queue Q, ElementType X )
    {
        Q->Rear = (Q->Rear+1)%Q->MaxSize;
        Q->Data[Q->Rear] = X;
        return 1;
    }
    
    int IsEmpty( Queue Q )
    {
        return (Q->Front == Q->Rear);
    }
    
    ElementType DeleteQ( Queue Q )
    {
        Q->Front =(Q->Front+1)%Q->MaxSize;
        return  Q->Data[Q->Front];
    }
    
    int IsEdge( Vertex V, Vertex W, MGraph Graph )
    {
        return Graph->G[V][W];
    }
    
    int BFS( MGraph Graph, Vertex V )
    {
        int count, level, last, tail;
        Vertex W;
        Queue Q = CreateQueue(MaxVerTexNum);
        Visited[V] = 1; count = 1;
        level = 0; last = V;
        AddQ(Q,V);
        while ( !IsEmpty(Q)){
            V = DeleteQ(Q);
            for ( W=0; W<Graph->Nv; W++ ){
                if ( !Visited[W] && IsEdge(V,W,Graph) ){
                    Visited[W] = 1;
                    AddQ(Q,W);
                    count++;
                    tail = W;
                }
            }
            if (V==last){
                level++;
                last = tail;
            }
            if ( level==6 ) break;
        }
        return count;
    }
    
    void SDS(MGraph Graph)
    {
        double count;
        double result;
        Vertex V, W;
        for ( V=0; V<Graph->Nv; V++){
            for (W=0; W<Graph->Nv; W++)
                Visited[W]=0;
            count = BFS(Graph, V);
            result = 100*count/Graph->Nv;
            printf("%d: %.2f%%\n",V+1,result);
        }
    }
    
    int main()
    {
        MGraph Graph;
        Graph = BuildGraph();
        SDS(Graph);
    }
    

    最短路径问题

    问题分类

    1. 单源最短路径问题:从某固定源点出发,求其道所有其他顶点的最短路径
    • 无权图
    • 有权图
    1. 多源最短路径问题:求任意两顶点间的最短路径

    无权图的单源最短路算法

    思路:按照递增(非递减)的顺序找出各个顶点的最短路(从路径长度为0,到路径长度为1、2、…)
    在这里插入图片描述

    有权图的单源最短路算法

    按照递增的顺序找出各个顶点的最短路— Djikstra算法

    Djikstra算法

    1. 令S={源点s+已经确定了最短路径的顶点vi_i}
    2. 对任一未收录的顶点v,定义dist[v]为s到v的最短路径长,但该路径仅经过S中的顶点但不一定是最终的最短路!)。即路径{s\rightarrow(vi_i\inS)\rightarrowv}的最小长度
    3. 若路径是按照递增的顺序生成的,则
    • 对于已经收进S的顶点,到该顶点真正的最短路必须只经过S中的顶点(反证法:假如把下一个v收进集合S时,从s到v存在另外一个点w,从s到v需从s到w再从w到v,则s到w的距离小于s到v的距离,而v是下一个要收进去的顶点,这矛盾了!)
    • 每次从未收录的顶点中选一个dist最小的收录(贪心)
    • 增加一个v进入S,可能影响另外一个w的dist值(如果收录v使得s到w的路径变短,则s到w的路径一定经过v,并且v到w有一条边(如果v到w之间还有另外一个顶点,则此顶点到源点的距离一定比v到源点的距离大,但w的dist值是s到w仅仅经过集合S里面的顶点的路径长度,如果另外有一个结点在v后面话,则该顶点不可能在S里面,因为v是新增进去的,所以v是集合里面dist最长的)–从而只需检查更新新增顶点的邻接点的dist值–dist[w] = min{dist[w], dist[v]+<v,w>的权重}
      在这里插入图片描述在这里插入图片描述

    多源最短路算法

    在这里插入图片描述

    Floyd算法

    1. Dk[i][j]D^k[i][j] = 路径{i{lk}j}\{i\rightarrow\{l\leq k\}\rightarrow j\}的最小长度
    2. D0D1,...,DV1[i][j]D^0D^1,...,D^{|V|-1}[i][j]即给出了iijj的真正最短距离
    3. 最初的D1D^{-1}:邻接矩阵,对角元为0
    4. Dk1D^{k-1}已经完成,递推到DkD^k时:
    • 或者kk\notin最短路径{i{lk}j}\{i\rightarrow\{l\leq k\}\rightarrow j\},则Dk=Dk1D^k=D^{k-1}
    • 或者kk\in最短路径{i{lk}j}\{i\rightarrow\{l\leq k\}\rightarrow j\},则该路径必定由两段最短路径组成:Dk[i][j]=Dk1[i][k]+Dk1[k][j]D^k[i][j]=D^{k-1}[i][k]+D^{k-1}[k][j]

    在这里插入图片描述

    /* 邻接表存储 - 无权图的单源最短路算法 */
     
    /* dist[]和path[]全部初始化为-1 */
    void Unweighted ( LGraph Graph, int dist[], int path[], Vertex S )
    {
        Queue Q;
        Vertex V;
        PtrToAdjVNode W;
         
        Q = CreateQueue( Graph->Nv ); /* 创建空队列, MaxSize为外部定义的常数 */
        dist[S] = 0; /* 初始化源点 */
        AddQ (Q, S);
     
        while( !IsEmpty(Q) ){
            V = DeleteQ(Q);
            for ( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
                if ( dist[W->AdjV]==-1 ) { /* 若W->AdjV未被访问过 */
                    dist[W->AdjV] = dist[V]+1; /* W->AdjV到S的距离更新 */
                    path[W->AdjV] = V; /* 将V记录在S到W->AdjV的路径上 */
                    AddQ(Q, W->AdjV);
                }
        } /* while结束*/
    }
    
    /* 邻接矩阵存储 - 有权图的单源最短路算法 */
     
    Vertex FindMinDist( MGraph Graph, int dist[], int collected[] )
    { /* 返回未被收录顶点中dist最小者 */
        Vertex MinV, V;
        int MinDist = INFINITY;
     
        for (V=0; V<Graph->Nv; V++) {
            if ( collected[V]==false && dist[V]<MinDist) {
                /* 若V未被收录,且dist[V]更小 */
                MinDist = dist[V]; /* 更新最小距离 */
                MinV = V; /* 更新对应顶点 */
            }
        }
        if (MinDist < INFINITY) /* 若找到最小dist */
            return MinV; /* 返回对应的顶点下标 */
        else return ERROR;  /* 若这样的顶点不存在,返回错误标记 */
    }
     
    bool Dijkstra( MGraph Graph, int dist[], int path[], Vertex S )
    {
        int collected[MaxVertexNum];
        Vertex V, W;
     
        /* 初始化:此处默认邻接矩阵中不存在的边用INFINITY表示 */
        for ( V=0; V<Graph->Nv; V++ ) {
            dist[V] = Graph->G[S][V];
            if ( dist[V]<INFINITY )
                path[V] = S;
            else
                path[V] = -1;
            collected[V] = false;
        }
        /* 先将起点收入集合 */
        dist[S] = 0;
        collected[S] = true;
     
        while (1) {
            /* V = 未被收录顶点中dist最小者 */
            V = FindMinDist( Graph, dist, collected );
            if ( V==ERROR ) /* 若这样的V不存在 */
                break;      /* 算法结束 */
            collected[V] = true;  /* 收录V */
            for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
                /* 若W是V的邻接点并且未被收录 */
                if ( collected[W]==false && Graph->G[V][W]<INFINITY ) {
                    if ( Graph->G[V][W]<0 ) /* 若有负边 */
                        return false; /* 不能正确解决,返回错误标记 */
                    /* 若收录V使得dist[W]变小 */
                    if ( dist[V]+Graph->G[V][W] < dist[W] ) {
                        dist[W] = dist[V]+Graph->G[V][W]; /* 更新dist[W] */
                        path[W] = V; /* 更新S到W的路径 */
                    }
                }
        } /* while结束*/
        return true; /* 算法执行完毕,返回正确标记 */
    }
    
    /* 邻接矩阵存储 - 多源最短路算法 */
     
    bool Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] )
    {
        Vertex i, j, k;
     
        /* 初始化 */
        for ( i=0; i<Graph->Nv; i++ )
            for( j=0; j<Graph->Nv; j++ ) {
                D[i][j] = Graph->G[i][j];
                path[i][j] = -1;
            }
     
        for( k=0; k<Graph->Nv; k++ )
            for( i=0; i<Graph->Nv; i++ )
                for( j=0; j<Graph->Nv; j++ )
                    if( D[i][k] + D[k][j] < D[i][j] ) {
                        D[i][j] = D[i][k] + D[k][j];
                        if ( i==j && D[i][j]<0 ) /* 若发现负值圈 */
                            return false; /* 不能正确解决,返回错误标记 */
                        path[i][j] = k;
                    }
        return true; /* 算法执行完毕,返回正确标记 */
    }
    

    哈利·波特的考试

    哈利·波特要考试了,他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha,将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念,例如ahah可以将老鼠变成猫。另外,如果想把猫变成鱼,可以通过念一个直接魔咒lalala,也可以将猫变老鼠、老鼠变鱼的魔咒连起来念:hahahehe。

    现在哈利·波特的手里有一本教材,里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场,要考察他把这只动物变成任意一只指定动物的本事。于是他来问你:带什么动物去可以让最难变的那种动物(即该动物变为哈利·波特自己带去的动物所需要的魔咒最长)需要的魔咒最短?例如:如果只有猫、鼠、鱼,则显然哈利·波特应该带鼠去,因为鼠变成另外两种动物都只需要念4个字符;而如果带猫去,则至少需要念6个字符才能把猫变成鱼;同理,带鱼去也不是最好的选择。

    输入格式:

    输入说明:输入第1行给出两个正整数N(100)N (≤100)MM,其中NN是考试涉及的动物总数,MM是用于直接变形的魔咒条数。为简单起见,我们将动物按1 N1~N编号。随后MM行,每行给出了3个正整数,分别是两种动物的编号、以及它们之间变形需要的魔咒的长度(100)(≤100),数字之间用空格分隔。

    输出格式:

    输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度,中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的,则输出0。如果有若干只动物都可以备选,则输出编号最小的那只。

    输入样例:

    6 11
    3 4 70
    1 2 1
    5 4 50
    2 6 50
    5 6 60
    1 3 70
    4 6 60
    3 6 80
    5 1 100
    2 4 60
    5 2 80
    

    输出样例:

    4 70
    

    分析:在这里插入图片描述
    在这里插入图片描述

    代码:

    #include <stdio.h>
    #include <stdlib.h>
    
    /* 图的邻接矩阵表示法 */
    
    #define MaxVertexNum 100    /* 最大顶点数设为100 */
    #define INFINITY 65535        /* ∞设为双字节无符号整数的最大值65535*/
    typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
    typedef int WeightType;        /* 边的权值设为整型 */
    
    /* 边的定义 */
    typedef struct ENode *PtrToENode;
    struct ENode{
        Vertex V1, V2;      /* 有向边<V1, V2> */
        WeightType Weight;  /* 权重 */
    };
    typedef PtrToENode Edge;
    
    /* 图结点的定义 */
    typedef struct GNode *PtrToGNode;
    struct GNode{
        int Nv;  /* 顶点数 */
        int Ne;  /* 边数   */
        WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
    };
    typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
    
    
    
    MGraph CreateGraph( int VertexNum )
    { /* 初始化一个有VertexNum个顶点但没有边的图 */
        Vertex V, W;
        MGraph Graph;
        
        Graph = (MGraph)malloc(sizeof(struct GNode)); /* 建立图 */
        Graph->Nv = VertexNum;
        Graph->Ne = 0;
        /* 初始化邻接矩阵 */
        for (V=0; V<Graph->Nv; V++)
            for (W=0; W<Graph->Nv; W++)
                Graph->G[V][W] = INFINITY;
        
        return Graph;
    }
    
    void InsertEdge( MGraph Graph, Edge E )
    {
        /* 插入边 <V1, V2> */
        Graph->G[E->V1][E->V2] = E->Weight;
        /* 若是无向图,还要插入边<V2, V1> */
        Graph->G[E->V2][E->V1] = E->Weight;
    }
    
    MGraph BuildGraph()
    {
        MGraph Graph;
        Edge E;
        int Nv, i;
        
        scanf("%d", &Nv);   /* 读入顶点个数 */
        Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */
        
        scanf("%d", &(Graph->Ne));   /* 读入边数 */
        if ( Graph->Ne != 0 ) { /* 如果有边 */
            /* 读入边,格式为"起点 终点 权重",插入邻接矩阵 */
            for (i=0; i<Graph->Ne; i++) {
                E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */
                scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
                E->V1--;  E->V2--;
                /* 注意:如果权重不是整型,Weight的读入格式要改 */
                InsertEdge( Graph, E );
            }
        }
        return Graph;
    }
    /* 邻接矩阵存储 - 多源最短路算法 */
    
    void Floyd( MGraph Graph, WeightType D[][MaxVertexNum] )
    {
        Vertex i, j, k;
        
        /* 初始化 */
        for ( i=0; i<Graph->Nv; i++ )
            for( j=0; j<Graph->Nv; j++ ) {
                D[i][j] = Graph->G[i][j];
            }
        
        for( k=0; k<Graph->Nv; k++ )
            for( i=0; i<Graph->Nv; i++ )
                for( j=0; j<Graph->Nv; j++ )
                    if( D[i][k] + D[k][j] < D[i][j] )
                        D[i][j] = D[i][k] + D[k][j];
    }
    
    WeightType FindMaxDist( WeightType D[][MaxVertexNum], Vertex i, int N )
    {
        WeightType MaxDist;
        Vertex j;
        
        MaxDist = 0;
        for ( j=0; j<N; j++ )
            if ( i!=j && D[i][j] > MaxDist )
                MaxDist = D[i][j];
        return MaxDist;
    }
    
    void FindAnimal( MGraph Graph )
    {
        WeightType MinDist, MaxDist;
        Vertex Animal, i;
        WeightType D[MaxVertexNum][MaxVertexNum];
        Floyd( Graph, D );
        // FindMin: 从每个动物i的最短距离的最大值中,找到最小值MinDist,以及对应的动物
        MinDist = INFINITY;
        for ( i=0; i<Graph->Nv;i++ ){
            MaxDist = FindMaxDist( D, i, Graph->Nv );
            if ( MaxDist == INFINITY ){
                printf("0\n");
                return;
            }
            if( MinDist > MaxDist ){
                MinDist = MaxDist;
                Animal = i+1;
            }
        }
        printf("%d %d\n", Animal, MinDist);
    }
    
    int main()
    {
        MGraph G = BuildGraph();
        FindAnimal( G );
        return 0;
    }
    

    旅游规划

    有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的,那么需要输出最便宜的一条路径。

    输入格式:

    输入说明:输入数据的第1行给出4个正整数NMSDN、M、S、D,其中N2N500N(2≤N≤500)是城市的个数,顺便假设城市的编号为0~(N1)(N−1)MM是高速公路的条数;SS是出发地的城市编号;DD是目的地的城市编号。随后的MM行中,每行给出一条高速公路的信息,分别是:城市1、城市2、高速公路长度、收费额,中间用空格分开,数字均为整数且不超过500。输入保证解的存在。

    输出格式:

    在一行里输出路径的长度和收费总额,数字间以空格分隔,输出结尾不能有多余空格。

    输入样例:

    4 5 0 3
    0 1 1 20
    1 3 2 30
    0 3 4 10
    0 2 2 20
    2 3 1 20
    

    输出样例:

    3 40
    

    代码:在这里插入图片描述

    // 单源最短路
    // Dijkstra-距离
    // 等距离时按收费更新
    
    
    #include <stdio.h>
    #include <stdlib.h>
    
    /* 图的邻接矩阵表示法 */
    
    #define MaxVertexNum 500
    #define INFINITY 65535        /* ∞设为双字节无符号整数的最大值65535*/
    typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
    typedef int LengthType;        /* 边的权值设为整型 */
    typedef int CostType;
    
    /* 边的定义 */
    typedef struct ENode *PtrToENode;
    struct ENode{
        Vertex V1, V2;      /* 有向边<V1, V2> */
        LengthType Length;
        CostType Cost;
    };
    typedef PtrToENode Edge;
    
    /* 图结点的定义 */
    typedef struct GNode *PtrToGNode;
    struct GNode{
        int Nv;  /* 顶点数 */
        int Ne;  /* 边数   */
        LengthType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
        CostType H[MaxVertexNum][MaxVertexNum];
    };
    typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
    
    int S, D;
    
    MGraph CreateGraph( int VertexNum )
    { /* 初始化一个有VertexNum个顶点但没有边的图 */
        Vertex V, W;
        MGraph Graph;
        
        Graph = (MGraph)malloc(sizeof(struct GNode)); /* 建立图 */
        Graph->Nv = VertexNum;
        Graph->Ne = 0;
        /* 初始化邻接矩阵 */
        /* 注意:这里默认顶点编号从0开始,到(Graph->Nv - 1) */
        for (V=0; V<Graph->Nv; V++)
            for (W=0; W<Graph->Nv; W++)
            {
                Graph->G[V][W] = INFINITY;
                Graph->H[V][W] = INFINITY;
            }
        return Graph;
    }
    
    void InsertEdge( MGraph Graph, Edge E )
    {
        /* 插入边 <V1, V2> */
        Graph->G[E->V1][E->V2] = E->Length;
        Graph->H[E->V1][E->V2] = E->Cost;
        /* 若是无向图,还要插入边<V2, V1> */
        Graph->G[E->V2][E->V1] = E->Length;
        Graph->H[E->V2][E->V1] = E->Cost;
    }
    
    MGraph BuildGraph()
    {
        MGraph Graph;
        Edge E;
        int Nv, i;
        
        scanf("%d", &Nv);   /* 读入顶点个数 */
        Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */
        
        scanf("%d", &(Graph->Ne));   /* 读入边数 */
        scanf("%d %d", &S, &D);
        if ( Graph->Ne != 0 ) { /* 如果有边 */
            /* 读入边,格式为"起点 终点 权重",插入邻接矩阵 */
            for (i=0; i<Graph->Ne; i++) {
                E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */
                scanf("%d %d %d %d", &E->V1, &E->V2, &E->Length, &E->Cost);
                InsertEdge( Graph, E );
            }
        }
        return Graph;
    }
    
    
    
    /* 邻接矩阵存储 - 有权图的单源最短路算法 */
    
    Vertex FindMinDist( MGraph Graph, int dist[], int collected[] )
    { /* 返回未被收录顶点中dist最小者 */
        Vertex MinV=-1, V;
        int MinDist = INFINITY;
        
        for (V=0; V<Graph->Nv; V++) {
            if ( collected[V]==0 && dist[V]<MinDist) {
                /* 若V未被收录,且dist[V]更小 */
                MinDist = dist[V]; /* 更新最小距离 */
                MinV = V; /* 更新对应顶点 */
            }
        }
        return MinV; /* 返回对应的顶点下标 */
    }
    
    void Dijkstra( MGraph Graph, int dist[], int path[], int cost[], Vertex S )
    {
        int collected[MaxVertexNum];
        Vertex V, W;
        
        /* 初始化:此处默认邻接矩阵中不存在的边用INFINITY表示 */
        for ( V=0; V<Graph->Nv; V++ ) {
            dist[V] = Graph->G[S][V];
            cost[V] = Graph->H[S][V];
            if ( dist[V]<INFINITY )
                path[V] = S;
            else
                path[V] = -1;
            collected[V] = 0;
        }
        /* 先将起点收入集合 */
        dist[S] = 0;
        collected[S] = 1;
        
        while (1) {
            /* V = 未被收录顶点中dist最小者 */
            V = FindMinDist( Graph, dist, collected );
            if ( V==-1 ) /* 若这样的V不存在 */
                break;      /* 算法结束 */
            collected[V] = 1;  /* 收录V */
            for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
            /* 若W是V的邻接点并且未被收录 */
                if ( collected[W]==0 && Graph->G[V][W]<INFINITY ) {
                    if ( Graph->G[V][W]<0 ) /* 若有负边 */
                        return; /* 不能正确解决,返回错误标记 */
                    /* 若收录V使得dist[W]变小 */
                    if ( dist[V]+Graph->G[V][W] < dist[W] ) {
                        dist[W] = dist[V]+Graph->G[V][W]; /* 更新dist[W] */
                        path[W] = V; /* 更新S到W的路径 */
                        cost[W] = cost[V] + Graph->H[V][W];
                    }
                    else if ( dist[V]+Graph->G[V][W] == dist[W] && cost[V] +Graph->H[V][W] < cost[W]){
                        cost[W] = cost[V] + Graph->H[V][W];
                        path[W] = V;
                    }
                }
        } /* while结束*/
        return; /* 算法执行完毕,返回正确标记 */
    }
    
    int main()
    {
        MGraph Graph;
        Graph = BuildGraph();
        int dist[MaxVertexNum], path[MaxVertexNum], cost[MaxVertexNum];
        Dijkstra(Graph, dist, path, cost, S);
        printf("%d %d\n",dist[D],cost[D]);
    }
    

    最小生成树问题(Minimum spanning Tree)

    1. 一棵
    • 无回路
    • |V|个顶点一定有|V|-1条边
    1. 生成
    • 包含全部顶点
    • |V|-1条边都在图里
    1. 边的权重和最小

    贪心算法:

    1. “贪”:每一步都要最好的
    2. “好”:权重最小的边
    3. 需要约束:
    • 只能用图里有的边
    • 只能正好用掉|V|-1条边
    • 不能有回路在这里插入图片描述在这里插入图片描述

    实现代码:

    /* 邻接矩阵存储 - Prim最小生成树算法 */
     
    Vertex FindMinDist( MGraph Graph, WeightType dist[] )
    { /* 返回未被收录顶点中dist最小者 */
        Vertex MinV, V;
        WeightType MinDist = INFINITY;
     
        for (V=0; V<Graph->Nv; V++) {
            if ( dist[V]!=0 && dist[V]<MinDist) {
                /* 若V未被收录,且dist[V]更小 */
                MinDist = dist[V]; /* 更新最小距离 */
                MinV = V; /* 更新对应顶点 */
            }
        }
        if (MinDist < INFINITY) /* 若找到最小dist */
            return MinV; /* 返回对应的顶点下标 */
        else return ERROR;  /* 若这样的顶点不存在,返回-1作为标记 */
    }
     
    int Prim( MGraph Graph, LGraph MST )
    { /* 将最小生成树保存为邻接表存储的图MST,返回最小权重和 */
        WeightType dist[MaxVertexNum], TotalWeight;
        Vertex parent[MaxVertexNum], V, W;
        int VCount;
        Edge E;
         
        /* 初始化。默认初始点下标是0 */
           for (V=0; V<Graph->Nv; V++) {
            /* 这里假设若V到W没有直接的边,则Graph->G[V][W]定义为INFINITY */
               dist[V] = Graph->G[0][V];
               parent[V] = 0; /* 暂且定义所有顶点的父结点都是初始点0 */ 
        }
        TotalWeight = 0; /* 初始化权重和     */
        VCount = 0;      /* 初始化收录的顶点数 */
        /* 创建包含所有顶点但没有边的图。注意用邻接表版本 */
        MST = CreateGraph(Graph->Nv);
        E = (Edge)malloc( sizeof(struct ENode) ); /* 建立空的边结点 */
                
        /* 将初始点0收录进MST */
        dist[0] = 0;
        VCount ++;
        parent[0] = -1; /* 当前树根是0 */
     
        while (1) {
            V = FindMinDist( Graph, dist );
            /* V = 未被收录顶点中dist最小者 */
            if ( V==ERROR ) /* 若这样的V不存在 */
                break;   /* 算法结束 */
                 
            /* 将V及相应的边<parent[V], V>收录进MST */
            E->V1 = parent[V];
            E->V2 = V;
            E->Weight = dist[V];
            InsertEdge( MST, E );
            TotalWeight += dist[V];
            dist[V] = 0;
            VCount++;
             
            for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
                if ( dist[W]!=0 && Graph->G[V][W]<INFINITY ) {
                /* 若W是V的邻接点并且未被收录 */
                    if ( Graph->G[V][W] < dist[W] ) {
                    /* 若收录V使得dist[W]变小 */
                        dist[W] = Graph->G[V][W]; /* 更新dist[W] */
                        parent[W] = V; /* 更新树 */
                    }
                }
        } /* while结束*/
        if ( VCount < Graph->Nv ) /* MST中收的顶点不到|V|个 */
           TotalWeight = ERROR;
        return TotalWeight;   /* 算法执行完毕,返回最小权重和或错误标记 */
    }
    
    /* 邻接表存储 - Kruskal最小生成树算法 */
     
    /*-------------------- 顶点并查集定义 --------------------*/
    typedef Vertex ElementType; /* 默认元素可以用非负整数表示 */
    typedef Vertex SetName;     /* 默认用根结点的下标作为集合名称 */
    typedef ElementType SetType[MaxVertexNum]; /* 假设集合元素下标从0开始 */
     
    void InitializeVSet( SetType S, int N )
    { /* 初始化并查集 */
        ElementType X;
     
        for ( X=0; X<N; X++ ) S[X] = -1;
    }
     
    void Union( SetType S, SetName Root1, SetName Root2 )
    { /* 这里默认Root1和Root2是不同集合的根结点 */
        /* 保证小集合并入大集合 */
        if ( S[Root2] < S[Root1] ) { /* 如果集合2比较大 */
            S[Root2] += S[Root1];     /* 集合1并入集合2  */
            S[Root1] = Root2;
        }
        else {                         /* 如果集合1比较大 */
            S[Root1] += S[Root2];     /* 集合2并入集合1  */
            S[Root2] = Root1;
        }
    }
     
    SetName Find( SetType S, ElementType X )
    { /* 默认集合元素全部初始化为-1 */
        if ( S[X] < 0 ) /* 找到集合的根 */
            return X;
        else
            return S[X] = Find( S, S[X] ); /* 路径压缩 */
    }
     
    bool CheckCycle( SetType VSet, Vertex V1, Vertex V2 )
    { /* 检查连接V1和V2的边是否在现有的最小生成树子集中构成回路 */
        Vertex Root1, Root2;
     
        Root1 = Find( VSet, V1 ); /* 得到V1所属的连通集名称 */
        Root2 = Find( VSet, V2 ); /* 得到V2所属的连通集名称 */
     
        if( Root1==Root2 ) /* 若V1和V2已经连通,则该边不能要 */
            return false;
        else { /* 否则该边可以被收集,同时将V1和V2并入同一连通集 */
            Union( VSet, Root1, Root2 );
            return true;
        }
    }
    /*-------------------- 并查集定义结束 --------------------*/
     
    /*-------------------- 边的最小堆定义 --------------------*/
    void PercDown( Edge ESet, int p, int N )
    { /* 改编代码4.24的PercDown( MaxHeap H, int p )    */
      /* 将N个元素的边数组中以ESet[p]为根的子堆调整为关于Weight的最小堆 */
        int Parent, Child;
        struct ENode X;
     
        X = ESet[p]; /* 取出根结点存放的值 */
        for( Parent=p; (Parent*2+1)<N; Parent=Child ) {
            Child = Parent * 2 + 1;
            if( (Child!=N-1) && (ESet[Child].Weight>ESet[Child+1].Weight) )
                Child++;  /* Child指向左右子结点的较小者 */
            if( X.Weight <= ESet[Child].Weight ) break; /* 找到了合适位置 */
            else  /* 下滤X */
                ESet[Parent] = ESet[Child];
        }
        ESet[Parent] = X;
    }
     
    void InitializeESet( LGraph Graph, Edge ESet )
    { /* 将图的边存入数组ESet,并且初始化为最小堆 */
        Vertex V;
        PtrToAdjVNode W;
        int ECount;
     
        /* 将图的边存入数组ESet */
        ECount = 0;
        for ( V=0; V<Graph->Nv; V++ )
            for ( W=Graph->G[V].FirstEdge; W; W=W->Next )
                if ( V < W->AdjV ) { /* 避免重复录入无向图的边,只收V1<V2的边 */
                    ESet[ECount].V1 = V;
                    ESet[ECount].V2 = W->AdjV;
                    ESet[ECount++].Weight = W->Weight;
                }
        /* 初始化为最小堆 */
        for ( ECount=Graph->Ne/2; ECount>=0; ECount-- )
            PercDown( ESet, ECount, Graph->Ne );
    }
     
    int GetEdge( Edge ESet, int CurrentSize )
    { /* 给定当前堆的大小CurrentSize,将当前最小边位置弹出并调整堆 */
     
        /* 将最小边与当前堆的最后一个位置的边交换 */
        Swap( &ESet[0], &ESet[CurrentSize-1]);
        /* 将剩下的边继续调整成最小堆 */
        PercDown( ESet, 0, CurrentSize-1 );
     
        return CurrentSize-1; /* 返回最小边所在位置 */
    }
    /*-------------------- 最小堆定义结束 --------------------*/
     
     
    int Kruskal( LGraph Graph, LGraph MST )
    { /* 将最小生成树保存为邻接表存储的图MST,返回最小权重和 */
        WeightType TotalWeight;
        int ECount, NextEdge;
        SetType VSet; /* 顶点数组 */
        Edge ESet;    /* 边数组 */
     
        InitializeVSet( VSet, Graph->Nv ); /* 初始化顶点并查集 */
        ESet = (Edge)malloc( sizeof(struct ENode)*Graph->Ne );
        InitializeESet( Graph, ESet ); /* 初始化边的最小堆 */
        /* 创建包含所有顶点但没有边的图。注意用邻接表版本 */
        MST = CreateGraph(Graph->Nv);
        TotalWeight = 0; /* 初始化权重和     */
        ECount = 0;      /* 初始化收录的边数 */
     
        NextEdge = Graph->Ne; /* 原始边集的规模 */
        while ( ECount < Graph->Nv-1 ) {  /* 当收集的边不足以构成树时 */
            NextEdge = GetEdge( ESet, NextEdge ); /* 从边集中得到最小边的位置 */
            if (NextEdge < 0) /* 边集已空 */
                break;
            /* 如果该边的加入不构成回路,即两端结点不属于同一连通集 */
            if ( CheckCycle( VSet, ESet[NextEdge].V1, ESet[NextEdge].V2 )==true ) {
                /* 将该边插入MST */
                InsertEdge( MST, ESet+NextEdge );
                TotalWeight += ESet[NextEdge].Weight; /* 累计权重 */
                ECount++; /* 生成树中边数加1 */
            }
        }
        if ( ECount < Graph->Nv-1 )
            TotalWeight = -1; /* 设置错误标记,表示生成树不存在 */
     
        return TotalWeight;
    }
    

    AOV/g拓扑排序

    拓扑序:如果图中从V到W有一条有向路径,则V一定排在W之前。满足此条件的顶点序列称为一个拓扑序。获得一个拓扑序的过程就是拓扑排序
    AOV如果有合理的拓扑许,则必定是有向无环图(Directed Acyclic Graph, DAG)

    在这里插入图片描述
    在这里插入图片描述

    AOE/关键路径问题

    在这里插入图片描述

    /* 邻接表存储 - 拓扑排序算法 */
     
    bool TopSort( LGraph Graph, Vertex TopOrder[] )
    { /* 对Graph进行拓扑排序,  TopOrder[]顺序存储排序后的顶点下标 */
        int Indegree[MaxVertexNum], cnt;
        Vertex V;
        PtrToAdjVNode W;
           Queue Q = CreateQueue( Graph->Nv );
      
        /* 初始化Indegree[] */
        for (V=0; V<Graph->Nv; V++)
            Indegree[V] = 0;
             
        /* 遍历图,得到Indegree[] */
        for (V=0; V<Graph->Nv; V++)
            for (W=Graph->G[V].FirstEdge; W; W=W->Next)
                Indegree[W->AdjV]++; /* 对有向边<V, W->AdjV>累计终点的入度 */
                 
        /* 将所有入度为0的顶点入列 */
        for (V=0; V<Graph->Nv; V++)
            if ( Indegree[V]==0 )
                AddQ(Q, V);
                 
        /* 下面进入拓扑排序 */ 
        cnt = 0; 
        while( !IsEmpty(Q) ){
            V = DeleteQ(Q); /* 弹出一个入度为0的顶点 */
            TopOrder[cnt++] = V; /* 将之存为结果序列的下一个元素 */
            /* 对V的每个邻接点W->AdjV */
            for ( W=Graph->G[V].FirstEdge; W; W=W->Next )
                if ( --Indegree[W->AdjV] == 0 )/* 若删除V使得W->AdjV入度为0 */
                    AddQ(Q, W->AdjV); /* 则该顶点入列 */ 
        } /* while结束*/
         
        if ( cnt != Graph->Nv )
            return false; /* 说明图中有回路, 返回不成功标志 */ 
        else
            return true;
    }
    
    展开全文
  • 基于easyx图形库的推箱子小游戏

    千次阅读 2020-06-17 09:18:09
    基于easyx图形库的推箱子小游戏 ...利用数字矩阵表示地图,不同的数字代表不同的图片。 程序遍历数组,遇到不同的数字贴相应的图片 程序代码 主程序: ```c ```c ```c ```c ```c #include"Thehead.h"//引

    基于easyx图形库的推箱子小游戏

    C语言期末项目要求自己设计一个项目,我选择了《推箱子》小游戏,
    因为这个程序当中涉及到的一些算法及语法,能够更好的帮助我复习有关C语言的基础知识。
    这是我的第一篇博客,希望大家多多指正。

    程序效果图

    在这里插入图片描述

    在这里插入图片描述图片是我自己在网上扣的,所以不怎么美观

    项目实现(主要算法)

    利用数字矩阵表示地图,不同的数字代表不同的图片。
    程序遍历数组,遇到不同的数字贴相应的图片

    程序代码

    主程序:

    ```c
    
    ```c
    
    ```c
    
    ```c
    ```c
    #include"Thehead.h"//引用头文件
    
    int map_temp_last[100][16][16];//用于保存上一步的地图
    int map_temp[MapMany][16][16];//用于保存上一关的地图
    
    int stepnum = 0;//统计步数
    char input;//用户的键入操作
    //设置窗口大小
    int main()
    {
    	ReadMapFile();
    	//PlaySound(TEXT("gamemusic.wav"), 0, SND_FILENAME | SND_ASYNC);
    
    	F:
    	Welcome();
    
    	//保存本关的地图,在执行之前保存,便于执行重启操作
    
    	for (int i = 0; i < 16; i++)
    		for (int j = 0; j < 16; j++)
    			map_temp[WhatMap][i][j] = map[WhatMap][i][j];
    
    	while (1)
    	{
    		//判断是否进入下一关
    		MOUSEMSG msg2;
    		{
    			while (MouseHit())	//监听鼠标信息;当有鼠标消息的时候执行,可检测连续的鼠标信息
    			{
    				msg2 = GetMouseMsg();//获取鼠标消息
    				if (WM_LBUTTONDOWN == msg2.uMsg)//判断鼠标信息;鼠标左键按下
    				{
    					if (msg2.x > 860 && msg2.x < 940 && msg2.y > 50 && msg2.y < 110)
    					{
    						
    
    ```c
    if(WhatMap<10)
    							WhatMap++;
    						
    					}
    					else if (msg2.x > 790 && msg2.x < 850 && msg2.y > 50 && msg2.y < 110)//鼠标点击特定区域`在这里插入代码片`
    					{
    						if (WhatMap >= 1)
    							WhatMap--;
    
    				}
    
    				else if (msg2.x > 10 && msg2.x < 50 && msg2.y > 50 && msg2.y < 90)//鼠标点击特定区域
    				{
    					goto F;
    				}
    				drawGame();
    			}
    
    		}
    	}
    	
    
    	if (kbhit())
    	{
    
    
    		PlaySound(TEXT("move.wav"), 0, SND_FILENAME | SND_ASYNC);
    		input = getch();
    		{
    
    			if (input == 'W' || input == 'w' || input == 72)
    			{
    				ManUp();
    
    			}
    			else if (input == 'S' || input == 's' || input == 80)
    			{
    				ManDown();
    
    			}
    			else if (input == 'A' || input == 'a' || input == 75)
    			{
    				ManLeft();
    
    			}
    			else if (input == 'D' || input == 'd' || input == 77)
    			{
    				ManRight();
    
    			}
    			else if (input == 'r' || input == 'R')
    			{
    				Reset();
    
    			}
    			else if (input == 'z' || input == 'Z')
    			{
    				if (stepnum > 0) {
    					stepnum--;
    					Backstep();
    				}
    			}
    			
    			else
    				continue;
    
    		}
    
    		drawGame();//每次移动后都要从新贴图,因此没执行一步调用一次该函数
    
    		if (GameOver())
    		{
    			PlaySound(TEXT("success.wav"), 0, SND_FILENAME | SND_ASYNC);
    			WhatMap++;//如果一个关卡完成,则进入下一个关卡
    			stepnum = 0;
    			for (int i = 0; i < 16; i++)
    				for (int j = 0; j < 16; j++)
    					map_temp[WhatMap][i][j] = map[WhatMap][i][j];
    			Sleep(1000);
    		}
    		if (WhatMap == 11)break;
    	}
    }
    
    Sleep(10000);
    return 0;
    //system("pause");
    

    }

    //初始化窗口,加载图片
    void initscreen()
    {
    initgraph(16 * (SPACE+20), 16 * SPACE);//初始化画图窗口

    outtextxy(700, 50, "目标数:");
    // 加载图片
    
    //0表示空地//1表示墙//2代表目的地//3代表人站在空地上//4代表箱子
    //5箱子与目的地重合// 6,人站在目的地上
    loadimage(&png[0], _T("0.jpg"), SPACE, SPACE, true);
    loadimage(&png[1], _T("1.jpg"), SPACE, SPACE, true);
    loadimage(&png[2], _T("2.jpg"), SPACE, SPACE, true);
    loadimage(&png[3], _T("3.jpg"), SPACE, SPACE, true);
    loadimage(&png[4], _T("4.jpg"), SPACE, SPACE, true);
    loadimage(&png[5], _T("5.jpg"), SPACE, SPACE, true);
    loadimage(&png[6], _T("6.jpg"), SPACE, SPACE, true);
    loadimage(&button, _T("button.jpg"), 150, 60, true);
    loadimage(&next, _T("next.jpg"), 60, 60, true);
    loadimage(&previous, _T("previous.jpg"), 60, 60, true);
    loadimage(&backto, _T("backto.jpg"), 60, 60, true);
    drawGame();
    

    }
    //画出游戏中的各个元素(贴图的方式)
    void drawGame() {
    for (int i = 0; i < 16; i++) {//显示一行
    for (int j = 0; j < 16; j++) {//显示一个格子
    putimage(j * SPACE, i * SPACE, &png[map[WhatMap][i][j]]);
    }
    }

    putimage(100, 50, &button);
    putimage(350, 50, &button);
    putimage(600, 50, &button);
    putimage(860, 50, &next);
    putimage(790, 50, &previous);
    putimage(10, 50, &backto);
    setbkmode(TRANSPARENT);//设置字体背景为透明
    settextcolor(COLORREF(RGB(255, 0, 0)));//设置字体颜色为黑色
    settextstyle(40, 0, _T("楷体"));//设置字体大小20,格式楷体
    
    //将数字通过字符的形式输出
    TCHAR t1[5];
    TCHAR t2[5];
    TCHAR t3[5];
    _stprintf(t1, _T("%d"), WhatMap + 1);	// 高版本 VC 推荐使用 _stprintf_s 函数
    _stprintf(t2, _T("%d"), stepnum);
    _stprintf(t3, _T("%d"), Boxnum());
    outtextxy(200, 50, t1);
    outtextxy(100, 50, "关卡:");
    
    outtextxy(450, 50, t2);
    outtextxy(350, 50, "步数:");
    
    outtextxy(730, 50, t3);
    outtextxy(600, 50, "目标数:");
    
    outtextxy(1000, 50, "撤回:z键");
    outtextxy(1000, 100, "重启本关:r键");
    outtextxy(1000, 150, "操作:a、w、s、");
    outtextxy(1000, 200, "d或者方向键");
    outtextxy(1000, 400, "其余操作用鼠标");
    

    }

    void ManDown()
    {

    //在每一步执行之前,将地图保存到临时数组里面
    int p, q;
    for (int i = 0; i < 16; i++)
    	for (int j = 0; j < 16; j++)
    		map_temp_last[stepnum][i][j] = map[WhatMap][i][j];
    
    //先找到人的位置
    int i, j;
    for (i = 0; i < 16; i++)
    {
    	int flag = 0;
    	for (j = 0; j < 16; j++)
    		if (map[WhatMap][i][j] == 3 || map[WhatMap][i][j] == 6)
    		{
    			flag = 1;
    			break;
    		}
    	if (flag)break;
    }
    //人的位置是map[WhatMap][i][j];
    
    
    //人的位置是空地(而不是人和目的地在一起)
    if (map[WhatMap][i][j] == 3)
    {
    	//人的上面是空地
    	if (map[WhatMap][i + 1][j] == 0)
    	{
    		map[WhatMap][i][j] = 0;
    		map[WhatMap][i + 1][j] = 3;
    	}
    	//人的上面是目的地
    	else if (map[WhatMap][i + 1][j] == 2)
    	{
    		map[WhatMap][i][j] = 0;
    		map[WhatMap][i + 1][j] = 6;
    	}
    	//人的上面是箱子
    	else if (map[WhatMap][i + 1][j] == 4)
    	{
    		//1箱子上面是目的地
    		if (map[WhatMap][i + 2][j] == 2)
    		{
    			map[WhatMap][i][j] = 0;
    			map[WhatMap][i + 1][j] = 3;
    			map[WhatMap][i + 2][j] = 5;
    		}
    		//2箱子上面是空地
    		else if (map[WhatMap][i + 2][j] == 0)
    		{
    			map[WhatMap][i][j] = 0;
    			map[WhatMap][i + 1][j] = 3;
    			map[WhatMap][i + 2][j] = 4;
    		}
    
    	}
    	//人的上面是箱子和目的地在一起
    	else if (map[WhatMap][i + 1][j] == 5)
    	{
    		//箱子上面是目的地
    		if (map[WhatMap][i + 2][j] == 2)
    		{
    			map[WhatMap][i][j] = 0;
    			map[WhatMap][i + 1][j] = 6;
    			map[WhatMap][i + 2][j] = 5;
    		}
    
    		//箱子上面是空地
    		else if (map[WhatMap][i + 2][j] == 0)
    		{
    			map[WhatMap][i][j] = 0;
    			map[WhatMap][i + 1][j] = 6;
    			map[WhatMap][i + 2][j] = 4;
    		}
    	}
    
    }
    
    //人的位置是目的地(即人和目的地在一起)
    else if (map[WhatMap][i][j] == 6)
    {
    
    	//人的上面是空地
    
    	if (map[WhatMap][i + 1][j] == 0)
    	{
    		map[WhatMap][i][j] = 2;
    		map[WhatMap][i + 1][j] = 3;
    	}
    	//人的上面是目的地
    	else if (map[WhatMap][i + 1][j] == 2)
    	{
    		map[WhatMap][i][j] = 2;
    		map[WhatMap][i + 1][j] = 6;
    	}
    	//人的上面是箱子
    
    	else if (map[WhatMap][i + 1][j] == 4)
    	{
    		//1.箱子上面是目的地
    		if (map[WhatMap][i + 2][j] == 2)
    		{
    			map[WhatMap][i][j] = 2;
    			map[WhatMap][i + 1][j] = 3;
    			map[WhatMap][i + 2][j] = 5;
    		}
    		//2.箱子上面是空地
    		else if (map[WhatMap][i + 2][j] == 0)
    		{
    			map[WhatMap][i][j] = 2;
    			map[WhatMap][i + 1][j] = 3;
    			map[WhatMap][i + 2][j] = 4;
    		}
    
    	}
    
    
    	//人的上面是箱子和目的地在一起
    	else if (map[WhatMap][i + 1][j] == 5)
    	{
    		//箱子上面是目的地
    		if (map[WhatMap][i + 2][j] == 2)
    		{
    			map[WhatMap][i][j] = 2;
    			map[WhatMap][i + 1][j] = 6;
    			map[WhatMap][i + 2][j] = 5;
    		}
    
    		//箱子上面是空地
    		else if (map[WhatMap][i + 2][j] == 0)
    		{
    			map[WhatMap][i][j] = 2;
    			map[WhatMap][i + 1][j] = 6;
    			map[WhatMap][i + 2][j] = 4;
    		}
    	}
    }
    
    //防止回到上一步也在增加步数
    for (p = 0; p < 16; p++)
    {
    	int flag = 0;
    	for (q = 0; q < 16; q++)
    		if (map[WhatMap][p][q] == 3 || map[WhatMap][p][q] == 6)
    		{
    			flag = 1;
    			break;
    		}
    	if (flag)break;
    }
    
    //将现在人的步数和刚开始人的步数进行比较,如果相同,则不进行步数的增加
    if (i != p || j != q)
    	stepnum++;
    

    }
    //人向右移动
    void ManRight()
    {
    int p, q;

    for (int i = 0; i < 16; i++)
    	for (int j = 0; j < 16; j++)
    		map_temp_last[stepnum][i][j] = map[WhatMap][i][j];
    //先找到人的位置
    int i, j;
    for (i = 0; i < 16; i++)
    {
    	int flag = 0;
    	for (j = 0; j < 16; j++)
    		if (map[WhatMap][i][j] == 3 || map[WhatMap][i][j] == 6)
    		{
    			flag = 1;
    			break;
    		}
    	if (flag)break;
    }
    //人的位置是map[WhatMap][i][j];
    
    
    
    //人的位置是空地
    if (map[WhatMap][i][j] == 3)
    {
    	//人的右面是空地
    	if (map[WhatMap][i][j + 1] == 0)
    	{
    		map[WhatMap][i][j] = 0;
    		map[WhatMap][i][j + 1] = 3;
    	}
    	//人的右面是目的地
    	else if (map[WhatMap][i][j + 1] == 2)
    	{
    		map[WhatMap][i][j] = 0;
    		map[WhatMap][i][j + 1] = 6;
    	}
    	//人的右面是箱子
    	else if (map[WhatMap][i][j + 1] == 4)
    	{
    		//1.箱子右面是目的地
    		if (map[WhatMap][i][j + 2] == 2)
    		{
    			map[WhatMap][i][j] = 0;
    			map[WhatMap][i][j + 1] = 3;
    			map[WhatMap][i][j + 2] = 5;
    		}
    		//2.箱子右面是空地
    		else if (map[WhatMap][i][j + 2] == 0)
    		{
    			map[WhatMap][i][j] = 0;
    			map[WhatMap][i][j + 1] = 3;
    			map[WhatMap][i][j + 2] = 4;
    		}
    
    	}
    
    
    	//人的右边是箱子和目的地在一起
    	else if (map[WhatMap][i][j + 1] == 5)
    	{
    		//箱子右边是目的地
    		if (map[WhatMap][i][j + 2] == 2)
    		{
    			map[WhatMap][i][j] = 0;
    			map[WhatMap][i][j + 1] = 6;
    			map[WhatMap][i][j + 2] = 5;
    		}
    
    		//箱子右边是空地
    		else if (map[WhatMap][i][j + 2] == 0)
    		{
    			map[WhatMap][i][j] = 0;
    			map[WhatMap][i][j + 1] = 6;
    			map[WhatMap][i][j + 2] = 4;
    		}
    	}
    }
    
    //人的位置是目的地
    else if (map[WhatMap][i][j] == 6)
    {
    	//人的右面是空地
    
    	if (map[WhatMap][i][j + 1] == 0)
    	{
    		map[WhatMap][i][j] = 2;
    		map[WhatMap][i][j + 1] = 3;
    	}
    	//人的右面是目的地
    	else if (map[WhatMap][i][j + 1] == 2)
    	{
    		map[WhatMap][i][j] = 2;
    		map[WhatMap][i][j + 1] = 6;
    	}
    	//人的右面是箱子
    
    	else if (map[WhatMap][i][j + 1] == 4)
    	{
    		//1.箱子右面是目的地
    		if (map[WhatMap][i][j + 2] == 2)
    		{
    			map[WhatMap][i][j] = 2;
    			map[WhatMap][i][j + 1] = 3;
    			map[WhatMap][i][j + 2] = 5;
    		}
    		//2.箱子右面是空地
    		else if (map[WhatMap][i][j + 2] == 0)
    		{
    			map[WhatMap][i][j] = 2;
    			map[WhatMap][i][j + 1] = 3;
    			map[WhatMap][i][j + 2] = 4;
    		}
    
    	}
    
    
    	//人的右边是箱子和目的地在一起
    	else if (map[WhatMap][i][j + 1] == 5)
    	{
    		//箱子右边是目的地
    		if (map[WhatMap][i][j + 2] == 2)
    		{
    			map[WhatMap][i][j] = 2;
    			map[WhatMap][i][j + 1] = 6;
    			map[WhatMap][i][j + 2] = 5;
    		}
    
    		//箱子右边是空地
    		else if (map[WhatMap][i][j + 2] == 0)
    		{
    			map[WhatMap][i][j] = 2;
    			map[WhatMap][i][j + 1] = 6;
    			map[WhatMap][i][j + 2] = 4;
    		}
    	}
    }
    for (p = 0; p < 16; p++)
    {
    	int flag = 0;
    	for (q = 0; q < 16; q++)
    		if (map[WhatMap][p][q] == 3 || map[WhatMap][p][q] == 6)
    		{
    			flag = 1;
    			break;
    		}
    	if (flag)break;
    }
    
    if (i != p || j != q)
    	stepnum++;
    

    }

    //人向左移动
    void ManLeft()
    {
    int p, q;

    for (int i = 0; i < 16; i++)
    	for (int j = 0; j < 16; j++)
    		map_temp_last[stepnum][i][j] = map[WhatMap][i][j];
    //先找到人的位置
    int i, j;
    for (i = 0; i < 16; i++)
    {
    	int flag = 0;
    	for (j = 0; j < 16; j++)
    		if (map[WhatMap][i][j] == 3 || map[WhatMap][i][j] == 6)
    		{
    			flag = 1;
    			break;
    		}
    	if (flag)break;
    }
    //人的位置是map[WhatMap][i][j];
    
    //改变人的方向
    
    //人的位置是空地
    if (map[WhatMap][i][j] == 3)
    {
    	//人的左面是空地
    	if (map[WhatMap][i][j - 1] == 0)
    	{
    		map[WhatMap][i][j] = 0;
    		map[WhatMap][i][j - 1] = 3;
    	}
    	//人的左面是目的地
    	else if (map[WhatMap][i][j - 1] == 2)
    	{
    		map[WhatMap][i][j] = 0;
    		map[WhatMap][i][j - 1] = 6;
    	}
    	//人的左面是箱子
    	else if (map[WhatMap][i][j - 1] == 4)
    	{
    		//1.箱子左面是目的地
    		if (map[WhatMap][i][j - 2] == 2)
    		{
    			map[WhatMap][i][j] = 0;
    			map[WhatMap][i][j - 1] = 3;
    			map[WhatMap][i][j - 2] = 5;
    		}
    		//2.箱子左面是空地
    		else if (map[WhatMap][i][j - 2] == 0)
    		{
    			map[WhatMap][i][j] = 0;
    			map[WhatMap][i][j - 1] = 3;
    			map[WhatMap][i][j - 2] = 4;
    		}
    
    	}
    
    	//人的左边是箱子和目的地在一起
    	else if (map[WhatMap][i][j - 1] == 5)
    	{
    		//箱子右边是目的地
    		if (map[WhatMap][i][j - 2] == 2)
    		{
    			map[WhatMap][i][j] = 0;
    			map[WhatMap][i][j - 1] = 6;
    			map[WhatMap][i][j - 2] = 5;
    		}
    
    		//箱子右边是空地
    		else if (map[WhatMap][i][j - 2] == 0)
    		{
    			map[WhatMap][i][j] = 0;
    			map[WhatMap][i][j - 1] = 6;
    			map[WhatMap][i][j - 2] = 4;
    		}
    	}
    }
    
    
    //人的位置是目的地
    else if (map[WhatMap][i][j] == 6)
    {
    	//人的上面是空地
    
    	if (map[WhatMap][i][j - 1] == 0)
    	{
    		map[WhatMap][i][j] = 2;
    		map[WhatMap][i][j - 1] = 3;
    	}
    	//人的上面是目的地
    	else if (map[WhatMap][i][j - 1] == 2)
    	{
    		map[WhatMap][i][j] = 2;
    		map[WhatMap][i][j - 1] = 6;
    	}
    	//人的上面是箱子
    
    	else if (map[WhatMap][i][j - 1] == 4)
    	{
    		//1.箱子上面是目的地
    		if (map[WhatMap][i][j - 2] == 2)
    		{
    			map[WhatMap][i][j] = 2;
    			map[WhatMap][i][j - 1] = 3;
    			map[WhatMap][i][j - 2] = 5;
    		}
    		//2.箱子上面是空地
    		else if (map[WhatMap][i][j - 2] == 0)
    		{
    			map[WhatMap][i][j] = 2;
    			map[WhatMap][i][j - 1] = 3;
    			map[WhatMap][i][j - 2] = 4;
    		}
    
    	}
    }
    //人的左边是箱子和目的地在一起
    else if (map[WhatMap][i][j - 1] == 5)
    {
    	//箱子左边是目的地
    	if (map[WhatMap][i][j - 2] == 2)
    	{
    		map[WhatMap][i][j] = 2;
    		map[WhatMap][i][j - 1] = 6;
    		map[WhatMap][i][j - 2] = 5;
    	}
    
    	//箱子左边是空地
    	else if (map[WhatMap][i][j + 2] == 0)
    	{
    		map[WhatMap][i][j] = 2;
    		map[WhatMap][i][j - 1] = 6;
    		map[WhatMap][i][j - 2] = 4;
    	}
    }
    for (p = 0; p < 16; p++)
    {
    	int flag = 0;
    	for (q = 0; q < 16; q++)
    		if (map[WhatMap][p][q] == 3 || map[WhatMap][p][q] == 6)
    		{
    			flag = 1;
    			break;
    		}
    	if (flag)break;
    }
    
    if (i != p || j != q)
    	stepnum++;
    

    }

    //人向下移动
    void ManUp()
    {
    int p, q;
    for (int i = 0; i < 16; i++)
    for (int j = 0; j < 16; j++)
    map_temp_last[stepnum][i][j] = map[WhatMap][i][j];
    //先找到人的位置
    int i, j;
    for (i = 0; i < 16; i++)
    {
    int flag = 0;
    for (j = 0; j < 16; j++)
    if (map[WhatMap][i][j] == 3 || map[WhatMap][i][j] == 6)//人站在空地上或者人站在目的地上
    {
    flag = 1;
    break;
    }
    if (flag)break;
    }

    //人的位置已被记录
    //人的位置是map[WhatMap][i][j];
    
    //1.人的位置是空地
    if (map[WhatMap][i][j] == 3)
    {
    	//人的上面是空地
    	if (map[WhatMap][i - 1][j] == 0)
    	{
    		map[WhatMap][i][j] = 0;//人变空地
    		map[WhatMap][i - 1][j] = 3;//空地变人
    	}
    	//人的上面是目的地
    	else if (map[WhatMap][i - 1][j] == 2)
    	{
    		map[WhatMap][i][j] = 0;
    		map[WhatMap][i - 1][j] = 6;//人和目的地咱一起
    	}
    	//人的上面是箱子
    	else if (map[WhatMap][i - 1][j] == 4)
    	{
    		//1.箱子上面是目的地
    		if (map[WhatMap][i - 2][j] == 2)
    		{
    			map[WhatMap][i][j] = 0;
    			map[WhatMap][i - 1][j] = 3;
    			map[WhatMap][i - 2][j] = 5;
    		}
    		//2.箱子上面是空地
    		else if (map[WhatMap][i - 2][j] == 0)
    		{
    			map[WhatMap][i][j] = 0;
    			map[WhatMap][i - 1][j] = 3;
    			map[WhatMap][i - 2][j] = 4;
    		}
    
    	}
    	//人的上面是箱子和目的地在一起
    	else if (map[WhatMap][i - 1][j] == 5)
    	{
    		//箱子上面是目的地
    		if (map[WhatMap][i - 2][j] == 2)
    		{
    			map[WhatMap][i][j] = 0;
    			map[WhatMap][i - 1][j] = 6;
    			map[WhatMap][i - 2][j] = 5;
    		}
    
    		//箱子上面是空地
    		else if (map[WhatMap][i - 2][j] == 0)
    		{
    			map[WhatMap][i][j] = 0;
    			map[WhatMap][i - 1][j] = 6;
    			map[WhatMap][i - 2][j] = 4;
    		}
    	}
    }
    
    //人的位置是目的地
    else if (map[WhatMap][i][j] == 6)
    {
    	//人的上面是空地
    
    	if (map[WhatMap][i - 1][j] == 0)
    	{
    		map[WhatMap][i][j] = 2;
    		map[WhatMap][i - 1][j] = 3;
    	}
    	//人的上面是目的地
    	else if (map[WhatMap][i - 1][j] == 2)
    	{
    		map[WhatMap][i][j] = 2;
    		map[WhatMap][i - 1][j] = 6;
    	}
    
    	//人的上面是箱子(有两种情况)
    
    	else if (map[WhatMap][i - 1][j] == 4)
    	{
    		//1箱子上面是目的地
    		if (map[WhatMap][i - 2][j] == 2)
    		{
    			map[WhatMap][i][j] = 2;
    			map[WhatMap][i - 1][j] = 3;
    			map[WhatMap][i - 2][j] = 5;
    		}
    		//2箱子上面是空地
    		else if (map[WhatMap][i - 2][j] == 0)
    		{
    			map[WhatMap][i][j] = 2;
    			map[WhatMap][i - 1][j] = 3;
    			map[WhatMap][i - 2][j] = 4;
    		}
    
    	}
    	//人的上面是箱子和目的地在一起
    	else if (map[WhatMap][i - 1][j] == 5)
    	{
    		//箱子上面是目的地
    		if (map[WhatMap][i - 2][j] == 2)
    		{
    			map[WhatMap][i][j] = 2;
    			map[WhatMap][i - 1][j] = 6;
    			map[WhatMap][i - 2][j] = 5;
    		}
    
    		//箱子上面是空地
    		else if (map[WhatMap][i - 2][j] == 0)
    		{
    			map[WhatMap][i][j] = 2;
    			map[WhatMap][i - 1][j] = 6;
    			map[WhatMap][i - 2][j] = 4;
    		}
    	}
    }
    for (p = 0; p < 16; p++)
    {
    	int flag = 0;
    	for (q = 0; q < 16; q++)
    		if (map[WhatMap][p][q] == 3 || map[WhatMap][p][q] == 6)
    		{
    			flag = 1;
    			break;
    		}
    	if (flag)break;
    }
    
    if (i != p || j != q)
    	stepnum++;
    

    }

    //判断游戏是否结束
    int GameOver()
    {
    //统计目的地的个数
    //每个地图的目的地个数不同,因此每次都要遍历地图数组
    int flag = 0;
    for (int i = 0; i < 16; i++)
    {
    for (int j = 0; j < 16; j++)
    {
    if (map[WhatMap][i][j] == 2)flag++;
    }
    }

    //箱子到达目的地的个数
    //当箱子和目的地在一起的个数和目的地总数相等,则该关卡已完成
    int count = 0;
    for (int i = 0; i < 16; i++)
    {
    	for (int j = 0; j < 16; j++)
    	{
    		if (map[WhatMap][i][j] == 4)count++;
    	}
    }
    if (count == 0 && flag == 0)return 1;
    else return 0;
    

    }

    //显示初始页面
    void Welcome()
    {
    initgraph(16 * SPACE, 16 * SPACE);//初始化画图窗口

    loadimage(&welcome, "welcome.jpg", 16 * SPACE, 16 * SPACE);//导入欢迎界面(特别注意:双引号里面不能有空格,要跟图片命名完全一致)
    loadimage(&Create, "Create.jpg", 300, 100);
    loadimage(&Create, "Create.jpg", 300, 100);
    loadimage(&Create, "Create.jpg", 300, 100);
    loadimage(&Create, "Create.jpg", 300, 100);
    
    putimage(0, 0, &welcome);//显示欢迎界面
    putimage(300, 100, &Create);
    putimage(300, 200, &Create);
    putimage(300, 300, &Create);
    putimage(300, 400, &Create);
    
    setbkmode(TRANSPARENT);//设置字体背景为透明
    settextcolor(COLORREF(RGB(128, 255, 0)));//设置字体颜色为黑色
    
    settextstyle(50, 0, _T("宋体"));//设置字体大小20,格式楷体
    char r1[] = "地图编辑";
    char r2[] = "开始游戏";
    char r3[] = "退出游戏";
    char r4[] = "游戏说明";
    outtextxy(350, 430, r1);
    outtextxy(350, 130, r2);
    outtextxy(350, 230, r3);
    outtextxy(350, 330, r4);
    
    MOUSEMSG msg;//定义变量,保存鼠标消息
    FlushMouseMsgBuffer();// 清空鼠标消息缓冲区,避免无效鼠标信息带入到正式判断中
    while (true) // 主循环,循环监听鼠标信息
    {
    	while (MouseHit())	//监听鼠标信息;当有鼠标消息的时候执行,可检测连续的鼠标信息
    	{
    		msg = GetMouseMsg();//获取鼠标消息
    		if (WM_LBUTTONDOWN == msg.uMsg)//判断鼠标信息;鼠标左键按下
    		{
    			if (msg.x > 300 && msg.x < 900 && msg.y > 100 && msg.y < 200)//鼠标点击特定区域
    			{
    				initscreen(); return;
    			}
    			else if (msg.x > 300 && msg.x < 900 && msg.y > 200 && msg.y < 300)
    			{
    				exit(0);
    			}
    			else if (msg.x > 300 && msg.x < 900 && msg.y > 300 && msg.y < 400)
    			{
    				ShowText();
    				getch();
    				Welcome();
    				return;
    
    			}
    			else if (msg.x > 300 && msg.x < 900 && msg.y > 400 && msg.y < 500)
    				CreatMap();
    			return;
    		}
    
    	}
    
    }
    

    }

    //显示帮助文档
    void ShowText()
    {
    initgraph(16 * SPACE, 16 * SPACE);
    loadimage(&helptext, “helptext.jpg”, 16 * SPACE, 16 * SPACE);
    putimage(0, 0, &helptext);

    setbkmode(TRANSPARENT);//设置字体背景为透明
    settextcolor(COLORREF(RGB(0, 0, 0)));//设置字体颜色为黑色
    settextstyle(40, 0, _T("楷体"));//设置字体大小20,格式楷体
    char s1[] = "这是一个经典的推箱子游戏";
    char s2[] = "使用方向键↑←↓→或者“w、a、s、d";
    char s3[] = "(不区分大小写)控制人物来推动箱子";
    char s4[] = "游戏开发者:扎扎西(单身可撩)";
    char s5[] = "开发时间:2020.5.18";
    char s6[] = "所有箱子到达目的地即可通关";
    char s7[] = "按R/r键重启关卡,按Z/z键撤回前一步操作";
    char s8[] = "除游戏控制外的操作支持鼠标点击";
    char s9[] = "按任意键返回!!";
    outtextxy(150, 270, s6);
    outtextxy(150, 150, s1);
    outtextxy(150, 190, s2);
    outtextxy(150, 230, s3);
    outtextxy(400, 450, s4);
    outtextxy(400, 490, s5);
    outtextxy(150, 310, s7);
    outtextxy(150, 350, s8);
    outtextxy(150, 610, s9);
    

    }

    //重置当前关卡
    void Reset()
    {
    stepnum = 0;//因为重启,步数归零
    for (int i = 0; i < 16; i++) //显示一行
    for (int j = 0; j < 16; j++) //显示一个格子
    map[WhatMap][i][j] = map_temp[WhatMap][i][j];
    }

    //实现撤回功能
    void Backstep()
    {

    if (stepnum < 0)
    	return;
    for (int i = 0; i < 16; i++) //显示一行
    	for (int j = 0; j < 16; j++) //显示一个格子
    		map[WhatMap][i][j] = map_temp_last[stepnum][i][j];
    

    }

    /

    /
    
    ```c
    统计当前关卡中剩余的目的地数
    int Boxnum()
    {
    	int boxnum = 0;
    	for (int m = 0; m < 16; m++)
    		for (int n = 0; n < 16; n++)
    
    		if (map[WhatMap][m][n] == 4)
    			boxnum++;
    return boxnum;
    

    }

    
    
    
    
    
    
    
    
    
    ## 创建地图部分
    
    ```c
    //#include"Thehead.h"//引用头文件
    #include <stdio.h>
    #include <windows.h>
    #include <conio.h>
    #define SPACE 60
    #include<graphics.h>
    #include<stdbool.h>
    #include<string.h>;
    void ShowhelpTxt();
    IMAGE png1[12];//5张图,定义5个变量,定义一个数组
    IMAGE background;
    IMAGE conti;
    #define N 16    //地图宽高
    
    #define FLMOP "NewMap.txt"
    
    void gotoxy(int x, int y);  //光标定位
    void TranMap();              //翻译输出地图
    void Control();            //控制移动和设置元素函数
    
    int cmap[N][N];      //地图数组
    char ck;            //读方向键
    int x, y;           //光标坐标(x*2)
    
    int CreatMap()                 //主函数控制所有
    {
    	initgraph(16 * SPACE, 16 * SPACE);//初始化画图窗口
    
    	//输出使用说明
    	ShowhelpTxt();
    	TranMap();              //输出地图
    
    	while (1)
    	{
    
    
    		Control(); //控制光标移动
    
    
    	}
    
    	Sleep(60);
    	return 0;
    
    
    }
    
    void dszcz()             //编辑结束后输出数组
    {
    
    	char s[] = "是否确认保存地图,确认请按Y";
    	outtextxy(250, 50, s);
    	char tch = _getch();
    
    	if (tch != 'y') return;     //输入y确认继续
    
    	FILE* fp = NULL;            //将地图数组保存进所选文件路径中
    	fopen_s(&fp, FLMOP, "a+");  //追加方式打开文件
    
    	if (fp)
    	{
    		for (int i = 0; i < N; i++) //将地图信息写入文件
    		{
    			for (int j = 0; j < N; j++)
    				fprintf(fp, "%d ", cmap[i][j]);
    			fprintf(fp, "\n");
    
    		}
    		fprintf(fp, "\n");
    		fclose(fp);
    	}
    
    	char q[] = "恭喜!地图信息添加成功";
    	outtextxy(250, 50, q);
    
    	exit(0);
    }
    
    void Control()
    {
    	loadimage(&png1[0], _T("0.jpg"), SPACE, SPACE, true);
    	loadimage(&png1[1], _T("1.jpg"), SPACE, SPACE, true);
    	loadimage(&png1[2], _T("2.jpg"), SPACE, SPACE, true);
    	loadimage(&png1[3], _T("3.jpg"), SPACE, SPACE, true);
    	loadimage(&png1[4], _T("4.jpg"), SPACE, SPACE, true);
    	loadimage(&png1[5], _T("5.jpg"), SPACE, SPACE, true);
    
    
    	ck = _getch();              //接收
    
    	switch (ck)
    	{
    	case 'w':
    	
    		y--;          //光标移动
    		if (y < 0)          //对光标的移动位置加以限制
    		{
    			y = 0;
    			return;
    		}
    		break;
    
    	case 'a':
    	
    		x--;
    		if (x < 0)
    		{
    			x = 0;
    			return;
    		}
    		break;
    
    	case 's':
    	
    		y++;
    		if (y > 15)
    		{
    			y = 15;
    			return;
    		}
    		break;
    
    	case 'd':
    	
    		x++;
    		if (x > 15)
    		{
    			x = 15;
    			return;
    		}
    		break;
    
    	case '1':
    		putimage(x * SPACE, y * SPACE, &png1[1]); break;
    	case '2':
    		putimage(x * SPACE, y * SPACE, &png1[2]); break;
    	case '3':
    		putimage(x * SPACE, y * SPACE, &png1[3]); break;
    	case '4':
    		putimage(x * SPACE, y * SPACE, &png1[4]); break;
    	default:   putimage(x * SPACE, y * SPACE, &png1[0]);
    		ck = '0';    //输入其他ch为0空格,就是打印空地
    		break;
    	case 'z':
    		dszcz();            //z结束编辑地图
    	}
    
    	if (ck != 'w' && ck != 'a' && ck != 's' && ck != 'd' && ck != 'z')  //不是移动和保存时,将ck值存储进数组中
    		cmap[y][x] = ck - '0';
    }
    
    void TranMap()       //输出初始地图
    {
    	loadimage(&png1[0], _T("0.jpg"), SPACE, SPACE, true);
    	loadimage(&png1[1], _T("1.jpg"), SPACE, SPACE, true);
    	loadimage(&png1[2], _T("2.jpg"), SPACE, SPACE, true);
    	loadimage(&png1[3], _T("3.jpg"), SPACE, SPACE, true);
    	loadimage(&png1[4], _T("4.jpg"), SPACE, SPACE, true);
    	loadimage(&png1[5], _T("5.jpg"), SPACE, SPACE, true);
    	loadimage(&png1[6], _T("6.jpg"), SPACE, SPACE, true);
    	int i, j;           //循环用变量
    	//gotoxy(0, 0);
    	for (i = 0; i < N; i++)
    	{
    		for (j = 0; j < N; j++)
    		{
    			putimage(j * SPACE, i * SPACE, &png1[cmap[i][j]]);
    		}
    
    	}
    
    }
    
    
    void ShowhelpTxt()
    {
    	loadimage(&background, "background.jpg", 16 * SPACE, 16 * SPACE);
    	putimage(0, 0, &background);//显示界面
    	loadimage(&conti, "continue.jpg", 100, 50);
    	putimage(600, 600, &conti);
    	//显示文档文字
    	setbkmode(TRANSPARENT);//设置字体背景为透明
    	settextcolor(COLORREF(RGB(0, 0, 0)));//设置字体颜色为黑色
    	settextstyle(40, 0, _T("楷体"));//设置字体大小20,格式楷体
    	char c1[] = "显示16*16的地图方格";
    	char c2[] = "使用“w、a、s、d";
    	char c3[] = "移动光标(记得调成英文输入法)";
    	char c4[] = "左上角第一格为光标的坐标(0,0),以此类推";
    	char c5[] = "按下1将光标处设置为墙,2设置为目标";
    	char c6[] = "3设置为人,4设置为箱子,其余部分自动认为空地";
    	char c7[] = "按z保存地图。如果想要使用自己的地图";
    	char c8[] = "则需要更改路径为Newmap.txt!";
    	outtextxy(150, 270, c4);
    	outtextxy(150, 150, c1);
    	outtextxy(150, 190, c2);
    	outtextxy(150, 230, c3);
    	outtextxy(150, 390, c7);
    	outtextxy(150, 430, c8);
    	outtextxy(150, 310, c5);
    	outtextxy(150, 350, c6);
    
    	MOUSEMSG msg1;
    	while (true) // 主循环,循环监听鼠标信息
    	{
    		while (MouseHit())	//监听鼠标信息;当有鼠标消息的时候执行,可检测连续的鼠标信息
    		{
    			msg1 = GetMouseMsg();//获取鼠标消息
    			if (WM_LBUTTONDOWN == msg1.uMsg)//判断鼠标信息;鼠标左键按下
    			{
    				if (msg1.x > 600 && msg1.x < 700 && msg1.y > 600 && msg1.y < 650)//鼠标点击特定区域
    				{
    					return;
    				}
    
    			}
    
    		}
    
    	}
    	return;
    }
    
    
    展开全文
  • C语言不一样,python的for循环没有括号()之类的约束,怎么看他的边界在哪里吖?是看他代码开头的空格是否与for对齐吗? ``` size = 100 theta0Vals = np.linspace(-10, 10, size) # 前两个参数分别是数列的...
  • 大话数据结构

    2018-12-14 16:02:18
    C语言版大话数据结构与算法,很有趣,值得一读 大话数据结构 目 录 第1章数据结构绪论 1 1.1开场白 2 如果你交给某人一个程序,你将折磨他一整天;如果你教某人如何编写程序,你将折磨他一辈子。 1.2你数据结构...
  • C++程序员面试宝典

    热门讨论 2013-04-01 13:36:19
    许多开发者对C/C++语言及其底层原理掌握不牢固,在面试过程中经常漏洞百出,无法取得好成绩。而招聘单位为了得到高素质的员工往往采用各种形式的面试考察求职者,这让面试难度大大增加。求职者要想成功应聘,不仅...
  • 已出版多部著作和译著,包括《程序设计语言基础》(译著,1990),《Mathematica数学软件系统的应用与程序设计》(1994),《从问题到程序——程序设计与C语言引论》(1999) [同作者作品] 计算机基础教程(上下)...
  • 已出版多部著作和译著,包括《程序设计语言基础》(译著,1990),《Mathematica数学软件系统的应用与程序设计》(1994),《从问题到程序——程序设计与C语言引论》(1999) [同作者作品] 计算机基础教程(上下)...
  • C++程序设计语言(特别版)--源代码

    热门讨论 2012-04-23 07:33:51
    已出版多部著作和译著,包括《程序设计语言基础》(译著,1990),《Mathematica数学软件系统的应用与程序设计》(1994),《从问题到程序——程序设计与C语言引论》(1999) [同作者作品] 计算机基础教程(上下)...

空空如也

空空如也

1 2
收藏数 28
精华内容 11
关键字:

c语言矩阵怎么表示

c语言 订阅