数据结构实验查找和排

数据结构查找实验报告数据结构查找实验报告1·实验目的本实验旨在研究不同的查找算法在不同数据结构下的性能表现，通过实验结果对比分析，选取最优算法来完成查找操作。

2·实验方法2·1 数据结构选择在本实验中，我们选择了常用的数据结构进行查找性能比较，包括线性表、二叉树、哈希表等。

2·2 查找算法选择我们选择了以下常用的查找算法进行实验：●顺序查找●二分查找●插值查找●二叉查找树●平衡二叉查找树（AVL树）●哈希查找3·实验过程3·1 实验环境设置首先，我们需要搭建合适的实验环境，包括编程语言选择、编译器、开发环境等。

在本次实验中，我们选择了C++编程语言，并使用了Visual Studio 2019作为开发环境。

3·2 实验步骤为了比较各个查找算法的性能，我们按照以下步骤进行实验： 1·创建用于查找的数据结构，并初始化数据集合。

2·调用每个查找算法进行查找，并记录查找耗时。

3·分析实验结果，比较各个查找算法的性能。

4·实验结果与分析根据实验步骤中记录的各个查找算法的耗时，我们得到了以下结果：●对于小规模数据集，顺序查找表现较好。

●对于有序数据集，二分查找和插值查找表现最佳。

●对于动态数据集，哈希表的查找效率最高。

5·结论根据实验结果与分析，我们得出以下结论：●不同的数据结构适用于不同的查找需求。

●在静态有序数据集中，二分查找和插值查找是较好的选择。

●在动态数据集中，哈希表具有较高的查找效率。

附件：附件1：实验数据集附件2：查找算法代码法律名词及注释：1·数据结构：数据之间的组织方式和关系，使得我们可以高效地进行数据的存储和操作。

2·查找算法：在给定某个目标值的情况下，在给定数据集内寻找目标值的算法。

3·顺序查找：逐个比较目标值和数据集内的元素，直到找到目标值或者遍历完整个数据集。

实验六、七：查找、排序算法的应用班级 10511 学号 20103051114 姓名高卫娜一、实验目的1 掌握查找的不同方法，并能用高级语言实现查找算法。

2 熟练掌握顺序表和有序表的顺序查找和二分查找方法。

3 掌握排序的不同方法，并能用高级语言实现排序算法。

4 熟练掌握顺序表的选择排序、冒泡排序和直接插入排序算法的实现。

二、实验内容1 创建给定的顺序表。

表中共包含八条学生信息，信息如下：学号姓名班级C++ 数据结构1 王立03511 85 762 张秋03511 78 883 刘丽03511 90 794 王通03511 75 865 赵阳03511 60 716 李艳03511 58 687 钱娜03511 95 898 孙胜03511 45 602 使用顺序查找方法，从查找表中查找姓名为赵阳和王夏的学生。

如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。

3 使用二分查找方法，从查找表中查找学号为7和12的学生。

如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。

（注意：创建静态查找表时必须按学号的从小到大排列！）4 使用直接插入排序方法，对学生信息中的姓名进行排序。

输出排序前和排序后的学生信息表，验证排序结果。

5 使用直接选择排序方法，对学生信息中的C成绩进行排序。

输出排序前和排序后的学生信息表，验证排序结果。

6 使用冒泡排序方法，对学生信息中的数据结构成绩进行排序。

输出排序前和排序后的学生信息表，验证排序结果。

7 编写一个主函数，将上面函数连在一起，构成一个完整程序。

8 将实验源程序调试并运行。

