Flyod算法求最短路径

1、PAGE PAGE 37一、问题分析和任务定义：课题16选择合适的结构表示图，在此基础上实现求解最短路径的Floyd算法。要求：对所设计的图结构，提供必要的基本功能。1.1问题分析：本课题要求用Floyd算法解决两个点间的的最短路径问题，首先需要有一个有向图，可以选用邻接矩阵、邻接表和边集数组三种来存储的，考虑到稀疏矩阵的问题，我们可以采用了领接矩阵来进行存储，存储每对节点的起点，终点和权值。对于两点间的最短路径的算法，应可以求我们输入的任意两点的最短路径，也可以求所有节点的最短路径，最短路径也即是两节点间所有通路中最短的一条，将它输出。可以方便我们让一些具体的事件的最优化。比如说交通图的最短

2、路程问题等，都可以在本算法上进行引升，会非常的方便。1.2解决思路：提供一个输入接口和标准的输入形式，让用户可以通过输入一组数据建立一个图，在屏幕上以邻接矩阵显示。通过floyd算法计算，可得出图中每对顶点的最短路径和路径长度。提供一个查询接口，通过输入起始顶点和终止顶点的代号，输出最短路径和路径长度。也可以查询全部的最短路径，让操作者自行选择。2、任务定义：要注意以下的问题输入输出的问题：2.1输入数据：顶点n(范围0-MVNUM)和边数e(范围0 - (n*(n-1)/2)，顶点信息i,j（字符型）(范围0 - MVNUM)，边的权值 w ( 整型)2.2输出数据：建立的邻接矩阵，有向图的

3、邻接矩阵，最短路径和最短路径长度（范围0MANUM）2.3算法所能达到的功能：求得任意两点间最短路径和路径长度输出显示。3、测试数据： 测试的数据组第一组第二组节点数边数3 33 3边的信息1 2 72 3 91 3 21 2 32 3 41 3 11矩阵输出 7 9 3 11 4 输出最短路径：1-2:路径长度为：7 路径为：1-21-3:路径长度为：2 路径为：1-3 2-1:不存在路径 2-3:路径长度为9 路径为：2-3 3-1:不存在路径 3-2:不存在路径1-2:路径长度为： 3 路径为：1-21-3:路径长度为： 7 路径为：1-2-3 2-1:不存在路径2-3:路径长度为： 4

4、 路径为：2-3 3-1:不存在路径 3-2:不存在路径 二、概要设计和数据结构的选择： 本次课程设计的数据的相关定义和主要程序段如下： 1、数据类型的定义typedef char VertexTYpe;/定义顶点的值类型typedef int Adjmatrix;/定义顶点的权值typedef struct/定义图的结构VertexTYpe vexsMVNUM;/顶点数组，类型定义为char 型Adjmatrix arcsMVNUMMVNUM;/领接矩阵为int 型MGraph;int D1MVNUM,p1MVNUM;int DMVNUMMVNUM,pMVNUMMVNUM;/设置为全局变量，

5、存放每对节点的路径和长度2、主程序的流程图： 图1流程图说明，首先开始程序输入边数和节点数，调用建图函数进行建图操作，对建好的图可以有选择进行矩阵的输出与否，再选择不同的Floyd算法来求 最短路径的可以有不同的输出形式，在结束每一种显示方法后，都可以返回到选择界面，直到选择3退出程序。三、详细设计和编码：我们可以从以下几个方面进行分析：1.弗罗伊德(Floyd)算法的基本思想如下： 对我们输入的有向网G=(V , E) i , jV 用邻接矩阵arcsij表示有向网。若 i 到 j 有一条弧，则存在arcsij 为从 i 到 j 的路径长度，但它不一定是从 i 到 j 的最短 路径长度。我们

6、应依次考虑 i 到 j 能否有以顶点1、2、n 为中间结点的更短路径，这样进行不短的试探。1.1首先考虑从 i 到 j是否有以顶点 1 为中间结点的路径。 即：是否有、，若有，则比较arcsij 与arcsi1+ arcs1j较短者为当前所求得的最短路径。 此时应修正arcsij 的值，并记下 i 的后继1。此时arcsij 的值是从 i 到 j 、中间顶点数不大于 1 时的最短路径。1.2 其次，考虑从 i 到 j 是否有包含顶点 2 为中间点的路径。若无，则从 i 到 j 的最短路径是(1)步求得的；若有，则 i 2j 可分解为两条路径：i 2 、2j 这两条路径的最短路径是是在(1)步求

7、得的，（即i 2 、2j可分别看作 (1)步中的 i 、j，它们之间有数量不超过 1 的结点）比较arcs1ij 与arcs1i2+ arcs12j ， 可修正arcs1ij 的值为arcs2ij （它是当前求得的从 i 到 j 、中间顶点数不大于 2 时的最短路径）。1.3 依次类推，直到考虑了顶点 n 加入当前从 i 到 j 的最短路径后，得出最新的最短路径arcsnij 是从 i 到 j 之间经过的顶点数不大于 n 时的最短路径长度现已考虑了所有顶点作为中间点的可能性，因而它必是从 i 到 j 的最短路径。由此看出，弗罗伊德(Floyd)算法实际是通过一系列矩阵D0 、 D1 、D2 D

8、n 、来实现求解。其中，Dkij 即arcsij ，表示从 i 到 j 之间经过的顶点数=k 时的最短路径长度。讨论的焦点： 由Dk-1 求Dk if (Dk-1ik +Dk-1kj Dkij) Dkij = Dk-1ik +Dk-1kj 算法描述如下： 设置矩阵Dn+1n+1 记录两点间的路径长度。 设置矩阵p n+1n+1 记录每一次求得当前两点 i 、j 间最短路径时，i 的后继顶点。算法结束时，由p ij的值可得从 i 到 j 的最短路径上的各个顶点。第一步： 初始化Dn+1n+1 ，使Dij=arcsij 初始化p n+1n+1 ，若从 i 到 j 有一条弧，则p ij j ,否则p

9、 ij 0 。第二步： 做 n 次迭代，每次均试图将顶点 k 扩充到当前求得的最短路径上，并修改 i 的后继顶点号。 for ( k=1; k=n; k+ ) for ( i =1; i =n; i + ) for (j =1; jDik+Dkj) Dij = Dik+Dkj ; p ij = p ik ; 2. 弗罗伊德(Floyd)算法主要描述如下： void Floyd(MGraph *G,int n)/Floyd算法 int i,j,k; for(i=1;i=n;i+)/设置路径长度D和路径P的初值 for(j=1;jarcsij!=Maxint)/判断两点间是否有直接路径，有就将它的

10、权值赋给Pij pij=j; else pij=0;/否则将它赋为0 Dij=G-arcsij; for(k=1;k=n;k+)/查找他们之间是否有中间节点 for(i=1;i=n;i+) for(j=1;j=n;j+) if(Dik+Dkj2,2-3但对于要求输入1-3的最短路径时，系统给出没有路径。在对Floyd函数进行仔细的查看和分析，了解到是因为循环没有做好控制，加以修改就解决了问题。2.该开始没有对输入的节点的起点和终点的的范围加以控制，系统不提示，但在矩阵输出时，就不会输出超过范围的点的信息。加了一do()while循环就可以提示，还可以对错误的输入进行再次的输入。3.在显示最短路

11、径的时候,同样出现了显示路径时对于1-2,23,的情况显示为1-3，而不是1-2-3，查看了是因为循环的空吃问题。加以修改即可。4. 在显示矩阵时，开始没有作好格式的控制，输出不对齐，修改格式后有不小心加了一个空格，细心检查才发现了错误。5.在最后的选择case语句时，刚开始没有做返回到主控菜单，设计不全面，加了一个do()while循环控制就可以了。1.2算法的时、空性能分析：时间复杂度是：O（n3），空间复杂度是：O（n）1.3改进设想： 通过对程序测试的进一步的分析，我认为可以对它进行以下的改进：1.可以在程序中加入实现无向图的邻接矩阵，设置它们是等距的，这样就可以求无向图的两节点间的最

12、短路径问题。2.可以预存入一组数据，假设为已经是一个已知地点的交通图，让用户可以直接查询不用输入建立有向图。2对设计实现的回顾讨论和分析：这是一个实现求图的最短路径算法的课题，所以需要先建立一个图来进行Floyd算法的运算。设计程序的时候，先是初步设计一些子函数：createMGaph()函数，用来输入数据构建有先向图的邻接矩阵表示；dispmgraph()函数，用来显示已建立的有向图用领接矩阵输出；Floyd()函数，用来求有向图的最短路径。Floyd1()函数，在4的基础上输出所有节点的最短路径。main()主函数，主要做的是界面，用来提示用户的输入输出以及一些选择。五.用户使用说明：运行

13、程序后可看到系统界面，提示用户输入他要查阅的图的情况，先输入图的节点数和边数，在输入每边的信息，包括起点，终点和权值。（超过范围会有提示）比如说节点数和边数为3和3输入为3 3（空格隔开），输入起点终点和权值同样是空格隔开；再来就是选择是否输出有向图的领接矩阵，用户输入y/n进行选择即可；之后是本设计的重点部分，用户可以通过1,2,3 选择不同的方法来求最短路径。1为求两个确定点的最短路径，用户需要输入要查询的起点和终，比如求1-3的最短路径，输入格式：1 3（有空格），就可查阅1-3的路径了。在用户查阅完之后，可以通过0 0结束查询。2为求所有节点的最短路径，选择后，系统会给出所有的节点之间

14、的最短路径。选择三将退出整个系统。六、测试结果：1.1当输入3个顶点3条边1-2-3的路径长大于1-3的情况为：1.2当输入3个顶点3条边1-2-3的路径长小于1-3的情况为：2.结果分析：通过对程序的运行结果的分析，我们可以看到通过选择不同的求路径的方法所得到的最短路径长度是一样的，。由1.1和1.2的输出最短路径的不同就可以得到，。它所求的最短路径是所有通路中最短的一条。七参考资料： 1.严蔚敏等。数据结构题集（c语言）。北京：清华大学出版社，1999年2月第1版。2.李春葆。数据结构与算法教程。北京：清华大学出版社，2005年6月第1 版。3.苏仕华，数据结构课程设计,北京：机械工业出版

15、社, 2005年5月第1版。八、源程序：#include#define MVNUM 100 /最大顶点个数#define Maxint 32767/用32767来表示无穷#include#include#include#includeenum boolean False,True;typedef char VertexTYpe;/定义顶点的值类型typedef int Adjmatrix;/定义顶点的权值typedef struct/定义图的结构VertexTYpe vexsMVNUM;/顶点数组，类型定义为char 型Adjmatrix arcsMVNUMMVNUM;/领接矩阵为int 型M

16、Graph;int D1MVNUM,p1MVNUM;int DMVNUMMVNUM,pMVNUMMVNUM;/设置为全局变量，存放每对节点的路径和长度void createMGaph(MGraph *G, int n,int e)int i,j,k=1,w;for(i=1;ivexsi=(char)i;for(i=1;i=n;i+)for(j=1;jarcsij=Maxint;cout输入e条边的顶点终点和权值(以空格隔开!):n|jn)/判断是否超出范围 printf(错识,重新输入n); else G-arcsij=w;/将权值赋给G-arcsij k+;while(kn;/e=G-e;f

17、or(i=1;i=n;i+)for(i=1;i=n;i+)for(j=1;jarcsij=Maxint)/若两点间无直接路径为 /if(i!=j)/printf( ); coutsetw(8); /else cout setw(8)0; else coutsetw(8)arcsij;/否则输出它的权值 coutendl;void Floyd(MGraph *G,int n)/Floyd算法 int i,j,k; for(i=1;i=n;i+)/设置路径长度D和路径P的初值 for(j=1;jarcsij!=Maxint)/判断两点间是否有直接路径，有就将它的权值赋给Pij pij=j; els

18、e pij=0;/否则将它赋为0 Dij=G-arcsij; for(k=1;k=n;k+)/查找他们之间是否有中间节点 for(i=1;i=n;i+) for(j=1;j=n;j+) if(Dik+DkjDij)/判断中间节点的路径之和是否小于Dij小于就将中间节点的值赋给Pij Dij=Dik+Dkj; pij=k;void Floyd1(MGraph *G,int n)/Flyod算法 int i,j,k; for(i=1;i=n;i+)/设置路径长度D和路径P的初值 for(j=1;jarcsij; pij=0; for(k=1;k=n;k+) for(i=1;i=n;i+) for(

19、j=1;j=n;j+) if(Dik+DkjDij) /判断中间节点的路径之和是否小于Dij小于就将中间节点的值赋给Pij Dij=Dik+Dkj; pij=k; for(i=1;i=n;i+)/循环控制输出所有的节点间的最短路径 for(j=1;j=n;j+) if(i!=j) cout ij:; if(Dij=Maxint) if(i!=j) cout不存在路径endl; else cout路径长度为：setw(3)Dij ; cout路径为：i; k=pij; while(k!=0) coutk; k=pkj; coutjendl; void main() MGraph *G; int

20、n,e,v,w,k; char x; int m; /int xz=1; G=(MGraph *)malloc(sizeof (MGraph); cout *endl; cout * *endl; cout *Floyd算法求最短路径*endl; cout * *endl; cout *endlx;/scanf(%c,&x);coutendl;if(x=y)cout显示图的领接矩阵为：m;switch(m)case 1:do printf(输入您要查找的起点和终点，以0,0结束查找!：v,w:); scanf(%d %d,&v,&w); if(v=0&w=0) break; Floyd(G,n

21、);/调用Flyod算法 k=pvw; if(k=0) printf(顶点%d到%d无路径!n,v,w); else printf(从顶点%d到%d的最短路径为：%d,v,w,v); while(k!=w) printf(-%d,k); k=pkw; printf(-%d,w); printf(路径长度：%dn,Dvw); while(v!=0&w!=0);break; case 2: printf(输出有向图的所有节点的最短路径为：n); Floyd1(G,n);/调用Flyod算法 break;case 3:printf(求最短路径结束！);break;while(m!=3); 九、指导老

22、师点评附录资料:不需要的可以自行删除 libxml2应用实例Libxml2 是一个xml的c语言版的解析器，本来是为Gnome项目开发的工具，是一个基于MIT License的免费开源软件。它除了支持c语言版以外，还支持c+、PHP、Pascal、Ruby、Tcl等语言的绑定，能在Windows、Linux、Solaris、MacOsX等平台上运行。功能还是相当强大的，相信满足一般用户需求没有任何问题。二、 Libxml2安装：一般如果在安装系统的时候选中了所有开发库和开发工具的话(Fedora Core系列下)，应该不用安装，下面介绍一下手动安装： 1) 从xmlsoft站点或ftp()站点

23、下载libxml压缩包(libxml2-xxxx.tar.gz)2) 对压缩包进行解压缩 tar xvzf libxml2-xxxx.tar.gz3) 进入解压缩后的文件夹中运行 ./configure -prefix /home/user/myxml/xmlinst(此处为待安装的路径)或者直接使用 ./configure make make install 4) 添加路径 export PATH=/home/user/myxml/xmlinst/bin:$PATH 说明：为了结构清晰，最好将libxml2不安装在解压目录中。安装完成后就可以使用简单的代码解析XML文件，包括本地和远程的文件

24、，但是在编码上有一些问题。Libxml默认只支持UTF8的编码，无论输入输出都是UTF-8，所以如果你解析完一个XML得到的结果都是UTF8的，如果需要输出GB2312或者其它编码，需要ICONV来做转码(生成UTF8编码的文件也可以用它做),如果系统中没有安装iconv的话，需要安装libiconv。 1) 下载libiconv压缩包(例如libiconv-1.11.tar.gz) 2) 对压缩包进行解压缩tar xvzf libiconv-1.11.tar.gz 3) 进入解压缩后的文件夹中运行 ./configure make make install三、关于XML：在开始研究 Libx

