数据结构查找算法总结

实验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、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。 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

第9章 排序

排序{ R1 , R2 , R3 , . . . , Rn } { K 1 , K2 , K 3 , . . . , Kn }

设 n 个记录的序列为 其相应的关键字序列为

若规定 1 , 2 , 3 , . . . , n 的一个排列 p1 , p2 , p3 , . . . , pn , 使得相应的关键字满足如下非递减关系: Kp ≤ K p ≤ K p ≤ . . . ≤ Kp1 2 3 n

则原序列变为一个按关键字有序的序列: { Rp , Rp , Rp , . . . , Rp }1 2 3n

此操作过程称为排序。

第9章 排序

稳定排序与不稳定排序

假设 Ki = Kj ,且排序前序列中 Ri 领先于 Rj ; 若在排序后的序列中 Ri 仍领先于 Rj ,则称排序方法是 稳定的。 若在排序后的序列中 Rj 仍领先于 Ri ,则称排序方法是 不稳定的。 例，序列 3 15 8 8 6 9

若排序后得 3若排序后得 3

66

88

88

99

1515

稳定的不稳定的

第9章 排序

内部排序与外部排序

内部排序: 指的是待排序记录存放在计算机随机存储 器中进行的排序过程。 外部排序: 指的是待排序记录的数量很大，以致内存 一次不能容纳全部记录，在排序过程

折半查找及其改进

一、问题描述

查找是在一个数据元素集合中查找关键字等于某个给个数据元素关键字的过程，也称为检索。给出一个特定的元素x，在含有n个元素的数列中判断是否存在这个元素，如果存在，返回此元素在数列中的位置，否则返回零。数列查找在实际中的应用十分广泛，因此数列查找算法的好坏直接影响到程序的优劣。本设计要求读取文件中的数据建立查找表,并设计算法实现折半查找及其改进查找。

二、基本要求

1、选择合适的存储结构，读取已知文件数据建立查找表； 2、完成基于递归和非逆归的折半查找算法的设计； 3、完成基于区间约束对折半查找算法的改进算法的设计； 4、完成三分查找算法的设计。

三、测试数据

文件in.txt中100个数据：1,2,3…98,99,100。 1、 读取文件in.txt中前50位数，查找元素:58 2、 读取文件in.txt中前50位数，查找元素:18 3、 读取文件in.txt中前100位数，查找元素：18 4、 读取文件in.txt中前100位数，待查元素：58

四、算法思想

1、折半查找的算法思想是以处于区间中间位置记录的关键字和给定值比较，若相等，则查找成功，如不等，则缩小范围，直至新的区间中间位置记录的关键字等于给

数据结构——折半查找源代码

数据结构折半查找源代码

源代码：

折半查找：

#include<iostream.h>//cout,cin

#include"process.h"//exit()

#include"stdio.h"//EOF,NULL

typedef int T; //定义关键字的类型,这里就以整形来处理

//查找表类定义

template <class T>

struct Node

{

T key; //关键字域

/*

........ //其他域,可以自己根据需要添加

*/

};

template <class T>

