算法与数据结构讲义三（搜索算法）

1、第十三课 搜索算法12.0 搜索树12.1 搜索算法的基本原理12.2 广度优先搜索12.3 深度优先搜索12.4 练习12.0 搜索树引例：在一个4*4的棋盘上的左下角有一个马，按照国际象棋的规则，将这个马跳到右*上角。分析：首先建立棋盘的坐标，我们以左下角为(1,1)，以右上角、为(4,4)。按照马的移动规则，假定当前马的位置坐标为(x,y)，则移动方法有：（1）x=x+1; y=y+2（2）x=x+1; y=y-2;（3）x=x+2; y=y+1;（4）x=x+2; y=y-1;（5）x=x-1; y=y+2;（6）x=x-1; y=y-2;（7）x=x-2; y=y+1;（8）x=x-

2、2; y=y-1113223122113314424114244112332232343233234123243213244可以建立搜索树如下：图中表示：由(1,1)可以跳到(2,3)和(3,2)两个点(其它移动规则由于边界限制无法到达)；(2,3)又可以跳到(1,1)、(4,4)、(4,2)、(3,1)四个点，(3,2)可以跳达(1,1)、(1,3)、(2,4)、(4,4)四个点，。搜索树：按照数据元素的产生式规则建立起来的数据元素逻辑关系。特点：（1）数据之间的逻辑关系为一对多。 （2）每个结点数据的下一级子结点是由该结点的产生式规则生成。 （3）目标结点（答案数据）一定在搜索树中能够出现

3、。 （4）对于数据规模较大的问题，搜索树的结点将是海量的。 （5）搜索树可能是无穷无尽的（因为很多结点回重复出现）。12.1 搜索算法的基本原理：从搜索树中可以看出，一个问题从起始状态，通过穷举的方式建立起搜索树后，目标状态一定能在搜索树中出现。因此，只要建立起搜索树，就可以在其中搜索到目标状态（数据、路径、位置等）。搜索算法要解决的问题：产生式规则：由当前状态按照问题的需求和限制，生成新的状态的方法集合。搜索树的生成和存储：一般采用一边生成，一边搜索；存储方法有：集合、栈。搜索的方法：按行搜索：即从上到下，逐层搜索双向按行搜索：一边从上往下（起始状态到中间状态），一边从下往上逐层搜索（从目标

4、状态到中间状态），找到相同的中间状态即可。回朔法搜索：优先向更深层结点查找，走不通则换一条路，无法换则退回到上一层。搜索状态的减少：在生成搜索树时，对于已搜过的中间状态的再次出现，是否需要再次加入到树中重新搜索。12.2 广度优先搜索（bfs）又称宽度优先搜索，是一种从搜索树的根结点开始，沿着树的宽度遍历树的结点。如果所有节点均被访问，则算法中止。一般用于求从起始状态到目标状态所需的最少步骤数。算法过程：1、首先将根结点放入队列中。 2、从队首取出一个结点，按照产生式规则逐个生成新的结点数据，对新数据： 如果如果是目标结点，则结束算法并返回结果。 如果不是目标结点，则检查它是否已在搜索树中出现

5、过，未出现就将它作为尚未检查过的子结点加入到队列的队尾（特殊情况下，也有已出现过的结点重新入队的）。 3、重复步骤2。4、若队列为空，表示整张图都检查过了，即目标无法达到，结束算法并返回“找不到目标”的信息。 算法细化：用哈希数组判断新生成的结点数据是否已出现过。队列经常要多开一行，记录新结点的父亲（即该结点由上一层的哪个结点扩展而来），用于最后输出过程。如数据规模过大，需要使用循环队列（后果是无法记录父亲）。算法框架：function creat(i)begin case i of 1:creat:=按照第一产生式规则生成新状态数据； 2:creat:=按照第二产生式规则生成新状态数据； .

6、 . . end;end;/procedure bfs;begin join(起始状态); while not(队空) do begin 当前处理状态:=deq; for i:=第一产生式规则 to 最大产生式规则 do begin 新状态:=creat(i); if 新状态=目标状态 then begin print; exit; end else if not(haxi新状态) then begin join(新状态); haxi新状态:=true; end; end; end;end;空间复杂度：线性队列：O(最大可能状态数)循环队列：O(最大可能状态数/2)时间复杂度：最差情形下，BF