25、ml2 库之前，先了解一下XML的相关基础。XML 是一种基于文本的格式，它可用来创建能够通过各种语言和平台访问的结构化数据。它包括一系列类似 HTML 的标记，并以树型结构来对这些标记进行排列。例如，可参见清单 1 中介绍的简单文档。为了更清楚地显示 XML 的一般概念，下面是一个简化的XML文件。清单 1. 一个简单的 XML 文件 root delete 10清单 1 中的第一行是 XML 声明，它告诉负责处理 XML 的应用程序，即解析器，将要处理的 XML 的版本。大部分的文件使用版本 1.0 编写，但也有少量的版本 1.1 的文件。它还定义了所使用的编码。大部分文件使用 UTF-8

26、，但是，XML 设计用来集成各种语言中的数据，包括那些不使用英语字母的语言。接下来出现的是元素。一个元素以开始标记 开始(如 )，并以结束标记 结束(如 )，其中使用斜线 (/) 来区别于开始标记。元素是 Node 的一种类型。XML 文档对象模型 (DOM) 定义了几种不同的 Nodes 类型，包括:Elements(如 files 或者 age)Attributes(如 units)Text(如 root 或者 10)元素可以具有子节点。例如，age 元素有一个子元素，即文本节点 10。XML 解析器可以利用这种父子结构来遍历文档，甚至修改文档的结构或内容。LibXML2 是这样的解析器中

