数据结构折半查找递归算法

#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

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

数据结构折半查找源代码

源代码：

折半查找：

#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();

折半查找及其改进

一、问题描述

查找是在一个数据元素集合中查找关键字等于某个给个数据元素关键字的过程，也称为检索。给出一个特定的元素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、折半查找的算法思想是以处于区间中间位置记录的关键字和给定值比较，若相等，则查找成功，如不等，则缩小范围，直至新的区间中间位置记录的关键字等于给

实验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

N矩阵的n次方运算及折半查找报告--数据结构(C语言)内含程序代码

数据结构作业报告

—①N矩阵的n次方运算报告

—②折半查找报告

姓名：江海强 班级：070921班 学号：07092007

上机时间：2010-9-29 报告时间：2010-9-10

N矩阵的n次方运算及折半查找报告--数据结构(C语言)内含程序代码

摘要

1.实验目的

本实验主要是让我们了解函数的调用与返回，理解递归函数的执行过程，学会利用递归函数解决实际问题。

2.实验方法

①本程序利用全局数组变量b[N][N]来统筹整个程序，有一个主函数和一个子函数，其中子函数为矩阵换算的函数，也作为递归函数。而递归就是本程序的主要实验方法。

②本程序也定义了一个全局指针变量*mid，也是有一个主函数和一个子函数，其中子函数为折半查找的函数，也作为递归函数。而递归也就是本程序的主要实验方法。

3.实验结果

①由运行出来的结果可以看出，即使为一次方，此矩阵运算的结果与实际运算得到的结果完全是一样，所以此程序是正确的，成功的。

②由运行出来的结果可以看出，折半查找所找到的数的位置经过验证也是正确、无误的。即使输入要查找的数不在数组中，则程序会输出error来说明查找失败。故此程序也是正确的，成功的。

注：这两个程序是用C

实验七 查找

一、实验目的

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

折半查找算法及程序实现

一、教材分析

教学重点：以图示法方式，演示折半查找算法的基本思想。

教学难点：由折半查找算法的思想到程序代码编写的转换，尤其是其中关键性语句的编写是教学中的难点。

二、学情分析

学生应该已经掌握程序设计的基本思想，掌握赋值语句、选择语句、循环语句的基本用法和VB基本操作，这节课学生可能会遇到的最大问题是：如何归纳总结对分查找解决不同情况问题的一般规律，鉴于此，在教学中要积极引导学生采取分解动作、比较迁移等学习策略。

三、教学目标

知识与技能：理解对分查找的概念和特点，通过分步解析获取对分查找的解题结构，初步掌握对分查找算法的程序实现。

过程与方法：通过分析多种不同的可能情况，逐步归纳对分查找的基本思想和方法，确定解题步骤。

情感态度与价值观：通过实践体验科学解题的重要性，增强效率意识和全局观念，感受对分查找算法的魅力，养成始终坚持、不断积累才能获得成功的意志品质。

四、教学策略与手段

1、教学线索：游戏引领---提出对分查找原理--- 解析对分查找的算法特征---实践解决问题。

2、学习线索：分解问题---归纳问题---实践提升，在三个阶段的不断推进中明确对分查找算法，总结规律。

五、教学过程

1、新课导入

（1）热身

第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. -

前五章习题算法

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. 顺序