数据结构(廿三) -- C语言版 -- 图 - 图的存储结构 -- 邻接表、逆邻接表

2023-12-09 17:20

本文主要是介绍数据结构(廿三) -- C语言版 -- 图 - 图的存储结构 -- 邻接表、逆邻接表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

内容预览

  • 零、读前说明
  • 一、概 述
  • 二、邻接表说明
    • 2.1、无向图的邻接表
    • 2.2、有向图的邻接表
    • 2.3、代码实现
      • 2.3.1、数据类型及操作函数定义
      • 2.3.2、主要操作函数的代码实现
      • 2.3.3、测试案例的实现源码
    • 2.4、测试效果
  • 三、逆邻接表
  • 四、简单对比总结

零、读前说明

  • 本文中所有设计的代码均通过测试,并且在功能性方面均实现应有的功能。
  • 设计的代码并非全部公开,部分无关紧要代码并没有贴出来。
  • 如果你也对此感兴趣、也想测试源码的话,可以私聊我,非常欢迎一起探讨学习。
  • 由于时间、水平、精力有限,文中难免会出现不准确、甚至错误的地方,也很欢迎大佬看见的话批评指正。
  • 嘻嘻。。。。 。。。。。。。。收!
      
       这一篇因项目上线中间忙拖了很久了才发出来,虽说也不是很复杂的内容,但是在学习的过程总结还是有很缓慢的,不过万幸坚持做完了,累并快乐着! 下一篇就不知道何年月能更新了(虽然看的人很少,但是还是要坚持做完),有事情回家一段时间,但愿所有事情能够顺利完成!!!

一、概 述

  在图中任何两个顶点之间都可能存在联系,所以图的存储结构应该需要根据具体问题的要求来进行设计。从图的逻辑结构定义来看,图中任何一个顶点都可以看成是第一个顶点。常用的存储结构有邻接矩阵邻接表(逆邻接表)、十字链表邻接多重表边集数组。那么本博文将带你就 “邻接表(逆邻接表)” 来窥探一二。。。

二、邻接表说明

  我们已经说明,对于稀疏图(边比较少的的图),邻接矩阵 占用空间大,空间浪费严重 。我们已经知道,使用链表形式可以明显的降低空间的浪费,那么是否可以将前面的数组形式的 邻接矩阵 用链表来表示呢。那么下面我们来看图的另外一种存储结构 — 邻接表 (Adjacency List)

  对于图中每个 顶点 v i v_i vi,将所有与 v i v_i vi 邻接的 顶点 连成一个 单链表,称为顶点 v i v_i vi边表(对于有向图则分别称为 出边表,反之为 入边表)。

  也就是说:

  1、将图中 所有的顶点 用一个数组来存储(也可以使用单链表存储,但数组容易读取顶点信息, vertex ),同时还需要保存指向此顶点的第一个邻接点信息的指针( firstEdge ),方便查找邻接点的信息;
  2、图中每一个顶点 v i v_i vi 的所有邻接点组成一个 线性表,由于邻接点的个数不确定,所以选择用单链表来存储;
  像这样把 数组链表 相结合的存储方式成为 邻接表

  邻接表 有两种结构:顶点表节点边表节点

  顶点表节点主要用于表示顶点的信息,主要需要记录顶点的信息指向此顶点的顶一个邻接点的指针,同样可以添加其他需要的元素,比如节点的个数等。

  边表节点主要用于表示顶点的邻接点,以及下一个邻接点。当然同样可以添加其他的需要的元素,比如边的权值等。

  本博文中所使用的边表结构和顶点表结构如下图所示。

图2.1 结构示意图

2.1、无向图的邻接表

  首先创造一个数组用来保存顶点的信息,以及一个指针指向顶点的第一个邻接点的指针,那么这个 first 指针域则成为了边表的头指针了。

  边表中的节点:表示的是节点在数组中的下标

  对于边 ( v 0 , v 1 ) (v_0,v_1) (v0,v1) 在邻接表中,可以理解为:顶点表中的第 0 个顶点( v 0 v_0 v0)到第 1 个顶点( v 1 v_1 v1)有一条边。

  无向图邻接表如下图所示。