27、的其中一种，并且文中的示例应用程序正是使用这种结构来实现该目的。对于各种不同的环境，有许多不同的解析器和库。LibXML2 是用于 UNIX 环境的解析器和库中最好的一种，并且经过扩展，它提供了对几种脚本语言的支持，如 Perl 和 Python。四、Libxml2中的数据类型和函数一个函数库中可能有几百种数据类型以及几千个函数，但是记住大师的话，90%的功能都是由30%的内容提供的。对于libxml2，我认为搞懂以下的数据类型和函数就足够了。1）内部字符类型xmlCharxmlChar是Libxml2中的字符类型，库中所有字符、字符串都是基于这个数据类型。事实上它的定义是：xmlstring

28、.htypedef unsigned char xmlChar;使用unsigned char作为内部字符格式是考虑到它能很好适应UTF-8编码，而UTF-8编码正是libxml2的内部编码，其它格式的编码要转换为这个编码才能在libxml2中使用。还经常可以看到使用xmlChar*作为字符串类型，很多函数会返回一个动态分配内存的xmlChar*变量，使用这样的函数时记得要手动删除内存。2） xmlChar相关函数如同标准c中的char类型一样，xmlChar也有动态内存分配、字符串操作等相关函数。例如xmlMalloc是动态分配内存的函数；xmlFree是配套的释放内存函数；xmlStrcm

