北邮数据结构第三次实验-实验报告

数据结构实验报告三数据结构实验报告三引言：数据结构是计算机科学中的重要内容之一，它研究的是如何组织和存储数据以便高效地访问和操作。

本实验报告将介绍我在数据结构实验三中的实验过程和结果。

实验目的：本次实验的主要目的是熟悉并掌握树这种数据结构的基本概念和操作方法，包括二叉树、二叉搜索树和平衡二叉树等。

实验内容：1. 实现二叉树的创建和遍历在本次实验中，我首先实现了二叉树的创建和遍历。

通过递归的方式，我能够方便地创建一个二叉树，并且可以使用前序、中序和后序遍历方法对二叉树进行遍历。

这些遍历方法的实现过程相对简单，但能够帮助我们更好地理解树这种数据结构的特点。

2. 实现二叉搜索树的插入和查找接下来，我实现了二叉搜索树的插入和查找操作。

二叉搜索树是一种特殊的二叉树，它的左子树上的节点的值都小于根节点的值，右子树上的节点的值都大于根节点的值。

通过这种特性，我们可以很方便地进行插入和查找操作。

在实现过程中，我使用了递归的方法，通过比较节点的值来确定插入的位置或者进行查找操作。

3. 实现平衡二叉树的插入和查找平衡二叉树是为了解决二叉搜索树在某些情况下可能会退化成链表的问题而提出的。

它通过在插入节点的过程中对树进行旋转操作来保持树的平衡。

在本次实验中，我实现了平衡二叉树的插入和查找操作。

通过对树进行左旋、右旋等操作，我能够保持树的平衡，并且能够在O(log n)的时间复杂度内进行插入和查找操作。

实验结果：通过本次实验，我成功地实现了二叉树、二叉搜索树和平衡二叉树的相关操作。

我编写了测试代码，并对代码进行了测试，结果表明我的实现是正确的。

我能够正确地创建二叉树，并且能够使用前序、中序和后序遍历方法进行遍历。

对于二叉搜索树和平衡二叉树，我能够正确地进行插入和查找操作，并且能够保持树的平衡。

实验总结：通过本次实验，我深入了解了树这种数据结构的特点和操作方法。

二叉树、二叉搜索树和平衡二叉树是树的重要应用，它们在实际开发中有着广泛的应用。

学姐们倾情奉献~跪安吧少年少女们！北京邮电大学实验报告课程名称数据库系统原理实验内容实验（三）数据查询实验班级姓名指导老师成绩_________XXXX年XX月XX日实验三数据查询实验实验目的通过对实验二中建立的数据库关系表和视图的各种查询的操作，加深对SQL语言和Transact SQL查询语言的了解，掌握相关查询语句的语法和使用方法。

实验内容数据库关系表查询：（1）简单的查询操作，包括单表的查询、选择条件、结果排序等的练习；（2）多表的连接查询，包括等值连接、自然连接等；（3）复杂的查询操作，包括使用分组函数等库函数的查询操作；（4）练习带有IN、比较符的嵌套查询。

具体内容包括：1.简单查询:(1)查询班号为g00401班的学生的学号和姓名；(2)查询“数据库开发技术”课程的学分；(3)查询选修了课程编号为“dep04_s003”的学生的学号和成绩，并将成绩按降序输出；(4)查询学号为“g9940205”的学生选修的课程编号和成绩；(5)查询选修了课程编号为“dep04_s001”且成绩高于85分的学生的学号和成绩。

2.在多表连接的查询实验中，在SQL SERVER提供的交互式语言环境下用Transact SQL 语句完成以下查询操作：(1)查询选修了课程编号为“dep04_s002”且成绩高于85分的学生的学号、姓名和成绩；(2)查询所有学生的学号、姓名、选修的课程名称和成绩；(3)查询计算机科学系林红同学选修的课程名称、学分和成绩。

(考试成绩>＝60有学分，否则无学分。

)3.在复杂查询实验中，在SQL SERVER提供的交互式语言环境下用Transact SQL语句完成以下查询操作：(1)查询至少选修了三门课程的学生的学号和姓名；(2)查询选修课程号为“dep04_b001”的学生的平均成绩；(3)查询所有学生的学号和他选修课程的最高成绩，要求他的选修课程中没有成绩为空的。

(4)查询严为老师2001/2002学年教的软件开发技术课程的最高成绩及此学生的学号、姓名、班级。

实验三——图一、实验目的1.掌握图的基本概念；2.掌握图的存储结构及其建立算法；3.熟练掌握图的两种遍历算法及其应用。

