太原理工大学软件工程《数据结构实验报告4-查找》

数据结构查找实验报告数据结构查找实验报告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·顺序查找：逐个比较目标值和数据集内的元素，直到找到目标值或者遍历完整个数据集。

实验四——查找一、实验目的1.掌握顺序表的查找方法，尤其是折半查找方法；2.掌握二叉排序树的查找算法。

二、实验内容1.建立一个顺序表，用顺序查找的方法对其实施查找；2.建立一个有序表，用折半查找的方法对其实施查找；3.建立一个二叉排序树，根据给定值对其实施查找；4.对同一组数据，试用三种方法查找某一相同数据，并尝试进行性能分析。

三、实验预习内容实验一包括的函数有：typedef struct ，创建函数void create(seqlist & L)，输出函数void print(seqlist L)，顺序查找int find(seqlist L,int number)，折半查找int halffind(seqlist L,int number) 主函数main().实验二包括的函数有：结构体typedef struct，插入函数void insert(bnode * & T,bnode * S)，void insert1(bnode * & T)，创建函数void create(bnode * & T)，查找函数bnode * search(bnode * T,int number)，主函数main().四、上机实验实验一：1.实验源程序。

#include<iostream.h>#define N 80typedef struct{int number; //关键字char name[5];char sex[2];int age;}record;typedef struct{record stu[N];int num;//记录人数}seqlist;//建顺序表void create(seqlist & L){int i;L.num=0;cout<<"请依次输入(输入学号为0认定为终止输入):"<<endl;cout<<"学号"<<"\t姓名"<<"\t性别"<<"\t年龄"<<endl;cin>>L.stu[1].number;for(i=1;L.stu[i].number!=0;){cin>>L.stu[i].name>>L.stu[i].sex>>L.stu[i].age;L.num++;cout<<endl;cin>>L.stu[++i].number;}}//输出学生信息void print(seqlist L){int i;cout<<"学生基本信息为:"<<endl;for(i=1;i<=L.num;i++)cout<<"\t"<<L.stu[i].number<<"\t"<<L.stu[i].name<<"\t"<<L.stu[i].sex<<"\t"<<L.stu[i].age<< endl;}//顺序查找int find(seqlist L,int number){int i;for(i=L.num;i>=0;i--)if(L.stu[i].number==number)return i;}//折半查找int halffind(seqlist L,int number){int high=L.num,low=1,mid;for(;low<=high;){mid=(high+low)/2;if(number==L.stu[mid].number)return mid;elseif(number<L.stu[mid].number)high=mid-1;elselow=mid+1;}return 0;}void main(){int i,number;seqlist L;create(L);print(L);cout<<"折半查找:"<<endl;cout<<"输入学生学号:";cin>>number;if((i=halffind(L,number))!=0)cout<<"\t"<<L.stu[i].number<<"\t"<<L.stu[i].name<<"\t"<<L.stu[i].sex<<"\t"<<L.stu[i].age<< endl;elsecout<<"失败!"<<endl;cout<<"顺序查找:"<<endl;cout<<"输入学生学号:";cin>>number;if((i=find(L,number))!=0)cout<<"\t"<<L.stu[i].number<<"\t"<<L.stu[i].name<<"\t"<<L.stu[i].sex<<"\t"<<L.stu[i].age<< endl;elsecout<<"失败!"<<endl;}实验二：#include<iostream.h>typedef struct{int number; //关键字char name[5];char sex[2];int age;}record;typedef struct node{record inf;struct node *lchild,*rchild;}bnode;void insert(bnode * & T,bnode * S){if(!T)T=S;elseif(S->inf.number<T->inf.number)insert(T->lchild,S);elseinsert(T->rchild,S);}void insert1(bnode * & T){int flag=1; int number; bnode * u; char ctinue;for(;flag==1;){cout<<"依次输入(学号为0默认为结束输入):"<<endl;cout<<"学号"<<"\t姓名"<<"\t性别"<<"\t年龄"<<endl;cin>>number;while(number){u=new bnode;u->inf.number=number;cin>>u->>>u->inf.sex>>u->inf.age;u->lchild=u->rchild=NULL;insert(T,u);cin>>number;}cout<<"继续插入(Y/N):";cin>>ctinue;if(ctinue=='y'||ctinue=='y')flag=1;elseflag=0;}}void create(bnode * & T){bnode * u;int number;T=NULL;cout<<"依次输入(学号为0默认为结束输入):"<<endl;cout<<"学号"<<"\t姓名"<<"\t性别"<<"\t年龄"<<endl;cin>>number;while(number){u=new bnode;u->inf.number=number;cin>>u->>>u->inf.sex>>u->inf.age;u->lchild=u->rchild=NULL;insert(T,u);cin>>number;}}bnode * search(bnode * T,int number){if(T==NULL||T->inf.number==number)return T;elseif(T->inf.number>number)return search(T->lchild,number);elsereturn search(T->rchild,number);}void main(){int number,flag=1,choice; char ctinue;bnode * T,*p;for(;flag==1;){cout<<"\t1.建立二叉排序树"<<"\n\t2.插入学生信息"<<"\n\t3.查找学生信息"<<endl;cout<<"选择:";cin>>choice;switch(choice){case 1:{create(T);cout<<"成功建立!"<<endl;};break;case 2:{insert1(T);cout<<"插入成功!"<<endl;};break;case 3:{cout<<"输入待查学生的学号:";cin>>number;p=search(T,number);if(p)cout<<p->inf.number<<"\t"<<p-><<"\t"<<p->inf.sex<<"\t"<<p->inf.age<<endl;elsecout<<"查找失败!"<<endl;};break;}cout<<"Continue(Y/N):";cin>>ctinue;if(ctinue=='y'||ctinue=='y')flag=1;elseflag=0;}}2.实验结果（截图）。