29、p是字符串比较函数等等。基本上xmlChar字符串相关函数都在xmlstring.h中定义；而动态内存分配函数在xmlmemory.h中定义。3）xmlChar*与其它类型之间的转换另外要注意，因为总是要在xmlChar*和char*之间进行类型转换，所以定义了一个宏BAD_CAST，其定义如下：xmlstring.h#define BAD_CAST (xmlChar *)原则上来说，unsigned char和char之间进行强制类型转换是没有问题的。4）文档类型xmlDoc、指针xmlDocPtrxmlDoc是一个struct，保存了一个xml的相关信息，例如文件名、文档类型、子节点等等；

30、xmlDocPtr等于xmlDoc*，它搞成这个样子总让人以为是智能指针，其实不是，要手动删除的。xmlNewDoc函数创建一个新的文档指针。xmlParseFile函数以默认方式读入一个UTF-8格式的文档，并返回文档指针。xmlReadFile函数读入一个带有某种编码的xml文档，并返回文档指针；细节见libxml2参考手册。xmlFreeDoc释放文档指针。特别注意，当你调用xmlFreeDoc时，该文档所有包含的节点内存都被释放，所以一般来说不需要手动调用xmlFreeNode或者xmlFreeNodeList来释放动态分配的节点内存，除非你把该节点从文档中移除了。一般来说，一个文档中