三、实验结果源程序代码为：#include<iostream.h>#include<string.h>#include <stdlib.h>#define MAXSIZE 10typedef char KeyType1;typedef int KeyType2;typedef struct{//学号姓名班级C++ 数据结构KeyType1 name[20];KeyType2 xuehao;KeyType1 Class[20];double score[2];} DataType;typedef struct{DataType data[MAXSIZE+1];int len;} SeqList;//顺序表的创建void create(SeqList &L){cout<<"请输入顺序表的大小:"<<endl;cin>>L.len;cout<<"请输入顺序表中八条学生信息（学号姓名班级C++ 数据结构）:"<<endl;for(int i=1;i<=L.len;i++){cin>>L.data[i].xuehao;cin>>L.data[i].name;cin>>L.data[i].Class;cin>>L.data[i].score[0];cin>>L.data[i].score[1];}}void Input(SeqList &L){for(int i=1;i<=L.len;i++){cin>>L.data[i].xuehao;cin>>L.data[i].name;cin>>L.data[i].Class;cin>>L.data[i].score[0];cin>>L.data[i].score[1];}}//顺序表的显示void print(SeqList L){cout<<"学号姓名班级C++ 数据结构"<<endl;if(L.len==0){cout<<"该表是空表！"<<endl;return;}for(int i=1;i<=L.len;i++){cout<<" "<<L.data[i].xuehao<<" "<<L.data[i].name<<" "<<L.data[i].Class<<" "<<L.data[i].score[0]<<" "<<L.data[i].score[1];cout<<endl;}}//顺序查找方法从查找表中查找姓名为赵阳和王夏的学生void S_Search(SeqList L){char na[20];cout<<"请输入要查找的同学的姓名："<<endl;cin>>na;strcpy(L.data[0].name,na); //监视哨int i=L.len;while(strcmp(L.data[i].name,na)>0||strcmp(L.data[i].name,na)<0)i--;if(i>0){cout<<"您要查找的学生的信息："<<endl; cout<<"学号姓名班级C++ 数据结构"<<endl;cout<<" "<<L.data[i].xuehao<<" "<<L.data[i].name<<" "<<L.data[i].Class<<" "<<L.data[i].score[0]<<" "<<L.data[i].score[1];cout<<endl;}if(i<=0){cout<<"对不起，没有该同学的信息！"<<endl;}}//二分查找方法从查找表中查找学号为7和12的学生//非递归void Binary_Search(SeqList &L){int kx;cout<<"请输入您要查找的学生信息的学号："<<endl;cin>>kx;int low=1,high=L.len,mid;while(low<=high){mid=(low+high)/2;if(L.data[mid].xuehao==kx){cout<<"您要查找的学生的信息："<<endl; cout<<"学号姓名班级C++ 数据结构"<<endl;cout<<" "<<L.data[mid].xuehao<<" "<<L.data[mid].name<<" "<<L.data[mid].Class<<" "<<L.data[mid].score[0]<<" "<<L.data[mid].score[1];cout<<endl;break;}else if(L.data[mid].xuehao>kx)high=mid-1;elselow=mid+1;}if(low>high){cout<<"没有该学号的学生信息！"<<endl;}}//直接插入排序方法对顺序表直接插入排序的算法对学生信息中的姓名进行排序：void InsertSort( SeqList &L ){int i, j;for( i=2; i<=L.len; i++ )if(strcmp(L.data[i].name, L.data[i-1].name)<0){L.data[0]=L.data[i]; // 复制为哨兵for(j=i-1; strcmp(L.data[0].name, L.data[j].name)<0; j-- )L.data[j+1]=L.data[j]; // 记录后移L.data[j+1]=L.data[0]; // 插入到正确位置}print(L);}//直接选择排序方法对学生信息中的C成绩进行排序void SelectSort(SeqList &L){int i, j,k;DataType temp;for( i=1; i<L.len; i++ ){k = i;for( j=i+1; j<=L.len; j++ )if( L.data[j].score[0] < L.data[k].score[0] )k = j ;if( k != i ){temp = L.data[i];L.data[i] = L.data[k];L.data[k] =temp;}}print(L);}//冒泡排序方法对学生信息中的数据结构成绩进行排序void BubbleSort(SeqList &L){int i,j,flag=1;DataType x;for(i=1;((i<L.len)&&(flag==1));i++){flag=0;for(j=1;j<L.len-i+1;j++)if(L.data[j].score[1]>L.data[j+1].score[1]){x=L.data[j];L.data[j]=L.data[j+1];L.data[j+1]=x;flag=1;}}print(L);}void main(){SeqList L;int a;cout<<endl;while(a!=0){cout<<endl;cout<<"-------------------------欢迎使用学生信息系统----------------------------\n"<<endl;cout<<endl;cout<<" 1 ：录入学生信息 2 ：按姓名查找学生信息3：按学号查找学生信息"<<endl;cout<<endl;cout<<" 4 ：按姓名排序后学生信息5 ：按c成绩排序学生信息"<<endl;cout<<endl;cout<<" 6 ：按数据结构成绩排序后学生信息7 ：显示0 ：退出"<<endl;cout<<endl;cout<<"--------------------------------------------------------------------------"<<endl;cout<<endl;cout<<"输入您的选择为：";cin>>a;switch(a){case 1:{ create(L); break; }case 2: //顺序查找方法从查找表中查找姓名为赵阳和王夏的学生{ S_Search(L); break; }case 3:{ Binary_Search(L); break; }case 4:{cout<<"对学生信息中的姓名进行排序为："<<endl;InsertSort(L);break;}case 5:{cout<<"对学生信息中的C成绩进行从低到高排序为："<<endl;SelectSort(L);break;}case 6:{cout<<"对学生信息中的数据结构成绩进行从低到高排序为："<<endl;BubbleSort(L);break;}case 7:{ print(L); break; }case 0: exit(0);default:{cout<<"您输入的序号不正确，请重新输入："<<endl;break;}}}}建立顺序表的运行结果为图1-1：图1-1录入学生信息查找的运行结果如图1-2,图1-3：图1-2按姓名查找图1-3按学号查询排序的运行结果如下图1-4,图1-5,图1-6：图1-4按姓名排序图1-5按c成绩排序图1-6按数据结构成绩排序结束结果如图1-7:图1-7推出程序四、实验总结（1）exit(0)需要头文件#include<stdlib.h>退出程序；（2）比较字符串使用头文件#<string.h>中得strcmp（）；复制字符串使用strcpy（）；（3）从表的一端开始，向另一端逐个将给定值x与关键码进行比较；使用折半查找的前提：查找表必须是有序表；在有序表中，取中间元素作为比较对象（4）直接插入排序是一种稳定的排序方法。