7、S必须寻找所有到可能结点的所有路径。O(最大可能状态数)完全性：广度优先搜索算法具有完全性。只要目标存在，则BFS一定会找到。但是，若目标不存在，且问题规模为无限大，则BFS将不收敛（不会结束）。适用范围：广度优先搜索是找到第一个解的算法，即距离根结点的边数最少的解。如果所有边的权值都相等（即所有产生新状态的代价相同），则这个解也是最优解。例一：将一个马从M*N的棋盘的左下角跳到右上角，需要的最少步数是多少？分析：1、用一个1.2,1.m*n的数组作为工作队列，用于存储搜索树。 2、使用m*n的二维哈希数组判重。 3、生成搜索树的同时，记录父节点的序号和新结点的层数。 4、最后从目标结点向起始

8、结点回朔，用一个栈存储回朔的中间状态。例二：在一个2n+1的一维棋盘上，有n个黑色棋子和n个白色棋子，初始状态如图：规定棋子移动规则如下：如果某棋子的旁边正好为空，这枚棋子可以移动到空位置上。如果某棋子的一侧有棋子，二那枚棋子的另一侧为空位置，这枚棋子可以跳过那枚棋子到空位置上。问：最少经过多少步，可以将棋盘状态变成分析：用2n+1位三进制数表示状态，如初始状态为：222201111，目标状态为111102222。转化为十进制进行存储，另记录空格位置。产生式规则：将棋子移动转化为空格的移动。空格向左移动空格向右移动空格向左跳动空格向右跳动用一个1.32n+1的哈希数组判重。例三：八数码问题。在

9、一个的九宫中有这个数及一个空格随机的摆放在其中的格子里，如图所示。现在要求实现这个问题：将该九宫格调整为如图2所示的形式。调整的规则是：每次只能将与空格（上、下、或左、右）相邻的一个数字平移到空格中。试编程实现这一问题的求解。 1238476512345678图一图二分析：1、字符串表达状态，另开一变量w记录空格位置。 2、空格移动规则：（1）向下移动：w=w+3。（2）向上移动：w=w-3。（3）向左移动：w=w-1。（4）向右移动：w=w+1。 3、用穷举法判重。（将来可以用排序二叉树判重）12.3 深度优先搜索（dfs）深度优先搜索是从根结点出发，沿着树的深度遍历树的结点。如果当前新产生

10、的结点还有以此为根的下一层结点，则沿此路继续下去，直到无法再深入访问时，回朔到上一层的结点，选另一条路继续深入访问。反复此过程，直到所有结点都被访问到为止。算法过程：首先将根结点放入栈中。取出栈顶结点，按照产生式规则生成新的结点数据，每产生一个：检查是否是目标结点，如果是且比保存的数据更优，刷新所保存的数据。检查该结点是否已搜过，如果是且比已保存的数据更优，则刷新所保存的数据，然后该结点进栈；如没有搜过，则保存数据并进栈。转第二步。如果栈空，则算法结束。细化说明：一般用回朔法，利用递归使用系统栈。哈希数组不仅用于判断新结点是否出现过，还用于保存到达该结点时的中间数据。算法框架：procedur

11、e dfs(结点数据);var i:integer;begin for i:=产生式规则一 to 最大产生式规则 do begin 新结点数据:=creat(i); if (新结点数据没有搜到过)or(新结点数据虽已搜过但本次搜索结果更优) then begin更新新结点搜索结果;dfs(新结点数据); end;end;procedure dfs(结点数据);var i:longint;beginfor i:=1 to 最大产生式规则 dobegin新结点:=creat(i);if 新结点是目标结点 thenbegin传回新结点;t:=true;exit;end;if 新结点更优 thenbe

12、gin更新新结点数据;dfs(新结点);if t then exit;end;end;end;空间复杂度：O(最大状态数) （主要用于存储各结点搜索结果）时间复杂度：O(最大产生式规则数最大状态数)深度优先搜索的理论依据是建立在穷举基础上的，所以时间是几何级数级的，其优化剪枝是非常必要的，因此，深搜的主要算法设计是在于如何剪枝，如何既高效地抛弃不必要的子树，又不至于将最优解剪掉，将是深搜的最大难点。适用范围：在缺乏有效的数学方法、递推算法，不符合动态规划要求，也没有专用算法可以应对，一般考虑使用深搜；得分情况将取决于优化剪枝的技巧（30-100分）。例一：有A、B、C、D、E 5本书，要分给张