图2.2 无向图邻接表示意图
  

  顶点的度:与顶点 v i v_i vi 连接的边的个数,也就是在 firstEdge 链表的节点的个数。

  如何去判断两个顶点 i, j 是否存在边:测试顶点 i 的边表中是否存在终点为 j 的节点。

2.2、有向图的邻接表

  有向图的邻接表是将顶点当作弧尾(默认是以弧尾)建立的邻接表,这样很容易的得到每个顶点的出度:顶点 i出边表的节点的个数

  但是求入度则变得困难:依次查找各个顶点的出边表中以顶点 v i v_i vi终点的节点的个数,所以需要将所有顶点及其边表扫描一遍。

  顶点 v i v_i vi 的所有的邻接点:该边表中所有顶点都是顶点 v i v_i vi 的邻接点。

  有向图邻接表如下图所示。

图2.3 有向图邻接表示意图
  

2.3、代码实现

2.3.1、数据类型及操作函数定义

  一、数据类型定义

  根据图的定义,定义图的数据结构类型中,需要包含两个重要的信息,一为 顶点的集合,二为 边的集合,本测试中加入一个 顶点的个数 的元素。测试代码中定义图的数据结构如下所示。

typedef void LGraph;
typedef void LVertex;typedef struct _tag_LGraph
{int count;        // 顶点的个数LVertex **vertex; // 顶点的信息LinkList **first; // 边集
} TLGraph;typedef struct _tag_ListNode
{LinkListNode next; //指向下一个边的指针int adjvex;        // 边的另一个顶点的下标int weight;        // 权值
} TListNode;

  二、图的操作函数定义

  图的操作,本博文中主要涉及三部分,创建销毁等操作边的集合的操作顶点的集合的操作。为了方便后续的添加其他的操作等,定义如下面代码所示。

#define UNDIRECTED_GRAPH 0               // 无向图定义
#define DIRECTED_GRAPH !UNDIRECTED_GRAPH // 有向图定义/****  边的操作集合**/
typedef struct __func_Edge
{int (*add)(LGraph *, int, int, int, int);int (*remove)(LGraph *, int, int, int);int (*get)(LGraph *, int, int);int (*count)(LGraph *, int);
} funcEdge;/****  顶点的操作集合**/
typedef struct __func_vertex
{int (*dgree)(LGraph *, int, int);int (*count)(LGraph *);
} funcVertex;/****  图的操作集合**/
typedef struct __func_Graph
{LGraph *(*create)(LVertex **, int);void (*destroy)(LGraph *);void (*clear)(LGraph *);void (*display)(LGraph *, int);funcEdge edge;     // 边的集合funcVertex vertex; //顶点的集合
} funcGraph;extern funcGraph funGraph;

2.3.2、主要操作函数的代码实现

  图的操作主要实现代码,方便起见,文件名称类型为 .cpp ,注释比较详细,此处不在赘述,代码如下所示。