本科实验报告课程名称：软件需求工程实验项目：软件需求课程实验实验地点：行勉楼A304 专业班级：学号：学生姓名：指导教师：2016年5月18日实验一需求分析实验一、实验目的1、要求学生根据实际项目的要求，应用传统的结构化方法或者面向对象方法进行需求分析；2、通过实验了解和掌握UML和Rataional等工具的使用方法。

二、实验设备：PC机、Windows操作系统、UML和Rational等工具软件。

三、实验内容：1、熟悉和掌握UML和Rational Rose工具的使用。

在rose中创建新的模型，分别画出如下的图：用例图、类图、包图、活动图、顺序图、状态图等。

2、根据如下项目，对系统进行需求分析。

具体要求，绘制系统的用例对用例进行规格说明，绘制类图、活动图、顺序图和状态图等。

四、实验步骤1、安装Rational Rose。

2、根据问题目标、业务背景、问题陈述（描述）等（此信息可以根据项目名称从网上搜索），确定系统的参与者Actor（用户），从用户角度确定系统相关功能用例Usecase，做出用例图。

3、针对每个功能用例使用《用例描述模板》，进行描述。

4、分别使用活动图、顺序图描述用例执行过程。

五、实验结果1、安装Rational Rose。

成功安装了UML软件。

2、根据问题目标、业务背景、问题陈述（描述）等（此信息可以根据项目名称从网上搜索），确定系统的参与者Actor（用户），从用户角度确定系统相关功能用例Usecase，做出用例图。

（一）选题1：学生选课系统项目背景：本系统实现学生选课的基本功能，包括学生退选课，查看自己的选课信息；教师查看选课学生的信息，提交成绩；管理员添加学生、管理学生、管理成绩、添加教师、管理教师和管理课程等。

实现学生选课的动态管理，使得对信息的管理更加及时、高效，提高了效率。

用例图：用户：学生：管理者：类图：时序图：管理者：学生：协作图：老师：学生：（二）选题2：图书管理系统项目背景：本系统实现图书管理的基本功能，包括学生借书退书，查看自己的借书信息；管理员添加学生、管理学生和管理书籍等。