13、、王、刘、赵、钱5位同学，每人只能选1本。每个人都将自己喜爱的书填写在下表中。请你设计一个程序，打印出让每个人都满意的所有分书方案。 张00110 王11001 刘01100 赵00010 钱01001分析：1、朴素的穷举法：产生5本书的所有全排列，共有5！=120个，逐个检查各种排列是否符合所有人的要求，符合则输出，否则丢弃。穷举法的改进：例如产生一个全排列12345时，第一个数1表示将第一本书给小张。但从表中可以看出，这是不可能的，因为小张只喜欢第三、第四本书。也就是说，X X X X这一类分法是不符合条件的。由此使我们想到，如果选定第一本书后，就立即检查一下是否符合条件，当发现第一个数的

14、选择不符合条件时，就不必再产生后面的4个数了，这样做可以减少很多的运算量。换句话说，第一个数只在3和4中选择，这样就可以减少35的运算量。同理，在选定了第一个数后，其他4个数字的选择也可以用类似的方法处理，即选择第二个数后，立即检查是否符合条件。例如，第一个数选3，第二个数选4后，立即进行检查，发现不符合条件，就另选第二个数。这样就又把34XXX一类的分法删去了，从而又减少了一部分运算量。开始张钱赵王刘王刘王张王钱王赵王刘赵王刘张王刘钱王钱张王钱刘王钱赵王刘张赵王刘张钱王钱张赵王钱张刘王钱赵张王钱赵刘王刘张赵钱深搜法：建立如上搜索树，每一层分发一本书，未向下扩展的结点为当前层已不合理，故剪去。

15、参考程序：program dfs1;const a:array1.5,1.5of boolean=(false,false,true,true,false), (true,true,false,false,true), (false,true,true,false,false), (false,false,false,true,false), (false,true,false,false,true);var outf:text; c:array1.5of integer; hx:array1.5of boolean;/procedure print;var i:integer;begin f

16、or i:=1 to 5 do case ciof 1:write(outf,张); 2:write(outf,王); 3:write(outf,刘); 4:write(outf,赵); 5:write(outf,钱); end;end;/procedure dfs(n:integer);var i:integer;begin for i:=1 to 5 do if (ai,n)and(not(hxi) then begin cn:=i; if n=5 then print; hxi:=true; dfs(n+1); hxi:=false; end;end;/begin assign(outf

17、,dfs_1.out); rewrite(outf); dfs(1); close(outf);end. 例二：跳马问题:在半张中国象棋盘上（5*9），有一匹马自左下角往右上角跳，今规定只许往右跳，不许往左跳。编程计算共有多少种不同的跳行路线，并将路线打印出来。 例三：0100001010000000111000010表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。 例四：有一个m*n的滑雪场，请找出最长的滑雪道。比如：24 40 20 30 28 44 33 35 20 18 30 40 40 35 22 15 13 2

18、0 30 35 25 20 12 18 28 40 30 10 11 20 15 30 12 15 20 12从第一排开始下滑，只能向上、下、左、右四个方向，且下一个区域的高度必须低于当前区域的高度，找出一条滑动距离最长的路径，可以在任何区域停止。12.4 习题：1、营求（save）【问题描述】铁达尼号发出了求救信号。距离最近的哥伦比亚号收到了信号，必须尽快赶到那里。通过侦测，哥伦比亚号获取了一张海洋图。这张图将海洋部分分化成nn个比较小的单位，其中用1标明的是陆地，用0标明的是海洋。船只能从一个格子移到相邻的四个格子。为了尽快赶到出事地点，哥伦比亚号最少需要走多远的距离。 【输入格式】第一行

19、为n，下面是一个nn的0，1矩阵，表示海洋地图。 最后一行为四个小于等于n的整数，分别表示哥伦比亚和铁达尼号的位置。 【输出格式】哥伦比亚号到达铁达尼号的最短距离，答案精确到整数。【输入样例】save.in 3 001 101 1001 1 3 3 【输出样例】save.out 4 【数据范围】n=1000 2、硬币翻转（coin） 00000000000000*0000000*00*0000000*00*000*000*0*00*0*0*00*00*00*0*000*0000*00000*000000000000【问题描述】在桌面上有一排硬币，共n枚，每一枚硬币均为正面向上。现在要把所有的硬

20、币翻转成反面向上，规则是每次可翻转任意n1枚硬币（正面向上的翻转成向下，向下的翻转成向上）。求一个最短的操作序列（将每次翻转n1枚硬币定为一次操作）。 【输入格式】只有一行，包含一个自然数n（n为不大于100的偶数） 【输出格式】第一行包含一个整数s，表示最少需要的操作次数。接下来s行每行分别表示每次操作后桌上硬币的状态（一行包含n个整数（0或1），表示每个硬币的状态，0正面向上，1反面向上，不允许出现多余的空格）。对于有多种操作方案的情况，则只需输出一种。 【输入样例】coin.in4 【输出样例】coin.out40111110000011111 3、闭合曲线面积(area)【问题描述】编

21、程计算由“*”号围城的下列图形的面积。面积计算方法是统计*号所围城的闭合曲线中水平线和垂直线交点的数目。如下图所示，在1010的二维数组中，有*围住了15点，因此面积为15。【输入样例】area.in 0000000000000011100000001001000000010010001000101001010100100100110110001000010000011111000000000000【输出样例】area.out15 4、细胞（cell） 【问题描述】一矩形阵列由数字09组成，数字19代表细胞，细胞的定义是沿细胞数字上下左右如果还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。

22、 如阵列： 0234500067 103456050020456006710000000089有4个细胞。 【输入格式】第一行为整数m，n，接着m行，每行n个数字 【输出格式】细胞的个数 【输入样例】cell.in 4 10 0234500067 1034560500 2045600671 0000000089 【输出样例】cell.out 4 5、最少转弯问题（turn） 【问题描述】给出一张地图，这张地图被分为nm（n，mn)，现在允许用量杯从水缸里取水或将水倒回水缸里，而且两个量杯中的水也可以相互倾倒，试设计计算机程序求出在m升的量杯中准确量得k升(Nknm)所需的最少操作步数。 (每一

23、个取水或倒水都算一个操作步数)【输入文件】ls.in仅一行，三个数，分别为m,n,k。【输出文件】ls.out仅一行，为最少步数。【样例数据】【输入】4 3 2【输出】6N8、 所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子： 43#9865#045+8468#6633其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。现在，我们对问题做两个限制：首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。其次，虫子把所有的数都啃光了，我们只知道哪

