北京邮电大学数据结构第二次实验车厢重排实验报告

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

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

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 实验目的本实验旨在掌握串的基本操作和模式匹配算法，并进行实际编程实现。

实验2用堆栈解决火车车厢重排问题的编程一、目的通过对本次实验，我们应：1、加深对线性表、堆栈的认识；2、加深接口、类、索引器的认识；3、掌握堆栈数据结构，并应用堆栈编程解决实际问题。

二、实验准备1、软件准备：C#.net。

2、参考数据（示例）：文件夹“…\实验2\示例”中的数据。

三、实验背景描述1、问题描述一列货运列车共有n节车厢，每节车厢将停放在不同的车站。

假定n个车站的编号分别为1 -n，货运列车按照第n站至第1站的次序经过这些车站。

车厢的编号与它们的目的地相同。

为了便于从列车上卸掉相应的车厢，必须重新排列车厢，使各车厢从前至后按编号1到n的次序排列。

当所有的车厢都按照这种次序排列时，在每个车站只需卸掉最后一节车厢即可。

我们在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲铁轨（位于入轨和出轨之间）。

图3.1a 给出了一个转轨站，其中有k= 3个缓冲铁轨H1，H2和H3。

开始时，n节车厢的货车从入轨处进入转轨站，转轨结束时各车厢从右到左按照编号1至编号n的次序离开转轨站（通过出轨处）。

在图3.1a 中，n= 9，车厢从后至前的初始次序为5，8，1，7，4，2，9，6，3。

图3.1b 给出了按所要求的次序重新排列后的结果。

图2.1根据上面的描述，编写程序实现下面的功能：编写一算法实现火车车箱的重排；编写程序模拟图2.1所示的具有9节车厢的火车入轨和出轨的过程。

程序主界面设计如图2.2所示。

图2.22、问题分析为了重排车厢，需从前至后依次检查入轨上的所有车厢。

如果正在检查的车厢就是下一个满足排列要求的车厢，可以直接把它放到出轨上去。

如果不是，则把它移动到缓冲铁轨上，直到按输出次序要求轮到它时才将它放到出轨上。

缓冲铁轨上车厢的进和出只能在缓冲铁轨的尾部进行。

当缓冲铁轨上的车厢编号不是按照从顶到底的递增次序排列时，重排任务将无法完成。

新的车厢u应送入这样的缓冲铁轨：其底部的车厢编号v满足v>u,且v是所有满足这种条件的缓冲铁轨顶部车厢编号中最小的一个编号。

高级计算机系统结构实验报告实验二指令流水线相关性分析实验三DLX处理器程序设计实验四代码优化实验五循环展开专业计算机科学与技术班级2015姓名学号2015实验二指令流水线相关性分析1. 实验目的：通过使用WINDLX模拟器，对程序中的三种相关现象进行观察，并对使用专用通路，增加运算部件等技术对性能的影响进行考察，加深对流水线和RISC处理器的特点的理解。

2. 实验设备环境：2.1 WinDLX模拟器可以装入DLX汇编语言程序，然后单步、设置断点或者连续执行该程序；2.2 CPU的寄存器、流水线、I/O和存储器都可以使用图形的方式表示出来；2.3 模拟器还提供了对流水线操作的统计功能；2.4 该模拟器对理解流水线和RISC处理器的特点很有帮助；2.5 所有浮点运算部件的延时都设定为4个周期；3. 实验原理：指令流水线中主要有结构相关、数据相关、控制相关。

相关影响流水线性能。

3.1数据相关定义：原有先后顺序的两条指令（I1，I2)在对共享变量（位置）进行读、写时，指令流水线中实际完成的读、写顺序与原有顺序不一致，导致流水线输出错误。

三类数据相关：写读(WR)相关读写(RW)相关写写(WW)相关解决方法技术：1.使某些流水线指令延迟、停顿一或多个周期。

2.双端口存储器:如果指令和数据放在同一个存储器。

3.设置两个存储器：一个数据存储，一个为指令存储器。