实验报告四课程名称：数据结构实验名称：数据结构实验地点：计算机110机房专业班级：计科Z1501 学号：2015001909 学生姓名：刘元瑞指导教师：孟亮2016年12 月26日1.序实现下面运算：在二叉排序树中查找关键字为key的记录。

#include <stdio.h>#include <malloc.h>#include <Windows.h>//构造二叉排序树的结点typedef struct sort{int a; //关键字struct sort *L_node;//其左孩子struct sort *R_node;//其右孩子}Sort, *Sort_;Sort_ Structure();//接收用户输入的数据构造二叉排序树Sort_ Find(Sort_ BS_tree, int a);//查找部分void main(){int t;Sort_ Record;Sort_ BS_tree = Structure();//调用函数构造二叉排序树printf("请输入要查找的关键字!\n");scanf("%d", &t);if((Record = Find(BS_tree, t)))printf("所要找的记录为%d", Record->a);system("pause");}//接收用户输入的数据构造二叉排序树Sort_ Structure(){Sort_ BS_tree= (Sort_)malloc(sizeof(Sort));Sort_ p, s, q;int t;BS_tree->L_node = BS_tree->R_node = NULL;printf("请按照任意顺序输入二叉树的结点，输入0时结束！\n");scanf("%d",&t);if(t!=0){BS_tree->a = t;}scanf("%d", &t);while(t!=0){p = BS_tree;q = (Sort_)malloc(sizeof(Sort));q->a = t;q->L_node = q->R_node = NULL;//查找要插入部分if(t>p->a) s = p->R_node;else if(t<p->a) s = p->L_node;else s = NULL;while(s != NULL){p = s;if(t>p->a) s = p->R_node;else if(t<p->a) s = p->L_node;else s = NULL;}if(p->a != t){if(t > p->a) p->R_node = q;else p->L_node = q;}scanf("%d", &t);}return BS_tree;}//查找部分Sort_ Find(Sort_ BS_tree, int a){Sort_ s;Sort_ p = BS_tree;if(a>p->a) s = p->R_node;else if(a<p->a) s = p->L_node;else return p;while(s != NULL){p = s;if(a>p->a) s = p->R_node;else if(a<p->a) s = p->L_node;else return p;}printf("查找不成功!\n");return NULL;}2．试将折半查找的算法改写成递归算法。

实验名称：线性表一．目的与要求本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。

要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后独立完成后面的实习题。

二．例题[问题描述]用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出字符串。

[输入]初始字符串，插入位置，插入字符，删除字符。

[输出]已建立链表（字符串），插入字符后链表，删除字符后链表，逆转后链表。

[存储结构]采用链式存储结构[算法的基本思想]建立链表：当读入字符不是结束符时，给结点分配存储空间，写数据域，将新结点插到表尾；插入字符：根据读入的字符在链表中找插入位置，将新结点插入到该位置之前；删除字符：根据读入的删除字符在链表中找到被删结点后，将其从链表中删除；链表逆转：从链表的第一个结点开始对所有结点处理，将每个结点的前驱变为它的后继；打印链表：从链表的第一个结点开始，依次打印各个结点的数据域。

[参考源程序]#define NULL 0typedef struct node{char a;struct node *link;}node,*nodelink;void readlink(nodelink head){nodelink p,q;char c;p=head;printf("Input a linktable(a string):");scanf("%c",&c);if (c=='\n') printf("This string is empty。

");while(c!='\n'){q=(nodelink)malloc(sizeof(node));q->a=c;p->link=q;p=q;scanf("%c",&c);}p->link=NULL;}void writelink(nodelink head){nodelink q;if (head->link==NULL) printf(" This link is empty。

太原理工软件工程实习报告一、实习背景与目的随着信息技术的快速发展，软件工程成为现代科技领域中的重要研究方向。