24、些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表午的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N-1)。输入数据保证N个字母分别至少出现一次。BADC +CRDADCCC上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解，- 输入文件输入文件alpha.in包含4行。第一行有一个正整数N(N=26)，后面的

25、3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有N位。- 输出文件输出文件alpha.out包含一行。在这一行中，应当包含唯一的那组解。解是这样表示的：输出N个数字，分别表示A，B，C所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。- 样例输入5ABCEDBDACEEBBAA- 样例输出1 0 3 4 2- 数据规模对于30的数据，保证有N10；对于50的数据，保证有N15；对于全部的数据，保证有N=26。附录资料:不需要的可以自行删除 libxml2应用实例Libxml2 是一个xml的c语言版的解析器，本来

26、是为Gnome项目开发的工具，是一个基于MIT License的免费开源软件。它除了支持c语言版以外，还支持c+、PHP、Pascal、Ruby、Tcl等语言的绑定，能在Windows、Linux、Solaris、MacOsX等平台上运行。功能还是相当强大的，相信满足一般用户需求没有任何问题。二、 Libxml2安装：一般如果在安装系统的时候选中了所有开发库和开发工具的话(Fedora Core系列下)，应该不用安装，下面介绍一下手动安装： 1) 从xmlsoft站点或ftp()站点下载libxml压缩包(libxml2-xxxx.tar.gz)2) 对压缩包进行解压缩 tar xvzf li

27、bxml2-xxxx.tar.gz3) 进入解压缩后的文件夹中运行 ./configure -prefix /home/user/myxml/xmlinst(此处为待安装的路径)或者直接使用 ./configure make make install 4) 添加路径 export PATH=/home/user/myxml/xmlinst/bin:$PATH 说明：为了结构清晰，最好将libxml2不安装在解压目录中。安装完成后就可以使用简单的代码解析XML文件，包括本地和远程的文件，但是在编码上有一些问题。Libxml默认只支持UTF8的编码，无论输入输出都是UTF-8，所以如果你解析完一个

28、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：在开始研究 Libxml2 库之前，先了解一下XML的相关基础。XML 是一种基于文本的格式，它可用来创建能够通过各种语言和平台访问