31、所有节点都应该动态分配，然后加入文档，最后调用xmlFreeDoc一次释放所有节点申请的动态内存，这也是为什么我们很少看见xmlNodeFree的原因。xmlSaveFile将文档以默认方式存入一个文件。xmlSaveFormatFileEnc可将文档以某种编码/格式存入一个文件中。5）节点类型xmlNode、指针xmlNodePtr节点应该是xml中最重要的元素了，xmlNode代表了xml文档中的一个节点，实现为一个struct，内容很丰富：tree.htypedef struct _xmlNode xmlNode;typedef xmlNode *xmlNodePtr;struct _x

32、mlNode void *_private;/* application data */ xmlElementType type; /* type number, must be second ! */ const xmlChar *name; /* the name of the node, or the entity */ struct _xmlNode *children;/* parent-childs link */ struct _xmlNode *last; /* last child link */ struct _xmlNode *parent;/* child-parent

33、 link */ struct _xmlNode *next; /* next sibling link*/ struct _xmlNode *prev; /* previous sibling link*/ struct _xmlDoc*doc;/* the containing document */ /* End of common part */ xmlNs *ns; /* pointer to the associated namespace */ xmlChar *content; /* the content */ struct _xmlAttr *properties;/* p

34、roperties list */ xmlNs *nsDef; /* namespace definitions on this node */ void *psvi;/* for type/PSVI informations */ unsigned short line; /* line number */ unsigned short extra;/* extra data for XPath/XSLT */;可以看到，节点之间是以链表和树两种方式同时组织起来的，next和prev指针可以组成链表，而parent和children可以组织为树。同时还有以下重要元素：节点中的文字内容：con

