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

上连第Z三堂大竽徽据牯构与算法实脸播导行计算机与信息学院实验三树【实验目的】【实验平台】操作系统:开发环境:熟练掌握在链式二叉树在二叉链表存储结构上的基本操作。Windows2000 或 Windows XPC 或 C+【实验内容及要求】要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所 有叶子及结点总数的操作等。具体实现要求：17 .基于先序遍历的构造算法：输入是二叉树的先序序列，但必须在其中加入虚结点以示空指针 的位置。假设虚结点输入时用空格字符表示。18 .用广义表表示所建二叉树。19 .分别利用前序遍历、中序遍历、后序遍历所建二叉树。20 .求二叉树结点总数，观察输出结果。21 .求二叉树叶子总数，观察输出结果。22 .交换各结点的左右子树，用广义表表示法显示新的二叉树。23 . （）二叉树采用链接存储结构，其根结点指针为T,设计一个算法对这棵二叉树的每个结 点赋值：（注意要修改DataType类型）a）叶结点的值为3b）只有左孩子或右孩子的结点那么其值分别等于左孩子或右孩子的值c）左、右孩子均有的结点，那么其值等于左、右孩子结点的值之和d）用广义表表示法显示所建二叉树【参考框架】#include #include 二叉树的链式存储表示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 CreateBinTree(BinTree *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(nnn);Display B inTree(T);printf(前序遍历:nn);Preorder(T);printf(nnn);printf(中序遍历：nH);Inorder(T);printf(nnn);printf(后序遍历:nn);Postorder(T);printf(Hnn);printf(二叉树的总结点数为 dn”,nodes(T);printf(二叉树的总叶子结点数为dnleafs(T); T=swap(T);ListBinTree(T); printf(nnn);构造二叉链表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 HuffmanTreem; /HuffmanTree 是向量类型/Huffman树的存储结构#define n 100#define m 2*n-l typedef struct float weight;int lchild,rchild,parent;HTNode;叶子数目树中结点总数结点类型权值，不妨设权值均大于零左右孩子及双亲指针typedef struct char ch;存储字符char bitsn+l;/存放编码位串CodeNode;typedef CodeNode HuffmanCoden;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);输入叶子权值至T0.n-l的weight域for(i=n;im;i+) 共进行n-1次合并，新结点依次存于Ti中 SelectMin(T,i-l ,&p 1 ,&p2);在中选择两个权最小的根结点，其序号分别为pl和p2Tpl .parent=Tp2 .parent=i;Ti.lchild=pl;/最小权的根结点是新结点的左孩子Ti.rchild=p2;/次小权的根结点是新结点的右孩子Ti.weight=Tp I.weight+Tp2. weight;)void InitHuffmanTree(HuffmanTree T)初始化Huffman树int i;for (i=0;im;i+)(Ti.weight=O;Ti.lchild=Ti.rchild=Ti .parent=NULL;)void InputWeight(HuffmanTree T)输入权值int i;for (i=0;in;i+)printf(”请输入第d个权值：”,i+1);scanf(n%f;&Ti.weight);)void SelectMin(HuffmanTree T,int i,int *pl,int *p2) 在T中选择两个权最小的根结点intj;float minl,min2;mini =min2=-l;for(j=0;j=i;j+)if(Tj .parent=NULL)(if(Tj.weightmin l|min 1 =-l)(if(minl!-1)min2=minl;*p2=*pl;)min l=Tj. weight;*pl二j;)elseif(Tj. weightmin2| |min2=-1) (min2=Tj. weight;*p2寸)void CharSetHuffmanEncoding(HuffmanTree T,HuffmanCode H)/根据Huffman树T求Huffman编码表Hint c,p,i;/c和p分别指示T中孩子和双亲的位置char cdn+l;/临时存放编码int start;指示编码在cd中的起始位置cdn=,0,;编码结束符printf(”请输入字符：)for(i=0;in;i+)依次求叶子Ti的编码(Hi.ch=getchar();读入叶子Ti对应的字符start=n;编码起始位置的初值c=i;/从叶子Ti开始上溯while(p=Tc.parent)!=NULL)直至上溯到 Tc是树根为止 假设Tc是Tp的左孩子，那么生成代码0；否那么生成代码1cd-start=(Tp.lchild=c)?!O,:,r； c=p;继续上溯)strcpy(Hi.bits,&cdstart);/复制编码位串) for(i=0;in;i+)printf(nM%d 个字符c 的编码为sn”,i+l,Hi.ch,Hi.bits);【实验报告】数据结构与算法实验报告学院:学号:日期:班级：姓名：程序名：L62CPP一、上机实验的问题和要求:阅读理解建立Huffman树的算法，对该算法进行运行及调试。具体实现要求:1 .调试并运行Huffman算法。2 .()求Huffman树的带权路径长度WPL。二、源程序及注释:三、运行输出结果:四、调试和运行程序过程中产生的问题及采取的措施:实验五查找（二叉排序树）【实验目的】【实验平台】操作系统:开发环境:熟练掌握二叉排序树上的查找算法。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); 在 二叉 排序树 中删除 关键字 keyBSTNode *SearchBST(BSTree T,KeyType key); 在二叉 排序树中查找 关键字 keyBSTree T;BSTNode *p;int key;printf(”请输入关键字(输入。为结束标志)：nn);T=CreateBST();ListBinTree(T);printf(nnn);printf(”请输入欲插入关键字：”)； scanf(H%dn,&key);InsertB ST(&T,key);ListBinTree(T);printf(nnn);printf(”请输入欲删除关键字：”)； scanf(H%dn,&key);DelBSTNode(&T,key);ListBinTree(T);printf(nnn);printf(”请输入欲查找关键字：”)；scanf(H%dn,&key);p=SearchBST(T,key);if(p=NULL)printf(没有找到%d! nkey);elseprintf(找到(1! nn,key);ListBinTree(p);printf(Hnn);将关键字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/表空间大小可根据实际需要而定，这里假设为100typedef int DataType; /DataType可以是任何相应的数据类型如int, float或chartypedef struct DataType dataListSize; 向量 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. gz3）进入解压缩后的文件夹中运行./configure prefix /home/usei7myxml/xmlinst（此处为待安装的路径）或者直接使用./configuremakemake install4）添加路径export PATH=/home/user/myxml/xmlinst/bin:$PATH说明：为了结构清晰，最好将libxml2不安装在解压目录中。安装完成后就可以使用简单的代码解析XML文件，包括本地和远程的文 件，但是在编码上有一些问题。Libxml默认只支持UTF8的编码，无论 输入输出都是UTF-8,所以如果你解析完一个XML得到的结果都是UTF-8 的，如果需要输出GB2312或者其它编码，需要ICONV来做转码（生成UTF -8编码的文件也可以用它做），如果系统中没有安装iconv的话，需要安 装 libiconvo1）下载 libiconv 压缩包（例如 libiconv-1. 11. tar. gz）2）对压缩包进行解压缩 tar xvzf libiconv-1. 11. tar. gz3）进入解压缩后的文件夹中运行./configuremakemake install三、关于XML：在开始研究Libxml2库之前，先了解一下XML的相关基础。XML是一 种基于文本的格式，它可用来创立能够通过各种语言和平台访问的结构化 数据。它包括一系列类似HTML的标记，并以树型结构来对这些标记进行 排列。例如，可参见清单1中介绍的简单文档。为了更清楚地显示XML的一 般概念，下面是一个简化的XML文件。清单1. 一个简单的XML文件?xml version=1. 0 encoding=UTF-8”?rootdeleteage units二days10/age清单1中的第一行是XML声明，它告诉负责处理XML的应用程序， 即解析器，将要处理的XML的版本。大局部的文件使用版本1.0编写, 但也有少量的版本1.1的文件。它还定义了所使用的编码。大局部文件 使用UTF-8,但是，XML设计用来集成各种语言中的数据，包括那些不使 用英语字母的语言。接下来出现的是元素。一个元素以开始标记 开始（如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 nodeNr; i+ + )nodeset-nodeTabi;注意，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;/* documentpointer */xmlNodePtr root_node = NULL, node = NULL, nodel=NULL;/* node pointers */ Creates a new document, a node and set it as a root nodedoc = 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.