数据结构实验报告实验第四章：实验: 简单查找算法一．需求和规格说明：查找算法这里主要使用了顺序查找，折半查找，二叉排序树查找和哈希表查找四种方法。

由于自己能力有限，本想实现其他算法，但没有实现。

其中顺序查找相对比较简单，折半查找参考了书上的算法，二叉排序树查找由于有之前做二叉树的经验，因此实现的较为顺利，哈希表感觉做的并不成功，感觉还是应该可以进一步完善，应该说还有很大的改进余地。

二．设计思想：开始的时候提示输入一组数据。

并存入一维数组中，接下来调用一系列查找算法对其进行处理。

顺序查找只是从头到尾进行遍历。

二分查找则是先对数据进行排序，然后利用三个标志，分别指向最大，中间和最小数据，接下来根据待查找数据和中间数据的比较不断移动标志，直至找到。

二叉排序树则是先构造，构造部分花费最多的精力，比根节点数据大的结点放入根节点的右子树，比根节点数据小的放入根节点的左子树，其实完全可以利用递归实现，这里使用的循环来实现的，感觉这里可以尝试用递归。

当二叉树建好后，中序遍历序列即为由小到大的有序序列，查找次数不会超过二叉树的深度。

这里还使用了广义表输出二叉树，以使得更直观。

哈希表则是利用给定的函数式建立索引，方便查找。

三．设计表示：四．实现注释：其实查找排序这部分和前面的一些知识联系的比较紧密，例如顺序表的建立和实现，顺序表节点的排序，二叉树的生成和遍历，这里主要是中序遍历。

应该说有些知识点较为熟悉，但在实现的时候并不是那么顺利。

在查找到数据的时候要想办法输出查找过程的相关信息，并统计。

这里顺序查找和折半查找均使用了数组存储的顺序表，而二叉树则是采用了链表存储的树形结构。

为了直观起见，在用户输入了数据后，分别输出已经生成的数组和树。

折半查找由于只能查找有序表，因此在查找前先调用函数对数据进行了排序。

在查找后对查找数据进行了统计。

二叉排序树应该说由于有了之前二叉树的基础，并没有费太大力气，主要是在构造二叉树的时候，要对新加入的节点数据和跟数据进行比较，如果比根节点数据大则放在右子树里，如果比根节点数据小则放入左子树。

