数据结构查找综合应用实验报告

数据结构查找实验报告

【篇一：数据结构查找算法实验报告】

数据结构实验报告 实验第四章：

实验: 简单查找算法

一．需求和规格说明：

查找算法这里主要使用了顺序查找，折半查找，二叉排序树查找和哈希表查找四种方法。由于自己能力有限，本想实现其他算法，但没有实现。其中顺序查找相对比较简单，折半查找参考了书上的算法，二叉排序树查找由于有之前做二叉树的经验，因此实现的较为顺利，哈希表感觉做的并不成功，感觉还是应该可以进一步完善，应该说还有很大的改进余地。 二．设计思想：

开始的时候提示输入一组数据。并存入一维数组中，接下来调用一系列查找算法对其进行处理。顺序查找只是从头到尾进行遍历。二分查找则是先对数据进行排序，然后利用三个标志，分别指向最大，中间和最小数据，接下来根据待查找数据和中间数据的比较不断移动标志，直至找到。二叉排序树则是先构造，构造部分花费最多的精力，比根节点数据大的结点放入根节点的右子树，比根节点数据小的放入根节点的左子树，其实完全可以利用递归实现，这里使用的循环来实现的，感觉这里可以尝试用递归。当二叉树建好后，中序遍历序列即为由小到大的有序序列，查找次数不会超过二叉树的深度。这里还使用了广义表输出二叉树，以使得更直观。

一、实验目的和要求

1理解串的一般线性表之间的差异。

2重点掌握在顺序串上和链串上实现串的基本运算算法。 3掌握串的简单匹配算法和KMP算法。

4灵活运用串这种数据结构解决一些综合应用问题。

二、实验环境、内容和方法

实验内容：

1实现顺序串的各种基本运算。 2实现链串的各种基本运算。

3实现顺序串的各种模式匹配运算。 4求一个串中出现的第一个最长重复串。 实验方法：

通过上机操作完成各内容。 实验环境：

实验用PC机一台，使用操作系统为Windows XP Professional，安装OFFICE 2003、VC++等软件。

三、实验过程描述

实验题4.1实现顺序串各种基本运算的算法

编写一个程序algo4-1.cpp，实现顺序串的各种基本运算，并在此基础上设计一个程序exp4-1.cpp 完成如下功能：

1建立串谁“abcdefghefghefghijklmn”和串s1=”xyz”; 2输出串s; 3输出串s的长度；

4在串s的第9个字符位置插入串s1而产生串s2; 5输出串s2;

6删除串s第2个字符开始的5个字符替换成串s1而产生串s2； 7输出串s2;

8将串s第2个字符开始的5个字符替换成串s1而产生串s2; 9

实验4查找

一、实验目的或任务

通过指导学生上机实践，对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。

二、实验教学基本要求

1.了解实验目的及实验原理；

2.编写程序，并附上程序代码和结果图；

3.总结在编程过程中遇到的问题、解决办法和收获。

三、实验教学的内容或要求

1.编写函数,建立有序表,采用折半查找实现某一已知的关键字的查找(采用顺序表存储结构)

2.编写函数,随机产生一组关键字,利用二叉排序树的插入算法建立二叉排序树

3.编写函数,在以上二叉排序树中删除某一指定关键字元素

4.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法

四、实验类型或性质

验证性

五、实验开出要求

必做

六、实验所需仪器设备

1.计算机

2.相关软件（如C,C++,PASCAL,VC,DELPHI等等）

七、实验所用材料

计算机耗材

一、程序运行界面：

二、源程序

#define _CRT_SECURE_NO_W ARNINGS

#include<stdio.h>

#include<malloc.h>

#define MAXNODE 256

typedefstruct Node

{

int data;

str

淮海工学院计算机科学系

实验报告书

课程名： 《数据结构》

题 目： 查找、排序的应用实验

班 级：

学 号： ^ ^

姓 名：

排序、查找的应用实验报告要求

1目的与要求:

1）查找、排序是日常数据处理过程中经常要进行的操作和运算，掌握其算法与应用对于提

高学生数据处理能力和综合应用能力显得十分重要。

2）本次实验前，要求同学完整理解有关排序和查找的相关算法和基本思想以及种算法使用

的数据存储结构；

3）利用C或C++语言独立完成本次实验内容或题目，程序具有良好的交互性（以菜单机制

实现实验程序的交互运行）和实用性；

4）本次与第七次实验已合二为一，实验结果在机房现场验收和评分，希望同学们认真对待，并于2009年12月20日按时提交本次实验报告（含电子和纸质报告），任何同学不得拖延。

5）如果验收时间紧张，不能再正课时间完成者，由老师择机决定另行通知专门验收时间。凡无故不主动或拖延验收者，均按照不及格处理。

5）认真书写实验报告（包括程序清单及相关实验数据与完整运行结果），并于按时提交。 2 实验内容或题目

题目：对数据序列（查找表）：{55，13，23，72，109，67，2，78,13}分别实现如下操作：

1) 顺序查找；

2) 分别使用直

实验七 查找

一、实验目的

1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。 2、掌握线性表中顺序查找和折半查找的方法。

3、学会哈希函数的构造方法，处理冲突的机制以及哈希表的查找。

二、实验内容和要求

1. 静态查找表技术

依据顺序查找算法和折半查找算法的特点，对下面的两个查找表选择一个合适的算法，设计出完整的C源程序。并完成问题：

查找表1 ： { 8 ，15 ，19 ，26 ，33 ，41 ，47 ，52 ，64 ，90 } ，查找key = 41 查找表2 ： {12 ，76 ，29 ，15 ，62 ，35 ，33 ，89 ，48 ，20 } ，查找key =35 查找key=41的比较次数： 查找key=35的比较次数： ? 算法实现代码