为了提高自身的实践能力和专业素养，我选择了太原理工大学的软件工程实习项目。

本次实习旨在通过实际操作，深入了解软件开发流程，掌握软件工程的核心技术，并培养团队合作和解决问题的能力。

二、实习内容与过程在实习期间，我参与了太原理工大学软件实验室的一个实际项目开发。

以下是实习的主要内容与过程：1. 项目启动：在实习的开始阶段，导师为我们介绍了项目的背景和需求。

我们通过讨论和分析，明确了项目的目标、功能要求和性能要求。

2. 需求分析：我们小组成员共同参与需求分析工作，通过与导师和客户的沟通，明确了用户需求和系统功能。

我们使用UML图和用例图工具，对系统的功能进行详细的描述和文档化。

3. 设计阶段：在需求分析的基础上，我们开始进行系统设计。

我负责设计和实现系统的数据库部分，包括数据库表的创建、关系的建立和SQL语句的编写。

4. 编码阶段：根据设计文档，我开始编写代码。

我使用了Java语言和MySQL数据库，实现了系统的核心功能。

在编码过程中，我注重代码的可读性和可维护性，遵循了软件工程的最佳实践。

5. 测试阶段：在编码完成后，我们进行了系统的测试。

我负责编写测试用例，并与其他成员一起进行测试。

我们发现了一些问题，并通过调试和优化，解决了这些问题。

6. 项目总结与汇报：在项目完成后，我们进行了项目总结和汇报。

我向导师和同学们展示了自己的工作成果，并分享了在实习过程中的收获和体会。

三、实习收获与反思通过本次实习，我对软件工程的核心技术和开发流程有了更深入的了解。

我掌握了UML图和用例图的使用，熟悉了Java语言和MySQL数据库的操作。

同时，我也学会了团队合作和解决问题的能力。

在实习过程中，我也意识到了自己在一些方面的不足之处。

例如，我在需求分析阶段的沟通能力和表达能力有待提高。

此外，我在代码编写和调试过程中，还需要更加注重细节和规范，以提高代码的质量和稳定性。

数据结构查找实验报告数据结构查找实验报告1. 简介查找是计算机科学中一种常见的操作，它用于在一组数据中快速定位特定的元素。

数据结构是计算机存储、组织数据的方式，可以有效地支持查找操作。

本实验报告将介绍查找算法的原理和实现，以及实验结果的分析和总结。

2. 查找算法2.1 顺序查找顺序查找是一种简单直观的查找算法，它从数据集的第一个元素开始逐个比较，直至找到目标元素或遍历完所有元素。

顺序查找的时间复杂度为O(n)，其中n是数据集的大小。

2.2 二分查找二分查找是一种高效的查找算法，它要求数据集必须是有序的。

它通过将数据集分成两部分，并与目标元素进行比较，以确定目标元素所在的区间，然后在该区间内继续二分查找，直至找到目标元素或确定目标元素不存在。

二分查找的时间复杂度为O(log n)，其中n是数据集的大小。

2.3 插值查找插值查找是对二分查找的一种改进，它根据目标元素的估计位置来确定比较的起始位置。

它适用于数据集分布均匀的情况，可以进一步减少查找的次数。

插值查找的时间复杂度为O(log(log n))。

3. 实验结果本次实验我们使用了三种查找算法（顺序查找、二分查找和插值查找）在不同大小的数据集上进行了性能测试。

实验结果如下表所示：---- 数据集大小 ---- 顺序查找时间（ms） ---- 二分查找时间（ms） ---- 插值查找时间（ms） ---------------------------------------------------------------------------------------------- 1000 ---- 10 ---- 2 ---- 1 -------- 10000 ---- 100 ---- 4 ---- 2 -------- 100000 ---- 1000 ---- 6 ---- 3 -------- 1000000 ---- 10000 ---- 8 ---- 4 ----从实验结果可以看出，随着数据集的增大，顺序查找的时间成正比增加，而二分查找和插值查找的时间相对较稳定。