35、tent；节点所属文档：doc；节点名字：name；节点的namespace：ns；节点属性列表：properties；Xml文档的操作其根本原理就是在节点之间移动、查询节点的各项信息，并进行增加、删除、修改的操作。xmlDocSetRootElement函数可以将一个节点设置为某个文档的根节点，这是将文档与节点连接起来的重要手段，当有了根结点以后，所有子节点就可以依次连接上根节点，从而组织成为一个xml树。6）节点集合类型xmlNodeSet、指针xmlNodeSetPtr节点集合代表一个由节点组成的变量，节点集合只作为Xpath的查询结果而出现（XPATH的介绍见后面），因此被定义在xpa

36、th.h中，其定义如下：/* A node-set (an unordered collection of nodes without duplicates).*/typedef struct _xmlNodeSet xmlNodeSet;typedef xmlNodeSet *xmlNodeSetPtr;struct _xmlNodeSet int nodeNr; /* number of nodes in the set */ int nodeMax; /* size of the array as allocated */ xmlNodePtr *nodeTab;/* array of

37、nodes in no particular order */ /* with_ns to check wether namespace nodes should be looked at */;可以看出，节点集合有三个成员，分别是节点集合的节点数、最大可容纳的节点数，以及节点数组头指针。对节点集合中各个节点的访问方式很简单，如下：xmlNodeSetPtr nodeset = XPATH查询结果;for (int i = 0; i nodeNr; i+)nodeset-nodeTabi;注意，libxml2是一个c函数库，因此其函数和数据类型都使用c语言的方式来处理。如果是c+，我想我宁愿用

38、STL中的vector来表示一个节点集合更好，而且没有内存泄漏或者溢出的担忧。五、使用Libxml2项目中要实现一个管理XML文件的后台程序，需要对XML文件进行创建，解析，修改，查找等操作，下面介绍如何利用libxml2提供的库来实现上述功能。1、创建XML文档：我们使用xmlNewDoc()来创建XML文档，然后使用xmlNewNode(),xmlNewChild(),xmlNewProp(),xmlNewText()等函数向XML文件中添加节点及子节点，设置元素和属性，创建完毕后用xmlSaveFormatFileEnc()来保存XML文件到磁盘(该函数可以设置保存XML文件时的编码格式

39、)。示例1： #include #include #include int main(int argc, char *argv) xmlDocPtr doc = NULL; /* document pointer */ xmlNodePtr root_node = NULL, node = NULL, node1 = NULL;/* node pointers */ / Creates a new document, a node and set it as a root node doc = xmlNewDoc(BAD_CAST 1.0); root_node = xmlNewNode(NU

40、LL, BAD_CAST root); xmlDocSetRootElement(doc, root_node); /creates a new node, which is attached as child node of root_node node. xmlNewChild(root_node, NULL, BAD_CAST node1,BAD_CAST content of node1); / xmlNewProp() creates attributes, which is attached to an node. node=xmlNewChild(root_node, NULL,

41、 BAD_CAST node3, BAD_CASTnode has attributes); xmlNewProp(node, BAD_CAST attribute, BAD_CAST yes); /Here goes another way to create nodes. node = xmlNewNode(NULL, BAD_CAST node4); node1 = xmlNewText(BAD_CASTother way to create content); xmlAddChild(node, node1); xmlAddChild(root_node, node); /Dumpin

42、g document to stdio or file xmlSaveFormatFileEnc(argc 1 ? argv1 : -, doc, UTF-8, 1); /*free the document */ xmlFreeDoc(doc); xmlCleanupParser(); xmlMemoryDump();/debug memory for regression tests return(0); 编译：gcc -o xmlCreator xmlCreator.cpp-I/home/usr/libxml2/xmlinst/include/libxml2/ -L /home/usr/

43、libxml2/xmlinst/lib/ -lxml2 （绿色文字为libxml2安装路径） -I后接头文件目录 -L后接lib库目录2、解析XML文档 解析文档时仅仅需要文件名并只调用一个函数，并有错误检查，常用的相关函数有xmlParseFile(),xmlParseDoc(),获取文档指针后，就可以使用xmlDocGetRootElement()来获取根元素节点指针，利用该指针就可以在DOM树里漫游了，结束后要调用xmlFreeDoc()释放。示例2： xmlDocPtr doc; /定义解析文档指针 xmlNodePtr cur; /定义结点指针(你需要它为了在各个结点间移动) xml