1

2、哈希表的构造与查找

/* 采用开放地址法构造哈希表*/ #include #include #define MAXSIZE 25 #define P 13 #define OK 1 #define ERROR 0

#define DUPLICATE -1

2

#define TRUE 1 #define FALSE 0

ty

本科生实验报告

实验课程 数据结构（C语言版） 学院名称 成都理工大学 专业名称 测控技术与仪器 学生姓名 学生学号 指导教师 实验地点 实验成绩

二〇一五年 五 月二〇一五 年 七月

实验一：成绩的顺序表实现

（1）问题描述

建立自己的成绩表,利用顺序表及链表两种方式实现,要求实现的基本操作有：插入新成绩，删除成绩，寻找指定科目成绩及输出功能。

（2）数据结构设计

a．逻辑结构设计

以链表形式存储，链表头存姓名、学号，用结构体No1实现，其指针指向存科目、成绩的结构体No2，而No2指向No2类型，以实现多科目存储。 b．物理逻辑设计

链式存储方式

（3）算法设计

a.算法列表 序号 1 2 名称 create insert 函数表示符 create(Sqlist *m,int n) 操作说明 创建成绩表 insert(NAME1 *head,int n,char 插入成绩 z[10],double gra) 3 del del(NAME1 *head,char sm[10]) 删除成绩 4 dislayelement dislayelement(NAME1 *head,char

本科生实验报告

实验课程 数据结构（C语言版） 学院名称 成都理工大学 专业名称 测控技术与仪器 学生姓名 学生学号 指导教师 实验地点 实验成绩

二〇一五年 五 月二〇一五 年 七月

实验一：成绩的顺序表实现

（1）问题描述

建立自己的成绩表,利用顺序表及链表两种方式实现,要求实现的基本操作有：插入新成绩，删除成绩，寻找指定科目成绩及输出功能。

（2）数据结构设计

a．逻辑结构设计

以链表形式存储，链表头存姓名、学号，用结构体No1实现，其指针指向存科目、成绩的结构体No2，而No2指向No2类型，以实现多科目存储。 b．物理逻辑设计

链式存储方式

（3）算法设计

a.算法列表 序号 1 2 名称 create insert 函数表示符 create(Sqlist *m,int n) 操作说明 创建成绩表 insert(NAME1 *head,int n,char 插入成绩 z[10],double gra) 3 del del(NAME1 *head,char sm[10]) 删除成绩 4 dislayelement dislayelement(NAME1 *head,char

实验目的

（1）学会用先序创建一棵二叉树。

（2）学会采用递归算法对二叉树进行先序、中序、后序遍历。 （3）学会打印输出二叉树的遍历结果。

实验内容

【问题描述】建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。 【基本要求】

从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。 【测试数据】

ABCффDEфGффFффф(其中ф表示空格字符) 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA 【选作内容】

采用非递归算法实现二叉树遍历。

实验步骤

（一）需求分析

1、在这个过程中，接受遍历的二叉树是从键盘接受输入（先序），以二叉链表作为存储结构，建立的二叉树。因此，首先要创建一棵二叉树，而这棵二叉树是先序二叉树。本演示程序中，集合的元素设定为大写字母ABCDEFG，输出的先序，中序，后序遍历分别为ABCDEGF,CBEGDFA,CGBFDBA。二叉树可以表示为：

接受的输入数据在进行递归的先序，中序，后序遍历后，分别将结果打印出来。

2、在程序运行的过程中可以看到，以计算机提示用户执行的方式进行下去，即在计算机终端上提示“

数据结构实验报告

实验名称： 实验3.5 利用队列结构实现车厢重排问题+

学生姓名： 李思敏

班 级： 2011211108

班内序号： 18

学 号： 2011210233

日 期： 2012年11月13日

1． 实验要求

实验目的：

② 熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法；

②学习指针、模版类、异常处理的使用；

③ 掌握线性表的操作实现方法；

④培养使用线性表解决实际问题的能力。

实验要求：

② 要有异常处理；

②保持良好的编程风格：

· 代码段之间要有空行和缩进；

· 标示符名称应该与其代表的意义一致；

· 函数名之前应该添加注释说明该函数功能；

· 关键代码应说明其功能。

2. 程序分析

2.1 存储结构

采用链式存储结构存储车厢原始信息，利用尾插法构建带尾指针和头指针的单循环链表。

2.2 关键算法分析

关键算法1.建立循环链表

单链表的插入操作

front rear rear

① 若链表中只有一个数据节点，则头指针front和尾指针rear都指向此节点；

② 若链表中不止一个节点，头指针front指向第一个数据节点，使用尾插法构建

?数 据 结 构?

《数据结构》实验报告五

实验内容： 简单查找类算法的应用和比较——顺序查找和折半查找 学号： 姓名： [题目] 学生成绩表已按成绩非递增有序排列，请分别用顺序查找和折半查找算法，找出指定成绩的学生信息，并分别指出所用的比较次数。给出查找成功和不成功两种情况。 一、问题分析及设计思想： 先要设计一个学生的顺序表，再进行查找，顺序查找（从表的一端开始，一次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后，仍未找到关键字和给定值相等的记录，则查找失败）；折半查找（从表的中间记录开始，如果给定值和中间纪录的关键字相等，则查找成功；如果给定值大于或小于中间记录的关键字，则在表中大于或小于中间记录的那一半中查找，这样重复操作，直到查找成功，或者在某一步中查找区间为空，则代表查找失败）。 二、存储结构定义： #include #include #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0