二、实验内容1.对给定的图G，设计算法输出从V0出发深（广）度遍历图G的深（广）度优先搜索序列；2.设计算法输出给定图G的连通分量个数及边（或弧）的数目。

三、实验预习内容在实验中要用到这几个函数：typedef struct 邻接矩阵的创建，Locate函数去查找，create 函数创建图，定义两个指针firstadj,nextadj找寻临接点和下一个临接点，void dfs函数从某一点开始遍历，void dfsgraph进行图的遍历算法，然后就是main 函数。

四、上机实验1.实验源程序。

#include<>#define max 80int num1=0,num2=0;bool visited[max]; ."<<"\n\ number of bian"<<endl;cout<<"Please choose:";cin>>choice;switch(choice){case 1:creat(G);break;case 2:{dfsgraph(G);cout<<endl;};break;case 3:cout<<num1<<endl;break;case 4:cout<<num2/2<<endl;break;}cout<<"Continue(Y/N):";cin>>ctinue;if(ctinue=='Y'||ctinue=='y')flag=1;else flag=0;}}2.实验结果（截图）。

开始界面：创建函数界面：输出创建的函数：输出创建函数的连通分量：输出创建函数的边数：五、实验总结（实验过程中出现的问题、解决方法、结果或其它）在这两个实验中，对locate 函数的编写存在问题，不知道自己怎么去定位，函数该怎么样编写后来用这样编写就可以了。

数据结构实验三实验报告数据结构实验三实验报告一、实验目的本次实验的目的是通过实践掌握树的基本操作和应用。

具体来说，我们需要实现一个树的数据结构，并对其进行插入、删除、查找等操作，同时还需要实现树的遍历算法，包括先序、中序和后序遍历。

二、实验原理树是一种非线性的数据结构，由结点和边组成。

树的每个结点都可以有多个子结点，但是每个结点只有一个父结点，除了根结点外。

树的基本操作包括插入、删除和查找。

在本次实验中，我们采用二叉树作为实现树的数据结构。

二叉树是一种特殊的树，每个结点最多只有两个子结点。

根据二叉树的特点，我们可以使用递归的方式实现树的插入、删除和查找操作。

三、实验过程1. 实现树的数据结构首先，我们需要定义树的结点类，包括结点值、左子结点和右子结点。

然后，我们可以定义树的类，包括根结点和相应的操作方法，如插入、删除和查找。

2. 实现插入操作插入操作是将一个新的结点添加到树中的过程。

我们可以通过递归的方式实现插入操作。

具体来说，如果要插入的值小于当前结点的值，则将其插入到左子树中；如果要插入的值大于当前结点的值，则将其插入到右子树中。

如果当前结点为空，则将新的结点作为当前结点。

3. 实现删除操作删除操作是将指定的结点从树中移除的过程。

我们同样可以通过递归的方式实现删除操作。

具体来说，如果要删除的值小于当前结点的值，则在左子树中继续查找；如果要删除的值大于当前结点的值，则在右子树中继续查找。

如果要删除的值等于当前结点的值，则有三种情况：- 当前结点没有子结点：直接将当前结点置为空。

- 当前结点只有一个子结点：将当前结点的子结点替代当前结点。

- 当前结点有两个子结点：找到当前结点右子树中的最小值，将其替代当前结点，并在右子树中删除该最小值。

4. 实现查找操作查找操作是在树中寻找指定值的过程。

同样可以通过递归的方式实现查找操作。

具体来说，如果要查找的值小于当前结点的值，则在左子树中继续查找；如果要查找的值大于当前结点的值，则在右子树中继续查找。

北邮数据结构实验报告摘要：本报告基于北邮数据结构实验，通过实际操作和实验结果的分析，总结和讨论了各实验的目的、实验过程、实验结果以及相关的问题和解决方法。

本报告旨在帮助读者了解数据结构实验的基本原理和应用，并为今后的学习和研究提供参考。

1. 实验一：线性表的操作1.1 实验目的本实验旨在掌握线性表的基本操作以及对应的算法实现，包括插入、删除、查找、修改等。

1.2 实验过程我们使用C++语言编写了线性表的相关算法，并在实际编程环境下进行了测试。

通过插入元素、删除元素、查找元素和修改元素的操作，验证了算法的正确性和效率。

1.3 实验结果经过测试，我们发现线性表的插入和删除操作的时间复杂度为O(n)，查找操作的时间复杂度为O(n)，修改操作的时间复杂度为O(1)。

这些结果与预期相符，并反映了线性表的基本特性。

1.4 问题与解决方法在实验过程中，我们遇到了一些问题，例如插入操作的边界条件判断、删除操作时的内存释放等。