29、的结构化数据。它包括一系列类似 HTML 的标记，并以树型结构来对这些标记进行排列。例如，可参见清单 1 中介绍的简单文档。为了更清楚地显示 XML 的一般概念，下面是一个简化的XML文件。清单 1. 一个简单的 XML 文件 root delete 10清单 1 中的第一行是 XML 声明，它告诉负责处理 XML 的应用程序，即解析器，将要处理的 XML 的版本。大部分的文件使用版本 1.0 编写，但也有少量的版本 1.1 的文件。它还定义了所使用的编码。大部分文件使用 UTF-8，但是，XML 设计用来集成各种语言中的数据，包括那些不使用英语字母的语言。接下来出现的是元素。一个元素以开始标

30、记 开始(如 )，并以结束标记 结束(如 )，其中使用斜线 (/) 来区别于开始标记。元素是 Node 的一种类型。XML 文档对象模型 (DOM) 定义了几种不同的 Nodes 类型，包括:Elements(如 files 或者 age)Attributes(如 units)Text(如 root 或者 10)元素可以具有子节点。例如，age 元素有一个子元素，即文本节点 10。XML 解析器可以利用这种父子结构来遍历文档，甚至修改文档的结构或内容。LibXML2 是这样的解析器中的其中一种，并且文中的示例应用程序正是使用这种结构来实现该目的。对于各种不同的环境，有许多不同的解析器和库。Li

31、bXML2 是用于 UNIX 环境的解析器和库中最好的一种，并且经过扩展，它提供了对几种脚本语言的支持，如 Perl 和 Python。四、Libxml2中的数据类型和函数一个函数库中可能有几百种数据类型以及几千个函数，但是记住大师的话，90%的功能都是由30%的内容提供的。对于libxml2，我认为搞懂以下的数据类型和函数就足够了。1）内部字符类型xmlCharxmlChar是Libxml2中的字符类型，库中所有字符、字符串都是基于这个数据类型。事实上它的定义是：xmlstring.htypedef unsigned char xmlChar;使用unsigned char作为内部字符格式是

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

33、xmlmemory.h中定义。3）xmlChar*与其它类型之间的转换另外要注意，因为总是要在xmlChar*和char*之间进行类型转换，所以定义了一个宏BAD_CAST，其定义如下：xmlstring.h#define BAD_CAST (xmlChar *)原则上来说，unsigned char和char之间进行强制类型转换是没有问题的。4）文档类型xmlDoc、指针xmlDocPtrxmlDoc是一个struct，保存了一个xml的相关信息，例如文件名、文档类型、子节点等等；xmlDocPtr等于xmlDoc*，它搞成这个样子总让人以为是智能指针，其实不是，要手动删除的。xmlNewD

34、oc函数创建一个新的文档指针。xmlParseFile函数以默认方式读入一个UTF-8格式的文档，并返回文档指针。xmlReadFile函数读入一个带有某种编码的xml文档，并返回文档指针；细节见libxml2参考手册。xmlFreeDoc释放文档指针。特别注意，当你调用xmlFreeDoc时，该文档所有包含的节点内存都被释放，所以一般来说不需要手动调用xmlFreeNode或者xmlFreeNodeList来释放动态分配的节点内存，除非你把该节点从文档中移除了。一般来说，一个文档中所有节点都应该动态分配，然后加入文档，最后调用xmlFreeDoc一次释放所有节点申请的动态内存，这也是为什么我

35、们很少看见xmlNodeFree的原因。xmlSaveFile将文档以默认方式存入一个文件。xmlSaveFormatFileEnc可将文档以某种编码/格式存入一个文件中。5）节点类型xmlNode、指针xmlNodePtr节点应该是xml中最重要的元素了，xmlNode代表了xml文档中的一个节点，实现为一个struct，内容很丰富：tree.htypedef struct _xmlNode xmlNode;typedef xmlNode *xmlNodePtr;struct _xmlNode void *_private;/* application data */ xmlElementT

36、ype 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 link */ struct _xmlNode *next; /* next sibling link*/ s