class SSearch {

private:

Node<T> *ST;

int len;//表长

public:

SSearch();//

~SSearch();//析构函数，删除表空间

void Create(int n); //创建时根据用户实际需求,再为相应的数据元素赋值 void Display(); //输出静态表中的数据元素

int SeSearch(T key); //从表中最后一个元素开始顺序查找

void Ascendsort();

第9章查找

一、单选题

1. 对一棵二叉搜索树按（）遍历，可得到结点值从小到大的排列序列。

A. 先序

B. 中序

C. 后序

D. 层次

2. 从具有n个结点的二叉搜索树中查找一个元素时，在平均情况下的时间复杂度大致为（）。

A. O(n)

B. O(1)

C. O(logn) D. O(n2)

3. 从具有n个结点的二叉搜索树中查找一个元素时，在最坏情况下的时间复杂度为（）。

A. O(n)

B. O(1)

C. O(logn)

D. O(n2)

4. 在二叉搜索树中插入一个结点的时间复杂度为（）。

A. O(1)

B. O(n)

C. O(logn)

D. O(n2)

5. 分别以下列序列构造二叉搜索树，与用其它三个序列所构造的结果不同的是（）。

A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D.（100，80， 60， 90， 120，130，110）

6. 在一棵AVL树中，每个结点的平衡因子的取值范围是（）。

A. -

#include #include #include

typedef int Elemtype;

void caidan() //菜单函数 {

printf(\欢迎来到查找实验！\\n\ printf(\实验内容：\\n\

printf(\1)建立一个无序表并实现其上的顺序查找；\\n\

printf(\2)建立一个有序表并实现其上的折半查找（用递归和非递归两种算法实现）。\\n\

printf(\ printf(\顺序查找·····\\n\ printf(\折半查找递归···\\n\ printf(\折半查找非递归··\\n\ printf(\退出·······\\n\ printf(\ printf(\请选择：\}

int SeqSeach(Elemtype a[],int n, Elemtype key) //顺序查找 {

int i;

for (i=0;i

if (key==a[i]) {

return i+1; } }

return 0; }

void shuchu(Elemtype a[]) //输出函数 {

int i;

printf(\数组里的数据：\\n\ for (i=0

前五章习题算法

2.2

算法设计题

1.设计一个算法从一给定的有序顺序表L中删除元素值在X到Y(X<=Y)之间的所有元素,要求以较高的效率实现,要求算法的空间复杂度为O(1) void delete(SqList &L,ElemType x,ElemType y) {

int i=0,k=0;

while(i=x &&L.elem[i]

L.length=L.length-k; }

2设一个有序表L,含有2n个整数,其中n个位负数,n个为正数,设计一个算法将L中所有元素按正负相间排列. 要求算法的空间复杂度为O(1),时间复杂度为O(n) void move(SqList &L) {

int i=0,j=L.length-1; int temp;

while(i0)i++; while(i

while(i

} }

3.假设一两个元素依之=值递增有序排列的线性表A和B分别表示两个集合(同一 元素值各不相同),要求分别设计求A和B交并差集的算法,要求结果线形表中的元素依值递增有序排列,试对顺序表实现上述操作. 交集:

void intersection(SqList A,SqList B ,SqList &C) {

int i=0,j=0,k=0;

while(iB.elem[j]) j++; else { C.elem[k]=A.elem[i]; k++;i++;j++;} //共同

一.选择题（共15题，每题3分）

（1）下面关于算法说法错误的是_______。 a. 算法最终必须由计算机程序实现

b. 为解决某问题的算法同为该问题编写的程序含义是相同的 c. 算法的可行性是指指令不能有二义性 d. 以上几个都是错误的 （2）下面说法错误的是______.

a. 算法原地工作的含义是指不需要任何额外的辅助空间

b. 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 c. 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 d. 同一个算法，实现语言的级别越高，执行效率就越低 （3）在下面的程序段中，对x的赋值语句的频度为_____。 for (int i; i

a. 0(2n) b. 0(n) c. 0(n2) d. O(log2n) （4）下面说法正确的是______。 a. 数据元素是数据的最小单位； b. 数据元素是数据的最小单位；

c. 数据的物理结构是指数据在计算机内的实际存储形式 d. 数据结构的抽象操作的定义与具体实现有关 （5）下面说法正确的是_______。

a. 在顺序存储结构中，有时也存储数据结构中元素之间的关系 b. 顺序

淮海工学院计算机科学系

实验报告书

课程名： 《数据结构》

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

班 级：

学 号： ^ ^

姓 名：

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

1目的与要求:

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

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

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

的数据存储结构；

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

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

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

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

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

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

1) 顺序查找；

2) 分别使用直