通过仔细分析问题，我们优化了算法的实现，并解决了这些问题。

2. 实验二：栈和队列的应用2.1 实验目的本实验旨在掌握栈和队列的基本原理、操作和应用，并进行实际编程实现。

2.2 实验过程我们使用C++语言编写了栈和队列的相关算法，并在实际编程环境下进行了测试。

通过栈的应用实现表达式求值和逆波兰表达式的计算，以及队列的应用实现图的广度优先遍历，验证了算法的正确性和效率。

2.3 实验结果经过测试，我们发现栈的应用可以实现表达式的求值和逆波兰表达式的计算，队列的应用可以实现图的广度优先遍历。

这些结果证明了栈和队列在实际应用中的重要性和有效性。

2.4 问题与解决方法在实验过程中，我们遇到了一些问题，例如中缀表达式转后缀表达式的算法设计、表达式求值的优化等。

通过查阅资料和与同学的讨论，我们解决了这些问题，并完善了算法的实现。

3. 实验三：串的模式匹配3.1 实验目的本实验旨在掌握串的基本操作和模式匹配算法，并进行实际编程实现。

数据结构实验报告1．实验要求(1)实验目的通过选择下面两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

(2)实验内容使用简单数组实现下面各种排序算法，并进行比较。

排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试排序算法的正确性。

2. 程序分析2.1 存储结构顺序表:示意图：2.2 关键算法分析（1）测试数据的产生：正序、逆序、随机数据用两个数组实现乱序、顺序以及逆序数据的排序。

基本思想为：随机序列产生一个指定长度的乱序序列，然后通过memcpy()函数拷贝到第二个数组里，第二个数组作为乱序序列的保存数组，每次对第一个数组进行排序，之后拷贝第二个数组中的乱序序列到第一个数组，实现各次乱序排列。

只要算法正确（第一步可以检验），之后顺序排列只需反复对第一个数组进行操作即可，再后用第二个数组保存逆序数组，然后同样在每次排序之后复制第二数组存储的乱序序列到第一组，对第一组反复排序即可。

<1> pRandom1=new long int[Max+1];pRandom2=new long int[Max+1];<2> srand((unsigned)time(NULL)); for(int i = 1; i <= Max;i++ ) pRandom2[i]=rand();<3> memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int));（2）排序算法：<1>插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。

北邮数据结构实验报告-排序北邮数据结构实验报告-排序一、实验目的本实验旨在掌握常见的排序算法，包括冒泡排序、插入排序、选择排序、快速排序、归并排序等，并通过实际编程实现对数字序列的排序。

二、实验内容1.冒泡排序冒泡排序是一种简单的排序算法，其基本思想是依次比较相邻的两个元素，并按照从小到大或从大到小的顺序交换。

具体步骤如下：- 从待排序序列的第一个元素开始，依次比较相邻的两个元素；- 如果前面的元素大于后面的元素，则交换这两个元素的位置；- 重复上述步骤，直到整个序列有序。

2.插入排序插入排序是一种简单且直观的排序算法，其基本思想是将待排序序列分为已排序和未排序两部分，每次从未排序部分中选择一个元素插入到已排序部分的合适位置。

具体步骤如下：- 从待排序序列中选择一个元素作为已排序部分的第一个元素；- 依次将未排序部分的元素插入到已排序部分的合适位置，使得已排序部分保持有序；- 重复上述步骤，直到整个序列有序。

3.选择排序选择排序是一种简单且直观的排序算法，其基本思想是每次选择未排序部分中的最小（或最大）元素，并将其放在已排序部分的末尾。

具体步骤如下：- 在未排序部分中选择最小（或最大）的元素；- 将选择的最小（或最大）元素与未排序部分的第一个元素交换位置；- 重复上述步骤，直到整个序列有序。

4.快速排序快速排序是一种高效的排序算法，其基本思想是通过一趟排序将待排序序列分割成两部分，其中一部分的元素都比另一部分的元素小。

具体步骤如下：- 选择一个枢轴元素（一般选择第一个元素）；- 将待排序序列中小于枢轴元素的元素放在枢轴元素的左侧，大于枢轴元素的元素放在枢轴元素的右侧；- 对枢轴元素左右两侧的子序列分别进行递归快速排序；- 重复上述步骤，直到整个序列有序。

5.归并排序归并排序是一种高效的排序算法，其基本思想是将待排序序列划分成足够小的子序列，然后对这些子序列进行两两合并，最终形成有序的序列。

具体步骤如下：- 将待排序序列递归地划分成足够小的子序列；- 对每个子序列进行归并排序；- 合并相邻的子序列，直到整个序列有序。