4.软件优化编译：通过指令重新排序，消除数据相关。

5.定向技术：又称旁路技术或专用通路技术，是使后续指令提前得到前指令的运算结果(适合ALU类指令）3.2结构相关定义：如果某指令在流水线重叠执行过程中，硬件资源满足不了指令重叠执行的要求，会产生资源冲突或竞争，称为流水线结构相关解决方法技术：1.延迟技术：使某些指令延迟、停顿一或多个时钟周期2.双端口存储器：允许同时读两个数据或指令3.设置双存储器（哈弗结构）：一个数据存储，一个指令存储。

4软件优化编译：通过指令重新排序消除结构相关。

数据结构实验报告实验名称：__ 哈夫曼树________学生姓名：______ 蔡宇豪_________________班级：________ 2 5____________________ 班内序号：__________15__________________学号：_________2012210673___________________ 日期：________2013.11.24____________________2. 程序分析2.1 存储结构哈夫曼树结点的存储结构包括双亲域parent，左子树lchild，右子树rchild，还有字符word，权重weight，编码code对用户输入的信息进行统计，将每个字符作为哈夫曼树的叶子结点。

统计每个字符出现的次数作为叶子的权重，统计次数可以根据每个字符不同的ASCII码，根据叶子结点的权重建立一个哈夫曼树2.2 关键算法分析要实现哈夫曼解/编码器，就必须用二叉树结构建立起哈夫曼树，其中有4个关键算法，首先是初始化函数，统计每个字符的频度，并建立起哈夫曼树；然后是建立编码表，将每个字符的编码输出；再次就是编码算法，根据编码表对输入的字符串进行编码，并将编码后的字符串输出；最后是译码算法，利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。

1.初始化函数int i,j;for(i=0;i<MAX;i++)a[i]=0; //先将a[]数组中每个值都赋为，不然程序会运行出错？for(i=0;s[i]!='\0';i++) //'\0'字符串结束标志{for(j=0;j<n;j++){if(s[i]==b[j]) //判断该字符是否已经出现过break;}if(j<n) //该字符出现过，对应计数器加一a[j]++;else//该字符为新字符,上面的循环全部运行完毕，j=n，记录到b[j]中，对应计数器加一{b[j]=s[i];a[j]++;n++; //出现的字符种类数加一}}//cout<<"共有"<<n<<"种字符，分别为:"<<endl;for(i=0;i<n;i++)cout<<b[i]<<"出现次数为:"<<a[i]<<endl;HTree=new HNode[2*n-1] ; //哈夫曼树初始化for(int i=0;i<2*n-1;i++){if(i<n){HTree[i].weight=a[i];}else{HTree[i].weight=0;}HTree[i].LChild=-1;HTree[i].RChild=-1;HTree[i].parent=-1;}int x,y,m1,m2; //x,y用于存放权值最小结点在数组中的下标for(int i=n;i<2*n-1;i++) //开始建哈夫曼树{//找出权值最小的结点m1=m2=MAX; //MAX=1000x=y=0;for(int j=0;j<i;j++){if(HTree[j].weight<m1&&HTree[j].parent==-1){m2=m1;m1=HTree[j].weight;x=j;}else if(HTree[j].weight < m2 && HTree[j].parent==-1){m2=HTree[j].weight;y=j;}}HTree[x].parent=HTree[y].parent=i;HTree[i].weight=HTree[x].weight+HTree[y].weight;HTree[i].LChild=x;HTree[i].RChild=y;HTree[i].parent=-1;2.生成编码表HCodeTable=new HCode[n];for(int i=0;i<n;i++){HCodeTable[i].data=b[i];int child=i;int parent=HTree[i].parent;int k=0;while(parent!=-1){if(child==HTree[parent].LChild)HCodeTable[i].code[k]='0';elseHCodeTable[i].code[k]='1';k++;child=parent;parent=HTree[child].parent;}HCodeTable[i].code[k]='\0';cout<<b[i]<<"的编码:";for(int j=k-1;j>=0;j--)cout<<HCodeTable[i].code[j];cout<<endl;}3.编码cout<<"编码后的字符串为:";while(*d!='\0'){for(int i=0;i<n;i++){if(b[i]==*d) //判断，每当出现一种时，就找到对应编码并输出{int k=strlen(HCodeTable[i].code);for(int j=k-1;j>=0;j--){*s=HCodeTable[i].code[j];cout<<*s;s++;}}}d++;}*s='\0';cout<<endl;【计算关键算法的时间、空间复杂度】关键算法A的时间复杂度为O(n)，关键算法B的时间复杂度为O(n),关键算法C的时间复杂度为O(n)，关键算法D的时间复杂度为O(n).2.3 其他程序完整代码：#include<iostream>using namespace std;const int MAX=1000;struct HNode{int weight;int parent;int LChild;int RChild;};struct HCode{char data;char code[200];};class Huffman{private:HNode *HTree; //哈夫曼树HCode *HCodeTable; //哈夫曼编码表char b[MAX]; //记录出现的字符int a[MAX]; //记录每个字符出现的次数，即权值static int n; //字符的种类数(静态变量)public:void init(char s[]); //初始化void init1(char s[]);void CreateCodeTable(); //创建编码表void Encoding(char *s,char *d); //编码void Decoding(char *s,char *d); //解码int count1() //算编码前长度{int q1=0;for(int i=0;i<n;i++){q1+=8*a[i];}return q1;}int count2() //算编码后长度{int q2=0;for(int i=0;i<n;i++){q2+=strlen(HCodeTable[i].code)*a[i];}return q2;}};int Huffman::n=0;void Huffman::init(char s[]){int i,j;for(i=0;i<MAX;i++)a[i]=0; //先将a[]数组中每个值都赋为，不然程序会运行出错？for(i=0;s[i]!='\0';i++) //'\0'字符串结束标志{for(j=0;j<n;j++){if(s[i]==b[j]) //判断该字符是否已经出现过break;}if(j<n) //该字符出现过，对应计数器加一a[j]++;else//该字符为新字符,上面的循环全部运行完毕，j=n，记录到b[j]中，对应计数器加一{b[j]=s[i];a[j]++;n++; //出现的字符种类数加一}}//cout<<"共有"<<n<<"种字符，分别为:"<<endl;for(i=0;i<n;i++)cout<<b[i]<<"出现次数为:"<<a[i]<<endl;HTree=new HNode[2*n-1] ; //哈夫曼树初始化for(int q=0;q<2*n-1;q++){if(q<n){HTree[q].weight=a[q];}else{HTree[q].weight=0;}HTree[q].LChild=-1;HTree[q].RChild=-1;HTree[q].parent=-1;}int x,y,m1,m2; //x,y用于存放权值最小结点在数组中的下标for(int w=n;w<2*n-1;w++) //开始建哈夫曼树{//找出权值最小的结点m1=m2=MAX; //MAX=1000x=y=0;for(int j=0;j<i;j++){if(HTree[j].weight<m1&&HTree[j].parent==-1){m2=m1;m1=HTree[j].weight;x=j;}else if(HTree[j].weight < m2 && HTree[j].parent==-1){m2=HTree[j].weight;y=j;}}HTree[x].parent=HTree[y].parent=w;HTree[w].weight=HTree[x].weight+HTree[y].weight;HTree[w].LChild=x;HTree[w].RChild=y;HTree[w].parent=-1;}}void Huffman::init1(char s[]){int i,j;for(i=0;i<MAX;i++)a[i]=0; //先将a[]数组中每个值都赋为，不然程序会运行出错？for(i=0;s[i]!='\0';i++) //'\0'字符串结束标志{for(j=0;j<n;j++){if(s[i]==b[j]) //判断该字符是否已经出现过break;}if(j<n) //该字符出现过，对应计数器加一a[j]++;else//该字符为新字符,上面的循环全部运行完毕，j=n，记录到b[j]中，对应计数器加一{b[j]=s[i];a[j]++;n++; //出现的字符种类数加一}}HTree=new HNode[2*n-1] ; //哈夫曼树初始化for(int e=0;e<2*n-1;e++){if(e<n){HTree[e].weight=a[e];}else{HTree[e].weight=0;}HTree[e].LChild=-1;HTree[e].RChild=-1;HTree[e].parent=-1;}int x,y,m1,m2; //x,y用于存放权值最小结点在数组中的下标，m1,m2用于存放两个无父结点且结点权值最小的两个结点for(int r=n;r<2*n-1;r++) //开始建哈夫曼树{//找出权值最小的结点m1=m2=MAX; //MAX=1000x=y=0;for(int j=0;j<r;j++){if(HTree[j].weight<m1&&HTree[j].parent==-1){m2=m1;//y=x;m1=HTree[j].weight;x=j;}else if(HTree[j].weight < m2 && HTree[j].parent==-1){m2=HTree[j].weight;y=j;}}HTree[x].parent=HTree[y].parent=r;HTree[r].weight=HTree[x].weight+HTree[y].weight;HTree[r].LChild=x;HTree[r].RChild=y;HTree[r].parent=-1;}}void Huffman::CreateCodeTable() //生成编码表{HCodeTable=new HCode[n];for(int i=0;i<n;i++){HCodeTable[i].data=b[i];int child=i;int parent=HTree[i].parent;int k=0;while(parent!=-1){if(child==HTree[parent].LChild)HCodeTable[i].code[k]='0';elseHCodeTable[i].code[k]='1';k++;child=parent;parent=HTree[child].parent;}HCodeTable[i].code[k]='\0';cout<<b[i]<<"的编码:";for(int j=k-1;j>=0;j--)cout<<HCodeTable[i].code[j];cout<<endl;}}void Huffman::Encoding(char *s,char *d) // 编码算法 //d为字符串{cout<<"编码后的字符串为:";while(*d!='\0'){for(int i=0;i<n;i++){if(b[i]==*d) //判断，每当出现一种时，就找到对应编码并输出{int k=strlen(HCodeTable[i].code);for(int j=k-1;j>=0;j--){*s=HCodeTable[i].code[j];cout<<*s;s++;}}}d++;}*s='\0';cout<<endl;}void Huffman::Decoding(char *s,char *d) //s为编码串{cout<<"解码后的字符串为:";while(*s!='\0'){int parent=2*n-1-1;while(HTree[parent].LChild!=-1){if(*s=='0')parent=HTree[parent].LChild;elseparent=HTree[parent].RChild;s++;}*d=HCodeTable[parent].data;cout<<*d;d++;}cout<<endl;void main(){int i=0;char d[MAX];char s[MAX];cout<<"请输入字符串:";while((d[i]=getchar())!='\n')i++;d[i]='\0';Huffman h;cout<<"哈夫曼功能："<<endl;cout<<"1.统计字符种类及出现次数"<<endl;cout<<"2.数据的编码解码"<<endl;cout<<"3.分析压缩效果"<<endl;int q;for(;;){cout<<"请输入（1~3）"<<endl;cin>>q;bool x=0;switch (q){case 1:h.init(d);break;case 2:h.init1(d);h.CreateCodeTable();h.Encoding(s,d);h.Decoding(s,d);break;case 3:cout<<"编码前的长度为:"<<h.count1()<<endl;cout<<"编码后的长度为:"<<h.count2()<<endl;cout<<"压缩比为:"<<(h.count2()*1.0/h.count1())<<endl;break;default:cout<<"请输入选择！！！！！"<<endl;break;}}3.}程序运行结果分析输入：I love data Structure, I love Computer。

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

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

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

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

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

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

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

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

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

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

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

《数据结构》课程设计报告设计题目：多级目录文件检索算法设计姓名___________________学号___________________班级___________________同组组员___________________实验报告日期：一.需求分析（详细说明要实现的功能和功能间的关系）程序旨在实现一个在Linux系统下(以Ubuntu 11.10发行版为蓝本)进行多级目录文件检索的功能。

程序支持传统检索和多星号通配符检索，在搜索结果中给出符合条件文件的文件名，最后修改时间和路径，并按照最后修改时间排序。

程序提供窗口形式的图形界面。

程序运行过程中用户只需手动输入待查的关键字，查找的根路径可以简明的图形界面方式选择。

查找的结果在窗口中显示，允许用户对显示窗口的大小进行任意调节，并使用滚动条查看不能完全显示的部分。

二.算法思想（对于实现较为复杂的功能，要写出所使用的算法和算法的思路）1- 文件查找程序递归调用一个子函数Filesearch(ENTRYPTR LIST, char* input, const char *dir_name)来实现对文件的查找，其思想近于树的先根遍历。

每到达一层目录程序均读取文件名（Linux 下文件夹也被看做是一个文件）并调用KMP算法进行匹配（节点访问过程），然后判定当前文件的性质（宏S_ISDIR），若该“文件”确实是一个文件，则停止向下遍历返回上一层；若该“文件”是一个文件夹，那么进入该文件夹递归遍历下一层。

2- 模式匹配程序使用KMP算法进行文件名和模式的匹配。

该算法首先分析模式的特征（重复性）并生成一个next数组，然后根据next数组的指示在主串上滑动模式进行匹配。

这种算法可以避免对不可能匹配的情况进行比对，从而降低模式匹配过程的时间复杂度。

3- 通配符程序中调用了如下函数const* strtok(char* str1, char* str2);这个函数的作用是按照str2对str1进行分割。

北邮数据结构答案【篇一：北邮数据结构实验报告实验二含源码】验名称：实验二——栈和队列学生姓名：申宇飞班级： 2012211103班内序号： 03学号： 2012210064日期： 2013年11月18日1．实验要求1.1实验目的：通过选择下面五个题目之一进行实现，掌握如下内容：? 进一步掌握指针、模板类、异常处理的使用? 掌握栈的操作的实现方法? 掌握队列的操作的实现方法? 学习使用栈解决实际问题的能力? 学习使用队列解决实际问题的能力1.2实验内容题目1根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。

要求：1、实现一个共享栈2、实现一个链栈3、实现一个循环队列4、实现一个链队列编写测试main()函数测试线性表的正确性。

2. 程序分析2.1 存储结构链栈：栈的链式存储结构,其实现原理类似于单链表，结点结构与单链表相同，但链栈在实现时直接采用栈顶指针指向栈顶元素。

datanexttop栈顶关键算法分析链栈：一、入栈操作算法步骤：自然语言描述：1、建立新结点2、给p结点的数据域赋值3、修改p结点的指针域，将其指向栈顶结点4、栈顶指针指向p结点伪代码描述：1）nodet * s = new nodet;2）p-data = x;3）p-next = top;4）top = p;二、出栈操作算法步骤：自然语言描述：1、判断栈是否为空2、保存栈顶结点的数据域3、定义指针p指向栈顶结点4、栈顶指针指向下一个结点5、释放p结点伪代码描述：1）if(empty())throw下溢;2）t x = top-data;3）nodet * p = top;4）top = top-next;5）elete p;三、链栈的取栈顶元素栈底算法步骤：自然语言描述:1、判断栈是否为空2、定义指针p指向栈顶结点3、返回栈顶元素的值，不删除伪代码描述1)if(empty())throw下溢;2)nodet*p=top;3)coutp-data;四、遍历链栈元素算法步骤：自然语言描述：1、定义指针p指向栈顶结点2、判断栈是否为空3、返回栈元素的值4、把下一个指针的值赋给p伪代码描述：1）nodet*p = top;2）while(p != null)3）cout p-data ;4）p = p-next;五、析构函数算法步骤：自然语言描述：1、判断栈顶指针是否为空2、定义指针p指向栈顶结点3、把下一个指针的值赋给栈顶指针4、释放要释放的指针伪代码描述：1）while(top)2）struct node t * p = top;3）top = top-next;4）delete p;时间复杂的：o(1)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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