电子科技大学实验报告课程名称：数据结构与算法学生姓名：学号：点名序号：指导教师：实验地点：基础实验大楼实验时间： 5月20日2014-2015-2学期信息与软件工程学院实验报告（二）学生姓名学号：指导教师：实验地点：基础实验大楼实验时间：5月20日一、实验室名称：软件实验室二、实验项目名称：数据结构与算法—排序与查找三、实验学时：4四、实验原理：快速排序的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。

一躺快速排序的算法是：1）设置两个变量I、J，排序开始的时候I：=1，J：=N2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；3）从J开始向前搜索，即（J：=J-1），找到第一个小于X的值，两者交换；4）从I开始向后搜索，即（I：=I+1），找到第一个大于X的值，两者交换；5）重复第3、4步，直到I=J。

二分法查找（折半查找）的基本思想：（1）确定该区间的中点位置：mid=（low+high）/2min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置（2）将待查a值与结点mid的关键字（下面用R[mid].key）比较，若相等，则查找成功，否则确定新的查找区间：A)如果R[mid].key>a，则由表的有序性可知，R[mid].key右侧的值都大于a，所以等于a的关键字如果存在，必然在R[mid].key左边的表中,这时high=mid-1;B)如果R[mid].key<a,则等于a的关键字如果存在，必然在R[mid].key右边的表中。

数据结构排序实验报告数据结构排序实验报告引言：数据结构是计算机科学中的重要概念之一，它涉及到数据的组织、存储和操作方式。

排序是数据结构中的基本操作之一，它可以将一组无序的数据按照特定的规则进行排列，从而方便后续的查找和处理。

本实验旨在通过对不同排序算法的实验比较，探讨它们的性能差异和适用场景。

一、实验目的本实验的主要目的是通过实际操作，深入理解不同排序算法的原理和实现方式，并通过对比它们的性能差异，选取合适的排序算法用于不同场景中。

二、实验环境和工具实验环境：Windows 10 操作系统开发工具：Visual Studio 2019编程语言：C++三、实验过程1. 实验准备在开始实验之前，我们需要先准备一组待排序的数据。

为了保证实验的公正性，我们选择了一组包含10000个随机整数的数据集。

这些数据将被用于对比各种排序算法的性能。

2. 实验步骤我们选择了常见的五种排序算法进行实验比较，分别是冒泡排序、选择排序、插入排序、快速排序和归并排序。

- 冒泡排序：该算法通过不断比较相邻元素的大小，将较大的元素逐渐“冒泡”到数组的末尾。

实现时，我们使用了双重循环来遍历整个数组，并通过交换元素的方式进行排序。

- 选择排序：该算法通过不断选择数组中的最小元素，并将其放置在已排序部分的末尾。

实现时，我们使用了双重循环来遍历整个数组，并通过交换元素的方式进行排序。

- 插入排序：该算法将数组分为已排序和未排序两部分，然后逐个将未排序部分的元素插入到已排序部分的合适位置。

实现时，我们使用了循环和条件判断来找到插入位置，并通过移动元素的方式进行排序。

- 快速排序：该算法通过选取一个基准元素，将数组分为两个子数组，并对子数组进行递归排序。

实现时，我们使用了递归和分治的思想，将数组不断划分为更小的子数组进行排序。

- 归并排序：该算法通过将数组递归地划分为更小的子数组，并将子数组进行合并排序。

实现时，我们使用了递归和分治的思想，将数组不断划分为更小的子数组进行排序，然后再将子数组合并起来。

注意事项：在磁盘上创建一个目录，专门用于存储数据结构实验的程序。

因为机房机器有还原卡，请同学们将文件夹建立在最后一个盘中，以学号为文件夹名。

实验八查找和排序一、实验目的掌握运用数据结构两种基本运算查找和排序,并能通过其能解决应用问题。

二、实验要求1．掌握本实验的算法。

2．上机将本算法实现。

三、实验内容为宿舍管理人员编写一个宿舍管理查询软件, 程序采用交互工作方式,其流程如下:建立数据文件，数据结构采用线性表，存储方式任选（建议用顺序存储结构），数据元素是结构类型（学号，姓名，性别，房号），元素的值可从键盘上输入，可以在程序中直接初始化。