北邮数据结构实验报告北邮数据结构实验报告一、引言数据结构是计算机科学中的重要基础知识，对于计算机程序的设计和性能优化起着至关重要的作用。

本报告旨在总结北邮数据结构实验的相关内容，包括实验目的、实验设计、实验过程和实验结果等。

二、实验目的本次实验旨在通过实践操作，加深对数据结构的理解和应用能力。

具体目的如下：1. 掌握线性表、栈和队列等基本数据结构的实现方法；2. 熟悉二叉树、图等非线性数据结构的构建和遍历算法；3. 学会使用递归和非递归算法解决实际问题；4. 培养编程实践能力和团队合作意识。

三、实验设计本次实验包括以下几个部分：1. 线性表实验：设计一个线性表类，实现线性表的基本操作，如插入、删除和查找等。

通过实验，了解线性表的顺序存储和链式存储结构的特点和应用场景。

2. 栈和队列实验：设计栈和队列类，实现栈和队列的基本操作，如入栈、出栈、入队和出队等。

通过实验，掌握栈和队列的应用，如括号匹配、迷宫求解等。

3. 二叉树实验：设计二叉树类，实现二叉树的创建、遍历和查找等操作。

通过实验，熟悉二叉树的前序、中序和后序遍历算法，并了解二叉树的应用，如表达式求值等。

4. 图实验：设计图类，实现图的创建、遍历和最短路径等操作。

通过实验，掌握图的邻接矩阵和邻接表表示方法，并了解图的深度优先搜索和广度优先搜索算法。

四、实验过程1. 线性表实验：根据实验要求，首先选择线性表的存储结构，然后设计线性表类，实现插入、删除和查找等基本操作。

在实验过程中，遇到了一些问题，如边界条件的处理和内存管理等，通过团队合作，最终解决了这些问题。

2. 栈和队列实验：根据实验要求，设计栈和队列类，实现入栈、出栈、入队和出队等基本操作。

在实验过程中，我们发现了栈和队列在实际应用中的重要性，如括号匹配和迷宫求解等，通过实验加深了对栈和队列的理解。

3. 二叉树实验：根据实验要求，设计二叉树类，实现二叉树的创建、遍历和查找等操作。

在实验过程中，我们发现了二叉树在表达式求值和排序等方面的应用，通过实验加深了对二叉树的理解。

11．实验要求利用二叉树结构实现哈夫曼编/ 解码器(1). 初始化：能够对输入的任意长度的字符串s 进行统计，统计每个字符的频度，并建立哈夫曼树。

(2). 建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。

(3). 编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。

(4). 译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。

(5). 打印：以直观的方式打印哈夫曼树。

(6). 计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。

(7). 用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。