/*** 功 能:*      创建并返回有n个顶点的图* 参 数:*      v:与顶点相关的数据的指针*      n:顶点的个数* 返回值:*      成功:*      失败:NULL**/
LGraph *LGraph_Create(LVertex **v, int n) // O(n)
{TLGraph *ret = NULL;if ((v == NULL) || (n < 1))goto END;// 申请一个图结构内存ret = (TLGraph *)malloc(sizeof(TLGraph));if (ret == NULL)goto END;ret->count = n;                                          //  图的节点个数赋值ret->vertex = (LVertex **)calloc(n, sizeof(LVertex *));  // 申请节点的空间ret->first = (LinkList **)calloc(n, sizeof(LinkList *)); // 申请节点的邻接表的内存if ((ret->vertex == NULL) || (ret->first == NULL)){free(ret);free(ret->vertex);free(ret->first);ret = NULL;goto END;}// 顶点赋值for (int i = 0; i < n; i++){ret->vertex[i] = v[i];}// 边集创建并赋值for (int i = 0; (i < n); i++){// 创建链表ret->first[i] = funLinkList.create();if (ret->first[i] == NULL) // 创建失败{for (int j = 0; j < i; j++){funLinkList.destory(ret->first[j]); // 销毁链表}// 内存释放free(ret->first);free(ret->vertex);free(ret);ret = NULL; // 返回值重定向break;}}END:return ret;
}/*** 功 能:*      添加顶点与顶点的关系 - 边*      在graph所指图中的v1和v2之间加上边,且边的权为w* 参 数:*      graph:要操作的图*      v1   :顶点(尾)的编号(位置)*      v2   :顶点(头)的编号(位置)*      w    :权值,如果为0,表示边不存在*      flag :表示是无向图还是有向图,如果为非0,表示为有向图* 返回值:*      0 :添加成功*      -1:添加失败,参数异常**/
int LGraph_AddEdge(LGraph *graph, int v1, int v2, int w, int flag) // O(1)
{TLGraph *tGraph = (TLGraph *)graph;TListNode *node = NULL, *node1 = NULL;int ret = -1;if (graph == NULL || w < 0 || //  w即可表示存在边(=1)也可表示边的权值(>=1),在表示边的权值的时候,一定是边存在(>0)((v1 < 0) && (v1 >= tGraph->count)) ||((v2 < 0) && (v2 >= tGraph->count)))goto RET;node = (TListNode *)malloc(sizeof(TListNode));if (node == NULL)goto RET;node->adjvex = v2;node->weight = w;funLinkList.insert(tGraph->first[v1], (LinkListNode *)node,funLinkList.length(tGraph->first[v1])); // 采用尾插入,方便在打印的时候比较if (!flag) // 如果是无向边,则再进行一次反向插入{node1 = (TListNode *)malloc(sizeof(TListNode));if (node == NULL)goto RET;node1->adjvex = v1;node1->weight = w;funLinkList.insert(tGraph->first[v2], (LinkListNode *)node1,funLinkList.length(tGraph->first[v2])); // 采用尾插入,方便在打印的时候比较}ret = 0;
RET:return ret;
}/*** 功 能:*      将graph所指图中v1和v2之间的边删除,返回权值* 参 数:*      graph:要操作的图*      v1   :顶点(尾)的位置(编号)*      v2   :顶点(头)的位置(编号)*      flag :表示是无向图还是有向图,如果为非0,表示为有向图* 返回值:*      删除成功 :非0值 -- 权值*      删除失败:0**/
int LGraph_RemoveEdge(LGraph *graph, int v1, int v2, int falg) // O(n*n)
{TLGraph *tGraph = (TLGraph *)graph;int ret = 0;TListNode *node = NULL;if ((tGraph == NULL) ||((v1 < 0) && (v1 >= tGraph->count)) ||((v2 < 0) && (v2 >= tGraph->count)))goto RET;for (int i = 0; i < funLinkList.length(tGraph->first[v1]); i++){node = (TListNode *)funLinkList.get(tGraph->first[v1], i);if (node->adjvex == v2){ret = node->weight;funLinkList.delet(tGraph->first[v1], i);break;}}if (!falg) // 如果是无线图的话,则删除反向的边{for (int i = 0; i < funLinkList.length(tGraph->first[v2]); i++){node = (TListNode *)funLinkList.get(tGraph->first[v2], i);if (node->adjvex == v1){funLinkList.delet(tGraph->first[v2], i);break;}}}free(node);
RET:return ret;
}/*** 功 能:*      将graph所指图中v1和v2之间的边的权值返回* 参 数:*      graph:要操作的图*      v1   :顶点(尾)的位置(编号)*      v2   :顶点(头)的位置(编号)* 返回值:*      0  :边 不存在*      -1 :参数异常*      其他:边存在或者权值**/
int LGraph_GetEdge(LGraph *graph, int v1, int v2) // O(n*n)
{TLGraph *tGraph = (TLGraph *)graph;int ret = -1;TListNode *node = NULL;if ((tGraph == NULL) ||((v1 < 0) && (v1 >= tGraph->count)) ||((v2 < 0) && (v2 >= tGraph->count)))goto RET;for (int i = 0; i < funLinkList.length(tGraph->first[v1]); i++){node = (TListNode *)funLinkList.get(tGraph->first[v1], i);if (node->adjvex == v2){ret = node->weight;break;}elseret = 0;}RET:return ret;
}
/*** 功 能:*      graph所指图中v顶点的度数* 参 数:*      graph:要操作的图*      v    :顶点 的位置(编号)*      flag :表示是无向图还是有向图,如果为非0,表示为有向图* 返回值:*      0  :参数异常*      其他:顶点的度**/
int LGraph_VertexDgree(LGraph *graph, int v, int flag) // O(n*n*n)
{TLGraph *tGraph = (TLGraph *)graph;int ret = 0;if ((tGraph == NULL) ||((v < 0) && (v >= tGraph->count)))goto RET;/***  对于有向图 ,顶点的度为出度加上入度*      出度 :等于邻接链表的长度*      入度 :其他的在邻接链表中存在此节点的每一个顶点*  对于无线图,顶点的度等于邻接链表的长度**/// 此节点的邻接链表的长度ret += funLinkList.length(tGraph->first[v]);if (flag) // 如果是有向图,则需要判断其他顶点与此顶点的关系{// 遍历图中的每一个顶点for (int i = 0; i < tGraph->count; i++){// 遍历顶点的邻接链表for (int j = 0; j < funLinkList.length(tGraph->first[i]); j++){TListNode *node = (TListNode *)funLinkList.get(tGraph->first[i], j);if (node->adjvex == v) // 如果邻接链表中存在此节点ret++;}}}
RET:return ret;
}funcGraph funGraph = {LGraph_Create,LGraph_Destroy,LGraph_Clear,LGraph_Display_matrix,{LGraph_AddEdge,LGraph_RemoveEdge,LGraph_GetEdge,LGraph_EdgeCount,},{LGraph_VertexDgree,LGraph_VertexCount,}};

2.3.3、测试案例的实现源码

  主要进行相关代码的测试,方便起见,测试案例的名称为 main.cpp ,注释比较详细,此处不在赘述说明,代码如下所示。

#include "../src/graph/graph.h"
#include <stdio.h>
#include <stdlib.h>int main(int argc, char *argv[])
{system("color "); // 颜色设置,用于在windows下终端显示的时候不明原因换行的问题printf("\n\e[1;31mLet's start with an example of an undirected graph:\e[0m\n");LVertex const *v[] = {"A", "B", "C", "D", "E", "F"};LGraph *ungraph = funGraph.create((LVertex **)v, 6);// 添加边funGraph.edge.add(ungraph, 0, 1, 1, UNDIRECTED_GRAPH); // (A, B)funGraph.edge.add(ungraph, 0, 2, 1, UNDIRECTED_GRAPH); // (A, C)funGraph.edge.add(ungraph, 0, 3, 1, UNDIRECTED_GRAPH); // (A, D)funGraph.edge.add(ungraph, 1, 4, 1, UNDIRECTED_GRAPH); // (B, E)funGraph.edge.add(ungraph, 1, 5, 1, UNDIRECTED_GRAPH); // (B, F)funGraph.edge.add(ungraph, 2, 1, 1, UNDIRECTED_GRAPH); // (C, B)funGraph.edge.add(ungraph, 3, 4, 1, UNDIRECTED_GRAPH); // (D, E)// 顶点的个数printf("\nThe number of vertices in the graph is : %d\n", funGraph.vertex.count(ungraph));// 显示邻接表printf("\nThe Adjacency List of the graph is :\n");funGraph.display(ungraph, 1);// 边的个数printf("\nThe number of Edge in the graph is : %d\n", funGraph.edge.count(ungraph, UNDIRECTED_GRAPH));// 顶点的度,参数为顶点在数组的下标printf("\nThe Degree of vertex 'B' is : %d\n", funGraph.vertex.dgree(ungraph, 1, UNDIRECTED_GRAPH));// 添加边,带有权值funGraph.edge.add(ungraph, 4, 2, 9, UNDIRECTED_GRAPH); // (E, C)  9// 边的权值printf("\nThe Weight of Edge (E, C) is : %d\n", funGraph.edge.get(ungraph, 4, 2));printf("\nThe Adjacency List of the graph is :\n");funGraph.display(ungraph, 0);// 添加边,带有权值  (E, C)funGraph.edge.remove(ungraph, 4, 2, 0);// 显示邻接表printf("\nThe Adjacency List of the graph is :\n");funGraph.display(ungraph, 0);// 边的个数printf("\nThe number of Edge in the graph is : %d\n", funGraph.edge.count(ungraph, UNDIRECTED_GRAPH));// 顶点的度,参数为顶点在数组的下标printf("\nThe Degree of vertex 'B' is : %d\n", funGraph.vertex.dgree(ungraph, 1, UNDIRECTED_GRAPH));// fixed 2020.08.29 : 原本测试时(下图中显示效果)写的是“undirected”,为错误的,现已经改正!printf("\n\e[1;31mLet's start with an example of directed graph:\e[0m\n");LGraph *graph = funGraph.create((LVertex **)v, 6);// 添加边funGraph.edge.add(graph, 0, 1, 1, DIRECTED_GRAPH); // <A, B>funGraph.edge.add(graph, 0, 2, 1, DIRECTED_GRAPH); // <A, C>funGraph.edge.add(graph, 0, 3, 1, DIRECTED_GRAPH); // <A, D>funGraph.edge.add(graph, 1, 4, 1, DIRECTED_GRAPH); // <B, E>funGraph.edge.add(graph, 1, 5, 1, DIRECTED_GRAPH); // <B, F>funGraph.edge.add(graph, 2, 1, 1, DIRECTED_GRAPH); // <C, B>funGraph.edge.add(graph, 3, 4, 8, DIRECTED_GRAPH); // <D, E>// 显示邻接表printf("\nThe Adjacency List of the graph is :\n");funGraph.display(graph, 0);// 边的个数printf("\nThe number of Edge in the graph is : %d\n", funGraph.edge.count(graph, DIRECTED_GRAPH));// 顶点的度,参数为顶点在数组的下标printf("\nThe Degree of vertex 'B' is : %d\n", funGraph.vertex.dgree(graph, 1, DIRECTED_GRAPH));// 权值printf("\nThe Weight of Edge <D, E> is : %d\n", funGraph.edge.get(graph, 3, 4));funGraph.destroy(ungraph);funGraph.destroy(graph);printf("\n\e[1;32msystem exited with return code %d\e[0m\n\n", 0);return 0;
}

  方便后续的测试与对照,上面测试案例中创建的图的显示效果如下图所示。

2.4 测试案例中图的示意图

2.4、测试效果

  本次测试是在 windows 环境下进行,也可以在 linux 环境下操作,详细说明在README.md中查看。

  使用 Cmake 编译,使用下面指令:

mkdir build ; cd build
在windows下使用    : cmake -G "MinGW Makefiles" .. # 注意 .. ,表示上级目录
在linux下使用      : cmake -G "Unix Makefiles" .. # 注意 .. ,表示上级目录
在linux下也可以使用 : cmake .. # 注意 .. ,表示上级目录
make

  经过cmake编译之后,可以使用在当前目录下使用指令 ./../runtime/graph来运行可执行程序,也可以进入到目录runtime中,然后使用指令 ./graph ,即可运行测试程序。实际测试的结果如下图所示。

2.5 测试案例显示的示意图

  
  至此,代码全部运行完成。

三、逆邻接表

  一、逆邻接表

  逆邻接表指的是将顶点当弧头建立的邻接表,这样便于得到每个顶点的 入度 或者以此顶点为弧头的弧。

  有向图邻接表如下图所示。

图3.1 逆邻接表示意图
  

  二、带权值的图(网)

  前面已经提到了,对于带有权值的边,只需要在边表节点的定义在增加一个数据域来存储权值即可。

  带权值的图如下图所示。

图3.2 带权值的图示意图
  

四、简单对比总结

   比较邻接矩阵、邻接点表的有确定,如下表所示。

表4.1 对比表
优点缺点
邻接矩阵1、通用性强
2、方便计算任意顶点的度(有向图中出度、入度)
3、容易判断任意两个顶点之间是否存在边
4、方便计算任意顶点的所有“邻接点”
1、占用空间大
2、对于稀疏图,空间利用率低
3、对于有向图,空间利用率低
邻 接 表1、方便查找任意顶点的所有“邻接点”
2、对于稀疏图,节约空间
3、对于无向图,方便计算任意顶点的度
4、对于有向图,方便计算任意顶点的“出度”
1、不易判断任意两个顶点之间是否存在边
2、需要 N N N个头指针 + 2 E +2E +2E 个节点
3、对于无向图,每条边都存储两次
4、对于有向图,不易计算顶点的“入度”

  好啦,废话不多说,总结写作不易,如果你喜欢这篇文章或者对你有用,请动动你发财的小手手帮忙点个赞,当然 关注一波 那就更好了,好啦,就到这儿了,么么哒(*  ̄3)(ε ̄ *)。

上一篇:数据结构(廿二) – C语言版 – 图 - 图的存储结构 – 邻接矩阵
下一篇:数据结构(廿四) – C语言版 – 图 - 图的存储结构 – 十字链表、邻接多重表、 边集数组

这篇关于数据结构(廿三) -- C语言版 -- 图 - 图的存储结构 -- 邻接表、逆邻接表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/474504

相关文章

C++中使用vector存储并遍历数据的基本步骤

《C++中使用vector存储并遍历数据的基本步骤》C++标准模板库(STL)提供了多种容器类型,包括顺序容器、关联容器、无序关联容器和容器适配器,每种容器都有其特定的用途和特性,:本文主要介绍C... 目录(1)容器及简要描述‌php顺序容器‌‌关联容器‌‌无序关联容器‌(基于哈希表):‌容器适配器‌:(

使用MongoDB进行数据存储的操作流程

《使用MongoDB进行数据存储的操作流程》在现代应用开发中,数据存储是一个至关重要的部分,随着数据量的增大和复杂性的增加,传统的关系型数据库有时难以应对高并发和大数据量的处理需求,MongoDB作为... 目录什么是MongoDB?MongoDB的优势使用MongoDB进行数据存储1. 安装MongoDB

Java中switch-case结构的使用方法举例详解

《Java中switch-case结构的使用方法举例详解》:本文主要介绍Java中switch-case结构使用的相关资料,switch-case结构是Java中处理多个分支条件的一种有效方式,它... 目录前言一、switch-case结构的基本语法二、使用示例三、注意事项四、总结前言对于Java初学者

使用JavaScript操作本地存储

《使用JavaScript操作本地存储》这篇文章主要为大家详细介绍了JavaScript中操作本地存储的相关知识,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... 目录本地存储:localStorage 和 sessionStorage基本使用方法1. localStorage

结构体和联合体的区别及说明

《结构体和联合体的区别及说明》文章主要介绍了C语言中的结构体和联合体,结构体是一种自定义的复合数据类型,可以包含多个成员,每个成员可以是不同的数据类型,联合体是一种特殊的数据结构,可以在内存中共享同一... 目录结构体和联合体的区别1. 结构体(Struct)2. 联合体(Union)3. 联合体与结构体的

PostgreSQL如何查询表结构和索引信息

《PostgreSQL如何查询表结构和索引信息》文章介绍了在PostgreSQL中查询表结构和索引信息的几种方法,包括使用`d`元命令、系统数据字典查询以及使用可视化工具DBeaver... 目录前言使用\d元命令查看表字段信息和索引信息通过系统数据字典查询表结构通过系统数据字典查询索引信息查询所有的表名可

异构存储(冷热数据分离)

异构存储主要解决不同的数据,存储在不同类型的硬盘中,达到最佳性能的问题。 异构存储Shell操作 (1)查看当前有哪些存储策略可以用 [lytfly@hadoop102 hadoop-3.1.4]$ hdfs storagepolicies -listPolicies (2)为指定路径(数据存储目录)设置指定的存储策略 hdfs storagepolicies -setStoragePo

HDFS—存储优化(纠删码)

纠删码原理 HDFS 默认情况下,一个文件有3个副本,这样提高了数据的可靠性,但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码,采用计算的方式,可以节省约50%左右的存储空间。 此种方式节约了空间,但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件,都会执行此策略。 默认只开启对 RS-6-3-1024k

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c