数据结构与算法实验指导书.docx

上连第Z三堂大竽徽据牯构与算法实脸播导行
计算机与信息学院
实验三树
【实验目的】
【实验平台】
操作系统:
开发环境:
熟练掌握在链式二叉树在二叉链表存储结构上的基本操作。
Windows2000 或 Windows XPC 或 C++
【实验内容及要求】
要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所 有叶子及结点总数的操作等。具体实现要求：
17 .基于先序遍历的构造算法：输入是二叉树的先序序列，但必须在其中加入虚结点以示空指针 的位置。假设虚结点输入时用空格字符表示。
18 .用广义表表示所建二叉树。
19 .分别利用前序遍历中序遍历、后序遍历所建二叉树。
20 .求二叉树结点总数，观察输出结果。
21 .求二叉树叶子总数，观察输出结果。
22 .交换各结点的左右子树，用广义表表示法显示新的二叉树。
23 . （★）二叉树采用链接存储结构，其根结点指针为T,设计一个算法对这棵二叉树的每个结 点赋值：（注意要修改DataType类型）
a）叶结点的值为3
b）只有左孩子或右孩子的结点那么其值分别等于左孩子或右孩子的值
c）左、右孩子均有的结点，那么其值等于左、右孩子结点的值之和
d）用广义表表示法显示所建二叉树
【参考框架】
#include
#include b.h>
〃二叉树的链式存储表示
typedef char DataType;〃应由用户定义DataType的实际类型
typedef struct node
{ DataType data;struct node *lchild, *rchild; 〃左右孩子指针
} BinTNode;〃结点类型
typedef BinTNode *BinTree;
void main（）void ListBinTree(BinTree T); //用广义表表示二叉树
void DisplayBinTree(BinTree T); 〃用凹入表表示二叉树
void CreateBinTreeBinTree *T); 〃构造二叉链表 void Preorder(BinTree T);〃前序遍历二叉树void Inorder(BinTree T);//中序遍历二叉树
void Postorder(BinTree T);〃后序遍历二叉树int nodes(BinTree T);〃计算总结点数
int leafs(BinTree T);//计算总叶子数BinTree sw叩(BinTree T);〃交换左右子树
B inTree T;
printf("请输入先序序列(虚结点用空格表示)：\n"); CreateBinTree(&T);
ListBinTree(T);
printf(n\nn);Display B inTree(T);
printf("前序遍历:\nn);Preorder(T);
printf(n\nn);printf("中序遍历：\nH);
Inorder(T);printf(n\nn);
printf("后序遍历:\nn);Postorder(T);
printf(H\nn);
printf("二叉树的总结点数为 ％d\n”,nodes(T));
printf("二叉树的总叶子结点数为％d\n\leafs(T)); T=swap(T);
ListBinTree(T); printf(n\nn);
}
〃构造二叉链表
void CreateBinTree(BinTree *T)
(//在此插入必要的语句
}
//用广义表表示二叉树
void ListBinTree(BinTree T)〃在此插入必要的语句
〃用凹入表表示二叉树
void DisplayBinTree(BinTree T) (//在此插入必要的语句
)
〃前序遍历二叉树
void Preorder(B inTree T)
(//在此插入必要的语句
)
〃中序遍历二叉树
void Inorder(B inTree T)
(〃在此插入必要的语句
}
〃后序遍历二叉树
void Postorder(B inTree T)
(〃在此插入必要的语句
}
〃计算总结点数
int nodes(B inTree T)
(//在此插入必要的语句
)
//计算总叶子数
int leafs(BinTree T)//在此插入必要的语句
〃交换左右子树
B inTree swap(B inTree T)
(//在此插入必要的语句
}
【实验报告】《数据结构与算法》实验报告三
学院：班级：
学号：姓名：
日期：程序名：L6LCPP一、上机实验的问题和要求：
要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所 有叶子及结点总数的操作等。具体实现要求：
i. 基于先序遍历的构造算法：输入是二叉树的先序序列，但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符表示。
ii. 用广义表表示所建二叉树。
iii. 分别利用前序遍历、中序遍历、后序遍历所建二叉树。
iv. 求二叉树结点总数，观察输出结果。
v. 求二叉树叶子总数，观察输出结果。
vi. 交换各结点的左右子树，用广义表表示法显示新的二叉树。
vii. (★)二叉树采用链接存储结构，其根结点指针为T,设计一个算法对这棵二叉树的每个结点赋值：(注意要修改DataType类型)
a.叶结点的值为3b.只有左孩子或右孩子的结点那么其值分别等于左孩子或右孩子的值
c.左、右孩子均有的结点，那么其值等于左、右孩子结点的值之和d.用广义表表示法显示所建二叉树
二、源程序及注释:
三、运行输出结果：
四、调试和运行程序过程中产生的问题及采取的措施:
实验四Huffman树【实验目的】
【实验平台】
操作系统:
开发环境:
理解建立Huffman树的算法。
Windows2000 或 Windows XPC 或 C++
【实验内容及要求】
阅读理解建立Huffman树的算法，对该算法进行运行及调试。具体实现要求:
1 .调试并运行Huffman算法。
2 .(★)求Huffman树的带权路径长度WPL。
【参考框架】#include >
#include #include typedef HTNode HuffmanTree[m]; //HuffmanTree 是向量类型
//Huffman树的存储结构
#define n 100
#define m 2*n-l typedef struct { float weight;
int lchild,rchild,parent;
}HTNode;
〃叶子数目
〃树中结点总数
〃结点类型
〃权值，不妨设权值均大于零
〃左右孩子及双亲指针
typedef struct
{ char ch;〃存储字符
char bits[n+l];//存放编码位串}CodeNode;
typedef CodeNode HuffmanCode[n];void InitHuffmanTree(HuffmanTree T);〃初始化 Huffman 树
void InputWeight(HuffmanTree T);〃输入权值void SelectMin(HuffmanTree T,int i,int *pl,int *p2);
void main() (
void CreateHuffmanTree(HuffmanTree T); 〃构造 Huffman 树 void CharSetHuffmanEncoding(HuffmanTree T,HuffmanCode H); HuffmanTree T;
HuffmanCode H;
CreateHuffmanTree(T);
CharSetHuffmanEncoding(T,H);void CreateHuffmanTree(HuffmanTree T)
{//构造Huffman树，为其根结点
int i,pl,p2;
InitHuffmanTree(T);〃将 T 初始化
InputWeight(T);〃输入叶子权值至T[0..n-l]的weight域
for(i=n;i{ SelectMin(T,i-l ,&p 1 ,&p2);〃在中选择两个权最小的根结点，其序号分别为pl和p2
T[pl] .parent=T[p2] .parent=i;T[i].lchild=pl;//最小权的根结点是新结点的左孩子
T[i].rchild=p2;//次小权的根结点是新结点的右孩子T[i].weight=T[p I].weight+T[p2]. weight;
)}
void InitHuffmanTree(HuffmanTree T){〃初始化Huffman树
int i;
for (i=0;ichild=T[i].rchild=T[i] .parent=NULL;
)}
void InputWeight(HuffmanTree T){〃输入权值
int i;
for (i=0;i ] .parent==NULL)
(if(T[j].weight亲的位置
char cd[n+l];//临时存放编码
int start;〃指示编码在cd中的起始位置
cd[n]=,\0,;〃编码结束符
printf(”请输入字符：)
for(i=0;ic)?!O,:,r； c=p;〃继续上溯)
strcpy(H[i].bits,&cd[start]);//复制编码位串
) for(i=0;i及注释:
三、运行输出结果:
四、调试和运行程序过程中产生的问题及采取的措施:

实验五查找（二叉排序树）
【实验目的】
【实验平台】
操作系统:
开发环境:
熟练掌握二叉排序树上的查找算法。
Windows2000 或 Windows XPC 或 C++
【实验内容及要求】
实现二叉排序树上的查找算法。具体实现要求：
24 .用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树。
25 .用广义表表示所建二叉树。
26 .按中序遍历这棵二叉排序树。
27 .在二叉排序树上插入结点。
28 .删除二叉排序树上的结点。
29 .在二叉排序树上实现查找算法。

【参考框架】#include
#include typedef int InfoType;
typedef int Key Type;〃假定关犍字类型为整数typedef struct node〃结点类型
(
Key Type key;〃关键字项
InfoType otherinfo;〃其它数据域，InfoType视应用情况而定 下面不处理它
struct node *lchild,*rchild;〃左右孩子指针 jBSTNode;typedef BSTNode *BSTree;//BSTree 是二叉排序树的类型
void main() (
void InsertB ST (B STree *Tptr,Key Type key); 〃将关键字 key 插入二叉排序树中
BSTree CreateBST(void);〃建立二叉排序树
void ListBinTree(BSTree T);〃用广义表表示二叉树
void DclBSTNodc(BSTrcc *Tptr,KcyTypc key); 〃在 二叉 排序树 中删除 关键字 key
BSTNode *SearchBST(BSTree T,KeyType key); 〃在二叉 排序树中查找 关键字 key
BSTree T;
BSTNode *p;
int key;printf(”请输入关键字(输入。为结束标志)：\nn);
T=CreateBST();ListBinTree(T);
printf(n\nn);printf(”请输入欲插入关键字：”)； scanf(H%dn,&key);
InsertB ST(&T,key);ListBinTree(T);
printf(n\nn);printf(”请输入欲删除关键字：”)； scanf(H%dn,&key);
DelBSTNode(&T,key);
ListBinTree(T);
printf(n\nn);
printf(”请输入欲查找关键字：”)；
scanf(H%dn,&key);
p=SearchBST(T,key);
if(p==NULL)printf("没有找到%d! \n\key);
elseprintf("找到％(1! \nn,key);
ListBinTree(p);
printf(H\nn);}
〃将关键字key插入二叉排序树中 void InsertBST(BSTree *Tptr,Key Type key) (
〃在此插入必要的语句}
//建立二叉排序树BSTree CreateBST(void) (
〃在此插入必要的语句)
//在二叉排序树中删除关键字keyvoid DelBSTNode(BSTree ^Tptr, Key Type key)
〃在此插入必要的语句实验一顺序表
【实验目的】
【实验平台】
操作系统:
开发环境:
熟练掌握线性表在顺序存储结构上的基本操作。
Windows2000 或 Windows XPC 或 C++
【实验内容及要求】
顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、 插入与删除。具体实现要求：
1. 从键盘输入10个整数，产生顺序表，并输出结点值。
2. 从键盘输入1个整数，在顺序表中查找该结点。假设找到，输出结点的位置；假设找不到，那么显 示“找不到”。
3. 从键盘输入2个整数，一个表示欲插入的位置i,另一个表示欲插入的数值x,将x插入在对 应位置上，输出顺序表所有结点值，观察输出结果。
4. 从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。
【参考框架】
#include
#include
〃顺序表的定义：
#define ListSize 100//表空间大小可根据实际需要而定，这里假设为100
typedef int DataType; //DataType可以是任何相应的数据类型如int, float或char
typedef struct
{ DataType data[ListSize]; 〃向量 data 用于存放表结点int length;//当前的表长度
}SeqList;
void main()
(SeqList L;
int i,x;int n=10;//欲建立的顺序表长度
L.length=0;void CreateList(SeqList *L,int n);
void PrintList(SeqList L,int n);int LocateList(SeqList L,DataType x);
void InsertList(SeqList DataType xjnt i);void DeleteList(SeqList *L,int i);
//用广义表表示二叉树void ListBinTree(BSTree T)
(
〃在此插入必要的语句}
//在二叉排序树中查找关键字keyBSTNode *SearchBST(BSTree T,Key Type key)
(
〃在此插入必要的语句}
【实验报告】《数据结构与算法》实验报告五
学院：班级：
学号：姓名：
日期：程序名：L8.CPP一、上机实验的问题和要求：
实现二叉排序树上的查找算法。具体实现要求：
1 .用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树。
2 .用广义表表示所建二叉树。
3 .按中序遍历这棵二叉排序树。
4 .在二叉排序树上插入结点。
5 .删除二叉排序树上的结点。
6 .在二叉排序树上实现查找算法。
二、源程序及注释：
三、运行输出结果：
四、调试和运行程序过程中产生的问题及采取的措施:
实验六排序
【实验目的】
【实验平台】
操作系统:
开发环境:
熟练掌握插入、冒泡、直接选择、快速、归并等排序算法。
Windows2000 或 Windows XPC 或 C++
【实验内容及要求】
实现直接插入、冒泡、直接选择、快速、归并等排序算法。具体实现要求:
30 .利用L91.CPP实现直接插入排序算法。
31 .利用L92.CPP实现冒泡排序算法。
32 .利用L93cpp实现直接选择排序算法。
33 .利用L94.CPP实现快速排序算法。
34 .利用L95.CPP实现归并排序算法。
【实验报告】《数据结构与算法》实验报告六
学院：班级：
学号：姓名:
日期：
程序名：L91 .CPP L92.CPP L93.CPP L94.CPP L95.CPP一、上机实验的问题和要求：
实现直接插入、冒泡、直接选择、快速、归并等排序算法。具体实现要求：
1 .利用L9LCPP实现直接插入排序算法。
2 .利用L92.CPP实现冒泡排序算法。
3 .利用L93.CPP实现直接选择排序算法。
4 .利用L94.CPP实现快速排序算法。
5 .利用L95.CPP实现归并排序算法。
二、源程序及注释:
三、运行输出结果:
U!
调试和运行程序过程中产生的问题及采取的措施:

附录资料:不需要的可以自行删除 libxml2应用实例
Libxml2是一个xml的c语言版的解析器，本来是为Gnome工程开发的 工具，是一个基于MIT License的免费开源软件。它除了支持c语言版以 外，还支持C++、PHP、Pascal> Ruby、Tel等语言的绑定，能在Windows、 Linux、Solaris、MacOsX等平台上运行。功能还是相当强大的，相信满 足一般用户需求没有任何问题。
二、Libxml2 安装：
一般如果在安装系统的时候选中了所有开发库和开发工具的话（Fedora Core系列下），应该不用安装，下面介绍一下手动安装：
1）从 xmlsoft 站点或 ftp （ftp. xmlsoft. org）站点下载 libxml 压缩包 （libxml2-xxxx. tar. gz）2）对压缩包进行解压缩tar xvzf libxm12-xxxx. tar. gz
3）进入解压缩后的文件夹中运行./configure —prefix /home/usei7myxml/xmlinst（此处为待安
装的路径）或者直接使用./configuremake
make install
4）添加路径export PATH=/home/user/myxml/xmlinst/bin:$PATH
说明：为了结构清晰，最好将libxml2不安装在解压目录中。
安装完成后就可以使用简单的代码解析XML文件，包括本地和远程的文 件，但是在编码上有一些问题。Libxml默认只支持UTF—8的编码，无论 输入输出都是UTF-8,所以如果你解析完一个XML得到的结果都是UTF-8 的，如果需要输出GB2312或者其它编码，需要ICONV来做转码（生成UTF -8编码的文件也可以用它做），如果系统中没有安装iconv的话，需要安 装 libiconvo
1）下载 libiconv 压缩包（例如 libiconv-1. 11. tar. gz）

2）对压缩包进行解压缩 tar xvzf libiconv-1. 11. tar. gz
3）进入解压缩后的文件夹中运行./configure
makemake install
三、关于XML：
在开始研究Libxml2库之前，先了解一下XML的相关基础。XML是一 种基于文本的格式，它可用来创立能够通过各种语言和平台访问的结构化 数据。它包括一系列类似HTML的标记，并以树型结构来对这些标记进行 排列。
例如，可参见清单1中介绍的简单文档。为了更清楚地显示XML的一 般概念，下面是一个简化的XML文件。
清单1. 一个简单的XML文件
encoding=〃UTF-8”?〉
rootdelete

清单1中的第一行是XML声明，它告诉负责处理XML的应用程序， 即解析器，将要处理的XML的版本。大局部的文件使用版本1.0编写, 但也有少量的版本1.1的文件。它还定义了所使用的编码。大局部文件 使用UTF-8,但是，XML设计用来集成各种语言中的数据，包括那些不使 用英语字母的语言。
接下来出现的是元素。一个元素以开始标记 开始（如files»,其中使用斜线（/）来区别于开始标记。 元素是Node的一种类型。XML文档对象模型（D0M）定义了几种不同的 Nodes类型,包括：
Elements （如 files 或者 age）
Attributes （如 units）
Text （如 root 或者 10）
元素可以具有子节点。例如，age元素有一个子元素，即文本节点10。
XML解析器可以利用这种父子结构来遍历文档，甚至修改文档的结构或 内容。LibXML2是这样的解析器中的其中一种，并且文中的例如应用程序 正是使用这种结构来实现该目的。对于各种不同的环境，有许多不同的解 析器和库。LibXML2是用于UNIX环境的解析器和库中最好的一种，并且 经过扩展，它提供了对几种脚本语言的支持，如Perl和Pythono
四、Libxml2中的数据类型和函数
一个函数库中可能有几百种数据类型以及几千个函数，但是记住大师 的话，90%的功能都是由30%的内容提供的。对于Iibxml2,我认为搞 懂以下的数据类型和函数就足够了。
1）内部字符类型xmlChar
xmlChar是Libxml2中的字符类型，库中所有字符、字符串都是基于这个数据类型。事实上它的定义是：xmlstring.h
typedef unsigned char xmlChar;
使用unsigned char作为内部字符格式是考虑到它能很好适应 UTF-8编码，而UTF-8编码正是Iibxml2的内部编码，其它格式的编码 要转换为这个编码才能在Iibxml2中使用。
还经常可以看到使用xmlChar*作为字符串类型，很多函数会返回一 个动态分配内存的xmlChar*变量，使用这样的函数时记得要手动删除内 存。
2) xmlChar相关函数
如同标准c中的char类型一样，xmlChar也有动态内存分配、字符 串操作等相关函数。例如xmlMalloc是动态分配内存的函数；xmlFree 是配套的释放内存函数；xmlStrcmp是字符串比拟函数等等。
基本上xmlChar字符串相关函数都在xmlstring.h中定义；而动态 内存分配函数在xmlmemory.h中定义。
3) xmlChar*与其它类型之间的转换
另外要注意，因为总是要在xmlChar*和char*之间进行类型转换， 所以定义了一个宏BAD_CAST,其定义如下：xmlstring.h
#define BAD_CAST (xmlChar *)
原那么上来说，unsigned char和char之间进行强制类型转换是没有问题的。
4）文档类型xmlDoc、指针xmlDocPtr
xmlDoc是一个struct,保存了一个xml的相关信息，例如文件名、 文档类型、子节点等等；xmlDocPtr等于xmlDoc*,它搞成这个样子总 让人以为是智能指针，其实不是，要手动删除的。
xmlNewDoc函数创立一个新的文档指针。
xmlParseFile函数以默认方式读入一个UTF-8格式的文档，并返回 文档指针。
xmlReadFile函数读入一个带有某种编码的xml文档，并返回文档 指针；细节见Iibxml2参考手册。
xmlFreeDoc释放文档指针。特别注意，当你调用xmlFreeDoc时, 该文档所有包含的节点内存都被释放，所以一般来说不需要手动调用 xmlFreeNode或者xmlFreeNodeList来释放动态分配的节点内存，除 非你把该节点从文档中移除了。一般来说，一个文档中所有节点都应该动 态分配，然后加入文档，最后调用xmlFreeDoc 一次释放所有节点申请 的动态内存，这也是为什么我们很少看见xmlNodeFree的原因。
xmlSaveFile将文档以默认方式存入一个文件。
xmlSaveFormatFileEnc可将文档以某种编码/格式存入一个文件中。
5）节点类型 xmlNode、指针 xmlNodePtr
节点应该是xml中最重要的元素了，xmlNode代表了 xml文档中的 一个节点，实现为一个struct,内容很丰富：tree.h
typedef struct _xmlNode xmlNode;
typedef xmlNode *xmlNodePtr;
struct _xmlNode {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 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;/* properties 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可以组织为树。同时 还有以下重要元素：
节点中的文字内容：content；CreateList(&L,n);〃建立 M页序表
PrintList(L,n);〃打印顺序表printf("输入要查找的值："); scanf(M%dn,&x);
i=LocateList(L,x);// 顺序表查找printf("输入要插入的位置:"); scanf(n%dn,&i);
printf("输入要插入的元素："); scanf(n%d\&x);InsertList(&L,x,i);//顺序表插入
PrintList(L,n);//打印顺序表printf("输入要删除的位置:"); scanf(n%d\&i);
DeleteList(&L,i)；〃川页序表册 U 除PrintList(L,n);〃打印顺序表
}
〃顺序表的建立：
void CreateList(SeqList *L,int n)
(//在此插入必要的语句
)
〃顺序表的打印:
void PrintList(SeqList L,int n) (//在此插入必要的语句
}
〃顺序表的查找：
int LocateList(SeqList L,DataType x) (//在此插入必要的语句
}
〃顺序表的插入：
void InsertList(SeqList *L,DataType x,int i)
• 节点所属文档：doc；
• 节点名字：name；
• 节点的 namespace： ns；
• 节点属性列表：properties；
Xml文档的操作其根本原理就是在节点之间移动、查询节点的各项信 息，并进行增加、删除、修改的操作。
xmlDocSetRootElement函数可以将一个节点设置为某个文档的 根节点，这是将文档与节点连接起来的重要手段，当有了根结点以后，所 有子节点就可以依次连接上根节点，从而组织成为一个xml树。
6） 节点集合类型 xmlNodeSet、指针 xmlNodeSetPtr
节点集合代表一个由节点组成的变量，节点集合只作为Xpath的查 询结果而出现（XPATH的介绍见后面）,因此被定义在xpath.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 nodes in no particular order */
/* @@ with_ns to check wether namespace nodes should be looked at @@ */
)；
可以看出，节点集合有三个成员，分别是节点集合的节点数、最大可 容纳的节点数，以及节点数组头指针。对节点集合中各个节点的访问方式 很简单，如下：
xmlNodeSetPtr nodeset = XPATH 查询结果；
for (int i = 0; i < nodeset->nodeNr; i+ + )
{nodeset->nodeTab[i];
}
注意，Iibxml2是一个c函数库，因此其函数和数据类型都使用c语 言的方式来处理。如果是C+ + ,我想我宁愿用STL中的vector来表示 一个节点集合更好，而且没有内存泄漏或者溢出的担忧。
五、使用Libxml2
工程中要实现一个管理XML文件的后台程序，需要对XML文件进行创立, 解析，修改，查找等操作，下面介绍如何利用libxml2提供的库来实现上 述功能。
1、创立XML文档：
我们使用xmlNewDoc ()来创立XML文档，然后使用xmlNewNode (), xmlNewChild (), xmlNewProp () xmlNewText ()等函数向
XML文件中添加节点及子节点，设置元素和属性，创立完毕后用 xmlSaveFormatFileEnc ()来保存XML文件到磁盘(该函数可以设置保存 XML文件时的编码格式)。
例如1：
ttinclude
ttinclude
#include int main(int argc, char **argv) (xmlDocPtr doc = NULL;/* document
pointer */xmlNodePtr root_node = NULL, node = NULL, nodel
=NULL;/* node pointers */// Creates a new document, a node and set it as a root node
doc = xmlNewDoc(BADCAST 〃1.0〃)；root_node = xmlNewNode (NULL, BAD_CAST "root");
xmlDocSetRootElement(doc, root_node);
//creates a new node, which is "attached〃 as child node of root_node node.