2.程序分析2.1存储结构二叉树：示意图：root2.21{2.3 关键算法分析1. 定义哈夫曼树的模板类#include <iostream>#include <string.h> using namespace std; structLNode {char ch;int weight;char code[20];LNode* next; };struct TNode{int weight; //int Lchild; //int Rchild; //int Parent; // };class Huffman 结点权值左孩子指针右孩子指针双亲指针// 链表的节点, 用来统计字符频率，并编码// 字符// 权值// 字符编码// 指向下一个节点// 哈弗曼树结点的结构体1 public:Huffman(); ~Huffman(); void CreateTable(); void PrintTable(); void Encoding(); void Decoding(); void Comrate();// 构造函数，输入、统计字符，创建哈弗曼树、码表// 释放链表空间、哈弗曼树的节点// 建立编码表，并将信息存入链表// 输出码表// 哈弗曼编码// 译码void SelectMin(int &x,int &y,int begin,int end);void reverse(char ch[]); voidcontrol();private: // 选取权值最小的两个数，创建哈弗曼树// 将码值倒置，用来编码// 对菜单交互等提示操作TNode* troot;LNode* lroot; void List(char a[]); void HTree(); int Letter; char astr[1000]; char bstr[1000]; // 在统计字符频率是构建链表的根节点// 统计字符的权值建立的单链表// 哈弗曼树建立// 共有不同字符总数// 用户输入的一串字符// 将字符串的码值保存Huffman::Huffman(){lroot=new LNode;bstr[0]='\0';lroot->next=NULL;Letter=0; // 初始化字符总数为1 cout<<" 请输入一串字符，以回车键结束"<<endl;cin.getline(astr,1000,'\n');if(strlen(astr)==0) throw 1;else{List(astr); // 用链表存储每个字符HTree();CreateTable();Encoding();}};Huffman::~Huffman(){delete troot;LNode* p=lroot;while(p=lroot->next)1{{ lroot=p->next; delete p; p=lroot;}delete p; };2. 建立哈夫曼树void Huffman::HTree(){LNode* p=lroot; int a=0;troot=new TNode[2*Letter-1]; //2n-1 while (p=p->next){troot[a].weight=p->weight; troot[a].Parent=-1; troot[a].Lchild=-1; troot[a].Rchild=-1; a++;};for (int i=Letter;i<2*Letter-1;i++)troot[i].Parent=-1; int x,y,begin=0;for (int j=Letter;j<2*Letter-1;j++) while (troot[begin].Parent!=-1)begin++;个结点// 建立叶子节点// 是两个最小值的角标SelectMin(x,y,begin,j);troot[j].weight=troot[x].weight+troot[y].weight;troot[j].Lchild=x;troot[j].Rchild=y;troot[j].Parent=-1;troot[x].Parent=j;troot[y].Parent=j;}};3.统计字符的频率void Huffman::List(char a[]){LNode *p=lroot;int i=0;while(a[i]!='\0'){{while (p&&p->ch!=a[i]) // 查找链表中没有该字符或者找到该字符p=p->next;if (!p) // 如果没有该字符，创建节点。

数据结构实验报告实验名称：实验三——树题目一学生姓名：申宇飞班级：2012211103班内序号：03学号：2012210064日期：2013年12月3日1．实验要求掌握二叉树基本操作的实现方法根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。

二叉树的基本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁9、其他：自定义操作编写测试main()函数测试线性表的正确性2. 程序分析2.1 存储结构采用二叉树的存储结构，其中每个二叉树的结点定义了一个结构体，该结构体包含三个元素，分别是一个T类型的数据域data，一个指向T类型的指针左孩子，一个指向T 类型的指针右孩子，示意图如图所示。

采用了队列的存储结构。

示意图如图所示：对于二叉树中每个结点的data 域的赋值，我们事先把这些data 储存在一个数组中，通过对数组元素的调用事先对二叉树中每个结点的data 域的赋值。

2.2 关键算法分析 一：二叉树的建立： A ． 自然语言描述：1首先判断调用的数组是否为空，如果为空，直接将一个已经初始化好的根节点置为空。

2 如果该数组不为空，则把调用的数组的第一个元素的赋给根节点的data 域。

3 采用递归的思想，分别将根节点的左右孩子作为根节点，递归调用该函数。

完成对左右子树的赋值。

B ． 代码详细分析：template <class T> void BiTree<T>::Create(Node<T> *&R,T* buf,int i) {if (buf[i-1]==0) R = NULL; else {R=new Node<T>; R->data = buf[i-1];Create(R->lch, buf, 2*i); Create(R->rch, buf, 2*i+1); }lchdata rchlchdata rchlchdata rchlchdata rchlchdata rchlchdata rchlch data rchA[2*i]A[2*i+1] lch data rch lch data rch二：前序遍历二叉树：A. 自然语言描述：1：建立栈2：判断该栈是否为空并且根节点是否为空指针3：如果根节点不是空指针，则输出它的data域，并且是它入栈4：入栈后将根节点指针指向它的左孩子5：如果根节点是空指针6：则根节点出栈，并且指向根节点的指针指向它的右孩子B.代码详细分析：template <class T> void BiTree<T>::Preorder(Node<T> *R){Stack<Node<T>*> S;while(!S.IsEmpty() || (R!=NULL)){if (R!=NULL){Print(R->data);S.Push(R);R=R->lch;}else{R=S.Pop();R=R->rch;}}}三：中序遍历二叉树：A.自然语言描述：1：建立栈2：判断该栈是否为空并且根节点是否为空指针3：如果根节点不是空指针，将它入栈4：入栈后将根节点指针指向它的左孩子5：如果根节点是空指针6：则根节点出栈，输出该节点的data域，并且指向根节点的指针指向它的右孩子B. 代码详细分析：template <class T> void BiTree<T>::Inorder(Node<T> *R){Stack<Node<T>*> S;while(!S.IsEmpty() || (R!=NULL)){if (R!=NULL){S.Push(R);R=R->lch;}else{R=S.Pop();Print(R->data);R=R->rch;}}}四：后序遍历二叉树：A.自然语言描述：1：判断根节点是否为空2：如果根节点不为空3：递归调用后续遍历函数，函数的参数改为根节点的左孩子 4：递归调用后续遍历函数，函数的参数改为根节点的右孩子 5：输出根节点的data域B.代码详细分析：template <class T> void BiTree<T>::Postorder(Node<T> *R) {if (R!=NULL) {Postorder(R->lch);Postorder(R->rch);Print(R->data);}}}}123五：层序遍历二叉树：A.自然语言描述：1：判断根节点是否为空2：如果根节点不为空3：输出根节点的data域4：递归调用层续遍历函数，函数的参数改为根节点的左孩子5：递归调用层序遍历函数，函数的参数改为跟结点的右孩子B.代码详细分析：template <class T> void BiTree<T>::Levelorder(Node<T> *R){Queue<Node<T>*> Q;while(!Q.IsEmpty() || (R!=NULL)){if (R!=NULL){Print(R->data);Q.EnQueue(R->lch);Q.EnQueue(R->rch);}R=Q.DelQueue();}}}123六：求二叉树的深度：A.自然语言描述：1：判断根节点是否为空，如果根节点为空，返回02：如果根节点不为空但是根节点的左右孩子同时为空，返回13：如果以上两个条件都不成立4：递归调用求二叉树的深度，函数的参数改为根节点的左孩子，并且深度初始化为1 5：递归调用求二叉树的深度，函数的参数改为跟结点的右孩子，并且深度初始化为0 6：返回4与5步中得出深度较大的那个数作为二叉树的深度数B.代码详细分析：template <class T> int BiTree<T>::GetDepth(Node<T> *R,int d){if (R==NULL) return d;if ((R->lch==NULL) && (R->rch==NULL))return d+1;else{int m = GetDepth(R->lch,d+1); int n = GetDepth(R->rch,d+1); return n>m? n:m; } }七：二叉树的销毁 A.自然语言描述：1：判断根节点是否为空 2：如果根节点不为空3：递归调用二叉树的销毁函数，参数改为根节点的左孩子 4：递归调用二叉树的销毁函数，参数改为根节点的右孩子 5：释放根节点指向的内存 B.代码详细分析：template <class T> void BiTree<T>::Destroy(Node<T> *R) {if (R!=NULL) { Destroy(R->lch); Destroy(R->rch); delete R; } }}：123八：求二叉树的叶子结点数： A.自然语言描述：1：判断根节点是否为空，如果为空，返回02：如果根节点不为空，切根节点的左右孩子同时为空，返回13：递归调用求二叉树的叶子节点数函数，参数改为根节点的左孩子 4：递归调用求二叉树的叶子结点数函数，参数改为根节点的右孩子 5：返回根节点的左右子树的叶子结点数之和 B.代码详细分析：template <class T> int BiTree<T>::LeafNodeCount(Node<T> *R) {if (R==NULL) return 0;if ((R->lch==NULL) && (R->rch==NULL)) return 1; else {int n=LeafNodeCount(R->lch); int m=LeafNodeCount(R->rch); return m+n; } }九：求二叉树的结点数： A.自然语言描述：} }123}1231：判断根节点是否为空，如果为空，返回02：如果根节点不为空3：递归调用求二叉树的结点数的函数，参数改为根节点的左孩子4：递归调用求二叉树的结点数的函数，参数改为根节点的右孩子5：返回根节点的左右字数的结点数之和B.代码详细分析：template <class T> int BiTree<T>::NodeCount(Node<T> *R){if (R==NULL) return 0;else{int m=NodeCount(R->lch);}}int n=NodeCount(R->rch); return m+n+1;}1232.3 其他对二叉树的操作上，前序遍历与中序遍历采用了非递归算法，后续遍历，层序遍历，求二叉树深度，求二叉树叶子结点数，求二叉树结点数等函数采用了递归算法。