数据文件按关键字（学号、姓名、房号）进行排序（排序方法任选一种），打印排序结果。

（注意字符串的比较应该用strcmp(str1,str2)函数）查询菜单: (查找方法任选一种)1. 按学号查询2. 按姓名查询3. 按房号查询打印任一查询结果（可以连续操作）。

参考：typedef struct {char sno[10];char sname[2];int sex; //以0表示女，1表示男int roomno;}ElemType;struct SqList{ElemType *elem;int length;};void init(SqList &L){L.elem=(ElemType *)malloc(MAXSIZE*sizeof(ElemType));L.length=0;}void printlist(SqList L){ int i;cout<<" sno name sex roomno\n";for(i=0;i<L.length;i++)cout<<setw(7)<<L.elem[i].sno<<setw(10)<<L.elem[i].sname<<setw(3)<<L.elem[i].sex<<setw(6) <<L.elem[i].roomno<<endl;}。

北京物资学院信息学院实验报告
课程名_数据结构与算法
实验名称查找与排序
实验日期年月日实验报告日期年月日姓名______ ___ 班级_____ ________ 学号___
一、实验目的
1.掌握线性表查找的方法；
2.了解树表查找思想；
3.掌握散列表查找的方法.
4.掌握插入排序、交换排序和选择排序的思想和方法；
二、实验内容
查找部分
1.实现顺序查找的两个算法（P307）, 可以完成对顺序表的查找操作, 并根据查到和未查到两种情况输出结果；
2.实现对有序表的二分查找；
3.实现散列查找算法(链接法)，应能够解决冲突；
排序部分
4.分别实现直接插入排序、直接选择排序、冒泡排序和快速排序算法
三、实验地点与环境
3.1 实验地点
3.2实验环境
(操作系统、C语言环境)
四、实验步骤
（描述实验步骤及中间的结果或现象。

在实验中做了什么事情, 怎么做的, 发生的现象和中间结果, 给出关键函数和主函数中的关键段落）
五、实验结果
六、总结
（说明实验过程中遇到的问题及解决办法；个人的收获；未解决的问题等）。

实验五查找得实现一、实验内容1、建立一个线性表,对表中数据元素存放得先后次序没有任何要求.输入待查数据元素得关键字进行查找。

为了简化算法,数据元素只含一个整型关键字字段,数据元素得其余数据部分忽略不考虑.建议采用前哨得作用，以提高查找效率。

2、查找表得存储结构为有序表,输入待查数据元素得关键字利用折半查找方法进行查找.此程序中要求对整型量关键字数据得输入按从小到大排序输入。

二、源代码与执行结果1、＃inclｕｄｅ〈ｉoｓtreａm>ｕsiｎg namespace stｄ；＃defｉne MAX １０0＃deｆinｅ KｅyTｙpe iｎｔtypｅｄef stｒuct{ＫｅｙＴｙpe key ；｝DataTｙpe；typedef struｃt{ﻩDaｔaＴyｐｅ elem[ＭAX］ ;iｎｔlength ；}SeqTａble ，＊PSeｑTable ；PSeｑTable Ｉniｔ_SｅqＴable（){ﻩＰSｅqTable p ＝（ＰＳｅｑTable）malｌoc(ｓizeof（SeｑTable)) ;ﻩiｆ（p ！＝ＮULＬ）｛p->lｅｎgtｈ = 0 ；ﻩｒｅｔｕrnｐ；}ﻩelsｅ｛ﻩｃｏｕt〈<"Ouｔｏf space!”〈〈endl ；ﻩrｅtuｒn NＵＬL;ﻩ}｝int insert＿SeqTable（PSeｑTable p,KeｙType x){ｉｆ(ｐ-＞length〉= ＭＡX）ﻩ｛ﻩcｏｕt〈<”ｏverｆｌow！"<<endl ;ﻩreｔuｒn 0 ；ﻩ}ｐ—>ｅlem[ｐ—＞leｎgｔh］、key＝ x ;p-〉ｌｅｎｇtｈ+＋；reｔurｎ 1 ;｝iｎｔ SｅqSｅarch（SｅqTａble s ,KｅｙTypｅk){ﻩｉnt n ， i = ０；ﻩn = s、ｌength ；s、eleｍ［n］、ｋeｙ =ｋ ;ﻩwhilｅ（s、eｌem[i］、key ！= k）ﻩﻩi ＋+ ;ﻩif(i == n）retｕrn —1 ；elseﻩﻩrｅturn i ;}ｖoidｍain（）｛PSeｑTabｌe ｐ ;intｉ , ｎ；ﻩKeyＴype a ;p =Ｉnit_ＳｅqTaｂｌｅ（）；ﻩｃout<〈"请输入数据个数：" ;ｃin＞>n ；couｔ〈＜＂请输入数据：”＜〈endｌ ;fｏr(ｉ = 0 ; ｉ＜ n ;ｉ＋+）ﻩ{ﻩciｎ〉＞a ；ﻩinsert_SｅqTaｂle（p , a）；｝ﻩcｏut＜＜"请输入要查找得数据，输入3２76７结束：” ；cin〉〉ａ ;ﻩwｈiｌｅ（a ！= ３27６７)ﻩ｛i =SｅｑSearcｈ(*p， a) ；ｉf（i == -１）{ﻩﻩﻩcｏｕt＜＜”无此数据!请重新输入：＂<〈ｅｎｄl ；ﻩﻩcin＞＞a ；ﻩ｝ﻩﻩeｌｓeﻩﻩ｛ﻩcout＜〈"该数据得位置就是：＂〈<i+1<<enｄｌ；ﻩcouｔ〈＜＂请输入要查找得数据：" ；ﻩﻩｃiｎ〉〉ａ；ﻩ}ﻩ｝｝2、＃incｌｕde<iosｔream>usinｇ naｍespace stｄ；#defｉne MAX 100＃dｅfine KeyTyｐe ｉｎtｔyｐedef sｔruct{KeyTｙpe key ；｝ＤataTypｅ；typedeｆ stｒuｃt｛ﻩDataType ｅｌem［MAX] ；ﻩinｔ length ；}BinTａbｌe ,＊PBｉnＴabｌe ;PBinTabｌｅ Iniｔ_BiｎTablｅ（）｛ﻩPBinＴable p = (PBiｎTabｌe)mａlloｃ（sizeof(ＢinTable）) ;if(p ！= ＮULＬ)｛p->length= ０；ﻩﻩｒeturn p ；ﻩ}eｌseﻩ{ﻩｃout〈<＂Ｏｕt ｏｆ spａｃe！"〈＜endl ;rｅturｎ NUＬL ;ﻩ｝｝int iｎsｅｒt＿BinTａble（PBinTａble p ，ＫｅyTｙpe x）{ｉf（p—〉ｌｅnｇth ＞＝ MAX)｛ﻩｃoｕt<＜"ｏｖerflow!”<〈ｅnｄl ;ﻩreturn 0 ;ﻩ}ﻩp－〉ｅlｅm［p—＞lｅngtｈ］、key =x ;ｐ->ｌengtｈ ++ ；ﻩreturn １；}int ＢinSearｃh（BinTable s ，KeyTｙpe k）｛ﻩint lｏw,mid , ｈiｇｈ；ﻩloｗ = 0 ；high = s、lｅngth-1 ;ｗｈile（low ＜= hiｇh）{ﻩﻩmid＝(ｌow+higｈ）／2 ；ﻩif(s、ｅlｅm［mｉd]、kｅy== k)ﻩﻩﻩretｕrｎｍiｄ;ﻩｅlse ｉｆ（s、elem[mｉd］、ｋｅy ＞ｋ）ﻩﻩhiｇh＝ mｉｄ－ 1 ;ﻩﻩｅlｓeﻩlow = mid +1 ；ﻩ｝ﻩrｅturn —1；}ｖoiｄ main（)｛PBinTablｅ p ；ﻩintｉ ,n ；ﻩKeyType ａ;p ＝Iｎit＿BinＴable（）;ｃｏuｔ<<”请输入数据个数：”;ｃｉn〉＞n；ﻩｃout<〈"请按从小到大得顺序输入数据：”〈<ｅndｌ；fｏr(i = 0 ；ｉ〈 n; i ++）ﻩ｛ｃin>〉a;ﻩinsert_BinTable（ｐ，a）;｝ﻩcout＜<＂请输入要查找得数据,输入32767结束：” ;ﻩcin〉＞ａ ;whilｅ（a！= 3２767){ﻩi =BｉｎSeaｒｃh（*p , ａ）；iｆ（ｉ =＝-1）ﻩ{ﻩﻩcｏut〈〈＂无此数据！请重新输入:＂〈〈ｅndl ;ｃiｎ>>a;ﻩ}ﻩelｓe{ﻩcout＜<"该数据得位置就是：”〈<i+1〈＜ｅndl ；ﻩﻩﻩｃｏut＜〈”请输入要查找得数据:" ；cin＞〉a ;}ﻩ}｝。

一、实验目的本次实验旨在让学生掌握数据结构的基本概念、逻辑结构、存储结构以及各种基本操作，并通过实际编程操作，加深对数据结构理论知识的理解，提高编程能力和算法设计能力。

二、实验内容1. 线性表（1）顺序表1）初始化顺序表2）向顺序表插入元素3）从顺序表删除元素4）查找顺序表中的元素5）顺序表的逆序操作（2）链表1）创建链表2）在链表中插入元素3）在链表中删除元素4）查找链表中的元素5）链表的逆序操作2. 栈与队列（1）栈1）栈的初始化2）入栈操作3）出栈操作4）获取栈顶元素5）判断栈是否为空（2）队列1）队列的初始化2）入队操作3）出队操作4）获取队首元素5）判断队列是否为空3. 树与图（1）二叉树1）创建二叉树2）遍历二叉树（前序、中序、后序）3）求二叉树的深度4）求二叉树的宽度5）二叉树的镜像（2）图1）创建图2）图的深度优先遍历3）图的广度优先遍历4）最小生成树5）最短路径三、实验过程1. 线性表（1）顺序表1）初始化顺序表：创建一个长度为10的顺序表，初始化为空。

2）向顺序表插入元素：在顺序表的第i个位置插入元素x。

3）从顺序表删除元素：从顺序表中删除第i个位置的元素。

4）查找顺序表中的元素：在顺序表中查找元素x。

5）顺序表的逆序操作：将顺序表中的元素逆序排列。

（2）链表1）创建链表：创建一个带头结点的循环链表。

2）在链表中插入元素：在链表的第i个位置插入元素x。

3）在链表中删除元素：从链表中删除第i个位置的元素。

4）查找链表中的元素：在链表中查找元素x。

5）链表的逆序操作：将链表中的元素逆序排列。

2. 栈与队列（1）栈1）栈的初始化：创建一个栈，初始化为空。

2）入栈操作：将元素x压入栈中。

3）出栈操作：从栈中弹出元素。

4）获取栈顶元素：获取栈顶元素。

5）判断栈是否为空：判断栈是否为空。

（2）队列1）队列的初始化：创建一个队列，初始化为空。

2）入队操作：将元素x入队。

3）出队操作：从队列中出队元素。

《数据结构》实验报告排序实验题目：输入十个数，从插入排序，快速排序，选择排序三类算法中各选一种编程实现。

实验所使用的数据结构内容及编程思路：1.插入排序：直接插入排序的基本操作是，将一个记录到已排好序的有序表中，从而得到一个新的，记录增一得有序表。

一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列r［1..i-1］中插入一个记录r［i］后，变成含有i个记录的有序子序列r［1..i］；并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在r［0］处设置哨兵。

在自i-1起往前搜索的过程中，可以同时后移记录。

整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。

2.快速排序：基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

假设待排序的序列为{L.r[s]，L.r[s+1],…L.r[t]},首先任意选取一个记录(通常可选第一个记录L.r[s])作为枢轴（或支点）（pivot），然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较大的记录都安置在它的位置之后。

由此可以该“枢轴”记录最后所罗的位置i作为界线，将序列{L.r[s]，…，L.r[t]}分割成两个子序列{L.r[i+1],L.[i+2],…,L.r[t]}。

这个过程称为一趟快速排序，或一次划分。

一趟快速排序的具体做法是：附设两个指针low和high，他们的初值分别为low和high，设枢轴记录的关键字为pivotkey，则首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两不直至low=high为止。