44、Char *key; doc = xmlReadFile(url, MY_ENCODING, 256); /解析文件 /*检查解析文档是否成功，如果不成功，libxml将指一个注册的错误并停止。一个常见错误是不适当的编码。XML标准文档除了用UTF-8或UTF-16外还可用其它编码保存。如果文档是这样，libxml将自动地为你转换到UTF-8。更多关于XML编码信息包含在XML标准中。*/ if (doc = NULL ) fprintf(stderr,Document not parsed successfully. n); return; cur = xmlDocGetRootElemen

45、t(doc); /确定文档根元素 /*检查确认当前文档中包含内容*/ if (cur = NULL) fprintf(stderr,empty documentn); xmlFreeDoc(doc); return; /*在这个例子中，我们需要确认文档是正确的类型。“root”是在这个示例中使用文档的根类型。*/ if (xmlStrcmp(cur-name, (const xmlChar *) root) fprintf(stderr,document of the wrong type, root node != root); xmlFreeDoc(doc); return; cur =

46、cur-xmlChildrenNode; while(cur!=NULL) if (!xmlStrcmp(cur-name, (const xmlChar *)keyword) key = xmlNodeListGetString(doc, cur-xmlChildrenNode, 1); printf(keyword: %sn, key); xmlFree(key); cur = cur-next; xmlFreeDoc(doc); 3、修改XML元素及属性等信息要修改XML文档里的元素及属性等信息，先需要解析XML文档，获得一个节点指针(xmlNodePtr node),利用该节点指针漫游

47、DOM树，就可以在XML文档中获取，修改，添加相关信息。示例3： 得到一个节点的内容： xmlChar *value = xmlNodeGetContent(node); 返回值value应该使用xmlFree(value)释放内存得到一个节点的某属性值： xmlChar *value = xmlGetProp(node, (const xmlChar *)prop1); 返回值需要xmlFree(value)释放内存 设置一个节点的内容： xmlNodeSetContent(node, (const xmlChar *)test);设置一个节点的某属性值： xmlSetProp(node,

48、(const xmlChar *)prop1, (const xmlChar *)v1); 添加一个节点元素： xmlNewTextChild(node, NULL, (const xmlChar *)keyword, (const xmlChar *)test Element); 添加一个节点属性： xmlNewProp(node, (const xmlChar *)prop1, (const xmlChar *)test Prop);4、查找XML节点有时候对一个XML文档我们可能只关心其中某一个或某几个特定的Element的值或其属性，如果漫游DOM树将是很痛苦也很无聊的事，利用XPat

49、h可以非常方便地得到你想的Element。下面是一个自定义函数：示例4： xmlXPathObjectPtr get_nodeset(xmlDocPtr doc, const xmlChar *xpath) xmlXPathContextPtr context; xmlXPathObjectPtr result; context = xmlXPathNewContext(doc); if (context = NULL) printf(context is NULLn); return NULL; result = xmlXPathEvalExpression(xpath, context);

50、 xmlXPathFreeContext(context); if (result = NULL) printf(xmlXPathEvalExpression return NULLn); return NULL; if (xmlXPathNodeSetIsEmpty(result-nodesetval) xmlXPathFreeObject(result); printf(nodeset is emptyn); return NULL; return result; 在doc指向的XML文档中查询满足xpath表达式条件的节点，返回满足这一条件的节点集合查询条件xpath的写法参见xpath

51、相关资料。在查询完毕获取结果集后，就可以通过返回的 xmlXPathObjectPtr 结构访问该节点：示例5： xmlChar *xpath = (/root/node/key=keyword); xmlXPathObjectPtr app_result = get_nodeset(doc,xpath); if (app_result = NULL) printf(app_result is NULLn); return; int i = 0; xmlChar *value; if(app_result) xmlNodeSetPtr nodeset = app_result-nodesetv

52、al; for (i=0; i nodeNr; i+) cur = nodeset-nodeTabi; cur = cur-xmlChildrenNode; while(cur!=NULL) value = xmlGetProp(cur,(const xmlChar *)key); if (value != NULL) printf(value: %snn, d_ConvertCharset(utf-8, GBK, (char *)value); xmlFree(value); value = xmlNodeGetContent(cur); if (value != NULL) printf(value: %snn, d_ConvertCharset(utf-8, GBK, (char *)value); xmlFree(value); xmlXPathFre