北邮数据结构实验报告图一、实验报告规范实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容：1.需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么?明确规定：(1)输入的形式和输入值的范围;(2)输出的形式;(3)程序所能达到的功能;(4)测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

2.概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。

3.详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法;对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序);画出函数的调用关系图。

4.调试分析内容包括：(1)调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析;(2)算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想;(3)经验和体会等。

5.用户使用说明说明如何使用你编写的程序，详细列出每一步的操作步骤。

6.测试结果列出你的测试结果，包括输入和输出。

这里的测试数据应该完整和严格，最好多于需求分析中所列。

7.附录带注释的源程序。

如果提交源程序软盘，可以只列出程序文件名的清单。

值得注意的是，实习报告的各种文档资料，如：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写(当然也可以应该最后用实验报告纸誊清或打印)。

数据结构实验报告;实验名称：实验一线性表实现一个多项式;学生姓名：黄锦雨;班级：XX211109;班内序号：20;学号：XX210263;日期：XX年10月31日;实验目的：;1.熟悉C++语言的基本编程方法，掌握集成编译环;2.学习指针、模板类、异常处理的使用;3.掌握线性表的操作的实现方法;4.学习使用线性表解决实际问题的能力;实验内容：;数据结构实验报告实验名称：实验一线性表实现一个多项式学生姓名：黄锦雨班级：XX211109班内序号： 20学号： XX210263日期： XX年10月31日实验目的：1.熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法2.学习指针、模板类、异常处理的使用3.掌握线性表的操作的实现方法4.学习使用线性表解决实际问题的能力实验内容：利用线性表实现一个一元多项式Polynomialf(x) = a0 + a1x + a2x2 + a3x3 + … + anxn要求：1. 能够实现一元多项式的输入和输出2. 能够进行一元多项式相加3. 能够进行一元多项式相减4. 能够计算一元多项式在x处的值5. 能够计算一元多项式的导数(选作)6. 能够进行一元多项式相乘(选作)7. 编写测试main()函数测试线性表的正确性2. 程序分析由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。