37、truct _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;/* properties list */ xmlNs *nsDef; /* namespace definitions

38、 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可以组织为树。同时还有以下重要元素：节点中的文字内容：content；节点所属文档：doc；节点名字：name；节点的namespace：ns；节点属性列表：propert

39、ies；Xml文档的操作其根本原理就是在节点之间移动、查询节点的各项信息，并进行增加、删除、修改的操作。xmlDocSetRootElement函数可以将一个节点设置为某个文档的根节点，这是将文档与节点连接起来的重要手段，当有了根结点以后，所有子节点就可以依次连接上根节点，从而组织成为一个xml树。6）节点集合类型xmlNodeSet、指针xmlNodeSetPtr节点集合代表一个由节点组成的变量，节点集合只作为Xpath的查询结果而出现（XPATH的介绍见后面），因此被定义在xpath.h中，其定义如下：/* A node-set (an unordered collection of no

40、des 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 nodes in no particular order */ /* with_ns to check weth

41、er namespace nodes should be looked at */;可以看出，节点集合有三个成员，分别是节点集合的节点数、最大可容纳的节点数，以及节点数组头指针。对节点集合中各个节点的访问方式很简单，如下：xmlNodeSetPtr nodeset = XPATH查询结果;for (int i = 0; i nodeNr; i+)nodeset-nodeTabi;注意，libxml2是一个c函数库，因此其函数和数据类型都使用c语言的方式来处理。如果是c+，我想我宁愿用STL中的vector来表示一个节点集合更好，而且没有内存泄漏或者溢出的担忧。五、使用Libxml2项目中要实现

42、一个管理XML文件的后台程序，需要对XML文件进行创建，解析，修改，查找等操作，下面介绍如何利用libxml2提供的库来实现上述功能。1、创建XML文档：我们使用xmlNewDoc()来创建XML文档，然后使用xmlNewNode(),xmlNewChild(),xmlNewProp(),xmlNewText()等函数向XML文件中添加节点及子节点，设置元素和属性，创建完毕后用xmlSaveFormatFileEnc()来保存XML文件到磁盘(该函数可以设置保存XML文件时的编码格式)。示例1： #include #include #include int main(int argc, cha

43、r *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(NULL, BAD_CAST root); xmlDocSetRootElement(doc, root_node)

44、; /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, BAD_CAST node3, BAD_CASTnode has attributes); xmlNewPro

45、p(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); /Dumping document to stdio or file xmlSaveFormatFileEnc(argc 1

46、? 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/libxml2/xmlinst/lib/ -lxml2 （绿色文字为libxml2安装路径） -I后接头文件目录

47、 -L后接lib库目录2、解析XML文档 解析文档时仅仅需要文件名并只调用一个函数，并有错误检查，常用的相关函数有xmlParseFile(),xmlParseDoc(),获取文档指针后，就可以使用xmlDocGetRootElement()来获取根元素节点指针，利用该指针就可以在DOM树里漫游了，结束后要调用xmlFreeDoc()释放。示例2： xmlDocPtr doc; /定义解析文档指针 xmlNodePtr cur; /定义结点指针(你需要它为了在各个结点间移动) xmlChar *key; doc = xmlReadFile(url, MY_ENCODING, 256); /解析

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

49、tf(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 = cur-xmlChildrenNode; while(cur!=NULL) if (!xmlStrcmp(cur

50、-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),利用该节点指针漫游DOM树，就可以在XML文档中获取，修改，添加相关信息。示例3： 得到一个节点的内容： xmlChar *val

51、ue = xmlNodeGetContent(node); 返回值value应该使用xmlFree(value)释放内存得到一个节点的某属性值： xmlChar *value = xmlGetProp(node, (const xmlChar *)prop1); 返回值需要xmlFree(value)释放内存 设置一个节点的内容： xmlNodeSetContent(node, (const xmlChar *)test);设置一个节点的某属性值： xmlSetProp(node, (const xmlChar *)prop1, (const xmlChar *)v1); 添加一个节点元素：

52、xmlNewTextChild(node, NULL, (const xmlChar *)keyword, (const xmlChar *)test Element); 添加一个节点属性： xmlNewProp(node, (const xmlChar *)prop1, (const xmlChar *)test Prop);4、查找XML节点有时候对一个XML文档我们可能只关心其中某一个或某几个特定的Element的值或其属性，如果漫游DOM树将是很痛苦也很无聊的事，利用XPath可以非常方便地得到你想的Element。下面是一个自定义函数：示例4： xmlXPathObjectPtr g

53、et_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); xmlXPathFreeContext(context); if (result = NULL) printf

54、(xmlXPathEvalExpression return NULLn); return NULL; if (xmlXPathNodeSetIsEmpty(result-nodesetval) xmlXPathFreeObject(result); printf(nodeset is emptyn); return NULL; return result; 在doc指向的XML文档中查询满足xpath表达式条件的节点，返回满足这一条件的节点集合查询条件xpath的写法参见xpath相关资料。在查询完毕获取结果集后，就可以通过返回的 xmlXPathObjectPtr 结构访问该节点：示例5：

55、 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-nodesetval; 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(cu