数据结构查找算法实验报告数据结构查找算法实验报告---------------------------------1.引言在计算机科学中，查找算法是一种用于在数据集合中寻找特定元素的算法。

查找算法在各种应用中广泛使用，例如数据库检索，关键字搜索等。

本次实验旨在研究和探索不同的数据结构查找算法，如线性查找、二分查找、哈希查找等，并比较它们的性能和适用场景。

2.线性查找2.1 算法原理线性查找又称为顺序查找，它从数据集合的起始位置开始，逐个比较元素直到找到目标元素或遍历完整个集合。

线性查找是最简单的查找算法，但效率较低，时间复杂度为O(n）2.2 算法步骤●从数组的第一个元素开始遍历，依次比较元素与目标元素是否相等。

●如果相等，返回目标元素的索引值。

●如果遍历完整个数组仍未找到目标元素，返回未找到的标志。

2.3 算法实现```function linearSearch(arr, target) {for (let i = 0。

i < arr.length。

i++) {if (arri === target) {return i。

}}return -1。

}```3.二分查找3.1 算法原理二分查找是一种高效的查找算法，要求数据集合必须有序。

它通过重复将数据集合一分为二，直到找到目标元素或确定目标元素不存在。

二分查找的时间复杂度为O(log n）3.2 算法步骤●将数据集合的起始位置和结束位置分别设为low和high。

●计算中间位置mid，并将mid元素与目标元素进行比较。

●如果mid元素等于目标元素，则返回mid。

●如果mid元素大于目标元素，则将high设为mid-1。

●如果mid元素小于目标元素，则将low设为mid+1。

●重复以上步骤，直到low大于high或找到目标元素。

3.3 算法实现```function binarySearch(arr, target) {let low = 0。

数据结构查找实验报告一、实验目的本次实验的主要目的是深入理解和掌握常见的数据结构查找算法，包括顺序查找、二分查找、哈希查找等，并通过实际编程实现和性能比较，分析它们在不同数据规模和分布情况下的效率和适用场景。

二、实验环境本次实验使用的编程语言为 Python 38，开发环境为 PyCharm。

实验中所使用的数据集生成工具为 numpy 库。

三、实验原理1、顺序查找顺序查找是一种最简单的查找算法，它从数据结构的开头依次逐个比较元素，直到找到目标元素或遍历完整个数据结构。

其平均时间复杂度为 O(n)。

2、二分查找二分查找要求数据结构是有序的。

通过不断将查找区间缩小为原来的一半，直到找到目标元素或者确定目标元素不存在。

其时间复杂度为 O(log n)。

3、哈希查找哈希查找通过将元素映射到一个特定的哈希表中，利用哈希函数计算元素的存储位置，从而实现快速查找。

理想情况下，其平均时间复杂度为 O(1)，但在存在哈希冲突时，性能可能会下降。

四、实验步骤1、数据集生成使用 numpy 库生成不同规模和分布的数据集，包括有序数据集、无序数据集和具有一定重复元素的数据集。

2、顺序查找实现编写顺序查找算法的函数，接受数据集和目标元素作为参数，返回查找结果（是否找到及查找次数）。

3、二分查找实现实现二分查找算法的函数，同样接受数据集和目标元素作为参数，并返回查找结果。

4、哈希查找实现构建哈希表并实现哈希查找函数，处理哈希冲突的情况。

5、性能比较对不同规模和类型的数据集，分别使用三种查找算法进行查找操作，并记录每种算法的查找时间和查找次数。

五、实验结果与分析1、顺序查找在无序数据集中，顺序查找的性能表现较为稳定，查找时间随着数据规模的增大线性增长。

但在有序数据集中，其性能没有优势。

2、二分查找二分查找在有序数据集中表现出色，查找时间随着数据规模的增大增长缓慢，体现了对数级别的时间复杂度优势。

然而，在无序数据集中无法使用。