北邮数据结构实验报告北京邮电大学信息与通信工程学院20XX级数据结构实验报告实验名称：实验三哈夫曼编/解码器的实现学生姓名：陈聪捷日期：20XX年11月28日1. 实验要求一、实验目的：了解哈夫曼树的思想和相关概念；二、实验内容：利用二叉树结构实现哈夫曼编 /解码器1. 初始化：能够对输入的任意长度的字符串s进行统计, 统计每个字符的频度，并建立哈夫曼树。

2. 建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。

3. 编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。

4. 译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。

5. 打印：以直观的方式打印哈夫曼树。

6. 计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。

7. 用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。

2. 程序分析存储结构二叉树templateclass BiTree(public:BiTree ; // 构造函数，其前序序列由键盘输入~BiTree(void); // 析构函数BiNode* Getroot ; // 获得指向根结点的指针protected:BiNode *root; // 指向根结点的头指针｝；//声明类BiTree 及定义结构BiNodeData :二叉树是由一个根结点和两棵互不相交的左右子树构成哈夫曼树类的数据域，继承节点类型为int的二叉树class HuffmanTree:public BiTreedata:HCode* HCodeTable;// 编码表int tSize; // 编码表中的总字符数二叉树的节点结构templatestruct BiNode // 二叉树的结点结构{T data; // 记录数据T lchild; // 左孩子T rchild; // 右孩子T parent; // 双亲};编码表的节点结构struct HCode{char data; // 编码表中的字符char code; // 该字符对应的编码};待编码字符串由键盘输入，输入时用链表存储，链表节点为struct Node{char character; // 输入的字符unsigned int count;// 该字符的权值bool used; // 建立树的时候该字符是否使用过Node* next; // 保存下一个节点的地址｝；示意图：关键算法分析1. 初始化函数(void HuffmanTree::Init(string Input))算法伪代码：1. 初始化链表的头结点2. 获得输入字符串的第一个字符，并将其插入到链表尾部,n=1(n记录的是链表中字符的个数)3. 从字符串第2个字符开始，逐个取出字符串中的字符将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出的字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。

数据结构实验报告三数据结构实验报告三引言：数据结构作为计算机科学的重要基础，对于计算机程序的设计和性能优化起着至关重要的作用。

在本次实验中，我们将深入研究和实践数据结构的应用，通过实验来验证和巩固我们在课堂上所学到的知识。

一、实验目的本次实验的主要目的是通过实践操作，进一步掌握和理解数据结构的基本概念和操作。

具体来说，我们将学习并实现以下几个数据结构：栈、队列、链表和二叉树。

通过对这些数据结构的实现和应用，我们将更好地理解它们的特点和优势，并能够灵活运用于实际问题的解决中。

二、实验内容1. 栈的实现与应用栈是一种后进先出（LIFO）的数据结构，我们将学习如何使用数组和链表两种方式来实现栈，并通过实例来演示栈的应用场景，如括号匹配、表达式求值等。

2. 队列的实现与应用队列是一种先进先出（FIFO）的数据结构，我们将学习如何使用数组和链表两种方式来实现队列，并通过实例来演示队列的应用场景，如任务调度、消息传递等。

3. 链表的实现与应用链表是一种动态数据结构，相比数组具有更好的灵活性和扩展性。

我们将学习如何使用指针来实现链表，并通过实例来演示链表的应用场景，如链表的插入、删除、反转等操作。

4. 二叉树的实现与应用二叉树是一种常见的树形结构，我们将学习如何使用指针来实现二叉树，并通过实例来演示二叉树的应用场景，如二叉树的遍历、搜索等操作。

三、实验过程1. 栈的实现与应用我们首先使用数组来实现栈，并编写相关的入栈、出栈、判空、获取栈顶元素等操作。

然后，我们通过括号匹配和表达式求值两个实例来验证栈的正确性和应用性。

2. 队列的实现与应用我们使用数组来实现队列，并编写相关的入队、出队、判空、获取队头元素等操作。

然后，我们通过任务调度和消息传递两个实例来验证队列的正确性和应用性。

3. 链表的实现与应用我们使用指针来实现链表，并编写相关的插入、删除、反转等操作。

然后，我们通过链表的插入和删除操作来验证链表的正确性和应用性。

数据结构实验报告实验名称：实验三树——哈夫曼编/解码器学生：班级：班序号：学号：日期：2014年12月11日1．实验要求利用二叉树结构实现赫夫曼编/解码器。

基本要求：1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。

3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。

4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。

5、打印(Print)：以直观的方式打印赫夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。

测试数据：I love data Structure, I love Computer。

I will try my best to study data Structure.提示：1、用户界面可以设计为“菜单”方式：能够进行交互。

2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。

2. 程序分析2.1 存储结构Huffman树给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径长度最小的二叉树称为Huffman树，也叫做最优二叉树。

weight lchild rchild parent 2-1-1-15-1-1-16-1-1-17-1-1-19-1-1-1weight lchild rchild parent2-1-155-1-156-1-167-1-169-1-17701713238165482967-12.2 关键算法分析（1）计算出现字符的权值利用ASCII码统计出现字符的次数，再将未出现的字符进行筛选，将出现的字符及頻数存储在数组a[]中。

void Huffman::Init(){int nNum[256]= {0}; //记录每一个字符出现的次数int ch = cin.get();int i=0;while((ch!='\r') && (ch!='\n')){nNum[ch]++; //统计字符出现的次数str[i++] = ch; //记录原始字符串ch = cin.get(); //读取下一个字符}str[i]='\0';n = 0;for ( i=0;i<256;i++){if (nNum[i]>0) //若nNum[i]==0，字符未出现{l[n] = (char)i;a[n] = nNum[i];n++;}}}时间复杂度为O（1）；（2）创建哈夫曼树：算法过程：Huffman树采用顺序存储---数组；数组的前n个结点存储叶子结点，然后是分支结点，最后是根结点；首先初始化叶子结点元素—循环实现；以循环结构，实现分支结点的合成，合成规则按照huffman树构成规则进行。

北邮数据结构实验报告实验三哈夫曼数据结构实验报告实验名称：实验三——哈夫曼编/解码器的实现学⽣姓名：侯在鹏班级： 2012211120班内序号： 13学号：2012210583⽇期：2013年12⽉10⽇1．实验要求利⽤⼆叉树结构实现赫夫曼编/解码器。

基本要求：1、初始化(Init)：能够对输⼊的任意长度的字符串s进⾏统计，统计每个字符的频度，并建⽴赫夫曼树2、建⽴编码表(CreateTable)：利⽤已经建好的赫夫曼树进⾏编码，并将每个字符的编码输出。

3、编码(Encoding)：根据编码表对输⼊的字符串进⾏编码，并将编码后的字符串输出。

4、译码(Decoding)：利⽤已经建好的赫夫曼树对编码后的字符串进⾏译码，并输出译码结果。

5、打印(Print)：以直观的⽅式打印赫夫曼树（选作）6、计算输⼊的字符串编码前和编码后的长度，并进⾏分析，讨论赫夫曼编码的压缩效果。

测试数据：I love data Structure, I love Computer。

I will try my best to study data Structure.提⽰：1、⽤户界⾯可以设计为“菜单”⽅式：能够进⾏交互。

2、根据输⼊的字符串中每个字符出现的次数统计频度，对没有出现的字符⼀律不⽤编码。

2. 程序分析2.1 存储结构程序实现了基本的编解码功能输⼊字符串选择⼯作⽬标编码解码相关树，表显⽰编码上根节点向下，左0右1根据不同字符在尾端相应排位,获得⾃⼰的编码，存储。

解码上依次读取数据0或1，循序寻找，最后在存储中找到对应编码的字符，输出再重新读取下⼀数字开始的数码在哈夫曼树编码这个程序中，所有数据⽤的存储结构都是顺序存储结构，其中包括顺序表和树（三叉树）树的存储结构如下：（输⼊的字符串为assddddffffffffgggggggggggggggg）上结构图中，填充为黄⾊的部分为写⼊内存中的部分。

每⼀⾏的部分为数组的下标，左边部分为所定义的结构的成员。